Research map / Reinforcement learning / MDPs and planning

Transfer Q-Learning with Composite MDP Structures

ICML 2025 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a composite MDP model whose transition core is low-rank plus sparse, and UCB-TQL, a transfer Q-learning algorithm with regret bounds that are dimension-independent when the source task has many more trajectories.

Problem

Transfer RL with high-dimensional transition dynamics where tasks share a low-rank core but differ in sparse task-specific components; existing theory covers only pure low-rank or linear MDPs and value/reward similarity.

Approach

Model transition core as L* + S* (shared low-rank incoherent plus sparse), estimate the shared part from source data, then correct only a sparse difference D on target data, and build a tighter UCB confidence region restricting the sparsity of D, giving regret that scales with sqrt(e) and not the ambient dimension.

Key results

• UCB-TQL achieves regret e O(sqrt(e) H^5 N) when the source has N0 ≍ N^2 trajectories, independent of ambient dimension d.
• Single-task UCB-Q-learning under composite MDPs achieves regret of order sqrt(N H^5) with respect to N and d, matching prior results up to ambient-dimension and sparsity factors.
• Phase transition: when N0 ≥ N(rC_phi^2 + s), the regret is dominated by the sparse-difference correction term.

Measured effects reported in the paper

Limitations

• Theory only, no empirical experiments reported
• Requires incoherence and sparsity assumptions on the low-rank and sparse components
• Assumes known reward function and known sparsity level s0 for the source estimator

Experimental setup

Metrics: cumulative regret

Baselines: Yang & Wang (2020) UCB-Q-learning single-task RL

Builds on: UCB-Q-learning linear mixture MDP (Yang & Wang, 2019) linear factored MDP (Ayoub et al., 2020) REFUEL Chai & Fan (2024) separation lemma

Closest papers by meaning

• The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure (NeurIPS 2024 · similarity 0.89)
• When is Transfer Learning Possible? (ICML 2024 · similarity 0.87)
• Model-Based Transfer Learning for Contextual Reinforcement Learning (NeurIPS 2024 · similarity 0.86)
• Fine-Grained Causal Dynamics Learning with Quantization for Improving Robustness in Reinforcement Learning (ICML 2024 · similarity 0.86)
• Composite Flow Matching for Reinforcement Learning with Shifted-Dynamics Data (NeurIPS 2025 · similarity 0.86)
• Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning (NeurIPS 2025 · similarity 0.86)