Transfer Q-Learning with Composite MDP Structures
Authors: Jinhang Chai
Elynn Chen
Lin Yang
Venue: ICML 2025 poster (2025)
Keywords: Transfer learning
Q learning
UCB Algorithms
Regret analysis
Low-rank plus sparse structure
Primary area: theory->learning_theory

Abstract: To bridge the gap between empirical success and theoretical understanding in transfer reinforcement learning (RL), we study a principled approach with provable performance guarantees. We introduce a novel composite MDP framework where high-dimensional transition dynamics are modeled as the sum of a low-rank component representing shared structure and a sparse component capturing task-specific variations. This relaxes the common assumption of purely low-rank transition models, allowing for more realistic scenarios where tasks share core dynamics but maintain individual variations. We introduce UCB-TQL (Upper Confidence Bound Transfer Q-Learning), designed for transfer RL scenarios where multiple tasks share core linear MDP dynamics but diverge along sparse dimensions. When applying UCB-TQL to a target task after training on a source task with sufficient trajectories, we achieve a regret bound of $\tilde{\mathcal{O}}(\sqrt{eH^5N})$ that scales independently of the ambient dimension. Here, $N$ represents the number of trajectories in the target task, while $e$ quantifies the sparse differences between tasks. This result demonstrates substantial improvement over single task RL by effectively leveraging their structural similarities. Our theoretical analysis provides rigorous guarantees for how UCB-TQL simultaneously exploits shared dynamics while adapting to task-specific variations.

Transfer Q-Learning with Composite MDP Structures
Jinhang Chai
Elynn Chen 2
Lin Yang
Abstract
inefficiency in RL. By leveraging knowledge from related tasks, transfer learning aims to accelerate policy learning and improve performance in new environments without re- quiring extensive data collection. This approach has shown empirical success across various domains, from robotics to game playing, yet theoretical understanding of how transfer provably benefits RL remains limited.
To bridge the gap between empirical success and theoretical understanding in transfer reinforce- ment learning (RL), we study a principled ap- proach with provable performance guarantecs. We introduce a novel composite MDP framework where high dighddimensional transition dynamics are modeled as the sum of low-rank component rep- resenting shared structure and sparse component capturing task-specife variations. This relaxes the common assumption of purely low-rank transi- tion models, allowing for more realistic scenarios where tasks share core dynamics but maintain individual variations. We introduce UCB-TQL (Upper Confidence Bound Transfer Q-Learning) designed for transfer RL scenarios where multiple tasks share core linear MDP dynamics but diverge along sparse dimensions. When applying UCB- TQL to a target task after training on a source task with sufficient trajectories, we achieve a regret bound of O(veHoN) that scales independently of the ambient dimension. Here, N represents the number of trajectories in the target task, while quantifies the sparse differences between tasks. This result demonstrates substantial improvement over single task RL by effectively leveraging their structural similarities. Our theoretical analysis provides rigorous guarantees for how UCB-TQL simultaneously exploits shared dynamics while adapting to task-specific variations.
Consider autonomous vehicle training as an illustrative ex- ample: core driving dynamics including vehicle physics, road rules, and basic navigation remain consistent across different driving scenarios. However, specific environments (urban vs. highway driving, varying weather conditions, dif- ferent traffic patterns) introduce distinct variations to these core dynamies. This naturally suggests modeling transition dynamics as a combination of shared low-rank structure capturing common elements, plus sparse components repre- senting scenario-specific variations.
We propose a composite MDP framework that formalizes this intuition: transition dynamics are modeled as the sum of a low-rank component representing shared structure and sparse component capturing task-specific deviations. This structure appears in many real-world applications beyond autonomous driving robotic manipulation with different objects, game playing across varying environments, and resource management under changing constraints all exhibit similar patterns of core shared dynamics with sparse task- specific variations.
Our approach extends existing work in several important directions. Prior transfer and multi-task RI. research has primarily focused on pure low-rank MDPs (Agarwal et al., 2023; Lu et al., 2021; Cheng et al., 2022) or made direct assumptions about value or reward function similarity (Ca- landriello et al., 2014; Du et al., 2024; Chen et al., 2024; Chai et al., 2025). While sparsity has been studied in the context of value function coefficients, theoretical analysis of sparse transition structures particularly in combina- tion with low-rank components remains unexplored. This gap is significant because transition dynamics often more directly capture task similarity than value functions.
1. Introduction
Transfer reinforcement learning (RL) has emerged as a promising solution to the fundamental challenge of sample
'Department of Operations Research and Financial Engi- neering, Princeton University 'Department of Technology, Op- erations, and Statistics, New York University 'Department of Electrical and Computer Engineering, UCLA. Correspon- dence to: Elynn Chen <clynn,chen @ www.e.n...e.u...... Lin Yang <linyang @ ucla.edu>>.
We begin by addressing single-task learning within this com- posite structure, introducing variant of OCB----leanning tailored specifically for composite MDPs, which may in- volve high-dimensional ambient space. In contrast to
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Transfer Q-Lcarning with Composite MDP Structures
previous work, we consider the high-dimensional setting where the feature dimensions P, Q > number of trajectories N, and the transition core M is no longer low-rank ma- trix. This departure from low-rank structures makes existing algorithms designed for linear MDPs inapplicable. Simi- larly, methods built for low-rank MDPs fail in our context due to the absence of low-rank assumptions in M
how structural similarities in transition dynamics enable effi- cient knowledge transfer. Our results suggest new directions for developing practical algorithms that can systematically leverage shared structure while accounting for task task-specific variations.
1.1. Related Work
Our work provides the first theoretical guarantees for this setting, demonstrating how the algorithm successfully learns both shared and task-specific components. These results extend and complement the existing body of work on low- rank MDPs by explicitly handling structured deviations from low-rank assumptions (Du et al., 2019b; Lattimore et al., 2020). Unlike the approach in (Foster et al., 2021), which introduced a
Transfer RL. (Agarwal et al., 2023) studied transfer via shared representations between source and target tasks, With generative access to source tasks, they showed that learned representations enable fast convergence to near- optimal policies in target tasks, matching performance as if ground truth features were known. (Cheng et al., 2022) proposed REFUEL for multitask representation learning in low-rank MDPs. They proved that learning shared repre- sentations across multiple tasks is more sample-efficient than individual task learning, provided enough tasks are available. Their analysis covers both online and offline downstream learning with shared representations. (Chen et al., 2022; 2024; Chai et al., 2025) analyzed transfer Q- learning without transition model assumptions, focusing instead on reward function similarity and transition density, These works established convergence guarantees for both backward and iterative Q-learnng approaches.
Coefficient (DEC) to characterize the statistical complexity of decision-making across various scenarios, our framework relies on distinct structural assumptions. This necessitates the development of new techniques, as discussed in detail in Section 3.3.
Building on this foundation, we propose UCB-TQL (Upper Confidence Bound Transfer Q-Learning) for transfer learn- ing in composite MDPs. UCB-TQL strategically exploits shared dynamics while efficiently adapting to task-specific variations. Our theoretical analysis demonstrates that UCB- TQL achieves dimension dimension-indeeendeee independent regret bounds that explicitly capture dependencies on both rank and sparsity, showing how structural similarities enable efficient knowl- edge transfer. In particular, we construct a novel confidence region (CR) for the sparse difference, thereby reducing the target sample complexity in the online learning process, as discussed in detail in Section 4.3.
Our work differs by studying transition models with low- rank plus sparse structures. This setting presents unique challenges beyond purely low-rank models, we must identify and leverage an unknown low-rank space while also accounting for sparse deviations.
Single task RL under structured MDPs. Single-task RL under structured MDPs has evolved through several key advances: Linear MDPs with known representations were initially studied by (Yang & Wang. 2020), leading to prov- ably efficient online algorithms (Sun al., 2019; Jin et al., 2020; Zanette et al., 2020; Neu & Pike-Burke 2020; Cai et al., 2020; Wang et al., 2021).
Our primary contributions are as follows.
A novel composite MDP model that combines low- rank shared structure with sparse task-specific compo- nents, while allowing high-dimensional feature spaces. This framework better captures real-world task rela- tionships and provides a foundation for future work in multi-task and meta-learning settings.
Low-rank MDPs extend this by requiring representation learning. Major developments include FLAMBE (Agarwal et al., 2020) for explore-then-comee and REP- (Uehara et al., 2022) for balancing represen- tation learning with exploration. Recent work has expanded to nonstationary settings (Cheng et al., 2023) and model- free approaches like MOFFLE (Modi et al., 2024). Related structured models include block MDPs (Du et al., 9a; Misra et al., 2020; Zhang et al., 2022), low Bellman rank (Jiang et al., 2017), low witness rank (Sun et al., 2019), bilinear classes (Du et al., 2021), and low Bellman cluder dimension (Jin et al., 2021).
transition estimation,
The first theoretical guarantees for single-task RL un- der the high-dimensional composite transition struc- ture, demonstrating how algorithms can effectively leam and utilize both shared and task-specific com- ponents.
A transfer Q-learning algorithm with provable regrel bounds that explicitly characterize how structural simi- larities enable efficient knowledge transfer across tasks.
Our work introduces the composite MDPs with high- dimensional feature space and low-rank plus sparse transi- tion, extending beyond pure low-rank models. We provide
This work represents a significant step toward bridging the gap between empirical success of transfer RL and theo- retical understanding by providing a rigorous analysis of
2

---

