Transition Transfer Q Q -Learning for Composite Markov Decision Processes Jinhang ChaiElynn Chen ♯, Lin Yang 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 𝒪 ~ ​ ( e ​ H 5 ​ N ) \widetilde{\mathcal{O}}(\sqrt{eH^{5}N}) that scales independently of the ambient dimension. Here, N N represents the number of trajectories in the target task, while e 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. Keywords: Transfer Learning; Reinforcement Learning; Online Q -Learning; Upper Confidence Bound Algorithms; Low-Rank plus Sparse Structure. 1 Introduction Transfer reinforcement learning (RL) has emerged as a promising solution to the fundamental challenge of sample inefficiency in RL. By leveraging knowledge from related tasks, transfer learning aims to accelerate policy learning and improve performance in new environments without requiring 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. Consider autonomous vehicle training as an illustrative example: 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, different traffic patterns) introduce distinct variations to these core dynamics. This naturally suggests modeling transition dynamics as a combination of shared low-rank structure capturing common elements, plus sparse components representing 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 a 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 RL 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 ( Calandriello 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 combination with low-rank components – remains unexplored. This gap is significant because transition dynamics often more directly capture task similarity than value functions. We begin by addressing single-task learning within this composite structure, introducing a variant of UCB-Q-learning tailored specifically for composite MDPs, which may involve a high-dimensional ambient space. In contrast to previous work, we consider the high-dimensional setting where the feature dimensions p,q\gg number of trajectories N , and the transition core M^{*} is no longer a low-rank matrix. This departure from low-rank structures makes existing algorithms designed for linear MDPs inapplicable. Similarly, methods built for low-rank MDPs fail in our context due to the absence of low-rank assumptions in M^{*} . 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, Kakade, Wang & Yang, 2019 ; Lattimore et al., 2020 ) . Unlike the approach in Foster et al. (2021) , which introduced a Decision-Estimation 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 learning 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-independent regret bounds that explicitly capture dependencies on both rank and sparsity, showing how structural similarities enable efficient knowledge 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 primary contributions are as follows. • A novel composite MDP model that combines low-rank shared structure with sparse task-specific components , while allowing high-dimensional feature spaces. This framework better captures real-world task relationships and provides a foundation for future work in multi-task and meta-learning settings. • The first theoretical guarantees for single-task RL under the high-dimensional composite transition structure, demonstrating how algorithms can effectively learn and utilize both shared and task-specific components. • A transfer Q-learning algorithm with provable regret bounds that explicitly characterize how structural similarities enable efficient knowledge transfer across tasks. This work represents a significant step toward bridging the gap between empirical success of transfer RL and theoretical understanding by providing a rigorous analysis of how structural similarities in transition dynamics enable efficient knowledge transfer. Our results suggest new directions for developing practical algorithms that can systematically leverage shared structure while accounting for task-specific variations. 1.1 Related Work 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 representations 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) ; Chen et al. (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 -learning approaches. Our work differs by studying transition models with low-rank plus sparse structures. This setting presents unique challenges beyond purely low-rank models, as 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 provably efficient online algorithms ( Sun et al., 2019 ; Jin et al., 2020 ; Zanette et al., 2020 ; Neu & Pike-Burke, 2020 ; Cai et al., 2020 ; Wang et al., 2021 ) . Low-rank MDPs extend this by requiring representation learning. Major developments include FLAMBE ( Agarwal et al., 2020 ) for explore-then-commit transition estimation, and REP-UCB ( Uehara et al., 2022 ) for balancing representation 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, Krishnamurthy, Jiang, Agarwal, Dudik & Langford, 2019 ; 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 eluder dimension ( Jin et al., 2021 ) . Our work introduces the composite MDPs with high-dimensional feature space and low-rank plus sparse transition, extending beyond pure low-rank models. We provide the first theoretical guarantees for UCB Q-learning under this composite structure. Multitask RL and Meta RL. Research in multitask and meta-RL has evolved through several key theoretical advances. 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) extended this framework by studying weight vectors spanning low-dimensional spaces, showing that sample efficiency improves when the rank is much smaller than both the ambient dimension and number of tasks. Arora et al. (2020) demonstrated how representation learning reduces sample complexity in imitation learning settings, providing theoretical guarantees for learning shared structure across tasks. Lu et al. (2022) further developed this direction by analyzing multitask RL with low Bellman error and unknown representations, establishing bounds that improve with task similarity. 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 & Pacchiano (2022) extended these results to meta-RL for linear mixture MDPs, showing how learned structure transfers to new tasks. In parallel, research on shared representations by 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. Our composite MDP structure advances this line of work by explicitly modeling deviations from low-rank similarity through a 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. 2 Problem Formulation Episodic MDPs. We consider an episodic Markov decision process (MDP) with finite horizon. It is defined by a tuple \mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\mu,H) , where \mathcal{S} denotes the state space, \mathcal{A} represents the action space, H is the finite time horizon, r:\mathcal{S}\times\mathcal{A}\to[0,1] the reward function, P is the state transition probability, and \mu is the initial state distribution. A policy \pi:\mathcal{S}\times[H]\rightarrow\mathcal{A} maps each state-time pair to an action that the agent takes in the episode. For each time step h\in[H] , the value function V^{\pi}_{h}:\mathcal{S}\rightarrow\mathbb{R} evaluates the expected cumulative reward from following policy \pi starting from state s at time h , defined as V^{\pi}_{h}(s)=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},\pi(s_{h^{\prime}}))\mid s_{h}=s\right] , and V^{\pi}_{H+1}(s)=0 , while the action-value function Q^{\pi}_{h}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} evaluates the value of taking action a in state s at time h , given by Q^{\pi}_{h}(s,a)=r_{h}(s,a)+\mathbb{E}\left[\sum_{h^{\prime}=h+1}^{H}r_{h^{\prime}}(s_{h^{\prime}},\pi(s_{h^{\prime}}))\mid s_{h}=s,a_{h}=a\right] and Q^{\pi}_{H}(s,a)=r_{h}(s,a). The Bellman equation for V^{\pi}_{h} and Q^{\pi}_{h} can be expressed as: V^{\pi}_{h}(s)=Q^{\pi}_{h}(s,\pi_{h}(s)),\ Q^{\pi}_{h}(s,a)=r_{h}(s,a)+[PV^{\pi}_{h+1}](s,a). The Bellman optimally equations for the optimal value function and action-value function is as follows: V^{*}_{h}(s)=\max_{a\in A}\left\{r_{h}(s,a)+[PV^{*}_{h+1}](s,a)\right\},\quad V^{*}_{H+1}(s)=0, Q^{*}_{h}(s,a)=r_{h}(s,a)+[PV^{*}_{h+1}](s,a),\quad Q^{*}_{H}(s,a)=r_{h}(s,a). The cumulative regret quantifies the performance discrepancy of an agent over episodes. Given an initial state s_{0}\sim\mu , for the n^{th} episode, the regret is the value difference of the optimal policy V^{*}(s_{0}) and the agent’s chosen policy V^{\pi_{n}}(s_{0}) which based on its experience up to the beginning of the n^{th} episode and applied throughout the episode. Accumulating over N episodes, it is defined as: Regret(N)=\sum_{n=1}^{N}\mathbb{E}_{\mu}\left[V^{*}(s_{0})-V^{\pi_{n}}(s_{0})\right] The agent aims to learn a sequence of policies (\pi_{1},\ldots,\pi_{N}) 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. Composite MDPs. Let \phi(\cdot)\in\mathbb{R}^{p} and \psi(\cdot)\in\mathbb{R}^{q} be feature functions where p and q can be large. Consider probability transitions \mathbb{P}(s^{\prime}|s,a) that can be fully embedded in the feature space via a core matrix M^{*} : \mathbb{P}(s^{\prime}|s,a)=\phi(s,a)^{\top}\cdot M^{*}\cdot\psi(s^{\prime}). Since feature dimensions p and q 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. To capture how transition dynamics combine shared core elements with scenario-specific variations, we impose the following structured assumption on the transition matrix: Definition 1 (Composite MDPs) . A probability transition model \mathbb{P}:{\cal S}\times{\cal A}\rightarrow\Delta({\cal A}) can be fully embedded in the feature space characterized by two given feature functions \phi(\cdot)\in\mathbb{R}^{p} and \psi(\cdot)\in\mathbb{R}^{q} where both p and q can be large. The core matrix of the transition model decomposes as: \mathbb{P}(s^{\prime}|s,a)=\phi(s,a)^{\top}\cdot(L^{*}+S^{*})\cdot\psi(s^{\prime}), where L^{*} is a low-rank incoherent matrix and S^{*} is a sparse matrix. Remark 1 . The composite MDP model we propose differs from both the linear MDP and the low-rank MDP. While the linear MDP assumes a linear structure for the transition matrix and requires knowledge of the feature maps, the low-rank MDP does not demand such knowledge but constrains the feature map to a known function class. Our model allows high-dimensional feature space with a similar assumption to the low-rank MDP but augments it with a extra sparse component. 3 Single-Task UCB- Q -Learning under High-Dimensional Composite MDPs This section introduces UCB- Q -Learning for composite MDPs with a high-dimensional feature space. Specifically, we consider the setting where the feature dimensions p,q\gg N , and the transition core M^{*} is no longer a low-rank matrix. As a 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 are required. For any tuples (s_{i,h},a_{i,h}) from episode i and stage h : We define \phi_{i,h}=\phi(s_{i,h},a_{i,h}) , \psi_{i,h}=\psi(s_{i,h}) , and \boldsymbol{K}_{\psi}:=\sum_{s^{\prime}\in{\cal S}}\psi(s^{\prime})\psi(s^{\prime})^{\top} . Our estimator is based on the following population-level equation at each step h , \displaystyle\mathbb{E}\left[\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}\mid s_{i,h},a_{i,h}\right]=\sum_{s^{\prime}}\mathbb{P}(s^{\prime}|s_{i,h},a_{i,h})\psi(s^{\prime})^{\top}\boldsymbol{K}_{\psi}^{-1} \displaystyle=\sum_{s^{\prime}}\phi_{i,h}^{\top}(L^{*}+S^{*})\psi(s^{\prime})\psi(s^{\prime})^{\top}\boldsymbol{K}_{\psi}^{-1} \displaystyle=\phi_{i,h}^{\top}(L^{*}+S^{*}). (1) This motivates us to use the sample-level counterpart of ( 1 ) to estimate L^{*} and S^{*} . 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. Assumption 1 . Let L^{*}=U^{*}\Sigma^{*}V^{*T} be the singular value decomposition (SVD) of L^{*} . We assume that: (i) (Incoherence.) \|U^{*}\|_{2,\infty},\|V^{*}\|_{2,\infty}\leq\sqrt{\frac{\mu r}{p}} . (ii) (Sufficient sparsity.) Matrix S^{*} contains at most s non-zero entries, where s\leq\overline{s}:=\frac{\max\{p,q\}}{4C_{S}\mu r^{3}} , for some constant C_{S} . Remark 2 . The incoherence condition ensures that the singular vectors of a low-rank matrix are not overly concentrated in any single direction or entry, a 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 \mu 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. We consider the online learning setting and propose to estimate L^{*} and S^{*} in the composite MDP by optimizing the following hard-constrained least-square objective for each episode n\in[N] with collected tuples (s_{i,h},a_{i,h}) from previous episode i\in[n] and stage h\in[H] : \displaystyle(\widehat{L}_{n},\widehat{S}_{n})\in \displaystyle\underset{L,S\in\mathbb{R}^{p\times q}}{\arg\min}\;\sum_{i0 such that a_{n}\leq Cb_{n} . \widetilde{\cal O}(\cdot) is similarly defined, neglecting logarithmic factors. Constants c,C,c_{0},\cdots may vary from line to line. Appendix A Regret Analysis of the Single-Task UCB- Q -Learning with Composite MDP Structures We present below the proof of Theorem 1 . The proof of Lemma 1 emerges as an intermediate step along the way. Proof of Theorem 1 . 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 {\cal E}_{n} , i.e., (L^{*},S^{*})\in{\cal B}_{n^{\prime}} for any n^{\prime}\leq n-1 . We assume {\cal E}_{n} holds first and use concentration to prove that {\cal E}_{n} holds with high probability later. We denote E_{n}=\mathds{1}_{{\cal E}_{n}} . 1. Under {\cal E}_{n} , prove Q_{n,h}\geq Q_{h}^{*} using induction. 2. Bound Q_{n,h}(s_{n,h},a_{n,h})-[r(s_{n,h},a_{n,h})+P(\cdot|s_{n,h},a_{n,h})^{T}V_{n,h+1}] . 3. Bound the total regret by one-step errors derived in Step 2. We elaborate each step in the sequel. A.1 Upper confidence bound Lemma 3 . Given any state-action pair (s,a)\in\mathcal{S}\times\mathcal{A} , for each episode n and decision step h , we have: Q_{n,h}(s,a)\geq Q_{h}^{*}(s,a). Proof. We use induction. At h=H , we have Q_{n,H}=Q_{H}^{*}(s,a)=r(s,a) . Assuming the argument is true for 1n^{\prime} . A.4 Confidence region In this subsection, we validate the confidence region. Recall the CR is defined in ( 3 ). Denote X_{n}=\begin{bmatrix}\phi_{1,1}^{\top}\\ \cdots\\ \phi_{1,H}^{\top}\\ \cdots\\ \phi^{\top}_{n-1,H}\end{bmatrix} and Y_{n}=\begin{bmatrix}\psi_{1,1}^{\top}\boldsymbol{K}_{\psi}^{-1}\\ \cdots\\ \psi_{1,H}^{\top}\boldsymbol{K}_{\psi}^{-1}\\ \cdots\\ \psi_{n-1,H}^{\top}\boldsymbol{K}_{\psi}^{-1}\end{bmatrix} , we have the observational model as follows: \displaystyle Y_{n}=X_{n}(L^{*}+S^{*})+W_{n} where W_{n}=Y_{n}-X_{n}(L^{*}+S^{*}) . In view of Chai & Fan (2024) , we need the observation model to satisfy the restricted strong convexity condition in order for the low-rank part and sparse part to be separated. \displaystyle\lambda_{\min}\left(\frac{X_{n}^{\top}X_{n}}{n-1}\right)\geq c_{1}. (20) We will later give specific cases in which this inequality holds. In the sequel, we bound \|X_{n}^{\top}W_{n}\|_{2} and \|X_{n}^{\top}W_{n}\|_{\max} . In fact, we can express X_{n}^{\top}W_{n} as \displaystyle X_{n}^{\top}W_{n}=\sum_{i=1}^{n-1}\sum_{h=1}^{H}\phi_{i,h}\left(\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}-\phi_{i,h}^{\top}M^{*}\right). Note that \mathbb{E}\left[\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}-\phi_{i,h}^{\top}M^{*}|{\cal F}_{i,h}\right]=0 , and X_{n}^{\top}W_{n} is a sum of martingale differences. Let Z_{i,h}=\phi_{i,h}\left(\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}-\phi_{i,h}^{\top}M^{*}\right) , we have that \displaystyle\|Z_{i,h}\|_{2} \displaystyle=\|\phi_{i,h}\|\cdot\|\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}-\phi_{i,h}^{\top}M^{*}\| \displaystyle=\|\phi_{i,h}\|\cdot\left(\|\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}\|+\|\phi_{i,h}^{\top}M^{*}\|\right) \displaystyle\leq 2C_{\phi}C^{\prime}_{\psi}, where we used \|\phi_{i,h}^{\top}M^{*}\|=\Big\|\mathbb{E}\left[\psi_{i,h}^{\top}\boldsymbol{K}_{\psi}^{-1}|{\cal F}_{i,h}\right]\Big\|\leq C^{\prime}_{\psi} . On the other hand, \Big\|\sum_{i=1}^{n-1}\sum_{h=1}^{H}\mathbb{E}[Z_{i,h}^{\top}Z_{i,h}|{\cal F}_{i,h}]\Big\|\leq 4nH(C_{\phi}C_{\psi}^{\prime})^{2} and \Big\|\sum_{i=1}^{n-1}\sum_{h=1}^{H}\mathbb{E}[Z_{i,h}Z_{i,h}^{\top}|{\cal F}_{i,h}]\Big\|\leq 4nH(C_{\phi}C_{\psi}^{\prime})^{2}. By Matrix Freedman inequality (Corollary 1.3 in Tropp (2011) ), we have with probability at least 1-\delta that \displaystyle\|X_{n}^{\top}W_{n}\|_{2}\lesssim C_{\phi}C^{\prime}_{\psi}\log\left(\frac{d}{\delta}\right)+C_{\phi}C_{\psi}^{\prime}\sqrt{nH\log\left(\frac{d}{\delta}\right)}. Similarly, each entry of X_{n}^{\top}W_{n} is the sum of martingale differences, almost surely bounded by 2C_{\phi\psi} , and we have by Azuma-Hoeffding’s inequality and a union bound over d^{2} entries that, with probability at least 1-\delta , \displaystyle\|X_{n}^{\top}W_{n}\|_{\max}=\max_{i,j}|[X_{n}^{\top}W_{n}]_{ij}|\lesssim C_{\phi\psi}\sqrt{nH\log\left(\frac{d}{\delta}\right)}. Confidence Region By the optimality condition, we have \displaystyle\|Y_{n}-X_{n}(\widehat{L}_{n}+\widehat{S}_{n})\|_{F}^{2}\leq\|Y_{n}-X_{n}(L^{*}+S^{*})\|_{F}^{2}. Expanding on both sides yields \displaystyle\|X_{n}(\Delta_{L}+\Delta_{S})\|_{F}^{2} \displaystyle\leq 2\langle W_{n},X_{n}(\Delta_{L}+\Delta_{S})\rangle \displaystyle=2\langle X_{n}^{\top}W_{n},\Delta_{L}+\Delta_{S}\rangle \displaystyle\leq 2\|X_{n}^{\top}W_{n}\|_{2}\|\Delta_{L}\|_{*}+2\|X_{n}^{\top}W_{n}\|_{\max}\|\Delta_{S}\|_{1} \displaystyle\leq 2\langle X_{n}^{\top}W_{n},\Delta_{L}+\Delta_{S}\rangle \displaystyle\leq 2\sqrt{2r}\|X_{n}^{\top}W_{n}\|_{2}\|\Delta_{L}\|_{F}+2\sqrt{2s}\|X_{n}^{\top}W_{n}\|_{\max}\|\Delta_{S}\|_{F}, where we denote \Delta_{L}:=\widehat{L}_{n}-L^{*} and \Delta_{S}:=\widehat{S}_{n}-S^{*} . On the other hand, by ( 20 ) and separation lemma in Chai & Fan (2024) , we have that \displaystyle\|X_{n}(\Delta_{L}+\Delta_{S})\|_{F}^{2} \displaystyle\geq c_{1}(n-1)\|\Delta_{L}+\Delta_{S}\|_{F}^{2} \displaystyle\geq\frac{c_{1}(n-1)}{2}\left(\|\Delta_{L}\|_{F}^{2}+\|\Delta_{S}\|_{F}^{2}\right). Putting together, we have \displaystyle\|\Delta_{L}\|_{F}^{2}+\|\Delta_{S}\|_{F}^{2} \displaystyle\leq\frac{4}{c_{1}(n-1)}\sqrt{2r}\|X_{n}^{\top}W_{n}\|_{2}\|\Delta_{L}\|_{F}+\sqrt{2s}\|X_{n}^{\top}W_{n}\|_{\max}\|\Delta_{S}\|_{F} \displaystyle\leq\frac{4}{c_{1}(n-1)}\sqrt{2r\|X_{n}^{\top}W_{n}\|_{2}^{2}+2s\|X_{n}^{\top}W_{n}\|_{\max}^{2}}\cdot\sqrt{\|\Delta_{L}\|_{F}^{2}+\|\Delta_{S}\|_{F}^{2}} which implies that \displaystyle\|\Delta_{L}\|_{F}^{2}+\|\Delta_{S}\|_{F}^{2} \displaystyle\leq\frac{32}{c_{1}^{2}(n-1)^{2}}\left(r\|X_{n}^{\top}W_{n}\|_{2}^{2}+s\|X_{n}^{\top}W_{n}\|_{\max}^{2}\right). Plugging in the aforementioned bounds of \|X_{n}^{\top}W_{n}\|_{2} and \|X_{n}^{\top}W_{n}\|_{\max} , we deduce that {\cal B}_{n} is a valid \delta -confidence region if we take \displaystyle\beta_{n}=\frac{C_{\beta}}{n^{2}}\left(r(C_{\phi}C^{\prime}_{\psi})^{2}nH\log(d/\delta)+sC_{\phi\psi}^{2}nH\log(d/\delta)\right)=\frac{C_{\beta}H\log(d/\delta)}{n}\left(r(C_{\phi}C^{\prime}_{\psi})^{2}+sC_{\phi\psi}^{2}\right) (21) for some large enough C_{\beta} . In particular, we take \delta=1/(N^{2}H) in the above display, then by the union bound, \mathbb{P}(E_{N}=0)\leq N\cdot\frac{1}{N^{2}H}=\frac{1}{NH} . Combining the definition of \beta_{n} with ( 19 ), we obtain that \displaystyle\text{Regret}(NH) \displaystyle\leq C_{\phi}C_{\psi}H^{2}\sum_{n=1}^{N}\sqrt{2\beta_{n}}+1 \displaystyle\lesssim C_{reg}\sqrt{NH^{5}}, where C_{reg}:=C_{\phi}C_{\psi}\sqrt{C_{\beta}\left(r(C_{\phi}C^{\prime}_{\psi})^{2}+sC_{\phi\psi}^{2}\right)\log(dNH)} . As a byproduct, we have that by the end of the N episode, with probability at least 1-1/(N^{2}H) , \displaystyle\left\lVert L-\widehat{L}_{N}\right\rVert_{F}^{2}+\left\lVert S-\widehat{S}_{N}\right\rVert_{F}^{2}\leq\beta_{N}. A.5 Discussion on Condition ( 20 ) Now we provide an example where Condition ( 20 ) holds. At a high level, \phi_{i,h} may be highly correlated, across different steps and episodes. Nonetheless, note that each episodes starts at independent initial states, hence providing diversity to the linear operator X_{n} . In fact, Condition ( 20 ) holds when \phi(s,a) depends mainly on s and a adds a perturbation effect. To be more concrete, consider the following lemma as an example. Lemma 5 . Suppose there exists some function \overline{\phi} such that \|\phi(s,a)-\overline{\phi}(s)\|_{2}\leq\eta . And \displaystyle\lambda_{\min}\left(\mathbb{E}_{\mu}[\overline{\phi}(s)\overline{\phi}(s)^{\top}]\right)\geq c_{\min}. If \eta(2C_{\phi}+\eta)\leq\frac{c_{\min}}{4} and n\geq C_{e}d for some constant C_{e} , then with probability at least 1-2e^{-c_{e}n} , Condition ( 20 ) holds with c_{1}=c_{\min}/4 . Proof. Denote \mathbb{E}_{\mu}[\overline{\phi}(s)\overline{\phi}(s)^{\top}] by \Sigma_{\mu} . As |\overline{\phi}(s)^{\top}v|\leq\|\overline{\phi}(s)\|\leq C_{\phi} for any v\in\mathbb{S}^{d} , we have that \overline{\phi}(s) is subGaussian with variance proxy (C-\phi/2)^{2} . By (5.25) in Vershynin (2010) , there exists some constants C_{e},c_{e} such that with probability at least 1-2e^{-c_{e}n} , \displaystyle\frac{1}{n-1}\sum_{i=1}^{n-1}\overline{\phi}(s_{i,1})\overline{\phi}(s_{i,1})^{\top}\succeq\frac{1}{2}\Sigma_{\mu}\succeq\frac{c_{\min}}{2}I as long as n\geq C_{e}d . Let \Delta=\frac{1}{n-1}\sum_{i=1}^{n-1}\overline{\phi}(s_{i,1})\overline{\phi}(s_{i,1})^{\top}-\frac{1}{n-1}\sum_{i=1}^{n-1}\phi_{i,1}\phi_{i,1}^{\top} , we have for any v\in\mathbb{S}^{d} that \displaystyle v^{\top}\Delta v \displaystyle=\frac{1}{n-1}\sum_{i=1}^{n-1}\left([\overline{\phi}(s_{i,1})^{\top}v]^{2}-[\phi_{i,1}^{\top}v]^{2}\right) \displaystyle\leq\frac{1}{n-1}\sum_{i=1}^{n-1}\Big\|\overline{\phi}(s_{i,1})-\phi_{i,1}\Big\|\cdot\Big\|\overline{\phi}(s_{i,1})+\phi_{i,1}\Big\| \displaystyle\leq\eta(2C_{\phi}+\eta). Hence \|\Delta\|\leq\eta(2C_{\phi}+\eta)\leq\frac{c_{\min}}{4} . It follows that \displaystyle\frac{1}{n-1}\sum_{i=1}^{n-1}\phi_{i,1}\phi_{i,1}^{\top}\succeq\frac{c_{\min}}{4}I. To conclude, note that \displaystyle\frac{1}{n-1}\sum_{i=1}^{n-1}\sum_{h=1}^{H}\phi_{i,h}\phi_{i,h}^{\top}\succeq\frac{1}{n-1}\sum_{i=1}^{n-1}\phi_{i,1}\phi_{i,1}^{\top}\succeq\frac{c_{\min}}{4}I. ∎ Remark 8 . The condition n\geq C_{e}d requires a warm start. For n\leq C_{e}d , one can use a fixed policy to generate samples. This will not affect the total regret as long as dH is neglegible compared to \sqrt{NH^{5}} . Appendix B Regret Analysis for UCB-TQL under Composite MDPs In this section, we provide proof for Theorem 2 . The pipeline is similar to the single-task setting. We start by constructing the confidence region. To that end, again denote Denote X_{n}^{(1)}=\begin{bmatrix}\phi_{1,1}^{(1)\top}\\ \cdots\\ \phi_{1,H}^{(1)\top}\\ \cdots\\ \phi^{(1)\top}_{n-1,H}\end{bmatrix} and Y_{n}^{(1)}=\begin{bmatrix}\psi_{1,1}^{(1)\top}\boldsymbol{K}_{\psi}^{-1}\\ \cdots\\ \psi_{1,H}^{(1)\top}\boldsymbol{K}_{\psi}^{-1}\\ \cdots\\ \psi_{n-1,H}^{(1)\top}\boldsymbol{K}_{\psi}^{-1}\end{bmatrix} , we have the observational model as follows: \displaystyle Y_{n}^{(1)}=X_{n}^{(1)}(L^{*}+S^{*(0)}+D^{*})+W_{n} where W_{n}:=Y_{n}^{(1)}-X_{n}^{(1)}(L^{*}+S^{*(0)}+D^{*}) . By the optimality condition, we have \displaystyle\|Y_{n}^{(1)}-X_{n}^{(1)}(\widehat{L}+\widehat{S}^{(0)}-\widehat{D}_{n})\|_{F}^{2}\leq\|Y_{n}^{(1)}-X_{n}^{(1)}(L^{*}+S^{*(0)}+D^{*})\|_{F}^{2}. After some calculation, we obtain \displaystyle\|X_{n}^{(1)}(\widehat{D}_{n}-D^{*})\|_{F}^{2} \displaystyle\leq 2\Big\langle Y_{n}^{(1)}-X_{n}^{(1)}(\widehat{L}+\widehat{S}^{(0)}-D^{*}),X_{n}^{(1)}(\widehat{D}_{n}-D^{*})\Big\rangle \displaystyle=2\Big\langle X_{n}^{(1)\top}\left(W_{n}+X_{n}^{(1)}(L^{*}-\widehat{L}+S^{*(0)}-\widehat{S}^{(0)})\right),\widehat{D}_{n}-D^{*}\Big\rangle \displaystyle\leq 2\Big\|X_{n}^{(1)\top}W_{n}\Big\|_{\infty}\Big\|\widehat{D}_{n}-D^{*}\Big\|_{1}+2\Big\|X_{n}^{(1)\top}X_{n}^{(1)}(L^{*}-\widehat{L}+S^{*(0)}-\widehat{S}^{(0)})\Big\|_{F}\Big\|\widehat{D}_{n}-D^{*}\Big\|_{F} \displaystyle\leq 2\sqrt{2e}\Big\|X_{n}^{(1)\top}W_{n}\Big\|_{\max}\Big\|\widehat{D}_{n}-D^{*}\Big\|_{F}+2\Big\|X_{n}^{(1)\top}X_{n}^{(1)}(L^{*}-\widehat{L}+S^{*(0)}-\widehat{S}^{(0)})\Big\|_{F}\Big\|\widehat{D}_{n}-D^{*}\Big\|_{F}. We have, similar as before, with probability at least 1-\delta , \displaystyle\|X_{n}^{(1)\top}W_{n}\Big\|_{\max}\lesssim C_{\phi\psi}\sqrt{nH\log\left(\frac{d}{\delta}\right)}. If \displaystyle\lambda_{\min}\left(\frac{X_{n}^{(1)\top}X_{n}^{(1)}}{n-1}\right)\geq c_{1}, \displaystyle\lambda_{\max}\left(\frac{X_{n}^{(1)\top}X_{n}^{(1)}}{n-1}\right)\leq C_{1}, then it holds that \displaystyle\|\widehat{D}_{n}-D^{*}\|_{F}^{2}\lesssim\frac{eC_{\phi\psi}^{2}H\log\left(\frac{d}{\delta}\right)}{n}+\|L^{*}-\widehat{L}\|_{F}^{2}+\|S^{*(0)}-\widehat{S}^{(0)}\|_{F}^{2}. Suppose at the first stage, we established \|L^{*}-\widehat{L}\|_{F}^{2}+\|S^{*(0)}-\widehat{S}^{(0)}\|_{F}^{2}\leq\beta_{N_{0}} with probability at least 1-1/(2N^{2}H) , where \displaystyle\beta_{N_{0}}=\frac{C_{\beta}H\log(d/\delta)}{N_{0}}\left(r(C_{\phi}C^{\prime}_{\psi})^{2}+sC_{\phi\psi}^{2}\right), as in ( 21 ). Naive CR Recall that we can construct a naive confidence region as \displaystyle\mathcal{B}_{n}=\left\{(L,S)\mid\left\lVert L-\widehat{L}_{n}\right\rVert_{F}^{2}+\left\lVert S-\widehat{S}_{n}\right\rVert_{F}^{2}\leq\beta^{(1)}_{n}\right\} where \beta^{(1)}_{n}:=\beta_{N_{0}}+\frac{eC_{\phi\psi}^{2}H\log\left(dNH\right)}{n} . When using this confidence region to construct optimistic value functions, we can plug the value of \beta_{n}^{(1)} into ( 19 ). It follows that \displaystyle\text{Regret}(NH) \displaystyle\lesssim C_{\phi}C_{\psi}H^{2}\sum_{n=1}^{N}\sqrt{\beta_{n}^{(1)}}+1 \displaystyle\lesssim C_{\phi}C_{\psi}H^{2}\left(N\sqrt{\beta_{N_{0}}}+\sqrt{eC_{\phi\psi}^{2}NH\log\left(dNH\right)}\right). Remark 9 . When N_{0}\gg N , this bound is dominated by the second term, which depends on C_{\phi} . Tight CR As illustrated in the proof sketch, we can achieve better rate by constructing a more fine-grained confidence region as \displaystyle\widetilde{{\cal B}}_{n}=\left\{(L,S,D)\mid\left\lVert L-\widehat{L}^{(0)}\right\rVert_{F}^{2}+\left\lVert S-D-\widehat{S}^{(0)}\right\rVert_{F}^{2}\leq\beta_{N_{0}},\ \left\lVert D-\widehat{D}_{n}\right\rVert_{F}^{2}\leq\beta_{n}^{(1)},\ \left\lVert D\right\rVert_{0}\leq e\right\}. It is straightforward to show that (L^{*},S^{*(0)},D^{*})\in\widetilde{\cal B}_{n} . We then carry out a more refined one-step analysis, similar in the vein of Section 3.2.2. In particular, let (\widetilde{L},\widetilde{S},\widetilde{D})=\arg\max_{\begin{subarray}{c}L,S\in\widetilde{{\cal B}}_{n}\end{subarray}}\phi(s,a)^{\top}(L+S)\Psi^{\top}V_{n,h+1} , it holds that \displaystyle Q_{n,h}(s_{n,h},a_{n,h})-\left(r(s_{n,h},a_{n,h})+[P_{h}V_{n,h+1}](s_{n,h},a_{n,h})\right) (22) \displaystyle\leq\left\lVert\phi_{n,h}^{\top}(\widetilde{L}-L^{*})\right\rVert_{2}\left\lVert\Psi^{\top}V_{n,h+1}\right\rVert_{2}+\left\lVert\phi_{n,h}^{\top}\left(\widetilde{S}-\widetilde{D}-S^{*}+D^{*}\right)\right\rVert_{2}\left\lVert\Psi^{\top}V_{n,h+1}\right\rVert_{2}+\left|\phi_{n,h}^{\top}\left(\widetilde{D}-D^{*}\right)\Psi^{\top}V_{n,h+1}\right| \displaystyle\leq H\left(C_{\psi}\left\lVert\phi_{n,h}^{\top}(\widetilde{L}-L^{*})\right\rVert_{2}+C_{\psi}\left\lVert\phi_{n,h}^{\top}\left(\widetilde{S}-\widetilde{D}-S^{*}+D^{*}\right)\right\rVert_{2}\right)+\sqrt{2e}HC_{\phi}^{\prime}C_{\psi}\left\lVert\widetilde{D}-D^{*}\right\rVert_{F} \displaystyle\leq H\left(C_{\psi}\left\lVert\phi_{n,h}\right\rVert_{2}\left\lVert\widetilde{L}-L^{*}\right\rVert_{F}+C_{\psi}\left\lVert\phi_{n,h}\right\rVert_{2}\left\lVert\widetilde{S}-\widetilde{D}-S^{*}+D^{*}\right\rVert_{F}\right)+\sqrt{2e}HC_{\phi}^{\prime}C_{\psi}\left\lVert\widetilde{D}-D^{*}\right\rVert_{F} \displaystyle\leq C_{\phi}C_{\psi}H\left(\left\lVert\widetilde{L}-L^{*}\right\rVert_{F}+\left\lVert\widetilde{S}-\widetilde{D}-S^{*}+D^{*}\right\rVert_{F}\right)+\sqrt{2e}HC_{\phi}^{\prime}C_{\psi}\left\lVert\widetilde{D}-D^{*}\right\rVert_{F} \displaystyle\leq C_{\phi}C_{\psi}H\sqrt{2\beta_{N_{0}}}+C_{\phi}^{\prime}C_{\psi}H\sqrt{4\beta_{n}^{(1)}e}, 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 \displaystyle\text{Regret}(NH) \displaystyle\lesssim C_{\phi}C_{\psi}H^{2}\sum_{n=1}^{N}\sqrt{\beta_{N_{0}}}+C_{\phi}^{\prime}C_{\psi}H^{2}\sum_{n=1}^{N}\sqrt{4\beta_{n}^{(1)}e} \displaystyle\lesssim\left(C_{\phi}+C_{\phi}^{\prime}\sqrt{e}\right)C_{\psi}H^{2}N\sqrt{\beta_{N_{0}}}+C_{\phi}^{\prime}C_{\psi}H^{2}\sqrt{eC_{\phi\psi}^{2}NH\log\left(dNH\right)}. Plugging the definition of \beta_{N_{0}} completes the proof. Remark 10 . When N_{0}\gg N , this bound is dominated by the second term, which does not depend on C_{\phi} , but rather on C_{\phi}^{\prime} . It is tighter than the rate of naive CR approach as C_{\phi}\geq C_{\phi}^{\prime} .