Transfer Q-Lcarning with Composite MDP Structures
the first theoretical guarantees for UCB Q-learning under this composite structure.
R evaluates the expected cumulative reward from fol- lowing policy starting from state 8 time h, de- fined as (s) = E The ((w))) sy s] and (*+1 = O. while the action-value function QR S x A + R evaluates the value of taking action in state s at time h, given by (%
Multitask RL and Meta RL. Research in multitask and meta-RL has evolved through several key theoretical ad- vances. Early work by (Calandriello et al., 2014) examined multitask RL with linear Q-functions sharing sparse support, establishing sample complexity bounds that scale with the sparsity rather than ambient dimension. (Hu et al., 2021) ex- tended this framework by studying weight vectors spanning now-dimensional spaces, showing that sample efficiency improves when the rank is much smaller than both the am- bient dimension and number of tasks. (Arora et al., 2020) demonstrated how representation learning reduces sample complexity in imitation learning settings, providing theo- retical guarantees for learning shared structure across tasks. (Lu et al., 2022) further developed this direction by ana- lyzing multitask RL with low Bellman error and unknown representations, establishing bounds that improve with task similarity.
rh a) + Σ# =h+=++1 The ((sx) 8% = 8, on = a and Q7 a) (s) The Bellman equation for V and Q% can be expressed as V - (s, (T, (8)) and
(((s.a)=r((.. a) + |
where (s),) = Eg P(s'|s ss a) (s')('')' The Bellman optimally equations for the optimal value func- tion and action-value function are as follows:
(s) max {ra(s, + (s)),
(% a) = nn rn a) + 1
with + = 0 and (s (s. a) (s)
Task distribution approaches offered another perspective. (Brunskill & Li, 2013) proved sample complexity benefits when tasks are independently sampled from a finite MDP set, while (Pacchiano et al., 2022) and (Müller & Pacchi- ano, 2022) extended these results to meta-RI. for linear mixture MDPs, showing how learned structure transfers to new tasks. In parallel, research on shared representations by (D' D'Eramo et al., 2020) established faster convergence rates for value iteration under common structure, and (Lu et al., 2021) proved substantial sample efficiency gains in the low-rank MDP setting. (Zhang et al., 2025) propose cross-market multi-task dynamic pricing framework that achieves minimax-opiin optimal regret bounds for both linear and nonparametric utilities under structured preference shifts.
The cumulative regret quantifies the performance discrep- ancy of an agent over episodes. Given initial state so ~ p., for the n episode, the regret is the value difference of the optimal policy (*o)s) and the agent's 's chosen policy v*a (50) which based on its experience up to the begin- ning of the nhhh episode and applied throughout the episode. Accumulating over N episodes, is defined as:
(egret(NV) Σ E2 (so) - VT (=o(s))-]
The agent aims to learn a sequence of policies (II,.... TTn) to minimize the cumulative regret. If the reward function has a linear feature representation, any additional regret from an unknown reward becomes a lower-order term and does not affect the regret's overall magnitude. For clarity of presentation, we assume the agent knows the reward function and focus primarily on estimating the transition probability.
Our composite MDP structure advances this line of work by explicitly modeling deviations from low-rank similar- ity through sparse component. This framework captures more realistic scenarios where tasks share core structure but maintain individual variations, opening new theoretical directions for multitask and meta-learning approaches.
Composite MDPs. Let d6-) E IR' and (+)) E R be feature functions where p and q can be large. Consider probabil- ity transitions P(s'|s |ss a) that can be fully embedded in the feature space via a core matrix M
2. Problem Formulation
Episodic MDPs. We consider an episodic Markov decision process (MDP) with finite horizon. It is defined by a tuple M (S,A, P, r, μ. H), where S denotes the state space, A represents the action space, H is the finite time horizon, r S x A + [0, 1] the reward function, P is the state transition probability, and μ is the initial state distribution. Let [ denote the index set 21, H.. A policy क : S x H + A maps each state state-stage pair to an action that
P(s'ss,a) o(s, M (ss)).
Since feature dimensions p and can be large, we need not know the exact feature functions we can include many possible features to span the space. What matters is learning the structure of M from data.
the agent takes in the episode.
Here P is function operator mapping from a function S + R to function S x A + R. One can think of that matrix with dimension S and S in the tabular case.
For each stage h E [/]]. the value function Vē S
3

---

Transfer Q-Lcarning with Composite MDP Structures
To capture how transition dynamies combine shared core elements with scenario-specifie variations, we impose the following structured assumption the transition matrix.
error rates that do not scale with d max(p, q). In con- trast, (Yang & Wang, 2019; Ayoub al., 2020) assume low-dimensional or identifiable parameter spaces and are not suitable for high-ding dithemmimniii regimes. In addition, our structured assumption is especially crucial in transfer RI., enabling effective knowledge sharing via L* while capturing task-specific deviations via S
Definition 2.1 (Composite MDPs), A probability transition model P: : S x A + ((A) can be fully embedded in the feature space characterized by two given feature functions <(+) E R and ())) E IRR where both p and can be large. The core matrix of the transition model decomposes as:
3. Single-Task UCB-Q-Learning under High-Dimensional Composite MDPs
P(s'|s: Is, a) a(s,a)" (L' + (-5 <>s's,
where L is a low-rank incoherent matrix and S* is a sparse matrix.
This section introduces UCB-Q-LLarning for composite MDPs with a high-dimensional feature space. Specifi- cally, we consider the setting where the feature dimensions P, q > N, and the transition core M is no longer low- rank matrix. As result, existing algorithms designed for linear MDPs are not applicable. Likewise, methods tailored for low-rank MDPs fail in our setting due to the absence of a low-rank structure in M To address the challenges arising from our relaxed dimensionality constraints and the more complex MDP structure, novel algorithmic approaches required.
Remark 2.2 (Distinction from linear and low-rank models), The composite MDP model generalizes both linear MDPs and low-rank MDPs. Linear MDPs assume a fixed linear transition structure with known feature maps, while low- rank MDPs drop the need for known features but restrict the transition matrix to be entirely low-rank under some feature representation. In contrast, our composite MDP assumes an unknown feature-bass factorization for a low-rank core as in the low-rank MDP, but augments it with an additional sparse component. This hybrid structure captures more complex transition dynamics and task- task-specific deviations than either linear or low-rank models alone, marking clear departure from those classical assumptions.
For any tuples (Si,h, (i.k) from episode i and stage h: We define diA = 6(sih ai,)), ViiA = ((s,,), and K == Eves (ss")e((s))) T. Our estimator is based on the follow- ing population-Iexee equation at each stage h.
Remark 2.3 (Distinction from classical low-rank settings). Our framework explicitly tackles high-dimensional feature spaces, in contrast to the classical low-rank MDP literature that typically assumes moderate dimensionality (Yang & Wang, 2020; Agarwal et al., 2020). We consider regimes where the feature dimensions (p and q) are significantly larger than the number of trajectories (p, >> N), and cru- cially, the shared transition core M is not constrained to be low-rank. This departure renders existing algorithms for linear or low-rank MDPs inapplicable, since those methods rely a strictly low-rank structure or low feature com- plexity. The digensiilnni composite setting therefore demands new estimation techniques that can leverage the mixed low-rank and sparse structure to achieve efficient learning.
E
W.A k 1 |
8 04.h = Σ (oo'ss,,, K
= Σ + T
oI' +
(1)
This motivates us to use the sample-level counterpart of (1) to estimate Lt and S* in a composite MDP, However, both L and S* are unknown. To recover the low-rank and sparse components, additional assumptions are required to ensure that the low-rank part can be separated from the sparse component. Below, we elaborate on the incoherence assumption and sufficient sparsity conditions.
Remark 2.4 (Relation to prior models). The composite MDP shares a structural philosophy with certain prior models notably the linear mixture MDP frameworks studied by (Yang & Wang, 2019) and (Ayoub et al., 2020)- - in that transitions are factorized via feature maps. Our model can be written in the form of (Yang & Wang, 2019) as IP(s' s, = o(s, a) T a(s') with a(s')= := +'"))''s). This reduces to (Yang& & Wang, 2019) when S* = 0. Simi- larly, our model matches the linear factored MDP in (Ayoub et al., 2020) via a Kronecker formulation: (Pss' a,a) = (Ø(s,a) a) @ vbs')) vCc(L" + S*). While structurally re- lated, a key difference lies in estimation. Our setting allows p.q >> N, and our estimator achieves minimax-optimal
Assumption 3.1. Let L' = --Σ*V=T be the singular value decomposition (SVD) of I.". Let μu be the incoherence parameter (a constant > 1) and r be the rank of L* We assume that: (i) (Incoherence.) 1001 S V p.
MT where the
2- tto-infinity norm || 112,.c denotes the maximum fn-morm of the rows of matrix.
(ii) (Sufficient sparsity.) Matrix S* contains at most non- max(p-g) for some constant zero entries, where s S s == 4Csprs Cs.
Remark 3.2 (Incoherence condition). The incoherence con- dition ensures that the singular vectors of low-rank matrix
4

---

Transfer Q-Lcarning with Composite MDP Structures
not overly concentrated in any single direction or entry, property that is crucial for matrix completion (Candes & Recht, 2012). In our setting, it also facilitates the separation of the sparse component from the low-rank matrix. When r and ja are treated as constants, the maximum permissible sparsity level scales linearly with p. Moreover, as shown in (Candès & Tao, 2010), the incoherence condition holds for a broad class of random matrices.
Algorithm UCB-Q Learning for HD Composite MDPs
Input: Total number of episodes N, feature function & E RR, 2 R". for episode n = 1, .,..,, N do
Construct confidence region in (3) Calculate Qn (8, a) in (5)
for stage h = 1, ... H do
Take action Oz,h = arg maxae Qu,h (Sn,h, a)
Observe next state 8n.h+1 end for
We consider the online learning setting and propose to es- timate L and S* in the composite MDP by optimizing the following hard-constrained least-square objective for each episode n E [A] with collected tuples (ss,hs as,b)) from previous episode E [n]] and stage h E [
Learn transition core estimator Lm 3,, using (2).
end for
by:
(Zn; E arg min L,SER
Σ iE(
MA KT
&i (L + 1)
(nn(s,a)=r(s.d)
+ max a(s,a)T(L ( T Vn,++1 L,SEBa
s.t. L= LEV,,
110|12,000 S
pr
(5)
p
(n, =
1V112,,0 S 115|u S V
where (s) = Hm mmax Qu, a)l, with II truncating values to (0, Hj. Here, V E (8] q is feature matrix, where each row represents the q-dimensional feature vector corresponding
(2)
Remark 3.3 (Computational Efficiency of K v.). When (S] large infinite, we can compute K2p using Monte Carlo
unique state in the state space S. The algorithm is summarized in Algorithm 2.
approximation: R2 = mn E (s;)))(ss)), 8;
Un. This is a standard approach in randomized nu- merical linear algebra (Drineas & Mahoney, 2016) and is computed only once before online learning. Our method is thus comparable in efficiency to (Yang & Wang, 2019), which stores empirical covariances, but we use K to build confidence regions specific to our model.
3.2. Regret Analysis for UCB-Q-Learning under High- -igh-Dimensional Composite MDPs
For the regret analysis, we impose certain regularity condi- tions on the features as outlined below.
Assumption 3.4. Let vi be matrix with rows (b()) Let Co, Cg. C Cap be positive parameters such that
3.1. UCB-Q Learning for High- Sigh--Dimensionl Composite MDPs
(i) (s,a), ( S Co: l10(s a)l S Ca
Since the transition dynamics P are typically unknown, we must leverage observed data to approximate the underlying
(i) | S Cpi
model parameters. To balance the ipploration-exploiaaiiii trade-off, we adopt the optimism-in-thee wwwh-face-of-ueeeeteeeeeeeeeeeee principle by employing an Upper Confidence Bound (UCB)- based algorithm. We begin by constructing the confidence region:
(ii) Yo', l1v(s') K 112 S Cy;
(iv) V(s,a,s)), [ a) (bs')) K |max S Cop.
Lemma 3.5 (Transition Estimation Error). For composite MDPs in Definition 2.1, under Assumption 3. and 3.4, the estimator obtained by solving program (2) at the end of thth episode satisfies, with probability at least 1 1-1111 (/ (n2//nnH))))))) H), that,
B, = ((L || Sn
2
+
S 3 (3)
IIN IEN-L-11
+1 -s-13 S
S.n s
where In and Sn are estimated by (2),
where 3n is defined in (4).
Bn = CgHt (og(dN) (r(CoC))² + s s
(4)
Remark 3.6. Our method handles the high-dimensional set- ting by explicitly exploiting the low-rank -ar--aaa--luusparss struc- ture of the transition core matrix M = = + S", where L* is of low-rank r << and S* is of sparsity << d. This structure enables consistent estimation in regimes where
n
d max (p. /} and Co. Co, Cr Cas are positive parame- ters defined in the regularity Assumption 3.4, Cg is a uni- versal constant. The optimistic value functions are given
5

---

Transfer Q-Lcarning with Composite MDP Structures
p.q > N, and is key our theoretical guarantees. This error bound is minimax optimal with respect to
overcome this, we enforce the strong convexity property by incorporating a restart mechanism for each trajectory.
Theorem 3.7 (Single-Taskk Regret Upper Bound). For com- posite MDPs in Definition 2.1, under Assumption 3.1 and 3.4, let RN) be the accumulative regret of a total of N episodes using the UCB-Q- -CB-Q--earnnng in Algorithm 2. We have that
Thirdly, EE E Φi,h term forms a martingale difference sequence, we apply matrix concentration techniques to control it effectively.
we
must
bound the error term Since this
N Regret S CoC Σ n=
4. Transition Transfer under Composite MDPs
28, +
In this section, we consider transfer learning with target task M1 and source task ( The transition probabilities of the target and source tasks are, respectively.
S Cregy V
where d = max q} and
(s0)sss a) = 0(s a) M) and (s'(ssss, = p(s, a) M (s').
(6)
Greg :- CaCo Co Co (T(,,C))+ log(dN
where the core transition matrices M()) and M()) are dif- ferent.
Remark 3.8. This regret bound achieves optimal scaling with respect to both the number of trajectories N and ambi- ent dimension d, matching previous results in reinforcement learning (Yang& & Wang. 2020; Jin et al., 2020). In Section 4, we demonstrate that transfer learning can substantially reduce both the dependence on ambient dimension and the scaling with N by effectively utilizing additional trajectories from source task.
We propose modeling task similarity through their transition dynamics: similar tasks share a common low-rank structure capturing core dynamics, while differing only in sparse directions that represent task-specific variations.
Assumption 4.1 (Transition Similarity). Consider the target and source tasks characterized by transition model (6). The target and source tasks are different in that their core transi- tion matrices (1) o (*), However, their similarity is defined by:
3.3. Challenge and Proof Sketch under the Composite Structure
By optimality condition of (2), it holds that
(0 L' (0 and M = L" + S (7)
Σ isn
K=1
oT, (f. + 5)11
where both tasks share the same low-rank component L", 1000 so, [| = are task-specific sparse components, two tasks are similar in the sense that their dif- ference D 5()) 500), called the "sparsity difference". is very sparse: | llo e s1.
Σ
I K (1= + 11
Expanding the inequality, we have
We have No episodes for the source task and N1 N episodes for the target task. In practice, No > N and we would like to use the source task to enhance the performance of the target task. Since our primary focus is on the target data, we don't 't make specific data generating ussumptions on the source data which can be both batch data or generated from certain online process.
Σ
(Z. - -1- + - (S-
2 Σ (1 + - Vi,n V k M³)
Σ iCR.NSH
(L O' SSn)
-2
For notation brevity, we use i and h to index episodes and time steps of the source task, with i E [No] and h E [H). For the target task, we use j and / to index its episodes and time steps, with j E [N] and h E [A]. We denote the following state-action-ssatioon transition triplet: (st,n, ar s(,,)) from the target task and (s),k: (5,, s'),)) from the source task. The associated features are
Establishing Theorem 3.7 presents several challenges and requires new techniques. First, deriving nigh-probabilin error bound for L and Š is nontrivial due to the presence of cross terms at the end of the inequality. To address this, we adapt the separation lemma from (Chai & Fan, 2024), which provides a way to control these cross terms effectively.
(0) = 0( (g.h) E R,,
Wih = ((66,,) E ER, with = vi(5',n) E R?.
(0)
Second, ensuring the strong convexity of the linear operator challenging due to high correlations across stages. To
1
(8)
1 j.h = ((85.1 E ERP
6

---

Transfer Q-Learning with Composite MDP Structures
Let K v :=:=>x EvEE ())) We have, at each step h for the target task,
Algorithm 2 UCB-TQL for Composite MDPs
Input: No episodes of source data, feature function Rº, I2, number of episodes N of the target task. Calculate pilot transition core estimators T., ((0) using (9).
(U) PLAVIA
K I $i,,, |i
= (ol Pith )
(1)T) (L*+5-(0).
Similarly, we have for the source task,
for episode n - 1,.,.... .N do
Construct confidence region (13). Calculate (n. (8,0) a) in (14). for stage h = 1, ... do
(0) T 18ghh. |s,h] (0 ( (L*+S-()).
J. K
4.1. UCB Transfer Q-Learning for High--Dimensiona Composite MDPs
Take action dz,h = arg maxae. Qu (Sn,h, a)
Observe Sn,h+1 from target domain M
end for
Now we introduce the UCB Transfer Q-Learning (UCB- TQL) for HD Composite MDPs. The algorithm is summa- rized in Algorithm 2. We first introduce the optimization- based estimator in the following two steps, then proceed to construct the confidence region.
Learn transition core estimator using (11).
end for
The online confidence region at step n is then constructed as
STEP Estimate the low-rank and sparse components of the source task by solving?
B, [L. (, : 1|4 -11--2001 +19 11---- D- - s BNo
||D D. s o ||ll
(1)) arg migmin min L.SERPX
Σ SEN
KJ - (0)
(L + |
(13)
where we incorporate D in the decision variables to put direct restriction the sparsity of sparse difference.
s.t. L= USVT,
111,,,00 S
pr
Similarly, the optimistic value functions are calculated as follows.
1 v 100
|15||0 S 80.
(9)
(an(s,))=r(ss00
max d(s, SL) Vn L.S,B,
STEP II. Use target data correct the bias of the sparse part in an online fashion.
(14)
(,, =0
Dn E arg min DEB
Σ
100 5h
K
( + D
Remark 4.2 (Extensions). We focus on sparsity-constrained optimization, which can be extended to a Lasso-type L penalty for improved computational efficiency. For brevity, we omit these details here.
jen.AsH
s.t.
||l|o Se
(10)
Then the target estimator for n episode is given by
= = (1) + D.).
(11)
4.2. Regret Analysis of UCB-TQL
The following assumption is parallel to Assumption 3.1. Assumption 4.3. Consider transfer RL setting with tran- sition similarity defined in Assumption 4.1. Recall that L U- V*. We assume that 12,00 [V" I AM and that the sparsity of (* and s-(1) satisfies
To construct the confidence region, suppose at the first stage, | (0) S( I|? < SN, with probability at least - 1/ H), where we slightly abuse notation by again referring to 3N. as the confidence radius at initial stage of target learning. When the source samples come from the online UCB algorithm as described in Section 3, have
we established - - i +
max so. $1} <3 :=
max(p.g) 4Csurt for some constant C's.
Coll log(NNo))) No
The following theorem demonstrates the provable benefits of UCB-TQL for the target RL task.
BN.
+
(12)
Lemma 4.4 (Estimation Error), Let No denotes the number of episodes from the source task. Under Assumption 3.4, 4.1, and 4.3, the estimator at the end of n -episode satisfies with probability at least 1 - -1/(n2 (( that,
d = max(p, }} and Co, Co, C,,, Cod are positive param- eters defined in the regularity Assumption 3.4, C3 is a un iversal constant.
Note that for simplicity. assume the sparsity appearing in the constraint is known. can be replaced by an upper bound on 8g-
eC2 H log (dnH)
I 1.1 1 - -5000 S S,N
7

---

Transfer Q-Lcarning with Composite MDP Structures
where Noo is the initial confidence radius defined in (12).
specific, plugging the value of 3 in (19), we have
Remark 4.5, The estimation error bound is minimax optimal with respect to No. n, and d. We extend these existing results in the contexts of regression and matrix completion (Chai & Fan, 2024) to the settings of reinforcement learning and transfer learning.
Regret(NH)) - C.C
Bh +1
a=1
S.C.HH N BNo+
Vecz oy NH log log(dN
Theorem 4.6 (Regret upper bound for UCB-TQL). Let No and N denotes the number of episodes from the source and target tasks, respectively. Let Reg)et(NH) be the ac- cumulative regret of a total of N target episodes using the UCB-TQL in Algorithm 2. Under Assumption 3.4, 4. I, and 4.3, it holds that
In contrast to (16), we employ a more fine-grained confi- dence region (13), where we directly restrict the sparsity of the sparse difference D be bounded, leading to improved rates.
In particular, we have (L", (L",)"( E B.. indicating this CR is valid. To bound the one-step error, let (L, S, D) arg max 0(s, a) S) Vi,h+1, it holds that
Regret(NH) S
No+
NH log (dN Hy V (C
On,n(Sm,,, an,h) ) (r(8n, ana)) ) + [PrV Vanniil(sn an,)))
I |o (t. - -1:) 1 Vnnhtall++
where: 8 mma $1} and
@n.h -D 1
Cra = (C+ + Cove) Coy/ H) (1 (ric, 0
aC%
Pnhh Dr) v T Vn,t+1
(15)
(17)
Remark 4.7. Note that the first term represents the rate at which the source is learned, while the second term accounts for correcting the bias of the sparse component.
The first two terms can be bounded similar to single-task case. From the constraint in the optimization problem (9) and Assumption 4.3, we have ||D S e, || llu S e, implying [i, - Do S 2e. This observation facilitates tight bound on the third term. Combining these one-step error bounds then yields the final regret bound in (19).
When the source sample size No is sufficiently larger than the target sample size, the regret is dominated by the sec- ond term. Specifically, when Ng x N2, the regret bound simplifies to ()) which scales independently of the ambient dimension. Since e < d, this represents a significant improvement over the result in (Yang & Wang, 2020).
5. Discussion
When employing low-rank and sparse structures as the core for transition probabilities, several directions for future ex- ploration emerge. Firstly, alternative sparse structures, such as row sparsity, column sparsity, or group sparsity, could be further investigated to understand their impact on learning dynamics and efficiency. These alternative formulations may offer more nuanced efficient ways capture the underlying patterns in transition dynamics across different domains.
We also characterize the phase transition. Specifically, when No > (rC3 + s), neglecting the logarithm terms, the regret bound becomes dominated by the second term, corre- sponding to estimation of the sparse difference.
4.3. Challenges and Proof Sketch of UCB-TQL with Sigh--Dimesioonl Composite MDPs.
A natural way to construct the confidence region is
Secondly, our analysis reveals that the regret bounds of the UBC-TQL algorithm are significantly influenced by the error bounds derived from matrix recovery. Since the Up- per Confidence Bound (UCB) is determined by the error bounds of matrix recovery, the regret bound is largely dic- tated by these errors. An extension goal is to achieve the current levels of regret under more relaxed assumptions. This could involve developing new theoretical frameworks or algorithms that either provide tighter error bounds or leverage additional structure in the transition dynamics that has not been fully exploited.
B, (L. || -L- 2n + +|s s-- 3. < 8(1)
(16)
where 3(11 = BN. + =0% (o
However, this confidence region is not tight in that we are not fully utilizing the sparse difference D. To be more
8

---

Transfer Q-Learning with Composite MDP Structures
Acknowledgements
References
Elynn Chen's research supported in part by the NSF Award 2412577. Lin Yang's research is supported in part by the NSF Award 2221871 and an Amazon Faculty Award.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. Flambe: Structural complexity and representation learn- ing of low rank mdps. Advances in neural information processing systems, 33:20095-201000 2020.
Impact Statement
Agarwal, A., Song, Y., Sun, W., Wang, K., Wang, M., and Zhang, X. Provable benefits of representational transfer in reinforcement learning. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2114-2187. PMLR, 2023.
This work addresses fundamental gap between the em- pirical success of transfer reinforcement learning and its limited theoretical foundation, while presenting a general approach applicable across robotics, autonomous systems, and other complex decision- makinn environments. Our core contribution novel composite MDP framework in which each task's transition dynamics are modeled as the sum of low-rank shared structure and a sparse task-specific compo- nent. Leveraging this formulation, we develop UCB-TQL. (Upper Confidence Bound Transfer Q-Learning), new al- gorithm with provable regret bounds and rigorous structural performance guarantees. By uniting theoretical guarantees with broad real-world applicabilityy this research bridges the gap between practical transfer learning and formal analysis, laying the groundwork for more efficient and principled reinforcement learning across diverse domains.
Arora, S., Du, S., Kakade, S., Luo, Y., and Saunshi, N. Provable representation learning for imitation learning via bi-level optimization. International Conference on Machine Learning, pp. 367-376. PMLR, 2020.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474444 PMLR, 2020.
Brunskill, E. and Li, L. Sample complexity of multi-task reinforcement learning. In Proceedings of the Twenty- Ninth Conference on Uncertainty Artificial Intelligence, pp. 122-131, 2013.
Cai, Q., Yang, Z., Jin, C., and Wang. Z. Provably efficient exploration in policy optimization. In International Con- ference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Calandriello, D., Lazaric, A., and Restelli, M. Sparse multi- task reinforcement learning. Advances in neural informa- tion processing systems, 27, 2014.
Candes, E. and Recht, B. Exact matrix completion via convex optimization. Communications of the ACM, 55 (6):111-119,2012 2012.
Candès, E. J. and Tao, T. The power of convex relaxation: Near-optimal matrix completion. IEEE transactions on information theory, 36(5):2053-2080, 2010.
Chai, J. and Fan, J. Structured matrix learning under ar- bitrary entrywise dependence and estimation of markov transition kernel. arXiv preprint 2tti::420..0220.. 2024.
Chai, J., Chen, E., and Fan, J. Deep transfer Q-learning for offline non-stationary reinforcement learning. arXiv preprint arXiv:2501.0455 2025.
Chen, E., Li, S., and Jordan, M. Transfer Q-learning. arXiv preprint arXiv:2202.044 04709, 2022.
Chen, E., Chen, X., and Jing, W. Data-driven knowl- edge transfer in batch Q" learning. arXiv preprint arXiv:2404, /5209, 2024.

---

Transfer Q-Lcarning with Composite MDP Structures
Cheng, Y., Feng, S., Yang, J., Zhang. H., and Liang, Y. Provable benefit of multitask representation learning in reinforcement learning. Advances in Neural Information Processing Systems, 35:31741-3111 2022.
Jin, C., Liu, Q.. and Miryoosefi, S. Bellman eluder di- mension: New rich classes of rl problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:13406-1344 13418, 2021.
Cheng, Y. Yang. J., and Liang, Y. Provably efficient al- gorithm for nonstationary low-rank mdps. Advances in Neural Information Processing Systems, 36:6330-6372, 2023.
Lattimore, T., Szepesvari, C., and Weisz, G. Learning with good feature representations in bandits and in rl with a generative model. In International conference on machine learning, pp. 5662-5670. PMLR, 2020.
D'Eramo, C., Tateo, D., Bonarini, A., Restelli, M., and Pe- ters, J. Sharing knowledge in multi-task deep reinforce- ment learning. International Conference on Learning Representations, 2020.
Lu, R., Huang, G., and Du, S. S. On the power of multitask representation learning in linear mdp. arXiv preprint arXiv:2106.08052 2021.
Lu, R., Zhao, A., Du, S. S., and Huang, G. Provable general function class representation learning in multitask bandits and mdp. Advances in Neural Information Processing Systems, 35: 15:111911,,,,, 2022.
Drineas, P. and Mahoney, M. W. Randnla: randomized numerical linear algebra. Communications of the ACM, 59(6):80-900 90, 2016.
Du, A. Y., Yang, I.. F., and Wang, R. Misspecified q-learning with sparse linear function approximation: Tight bounds on approximation error. arXiv preprint arXiv:2407.1362. 2024.
Misra, D., Henaff, M., Krishnamurthy, A., and Langford, J. Kinematic state abstraction and provably efficient rich- observation reinforcement learning. In International con- ference on machine learning, pp. 6961-6971. PMLR. 2020.
Du, S., Krishnamurthy, A., Jiang, N., Agarwal, A., Dudik, M., and Langford, J. Provably efficient rl with rich obser- vations via latent state decoding. In International Con- ference on Machine Learning, pp. 1665-1674. PMLR, 2019a.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, N., and Agar- wal, A. Model-free representation learning and explo- ration in low-rank mdps. Journal of Machine Learning Research, 25(6):1-76, 2024.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Müller, R. and Pacchiano, A. Meta learning mdps with linear transition models. In International Conference on Artificial Intelligence and Statistics, pp. 5928-5948. PMLR, 2022.
Du, S. S., Kakade, S. M., Wang, R., and Yang, L. F. Is good representation sufficient for sample efficient rein- forcement learning? arXiv preprint arXiv: 1910.0006, 2019b.
Neu, G. and Pike-Burke C. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1 13:1132-11003, 2020.
Pacchiano, A., Nachum, O., Tripuraneni, N., and Bartlett, P. Joint representation training in sequential tasks with shared structure. arXiv preprins arXiv:2206. /2441, 2022.
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing. arXiv preprint arXiv:21 12. 13487, 2021.
Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. Model-based rl in contextual decision pro- cesses: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 1898-2933, PMLR, 2019.
Hu, J., Chen, X., Jin, C., Li, L., and Wang. L. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pp. 4349 4358. PMLR, 2021.
Jingg N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Con- ference on Machine Learning, pp. 1704-1713 PMLR, 2017.
Tropp, J. Freedman's 's inequality for matrix martingales. 2011.
Uehara, M., Zhang, X., and Sun, W. Representation learning for online and offline rl in low-rank mdps. International Conference on Learning Representations, 2022.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference on learning theory, pp. 2132137-222 2137-2143. PMLR, 2020.
Vershynin, R. Introduction to the nom-asympto analysis random matrices. arXiv preprint arXiv: 2010.
10

---

Transfer Q-Learning with Composite MDP Structures
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. Opti- mism in reinforcement learning with generalized linear function approximation. International Conference Learning Representations, 2021.
Yang, L. and Wang. M. Sample-optimal parametric q- learning using linearly additive features. In International conference machine learning, pp. 6995-7004. PMLR, 2019.
Yang, L. and Wang, M. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In In- ternational Conference Machine Learning, pp. 10746- 10756. PMLR, 2020.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-19900 10989. PMLR, 2020.
Zhang, X., Song, Y., Uchara, M., Wang. M., Agarwal, A., and Sun, W. Efficient reinforcement learning block mdps: A model-free representation learning approach. In International Conference Machine Learning, pp. 26517-26547. PMLR, 2022.
Zhang, Y., Chen, E., and Yujun, Transfer faster, price smarter: Minimax dynamic pricing under cross-market preference shift, arXiv preprint: 2505. 2025.

---

Transfer Q-Learning with Composite MDP Structures
Supplemental Materials
Notation We use [k] = 21,,...... hi for integers from I to h. In this paper, vectors are assumed to be column vectors. For vector V E RR, the norms l/v||,, |/v|2, and l| represent the 1-norm, Euclidean norm(or 2-norm), and infinity norm, respectively. For a matrix M E TEPx,, we use the following notation for norms: [| denotes the number of non-zero elements, || = Ei=1 Eソ=1 Mayl is the sum of the absolute values of all elements, and || = maxi, MMy is the
maximum absolute value among elements. The Frobenius norm is || = VTr(M M) E
R M3 which d1
also equivalent VE, ( where (M) are the singular values of M. The nuclear norm is || 23 ( and the operator norm is || llp - max, (M)). Moreover, the 2 2-16 to - oo norm is defined as ||M]|2.ce = max ||
For two matrices, (T., 5) represents the Fuclidean inner product. We use On = O(ba) or On S bn if there exists some C > such that an - Cb2- (-) is similarly defined, neglecting logarithmic factors. Constants c, Co. may vary from line to line.
A. Regret Analysis of the Single-Task UCB-Q-Learning with Composite MDP Structures
We present below the proof of Theorem 3.7. The proof of Lemma 3.5 emerges as an intermediate step along the way.
Proof of Theorem 3.7. We first sketch the proof as follows. First of all, we define the "good event" that the ground truth transition core matrix before episode n lies in the confidence region as &,, i.c., (L*,S*) E Br for any n' S 1. We assume & holds first and use concentration to prove that e,, holds with high probability later. We denote En 1...
1. Under En. prove Qu,h Qi, using induction.
2. Bound Qn, (s (n,hh) [r(sn,h, Rn.1.) P(-Ism,h, an,,) "T.. V vnll
3. Bound the total regret by one-step enrors derived in Step 2.
We elaborate each step in the sequel.
A.1. Upper confidence bound
Lemma A.1. Given any state-action pair (8, a) E x for each episode n and decision step h, we have:
(n, a) 2 (s,
Proof. We use induction. At h H, we have Qn.H = (H naturally extends to h h' 1 that (s) 2 (s), and hence
(8. a) = r(s, a). Assuming the argument true for 1 <M S H,
Qn, = r(x, - max ((s.u) (in))((L)))) (L S\ VA
L.SEB.
r(s - a(s,a) (L' S Vnn+
2 r(s PP | = (s)..).
A.2. One-step bound
Lemma A.2. For any h E [H] and n E [N], we have
Qn an,r) - (r(sn,h, + [PAV V.,VV+14(((Bnn a)) S CoCypH
Proof. Let (I, 5) arg Seg, a(s,a) SY Vn,,+1, it holds that
Qm,,((5n,hhun,,)) (n (r(sn,), an, [Pa V Vn, (1 [(n,, kn) - -TT (I++5) - -M*) v VVn
= -T |I- L²) + (5- st)] v vT Vn
12

---

Transfer Q-Learning with Composite MDP Structures
Applying Hölder's inequality, the triangle inequality, and Cauchy-Schwarz inequality, deduce the following results:
Qn,h (8m, an,A) - (r(8n, an,h) + PN Vn,n+1((snn) an,h))
panlt - 11 Van+1 1 + I (S-S") Srx
1 v Vn,at1l22
H (Co | ( ---)
+ Cs 0h.n (s- (5=5s)111)
(18)
H CCp 11 | 1| L3
[ 5* |pp)
Co llón,ill2
F
s CoC H (|E-L-
--5t s²1pp)
+
F
CoC H 22m.
A.3. Regret decomposition
We bound the regret by the sum of one-step errors. To set the stage, let Fn,s be defined as the a-field generated by all the random variables up until episode n, step h, essentially fixing the sequence $1,1, $1,,, 01,2........ Sn,hs an, To proceed, let
8n,h = (Vn, Vi (8nnh) Yn.h == Qn,h (8m, an,h) - (r(8n,h and + [PA +1) an,h))
And hence
N V (50 voo
Regret
E
N
N
S
(Vn,1 - (50)
1(
We have
1(,,,1) 1(8n, + (1 En)dn.1) 1666n (n) HPLE 0]
and
E (ōn,1 En Fn.1) = =(Vn, ViaT (sn.1) En
IQn,1 (8n,1, an,1) - 1iT (8n,1)
7n, + (r (8n,1, an,1) + [PV (8n,1, an,1)) - VTT" (8n.1)
Sm.. + ((Vn22 V²2h) (8n,2) En Fn.1) S...
B(Tn,h Fa.1)
CC 223
Therefore, establish the regret bound with high probability that
N Regret(NNH) S C2 Σ
2 + NHPPEN = 0],
(19)
D=
where we use &n C E, with n > n'
A.4. Confidence region
In this subsection, we validate the confidence region, Recall the CR defined in (3).
13

---

Transfer Q-Learning with Composite MDP Structures
11,1
"T,1 T
Denote Xn
I1
and y,
v 11 K
have the observational model as follows:
0 11-1
1 1.H K
Y, = + 8") W
where Wa = Yn Xx (L* + 5*).
In view of (Chai & Fan, 2024), we need the observation model to satisfy the restricted strong convexity condition order for the low-rank part and sparse part to be separated.
X X
Amin
2 C1
(20)
We will later give specific cases in which this inequality holds. In the sequel, we bound || W and |X,, W mma In fact, we can express X,, W,, as
H
W,W Wn = ΣΣ
Lihh
W k
==
h=1
Note that 4i K DT,
O, and X,W, Wn sum of martingale differences. Let Zi,
di.h TTT K-1 v
14.1. M²) we have that
7 |1 K. TT M
|| (IVVT +1+ [1
S 2C Chp.
where we used M1 =
E
w.nn K
Fin
s CC'
On the other hand,
Z, EE S
Σ
A=1
and
H E, E Frnn AnH((C,C))
i=1 1=1
By Matrix Freedman inequality (Corollary 1.3 in (Tropp, 2011)), we have with probability at least 1 that
|X_ Wwllk 5 C.C' log d + +GGG (
Similarly, each entry of X W,, is the sum of martingale differences, almost surely bounded by 2Coy, and we have by Azuma-Hoeffdingss inequality and a union bound over d² entries that, with probability at least 5,
| Wollmax = 5,3
[X] W W S Covi nil log
Confidence Region
14

---

C3 Transfer Q-Lcarning with Composite MDP Structures
By the optimality condition, have
| xnn(tn S SY - X. + 11
Expanding on both sides yields
||,,,, (A, + As)l S 2(W,, (n +1s)
2(X,, W., Ag + As)
S X WT, |222| A + 21 W., [allmmmx|Asss
2(x,, Wn, A AAs)
$ 2/ X,, W W + 2/2s|| Wa mmx AAslE
where denote AL : L,, L and Ag: = S.. On the other hand, by (20) and separation lemma in (Chai & Fan, 2024), we have that
(A, + As)l 2 (n - 11)| + As
Ci
1)
2 (1 1/ + و 1
Putting together, have
4
|
||A
22 |X, W. W. 1 v2s|| Wn |l |ma |As||r
4 1)
2r |r W. + 2s X Ww 1l. +
(n - 1)
which implies that
32
| + ||s <
ciin 1)² (rl [IIXX,Wllll Wn
+ + Wn. JiI.W,W... 1 l?xax)
Plugging in the aforemennioned bounds of || Wn, l22 and ||_X, Wn, Imlmxax. we deduce that B, is valid 8-confidence region if we take
(r(C,C,)) log(d/)) + Sy nH log(d/6)) = C3 H log(d/0) (x(C sC
Bn = ?
(21)
n
for some large enough Cg. In particular, we take 6 = 1/(N²H) in the above display, then by the union bound, PPEN 0) N. N²N NH Combining the definition of Bn with (19), we obtain that
N Regret(NH) S C.C 2
Σ n=1
22n + 1
X Creg VN
where Creg == CoCoyCs (r(C,C))+ + 50))) Ho
As byproduct, we have that by the end of the episode, with probability at least - 1/(N2
| IN + -||s -mm - s 3N.
15

---

Transfer Q-Learning with Composite MDP Structures
A.5. Discussion Condition (20)
Now we provide an example where Condition (20) holds. At a high level, Pi may be highly correlated, across different steps and episodes. Nonetheless, note that each episodes starts at independent initial states, hence providing diversity the linear operator Xn. In fact, Condition (20) holds when ((s, a) depends mainly and adds perturbation effect. To be more concrete, consider the following lemma as an example.
Lemma A.3. Suppose there exists some function é such that (Io(s, a) x())ll2 And
Amin (E ( TT) 2 Cmin-
If [n(22 + < Suju and n. 2 Ced for some constant Ce, then with probability at least 1 - 2en Condition (20) holds with 01 = Cmin/44
Proof. Denote E,, {)))(()) 1 by Σn. As [ < |[(()]| S C. for any v E Sd, we have that d(s) is subGaussian with variance proxy (C- 6/2)2. By (5.25) (Vershynin, 2010), there exists some constants Ce, Ce such that with probability at least 1 -e--ee
((L1))((11.1"
1 = 2
Cuin I 2
as long as n 2 C.d.
Let A - E
1 n-1 Ei 01,10,,1 T we have for any v Sd that
Ar ( To}² 10,, 2)1²)
(o(su.)) 02u1| (oll-1(((s.)) oz.1
S (2C + n)
Hence |||| (2C, + 1)) s emin It follows that
Cmin 4
1 x
To conclude, note that
Σ 1=1
01.1011
Caiin
I.
4
1=1 k=
Remark A.4. The condition 2 Ced requires a warm start. For n S Ced, one can use a fixed policy to generate samples. This will not affect the total regret as long as dH is neglegible compared to H5
B. Regret Analysis for UCB-TQL under Composite MDPs
In this section, we provide proof for Theorem 4.6. The pipeline is similar to the single-task setting.
(1)
11,1
We start by constructing the confidence region. To that end, again denote Denote x(!)
(1)T
and
y(1)
(1)T
1-118
16

---

Transfer Q-Learning with Composite MDP Structures
(IT K
V
I,
(2)T
K
we have the observational model as follows:
n-1.
- X1" + + +D) Wa
where W, = y2 - -x* + s0(0) + D*).
By the optimality condition, we have
| - Dn)ll ( (L* + 5- + 1.
After some calculation, obtain
Ix --)) x 2 X (L+ 3
D²), - x x (D, - -D7)
2 x
WWn + x (L" Ż + 5 -5:0 -Dn-D") Dr)
< X Wr, 00
Dr - Di + 2 - x (T= T 5-(0) - - /100 Dn -D'
s 2e x(I)TT. Wn
Dr D" +2 + x (I= -I+ - 5000 / rr || Dr -D"
We have, similar as before, with probability at least 1 - 6,
d ( I &Crvy nH nHllog log
max
(1) x!
Amin
2 C1
11 n-1
((1T x
Amax
S C1,
n-
then it holds that
cC² H Hlog (d)
[1 12 x
+ +|| - -,113- + (1s) 11
n
Suppose at the first stage, we established - L1p + (1))0(0) - -5(0) s SN. with probability at least 1/(2N2 H). where
NN. = CsHlog(d/0) (r(CoCC,) + sC2n),
No
as in (21).
Naive CR
Recall that we can construct a naive confidence region as
B, = { (T,,S)
T.-
T.m1
S S. 11 3((
where a(() = BNO + c02 log(dN
17

---

Transfer Q-Learning with Composite MDP Structures
When using this confidence region to construct optimistic value functions, we can plug the value of 3% into (19). follows
that
N
Regret( &
+1
n=1 S
C N
WN.. + VeCa log (dNH))
Remark B.I.
When No >> N, this bound is dominated by the second term, which depends on C..
Tight CR region as
As illustrated in the proof sketch, we can achieve better rate by constructing more fine-graines confidence
B - (1..s. --- 2101 + ||s-- -- D ---500l |10l| I BNo, D - D.lli S 1000 1D I {e ]
is straightffrward to show that (L", (*) D*) Bn. We then carry out more refined one-step analysis, similar in the vein of Section 3.2.2. In particular, let (I, S, D) = arg max a( (L + S T Vn,441, it holds that
Qn (Sm,h hn) - (r(Sn,,, an,h) ) + [Ph Vn, n+, (sn an.h))
$ on - V Vo.++1l2 + | 6 (3 D - -5 + +11 [ + + (D-Dr) T Vnntt 2
S Co & (I- + +Cp Un.h (5-D-S - -5 + 10-55+D' +D+))1
+2EHCC | 1D-
S H (Co / 1/2 1 1,¹
+ + Colllnnl 13 8- ---S* + Dr 1011)) + +2eeHC
5 D"
H. (1T-- 1:- | Đ S + Dr (111p)) v2eHC' [ D'
S C. H
23 + C. H 13
(22)
where the sparsity constraint on D is used in bound the third term in the second line. Combined with the one-step error in the regret decomposition (19), we obtain that
Regret(NH)) $ C2 Σ BN, + C.C.HH
4300
z (Co (C&+C.ve)) C. CC BNo + +C C2, /C (dNH).
Plugging the definition of AN, completes the proof. Remark B.2. When No >> N, this bound is dominated by the second term, which does not depend on C.. but rather on C² is tighter than the rate naive CR approach as Co 2 C%
18


Reviews:
[{"review_id": "SfRIgb2YBJ", "reviewer": "Reviewer_ZhAb", "summary": "The paper introduces a Upper Confidence Bound method for Transfer Q-Learning for transfer RL settings where it is assumed that transition dynamics are assumed to decompose to a low-rank shared matrix and a sparse matrix that captures task specific dynamics. A key feature is that the method allows for high-dimensional transition dynamics. The paper follows on to provide theoretical guarantees on the UCB Q-learning applied to this structure for single-task learning as well as transfer. Transfer occurs by fixing the low-rank component and adapting the sparse component.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their positive assessment and constructive suggestions.** We are especially grateful for the recognition of our theoretical contribution, which we believe offers a timely and foundational advancement in transfer reinforcement learning.\n\nOur work provides the *first provable regret guarantees* for transfer RL in high-dimensional settings where the transition dynamics exhibit structured heterogeneity. By modeling transitions as $M^* = L^* + S^*$—with $L^*$ low-rank and $S^*$ sparse—we capture realistic task variations (e.g., shared core dynamics with sparse task-specific shifts). This structure allows us to derive *minimax-optimal error rates* for estimating $L^*$ and $S^*$, and achieve regret bounds that are *independent of the ambient dimension* $d = \\max(p, q)$. These insights lay a theoretical foundation that complements ongoing empirical advances and help answer the fundamental question: *when and how does transfer learning help in high-dimensional RL?*\n\nWe have revised the manuscript to improve clarity in notation and address specific concerns raised:\n\n- **Section 2 – Notation of $\\mathcal{P}$ and $\\mathcal{P}V^\\pi_{h+1}(s,a)$:**  \n  $\\mathcal{P}$ is a linear operator mapping a function $V : \\mathcal{S} \\to \\mathbb{R}$ to a function over $(s,a)$ via $\\mathcal{P}V^\\pi\\_{h+1}(s,a) = \\sum\\_{s'} \\mathcal{P}(s'|s,a) V^\\pi\\_{h+1}(s')$. We have clarified this in the updated text.\n\n- **Line 154 – $[H]$ Notation:**  \n  Yes, you are right. $[H]$ denotes the index set $\\{1,2,\\dots,H\\}$. We have clarified this in the updated text.\n\n- **Line 191 – Summation in $K_\\psi$ and Equation (1):**  \n  The equality in Equation (1) is valid. $K_\\psi$ is defined as the sum over all $s' \\in \\mathcal{S}$ and is independent from the outer summation over $s' \\in \\mathcal{S}$ in Equation (1). The simplification extracts common factors based on our composite MDP formulation.\n\n- **Line 210 – $\\|\\cdot\\|_{2,\\infty}$ Notation:**  \n  This denotes the 2-to-infinity operator norm, i.e., the maximum $\\ell_2$ norm of the rows. We've added this to the notation section for clarity.\n\n- **Equation (3) – Frobenius Norm:**  \n $\\|\\cdot\\|_F$ refers to the Frobenius norm and was defined in the supplementary material, now clarified in the main text.\n\n- **Assumption 3.1 – Meaning of $\\mu$ and $r$:**  \n  Thank you for your careful reading! $\\mu$ is the incoherence parameter (a constant > 1), and $r$ is the rank of the low-rank component $L^*$, now clarified in the main text.\n\nRegarding examples of our model, consider **personalized healthcare**: the low-rank component captures typical patient responses to treatments, while the sparse component models anomalies or individual-specific deviations. Other real-world domains include **recommendation systems** and **robotics**, where core dynamics are shared but task-specific noise or variation exists. A **counterexample** would be settings where task variation arises from structured transformations or complex nonlinear mappings—scenarios that go beyond additive sparse deviations and are natural directions for future work.\n\nWe thank the reviewer again for their support and helpful comments, and we hope the improvements further affirm the strength and clarity of our submission.", "claims_and_evidence": "I believe that the key claims of the paper are verified through the theorems up to their correctness.", "methods_and_evaluation_criteria": "This is a theoretical paper; no experiments were reported.", "theoretical_claims": "The paper provides several theorems. While I have gone through the proofs, and believe that they are correct, I would not say that I have verified them rigorously.", "experimental_designs_or_analyses": "This is a theoretical paper; no experiments were reported.", "relation_to_broader_scientific_literature": "The paper builds on top of Composite MDPs and Q-learning with UCB.", "essential_references_not_discussed": "None to my knowledge.", "other_strengths_and_weaknesses": "### Strengths\n- Good literature review\n- Other than the weakness mentioned below, it is written well.\n### Weaknesses\n- The notation in some places can be better explained. \n- There are no examples of experiments run with the proposed method to show how well the theory can be utilized in practice.", "other_comments_or_suggestions": "### Section 2\n- Could the authors be more explicit about the form of $P$. Is it a function $\\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\rightarrow [0, 1]$? If so, I am not sure I understand the notation $[PV_{h+1}^\\pi](s, a)$. \n\n### Section 3\n- Assumption 3.1(i) - Please specify what $\\mu$ and $r$ are. \n- Equation 3 - Please state that $|| \\cdot ||_F$ refers to the Frobenius norm (which I assume is what it means).", "questions_for_authors": "1. line 154: What does the notation $[H]$ mean. I think it means the range from $[0, H]$. If so, why not say that, or specify what the notation means. \n2. line 191: Is the summation in $\\mathbf{K}_\\psi = \\sum_{s'\\in \\mathcal{S} ...$ a mistake? I don't think the simplification in step 2 of Equation (1) works with this sum. \n3. line 210: What does the notation $|| \\cdot ||_{2, \\infty}$ mean? Specifically, does it mean the 2-norm and $\\infty$-norm, or all norms from 2 to $\\infty$, or something else?\n4. Could you give examples of where the specific 'low rank core transition with sparse task specific structures' arise. Could you also give counter examples?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pS4xKSg5MI", "reviewer": "Reviewer_fH8W", "summary": "This paper introduces a composite MDP framework combining low-rank shared dynamics and sparse task-specific variations, along with the UCB-TQL algorithm for transfer Q-learning. Theoretically, it establishes a dimension-free regret bound for the target task by leveraging structural similarities between tasks. While the work provides rigorous theoretical guarantees, empirical validation and comparisons with existing methods remain open questions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer fH8W**\n\nWe sincerely thank the reviewer for the thoughtful feedback and recognition of our theoretical contributions. We address the two concerns raised below.\n\n---\n\n**Q1: Lack of empirical validation of UCB-TQL**\n\nWe appreciate the reviewer’s point. While this submission does not include empirical evaluations, our goal is to provide a *theoretical foundation* for transfer reinforcement learning (RL) in high-dimensional settings with structured heterogeneity. Specifically, UCB-TQL is the **first algorithm with provable regret guarantees** under the composite MDP model that includes *both low-rank and sparse deviations*, and achieves $\\widetilde{\\mathcal{O}}(\\sqrt{e} H^5 N)$ regret that is **independent of ambient dimension**.\n\nThis setting is motivated by real-world applications (e.g., autonomous driving, robotics, and healthcare), where tasks often share underlying dynamics but differ in subtle, structured ways. In such domains, the transition dynamics may be high-dimensional, and assuming *pure low-rank* or *dense similarity* across tasks can be too simplistic. The low-rank-plus-sparse decomposition we propose reflects this nuanced task structure and provides an *interpretable and tractable* way to model variation.\n\nAlthough we do not present experiments here, we see our work as a **theoretical counterpart** to recent empirical transfer RL methods. Our regret guarantees offer insights into *when and how transfer should help*, which is often unclear in empirical work. We believe our analysis will inspire future algorithms that combine empirical effectiveness with theoretical robustness, and we are currently implementing UCB-TQL in benchmark settings.\n\nWe hope the community will view our contribution as laying the groundwork for **provably efficient transfer in high-dimensional RL**, and we are **excited to follow up** with empirical validation in future work.\n\n---\n\n**Q2: Limitation of sparsity-based task differences**\n\nWe fully agree that real-world tasks can exhibit more complex deviations than those modeled by sparse differences. Our current work makes a *structured but generalizable starting assumption*: tasks differ sparsely in transition dynamics after aligning shared core structure. This assumption enables us to design statistically and computationally efficient estimators, while still covering rich task classes.\n\nWe appreciate the suggestion and have added discussion in the revised manuscript exploring possible **extensions**:\n\n- **Task-specific low-rank components**: One natural direction is to allow each task to have its own low-rank variation on top of a shared component. This introduces additional complexity but could capture broader relationships.\n- **Decomposable low-rank spaces**: Another extension is to learn a union of low-rank subspaces across tasks, leveraging techniques from subspace clustering and matrix factorization.\n- **Feature selection on $\\Phi$ and $\\Psi$**: When feature sets are known but high-dimensional, incorporating feature selection or structured sparsity could adaptively identify task-relevant components.\n- **Group-sparse or structured differences**: Beyond elementwise sparsity, our model could be extended to handle block or group-structured variations, which would better capture correlated shifts.\n\nWe view our work as a first step toward unifying high-dimensional structure with transfer learning, and we are enthusiastic about these extensions.\n\n---\n\n**Closing Remarks**\n\nWe again thank the reviewer for the constructive comments. We believe our theoretical framework makes a timely and valuable contribution to the transfer RL literature, particularly in advancing the understanding of *when and how transfer helps* in high-dimensional environments. By addressing the above concerns, we hope to improve the clarity, flexibility, and practical relevance of our work. We respectfully hope the reviewer may consider increasing their score.", "claims_and_evidence": "Yes, the claims are generally supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes. The methods are largely appropriate for addressing the challenges of transfer reinforcement learning.", "theoretical_claims": "Yes. The theoretical claims are sound.", "experimental_designs_or_analyses": "This paper primarily focuses on theoretical analysis and lacks experimental validation.", "relation_to_broader_scientific_literature": "The paper introduces a composite MDP framework combining low-rank shared dynamics with sparse task-specific components, and proposes UCB-TQL for transfer RL with dimension-independent regret bounds. Theoretical analysis demonstrates that UCB-TQL effectively exploits structural similarities while adapting to task variations, achieving improved sample efficiency over single-task RL through rigorous confidence region construction for sparse differences.", "essential_references_not_discussed": "No, the essential references are discussed in the paper.", "other_strengths_and_weaknesses": "Strengths:\n- This paper introduces a low-rank + sparse composite MDP to model shared dynamics and task-specific variations, addressing limitations of prior work that assumes purely low-rank structures.\n- It provides a very detailed theoretical analysis and proof.\n\nWeaknesses:\n- While theoretically sound, the paper does not include experiments to validate UCB-TQL’s performance on benchmarks or compare it with existing transfer RL methods, leaving practical efficacy unverified.\n- Assumes tasks differ only along sparse dimensions, ignoring more complex inter-task relationships. Real-world tasks often exhibit more complex deviations, limiting the framework’s generality.", "other_comments_or_suggestions": "Page 3, Definition 2.1: \"probability transition model $P: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\bigtriangleup(\\mathcal{A})$\" -> Should clarify $ \\bigtriangleup(\\mathcal{S})$ instead of $\\bigtriangleup(\\mathcal{A})$.", "questions_for_authors": "Please see Weaknesses and Suggestions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nJvP5bnqCY", "reviewer": "Reviewer_CS8V", "summary": "The paper addresses transfer reinforcement learning (RL) under a new framework model called composite MDP, where transition dynamics consist of a low-rank “shared” component plus a sparse “task-specific” component. This setup reflects how different tasks can share a core set of dynamics while still varying in a limited number of ways.\n\nThe authors first studies single-task Learning with composite MDPs. They present a UCB-based algorithm (UCB-Q-Learning) and provide regret bounds that extend standard results in linear and low-rank MDPs to this more flexible composite structure.\n\nThen the authors consider transfer learning across tasks, where in the source and target tasks, the low-rank parts are shared, and only the sparse components differ. They introduce a transfer Q-learning algorithm (UCB-TQL) to leverage a previously learned source-task model. They prove that when the difference between the target task and source tasks' sparse components is very small, the regret bound for the target task becomes nearly dimension-free w.r.t. ambient dimension.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments! \n\n**Low-Rank:** We agree that clarifying this terminology is important for improving readability and avoiding confusion. In classical low-rank MDPs literature, \"low-rank\" refers to embedding-based models where the effective feature dimension $d$ is small compared to $|\\mathcal{S}|$. In contrast, in our setting, we work in a high-dimensional regime with $p, q \\gg N$, so $M^*$ is not globally low-rank.  Prior methods developed for low-rank MDPs—which assume a small feature dimension—do not apply directly, since they cannot consistently estimate $M^\\ast$ within $N$ trajectories. \n\nTo resolve this issue, we assume $M^* = L^* + S^*$, where $L^*$ is of low-rank $r$ and $S^*$ is sparse. This structure enables consistent estimation in high dimensions and is key to our theoretical analysis. Crucially, this assumption enables us to design an estimator that achieves *minimax-optimal error rates* for recovering $L^\\ast$, $S^\\ast$, and consequently $M^\\ast$, *independently of the ambient dimension* $d = \\max (p, q)$.\n\nWe have revised the manuscript to clarify the distinction between embedding-based low-rank MDPs and our structured high-dimensional setting.\n\n**Prior Work [1,2]:** Our model can be written in the form of [1] as $P(s' \\mid s, a) = \\phi(s,a)^\\top \\alpha(s')$ with $\\alpha(s') := (L^* + S^*)\\psi(s')$. This reduces to [1] when $S^* = 0$. Similarly, our model matches the linear factored MDP in [2] via a Kronecker formulation: $P(s' \\mid s,a) = (\\phi(s,a) \\otimes \\psi(s'))^\\top \\operatorname{vec}(L^* + S^*)$.\nWhile structurally related, a key difference lies in estimation. Our setting allows $p, q \\gg N$, and our estimator achieves minimax-optimal error rates that do **not** scale with $d = \\max(p, q)$. In contrast, [1,2] assume low-dimensional or identifiable parameter spaces and are not suitable for high-dimensional regimes. Our structured assumption is especially crucial in **transfer RL**, enabling effective knowledge sharing via $L^*$ while capturing task-specific deviations via $S^*$.\n\n**Comp. Efficiency of $K_\\psi$:** We agree this is important. When $|\\mathcal{S}|$ is large or infinite, we compute $K_\\psi$ using a Monte Carlo approximation:\n$\n\\hat{K}\\_\\psi = \\frac{1}{m} \\sum\\_{i=1}^m \\psi(s\\_i)\\psi(s\\_i)^\\top, \\quad s\\_i \\sim \\text{Unif}(\\mathcal{S}).\n$\nThis is a standard approach in randomized numerical linear algebra [3] and is computed only **once** before online learning. Our method is thus comparable in efficiency to [1], which stores empirical covariances, but we use $K_\\psi$ to build confidence regions specific to our model.\n\n**Clarification on Theorem 3.6:** Our method handles the high-dimensional setting by explicitly exploiting the low-rank-plus-sparse structure of the transition core matrix $M^* = L^* + S^*$, where $L^*$ is of low-rank $r << d$ and $S^*$ is of sparsity $s << d$. This structure enables consistent estimation in regimes where $p, q \\gg N$, and is key to our theoretical guarantees. We have updated Remark 3.7 to clearly state the point. \n\nCrucially, our estimation procedure achieves *minimax-optimal error rates* for $L^*$, $S^*$, and $M^*$ that are **independent of the ambient dimension** $d = \\max(p, q)$. We do **not** assume that the rank $r$ or sparsity level $s$ scale with $d$; under Assumption 3.1, both can remain small (e.g., constant or logarithmic in $d$), ensuring the estimation error bound does not grow with $d$ even in high-dimensional settings and our transfer learning result is **explicitly free of $d$**, demonstrating that the benefit of structural transfer carries over without dependence on the ambient dimension. \n\n**Technical Note and Transfer RL:** Our regret analysis relies on bounding Frobenius norm errors and carefully transferring them to Bellman recursion. Improvements using variance reduction or stronger structural assumptions are possible future work. A major contribution of our paper is in **transfer RL**: our low-rank-plus-sparse structure enables sample-efficient transfer, capturing shared structure via $L^*$ and task-specific deviations via $S^*$. Prior work like FLAMBE [Agarwal et al., 2020] does not handle this generality. We have added clarifications throughout the revised paper.\n\nWe thank the reviewer again for your support and helpful comments, and we hope the improvements further affirm the strength and clarity of our submission.\n\n**References:**\n\n[1] Sample-Optimal Parametric Q-Learning Using Linearly Additive Features  \n[2] Model-Based Reinforcement Learning with Value-Targeted Regression  \n[3] Drineas & Mahoney, RandNLA: randomized numerical linear algebra, CACM 2016", "claims_and_evidence": "The term **“low-rank”** in this paper appears to be used inconsistently, leading to ambiguity.\n\nIn summary, I find three different interpretations of “low-rank” within the paper:\n\n1. **\"Low-rank MDPs\"**  \n   - In my understanding, the notion of \"low-rank\" in **low-rank MDPs** compares the embedding dimension $d$ with the original large state space. As long as $ d \\ll |\\mathcal{S}| $, the MDP should still be considered low-rank.\n\n2. **\"Transition core** $M^*$ **is no longer a low-rank matrix\"**  (Line 53, Right Column)  \n   - Here, \"not low-rank\" likely refers to the high-dimensional setting, where $ p, q \\gg N $.  \n\n\n3. **\"Where** $L^* $  **is a low-rank incoherent matrix\"**  (Line 163, Right Column)  \n   - I did not find any further explanation of the **low-rank structure** of $L^*$, so its exact role seems unclear. Also I wonder whether this structure contributes to solving the high-dimensional problem.\n\nI find these differing interpretations make the discussion difficult to follow. For instance, the paper states:\n\n> *\"Similarly, methods built for low-rank MDPs fail in our context due to the absence of low-rank assumptions in $M^* $.\"* (Line 57)\n\nHowever, even if $M^* $ does not satisfy a low-rank assumption, the model may still be a low-rank MDP in the sense of an embedding-based formulation.  So why do methods for low-rank MDPs fail if the overall structure is still low-rank? \n\nI think clarifying these distinctions would improve the paper's readability and consistency.", "methods_and_evaluation_criteria": "The algorithm is standard UCB-type algorithm and the evaluation criteria is standard regret.", "theoretical_claims": "I go through the proof of theorem 3.6, which seems correct.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "The proposed model composite MDPs is different from previous literature, but more discusssions on the relationship with previous literature are required. Please see below and \"Claims And Evidence\".", "essential_references_not_discussed": "The composite MDPs also seem to be a special case of a linear factored MDPs. [1,2]. I think there should be some discussions on how these models are related.\n\n[1] Sample-Optimal Parametric Q-Learning Using Linearly Additive Features.\n\n[2] Model-Based Reinforcement Learning with Value-Targeted Regression.", "other_strengths_and_weaknesses": "Weakness:\n\n1. Computational Efficiency of  $K_\\Psi$  in Large State Spaces. When the state space $\\mathcal{S}$  is infinite or extremely large (which should be considered given the assumed high-dimensional setting), how can  $K_\\Psi$  be computed efficiently, even if  $\\Psi$  is known?\nPrevious works, such as [1], typically store only the covariance matrix of the sampled features, making their approach computationally efficient. How does your method compare in terms of efficiency?\n\nQuestion:\n\n1. Clarification on Theorem 3.6. Could you elaborate more on Theorem 3.6? In Remark 3.7, you mention that the result matches previous bounds in terms of  $d$ , which have polynomial dependence on $d$, but your bound does not explicitly involve any polynomial dependence on  $d$. Do  $r$  and  $s$  scale as poly$( d )$? This is crucial because you assume  $p, q \\gg N$; if the upper bound includes  $O(d)$ , the regret will scale superlinear with $N$. If the result does not involve polynomial dependence on  $d$, could you provide a high-level explanation of why your method can handle the high-dimensional setting, whereas low-rank and linear MDP methods fail?\n\n[1] Provably Efficient Reinforcement Learning with Linear Function Approximation.", "other_comments_or_suggestions": "Please add the Impact Statement section.", "questions_for_authors": "Please see Other Strengths And Weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel theoretical framework, the composite MDP (low-rank shared + sparse task-specific dynamics), and associated UCB-based algorithms (UCB-Q, UCB-TQL) for single-task and transfer reinforcement learning in high dimensions. Reviewers acknowledged the novelty of the composite model and the significance of the theoretical contributions, particularly the derived regret bounds that achieve near dimension-free dependence on the ambient dimension under specific transfer conditions. The detailed theoretical analysis was also noted as a strength. However, a major and unanimous criticism is the complete absence of any experimental validation. This lack of empirical results prevents assessment of the practical performance, applicability, or comparison of the proposed methods against existing approaches. Significant concerns were also raised regarding clarity and consistency, especially the ambiguous use of the term "low-rank," alongside requests for clarification on specific notations and theorem details. Furthermore, questions about the computational efficiency of the proposed algorithms in large state spaces and the generality of the structural assumptions relative to real-world task variations were highlighted. While the theoretical advancements are recognized, the lack of experiments and clarity issues significantly detract from the work, leading to a mixed assessment leaning slightly negative.
Decision: Accept (poster)