The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure

Authors: tyler  sam
yudong  chen
christina  lee
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:44:54

Abstract: Many reinforcement learning (RL) algorithms are too costly to use in practice due to the large sizes $S,A$ of the problem's state and action space. To resolve this issue, we study transfer RL with latent low rank structure. We consider the problem of transferring a latent low rank representation when the source and target MDPs have transition kernels with Tucker rank $(S, d, A)$, $(S ,S , d), (d, S , A )$, or $(d , d , d )$. In each setting, we introduce the transfer-ability coefficient $\alpha$ that measures the difficulty of representational transfer. Our algorithm learns latent representations in each source MDP and then exploits the linear structure to remove the dependence on $S , A $, or $SA $ in the target MDP regret bound. We complement our positive results with information theoretic lower bounds that show our algorithms (excluding the ($d, d, d$) setting) are minimax-optimal with respect to $\alpha$.

Main paper: 
 introduction: 
 Recently, reinforcement learning (RL) algorithms have exhibited great success on a variety of problems, e.g., video games [31] , robotics [21] , etc, that require a series of decisions over time. These algorithms can be used on any problem that can be modeled as a Markov decision process (MDP) with state space cardinality S, action space cardinality A, and horizon H. However, RL algorithms' practical application is constrained due to the large amounts of data and computational resources required to train models that outperform heuristic approaches. This limitation arises due to the inefficient scaling of RL algorithms with respect to the size of the state and action spaces. In an online setting where rewards are incurred during the process of learning, we may want to minimize the regret, or the difference between the reward of an optimal policy and the reward collected by the learner. In the finite-horizon online episodic MDP setting with K episodes, any algorithm must incur regret of at least Ω( √ SAH 3 K) [18] . This regret bound is often too large in practice as many problems modeled as MDPs have large state and action spaces. For example, in the Atari games [25] , the state space is the set of all images as a vector of pixel values.One way to remove the dependence on the state or action space in RL algorithms is to leverage existing data or models from similar problems through transfer learning. In the transfer learning setting for MDPs, the learner can interact with or query from multiple source MDPs, which the learner can utilize at low-cost to improve their performance in the target MDP [27] . The efficacy of the transfer learning approach depends both on the similarity between the source and the target MDPs, and how information is utilized when transferring knowledge between the source and target.As feature learning in MDPs is difficult and expensive, reusing learned low rank representations can greatly improve the performance on new problems. Thus, in this work, we consider the setting when the source and target MDPs exhibit latent low rank structure, and the transfer RL task is to learn latent low rank representation of the state, action, or state-action pair from the source MDPs, and subsequently use it to improve learning on the target MDP. If the learned representations were perfect, then one could remove all dependence on the state space or action space in the learning task on the 1 : Theoretical guarantees of our algorithms alongside results from literature in the different Tucker rank settings. See Table 3 for the regret bounds of algorithms in each Tucker rank setting with known latent representations.target MDP. This approach relies on a critical assumption that the transition kernels of the source and target MDPs have low Tucker rank when viewed as an S-by-S-by-A tensor.The work [4] studied this problem when the transition kernel is low rank along the first mode, i.e., with Tucker rank (d, S, A) where d < min{S, A}; this is also referred to as the Low Rank MDP model. We also consider this setting, as well as the complementary settings in which the transition kernel has low Tucker rank along the second or third mode, i.e., Tucker rank (S, d, A) or (S, S, d).In addition, we study the The different modes are not interchangeable algorithmically as there is a directionality due to the time of the transition between the current and future state. Additionally, the algorithm in [4] is not computationally tractable as it utilizes an optimization oracle which may not be practical. They assume that the latent representations are within a known finite function class. Our work proposes a computationally efficient algorithm that can handle latent low rank structure on the transition kernel along any of the three different modes.As the success of a transfer learning approach depends on the similarity between the source and target problems, we introduce the transfer-ability coefficient α, which quantifies the similarity between the source and target problems under our low rank assumptions. This coefficient, genearlizing the task-relatedness in [4] , captures the unique challenge in the transfer reinforcement learning setting.Our Contributions: We propose new computationally efficient transfer RL algorithms that admit the desired efficient regret bounds under all low Tucker rank settings (S, d, A), (S, S, d), (d, S, A),  and (d, d, d ). With enough samples from the source MDPs, we remove the dependence on S, A, or SA in the regret bound on the target MDP. In addition, we introduce the transfer-ability coefficient α that measures the ease of transferring a latent representation from the source MDPs to target MDP. We establish information theoretic lower bounds showing that our algorithms are optimal with respect to α (excluding the (d, d, d) Tucker rank setting). In particular, in the (d, S, A) Tucker rank setting, we achieve the optimal dependence of α 2 while [4] is sub-optimal with a dependence on α 5 .Table 1 summarizes our main theoretical results, suppressing the dependence on common matrix estimation terms, and compares them with the results from [4] . 1 In the appendix, we further consider the setting where one has access to generative models in both the source and target problems, and show that the benefits of transfer learning go beyond alleviating exploration burden.2 Related Work RL in the (d, S, A) Tucker rank Setting: There exists an extensive literature on Linear MDPs and Low-rank MDPs, which correspond to the (d, S, A) Tucker rank setting. Linear MDPs assume that the dynamics are linear with respect to a known feature mapping ϕ. This allows one to remove all dependence on the size of the state and action spaces and replace it with the rank d of the latent space [17, 37, 36, 34] . The work [13] proposes an algorithm that admits a regret bound of Õ( √ d2 H 2 T ), matching the known lower bounds. Our algorithm in the target phase modifies existing linear MDP algorithms to take advantage of the knowledge learned in the source phase. Low Rank MDPs impose the same low-rank structure as linear MDPs but assume that ϕ is unknown. To avoid dependence on the size of the state space, many works in this setting construct algorithms that utilize a computationally inefficient oracle to admit sample complexity or regret bounds that scale with the size of the action space and the log of the size of the function class the true low rank representation [3, 33, 26, 40] . [32] incurs sample complexity on SA instead of the size of the function class to learn near-optimal policies in reward free low rank MDPs.Transfer RL: As feature learning in low rank MDPs is difficult, [4, 10, 23, 15] study representational transfer in low rank MDPs. The work most closely related to ours is [4] , which performs reward-free exploration in the source problem to learn a sufficient representation to use in the target problem in the (d, S, A) Tucker rank setting. They propose a task relatedness coefficient that captures the existing representational transfer RL settings [10] . This coefficient is similar to our transfer-ability coefficient but differs as our low rank assumption is imposed on different modes of the probability transition tensor. Their algorithm admits a source sample complexity bound of Õ(A 4 α3 d 5 H 7 K 2 T log(|Φ||Γ|)) with a target regret bound of Õ(√ d 3 α 2 H 4 T ).Other transfer RL works [10, 23] require reach-ability assumptions to learn the latent representations in the source phase. Similar to transfer RL, reward free RL studies the problem of giving the learner access to only the transition kernel in the first phase, and in the second phase the learner must output a good policy when given multiple reward functions [19, 39, 11, 32] . While reward free RL is similar to our setting, enabling the dynamics to differ between the source and target phase greatly increases the difficulty and changes the objective in the source problem, i.e., learning a good latent representation instead of collecting trajectories that sufficiently explore the state space.RL in the (S, d, A) or (S, S, d) Tucker Rank Setting: The work [30] introduces the RL setting in which the transition kernel has Tucker rank (S, d, A) or (S, S, d). Assuming access to a generative model, their algorithms learn near-optimal polices with sample complexities that scale with S + A, thereby circumventing the SA lower bound for tabular reinforcement learning [6] . The work [35] consider the same low Tucker rank assumption on the dynamics but in the offline RL setting. The works [38, 29, 28] empirically show the benefits of combining matrix/tensor estimation with RL algorithms on common stochastic control tasks. [16] consider the low-rank bandits setting and use a similar algorithm to ours by estimating the singular subspaces of the reward matrix to improve the regret bound's dependence on the dimension of the problem. 
preliminaries: 
 We consider the transfer reinforcement learning setting introduced by [4] , in which the learner interacts with M finite-horizon source MDPs and one finite horizon episodic target MDP. All MDPs share the same discrete state space S with cardinality S, discrete action space A with cardinality A, and finite horizon H ∈ Z + . 2 Let r = {r h } h∈[H] be the deterministic unknown reward function of the target MDP, where r h : S × A → [0, 1]. For m ∈ [M ], let r m = {r m,h } h∈[H] be the deterministic unknown reward function for the mth source MDP, where r m,h : S × A → [0, 1]. 3 Let P = {P h } be the transition kernel for the target MDP, where P h (s ′ |s, a) is the probability of transitioning to state s ′ from state-action pair (s, a) at time step h. Similarly, for m ∈ [M ], P m is the transition kernel for mth source MDP and defined in the same way as P. An agent's policy has the form π = {π h } h∈[H] , π h : S → ∆(A), where π h (a|s) is the probability that the agent chooses action a at state s and time step h.The value function and action-value (Q) function of a policy π are the expected reward of following π given a starting state and starting action, respectively, beginning at time step h. We define these as )] for all (s, a, h) ∈ S × A × [H]. We define an ϵ-optimal policy π for ϵ > 0 as any policy that satisfies V * h (s) -V π h (s) ≤ ϵ for all s ∈ S, h ∈ [H]. Similarly, Q is ϵ-optimal if Q * h (s, a) -Q h (s, a) < ϵ for all (s, a, h) ∈ S × A × [H] . Also, we use the shorthand P h V (s, a) = E s ′ ∼P h (•|s,a) [V (s ′ )].EQUATIONIn the transfer RL problem, the learner first interacts with the M source MDPs without access to the target MDP. In this phase, called the source phase, the learner is given access to a generative model in each of the source MDPs. The generative model takes in a state-action pair (s, a) and time step h and outputs r h (s, a) and an independent sample from P h (•|s, a) [20] . Access to a generative model in the source phase is necessary; in particular, it has been shown in [4, Theorem 4.1] that without access to a generative model in the source phase, one cannot learn a near-optimal policy in the target phase using the learned representation. Then, in the next phase, called the target phase, the learner loses access to the source MDPs and interacts only with the target MDP in a standard online model, without access to a generative model. The performance of the learner is evaluated by two metrics: i) the regret in the target MDP, i.e., Regret(T) = k∈[K] V * 1 (s) -V π k 1 (s), where π k is the learner's policy in episode k, and ii) the number of samples taken in the source phase.For the reader's convenience, we first recall the standard definition of the Tucker rank of a tensor. Definition 1 (Tucker Rank [24] ). A tensor M ∈ R n1×n2×n3 has Tucker rank(d 1 , d 2 , d 3 ) if (d 1 , d 2 , d 3 )is the smallest such that there exists a core tensor X ∈ R d1×d2×d3 and matrices G i ∈ R ni×di for i ∈ [3] with orthonormal columns such thatM (a, b, c) = i∈[d1],j∈[d2],k∈[d3] X(i, j, k)G 1 (a, i)G 2 (b, j)G 3 (c, k).We note in passing that all our sample complexity and regret bounds in Table 1 remain valid when d is an upper bound on the exact rank. In standard MDPs, the transition kernel can have Tucker rank (S, S, A) as there is no low rank structure imposed on the tensor. In this work, we investigate the benefits of assuming that the transition kernel is low rank along each mode/dimension of the transition kernel, which corresponds to the (S, d, A), (S, S, d), and (d, S, A) Tucker rank settings. To illustrate the difference in these three settings, we consider d = 1 and present the corresponding structure of the transition kernel in Equations ( 1), (2) , and (3), respectively: Tucker rank (S, 1, A): P (s ′ |s, a) = µ(s)ϕ(s ′ , a),Tucker rank (S, S, 1):EQUATIONTucker rank (1, S, A): P (s ′ |s, a) = µ(s ′ )ϕ(s, a),for some functions µ, ϕ defined on the appropriate domains. Figure 1 pictorially displays the (S, S, d) Tucker rank assumption on the transition kernel. While the three settings may seem similar, the (S, d, A) and (S, S, d) Tucker rank settings differ significantly from the (d, S, A) Tucker rank setting (i.e., Low Rank MDP). In particular, the (d, S, A) setting assumes low rank structure across time, i.e., the current state and action vs. the next state, while the other Tucker rank assumptions impose low rank structure between the current state and action. These differences are significant as each setting requires different algorithms in the target problem and construction for the lower bounds. While the sample complexity and regret bound of each algorithm differ in each Tucker rank setting, one should choose which algorithm to use based on the low rank structure inherent in their problem. For example, in the (S, S, d) Tucker rank setting, one assumes that each action has a low rank For sake of brevity, we will only present our assumption and algorithm for the (S, S, d) Tucker rank setting in the main body of this work and defer the other settings to the appendix.G T = [0, 1] G 1 = [1, 0] G 2 = [ 1 -1/α 2 , 1/α]We first define the incoherence µ of a matrix, which is used in the regularity conditions of our Tucker rank assumption.Definition 2 (Incoherence). Let X ∈ R m×n have rank d with singular value decomposition X = U ΣV ⊤ with U ∈ R m×d , V ∈ R n×d . Then, X is µ-incoherent if for all i ∈ [m], j ∈ [n], ∥U (i, :)∥ 2 ≤ dµ/m and ∥V (j, :)∥ 2 ≤ dµ/n.A small µ guarantees that the signal in U and V is sufficiently spread out among the rows in those matrices. The notion of incoherence is pervasive in the low-rank estimation literature [7, 8] .Introduced in [30] , we assume that reward functions are low rank and the transition kernels have low Tucker rank in each of the source and target MDPs. The main benefit of Assumption 1 is that for any value function V , the Bellman update of any value function, Q h = r h + P h V , is a low rank matrix due to Proposition 4 [30] . Assumption 1. In each of the M source MDPs, the reward functions have rank d, and the transition kernels have Tucker rank (S, S, d). The target MDP has reward function with rank d ′ and transition kernels with Tucker rank (S, S, d ′ ) where d ′ ≤ dM . Thus, there existsS × S × d tensors U m,h , S × S × d ′ tensors U h s, A × d µ-incoherent matrices G m,h with orthonormal columns, A × d ′ µ-incoherent matrices G h with orthonormal columns, and S × d matrices W m,h , S × d ′ matrices W h such that P m,h (s ′ |s, a) = i∈[d] G m,h (a, i)U m,h (s ′ , s, i), r m,h (s, a) = i∈[d] G m,h (a, i)W m,h (s, i), P h (s ′ |s, a) = i∈[d ′ ] G h (a, i)U h (s ′ , s, i), r h (s, a) = i∈[d ′ ] G h (a, i)W h (s, i)where∥ s ′ ∈S g(s ′ )U m,h (s ′ , s, :)∥ 2 ,∥ s ′ ∈S g(s ′ )U h (s ′ , s, :)∥ 2 , ∥W h (s)∥ 2 , ∥W m,h (s)∥ 2 ≤ A/(dµ) for all s ∈ S, a ∈ A, h ∈ [H], and m ∈ [M ] for any function g : S → [0, 1].The latent representations of the reward function and transition kernel are not unique under our assumption. Figure 1 visualizes the low rank structure Assumption 1 imposes on the transition kernel. While Assumption 1 states that the source MDPs and target MDPs have latent low rank structure, the assumption does not guarantee that low rank representations are similar. Additionally, we allow target MDP to be more complex than a single source MDP (at most Tucker rank (S, S, dM ) compared to Tucker rank (S, S, d), respectively). Thus, to allow for transfer learning, we assume that for each step h ∈ [H], the space spanned by the target latent factors is a subset of the space spanned by the latent factors from all the source MDPs. (:, i)} i∈[d ′ ] ) ⊆ Span({G m,h (:, i)} i∈[d],m∈[M ] ).Under Assumption 2, it is possible that no single source MDP captures the target MDP, but the union of all source MDP does. It is also possible that the source MDPs span a strictly larger subspace than the target MDP. Thanks to the above assumptions, by estimating the latent features {G m,h } of the source MDPs, we can construct an approximation of the target features {G h } without interacting with the target MDP, which is essential to transfer learning. Assumption 1 only upper bounds the rank of Q * m,h by d. However, to learn each source latent factor, one needs to obtain a good estimate of a rank d matrix with at least one large entry. Therefore, we assume that the optimal Q-functions in each source MDP are full rank with the largest entry lower bounded by a constant.Assumption 3. For each m ∈ [M ], h ∈ [H], the optimal Q-function of the m-th source MDP at step h satisfies rank(Q * m,h ) = d and ∥Q * m,h ∥ ∞ ≥ C for some C ∈ R + .This assumption allows one to learn the near-optimal Q-functions from noisy samples of the source MDPs. Assumption 3 and its variants are common in the literature of noisy low-rank estimation [2, 9] . Without the above assumption (the rank of Q * is strictly less than d), then one cannot learn every latent factor G m,h (:, i) since it may have a zero singular value, and thus using the approximate feature mapping would result in regret linear in T . Similarly, ∥Q * ∥ ∞ ≥ C ensures that some entries of Q * are sufficiently large and prevents the noise from dominating the low rank signal that one learns in the source phase. 
transfer-ability: 
 Our transfer-ability coefficient is motivated by the following observation. Under Assumption 2, we can construct each target latent factor G h with a linear combination of the source latent factors G m,h . The magnitudes of the coefficients correspond to the difficulty in estimating the target latent factor because the estimation error of G m,h is amplified by its coefficient. Thus, when these coefficients are too large, transfer learning is essentially impossible; one example is when the source latent factors are almost identical or parallel to each other while the target latent factor is orthogonal to the source latent factors (see Figure 2 ).However, these coefficients are not unique and are a function of the source and target latent factors. Furthermore, as the source MDPs latent factors of Q * m,h and target latent factors {G h } are not unique, each choice of latent factor results in a different set of coefficients. Thus, we introduce B h as the set containing all such coefficients given the subspaces from the target and source MDPs. Let G S,h be the set of all R S×d orthonormal latent factor matrices with columns that span the column space of Q * m,h for all m ∈ [M ], and let G T,h be the set of all R S×d ′ orthonormal latent factor matrices with columns that span the column space of P h (s ′ ) for all s ′ ∈ S. Then, we define the setB h (G T,h , G S,h ) to contain all such coefficients, i.e., B h ∈ R d ′ ,d,M and B h ∈ B h (G T,h , G S,h ) if there exists G h ∈ G T,h , G m,h ∈ G S,h such that for all i ∈ [d ′ ], h ∈ [H], G h (•, i) = j∈[d],m∈[M ] B h (i, j, m)G m,h (•, j). Now, we define α, which precisely measures the challenge involved in transferring the latent representation.Definition 3 (Transfer-ability Coefficient). Given a transfer RL problem that satisfies Assumptions 1, 2, and 3, with the definition of B h above, we define α asα := max h∈[H] min B∈B h (G T ,h ,G S,h ) max i∈[d ′ ],j∈[d],m∈[M ] |B(i, j, m)|.Note that the minimum is taken over all latent factor matrices. When there is only one source MDP, α is small, i.e., less than or equal to one, because the columns of G form an orthonormal basis of the space containing the target latent factor. In the best case, α is 1/(dM ) (see Appendix D). On the other hand, when there are multiple source MDPs, α can be arbitrarily large as in Figure 2 ; in this case, the estimation error of G 1 and G 2 are amplified by α when estimating G T using G 1 and G 2 . We remark that adding more source MDPs or increasing the rank of Q * m,h will not increase α as one can use the same set of coefficients without the additional source MDP or larger subspace of Q * m,h . See Appendix D for more discussion on α.Our transfer-ability coefficient is similar to the quantity α max defined in [4] . While these terms both quantify the similarity between the source and target MDPs, in our setting, we allow for the source MDPs' state latent factors, {G m,h }, to differ from target MDP's state latent factors while [4] assumes that all MDPs share the same latent representation ϕ. Our setting is more general than the one in [4] even when assuming the same Tucker rank assumption.To formalize the importance of α, we prove a lower bound that shows that a dependence on α in the sample complexity of the source phase is necessary to benefit from transfer learning. Before proving our main result, we first present an intermediate lower bound to provide intuition on how α measures the difficulty in transferring a learned representation. Theorem 1. There exist two transfer RL instances such that (i) they satisfy Assumptions 1 and 2, (ii) they cannot be distinguished without observing Ω(α 2 ) samples in the source phase, and (3) they have target action latent features that are orthogonal to each other.Learning a latent representation G that is orthogonal to the true representation is no better than randomly guessing a representation G ′ in the source phase; using either G or G ′ in the target phase incurs regret linear in T . Thus, Theorem 1 states that without observing Ω(α 2 ) samples in the source MDPs, one cannot learn a good policy in the target phase with G or G ′ , and one should disregard the information from the source MDPs and use a non-transfer learning RL algorithm to achieve regret bound that scales withT . Therefore, Ω(α 2 ) samples are required to benefit from transfer learning.To prove Theorem 1, we construct two (S, S, 1) transfer RL problems that satisfies Assumption 2 with similar source action latent representations G i m,h ∈ G but orthogonal target action latent representations G i T for i ∈ {1, 2}. To avoid learning the incorrect representation, one must identify the transfer RL problem by differentiating the Q * s. By construction, the Q * s for the two transfer RL problems differ by at most 1/α entrywise, so one must observe Ω(α 2 ) samples in the source problem from standard hypothesis testing lower bounds [5] . Observing less samples in the source problem results in an estimate orthogonal to the true target representation with constant probability. See Appendix E for the formal proof. One can easily prove a similar result in the (S, d, A) and (d, S, A) Tucker rank setting with similar constructions by switching the states and actions (see Appendices F and G). 
algorithm: 
 We now present our algorithm that achieves the optimal dependence on α. In the source phase, our algorithm can use any algorithm that learns ϵ-optimal Q functions on each source MDP. As the error bound on the estimated feature representation depends on the incoherence of Q * m,h , we use LR-EVI, which combines empirical value iteration with low rank matrix estimation [30] . After obtaining estimates Qm,h of Q * m,h , our algorithm computes the singular value decompositions (SVDs) of each Qm,h to construct the latent feature representation G by scaling and concatenating the singular vectors. Then, in the target phase, our algorithm deploys a modification of LSVI-UCB [17] adapted to our Tucker rank setting called LSVI-UCB-(S, S, d) using the G. For ease of notation, we defineT s k,h = {k ′ ∈ [k]|s k h = s},which is the set of episodes before k, in which one was at s at time step h.Input: {N h } h∈[H] 1: for m ∈ [M ] do 2: Run LR-EVI({N h } h∈[H]) on source MDP m to obtain Qm,h . Input: λ, β s k,h , Ĝ 1: for k ∈ [K] do 2:Receive initial state s k 1 .for h = H, . . . , 1 dofor s ∈ S do Setw s h ← -(Λ s h ) -1 t∈T s k-1,h Ĝh (a t h ) r h (s, a t h ) + max a ′ ∈A Q h+1 (s t h+1 , a ′ ) . 9:/* Estimate Q * via the low rank structure with optimism */ 10:Set Q h (•, •) ← -min H, ⟨w • h , Ĝh (•)⟩ + β • k,h Ĝh (•) ⊤ (Λ • h ) -1 Ĝh (•) .11:for h ∈ [H] do 12:Take action a k h ← -max a∈A Q h (s k h , a), and observe s k h+1 .regularized least squares problem,w s h ← -arg min w∈R d t∈T s k,h (r h (s, a t h ) + max a ′ ∈A Q h+1 (s t h+1 , a ′ ) -w ⊤ Gh (a t h )) 2 + λ∥w∥ 2 2 ,using the reward when s was observed and add an exploration bonus β s k,hĜh (a) ⊤ (Λ s h ) -1 Ĝh (a) to our estimate of Q * , which is common in linear MDP/bandits algorithms [17, 1] . Multiplying the latent factors by A/(dµ) to construct Ĝ ensures that the feature mapping and coefficients are of similar magnitude, which is crucial in adapting the mechanisms of LSVI-UCB to our setting.While one may wonder why our modification of LSVI-UCB is necessary, Algorithm 2 improves the regret bound by a factor √ S compared to using any linear MDP algorithm off the shelf; reducing our setting to a linear MDP results in using a feature mapping with dimension dS. Thus, using any linear MDP algorithm results in a target regret bound of Õ( [41] . However, our algorithm shaves off a factor of √ S as our algorithm computes S copies of d × d dimensional gram matrices in contrast to the d 2 S 2 dimensional gram matrices used in linear MDP algorithms.√ d 2 S 2 H 2 T ) 
theoretical results: 
 In this section, we prove our main theoretical results that show with enough samples in the source problem, our algorithms admit regret bounds that are independent of S, A, or both S and A in the target problem. We first state our main result in the (S, S, d) Tucker rank setting. Theorem 2. Suppose Assumptions 1, 2, and 3 hold, and set δ ∈ (0, 1). Furthermore, assume that, for any ϵ ∈ (0, SH/T ), Q m,h = r m,h + P m,h V m,h+1 has rank d and is µ-incoherent with condition number κ for all ϵ-optimal value functions V h+1 . Let λ = 1 and β s k,h be a function of d, H, |T s k,h |, |S|, M, T . Then, for T ≥ S α 2 , using at most Õ(d 4 µ 5 κ 4 (1 + A/S)M 2 H 4 α 2 T ) samples in the source problems, our algorithm has regret Õ( (dM H) 3 ST ) with probability at least 1 -δ.Theorem 2 states that using transfer learning improves the performance on the target problem by removing the regret bound's dependence on the action space. Thus, with enough samples from the source MDPs one can recover a regret bound in the target problem that matches the best regret bound for any algorithm in the (S, S, d) Tucker rank setting with known latent feature representation G concerning S and T . See Appendix E for the proof of Theorem 2.For sake of brevity, we present our results in our other Tucker rank settings in Table 1 (see Appendices F, G, and H for the formal statements and proofs). In each of our Tucker rank settings, our algorithms use transfer learning to remove the dependence on S, A, or SA in the target regret bound, which matches the dependence on S and A of the best regret bounds of algorithms with known latent representation. While the source sample complexities of Theorems 2 and 10 may seem to not scale linearly in A and S, respectively, we require the horizon in the target phase to be large enough, i.e., T α 2 (S/A + 1) ≥ S + A and T α 2 (1 + A/S) ≥ S + A, respectively, so that one observes at least Ω(S + A) samples in the source phase.While our dependence on M in the target regret bound may seem sub optimal, our algorithm cannot distinguish which of the d dimensions (out of dM possible dimensions) match the ones in the target MDP without interacting with it. Thus, our algorithm must include all of them, which results in using at worst a dM -dimensional feature representation. However, in the case when the feature representations from source MDPs lie in subspaces that intersect, we can apply a singular value thresholding procedure to remove the unneeded dimensions used in the feature representation at the cost of an increased sample complexity (by a factor of A) in the source phase (see Appendix C).Comparison with [4] : In comparison to Theorem 3.1 from [4] , our result, Theorem 14, has similar dependence on A, d, H, and T while our dependence on α is optimal compared to their α5 dependence4 . While our dependence on M in the regret bound is worse, this is due to our transfer learning setting being more general; we only require that the space spanned by the target features be a subset of the space spanned by the source features instead of having the target features being a linear combination of the source features. Furthermore, our source sample complexity scales with the size of the state space instead of scaling logarithmically in the size of the given function class.The proofs of 2, Theorem 10, 15, and 14 synthesize the theoretical guarantees of LR-EVI, singular vector perturbation bounds, and LSVI-UCB or our modification of LSVI-UCB. Given N samples from the source MDPs, we first bound the error between the singular subspaces up to a rotation by d 3 M (S + A)/N (suppressing the dependence on common matrix estimation terms) to construct our feature mapping. Thus, with enough samples in the source MDPs, LR-EVI returns Q functions with singular vectors that can be used to construct a sufficient feature representation; the additional regret incurred from using the approximate feature representation in LSVI-UCB or Algorithm 2 is dominated by the original regret of using the true representation.In the (S, d, A), (S, S, d), (d, S, A), and (d, d, d) Tucker rank settings, the source sample complexity's scalings concerning S, A, H, and T are reasonable when learning A/T , S/T , 1/T , and 1/T -optimal Q functions, respectively, given the Q learning lower bounds in [30] . Similarly, the dependence on µ and κ are standard for RL algorithms incorporating matrix estimation.In the (S, d, A), (S, S, d), and (d, S, A) Tucker rank settings, our α 2 dependence in the source sample complexity is optimal due to our lower bounds. In the (d, d, d) Tucker rank setting, our α 4 dependence is likely optimal when eliminating the dependence on S and A in the target problem; one must combine both sets of singular vectors together, F : S → R dM and G : A → R dM , to create a feature mapping ϕ :S × A → R d 2 M 2, which causes the α 4 dependence in our upper bound. However, if α 4 is too large, one can use the algorithms from the (S, d, A) or (S, S, d) Tucker rank settings to benefit from transfer learning. Proving an α 4 lower bound is an interesting open question. Additionally, the dependence on d and M in this setting is worse as our low rank latent representation of each state-action pair lies in a d 2 M 2 dimensional space in contrast to a space with dimension dM .The regret bounds of our algorithms used in the target phase, i.e., Algorithm 2, Algorithm 4, and LSVI-UCB [17] , in each Tucker rank setting are optimal with respect to S, A, and T . Since each Tucker rank setting captures tabular MDPs, we can construct lower bounds with a reduction from the bound in [18] , e.g., in the (S, S, d) setting, the regret is at least Ω( √ dSH 2 T ). However, our dependence on d and H are sub-optimal. The extra factor of √ H is likely due to our use of Hoeffding's inequality instead of tracking the variance of the estimates to use Bernstein's inequality. Our dependence on d is sub-optimal as LSVI-UCB is sub-optimal with respect to d; for linear MDPs, LSVI-UCB++ [13] admits a regret bound of Õ( √ d 2 H 2 T ), which matches the lower bound from [41] . Thus, to obtain the optimal dependence on d and H, we would need to adapt LSVI-UCB++ to our Tucker rank setting. 
conclusion: 
 We study transfer RL, in which one transfers a latent representation between source MDPs and target MDP with Tucker rank (S, S, d), (S, d, A), (d, S, A) or (d, d, d) transition kernels. As [4] studied transfer RL in the (d, S, A) Tucker rank setting, our study completes the analysis of representational transfer in RL assuming that one or more modes of the transition kernel is low rank. Furthermore, we propose the transfer-ability coefficient that quantifies the difficulty of transferring latent representations between the source and target problems with information theoretic lower bounds. We propose computationally simple algorithms that admit regret bounds that are independent of S, A, or SA depending on the Tucker rank setting given enough samples from the source MDPs. Furthermore, these regret bounds match the bounds of algorithms that are given the true latent representation. Our dependence on d and H is not optimal and can be improved by adapting the methods in [13] Since each Tucker rank setting captures tabular MDPs, we can construct lower bounds with a reduction from the bound in [18] ; in the (S, d, A) Tucker rank setting, the regret is at least Ω( √ dAH 2 T ), and in the (S, S, d) setting, the regret is at least Ω(√ dAH 2 T ).As mentioned, our dependence on d and H are sub optimal because we modify LSVI-UCB [17] , which has a sub-optimal dependence on d and H. Modifying the algorithm from [13] to achieve the optimal dependence on d and H in the (S, S, d) and (S, d, A) Tucker rank settings is an interesting problem for future research. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] .Justification: There are no experiments, so there were no computational resources needed.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] .Justification: The contributions of this paper are theoretical results, and we believe that they will not lead to societal harm.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] .Justification: We mention potential scenarios in which one benefits from our methodology. As this paper focuses on foundational research by proving theoretical bounds on transfer reinforcement learning, we do not believe that there are any direct paths to negative applications.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] . Justification: Our paper poses no such risks as are contributions are strictly theoretical. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] . Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: When the feature representations of each source MDP lies in orthogonal d-dimensional subspaces, we cannot discard any unique dimension of the M subspaces as we cannot tell which of the d-dimensions match the ones in the target MDP without interacting with it. However, when the feature mappings from the source MDPs lie in intersecting subspaces, i.e., The proof of Theorem 3 follows the proof of Theorem 2, except we require a larger source sample complexity to guarantee with high probability that the d ′′ +1-th singular value of the concatenated feature representation is sufficiently small. With this procedure, we ensure that our feature representation removes the unneeded dimensions. See Appendix E for proof of the above theorem.rank Gh = rank A dµ [G 1,h . . . G M,h ] = d ′′ for d ′ ≤ d ′′ ≤While the above procedure requires knowledge of the dimension of the subspace spanned by the latent features of the source MDPs, one can also threshold small singular values of the concatenated feature mapping as the misspecification error will still be small. The specific procedure is as follows: after performing the singular value decomposition on the concatenation of Ĝm,h , we first find the smallest value of t ∈ [dM ] that satisfiesσ t+1 ≤ tHSdµ α 2 T (dM -t)M 2 A ,and threshold σ t+1 , . . . , σ dM . LetT = t ∈ [dM ]|σ t+1 ≤ tHSdµ α 2 T (dM -t)M 2 Abe the set of t that satisfies the inequality on the singular values. Then, with the specified procedure, our algorithm admits a target regret bound that depends on t instead of dM . Note that t is minimally 1 and at most dM . Theorem 4. Suppose Assumptions 1, 2, and 3 hold. Let δ ∈ (0, 1) and t = min t ′ ∈T t ′ . Furthermore, assume that, for any ϵ ∈ (0, SH/T ), Q m,h = r m,h + P m,h V m,h+1 has rank d and is µ-incoherent with condition number κ for all ϵ-optimal value functions V h+1 . Let λ = 1 andβ s k,h be a function of d, H, |T s k,h |, |S|, M, T . Then, for T ≥ S α 2 , using at most Õ(d 5 µ 5 κ 4 (1 + A/S)M 3 H 4 α 2 T) samples in the source problems, our algorithm has regret Õ( (tH) 3 ST ) with probability at least 1 -δ.With an increase in a factor of dM to the source sample complexity, we can potentially improve the regret bound of the target by decreasing the dimension of the feature representation from dM to t. See Appendix E for the proof of the above theorem.In this section, we prove properties of α and provide easy and hard instances. We first bound the values of α. Lemma 1. Let α be defined according to Definition 4. Then, we have that 1 dM ≤ α < ∞.Proof. Since Assumption 6 holds and that the latent factors are normalized, it follows that for all i ∈ [d ′ ] and any latent factor matrix,∥F h (:, i)∥ 2 = ∥ j∈[d],m∈[M ] B h (i, j, m)F m,h (:, j)∥ 2 1 ≤ j∈[d],m∈[M ] ∥B h (i, j, m)F m,h (:, j)∥ 2 ≤ j∈[d],m∈[M ] |B h (i, j, m)|∥F m,h (:, j)∥ 2 = j∈[d],m∈[M ] |B h (i, j, m)|. Given that 1 ≤ j∈[d],m∈[M ] |B h (i, j, m)|, it follows that the minimum of max j∈[d],m∈[M ] |B h (i, j, m)| is attained when |B h (i, j, m)| = 1 dM . Thus, α ≥ 1 dMLet γ ∈ (0, 1). Consider the construction where the target latent factor is F T = [1, 0] and the source latent factors from source MDPs one and two areF 1 = [1 -γ, γ 2/γ -1], F 2 = [1 -γ, -γ 2/γ -1].Clearly, the latent factors are orthonormal. Then, it follows that the only linear combination of F 1 and F 2 that results in F isF T = cF 1 + cF 2 ,which implies that c = 1 2-2γ . Thus, α = 1 2-2γ , and it follows that we can make α arbitrarily large because for any positive constant C, we can choose γ so that α > C.As the proof of Lemma 1 uses a construction in which α can be arbitrarily large, we next provide simple constructions where α is small. In the rank one case where all source latent factors equal the target latent factor, α attains its minimum of α = 1 M . Next, we consider the construction whereF T = 1 √ d , . . . , 1 √ d ,and there are M source MDPs with the standard basis vectors in R d as the latent factors equally distributed among the M rank one source MDPs. Thus,F T = m∈M √ d M F m , and α = √ d/M .We next present a transfer RL instance with large α. Consider the following construction with the goal of trying to transfer the state latent factors. Without loss of generality, let the size of the state space and action space be 4n for some n ∈ N + . Furthermore, we refer to the i-th quarter of the states as s i for i ∈ [4] and the i-th half of the actions as a i for i ∈ [2] because our construction is a block MDP with four latent states and two latent actions. Let H = 2. In each MDP, the transition kernel does not vary with h while the reward function is time dependent. Assume that the transition kernels have Tucker rank (S, d, A) (Assumption 5). For ease of notation, we refer to the i-th row as any state in s i and the i-th column as any state in a i . The target MDP's latent factors areF h =     1/(2n) 0 1/(2n) 0 0 1/(2n) 0 1/(2n)     , W 1 = 1/(2n) 1/(8n) 1/(2n) 1/(8n) , W 2 = 1/(8n) 1/(2n) 1/(8n) 1/(2n) for all h ∈ [H],andU h (s 1 |a 1 ) = U h (s 2 |a 1 ) = [3 √ 2/(8 √ n), √ 2/(8 √ n)] U h (s 1 |a 2 ) = U h (s 2 |a 2 ) = [ √ 2/(8 √ n), 3 √ 2/(8 √ n)] U h (s 3 |a 1 ) = U h (s 4 |a 1 ) = [3 √ 2/(8 √ n), √ 2/(8 √ n)] U h (s 3 |a 2 ) = U h (s 4 |a 2 ) = [ √ 2/(8 √ n), 3 √ 2/(8 √ n)].Thus, the reward functions and transition kernels for the target MDP arer 1 =     1 2n 1 2n 1 2n 1 2n 1 4n 1 4n 1 4n 1 4n     r 2 =     1 4n 1 4n 1 4n 1 4n 1 2n 1 2n 1 2n 1 2n    and the transition kernels areP h (s 1 |•, •) = P h (s 2 |•, •) =     3 8n 1 8n 3 8n 1 8n 1 8n 3 8n 1 8n 3 8n     P h (s 3 |•, •) = P h (s 4 |•, •) =     1 8n 3 8n 1 8n 3 8n 3 8n 1 8n 3 8n 1 8n     for all h ∈ [H].Using the Bellman equations, it follows that the optimal Q function for the above MDP is EQUATION    , Q * 2 =     1 4n 1 4n 1 4n 1 4n 1 2n 1 2n 1 2n 1 2n     .and both Q * s have F h as orthonormal latent factors. Next, we present the orthonormal latent factors for the first source MDPF 1,h =     1/ √ 2n 1/ √ 4n -1/ √ 2n 1/ √ 4n 0 1/ √ 4n 0 1/ √ 4n     , W 1,1 = 3/ √ 4n 3/ √ 4n 1/ √ 4n 1/ √ 4n , W 1,2 = 1/ √ 4n 1/ √ 4n 2/ √ 4n 2/ √ 4n .It follows that the reward functions arer 1,1 =    (3 + 3 √ 2)/(4n) (1 + √ 2)/(4n) (3 -3 √ 2)/(4n) (1 - √ 2)/(4n) 3/(4n) 1/(4n) 3/(4n) 1/(4n)    , r 1,2 =    (1 + √ 2)/(4n) (1 + √ 2)/(2n) (1 - √ 2)/(4n) (1 - √ 2)/(2n) 1/(4n) 1/(2n) 1/(4n) 1/(2n)    . with P 1,h (•|•, •) = 1/(4n). Since P 1,his the uniform transition kernel (which has the second column of F 1,h as its latent factor), it follows that P V * 1,2 (•, •) is a rank one matrix with every entry being the same positive constant. Thus,Q * 1,1 = r 1,1 + P 1,1 V * 1,2 and Q * 1,2 = r 1,2are rank two matrices with F 1,h as latent factors.The second source MDP has the following latent factorsEQUATIONwhere c = 1 + 1/β 2 for all h ∈ [H] with P 2,h (•|•, •) = 1/(4n). Since P 2,his the uniform transition kernel (which has the second column of F 2,h as its latent factor), it follows that P V * 2,2 (•, •) is a rank one matrix with every entry being the same positive constant. Thus,Q * 2,1 = r 2,1 + P 2,1 V * 2,2and Q * 2,2 = r 2,2 are rank two matrices with F 2,h as latent factors. Now, we prove that α ∈ Ω(β). Corollary 1. Consider the above construction that satisfies Assumptions 5 and 6. Then, α defined in Definition 4 satisfies α ∈ Ω(β).Proof. Consider the above construction with β > 0. First, we show that when expressing the first column of F h as a linear combination of the columns of F 1,h and F 2,h , one coefficient is Ω(β).We first note that one must use the first column in F 2,h or else the system of linear equations is inconsistent. Thus, we solvea    1/ √ 2n -1 √ 2n 0 0    + b     1/ √ 4n 1/ √ 4n 1/ √ 4n 1/ √ 4n     + d      1 c √ 2n + 1 cβ √ 4n -1 c √ 2n + 1 cβ √ 4n -1/(cβ √ 4n) -1/(cβ √ 4n)      =    1/ √ 22n 1/ √ n 0 0    It follows that d = bcβ. Thus, b = 1/ √ 2, and d ∈ Ω(β) because c ≥ 1.To show that α ∈ Ω(β), we assume for sake of contradiction that there exists some set of basis vectors F ′ 1,h and F 2,h ′ that span the subspace defined by F 1,h and F 2,h , respectively, such that we can express the any rotation of the first column of F h as a linear combination of the columns ofF ′ 1,h and F 2,h ′ using coefficients a, b, c, d such that |a|, |b|, |c|, |d| ∈ o(β). Since F h , F 1,h , and F 2,h are orthonormal latent factors, it follows that there exist rotation matrices R, R 1 , R 2 with ∥R∥ ∞ , ∥R 1 ∥ ∞ , ∥R 2 ∥ ∞ ∈ O(1) such that F ′ 1,h = R 1 F 1,h and F ′ 2,h = R 2 F 2,h. It follows that R -1 exists and has entries with constant magnitude. By construction we haveF h (:, 0) = aR -1 R 1 F 1,h (:, 0) + bR -1 R 1 F 1,h (:, 1) + cR -1 R 2 F 2,h (:, 0) + dR -1 R 2 F 2,h (:, 1).Since the entries of the rotation matrices and their inverse are bounded by a constant, the above equation states that we can represent the first column of F h as a linear combination of the columns of F 1,h and F 2,h using only constant coefficients. Thus, we reach a contradiction because we've shown that one entry of dR -1 R 2 ∈ Ω(β). Therefore, α ∈ Ω(β).We first prove our lower bound.Proof. Suppose all source and target MDPs (S, A, P, H, r) share the same state space, action space, and horizon H = 1 and assume that S = A = [2n] for some n ∈ N + . For ease of notation, we let s 1 and a 1 refer to any state and action in [n], respectively, and s 2 and a 2 refer to any state and action in {n + 1, . . . 2n}, respectively. We will present the latent factors and optimal Q functions as block vectors and matrices with s 1 , s 2 , a 1 , a 2 as the blocks containing n entries. The initial state distribution in the target MDP is uniform over S. We now present two transfer RL problems with similar Q functions (with rows s 1 , s 2 and columns a 1 , a 2 ) that satisfy Assumptions 1 and 2 but have orthogonal target state latent factors. For ease of notation, the superscript i of Q * ,i m,h , Q * ,i h denotes transfer RL problem for i ∈ {1, 2}. Then, the optimal Q functions for transfer RL problem one areQ * ,1 1,1 = n 1/n 0 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2 0 0 , Q * ,1 2,1 = n 0 1/n 1/(2n) 1/(2n) = 0 0 1/ √ 2 1/ √ 2 , Q * ,1 1 = n 1/(2n) -1/(2n) 1/(2n) 1/(2n) = 1/2 1/2 -1/2 -1/2 ,and the optimal Q functions for transfer RL problem two areQ * ,2 1,1 = n 1/n 0 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2 0 0 , Q * ,2 2,1 = n 0 1/n G ′ = 0 0 (1 + 1/α)/(c √ 2) (1 -1/α)/(c √ 2) , Q * ,2 1 = n 1/(2n) -1/(2n) 1 (2n) - 1 (2n) = 1/2 -1/2 -1/2 1/2 ,whereG ′ = ( 1/(2n) + 1/(2nα 2 ))/ 1 + 1/α 2 ( 1/(2n) -1/(2nα 2 )/ 1 + 1/α 2 ,and c = 1 + 1/α 2 . Note that c ∈ (1, 2dM ) because α ≥ 1/(dM ) from Lemma 1 for α > 0. The incoherence µ, rank d, and condition number κ of the above Q functions are O(1). Furthermore, the above construction satisfies Assumption 5 with Tucker rank (S, S, 1) and Assumption 6 because the source and target MDPs share the same action latent factor 1/(2n) 1/(2n) in the first transfer RL problem while in the second transfer RL problem,1/(2n) -1/(2n) = -α 1/(2n) 1/(2n) + αcG ′ . Note that G 1 = 1/(2n) 1/(2n) and G 2 = 1/(2n) -1/(2n), so the target latent factors of the different transfer RL problems are orthogonal to each other.The learner is given either transfer RL problem one or two with equal probability with a generative model in the source problem. When interacting with the source MDPs, the learner specifies a stateaction pair (s, a) and source MDP m and observes a realization of a shifted and scaled Bernoulli random variable X. The distribution of X is that X = 1 with probability(Q * ,i m,1 (s, a) + 1)/2 and X = -1 with probability (1 -Q * ,i m,1 (s, a))/2).Furthermore, the learner is given the knowledge that the state latent features lie in the function class G = {G 1 , G 2 } and must use the knowledge obtained from interacting with the source MDP to choose one to use in the target MDP, which is no harder than receiving no information about the function class.To distinguish between the two transfer RL problems, one needs to differentiate between Q * ,1 2,1 and Q * ,2 2,1 . By construction, the magnitude of the largest entrywise difference between Q * ,1 2,1 and Q * ,2 2,1 is lower bounded by Ω(1/α).If the learner observes Z samples in the source MDPs, where Z ≤ O(α 2 ) for some constant C > 0, then the probability of correctly identifying G is upper bounded by 0.76 (Lemma 5.1 with δ = 0.24 [5] ). Thus, if the learner does not observe Ω(α 2 ) samples in the source phase, then the learner returns the incorrect feature mapping that is orthogonal to the true feature mapping with probability at least 0.24.We first present the theoretical guarantees of LSVI-UCB-(S, S, d) and defer their proofs to Appendix J. Theorem 5. Assume that Assumption 1 holds and the learner is given the true latent action representation G = {G h } h∈ [H] . Then, there exists a constant c > 0 such that for any δ ∈ (0, 1), if we set λ = 1, β s k,h = cdH √ ι, ι = log(2dT S/δ), then with probability at least 1 -δ, the total regret of Algorithm 2 is Õ( √ d 3 SH 3 T ).= {U h } h∈[H] such that |r h (s, a) -W h (s) ⊤ G h (a)| ≤ ξ, s ′ ∈S (P h (s ′ |s, a) -U h (s ′ , s)G h (a) ⊤ ) ≤ ξ for all h ∈ [H] where ∥W h ∥ 2 , ∥ s ′ ∈S g(s ′ )U h (s ′ , a)∥ 2 ≤ A/(dµ) for any function g : S → [0, 1].Theorem 6. Under the Assumption 4, for any δ ∈ (0, 1),for λ = 1, β s k,h = O(Hd √ ι + ξ √ kdH) for ι = log(2dT S/δ), the regret of Algorithm 2 is Õ( √ d 3 H 3 ST + ξdHT ) with probability at least 1 -δ.We now prove Theorem 2.Proof. Suppose the assumption stated in Theorem 2 hold. Then, from [30] , running LR-EVI with a sample complexity of C ′ d 4 µ 5 κ 4 (S + A)M H 4 α 2 T log(2SAdM H/δ)/S on each source MDP results in Qm,h functions with singular value decomposition Qm,h = Fm,h Σm,h Ĝm,h that are √ HS/(16αµκ √ dM T )-optimal with probability at least 1 -δ/2.Since our estimates are √ HS/(16ακ √ dM T )-optimal, it follows that γ < 1/2 in the singular vector perturbation bound, Corollary 3. Since ∥Q * m,h ∥ ∞ ≥ C, from Corollary 3, it follows that there exists rotation matrices R m,h such that∥( Ĝm,h R m,h -G m,h )(a)∥ 2 ≤ d √ HµS α √ AM T for all a ∈ A where the optimal Q function have singular value decomposition Q * m,h = F m,h Σ m,h G ⊤ m,h .Let G be the A × dM matrix from joining all the source action latent factor matrices, and Ĝh be the A × dM matrix from joining all Ḡm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ]. Then, from Assumption 2 and Definition 3, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] W h (s, i)G h (a, i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)G h,m (a, j)   W h (s, i) = i,j∈[d],m∈[M ] B(i, j, m)G m,h (a, j)W h (s, i) = W ′ h (s)G h (a) ⊤ and P (s ′ |•, •) = Gh U ′ h (s ′ ) ⊤ (with the same argument) for some S × dM matrices W ′ h , U ′ h (s ′ ) with entries bounded by α. Note that W ′ h and U ′ h (s ′ ) are matrices that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry. Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H],|r h (s, a) -Ĝh (a)R h W ′ h (s) ⊤ | = | Gh (a)W ′ h (s) ⊤ -Ĝh (a)R h W ′ h (s) ⊤ | = |( Gh (a) -Ĝh (a)R h )W ′ h (s)| ≤ α| m∈M (G m,h (a) -Ĝm,h (a)R m,h )W m,h (s)| ≤ α m∈M ∥G m,h (a) -Ĝm,h (a)R m,h ∥ 2 ∥W m,h (s)∥ 2 ≤ α A dµ m∈M ∥G m,h (a) -Ĝm,h (a)R m,h ∥ 2 ≤ dHM S Tfrom the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,s ′ ∈S (P h (s ′ |s, a) -U h (s ′ , s)G h (a) ⊤ ) = | s ′ ∈S Gh (a)U ′ h (s ′ , s) -Ĝh (a)R h U ′ h (s ′ , s) ⊤ | = |( Gh (a) -Ĝh (a)R h ) s ′ ∈S U ′ h (s ′ , s) ⊤ | ≤ α| m∈M (G m,h (a) -Ĝm,h (a)R m,h ) s ′ ∈S U m,h (s ′ , s)| ≤ α m∈M ∥(G m,h (a) -Ĝm,h (a)R m,h )∥ 2 ∥ s ′ ∈S U m,h (s ′ , s) ⊤ ∥ 2 ≤ dHM S T .Therefore, Ĝh (a) satisfies Assumption 4 with ξ = dM HS T . Then it follows that running LSVI-UCB-TR using Ĝh (a) with δ ′ = δ/2 during the target phase of the algorithm admits a regret bound ofRegret(T ) ≤ C"( √ d 3 M 3 H 3 ST + dM HT dM HS T ) ∈ Õ( √ d 3 M 3 H 3 ST )with probability at least 1 -δ from a final union bound. Furthermore, the sample complexity in the source phase isÕ d 4 µ 5 κ 4 (S + A)M 2 H 4 α 2 T S ,which proves our result.Proof. Let the assumptions of Theorem 3 hold. Then, from [30] , running LR-EVI with a sample complexity of C ′ d 7 µ 5 κ 4 A(S + A)M 2 H 4 α 2 T log(2SAdM H/δ)/(∥( Ĝm,h R m,h -G m,h )(a)∥ 2 ≤ √ Hd ′′ µS αAM √ dTfor all a ∈ A where the optimal Q function have singular value decompositionQ * m,h = F m,h Σ m,h G ⊤ m,h .Let G be the A × dM matrix from joining all the source action latent factor matrices, and Ĝh be the A × dM matrix from joining all Ḡm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ]. Then, from Assumption 2 and Definition 3, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] W h (s, i)G h (a, i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)G h,m (a, j)   W h (s, i) = i,j∈[d],m∈[M ] B(i, j, m)G m,h (a, j)W h (s, i) = W ′ h (s)G h (a) ⊤ and P (s ′ |•, •) = Gh U ′ h (s ′ ) ⊤ (with the same argument) for some S × dM matrices W ′ h , U ′ h (s ′) with entries bounded by α. Note that W ′ h and U ′ h (s ′ ) are matrices that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry.Let E = Ĝh -Gh , where E = [E 1 . . . E M ] .We next bound the d ′′ + 1 smallest singular value of Ĝh with our singular vector perturbation bound ( ∥E∥ ∞ ≤ ∥E∥ 2,∞ ).σ d ′′ +1 ( Ĝh ) = σ d ′′ +1 ( Gh ) + ∥E∥ op ≤ √ AdM ∥E∥ ∞ ≤ √ Hd ′′ µS α √ AM TWith singular value decomposition Ĝh = XΣY ⊤ , let G d ′′ h be the thresholded feature representation estimate, i.e., G d ′′ h = X(:, : d ′′ )Σ(:d ′′ , : d ′′ )Y (:, d ′′ ) ⊤ . Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H], |r h (s, a) -G d ′′ h (a)R h W ′ h (s, : d ′′ ) ⊤ | = | Gh (a)W ′ h (s) ⊤ -G d ′′ h (a)R h W ′ h (s, : d ′′ ) ⊤ | ≤ | Gh (a)W ′ h (s) ⊤ -Ĝh (a)R h W ′ h (s) ⊤ + | Ĝh (a)R h W ′ h (s) ⊤ -G d ′′ h (a)R h W ′ h (s, : d ′′ ) ⊤ | ≤ α| m∈M (G m,h (a) -Ĝm,h (a)R m,h )W m,h (s)| + | Ĝh (a, d ′′ + 1 :)W ′ h (s, d ′′ + 1 :) ⊤ | ≤ α m∈M ∥G m,h (a) -Ĝm,h (a)R m,h ∥ 2 ∥W m,h (s)∥ 2 + ασ d ′′ +1 ( Ĝh ) √ dM m∈[M ] ∥W m,h ∥ 2 ≤ α A dµ m∈M ∥G m,h (a) -Ĝm,h (a)R m,h ∥ 2 + σ d ′′ +1 ( Ĝh )√ dM ≤ d ′′ HS T from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,s ′ ∈S (P h (s ′ |s, a) -U h (s ′ , s)G d ′′ h (a) ⊤ ) ≤ d ′′ HS T .Therefore, G d ′′ h (a) satisfies Assumption 4 with ξ = d ′′ HS T . Then it follows that running LSVI-UCB-TR using G d ′′ h (a) with δ ′ = δ/2 during the target phase of the algorithm admits a regret bound ofRegret(T ) ≤ C"( (d ′′ ) 3 H 3 ST + d ′′ HT d ′′ HS T ) ∈ Õ( (d ′′ ) 3 H 3 ST )with probability at least 1 -δ from a final union bound. Furthermore, the sample complexity in the source phase isÕ d 7 µ 5 κ 4 (A + A 2 )M 3 H 4 α 2 T Sd ′′ ,which proves our result.We now prove Theorem 4.Proof. Suppose the assumption stated in Theorem 4 hold. Then, from [30] , running LR-EVI with a sample complexity of C ′ d 5 µ 5 κ 4 (S + A)M 2 H 4 α 2 T log(2SAdM H/δ)/∥( Ĝm,h R m,h -G m,h )(a)∥ 2 ≤ √ HdµS α √ AM 2 Tfor all a ∈ A where the optimal Q function have singular value decompositionQ * m,h = F m,h Σ m,h G ⊤ m,h .Let G be the A × dM matrix from joining all the source action latent factor matrices, and Ĝh be the A × dM matrix from joining all Ḡm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ]. Then, from Assumption 2 and Definition 3, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] W h (s, i)G h (a, i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)G h,m (a, j)   W h (s, i) = i,j∈[d],m∈[M ] B(i, j, m)G m,h (a, j)W h (s, i) = W ′ h (s)G h (a) ⊤ and P (s ′ |•, •) = Gh U ′ h (s ′ ) ⊤ (with the same argument) for some S × dM matrices W ′ h , U ′ h (s ′) with entries bounded by α. Note that W ′ h and U ′ h (s ′ ) are matrices that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry. Let Ĝt be the thresholded feature mapping, where t is defined as t = min t ′ ∈T t ′ forT = t ∈ [dM ]|σ t+1 ≤ tHSdµ α 2 T (dM -t)M 2 A .Therefore, with the same logic as the previous proof, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H],|r h (s, a) -Ĝt (a)R h W ′ h (s) ⊤ | = | Gh (a)W ′ h (s) ⊤ -Ĝt R h W ′ h (s) ⊤ | ≤ |( Gh (a) -Ĝh (a)R h )W ′ h (s)| + | Ĝh (a)R h W ′ h (s) ⊤ -Ĝt h (a)(R h W ′ h (s)) t,⊤ | ≤ HS T + | Ĝh (a, t + 1 :)(R h W ′ h )(s, t + 1 :) ⊤ | ≤ HS T + σ t+1 α √ dM -t∥W ′ h ∥ 2 ≤ HS T + tHS T ≤ 2 tHS Twhere the second and third inequalities comes from the same logic used in the proofs of Theorems 2 and 4, and the fourth inequality comes from the definition of t. From the same logic,s ′ ∈S (P h (s ′ |s, a) -U h (s ′ , s) Ĝt (a) ⊤ ) ≤ 2 tHS T .Therefore, Ĝh (a) satisfies Assumption 4 with ξ = tHS T . Then it follows that running LSVI-UCB-TR using Ĝt h (a) with δ ′ = δ/2 during the target phase of the algorithm admits a regret bound ofRegret(T ) ≤ C"( √ t 3 H 3 ST + 2tHT tHS T ) ∈ Õ( √ t 3 H 3 ST )with probability at least 1 -δ from a final union bound. Furthermore, the sample complexity in the source phase isÕ d 5 µ 5 κ 4 (S + A)M 3 H 4 α 2 T S ,which proves our result.In this section, we present the assumptions, algorithm, and results for the (S, d, A) Tucker rank setting. In this setting, we assume the following structure on the source and target MDPs. Assumption 5. In each of the M source MDPs, the reward functions have rank d, and the transition kernels have Tucker rank (S, d, A). Let the target MDP's reward functions have rank d ′ and transition kernels have Tucker rank (S, d ′ , A) where d ′ ≤ dM . Thus, there existsS × d × A tensors U m,h , S × d ′ × A tensors U h , S × d µ-incoherent matrices F m,h , S × d ′ µ-incoherent matrices F h with orthonormal columns, and A × d matrices W m,h , A × d ′ matrices W h such that P m,h (s ′ |s, a) = i∈[d] F m,h (s, i)U m,h (s ′ , a, i), r m,h (s, a) = i∈[d] F m,h (s, i)W m,h (a, i)andP h (s ′ |s, a) = i∈[d ′ ] F h (s, i)U h (s ′ , a, i), r h (s, a) = i∈[d ′ ] F h (s, i)W h (a, i)where ∥ s ′ ∈S g(s ′ )U m,h (s ′ , :, a)∥ 2 , ∥ s ′ ∈S g(s ′ )U h (s ′ , :, a)∥ 2 , ∥W h (a)∥ 2 , ∥W m,h (a)∥ 2 ≤ S/(dµ) for all s ∈ S, a ∈ A, h ∈ [H],(:, i)} i∈[d ′ ] ) ⊆ Span({F m,h (:, i)} i∈[d],m∈[M ] ).Before defining our transfer-ability coefficient, we first introduce the following notation. We define the set B h (F h , {F h,m } m∈M ) to contain all coefficients of the linear combinations, i.e.,B h ∈ R d ′ ,d,M and B h ∈ B h (F h , {F h,m } m∈M ) if for all i ∈ [d ′ ], h ∈ [H], F h (•, i) = j∈[d],m∈[M ] B h (i, j, m)F m,h (•, j).Furthermore, as the source MDPs latent factors of Q * m,h are not unique, we define α to measure the difficulty given the best set of latent factors from the source MDPs. Thus, α precisely measures the challenge involved in transferring the latent representation. Definition 4 (Transfer-ability Coefficient). Given a transfer RL problem that satisfies Assumptions 5, 6, and 3, let F be the set of all R S×d matrices with orthonormal columns that span the column space ofQ * m,h for all m ∈ [M ], h ∈ [H].Then, we define α as α := maxh∈[H] min F ∈F min B∈B h (F h ,F ) max i∈[d ′ ],j∈[d],m∈[M ]|B(i, j, m)|.We now prove our lower bound in this Tucker rank setting.To formalize the importance of α in transfer learning, we prove a lower bound that shows that a dependence on α in the sample complexity of the source phase is necessary to benefit from transfer learning. Theorem 7. There exist two transfer RL instances such that (i) they satisfy Assumptions 5 and 6, (ii) they cannot be distinguished without observing Ω(α 2 ) samples in the source phase, and (3) they have target state latent features that are orthogonal to each other.Proof. Suppose all source and target MDPs (S, A, P, H, r) share the same state space, action space, and horizon H = 1 and assume that S = A = [2n] for some n ∈ N + . For ease of notation, we let s 1 and a 1 refer to any state and action in [n], respectively, and s 2 and a 2 refer to any state and action in {n + 1, . . . 2n}, respectively. We will present the latent factors and optimal Q functions as block vectors and matrices with s 1 , s 2 , a 1 , a 2 as the blocks containing n entries. The initial state distribution in the target MDP is uniform over S. We now present two transfer RL problems with similar Q functions (with rows s 1 , s 2 and columns a 1 , a 2 ) that satisfy Assumptions 5 and 6 but have orthogonal target state latent factors. For ease of notation, the superscript i of Q * ,i m,h , Q * ,i h denotes transfer RL problem. Then, the optimal Q functions for transfer RL problem one areQ * ,1 1,1 = n 1/(2n) 1/(2n) 1/n 0 = 1/ √ 2 0 1/ √ 2 0 , Q * ,1 2,1 = n 1/(2n) 1/(2n) 0 1/n = 0 1/ √ 2 0 1/ √ 2 , Q * ,1 1 = n 1/(2n) 1/(2n) 1 n -1 n = 1/2 -1/2 1/2 -1/2 ,and the optimal Q functions for transfer RL problem two areQ * ,2 1,1 = n 1/(2n) 1/(2n) 1/n 0 = 1/ √ 2 0 1/ √ 2 0 Q * ,2 2,1 = nF ′ 0 1/n = 0 (1 + 1/α)/(c √ 2) 0 (1 -1/α)/(c √ 2) , Q * ,2 1 = n 1/(2n) -1/(2n) 1 n -1 n = 1/2 -1/2 -1/2 1/2 ,where F ′ = ( 1/(2n) + 1/(2nα 2 )/ 1 + 1/α 2 ( 1/(2n) -1/(2nα 2 )/ 1 + 1/α 21/(2n) -1/(2n) = -α 1/(2n) 1/(2n) + αcF ′ ⊤ .Furthermore, note that the target latent factors,F 1 = 1/(2n) 1/(2n) and F 2 = 1/(2n) -1/(2n)are orthogonal to each other.The learner is given either transfer RL problem one or two with equal probability with a generative model in the source problem. When interacting with the source MDPs, the learner specifies a stateaction pair (s, a) and source MDP m and observes a realization of a shifted and scaled Bernoulli random variable X. The distribution of X is that X = 1 with probability (Q * ,i m,1 (s, a) + 1)/2 and X = -1 with probability (1 -Q * ,i m,1 (s, a))/2). Furthermore, the learner is given the knowledge that the state latent features lie in the function class F = {F 1 , F 2 } and must use the knowledge obtained from interacting with the source MDP to choose one to use in the target MDP, which is no harder than receiving no information about the function class.To distinguish between the two transfer RL problems, one needs to differentiate between Q * , 1 2,1 and Q * ,2 2,1 . By construction, the magnitude of the largest entrywise difference between Q * ,1 2,1 and Q * ,2 2,1 is lower bounded by Ω(1/α).If the learner observes Z samples in the source MDPs, where Z ≤ O(α 2 ) for some constant C > 0, then the probability of correctly identifying F is upper bounded by 0.76 (Lemma 5.1 with δ = 0.24 [5] ). Thus, if the learner does not observe Ω(α 2 ) samples in the source phase, then the learner returns the incorrect feature mapping that is orthogonal to the true feature mapping with probability at least 0.24.Theorem 7 states that unless one incurs a sample complexity of Ω(α 2 ) in the source phase, the latent representation F learned in the source phase is useless in the target phase as one would incur linear regret using F .Our algorithm in this setting is essentially the same as the one used in the (S, S, d) Tucker rank setting except we construct our latent factors using the other set of singular vectors and compute Gram matrices and coefficients for each action instead of each state.Input: {N h } h∈[H] 1: for m ∈ [M ] do 2:Run LR-EVI({N h } h∈[H] ) on source MDP m to obtain Qm,h . (S, d, A )Input: λ, β a k,h , F 1: for k ∈ [K] do 2:Receive initial state s k 1 .3:for h = H, . . . , 1 do 4:for a ∈ A do5: Set Λ a h ← -t∈T a k-1,h Fh (s t h ) Fh (s t h ) ⊤ + λI. 6: /* Compute Gram matrix Λ a h */ 7: Set w a h ← -(Λ a h ) -1 t∈T a k-1,h Fh (s t h ) r h (s t h , a) + max a ′ ∈A Q h+1 (s t h+1 , a ′ ) . 8:/* Estimate w a h via regularized least squares */ Take action a k h ← -max a∈A Q h (s k h , a), and observe s k h+1 .9: Set Q h (•, •) ← -min H, ⟨w • h , Fh (•)⟩ + β • k,h Fh (•) ⊤ (Λ • h ) -1 Fh (•) .We first present the theoretical guarantees of LSVI-UCB-(S, d, A) and defer their proofs to Appendix J.Before proving our main positive result in the (S, d, A) Tucker rank setting, we first present the definitions and theorems of LSVI-UCB-(S, d, A) and defer their proofs to Appendix J. If one is given the true latent low-rank representation of each state, then LSVI-UCB-(S, d, A) admits the following regret bound. Theorem 8. Assume that Assumption 5 holds and the learner is given the true latent state representationF = {F h } h∈[H] .Then, there exists a constant c > 0 such that for any δ ∈ (0, 1), if we set λ = 1, β a k,h = cdH √ ι, ι = log(2dT A/δ), then with probability at least 1 -δ, the total regret of LSVI-UCB-TR is Õ(√ d 3 AH 3 T ).Theorem 8 states that LSVI-UCB-TR completely removes the regret bound's dependence on the size of the state space by utilizing the latent state representation F . To measure the algorithm's robustness with respect to misspecification error of the low-rank representation, we first define ξ-approximate (S, d, A) Tucker rank MDPs (similarly to Assumption B from [17] ). |r h (s, a) -F h (s) ⊤ W h (a)| ≤ ξ, s ′ ∈S (P h (s ′ |s, a) -F h (s) ⊤ U h (s ′ , a)) ≤ ξ for all h ∈ [H] where ∥W h ∥ 2 , ∥ s ′ ∈S g(s ′ )U h (s ′ , a)∥ 2 ≤ S/(dµ) for any function g : S → [0, 1].The following result shows that similar to LSVI-UCB, our algorithm is robust to the misspecified setting. Theorem 9. Suppose that the learner is given a feature mapping F ′ that satisfies Assumption 7. Then, using F = S/(dµ)F ′ as the feature mapping for any δ ∈ (0, 1) and λ = 1, β a k,h = O(Hd√ ι + ξ d|T a k,h |H) for ι = log(2dT A/δ), the regret of LSVI-UCB-TR is Õ( √ d 3 H 3 AT + ξdHT ) with probability at least 1 -δ.The above theorem states that the misspecification error adds a term that is linear in T to the regret bound of LSVI-UCB-(S, d, A). Thus, if one's latent state representation is close enough, i.e., ξ is so small that there exists some positive constant c such that ξdHT ≤ c √ d 3 H 3 AT , then LSVI-UCB-(S, d, A) admits a regret bound that is independent of the state space, which is the motivation for our main result. We now present our main theorem. Theorem 10. Suppose Assumptions 5, 6, and 3 hold, and set δ ∈ (0, 1). Furthermore, assume that, for any ϵ ∈ (0, AH/T ), Q m,h = r m,h + P m,h V m,h+1 has rank d and is µ-incoherent with condition number κ for all ϵ-optimal value functions V h+1 . Also, let λ = 1 and β a k,h be a function of d, H, |T a k,h |, |A|, M, T . Then, for T ≥ A α 2 , using at most Õ d 4 µ 5 κ 4 (S/A + 1)M 2 H 4 α 2 T samples in the source problems, our algorithm has regret at most Õ (dM H) 3 AT with probability at least 1 -δ.Theorem 10 states that using transfer learning improves the performance on the target problem by removing the regret bound's dependence on the state space. Thus, with enough samples from the source MDPs one can recover a regret bound in the target problem that matches the best regret bound for any algorithm in the (S, d, A) Tucker rank setting with known latent feature representation F concerning A and T . We now prove Theorem 10.Proof. Suppose the assumption stated in Theorem 10 hold. Then, from [30] , running LR-EVI with a sample complexity of C ′ d 4 µ 5 κ 4 (S + A)M H 4 α 2 T log(2SAdM H/δ)/A on each source MDP results in Qm,h functions with singular value decomposition Qm,h = Fm,h Σm,h Ĝm,h that are √ HA/(16αµκ √ dM T )-optimal with probability at least 1 -δ/2.Since our estimates are √ HA/(16α √ dM T )-optimal, it follows that γ < 1/2 in the singular vector perturbation bound, Corollary 3. Since ∥Q * m,h ∥ ∞ ≥ C, from Corollary 3, it follows that there exists rotation matrices R m,h such that∥( Fm,h R m,h -F m,h )(s)∥ 2 ≤ d √ HµA α √SM T for all s ∈ S where the optimal Q function have singular value decompositionQ * m,h = F m,h Σ m,h G ⊤ m,h .Let F be the S × dM matrix from joining all the source state latent factor matrices, and Fh be the S × dM matrix from joining all Fm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ].Then, from Assumption 6 and Definition 4, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] F h (s, i)W h (a, i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)F h,m (s, j)   W h (a, i) = i,j∈[d],m∈[M ] B(i, j, m)F m,h (s, j)W h (a, i) = Fh (s)W ′ h (a) ⊤ and P (s ′ |•, •) = Fh U ′ h (s ′ ) ⊤ (with the same argument) for some A × dM matrices W ′ h , U ′ h (s ′ ). Note that W ′ h and U ′ h (s ′) are matrices that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry.Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H],|r h (s, a) -Fh (s)R h W ′ h (a) ⊤ | = | Fh (s)W ′ h (a) ⊤ -Fh (s)R h W ′ h (a) ⊤ | = |( Fh (s) -Fh (s)R h )W ′ h (a)| ≤ α| m∈M (F m,h (s) -Fm,h (s)R m,h )W m,h (a)| ≤ α m∈M ∥F m,h (s) -Fm,h (s)R m,h ∥ 2 ∥W m,h (a)∥ 2 ≤ α S dµ m∈M ∥F m,h (s) -Fm,h (s)R m,h ∥ 2≤ dHM A T from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,s ′ ∈S (P h (s ′ |s, a) -F h (s) ⊤ U h (s ′ , a)) = | Fh (s)U ′ h (s ′ , a) -Fh (s)R h U ′ h (s ′ , a) ⊤ | = |( Fh (s) -Fh (s)R h ) s ′ ∈S U ′ h (s ′ , a) ⊤ | ≤ α| m∈M (F m,h (s) -Fm,h (s)R m,h ) s ′ ∈S U m,h (s ′ , a)| ≤ α m∈M ∥F m,h (s) -Fm,h (s)R m,h ∥ 2 ∥ s ′ ∈S U m,h (s ′ , a) ⊤ ∥ 2 ≤ dHM A T .Therefore, Fh (s) satisfies Assumption 7 with ξ = dM HA T . Then it follows that running LSVI-UCB-TR using Fh (s) with δ ′ = δ/2 during the target phase of the algorithm admits a regret bound ofRegret(T ) ≤ C"( √ d 3 M 3 H 3 AT + dM H dM HA T ) ∈ Õ( √ d 3 M 3 H 3 AT )with probability at least 1 -δ from a final union bound. Furthermore, the sample complexity in the source phase isÕ d 4 µ 5 κ 4 (S + A)M 2 H 4 α 2 T A ,which proves our result.In this section, we consider the same transfer reinforcement learning setting with the low Tucker rank assumptions except the learner is given access to the generative model in both the source and target problems. In this setting, we isolate the statistical difficulty of the transfer RL problem by removing the challenge of exploration. Thus, instead of regret, the goal in this setting is to learn an ϵ-optimal Q function in the target phase using as few samples in the source and target phases as possible. The main benefit of having access to a generative model in the target phase is that the learner can choose the best states to observe covariates from when performing the regression step at each time step. In this setting, our algorithm still uses LR-EVI in the source phase (Algorithm 3 and adapts the algorithm from [22] for the finite horizon setting in the target phase. Learning Q * over the support of an approximately optimal design ρ on our latent factors F allows us to construct a good estimate of Q * over all state-action pairs. The optimal design problem that we solve in this algorithm isG(ρ) = s∈S ρ(s) F (s) F (s) ⊤ , g(ρ) = max s∈S ∥ F ∥ G(ρ) -1where ρ is a probability distribution over S. From Theorems 4.3 and 4.4 [22] , one can compute a ρ such that g(ρ) ≤ 2d, with the core set of states, or anchor states, S # = {s ∈ S|ρ(s) > 0} having size at most 4d log(log(d)) + 16 in a polynomial number of computations. This ensures that both the error amplification from using the low-rank structure and the number of states we need to observe Q * is not too large. Our algorithm is tailored to the (S, d, A) Tucker rank setting but can easily be modified for the other Tucker rank settings.Algorithm 5 Target PhaseInput: {N t h } h∈[H] , F 1: for h = H, . . . , 1 do 2:Compute S # h , ρ h according to the above optimal design problem with Fh .3:for (s, a) ∈ S # h × A do 4:Collect N t h samples of the reward function and one-step transition to estimate Qh (s, a) with Qh (s, a) = rh (s, a)+ E s ′ ∼ Ph (•|s,a) [ Vh+1 (s ′ )],where rh (s, a) denotes the empirical average of the N t h samples of the reward function, and Ph (•|s, a) denotes the empirical distribution over the N t h samples.Use the linear structure to estimate Q over all state-action pairs withθa,h = G(ρ) -1 s∈S # h ρ(s) Fh (s) Qh (s, a), Qh (s, a) = Fh (s)θ a,h . 6:Compute the value function and policy using the Q function, Vh (s) = max a∈A Qh (s, a), πh (s) = arg max a∈A Qh (s, a).In the source phase, our algorithm learns estimates of Q * m,h and then computes the singular value decomposition to construct approximate feature mappings using the singular subspaces with respect to the state. In step (a) of the target phase, one first approximately solves the optimal design problem to compute the anchor states. After obtaining estimates of the Q function on the anchor states, one uses the linear structure in step (c) to estimate the full Q function over all states with the least squares solution. The above algorithm admits the following sample complexities for learning an ϵ-optimal Q function in the target phase. Theorem 11. Suppose Assumptions 5, 6, and 3 hold, and set δ ∈ (0, 1). Furthermore, assume that for any ϵ > 0, Q m,h = r m,h + P m,h V m,h+1 has rank d and is µ-incoherent with condition number κ for all ϵ-optimal value functions V h+1 . Then, for ϵ ≤ αd 2 , using at mostÕ d 7 µ 3 κ 4 (S + A)H 9 α 2 M 3 ϵ 2samples in the source problems, Algorithm 5 learns an ϵ-optimal policy in the target MDP using at most Õ d 2 M 2 H 5 A ϵ 2 samples with probability at least 1 -δ.Theorem 11 states that with enough samples in the source phase, one can remove the dependence on the size of the state space in the target phase; in tabular finite-horizon MDPs with (S, d, A) Tucker rank transition kernels, one needs to observe at least Ω(d(S + A)H 3 /ϵ 2 ) samples from a generative model to learn an ϵ-optimal policy. Furthermore, the source sample complexity's dependence on S, A, and H are reasonable while the dependence on α is optimal due to our lower bound. We can easily construct similar algorithms that admit the corresponding theoretical guarantees in the other Tucker rank settings. We now prove Theorem 11.Proof. In the source phase, usingÕ d 6 µ 3 κ 4 (S + A)H 9 α 2 M 4 ϵ 2samples guarantees that we learn ϵ/(128H 2 αM 3/2 κd 2 )-optimal Qm,h = Fm,h Σm,h Ĝ⊤ m,h functions for each source MDP with probability at least 1 -δ/2. Since αd 2 ≥ ϵ by assumption, we have γ < 1/2 in the singular vector perturbation bound, Corollary 3. Since ∥Q * m,h ∥ ∞ ≥ C, it follows from Corollary 3 that there exists rotation matrices R m,h such that∥F m,h -Fm,h R∥ 2,∞ ≤ ϵ √ µ 8H 2 αM 3/2 √ Sholds for all m ∈ [M ], h ∈ [H] with probability at least 1 -δ/2. Let F be the S × dM matrix from joining all the source state latent factor matrices, and Fh be the S × dM matrix from joining all Fm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ]. Then, from Assumption 6 and Definition 4, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] F h (s, i)W h (a, i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)F h,m (s, j)   W h (a, i) = i,j∈[d],m∈[M ] B(i, j, m)F m,h (s, j)W h (a, i) = Fh (s)W ′ h (a) ⊤ and P (s ′ |•, •) = Fh U ′ h (s ′ ) ⊤ (with the same argument) for some A × dM matrices W ′ h , U ′ h (s ′ ). Note that W ′h and U ′ h (s ′ ) are matrices that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry. Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H],|r h (s, a) -Fh (s)R h W ′ h (a) ⊤ | = | Fh (s)W ′ h (a) ⊤ -Fh (s)R h W ′ h (a) ⊤ | = |( Fh (s) -Fh (s)R h )W ′ h (a)| ≤ α| m∈M (F m,h (s) -Fm,h (s)R m,h )W m,h (a)| ≤ α m∈M ∥F m,h (s) -Fm,h (s)R m,h ∥ 2 ∥W m,h (a)∥ 2 ≤ α S dµ m∈M ∥F m,h (s) -Fm,h (s)R m,h ∥ 2 ≤ ϵ 8 √dM H 2 from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,|P V (s, a) -[ Fh R h U ′ h V ](s, a)| = | s ′ ∈S P h (s ′ |s, a)V (s ′ ) -Fh (s)R h U ′ h (s ′ , a) ⊤ V (s ′ )| = | s ′ ∈S Fh (s)U ′ h (s ′ , a) ⊤ V (s ′ ) -Fh (s)R h U ′ h (s ′ , a) ⊤ V (s ′ )| ≤ H|( Fh (s) -Fh (s)R) s ′ ∈S U ′ h (s ′ , a)| ≤ Hα m∈M ∥F m,h (s) -Fm,h (s)R∥ 2 ∥ s ′ ∈S U m,h (s ′ , a)∥ 2 ≤ Hα √ S √ dµ m∈M ∥F m,h (s) -Fm,h (s)R∥ 2 ≤ ϵ 8 √ dM H .From the above result, it follows that for any value function V , the misspecification error of using the approximate feature mapping of the correspondingQ function Q ′ = r + P V satisfies |Q ′ h (s, a) -Q ′ h,d (s, a)| ≤ |r h (s, a) -F (s)RW (a) ⊤ | + |P V (s, a) -[ Fh R h U ′ h V ](s, a)| ≤ ϵ 8 √ dM H 2 + ϵ 8 √ dM H ≤ ϵ 4H √ dM .To prove our main theorem, we first present the following helper lemma and defer the proof to later in this section.Lemma 2. Suppose the setting of Theorem 11 holds and that the misspecification error of the bellman update for any value function using an approximate feature mapping satisfies|Q ′ h (s, a) -Q ′ h,d (s, a)| ≤ ϵ 4H √ dM .Then, the learned Q function from our algorithm at time step h satisfies∥ Qh -Q * h ∥ ∞ , ∥ Qh -Q π h ∥ ∞ ≤ ϵ(H -h + 1) H for h ∈ [H] for N h = H 4 dM C 2 log(SAH/δ)/ϵ 2 with probability at least 1 -(H -h + 1)δ/(2H).From a union bound and applying Lemma 2, it follows that Linear Q-Learning learns an ϵ-optimal policy with probability at least 1 -δ. Therefore, the sample complexity of the algorithm ish∈H N h |S # h |A ≤ Õ d 2 M 2 H 5 A ϵ 2 .It follows from the triangle inequality that the learned policy is 2ϵ-optimal by replacing 2ϵ with ϵ ′ .We now prove Lemma 2.Proof. We proceed via induction. At time step H (the base case), it follows from Hoeffding's inequality for N H = H 4 dM C 2 log(SAH/δ)/ϵ 2 for some constant C > 0,| QH (s, a) -Q * H (s, a)| ≤ ϵ 4 √ dM Hfor (s, a) ∈ S # h × A. From Proposition 4.5 from [22] and our assumption on the misspecification error of the approximate feature mapping, it follows that| QH (s, a) -Q * H (s, a)| ≤ ϵ H .Since Q π H = Q * H , it follows that the base case holds.Next, assume that∥ Qh+1 -Q * h+1 ∥ ∞ , ∥ Qh+1 -Q π h+1 ∥ ∞ ≤ ϵ(H -h) H holds with probability at least 1 -(H -h)δ/(2H). We define Q ′ h as Q ′ h = r h + P h Vh+1 . Let Q ′ h,d = F h (W h + s ′ ∈S Vh+1 (s ′ )U h (s ′ )).Then, it follows that from Hoeffding's inequality forN h = H 4 C 2 dM log(SAH/δ)/ϵ 2 for some constant C > 0, for all (s, a) ∈ S # h × A, in step (b) of our algorithm, | Qh (s, a) -Q ′ h (s, a)| ≤ ϵ 4H √ dM .From our assumption on the misspecification error of the approximate feature mapping, it follows that∥Q ′ h -Q ′ h,d ∥ ∞ ≤ ϵ 4H √dM . Then, from Proposition 4.5 [22] , we have| Qh (s, a) -Q ′ h,d (s, a)| ≤ ϵ 2H + ϵ 2H = ϵ H for all (s, a) ∈ S × A. Since |Q * h (s, a) -Q ′ h (s, a)| ≤ | s ′ ∈S (V * h+1 (s ′ ) -Vh+1 (s ′ ))P h (s ′ |s, a)| ≤ ϵ(H -h) H and |Q π h (s, a) -Q ′ h (s, a)| ≤ | s ′ ∈S (V * h+1 (s ′ ) -Vh+1 (s ′ ))P h (s ′ |s, a)| ≤ ϵ(H -h) H ,holds from the inductive hypothesis for all (s, a) ∈ S × A, it follows that| Qh (s, a) -Q * h (s, a)| ≤ | Qh (s, a) -Q ′ h (s, a)| + |Q ′ h (s, a) -Q * h (s, a)| ≤ ϵ H + ϵ(H -h) H = ϵ(H -h + 1) H ,and similarly,|Q π h (s, a) -Qh (s, a)| ≤ ϵ(H -h + 1) H .Thus, the inductive hypothesis holds as a union bound asserts that the above result holds with probability at least 1 -(H -h + 1)δ/(2H).In the low-rank MDP transfer RL setting, [4] provide an algorithm that admits a source sample complexity of Õ(Aα 3 M T log(Φ)) and target regret of Õ( ᾱH 2 d 3/2 √ T ) with high probability in the transfer RL setting with low-rank MDPs. We first present the transfer learning assumptions in [4] needed to prove a lower bound in their setting. Low rank MDPs assume the following stucutre with shared latent representation ϕ,P m,h (s ′ |s, a) = µ m,h (s ′ ) ⊤ ϕ h (s, a), P h (s ′ |s, a) = µ h (s ′ ) ⊤ ϕ h (s, a), where ∥ϕ h (s, a)∥ 2 ≤ 1 and ∥ µ(s)g(s)dx∥ 2 ≤ √ d for any function g : S → [0, 1] [3] for all m ∈ [M ], h ∈ [H].To allow transfer learning to occur, [4] assume the following: Assumption 8 (Assumption 2.2 [4] ). For any h ∈ [H] and s ′ ∈ S, there exists α m,h (s′ ) ∈ R such that µ h (s ′ ) = m∈[M ] α m,h (s ′ )µ m,h (s ′ ),and define the task-relatedness coefficient as α = max m∈[M ],h∈[H],s∈S α m,h (s). They leave determining the optimal dependence on α as an interesting open question. Similarly to our lower bound in Theorem 1, we prove that one must incur a source sample complexity of Ω(α 2 ) to benefit from using transfer learning. Note that in this version of transfer RL, there is no reward function in the source tasks.Theorem 12. There exist two transfer RL instances such that (i) they satisfy Assumptions 9 and 8, (ii) they cannot be distinguished without observing Ω(α 2 ) samples in the source phase, and (3) they have target state-action latent features that are orthogonal to each other.Proof. We consider two low-rank transfer RL problems, in which the source MDPs have similar transition kernels but differing ϕ. All source and target MDPs (S, A, P, H, r) share the same state space, action space, and horizon H = 2 with M = 2. The learner is given access to a generative model in the source problems. To introduce the MDPs (without loss of generality assume that |S|, |A| are even), we first define the feature representations: the feature mapping ϕ i for transfer RL problem i isϕ 1 (s 1 , a 1 ) = ϕ 1 (s 2 , a 2 ) = [1, 0] ⊤ , ϕ 1 (s 1 , a 2 ) = ϕ 2 (s 2 , a 1 ) = [0, 1] ⊤ , ϕ 2 (s 1 , a 1 ) = ϕ 2 (s 2 , a 2 ) = [0, 1] ⊤ , ϕ 2 (s 1 , a 2 ) = ϕ 2 (s 2 , a 1 ) = [1, 0] ⊤where s 1 refers to states 1, . . . , |S|/2, s 2 refers to states |S|/2 + 1, . . . , |S|, and similarly for actions. We will present the transition kernels matrices with s 1 , s 2 , a 1 , a 2 as the blocks containing |S|/2 or |A|/2 entries. Clearly, the two feature representations are orthogonal to each other. Next, the transition kernels P i m,1 for transfer RL problem i and source MDP m areP 1 1,1 (s 1 |•, •) = [1/2, 1/2 -1/α]ϕ 1 (•, •) = 1/2 1/2 -1/α 1/2 -1/α 1/2 P 1 1,1 (s 2 |•, •) = [1/2, 1/2 + 1/α]ϕ 1 (•, •) = 1/2 1/2 + 1/α 1/2 + 1/α 1/2 P 2 1,1 (s 1 |•, •) = [1/2, 1/2 -1/α]ϕ 2 (•, •) = 1/2 -1/α 1/2 1/2 1/2 -1/α P 2 1,1 (s 2 |•, •) = [1/2, 1/2 + 1/α]ϕ 2 (•, •) = 1/2 + 1/α 1/2 1/2 1/2 + 1/α P 1 2,1 (s 1 |•, •) = P 1 2,1 (s 2 |•, •) = P 2 2,1 (s 2 |•, •) = P 2 2,1 (s 2 |•, •) = [1/2, 1/2]ϕ 1 (•, •) = [1/2, 1/2]ϕ 2 (•, •) = 1/2 1/2 1/2 1/2 P i T (•|•, •) = µ T (•)ϕ i (•, •), where µ T (•) = [0, 1] in both transfer RL problems. It follows that µ T (s 1 ) = α(µ 2 1 (s 1 ) -µ 1 1 (s 1 )) = α(µ 2 2 (s 1 ) -µ 1 2 (s 1)) and similar results hold for s 2 , so α satisfies the definition of the task-relatedness coefficient. It follows that in both settings, α max = α. The target phase reward functions are defined asr 1 1 (•, •) = r 1 2 (•, •) = [1, 0]ϕ 1 (•, •) r 2 1 (•, •) = r 2 2 (•, •) = [1, 0]ϕ 2 (•,•), and the initial state distribution is uniform across all states. By construction, in transfer RL problem 1, the only state action pairs that receive reward are (s 1 , a 1 ), (s 2 , a 2 ). In contrast, in transfer RL problem 2, the only state action pairs that receive reward are (s 1 , a 1 ), (s 2 , a 1 ).The learner is given either transfer RL problem one or two with equal probability with a generative model in the source problem. When interacting with the source MDPs, the learner specifies a state-action pair (s, a) and source MDP m and observes a transition from P i 1,m . Furthermore, the learner is given the knowledge that the state latent features lie in the function class Φ = {ϕ 1 , ϕ 2 } and must use the knowledge obtained from interacting with the source MDP to choose one to use in the target MDP, which is no harder than receiving no information about the function class.To distinguish between the two transfer RL problems, one needs to differentiate between P 1 1,1 and P 2 1,1 . By construction, the magnitude of the largest entrywise difference between P 1 1,1 and P 2 1,1 is lower bounded by Ω(1/α 2 ). If the learner observes Z transitions in the source MDPs, where Z ≤ O(α 2 ) for some constant C > 0, then the probability of correctly identifying ϕ is upper bounded by 0.76 [5] . Thus, if the learner does not observe Ω(α 2 ) samples in the source phase, then the learner returns the incorrect feature mapping that is orthogonal to the true feature mapping with probability at least 0.24.Theorem 12 states that one must incur dependence on α in the source sample complexity to benefit from transfer learning as using a feature mapping that is orthogonal to the true one results in regret linear in T .As the low rank MDP setting is analogous to our (d, S, A) Tucker rank setting, we next present our assumptions in this setting, EQUATIONandP h (s ′ |s, a) = i∈[d ′ ] ϕ h (s, a, i)U h (s ′ , i), r h (s, a) = i∈[d ′ ] ϕ h (s, a, i)W h (i)where While [4] assume that the target latent representation is a linear combination of the source latent representation, we allow for a more general setting to enable transfer learning. Specifically, we assume that the space spanned by the target latent representations is a subset of the space spanned by the source latent representations. Assumption 10. Suppose Assumption 9 holds. For latent factors ϕ h from the target MDP and ϕ m,h for the source MDPs, let∥ s ′ ∈S g(s ′ )U m,h (s ′ )∥ 2 ,∥ s ′ ∈S g(s ′ )U h (s ′ )∥ 2 ≤ √ d, ∥W h ∥ 2 ,ϕ h = {ϕ h , ϕ h,m } m∈[M ] . Then, there exists a non-empty set B(ϕ h ) such that the elements in B(ϕ h ) are B h ∈ R d ′ ,d,M such that ϕ h (s, i) = j∈[d],m∈[M ] B h (i, j, m)ϕ m,h (s, j) for all i ∈ [d ′ ], s ∈ S, h ∈ [H].As in the previous Tucker rank settings, we present the transfer-ability coefficient to quantify the difficulty transfer learning. |B(i, j, m)|.[4] provide an alternate definition of α, which also measures the difficulty of transfer RL, and leave determining the optimal dependence on α as an interesting open question. Similarly to our lower bound in Theorem 1, we prove that one must incur a source sample complexity of Ω(α 2 ) to benefit from using transfer learning. Note that in this Tucker rank setting, there is no reward function in the source tasks.Theorem 13. There exist two transfer RL instances such that (i) they satisfy Assumptions 9 and 10, (ii) they cannot be distinguished without observing Ω(α 2 ) samples in the source phase, and (3) they have target state-action latent features that are orthogonal to each other.Proof. Consider the construction where all source and target MDPs (S, A, P, 1, r) share the same state space, action space, and horizon with H = 1. As the horizon is one, we use the construction used to prove Theorem 7. We consider two transfer RL problems i, i ′ , in which the source MDPs have similar Q * 1 , but with orthogonal target ϕ T . For ease of notation, we let a 1 refer to any action in [n], and a 2 refer to any action in {n + 1, . . . 2n}, respectively. The initial state distribution in the target MDP is uniform over S. We now present two transfer RL problems with similar Q functions that satisfy Assumptions 5 and 6 but have orthogonal target state latent factors. For ease of notation, the superscript i of Q * ,i m,h , Q * ,i h denotes transfer RL problem. Then, the optimal Q functions (with columns representing a 1 and a 2 and the row being any state) for transfer RL problem one areQ * ,1 1,1 = W 1 1,h ϕ 1 1,1 √ n √ n 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2 , Q * ,1 2,1 = W 1 2,h ϕ 1 1,1 √ n √ n 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2 , Q * ,1 1 = W h ϕ 1 1 = √ n √ n 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2and for transfer RL problem two areQ * ,2 1,1 = W 2 1,h ϕ 2 1,1 √ n √ n 1/(2n) 1/(2n) = 1/ √ 2 1/ √ 2 , Q * ,2 2,1 = W 2 2,h ϕ 2 2,1 √ n √ n G ′ = (1 + 1/α)/(c √ 2) (1 -1/α)/(c √ 2) , Q * ,1 2 = W h ϕ 2 1 = √ n √ n 1/(2n) -1/(2n) = 1/ √ 2 -1/ √ 2and c = 1 + 1/α 2 . Note that c ∈ (1, 2dM ) because α ≥ 1/(dM ) from Lemma 1 for α > 0. The incoherence µ, rank d, and condition number κ of the above Q functions are O(1). Furthermore, the above construction satisfies Assumption 9 with Tucker rank (1, S, A) and Assumption 10 because the source and target MDPs share the same feature representation ϕ 1 1 = ϕ 1 1,1 in the first transfer RL problem while in the second transfer RL problem,ϕ 2 1 = -αϕ 2 2,1 + αϕ 2 2,1 .Note that ϕ 1 1 and ϕ 2 2 are orthogonal to each other by construction. The learner is given either transfer RL problem one or two with equal probability with a generative model in the source problem. When interacting with the source MDPs, the learner specifies a stateaction pair (s, a) and source MDP m and observes a realization of a shifted and scaled Bernoulli random variable X. The distribution of X is that X = 1 with probability (Q * ,i m,1 (s, a) + 1)/2 and X = -1 with probability (1 -Q * ,i m,1 (s, a))/2). Furthermore, the learner is given the knowledge that the state latent features lie in the function class Φ = {ϕ 1 , ϕ 2 } and must use the knowledge obtained from interacting with the source MDP to choose one to use in the target MDP, which is no harder than receiving no information about the function class.To distinguish between the two transfer RL problems, one needs to differentiate between Q * ,1 2,1 and Q * ,2 2,1 . By construction, the magnitude of the largest entrywise difference between Q * ,1 2,1 and Q * ,2 2,1 is lower bounded by Ω(1/α).If the learner observes Z samples in the source MDPs, where Z ≤ O(α 2 ) for some constant C > 0, then the probability of correctly identifying G is upper bounded by 0.76 (Lemma 5.1 with δ = 0.24 [5] ). Thus, if the learner does not observe Ω(α 2 ) samples in the source phase, then the learner returns the incorrect feature mapping that is orthogonal to the true feature mapping with probability at least 0.24.Theorem 13 states that one must incur dependence on α in the source sample complexity to benefit from transfer learning. With this lower bound, we've shown in all three Tucker rank settings that α determines the effectiveness of transfer learning under our transfer learning assumptions. We now present our algorithm that admits an efficient source sample complexity and target regret bound.In contrast to our approaches in the other Tucker rank settings, one learns the latent representation in the source MDPs through the transition kernels. One potential issue arises when all entries of P (•|•, a) are small; for example, each entry of the uniform transition kernel is 1/S, which is not lower bounded by a constant. Thus, we let D = min m∈[M ],h∈[H],a∈A ∥P m,h (•|•, a)∥ ∞ , and the dependence on D is unsurprising as one needs to ensure the noise is sufficiently small to learn the latent representations from P m,h . We now present and prove the main result in this Tucker rank setting.Input: N 1: for (s, a) ∈ S × A, h ∈ [H], m ∈ [M ] do 2:Collect N transitions from source MDP m at time step h at state-action pair (s, a).Use the samples to estimate the transition kernel withPm,h (s ′ |s, a) = 1 N i∈[N ] 1 Xi,s,a=s ′ ,where X i,s,a ∼ P m,h (•|s, a). |P m,h (s ′ |s, a) -Pm,h (s ′ |s, a)| ≤ √ H αµκD √ dM T with probability at least 1 -δ/(2S 2 AM H) where Pm,h (s ′ |s, a) = 1 N i∈[N ] 1 Xi(s,a)=s ′ and X i ∼ P (•|s, a) for N = α 2 dµ 2 κ 2 M T log(4S 2 AM H/δ) 2HD 2 . Let Pm,h (•|•, a) = F a m,hΣm,h Ĝm,h ⊤ be the singular value decomposition of our estimate where F corresponds to the state one transitions from. Since T ≥ α 2 /H, it follows that γ ≤ 1/2. Thus, 3 states that there exists rotation matrices R m,h,a such that∥( F a m,h R m,h,a -F a m,h )(s)∥ 2 ≤ d √ Hµ α √ M T S ,for all s ∈ S where the the true transition kernel P m,h (•|•, a) has singular value decompositionP m,h (•|•, a) = F a m,h Σ m,h G ⊤ m,h. We can re-express our terms in the more common Low rank MDP setting with ϕ m,h (s, a) = F a m,h (s) and µ m,h (s′ ) = Σ m,h G ⊤ m,h .Let F be the SA × dM matrix from joining all the source state latent factor matrices from P (•|•, a)for each a ∈ A, and Fh be the SA × dM matrix from joining all Fm,h . Let R h be the d × dM matrix that joins R m,h for all m ∈ [M ]. Then, from Assumption 6 and Definition 4, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] F a h (s, i)W h (i) = i∈[d]   j∈[d],m∈[M ] B(i, j, m)F a h,m (s, j)   W h (i) = i,j∈[d],m∈[M ] B(i, j, m)F a m,h (s, j)W h (i) = F a h (s)W ′ ⊤ h and P (s ′ |s, a) = F a h (s)U ′ h (s ′ ) ⊤ (with the same argument) for some dM -dimension vector W ′ h , U ′ h (s ′ ). Note that W ′ h and U ′ h (s ′) are vectors that join W m,h and U m,h (s ′ ), respectively, with entries that at most α times larger than the original entry.Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H],|r h (s, a) -F a h (s)R h W ′ ⊤ h | = | F a h (s)W ′ ⊤ h -F a h (s)R h W ′ ⊤ h | = |( F a h (s) -F a h (s)R h )W ′ ⊤ h | ≤ α| m∈M (F a m,h (s) -F a m,h (s)R m,h )W m,h | ≤ α m∈M ∥F a m,h (s) -F a m,h (s)R m,h ∥ 2 ∥W m,h ∥ 2 ≤ α S dµ m∈M ∥F a m,h (s) -F a m,h (s)R m,h ∥ 2≤ dHM T from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,s ′ ∈S (P h (s ′ |s, a) -F a h (s)R h U ′ h (s ′ ) ⊤ ≤ | s ′ ∈S P h (s ′ |s, a) -F a h (s)R h U ′ h (s ′ ) ⊤ | = | s ′ ∈S F a h (s)U ′ h (s ′ ) -F a h (s)R h U ′ h (s ′ ) ⊤ | ≤ α| m∈M (F a m,h (s) -F a m,h (s)R m,h ) s ′ ∈S U m,h (s ′ )| ≤ α m∈M ∥F a m,h (s) -F a m,h (s)R m,h ∥ 2 ∥ s ′ ∈S U m,h (s ′ ) ⊤ ∥ 2 ≤ dHM T .Therefore, F a h (s) satisfies Assumption B in [17] with ξ = dM H T 5 . Then it follows that running LSVI-UCB using F a h (s) with δ ′ = δ/2 during the target phase of the algorithm admits a regret bound ofRegret(T ) ≤ C"( √ d 3 M 3 H 3 T + dM H dM H T ) ∈ Õ( √ d 3 M 3 H 3 T )with probability at least 1 -δ from a final union bound. Furthermore, the sample complexity in the source phase isÕ α 2 dµ 2 κ 2 M 2 T SA D 2 ,which proves our result.In this section, we present the assumptions, algorithm, and proof for Theorem × d × d tensors U m,h , d × d ′ × d ′ tensors U h , S × d matrices V m,h , S × d ′ matrices V h , S × d matrices F m,h , S × d ′ matrices F h , A × d matrices G m,(i) ≥ R + } i∈[d] , {σ h (i) ≥ R + } i∈[d ′ ] such that P m,h (s ′ |s, a) = i∈[d],j∈[d ′ ],k∈[d] U m,h (i, j, k)V m,h (s ′ , i)F m,h (s, j)G m,h (a, k), r m,h (s, a) = i∈[d] σ m,h (i)F m,h (s, i)G m,h (a, i)and P h (s ′ |s, a) = i∈[d],j∈[d ′ ],k∈[d ′ ] U h (i, j, k)V h (s ′ , i)F h (s, j)G h (a, k), r h (s, a) = i∈[d ′ ] σ h (i)F h (s, i)G h (a, i) where ∥ i∈[d],s ′ ∈S g(s ′ )U m,h (i, :, :)V m,h (s ′ , i)∥ F ,∥ s ′ ∈S,i∈[d] g(s ′ )U h (i, :, : )V h (s ′ , i)∥ F , σ m,h (i), σ h (i) ≤ √ SA dµ for all s ∈ S, a ∈ A, h ∈ [H], m ∈ [M ](G) are C ∈ R d ′ ,d,M such that F h (s, i) = j∈[d],m∈[M ] B(i, j, m)F m,h (s, j) and G h (a, i) = j∈[d],m∈[M ] C(i, j, m)G m,h (a, j) for all i ∈ [d ′ ], s ∈ S, a ∈ A.Similarly to the (S, d, A) and (S, S, d) Tucker rank settings, we introduce the transfer-ability coefficient that measures the difficulty of applying transfer learning. Definition 6 (Transfer-ability Coefficient). Given a transfer RL problem that satisfies Assumptions 11, 12, and 3, let F be the set of all R S×d latent factor matrices with orthonormal columns that span the column space ofQ * m,h for all m ∈ [M ], h ∈ [H].Let G be the set of all R A×d latent factor matrices with orthonormal columns that span the row space ofQ * m,h for all m ∈ [M ], h ∈ [H].Then, we define α as α := max minF ∈F min B∈B(F ) max i∈[d ′ ],j∈[d],m∈[M ] |B(i, j, m)|, min G∈G min C∈C(F ) max i∈[d ′ ],j∈[d],m∈[M ] |C(i, j, m)| .In contrast to the definition in the other Tucker rank settings, α bounds the largest coefficient used in the linear combination of F h and G h . The algorithm that we use in this setting runs LR-EVI on each of the source MDPs, constructs a feature mapping φ using the singular vectors from the singular value decomposition of Qm,h , and runs LSVI-UCB with φ. Since we use both sets of singular vectors to construct φ, our feature mapping has latent dimension d 2 M 2 .Input: {N h } h∈[H] 1: for m ∈ [M ] do 2:Run LR-EVI({N h } h∈[H] ) on source MDP m to obtain Qm,h . The above algorithm admits the following result.Theorem 15. Suppose Assumptions 11, 12, and 3 hold in the (d, d, d) Tucker Rank setting, and set δ ∈ (0, 1). Furthermore, assume that for any ϵ ∈ (0, H/T ), Q m,h = r m,h + P m,h V m,h+1 has rank d and is µ-incoherent with condition number κ for all ϵ-optimal value functions V h+1 . Then, assuming T ≥ H/α 2 , using at mostÕ d 10 µ 5 κ 4 (S + A)M 2 H 4 α 4 Tsamples in the source problems, our algorithm has regret at mostÕ √ d 6 M 6 H 3 Twith probability at least 1 -δ for λ = 1 and β h,k , which is a function of d, H, T, M .We now prove Theorem 15 using a similar argument to the one used in the proof of Theorem 10 except we show that the target MDP with our feature mapping satisfies Assumption B in [17] and apply LSVI-UCB.Proof. Suppose the assumptions stated in Theorem 15 hold. Then, from Theorem 9 [30] , it follows that LR-EVI returns near-optimal Q functions Qm,h functions with singular value decomposition Qm,h = Fm,h Σm,h Ĝm,h that are √ H/(κα 2 M d 4 µ √ T )-optimal with probability at least 1 -δ/2 using Õ d 10 µ 5 κ 4 (S + A)M H 4 α 4 T samples on each source MDP. Since T ≥ H/α 4 , from γ ≤ 1 2 in Proposition 2. Thus, 3 states that there exists rotation matrices R m,h,f , R m,h,g such that∥( Fm,h R m,h,f -F m,h )(s)∥ 2 ≤ √ H α 4 M d 2 √ T Sµ , ∥( Ĝm,h R m,h,g -G m,h )(s)∥ 2 ≤ √ H α 4 M d 2 √T Aµ for all s ∈ S where the optimal Q function have singular value decompositionQ * m,h = F m,h Σ m,h G ⊤ m,h .Then, from Assumption 6 and Definition 4, it follows that for all (s ′ , s, a) ∈ S × S × A, thatr h (s, a) = i∈[d] σ h (i)F h (s, i)G h (a, i) = i∈[d] σ h (i)   j∈[d],m∈[M ] B(i, j, m)F h,m (s, j)     l∈[d],n∈[M ] C(i, l, n)G h,n (s, l)   = j,l∈[d],m,n∈[M ] F m,h (s, j)G n,h (a, l)   i∈[d] σ h (i)B(i, j, m)C(i, l, n)   = θ h ϕ(s, a) ⊤ h where θ h = { i∈[d] σ h (i)B(i, j, m)C(i, l, n)} j,l∈[d],m,n∈[M ] and ϕ h = {F m,h (s, j)G n,h (a, l)} j,l∈[d],m,n∈[M ] and P (s ′ |•, •) = µ h (s ′ )ϕ ⊤ h (with the same argument) for µ h (s ′ ) = { i,j,k∈[d] U h (i, j, k)V h (s ′ , i)B(j, l, m)C(k, x, n)} l,x∈[d],m,n∈[M ]. It follows that we can express r h = Fh Σh G⊤ h where Fh be the S × d 2 M 2 matrix from joining all F m,h dM times, Gh be the A × d 2 M 2 matrix from joining all G m,h dM times, and Σh is the diagonal matrix with entries θ h (j, l, m, n) for all j, l ∈ [d], m, n ∈ [M ]. Note that the entries of Σh and µ h are at most dα 2 larger than their original value.Let Fh be the S × d 2 M 2 matrix from joining all Fm,h R m,h,f dM times, and Ĝh be the A × d 2 M 2 matrix from joining all Ḡm,h R m,h,g dM times. Let θh satisfyθh φ⊤ h = Fh Σh Ĝ⊤ h . Therefore, it follows for all (s ′ , s, a, h) ∈ S × S × A × [H], |r h (s, a) -θh φ⊤ h (s, a)| = | Fh Σh G⊤ h (s, a) -Fh Σh Ĝ⊤ h (s, a)| ≤ | Fh Σh G⊤ h (s, a) -Fh Σh G⊤ h (s, a)| + | Fh Σh G⊤ h (s, a) -Fh Σh Ĝ⊤ h (s, a)| ≤ dM m∈M ∥F m,h (s) -Fm,h (s)R m,h,f ∥ 2 ∥ Σh ∥ op max m∈M √ d∥G m,h ∥ ∞ + √ d max m∈M ∥ Fm,h ∥ ∞ ∥ Σh ∥ op ∥G m,h (a) -Ĝm,h (s)R m,h,g ∥ 2 ≤ d 3/2 M m∈M ∥F m,h (s) -Fm,h (s)R m,h,f ∥ 2 ∥ Σh ∥ op max m∈M ∥G m,h ∥ ∞ + max m∈M (∥F m,h ∥ + ∥F m,h R -Fm,h ∥ ∞ )∥ Σh ∥ op ∥G m,h (a) -Ĝm,h (s)R m,h,g ∥ 2 ≤ Cd 3 M √ S √ µ m∈M ∥F m,h (s) -Fm,h (s)R m,h,f ∥ 2 ≤ C dM √ H √ T ,where the second inequality comes from the triangle inequality and Cauchy-Schwarz inequality, the third inequality comes from the triangle inequality, and the fourth inequality comes from the definition of incoherence, our bound on the entries of Σ and the left term dominating the right term, and the final inequality is due to our singular vector perturbation bounds. Similarly,∥P h (•|s, a) -μh (s ′ ) φh (s, a) ⊤ ∥ T V ≤ C dM √ H √ Tfor some absolute constant C > 0 where μh (s ′ ) satisfies Fh Σh (s ′ ) Ĝ⊤ h and Σh (s ′ ) is the d 2 M 2 × d 2 M 2 diagonal matrix with entries µ h (s ′ , l, k, m, n) with the same argument using the regularity condition on µ h . Therefore, φ satisfies Assumption B in [17] with ξ = O(dM H/T ). Running LSVI-UCB with φ admits a regret bound ofRegret(T ) ≤ C √ d 6 M 6 H 3 T ι 2 + d 3 M 3 H 3/2 T √ ι √ T ∈ Õ d 6 M 6 H 3 Tfor some absolute constant C > 0 with probability at least 1 -δ from a final union bound. The sample complexity in the source phase isÕ d 10 µ 5 κ 4 (S + A)M H 4 α 4 T .which completes the proof.I ℓ ∞ eigen perturbation bound with non-uniform noise: rank-r caseSuppose A = A * + D ∈ R m×n, where A * is the true rank-r matrix and D is the noise matrix. Suppose A * has SVD A * = U * Σ * V * ⊤ , where U * ∈ m×r , V * ∈ n×r are orthonormal matrices containing the left and right singular vectors, respectively, and Σ * = diag(σ * 1 , . . . , σ * r ) is a diagonal matrix of the singular values. Similarly, suppose A has SVD A = U ΣV ⊤ + U ′ Σ ′ V ′⊤ , where U ∈ m×r , V ∈ n×r and Σ = diag(σ 1 , . . . , σ r ) correspond to the top-r singular vectors/values, and U ′ ∈ m×(m-r) , V ′ ∈ m×(n-r) and Σ ∈ (m-r)×(n-r) correspond to the bottom singular vectors/values.The following proposition is a generalization of the perturbation bound in [12] to the setting with non-uniform noise.Proposition 2. Suppose γ := ∥D∥ op σ * r < 1 2 .There exist two orthonormal matrices R,R ∈ r×r such thatU -U * R i• 2 ≤ ∥U * i• ∥ 2 • 8γ + ∥D i• ∥ 2 • 1 σ * r (1 -γ) , ∀i ∈ [m], (V -V * R) j• 2 ≤ V * j• 2 • 8γ + ∥D •j ∥ 2 • 1 σ * r (1 -γ) , ∀j ∈ [n].To prove Proposition 2, we need some notations. Let H := U ⊤ U * ∈ r×r and its SVD beH = AΛB ⊤ ,where A, B ∈ r×r are orthonormal, and Λ = diag(σ 1 , . . . , σ r ) ∈ r×r is a diagonal matrix. Similarly, let H := V ⊤ V * ∈ r×r and its SVD be H = AΛB ⊤ . Finally, define the orthonormal matrices sgn(H) := AB ⊤ and sgn(H) := AB ⊤ . (The function sgn(•) is called the matrix sign function.)We need a technical lemma, which generalizes [2, Lemma 3] to the asymmetric case.Lemma 3 (Properties of matrix sign function). We have H op ≤ 1 and ∥H∥ op ≤ 1. WhenEQUATIONH -1 op ≤ (1 -γ) 2 (1 -2γ) , H -1 op ≤ (1 -γ) 2 (1 -2γ) .Proof. We prove the bounds for H. The proof for H is identical. Clearly H op ≤ ∥U ∥ op ∥U * ∥ op = 1.* i -σ i | ≤ ∥D∥ op , ∀i ∈ [m], hence σ * r -σ r+1 ≥ σ * r -∥D∥ op = (1 -γ)σ * r > 1 2 σ * r > 0by assumption. On the other hand, by standard perturbation theory,1 ≥ σ 1 ≥ • • • ≥ σ r ≥ 0 are the cosines of the principal angles 0 ≤ θ 1 ≤ • • • ≤ θ r ≤ π/2between the column spaces of U and U * , and sin θ r = U U ⊤ -U * U * ⊤ op . Hence sgn(H) -H op = 1 -cos θ r . By Wedin's sin Θ Theorem, we havesin θ r ≤ max ∥U * D∥ op , ∥DV * ∥ op σ * r -σ r+1 ≤ max ∥U * D∥ op , ∥DV * ∥ op (1 -γ)σ * r .Since cos θ r ≥ cos 2 θ r = 1 -sin 2 θ r , we obtainsgn(H) -H op = 1 -cos θ r ≤ sin θ r ≤ max ∥U * D∥ op , ∥DV * ∥ op (1 -γ)σ * r ≤ ∥D∥ op (1 -γ)σ * r = γ 1 -γ .Note thatEQUATIONHenceΣH -HΣ op ≤ ΣH -HΣ * op + H(Σ * -Σ) op = U ⊤ DV * op + H(Σ * -Σ) op ≤ ∥D∥ op + H op ∥Σ * -Σ∥ op ≤ 2 ∥D∥ op ,where we use H op ≤ 1 and ∥Σ * -Σ∥ op ≤ ∥D∥ op . Similarly,U * ⊤ DV = U * ⊤ (A -A * ) V = U * ⊤ U Σ -Σ * V * ⊤ V ⊤ = H ⊤ Σ -Σ * H ⊤ ,so a similar argument as above givesH ⊤ Σ -ΣH ⊤ op ≤ 2 ∥D∥ op .Finally, recall that H -sgn(H) op ≤ γ 1-γ 2 and note the simple identityX -1 -Y -1 = X -1 (Y -X)Y -1 . It follows that H -1 -sgn(H) -1 op ≤ H -1 op H -sgn(H) op sgn(H) -1 op = σ r sgn(H) + (H -sgn(H) -1 H -sgn(H) op ≤ 1 1 -γ 1-γ 2 • γ 1 -γ 2 = γ 2 1 -2γ .It follows thatH -1 op ≤ sgn(H) -1 op + H -1 -sgn(H) -1 op ≤ 1 + γ 2 1 -2γ = (1 -γ) 2 1 -2γ .This completes the proof of Lemma 3.We are now ready to prove Proposition 2. We haveU -U * sgn(H) ⊤ = AV Σ -1 -U * sgn(H) ⊤ A = U ΣV ⊤ = (A * + D)V Σ -1 -U * sgn(H) ⊤ = U * Σ * V * ⊤ V Σ -1 -U * sgn(H) ⊤ + DV Σ -1 A * = U * Σ * V * ⊤ = U * Σ * H ⊤ Σ -1 -U * sgn(H) ⊤ + DV Σ -1 . H = V ⊤ V * But Σ * H ⊤ = (Σ + Σ * -Σ)H ⊤ = H ⊤ Σ + ΣH ⊤ -H ⊤ Σ + (Σ * -Σ) H ⊤ . Hence U -U * sgn(H) ⊤ = U * H ⊤ Σ + ΣH ⊤ -H ⊤ Σ + (Σ * -Σ) H ⊤ Σ -1 -U * sgn(H) ⊤ + DV Σ -1 = U * H ⊤ + U * ΣH ⊤ -H ⊤ Σ Σ -1 + U * (Σ * -Σ) H ⊤ Σ -1 -U * sgn(H) ⊤ + DV Σ -1 = U * H -sgn(H) ⊤ + U * ΣH ⊤ -H ⊤ Σ Σ -1 + U * (Σ * -Σ) H ⊤ Σ -1 + DV Σ -1 .For each i ∈ [m], we can bound the i-th row of U -U * sgn(H) ⊤ asU -U * sgn(H) ⊤ i• 2 ≤ ∥U * i• ∥ 2 H -sgn(H) op + ΣH ⊤ -H ⊤ Σ op Σ -1 op + ∥Σ * -Σ∥ op ∥H∥ op Σ -1 op + ∥D i• ∥ 2 ∥V ∥ op Σ -1 op (i) ≤ ∥U * i• ∥ 2 γ 1 -γ 2 + 2 ∥D∥ op • 1 σ * r (1 -γ) + ∥D∥ op • 1 • 1 σ * r (1 -γ) + ∥D i• ∥ 2 • 1 σ * r (1 -γ) = ∥U * i• ∥ 2 γ 1 -γ 2 + 3γ 1 -γ + ∥D i• ∥ 2 • 1 σ * r (1 -γ) (ii) ≤ ∥U * i• ∥ 2 • 8γ + ∥D i• ∥ 2 • 1 σ * r (1 -γ),where step (i) follows from Lemma 3 and the boundEQUATION, and step (ii) holds since γ ≤ 1 2 . Setting R = sgn(H) ⊤ proves the first inequality in Proposition 2. The second inequality in Proposition 2 can be established by a similar argument. Corollary 3. Suppose the setting of Proposition 2 holds. Furthermore, assume that A * is µincoherent with condition number κ and ∥A * ∥ ∞ ≥ C for some constant C > 0. Then, there exist two orthonormal matrices R,R ∈ r×r such thatU -U * R i• 2 ≤ 16κ(µd) 3/2 ∥D∥ ∞ C √ m , ∀i ∈ [m], (V -V * R) j• 2 ≤ 16κ(µd) 3/2 ∥D∥ ∞ C √ n , ∀j ∈ [n].Proof. From the definition of the ℓ ∞ norm, there exists(i, j) ∈ [m] × [m] such that ∥A * ∥ ∞ = |A i,j |.Then, it follows that∥A * ∥ ∞ = |A i,j | = |(U * Σ * V * ⊤ ) i,j | ≤ ∥Σ * ∥ op ∥U * i ∥ 2 ∥V * j ∥ 2 ≤ σ 1 µd √ mn ≤ κσ d µd √ mn .Furthermore, we note that ∥D∥ op ≤ ∥D∥ ∞ √ mn. Thus, the result follows from Proposition 2 and using the definition of incoherence and the above inequalities.In this section, we present the proofs of Theorem 8 and 9 and the related lemmas. The proofs, theorems, and lemmas are modifications of the analogous result/proof in [17] tailored to our Tucker rank settings.To prove Theorem 8, we first introduce notation used throughout this section and then present auxiliary lemmas. We reiterate that the steps and analysis in this subsection are essentially the same as the proofs in [17] , except we have A copies of the weight vectors and gram matrices. We let Λ a h,k , w a h,k , Q k h , V k h , π k as the parameters/estimates at episode k. Furthermore, let V k h = max a∈A Q k h (s, a) and π k be the greedy policy w.r.t. Q k h . We let F k h := F h (s k h ). To prove the desired regret bound, we first need to prove that PV -P V concentrates about 0, which differs from typical concentration inequalities for self normalized processes due to the value function not being constant. Thus, we first bound the log of the covering number of our function class for the value function to control the error of our algorithm's estimate. Lemma 4. Let V denote a function class of mappings from S to R with the following parametric formV (•) = min max a∈A w ⊤ a F (•) + β F (•) ⊤ Λ -1 a F (•), Hwhere the parameters w a , β, Λ a satisfy ∥w a ∥ ≤ L for all a ∈ A, β ∈ [0, B], and the minimum eigenvalue of Λ a is greater than λ. Assume that ∥F (s)∥ ≤ 1 for all s ∈ S, and let N ϵ be the ϵ-covering number of V with respect to the distance dist(V,V ′ ) = sup s |V (s) -V ′ (s)|. Then, log(N ϵ ) ≤ d log(1 + 4L/ϵ) + d 2 log(1 + 8d 1/2 B 2 /(λϵ 2 ))Proof. Equivalently, we reparameterize the function class byD a = β 2 Λ -1 a , V (•) = min max a∈A w ⊤ a F (•) + F (•) ⊤ D a F (•), Hwhere ∥w a ∥ ≤ L and ∥D a ∥ ≤ B 2 /λ for all a ∈ A. For any V 1 , V 2 ∈ V, let them take the form in the above equation with parameters (w a , D a ) and (w ′ a , D ′ a ). Since min(•, H) and max a∈A are contraction maps,dist(V 1 -V 2 ) ≤ sup s,a |(w ⊤ a F (s) + F (s) ⊤ D a F (s)) -(w ′⊤ a F (s) + F (s) ⊤ D ′ a F (s))| ≤ sup a,F :∥F ∥≤1 |(w ⊤ a F + F ⊤ D a F ) -(w ′⊤ a F + F ⊤ D ′ a F )| ≤ max a∈A sup F :∥F ∥≤1 |(w a -w ′ a ) ⊤ F | + sup F :∥F ∥≤1 | F ⊤ (D a -D ′ a )F | ≤ max a∈A ∥w a -w ′ a ∥ + ∥D a -D ′ a ∥ ≤ max a∈A ∥w a -w ′ a ∥ + ∥D a -D ′ a ∥ Fwhere the holds because | √ x -√ y| ≤ |x -y| for any x, y ≥ 0. Let C w be an ϵ/2-cover of {w ∈ R d |∥w∥ ≤ L} with respect to the 2-norm, and C D be anϵ 2 /4-cover of {D ∈ R d×d |∥D∥ F ≤ d 1/2 B 2 /λ} with respect to the Frobenius norm. By Lemma D.5 from [17] , we know that,|C w | ≤ (1 + 4L/ϵ) d , |C D | ≤ (1 + 8d 1/2 B 2 /(λϵ 2 )) d 2 .Hence, for any V 1 , there exists a w ′ a ∈ C w andD ′ a ∈ C D for all a ∈ A such that V 2 parameterized by (w ′ a , D ′ a ) satisfies dist(V 1 , V 2 ) ≤ ϵ. Hence, N ϵ ≤ |C w ||C D |, which gives: log(N ϵ ) ≤ log(|C w |) + log(|C D |) ≤ d log(1 + 4ϵL/ϵ) + d 2 log(1 + 8d 1/2 B 2 /(λϵ 2 )).We next bound the ℓ 2 -norm of the weight vector of any policy. Lemma 5. Let {w a h } be the weight vector of some policy π, i.e., Q π h (s, a) = F h (s) ⊤ w a h . Then,∥w a h ∥ ≤ 2H √ d. Proof. Note that Q π h (s, a) = r h (s, a) + s ′ V π h+1 (s ′ )P h (s ′ |s, a), so, using the low-rank representations of r h , P h , it follows that∥w a h ∥ 2 = ∥W h (a, •)+ s ′ V π (s ′ )U h (s ′ , a, •)∥ 2 ≤ ∥W h (a, •)∥ 2 +∥ s ′ V π (s ′ )U h (s ′ , a, •)∥ 2 ≤ √ d+H √ d.Recall that since the feature mapping was scaled up (F h = S dµ F ′ ) to ensure the max entries of F and W, U are on the same scale, it follows that ∥W h (a)∥ 2 ≤ 1 and∥ s ′ ∈S V π h+1 (s ′ )U h (s ′ , a)∥ 2 ≤ H. Therefore, it follows that ∥w a h ∥ 2 ≤ 2H √ d.We next bound the 2-norm of the weight vector from the algorithm. Lemma 6. For any k, h, a, the weight vector from the above algorithm satisfies ∥w a h,k ∥ ≤ 2H dk/λ.F h (s) = f , we have for any a ∈ A |f ⊤ w a h,k | = |f ⊤ (Λ a h ) -1 t∈T a h,k-1 F h (s t h ) r h (s t h , a) + max a ′ ∈A Q h+1 (s t h+1 , a ′ ) | ≤ | t∈T a h,k-1 f ⊤ (Λ a h ) -1 F h (s t h )|2H ≤ 2H ( t∈T a h,k-1 f ⊤ (Λ a h ) -1 f ⊤ )( t∈T a h,k-1 F h (s t h ) ⊤ (Λ a h ) -1 F h (s t h )) ≤ 2H∥f ∥ 2 d|T a h,k-1 |/λ ≤ 2H dk/λ, where the second to last inequality is due to Lemma D.1 from [17] and that Rayleigh quotients are upper bounded by the largest eigenvalue of the matrix (Theorem 4.2.2 from [14] ). The last inequality is due to∥F h (s)∥ 2 ≤ 1 and |T a h,k-1 | ≤ k.The above two lemmas are necessary in ensuring that the estimation error is small as they depend multiplicatively on the norm of the weight vectors. We next prove the main concentration lemma that controls the estimate. Lemma 7. Let c ′ be the constant in the definition of β a k,h = c ′ dH √ ι. Then, there exists a constant C > 0 that is independent of c ′ such that for any δ ∈ (0, 1), if we let the event X be∀(a, k, h) ∈ A×[K]×[H] : t∈T a h,k-1 F h (s t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s t h , a) (Λ a h,t ) -1 ≤ CdH √ χ where χ = log(2(c ′ + 1)dT A/δ), then P(X ) ≥ 1 -δ/2.Proof. From Lemma 6, we have ∥w a h,k ∥ 2 ≤ 2H dk/λ. By construction, the minimum eigenvalue of Λ a h,t is lower bounded by λ. Then, from Lemma D.4 in [17] (with δ ′ = δ/A), Lemma 4, and taking a union bound over actions, we have that with probability at least 1 -δ ′ /2, for all a ∈ A and ϵ > 0,t∈T a h,k-1 F h (s t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s t h , a)) 2 (Λ a h,t ) -1 ≤ 4H 2 d 2 log((k + λ)/λ)) + log(2AN ϵ /δ) +8k 2 ϵ 2 /λ.Then, from Lemma 4, it follows that with probability at least 1 -δ ′ /2, for all a ∈ A and ϵ > 0,t∈T a h,k-1 F h (s t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s t h , a) 2 (Λ a h,t ) -1 ≤ 4H 2 d 2 log((k + λ)/λ)) + log(2A/δ) + d log(1 + 4L/ϵ) + d 2 log(1 + 8d 1/2 β 2 /(λϵ 2 )) + 8k 2 ϵ 2 /λ.Choosing λ = 1, β a k,h = CdHι, ϵ = dH/k gives that there exists some constant C ′ such thatt∈T a h,k-1 F h (s t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s t h , a) 2 (Λ a h,t ) -1 ≤ C ′ d 2 H 2 log(2(c β + 1)dT A/δ).We next recursively bound the difference between the value function maintained in the algorithm and the true value function of any policy π. We upperbound this with their expected difference and an additional error term, which is bounded with high probability. Lemma 8. There exists a constant c β such that β a k,h = c β dH √ ι where ι = log(2dAT /p) and for any fixed policy π, on the event X defined in Lemma 7, we have for all (s, a, h, k)∈ S × A × [H] × [K]: F h (s) ⊤ w a h,k -Q π h (s, a) = P h (V k h+1 -V π h+1 )(s, a) + ∆ k h (s, a),where|∆ k h (s, a)| ≤ β a k,h F h (s) ⊤ (Λ a h,k ) -1 F h (s).Proof. From our low-rank assumption, it follows thatQ π h (s, a) = F h (s) ⊤ w a h = (r h + P h V π h+1)(s, a), which following the steps from the proof of Lemma B.4 in [17] givesw a h,k -w a,π h = -λ(Λ a h,k ) -1 w a,π h + (Λ a h,k ) -1 t∈T a k-1,h F h (s t h )(V k h+1 (s t h+1 ) -P h V k h+1 (s t h , a) + (Λ a h,k ) -1 ) t∈T a k-1,h F h (s t h )P h (V k h+1 -V π h+1 )(s t h , a)Now, we bound each term (q a 1 , q a 2 , q a 3 ) individually, for the first term, note for all a ∈ A|F h (s) ⊤ q a 1 | = |λF h (s) ⊤ (Λ a h,k ) -1 w a,π h | ≤ √ λ∥w a,π h ∥ F h (s) ⊤ (Λ a h,k ) -1 F h (s)For the second term, given the event X , we have from Cauchy Schwarz|F h (s) ⊤ q a 2 | ≤ CdH √ χ F h (s) ⊤ (Λ a h,k ) -1 F h (s)where χ = log(2(c β + 1)dT A/p). For the third term,F h (s) ⊤ q a 3 = F h (s) ⊤   (Λ a h,k ) -1 ) t∈T a k-1,h F h (s t h )P h (V k h+1 -V π h+1 )(s t h , a)   = F h (s) ⊤   (Λ a h,k ) -1 ) t∈T a k-1,h F h (s t h )F h (s t h ) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a)   = F h (s) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a) -λF h (s) ⊤ (Λ a h,k ) -1 ) s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a)We note thatF h (s) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a) = P h (V k h+1 -V π h+1 )(s, a)and|λF h (s) ⊤ (Λ a h,k ) -1 ) s ′ ∈S (V k h+1 -V k h+1 )(s ′ )U h (s ′ , a) | ≤ 2H √ dλ F h (s) ⊤ (Λ a h,k ) -1 F h (s) Since |F h (s) ⊤ w a h,k -Q π h (s, a)| = F h (s) ⊤ (w a h,k -w a,π h ) = F h (s) ⊤ (q a 1 + q a 2 + q a 3 ), it follows that |F h (s) ⊤ w a h,k -Q π h (s, a) -P h (V k h+1 -V π h+1 )(s, a)| ≤ C"dH √ χ F h (s) ⊤ (Λ a h,k ) -1 F h (s).Similarly as in [17] , we choose c β that satisfies C" log(2) + log(c β + 1) ≤ c β log(2).This lemma implies that by adding the appropriate bonus, Q k h is always an upperbound of Q * h with high probability, i.e., achieving optimism. Lemma 9. On the event X defined in lemma 7, we haveQ k h (s, a) ≥ Q * h (s, a) for all (s, a, h, k) ∈ S × A × [H] × [K].Proof. We prove this with induction. The base case holds because at step H + 1, the value function is zero, so from Lemma 8,|F H (s) ⊤ w a H,k -Q * H (s, a)| ≤ β a k,h F H (s) ⊤ (Λ a H,k ) -1 )F H (s)and thus,Q * H (s, a) ≤ min H, F H (s) ⊤ w a H,k + β a k,h F H (s) ⊤ (Λ a H,k ) -1 )F H (s) = Q k H (s, a).From the inductive hypothesis (assuming thatQ k h+1 (s, a) ≥ Q * h+1 (s, a)), it follows that P h (V k h+1 - V * h+1 )(s, a) ≥ 0. From Lemma 8, F h (s) ⊤ w a h,k -Q * h (s, a) ≤ β a k,h F h (s) ⊤ (Λ a h,k ) -1 )F h (s). It follows that Q * h (s, a) ≤ min H, F h (s) ⊤ w a h,k + β a k,h F h (s) ⊤ (Λ a h,k ) -1 )F h (s) = Q k h (s, a).We next show that Lemma 8 transforms to the recursive formulaδ k h = V k h (s k h ) -V π k h (s k h ), which is used in proving our regret bound. Lemma 10. Let δ k h = V k h (s k h ) -V π k h (s k h ) and ξ k h+1 = E[δ k h+1 |s k h , a k h ] -δ k h+1 .Then, on the event X defined in Lemma 7, we have for any (h, k):δ k h ≤ δ k h+1 + ξ k h+1 + β a k,h F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )Proof. From Lemma 8, we have for any (s, a, h, k) thatQ k h (s, a) -Q π k h (s, a) ≤ P h (V k h+1 -V π k h+1 )(s, a) + β a k,h F h (s) ⊤ (Λ a h,k ) -1 F h (s).From the definition of V π k , we haveδ k h = Q k h (s k h , a k h ) -Q π k h (s k h , a k h ).Finally, we prove the main theorem, Theorem 8, which asserts that the regret bound of our algorithm is efficient with respect to A and T .Proof. Suppose that the Assumptions required in Theorem 8 hold. We condition on the event X from Lemma 7 with p = δ/2 and use the notation for δ k h , ξ k h as in Lemma 10. From Lemmas 9 and 10, we haveRegret(K) = K k=1 (V * 1 (s k 1 )-V π k 1 (s k 1 )) ≤ K k=1 δ k 1 ≤ k∈[K] h∈[H] ξ k h +β a k,h k∈[K] h∈[H] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )Since the observations at episode k are independent of the computed value function (this uses the trajectories from episodes 1 to k -1, it follows {ξ k h } is a martingale difference sequence with |ξ k h | ≤ 2H for all (k, h). Thus, from the Azuma Hoeffding inequality, we havek∈[K],h∈H ξ k h ≤ 2T H 2 log(2/p) ≤ 2H √ T ιwith probability at least 1 -δ/2. For the second term, we note that the minimum eigenvalue of Λa k h h,kis at least one by construction and ∥F h (s)∥ ≤ 1. From the Elliptical Potential Lemma (Lemma D.2 [17] ), we have for all a ∈ A and h ∈ [H],K k=1 F h (s k ) ⊤ (Λ a h,k ) -1 F h (s k ) ≤ 2 log(det(Λ a h,k+1 )/det(Λ a h,0 )) Furthermore, we have ∥Λ a h,k+1 ∥ = ∥ t∈T a K,h F h (s t h )F h (s t h ) ⊤ + λI∥ ≤ λ + |T a K,h | ≤ λ + K. It follows that K k=1 F h (s k ) ⊤ (Λ a h,k ) -1 F h (s k ) ≤ 2d log(1 + K/λ) ≤ 2dιNext, by Cauchy-Schwarz and grouping the regret by each action, it follows thatk∈[K] h∈[H] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) ≤ h∈[H] √ K   k∈[K] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )   1/2 = h∈[H] √ K   a∈A t∈T a K,h F h (s t h ) ⊤ (Λ a h,t ) -1 F h (s t h )   1/2 ≤ h∈[H] √ K a∈A 2dι 1/2 ≤ H √ 2KAdι.Since β a k,h = cdH √ ι for some constant c, from a union bound and the previous bounds, it follows thatRegret(K) ≤ 2H √ T ι + β a k,h H √ 2KAdι ∈ Õ( √ d 3 H 3 AT ).with probability at least 1 -δ.To use LSVI-UCB-(S, d, A) in our transfer RL setting, we next show that it is robust to misspecification error. Similarly, we first prove the helper lemmas needed in the misspecified setting and follow the proof structure and techniques used in [17] .Lemma 11. For a ξ-approximate (S, d, A) Tucker rank MDP (Assumption 7), then for any policy π there exists corresponding weight vectors {w a h } wherew a h = W h (a) + s ′ ∈S V π h+1 (s ′ )U h (s ′ , a) such that for all (s, a) ∈ S × A |Q π h (s, a) -F h (s)w a⊤ h | ≤ 3Hξ.Proof. Note that Q π h (s, a) = r h (s, a) + s ′ V π h+1 (s ′ )P h (s ′ |s, a), so, using the low-rank representations of r h , P h , it follows that|Q π h (s, a) -F h (s)w a⊤ h | ≤ |r h (s, a) -F h (s)W h (a) ⊤ | + s ′ V π h+1 (s ′ )P h (s ′ |s, a) -F h (s) s ′ ∈S V π h+1 (s ′ )U h (s ′ , a) ≤ ξ + 2Hξ ≤ 3HξLemma 12. Suppose Assumption 7 holds. Let {w a h } be the weight vector of some policy π, i.e.,Q π h (s, a) = F h (s) ⊤ w a h . Then, ∥w a h ∥ ≤ 2Hd. Proof. Recall that w a h = W h (a) + s ′ ∈S V π h+1 (s ′ )U h (s ′ , a). Since the feature mapping was scaled up (F h = S dµ F ′ ) to ensure the max entries of F and W, U are on the same scale, it follows that ∥W h (a)∥ 2 ≤ 1 and∥ s ′ ∈S V π h+1 (s ′ )U h (s ′ , a)∥ 2 ≤ H. Thus, ∥w a h ∥ 2 ≤ 2Hd.Similarly, we bound the stochastic noise but account for the misspecification error. Lemma 13. Suppose Assumption 7 holds. Let c ′ m be the constant in the definition ofβ a k,h = c ′ m H(d √ ι + ξ |T a k,h |d).Then, there exists a constant C > 0 that is independent of c ′ m such that for any δ ∈ (0, 1), if we let the event X be∀(a, k, h) ∈ A×[K]×[H] : t∈T a h,k-1 F h (s t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s t h , a) (Λ a h,t ) -1 ≤ CdH √ χwhere χ = log(2(c ′ m + 1)dT A/δ), then P(X ) ≥ 1 -δ/2.Proof. The proof is the same as the proof of Lemma 7 except we increase β a k,h to account for the misspecifiction error. Since ξ ≤ 1 by assumption, the modification to β a k,h only affects C.We next account for the noise being adversarial due to the misspecification error. Lemma 14. Let {ϵ t } be any sequence such that |ϵ τ | ≤ B for any t. Then, for any(h, k, a) ∈ [H] × [K] × A and F ∈ R d , we have |F ⊤ (Λ a k,h ) -1 t∈T a k-1,h F h (s t h )ϵ t | ≤ B d|T a k-1,h |F ⊤ (Λ a k,h ) -1 F .Proof. From the Cauchy-Schwarz inequality and Elliptical Potential Lemma (Lemma D.1 [17] ), we have|F ⊤ (Λ a k,h ) -1 t∈T a k-1,h F h (s t h )ϵ t | ≤ B   t∈T a k-1,h F ⊤ (Λ a k,h ) -1 F     t∈T a k-1,h F h (s t h ) ⊤ (Λ a k,h ) -1 F h (s t h )   ≤ B d|T a k-1,h |F ⊤ (Λ a k,h ) -1 F .Next, we bound the error between a policies Q function and our low-rank estimate.Lemma 15. There exists a constant c ′ m such thatβ a k,h = c ′ m H(d √ ι + ξ |T a k,h |d)where ι = log(2dAT /p) and for any fixed policy π, on the event X defined in Lemma 13, we have for all (s, a, h, k) ∈ S × A × [H] × [K]:F h (s) ⊤ w a h,k -Q π h (s, a) = P h (V k h+1 -V π h+1 )(s, a) + ∆ k h (s, a),where|∆ k h (s, a)| ≤ β a k,h F h (s) ⊤ (Λ a h,k ) -1 F h (s) + 4Hξ.Proof. From Lemma 12, it follows that there exists a weight vector w a h = W h (a) + s ′ ∈S V π h+1 (s ′ )U h (s ′ , a), such that for all (s, a)∈ S × A, |Q π h (s, a) -F h (s) ⊤ w a h | ≤ 2Hξ. Let P (•|s, a) = F h (s) ⊤ U h (•, a), so we have for any (s, a) ∈ S × A, F h (s) ⊤ w a h = F h (s) ⊤ W h (a) + P V π h+1 (s, a). Therefore, w a h,k -w a,π h = -λ(Λ a h,k ) -1 w a,π h + (Λ a h,k ) -1 t∈T a k-1,h F h (s t h )(V k h+1 (s t h+1 ) -P h V k h+1 (s t h , a) + (Λ a h,k ) -1 t∈T a k-1,h F h (s t h ) Ph (V k h+1 -V π h+1 )(s t h , a) + (Λ a h,k ) -1 t∈T a k-1,h F h (s t h ) r h (s t h , a) -F h (s t h )W h (a) + (P h -Ph )V k h+1 (s t h , a)Now, we bound each of the four terms above (q a 1 , q a 2 , q a 3 , q a 4 ) individually, for the first term, note for all a ∈ A|F h (s) ⊤ q a 1 | = |λF h (s) ⊤ (Λ a h,k ) -1 w a,π h | ≤ √ λ∥w a,π h ∥ F h (s) ⊤ (Λ a h,k ) -1 F h (s)For the second term, given the event X , we have from Cauchy Schwarz|F h (s) ⊤ q a 2 | ≤ CdH √ χ F h (s) ⊤ (Λ a h,k ) -1 F h (s)where χ = log(2(c β + 1)dT A/p). For the third term,F h (s) ⊤ q a 3 = F h (s) ⊤   (Λ a h,k ) -1 t∈T a k-1,h F h (s t h ) Ph (V k h+1 -V π h+1 )(s t h , a)   = F h (s) ⊤   (Λ a h,k ) -1 t∈T a k-1,h F h (s t h )F h (s t h ) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a)   = F h (s) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a) -λF h (s) ⊤ (Λ a h,k ) -1 s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a) ,and note thatF h (s) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , a) = Ph (V k h+1 -V π h+1 )(s, a)and|λF h (s) ⊤ (Λ a h,k ) -1 s ′ ∈S (V k h+1 -V k h+1 )(s ′ )U h (s ′ , a) | ≤ 2H √ dλ F h (s) ⊤ (Λ a h,k ) -1 F h (s). Since ∥ Ph (•|s, a) -P h (•|s, a)∥ ∞ ≤ 1 for all (s, a) ∈ S × A, it follows that | Ph (V k h+1 -V π h+1 )(s, a) -P h (V k h+1 -V π h+1 )(s, a)| ≤ |( Ph -P h )(V k h+1 -V π h+1 )(s, a)| ≤ 2Hξ.From Lemma 14, we have |F h (s),q a 4 | ≤ 2Hξ d|T a k,h |F h (s) ⊤ (Λ -1 h,k ) -1 F h (s). Since |F h (s) ⊤ w a h,k -Q π h (s, a)| = F h (s) ⊤ (w a h,k -w a,π h ) = F h (s) ⊤ (q a 1 + q a 2 + q a 3 + q a 4 ), it follows that |F h (s) ⊤ w a h,k -Q π h (s, a)-P h (V k h+1 -V π h+1 )(s, a)| ≤ √ χ(C"d √ χ+2ξ |T a k,h |d)H F h (s) ⊤ (Λ a h,k ) -1 F h (s)+4Hξ.Similarly as in [17] , we choose c β that satisfies C" log(2) + log(c β + 1) ≤ c β log (2) .Now, we prove that Q k h is an upperbound of Q * h conditioned on the event in Lemma 13. Lemma 16. Suppose Assumption 7 holds. On the event X defined in lemma 13, we haveQ k h (s, a) ≥ Q * h (s, a) -4H(H + 1 -h)ξ for all (s, a, h, k) ∈ S × A × [H] × [K].Proof. We prove this with induction. The base case holds because at step H + 1, the value function is zero, so from Lemma 15,|F H (s) ⊤ w a H,k -Q * H (s, a)| ≤ β a k,h F H (s) ⊤ (Λ a H,k ) -1 )F H (s) + 4Hξand thus,Q * H (s, a) -4Hξ ≤ min H, F H (s) ⊤ w a H,k + β a k,h F H (s) ⊤ (Λ a H,k ) -1 )F H (s) = Q k H (s, a).From the inductive hypothesis (assuming thatQ k h+1 (s, a) ≥ Q * h+1 (s, a) -4H(H -h)ξ), it follows that P h (V k h+1 -V * h+1 )(s, a) ≥ -4ξ. From Lemma 15, F h (s) ⊤ w a h,k -Q * h (s, a) ≤ β a k,h F h (s) ⊤ (Λ a h,k ) -1 )F h (s) + 4Hξ. It follows that Q * h (s, a)-4H(H-h+1)ξ ≤ min H, F h (s) ⊤ w a h,k + β a k,h F h (s) ⊤ (Λ a h,k ) -1 )F h (s) = Q k h (s, a).This completes the proof.Similarly, to the regular case, the gap in the misspecified setting has a recursive formula.Lemma 17. Let δ k h = V k h (s k h ) -V π k h (s k h ) and ξ k h+1 = E[δ k h+1 |s k h , a k h ] -δ k h+1 .Then, on the event X defined in Lemma 13, we have for any (h, k):δ k h ≤ δ k h+1 + ξ k h+1 + β a k,h F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) + 4HξProof. From Lemma 15, we have for any (s, a, h, k) thatQ k h (s, a) -Q π k h (s, a) ≤ P h (V k h+1 -V π k h+1 )(s, a) + β a k,h F h (s) ⊤ (Λ a h,k ) -1 F h (s) + 4Hξ.From the definition of V π k , we haveδ k h = Q k h (s k h , a k h ) -Q π k h (s k h , a k h ),and substituting this into the first equation finishes the proof.Finally, we prove the main result in the misspecified setting Theorem 9.Proof. Suppose that the Assumptions required in Theorem 9 hold. We condition on the event X from Lemma 13 with p = δ/2 and use the notation for δ k h , ξ k h as in Lemma 17. From Lemma 16, we haveQ k 1 (s, a) ≥ Q * 1 (s, a) -4H 2 ξ, which implies V * 1 (s) -V π k 1 (s) ≤ δ k 1 + 4H 2 ξ.Thus, from Lemma 15, on the event X , it follows thatRegret(K) = K k=1 (V * 1 (s k 1 ) -V π k 1 (s k 1 )) ≤ K k=1 δ k 1 + 4H 2 ξ ≤ k∈[K] h∈[H] ξ k h + k∈[K] β a k,h h∈[H] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) + 4HT ξsince HK = T . Since the observations at episode k are independent of the computed value function (this uses the trajectories from episodes 1 to k -1, it follows {ξ k h } is a martingale difference sequence with |ξ k h | ≤ 2H for all (k, h). Thus, from the Azuma Hoeffding inequality, we havek∈[K],h∈H ξ k h ≤ 2T H 2 log(2/p) ≤ 2H √ T ιwith probability at least 1 -δ/2. By construction of β a k,h , we havek∈[K] β a k,h F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) ≤ CH( k∈[K] d √ ι F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) + k∈[K] ξ |T a k,h |d F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )).From the Cauchy-Schwarz inequality, it follows thatk∈[K] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) ≤ √ K   k∈[K] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )   .Since the minimum eigenvalue of Λ a k h h,k is at least one by construction and ∥F h (s)∥ ≤ 1, from the Elliptical Potential Lemma (Lemma D.2 [17] ), we have for all a ∈ A and h ∈ [H],K k=1 F h (s k ) ⊤ (Λ a h,k ) -1 F h (s k ) ≤ 2 log(det(Λ a h,k+1 )/det(Λ a h,0 )) Furthermore, we have ∥Λ a h,k+1 ∥ = ∥ t∈T a K,h F h (s t h )F h (s t h ) ⊤ + λI∥ ≤ λ + |T a K,h | ≤ λ + K. It follows that K k=1 F h (s k ) ⊤ (Λ a h,k ) -1 F h (s k ) ≤ 2d log(1 + K/λ) ≤ 2dι,so grouping the episodes by actions gives  k∈[K] F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )   1/2 =   a∈A t∈T K,h,a F h (s t h ) ⊤ (Λ a h,t ) -1 F h (s t h )   1/2 ≤ √ 2dAι.For the next term, let k a,i refer to the episode in which action a was taken at time step h for the ith time. Then, we first re-index the summation and then use the Cauchy-Schwarz inequality to getk∈[K] |T a k,h | F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h )) = a∈A |T a K,h | i=1 √ i F ⊤ ka,i,h (Λ a ka,i,h ) -1 F ka,i,h ≤ a∈A   |T a K,h | i=1 i   1/2   t∈T a K,h F ⊤ t,h (Λ a t,h ) -1 F t,h   1/2 ≤ C ′ a∈A |T a K,h |   t∈T a K,h F ⊤ t,h (Λ a t,h ) -1 F t,h   1/2 ≤ C ′ a∈A |T a K,h | √ 2dι,where the last inequality comes from holds from the above elliptical potential lemma. Applying the results to the initial inequality, we havek∈[K] β a k,h F h (s k h ) ⊤ (Λ a k h h,k ) -1 F h (s k h ) ≤ CH( √ 2d 3 AKι 2 +ξ √ dC ′ a∈A |T a K,h | √ 2dι) ≤ C( √ 2d 3 AHT ι 2 +ξ √ 2ιdT.Substituting these results into the original regret bound givesRegret(K) ≤ C ′′′ ( √ d 3 H 3 AT ι 2 + dT Hξ √ ι).for some constant C ′′′ > 0 with probability at least 1 -δ.We reiterate that the steps and analysis in this subsection are essentially the same as the proofs in [17] , except we have S copies of the weight vectors and gram matrices. The results and proofs follow the same structure and logic as in The proof of all the theorems and lemmas follow the same steps as the proofs for the analogous result in the (S, d, A) setting except we replace F (s) with G(a) and estimate the Gram matrix and weight vectors for each state instead of each action.To prove Theorem 5, we first introduce notation used throughout this section and then present auxiliary lemmas. We let Λ s h,k , w s h,k , Q k h , V k h , π k as the parameters/estimates at episode k. Furthermore, let V k h = max s∈S Q k h (s, a) and π k be the greedy policy w.r.t. Q k h . We let G k h := G h (a k h ). We first bound the log of the covering number of our function class for the value function to control the error of our algorithm's estimate, which allows us to prove our concentration result as the value function estimate is not constant. Lemma 18. Let V denote a function class of mappings from S to R with the following parametric form for all s ∈ SV (s) = min max a∈A w ⊤ s G(a) + β G(a) ⊤ Λ -1 s G(a), Hwhere the parameters w s , β, Λ s satisfy ∥w s ∥ ≤ L for all s ∈ S, β ∈ [0, B], and the minimum eigenvalue of Λ s is greater than λ. Assume that ∥G(a)∥ ≤ 1 for all s ∈ S, and let N ϵ be the ϵ-covering number of V with respect to the distance dist(V, V′ ) = sup s |V (s) -V ′ (s)|. Then, log(N ϵ ) ≤ d log(1 + 4L/ϵ) + d 2 log(1 + 8d 1/2 B 2 /(λϵ 2 ))Proof. Equivalently, we reparameterize the function class byD s = β 2 Λ -1 s , for all s ∈ S V (s) = min max a∈A w ⊤ s G(a) + G(a) ⊤ D s G(a), Hwhere ∥w s ∥ ≤ L and ∥D s ∥ ≤ B 2 /λ for all s ∈ S. For any V 1 , V 2 ∈ V, let them take the form in the above equation with parameters (w s , D s ) and (w s ′ , D s ′ ). Since min(•, H) and max s∈S are contraction maps,dist(V 1 -V 2 ) ≤ sup s,a |(w ⊤ s G(a) + G(a) ⊤ D s G(a)) -(w ⊤ s ′ G(a) + G(a) ⊤ D s ′ G(a))| ≤ sup s,G:∥G∥≤1 |(w ⊤ s G + G ⊤ D s G) -(w ⊤ s ′ G + G ⊤ D s ′ G)| ≤ max s∈S sup G:∥G∥≤1 |(w s -w s ′ ) ⊤ G| + sup G:∥G∥≤1 | G ⊤ (D s -D s ′ )G| ≤ max s∈S ∥w s -w s ′ ∥ + ∥D s -D s ′ ∥ ≤ max s∈S ∥w s -w s ′ ∥ + ∥D s -D s ′ ∥ Fwhere the third inequality holds because | ≤ (1 + 4L/ϵ) d , |C D | ≤ (1 + 8d 1/2 B 2 /(λϵ 2 )) d 2 . Hence, for any V 1 , there exists a w s ′ ∈ C w and D s ′ ∈ C D for all a ∈ A such that V 2 parameterized by (w s ′ , D s ′ ) satisfies dist(V 1 , V 2 ) ≤ ϵ. Hence, N ϵ ≤ |C w ||C D |, which gives: log(N ϵ ) ≤ log(|C w |) + log(|C D |) ≤ d log(1 + 4ϵL/ϵ) + d 2 log(1 + 8d 1/2 B 2 /(λϵ 2 )).We next bound the ℓ 2 -norm of the weight vector of any policy. Lemma 19. Let {w s h } be the weight vector of some policy π, i.e., Q πh (s, a) = G h (a) ⊤ w s h . Then, ∥w s h ∥ ≤ 2H √ d.Proof. Note that Q π h (s, a) = r h (s, a) + s ′ V π h+1 (s ′ )P h (s ′ |s, a), so, using the low-rank representations of r h , P h , it follows that∥w s h ∥ 2 = ∥W h (s, •) + s ′ V π (s ′ )U h (s ′ , s, •)∥ 2 ≤ ∥W h (s, •)∥ 2 + ∥ s ′ V π (s ′ )U h (s ′ , s, •)∥ 2 .Recall that since the feature mapping was scaled up (G h = A dµ G ′ ) to ensure the max entries of G and W, U are on the same scale, it follows that ∥W h (s)∥ 2 ≤ 1 and∥ s ′ ∈S V π h+1 (s ′ )U h (s ′ , s)∥ 2 ≤ H. Therefore, it follows that ∥w s h ∥ 2 ≤ 2H √ d.We next bound the 2-norm of the weight vector from the algorithm. Lemma 20. For any k, h, s, the weight vector from the above algorithm satisfies ∥w s h,k ∥ ≤ 2H dk/λ.Proof. For any G h (a) = g, we have for all s ∈ S,|g ⊤ w s h,k | = |g ⊤ (Λ s h ) -1 t∈T s k-1,h G h (a t h ) r h (s, a t h ) + max a ′ ∈A Q h+1 (s t h+1 , a ′ ) | ≤ | t∈T s k-1,h g ⊤ (Λ s h ) -1 G h (a t h )|2H ≤ 2H ( t∈T s k-1,h g ⊤ (Λ s h ) -1 g)( t∈T s k-1,h G h (a t h ) ⊤ (Λ s h ) -1 G h (a t h )) ≤ 2H∥g∥ 2 d|T s k-1,h |/λ ≤ 2H dk/λwhere the second to last inequality is due to Lemma D.1 from [17] and that Rayleigh quotients are upper bounded by the largest eigenvalue of the matrix (Theorem 4.2.2 from [14] ). The last inequality is due to ∥g∥ 2 ≤ 1 and |T s k-1,h | ≤ k.We next prove the main concentration lemma that controls the estimate.Lemma 21. Let c ′ be the constant in the definition of β s k,h = c ′ dH √ ι. Then, there exists a constant C > 0 that is independent of c ′ such that for any δ ∈ (0, 1), if we let the event X be∀(s, k, h) ∈ S×[K]×[H] : t∈T s k-1,h G h (a t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s, a t h ) (Λ s h,t ) -1 ≤ CdH √ χ where χ = log(2(c ′ + 1)dT S/δ), then P(X ) ≥ 1 -δ/2.Proof. From Lemma 20, we have ∥w s h,k ∥ 2 ≤ 2H dk/λ. By construction, the minimum eigenvalue of Λ s h,t is lower bounded by λ. Then, from Lemma D.4 in [17] (with δ ′ = δ/S), Lemma 18, and taking a union bound over all states, we have that with probability at least 1 -δ ′ /2, for all s ∈ S and ϵ > 0,t∈T s k-1,h G h (a t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s, a t h ) 2 (Λ s h,t ) -1 ≤ 4H 2 d 2 log((k + λ)/λ)) + log(2SN ϵ /δ) +8k 2 ϵ 2 /λ.Then, from Lemma 18, it follows that with probability at least 1 -δ ′ /2, for all a ∈ S and ϵ > 0,t∈T s k-1,h G h (a t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s, a t h ) 2 (Λ s h,t ) -1 ≤ 4H 2 d 2 log((k + λ)/λ)) + log(2S/δ) + d log(1 + 4L/ϵ) + d 2 log(1 + 8d 1/2 β 2 /(λϵ 2 )) + 8k 2 ϵ 2 /λ.Choosing λ = 1, β s k,h = CdHι, ϵ = dH/k gives that there exists some constant C ′ such thatt∈T s k-1,h G h (a t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s, a t h ) 2 (Λ s h,t ) -1 ≤ C ′ d 2 H 2 log(2(c β + 1)dT S/δ).We next recursively bound the difference between the value function maintained in the algorithm and the true value function of any policy π. We upperbound this with their expected difference and an additional error term, which is bounded with high probability.Lemma 22. There exists a constant c β such that β s k,h = c β dH √ ι where ι = log(2dST /p) and for any fixed policy π, on the event X defined in Lemma 21, we have for all (s, a, h, k)∈ S × S × [H] × [K]: G h (a) ⊤ w s h,k -Q π h (s, a) = P h (V k h+1 -V π h+1 )(s, a) + δ k h (s, a), where |δ k h (s, a)| ≤ β s k,h G h (a) ⊤ (Λ s h,k ) -1 G h (a).Proof. From our low-rank assumption, it follows thatQ π h (s, a) = G h (a) ⊤ w s h = (r h + P h V π h+1 )(s, a),which following the steps from the proof of Lemma B.4 in [17] givesw s h,k -w s,π h = -λ(Λ s h,k ) -1 w s,π h + (Λ s h,k ) -1 t∈T s k-1,h G h (a t h )(V k h+1 (s t h+1 ) -P h V k h+1 (s, a t h ) + (Λ s h,k ) -1 ) t∈T s k-1,h G h (a t h )P h (V k h+1 -V π h+1 )(s, a t h )Now, we bound each term (q s 1 , q s 2 , q s 3 ) individually, for the first term, note for all s ∈ S, a ∈ A|G h (a) ⊤ q s 1 | = |λG h (a) ⊤ (Λ s h,k ) -1 w s,π h | ≤ √ λ∥w s,π h ∥ G h (a) ⊤ (Λ s h,k ) -1 G h (a)For the second term, given the event X , we have from Cauchy Schwarz|G h (a) ⊤ q s 2 | ≤ CdH √ χ G h (a) ⊤ (Λ s h,k ) -1 G h (a)where χ = log(2(c β + 1)dT S/p). For the third term,G h (a) ⊤ q s 3 = G h (a) ⊤   (Λ s h,k ) -1 ) t∈T s k-1,h G h (a t h )P h (V k h+1 -V π h+1 )(s, a t h )   = G h (a) ⊤   (Λ s h,k ) -1 ) t∈T s k-1,h G h (a t h )G h (a t h ) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s)   = G h (a) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s) -λG h (a) ⊤ (Λ s h,k ) -1 ) s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s)We note thatG h (a) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s) = P h (V k h+1 -V π h+1 )(s, a)and|λG h (a) ⊤ (Λ s h,k ) -1 ) s ′ ∈S (V k h+1 -V k h+1 )(s ′ )U h (s ′ , s) | ≤ 2H √ dλ G h (a) ⊤ (Λ s h,k ) -1 G h (a) Since |G h (a) ⊤ w s h,k -Q π h (s, a)| = G h (a) ⊤ (w s h,k -w s,π h ) = G h (a) ⊤ (q s 1 + q s 2 + q s 3 ), it follows that |G h (a) ⊤ w s h,k -Q π h (s, a) -P h (V k h+1 -V π h+1 )(s, a)| ≤ C"dH √ χ G h (a) ⊤ (Λ s h,k ) -1 G h (a).Similarly as in [17] , we choose c β that satisfies C" log(2) + log(c β + 1) ≤ c β log(2).This lemma implies that by adding the appropriate bonus, Q k h is always an upperbound of Q * h with high probability Lemma 23. On the event X defined in lemma 21, we haveQ k h (s, a) ≥ Q * h (s, a) for all (s, a, h, k) ∈ S × A × [H] × [K].Proof. We prove this with induction. The base case holds because at step H + 1, the value function is zero, so from Lemma 22,|G h (a) ⊤ w s h,k -Q * H (s, a)| ≤ β s k,h G h (a) ⊤ (Λ s h,k ) -1 )G h (a)and thus,Q * H (s, a) ≤ min H, G h (a) ⊤ w s h,k + β s k,h G h (a) ⊤ (Λ s h,k ) -1 )G h (a) = Q k H (s, a).From the inductive hypothesis (assuming thatQ k h+1 (s, a) ≥ Q * h+1 (s, a)), it follows that P h (V k h+1 - V * h+1 )(s, a) ≥ 0. From Lemma 22, G h (a) ⊤ w s h,k -Q * h (s, a) ≤ β s k,h G h (a) ⊤ (Λ s h,k ) -1 G h (a). It follows that Q * h (s, a) ≤ min H, G h (a) ⊤ w s h,k + β s k,h G h (a) ⊤ (Λ s h,k ) -1 )G h (a) = Q k h (s, a).We next show that Lemma 22 transforms to the recursive formulaδ k h = V k h (s k h ) -V π k h (s k h ). Lemma 24. Let δ k h = V k h (s k h ) -V π k h (s k h ) and ξ k h+1 = E[δ k h+1 |s k h , s k h ] -δ k h+1 .Then, on the event X defined in Lemma 21, we have for any (h, k):δ k h ≤ δ k h+1 + ξ k h+1 + β s k,h G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h )Proof. From Lemma 22, we have for any (s, a, h, k) thatQ k h (s, a) -Q π k h (s, a) ≤ P h (V k h+1 -V π k h+1 )(s, a) + β s k,h G h (a) ⊤ (Λ s h,k ) -1 G h (a).From the definition of V π k , we haveδ k h = Q k h (s k h , a k h ) -Q π k h (s k h , a k h ).Finally, we prove the main theorem, Theorem 5.Proof. Suppose that the Assumptions required in Theorem 5 hold. We condition on the event X from Lemma 21 with p = δ/2 and use the notation for δ k h , ξ k h as in Lemma 24. From Lemmas 9 and 24, we haveRegret(K) = K k=1 (V * 1 (s k 1 )-V π k 1 (s k 1 )) ≤ K k=1 δ k 1 ≤ k∈[K] h∈[H] ξ k h +β s k,h k∈[K] h∈[H] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h )Since the observations at episode k are independent of the computed value function (this uses the trajectories from episodes 1 to k -1, it follows {ξ k h } is a martingale difference sequence with |ξ k h | ≤ 2H for all (k, h). Thus, from the Azuma Hoeffding inequality, we havek∈[K],h∈H ξ k h ≤ 2T H 2 log(2/p) ≤ 2H √ T ιwith probability at least 1 -δ/2. For the second term, we note that the minimum eigenvalue of Λs k h h,kis at least one by construction and ∥G h (a)∥ ≤ 1. From the Elliptical Potential Lemma (Lemma D.2 [17] ), we have for all s ∈ S and h ∈[H], K k=1 G h (a k h ) ⊤ (Λ s h,k ) -1 G h (a k h ) ≤ 2 log(det(Λ s h,k+1 )/ det(Λ s h,0 )) Furthermore, we have ∥Λ s h,k+1 ∥ = ∥ t∈T s K,h G h (a t h )G h (a t h ) ⊤ + λI∥ ≤ λ + |T s K,h | ≤ λ + K. It follows that K k=1 G h (a k h ) ⊤ (Λ s h,k ) -1 G h (a k h ) ≤ 2d log(1 + K/λ) ≤ 2dιNext, by Cauchy-Schwarz and grouping the regret by each state, it follows thatk∈[K] h∈[H] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) ≤ h∈[H] √ K   k∈[K] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h )   1/2 = h∈[H] √ K   s∈S t∈T s K,h G h (a t h ) ⊤ (Λ s h,t ) -1 G h (a t h )   1/2 ≤ h∈[H] √ K s∈S 2dι 1/2 ≤ H √ 2KSdι.Since β s k,h = cdH √ ι for some constant c, from a union bound and the previous bounds, it follows thatRegret(K) ≤ 2H √ T ι + β s k,h H √ 2KSdι ∈ Õ( √ d 3 H 3 ST ).with probability at least 1 -δ.Next, we prove the helper lemmas needed in the misspecified setting and follow the proof structure and techniques used in [17] .Lemma 25. For a ξ-approximate (S, S, d) Tucker rank MDP (Assumption 4), then for any policy π there exists corresponding weight vectors {w s h } where w sh = Σ h W h (s) + s ′ ∈S V π h+1 (s ′ )U h (s ′ , s) such that for all (s, a) ∈ S × A |Q π h (s, a) -G h (a)w s⊤ h | ≤ 3Hξ. Proof. Note that Q π h (s, a) = r h (s, a) + s ′ V π h+1 (s ′ )P h (s ′ |s, a), so, using the low-rank representations of r h , P h , it follows that|Q π h (s, a) -G h (a)w s⊤ h | ≤ |r h (s, a) -G h (a)W h (s) ⊤ | + s ′ V π h+1 (s ′ )P h (s ′ |s, a) -G h (a) s ′ ∈S V π h+1 (s ′ )U h (s ′ , s) ≤ ξ + 2Hξ ≤ 3Hξ.Lemma 26. Suppose Assumption 7 holds. Let {w s h } be the weight vector of some policy π, i.e., Q π h (s, a) = G h (a) ⊤ w s h . Then, ∥w s h ∥ ≤ 2H √ d. Proof. Recall that w s h = Σ h W h (s) + s ′ ∈S V π h+1 (s ′ )U h (s ′ , s= c ′ m H(d √ ι + ξ |T s k,h |d).Then, there exists a constant C > 0 that is independent of c ′ m such that for any δ ∈ (0, 1), if we let the event X be∀(a, k, h) ∈ A×[K]×[H] : t∈T s k-1,h G h (a t h )(V t h+1 (s t h+1 ) -P h V t h+1 (s, a t h ) (Λ s h,t ) -1 ≤ CdH √ χ where χ = log(2(c ′ m + 1)dT S/δ), then P(X ) ≥ 1 -δ/2.Proof. The proof is the same as the proof of Lemma 21 except we increase β s k,h to account for the misspecifiction error. Since ξ ≤ 1 by assumption, the modification to β s k,h only affects C.Next, we account for the adversarial misspecification error. Lemma 28. Let {ϵ t } be any sequence such that |ϵ τ | ≤ B for any t. Then, for any(h, k, s) ∈ [H] × [K] × S and G ∈ R d , we have |G ⊤ (Λ s k,h ) -1 t∈T s k-1,h G h (a t h )ϵ t | ≤ B d|T s k-1,h |G ⊤ (Λ s k,h ) -1 G.Proof. From the Cauchy-Schwarz inequality and Elliptical Potential Lemma (Lemma D.1 [17] ), we have|G ⊤ (Λ s k,h ) -1 t∈T s k-1,h G h (a t h )ϵ t | ≤ B   t∈T s k-1,h G ⊤ (Λ s k,h ) -1 G     t∈T s k-1,h G h (a t h ) ⊤ (Λ s k,h ) -1 G h (a t h )   ≤ B d|T s k-1,h |G ⊤ (Λ s k,h ) -1 G.Next, we bound the error between a policies Q function and our low-rank estimate. Now, we bound each of the four terms above (q s 1 , q s 2 , q s 3 , q s 4 ) individually, for the first term, note for all a ∈ A |G h (a) ⊤ q s1 | = |λG h (a) ⊤ (Λ s h,k ) -1 w s,π h | ≤ √ λ∥w s,π h ∥ G h (a) ⊤ (Λ s h,k ) -1 G h (a)For the second term, given the event X , we have from Cauchy Schwarz|G h (a) ⊤ q s 2 | ≤ CdH √ χ G h (a) ⊤ (Λ s h,k ) -1 G h (a)where χ = log(2(c β + 1)dT S/p). For the third term,G h (a) ⊤ q s 3 = G h (a) ⊤   (Λ s h,k ) -1 t∈T s k-1,h G h (a t h ) Ph (V k h+1 -V π h+1 )(s, a t h )   = G h (a) ⊤   (Λ s h,k ) -1 t∈T s k-1,h G h (a t h )G h (a t h ) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s)   = G h (a) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s) -λG h (a) ⊤ (Λ s h,k ) -1 s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s) ,and note that From Lemma 28, we have |G h (a), q s 4 | ≤ 2Hξ d|T s k,h |G h (a) ⊤ (Λ -1 h,k ) -1 G h (a). Since |G h (a) ⊤ w s h,k -Q π h (s, a)| = G h (a) ⊤ (w s h,k -w s,π h ) = G h (a) ⊤ (q s 1 + q s 2 + q s 3 + q s 4 ), it follows thatG h (a) ⊤ s ′ ∈S (V k h+1 -V π h+1 )(s ′ )U h (s ′ , s) = Ph (V k h+1 -V π h+1 )(s,|G h (a) ⊤ w s h,k -Q π h (s, a)-P h (V k h+1 -V π h+1 )(s, a)| ≤ √ χ(C"d √ χ+2ξ |T s k,h |d)H G h (a) ⊤ (Λ s h,k ) -1 G h (a)+4Hξ.Similarly as in [17] , we choose c β that satisfies C" log(2) + log(c β + 1) ≤ c β log(2). Now, we prove that Q k h is an upperbound of Q * h conditioned on the event in Lemma 27. Lemma 30. Suppose Assumption 7 holds. On the event X defined in lemma 27, we have Q Similarly, to the regular case, the gap in the misspecified setting has a recursive formula.Lemma 31. Let δ k h = V k h (s k h ) -V π k h (s k h ) and ξ k h+1 = E[δ k h+1 |s k h , a k h ] -δ k h+1 .Then, on the event X defined in Lemma 27, we have for any (h, k):δ k h ≤ δ k h+1 + ξ k h+1 + β s k,h G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) + 4HξProof. From Lemma 29, we have for any (s, a, h, k) thatQ k h (s, a) -Q π k h (s, a) ≤ P h (V k h+1 -V π k h+1 )(s, a) + β s k,h G h (a) ⊤ (Λ s h,k ) -1 G h (a) + 4Hξ.From the definition of V π k , we haveδ k h = Q k h (s k h , a k h ) -Q π k h (s k h , a k h ), and substituting this into the first equation finishes the proof.Finally, we prove the main result in the misspecified setting Theorem 9.Proof. Suppose that the Assumptions required in Theorem 6 hold. We condition on the event X from Lemma 27 with p = δ/2 and use the notation for δ k h , ξ k h as in Lemma 31. From Lemma 16, we have Q k 1 (s, a) ≥ Q * 1 (s, a) -4H 2 ξ, which implies V * 1 (s) -V π k 1 (s) ≤ δ k 1 + 4H 2 ξ. Thus, from Lemma 29, on the event X , it follows that Regret(K) = K k=1 (V * 1 (s k 1 ) -V π k 1 (s k 1 )) ≤ K k=1 δ k 1 + 4H 2 ξ ≤ k∈[K] h∈[H] ξ k h + k∈[K] β s k,h h∈[H] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) +β s k,h G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) ≤ CH( k∈[K] d √ ι G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) + k∈[K] ξ |T s k,h |d G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (s k h )).From the Cauchy-Schwarz inequality, it follows thatk∈[K] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) ≤ √ K   k∈[K] G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h )   .Let k i refers to the episode in which state s was seen at time step h for the ith time. Then, for the other term, we first re-index the summation and then use the Cauchy-Schwarz inequality to getk∈[K] |T s k,h | G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h )) = s∈S |T s K,h | i=1 √ i G ⊤ ki,h (Λ a ki,h ) -1 G ki,h ≤   |T s K,h | i=1 i   1/2   t∈T s K,h G ⊤ k,h (Λ s k h k,h ) -1 G k,h   1/2 ≤ C ′ |T s K,h |   t∈T s K,h G ⊤ k,h (Λ s k h k,h ) -1 G k,h   1/2for some absolute constant C ′ > 0. Since the minimum eigenvalue of Λ G h (a k h ) ⊤ (ΛEQUATIONThus,k∈[K] β s k,h G h (a k h ) ⊤ (Λ s k h h,k ) -1 G h (a k h ) ≤ CH( √ 2d 3 SKι 2 + ξ √ dC ′ s∈S |T s k,h | √ 2dι) ≤ C( √ 2d 3 SHT ι 2 + ξ √ 2ιdT.Substituting these results into the original regret bound givesRegret(K) ≤ C ′′′ ( √ d 3 H 3 ST ι 2 + dT Hξ √ ι).for some constant C ′′′ > 0 with probability at least 1 -δ.• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Since ᾱ ≥ α, moving ᾱ into the source sample complexity yields a sample complexity that scales with α 5 . Φ and Γ refer to the function classes that contain the true ϕ and µ, respectively. As we make no assumptions on the function class of ϕ, we replace log(|Φ||Γ|) with |S||A|.It is possible to relax the assumption of sharing the same state/action spaces. In particular, depending on the Tucker rank of the transition kernel, we only require the source and target MDPs share only one of the spaces.Our results can easily be extended to stochastic reward functions.Since ᾱ ≥ α, moving ᾱ into the source sample complexity yields a sample complexity that scales with α.While the misspecified assumption in[17] uses the total variation distance, they refer to it as | s ′ ∈S P (s ′ |s, a) -P (s ′ |s, a)| in the second to last inequality in the proof of Lemma C.1 and the second to last equation on page23 


Decision: The paper studies the problem of transfer learning in RL under low-rank assumptions on the dynamics. While some of the reviewers raised concerns about the novelty of the contribution, there is general consensus about the fact that the main merit of the paper is to provide a comprehensive treatment of different low-rank settings and a somehow general and unified solution for them. Furthermore, for most of the assumptions considered in the paper, the results are minimax optimal. As such, I think this is an important contribution to the community and I believe this paper could become a go-to reference for this setting. Hence, my recommendation for acceptance.

I still strongly encourage the authors to revise the current manuscript:
* Fix all the typos identified by rev. LmTe. In particular, given that the paper reviews many different settings, it is easy to get "lost" in the different results of the paper. So it is really important to have very rigorous writing. 
* Please include all the discussion and clarification from the rebuttal. For instance, the dependence on M may indeed by a source of confusion.

Reviews: review: paper_summary: paper_summary: This work considers transfer RL, where the source and target MDPs admit low Tucker rank. An information-theoretic lower bound is derived for the source sample complexity, and the proposed algorithm is minimax optimal respecting the transfer-ability coefficient $\alpha$ (in the case of $(d,S,A)$). The results do not assume the representations lie within the given function class.
strength_weakness: strength_weakness: (-) The target regret bound grows polynomially in the number $M$ of source MDPs.

(-) Assumption 3 of full-rank $Q^*$-function can be quite restrictive, and does not hold in simple settings such as goal-reaching tasks in a binary tree (i.e., yielding reward only when reaching some leaf node at the last layer).
questions: questions: 1. Does alg in [4] also work for MDPs with Tucker ranks $(S,S,d),(S,d,A)$, and $(d,d,d)$? If yes, are the source sample complexity and the target regret bound the same to the case of $(d,S,A)$? If not, is there any reason?
2. As different algorithms are required for various types of low-Tucker-rank MDPs, could you provide examples of how to choose the algorithm in practice?
3. I am quite confused by the statement in Lines 325-328. What is the difference between "a subset of the space spanned by the source features" and "being a linear combination of the source features"? According to (Assumption 2.2, [4]), it is possible that some $\alpha_{k;h}$'s are zero.
4. What is $Q_{2,1}^{\*,1}$ at Line 523 (should it be $Q_{1,2\}^{*,1}$)? Also, could you provide more explanations on why the agent needs to differentiate between the two optimal $Q$-functions to enable the transferring? 
5. To improve interpretability, I suggest adding a column in Table 1 and listing the target regret bounds with known latent representations.
limitations: limitations: The limitations are addressed in the paper.
paper_summary: paper_summary: This paper addresses the computational and data inefficiencies of reinforcement learning (RL) algorithms due to large state and action spaces. It introduces a transfer learning approach that utilizes latent low-rank structures in the transition kernels of source and target Markov Decision Processes (MDPs). The paper presents a new algorithm that achieves efficient transfer by learning and utilizing latent representations, significantly reducing the dependency on state and action spaces in the target MDP. The paper provides theoretical guarantees for their algorithms, including source sample complexity and target regret bounds for each Tucker rank setting. The authors also discuss connections to related work in linear MDPs, low-rank MDPs, and other transfer RL approaches
strength_weakness: strength_weakness: - While the paper is mostly original, it builds significantly on existing concepts in low-rank MDPs and linear MDPs. More explicit discussion on how this work diverges from traditional approaches could enhance its originality.
- The assumptions required for the theoretical results, such as the specifics of the Tucker rank and the incoherence conditions, might limit the applicability of the results in practical, real-world scenarios where such assumptions may not hold.
- The practical implications and applications of the proposed methods could be highlighted more. Discussions on how these methods could be integrated into existing RL systems or specific real-world applications would enhance the paper's impact.
questions: questions: - The paper assumes specific structures for the MDPs. How robust are the proposed methods to deviations from these assumptions?
- How sensitive is the algorithm's performance to changes in the transfer-ability coefficient $\alpha$? What are the practical steps for estimating $\alpha$ in a new environment?
- Could the authors conduct numerical experiments like [4, 28] did in their paper? It would be valuable to include empirical comparisons against relevant baselines on benchmark RL tasks to demonstrate practical performance gains.
- Could the authors clarify the practical implications of the transfer-ability coefficient in real-world scenarios? How can one estimate this coefficient in practice?
- The current setup focuses on transferring from the source to a single target task. Is there potential to extend this framework to continual or multi-task learning settings? How does this approach relate to other forms of transfer in RL, such as policy distillation or meta-learning?
- Typos
    - Inconsistency in Line 150 and Figure 1 caption. It seems $(S, S, d)$ Tucker rank.
    - Line 352: Algorithm 2, 2,
limitations: limitations: The paper discusses the minimax optimality of theoretical guarantees with respect to the parameters or some assumptions of the problem, but a more direct mention of this paper's limitations would make the paper more complete. Furthermore, practical limitations, such as the algorithms' scalability to extremely large state and action spaces or their performance under model misspecification, are not thoroughly examined.
paper_summary: paper_summary: The paper investigates transfer in reinforcement learning, where one tries to exploit latent structure common across several MDPs. Specifically the paper consider M "source" episodic MDPs sharing a latent low-rank structure of the transition matrix and one "target" episodic MDP whose transition matrix is also-low rank, with latent features on the span of the source features. The main results take the form of minimal sample-complexity bounds on the source MDPs that induce a regret bound on the target MDP that avoid a dependence in the size of the state-action space. Since the transition matrix of a MDP is actually a 3-tensor, several notions of low-rank are considered in the sense of the Tucker rank of a tensor, which correspond to different ways of factorizing $P(s' | s,a)$ as a product of two matrices. One such low-rank assumption covers the case of low-rank and linear MDPs. For each of these cases, the paper also identifies a transferability coefficient from which a sample-complexity lower bound is also established.
strength_weakness: strength_weakness: The paper is quite long, technical and I think some effort could be made to make it easier to read. I have not gone carefully over all the proofs but I have found quite a number of statements that I did not understand. There is also a large number of typos. A typo here and there should normally not be a big problem, but their number is quite irritating. I think a certain number of them arises from the similarity between the different Tucker rank assumptions.
questions: questions: Essentially, I simply suggest improving the clarity of the paper.  I have made a list of a few things which caught my attention, but this is probably not exhaustive. 

1. I do not understand the proof of Theorem 1:

a. It is really difficult to identify the different quantities involved in Assumptions 1 and 2, such as the latent factors $G_i$, from what is given in the proof. This all the more so true as the notation is really heavy (e.g. $Q_{1,1}^{\ast,1}$) and inconsistent, resulting in conflicts of notation: for example in line 513 $G_i$ refers to the target latent factor of problem $i$ but this notation is also used in Assumption 1 with $i$ referring to a time step. From the notation used in the proof $i$ should be used as an exponent to refer to problem $i$. 

b. In line 508 $c = \sqrt{1+1/\alpha^2}$ is not bounded by $2$ as $\alpha \rightarrow 0$...

c. There is a $c$ missing in the equation of line 512: $[\sqrt{1/2n} \quad - \sqrt{1/2n}] = - \alpha [\sqrt{1/2n} \quad - \sqrt{1/2n}] + \alpha c G'$.

d. I guess the parameter $\alpha$ of the proof is supposed to be the transferability coefficient of Definition 3. Is it still the case with the missing $c$? Furthermore the relation between Definition $3$ and the difference between entries of $Q^{\ast}$-s is not clear.

e. The end of the argument (l. 526 - 529) is too elusive: the relation with the rest of the proof is not explained. One does not understand how the Bernoulli variable $X$ comes into play. 

 f. l. 527 is the reader supposed to read all the 389 pages of [5] to be convinced that ”the probability of correctly identifying $G$ is upper bounded by 0.76 [5]"?

g. Theorem 1 requires Assumptions 1 and 2 but the proof involves Assumptions 5 and 6 

h. Assumptions 1 and 2 are assumptions on transition matrices but in the proof these are deduced directly from the form of the $Q$-functions

 i. The matrices given in the proof have size $2 \times 1, 1 \times 2$ or $2 \times 2$ but the example is about a state space of size $[2n]$. If the matrices are block matrices this needs to be emphasized. What about orthonormality of columns?

j. Finally, there is (at least) one typo in the second equation of line 505: $Q_{1,2}^{\ast,1}$ should be $Q_{2,1}^{\ast,1}$.

2.Some notations change throughout the paper. For instance, the number of episodes (which i think is not defined anywhere) is sometimes written $K$, sometimes $T$. Same for the rank of the matrices considered, it is sometimes $r$, sometimes $d$ (e.g. from Prop. 2 to Corollary 3)

3. p.2, l 113-116, there is a problematic conflict of notation in having $P_{h}$ stand for both the transition matrix of the source MDP at time $h$ and the family of transition matrices of the $h$-th MDP

4. p.4 In Definition 1 the factors $G_i$ belong to $\mathbb{R}^{n_i \times d_i}$ instead of just $\mathbb{R}^{n_i}$. Strictly speaking orthonormal matrices need to be square matrices so if $d_i \neq n_i$ they only have orthonormal columns. It should be $G_{h}(a,i)$ instead of $G_{h}(s,i)$

5. p.4 l.150 "Figure 1 pictorially displays the $(S,d,A)$ Tucker rank decomposition": as indicated by the caption, the case displayed is $(S,S,d)$...

6. p.5 In Assumption 1 l; 192 It should be $G_{h}(a,i)$ instead of $G_{h}(s,i)$. Same remark as above, orthonormality refers to orthonormality of the columns.

7. p.7 l.281 $Q_{h,m}^{\ast}$ should be $Q_{m,h}^{\ast}$
 
8. p.7 l.290: I think $s_{h+1}^{k}$ should be $s_{h+1}^{t}$.
 
9. p.9 l.352 "Algorithm 2, 2": remove one 2

10. p.15 in the proof of Theorem 2 how is $\bar{\gamma}$ bounded? Shouldn't there be an additional factor $8 / \sqrt{\mu}$ in l.556?

11. p.16 l.568 I assume $|| \cdot ||_{TV}$ is total variation distance. It should be defined explicitly. Also there shouldn't be an $s'$ in the left hand side, and the sum in the right hand side should be inside the absolute value.

12. In Appendices F and G, I suggest adding more references, links between proofs and equations, recalling some assumptions that are made to simplify the exposition. 
 
12. p.36 in Prop.2 the second bound should involve $V_j^{\ast}$ instead of $U_j^{\ast}$ in the right hand side

13. p.38 I do not understand the proof of Corollary 3: from Prop.2 one should bound $\bar{\gamma}$. The proof gives a bound on $\|| A^{\ast} \||_{\infty}$.

14. p.39 l.1131 in the first equation there is a $\top$ sign that should be in exponent

15. p.48 l.1323 $s$ appears both as an argument of $V$ and in the maximum

16. p.49 l.1331 a word is missing in "where the holds"

17. p.49 l.1340 I do not understand where the last inequality comes from

18. p.49 in the proof of Lemma 20 I do not understand where the third inequality comes from. Also the indices $h$ and $k$ are reversed in $T_{h,k-1}$ are reversed compared to when the notation was introduced in l.286

19. p.49 in the 3rd equation of l.1345, there is no $\top$ on the second $g$ term
limitations: limitations: The authors addressed the limitations of the paper.

Comments: title: Thank you
Answer to rebuttal
Thank you for your response
Follow-up Questions
comment: **1:** Yes, the thresholding procedure also works for the intermediate case. This procedure computes the union of the dimensions from all the source MDP subspaces. It then discards the repeated dimensions from each source MDP (as well as superfluous dimensions due to estimation error in the source MDPs). Thus, if the feature mapping lies in a $n$-dimensional subspace where $d < n < dM$, then the union of the subspaces of all the source MDPs is also $n$-dimensional, in which case the thresholding procedure will output $\tilde{G}_h$ with dimension $n$ (with high probability with respects to the estimation errors).

 **2:** We thank reviewer Stu9 for the suggestion and will include a notation table in the appendix in the final version.
I appreciate the detailed clarification from the authors. I have raised my score accordingly. Responding:

1. I wonder if the thresholding procedure is also applicable to (intermediate) cases where the feature mappings lie in an $n$-dimensional subspace with $d<n<dM$.

2. To improve readability, I suggest including a notation list in the Appendix with clear explanations for (at least the essential) variables used in the analysis.
We thank reviewer LmTe for catching this typo and have corrected it for the final version.
**Dependence on $M$**: Thank you for pointing this out, we realize our notation of $\tilde{G}\_h$ is confusing. 

We first remark that our current assumptions in our work are stronger than what we actually need. Instead, our analysis only requires that $G\_h$ satisfy Assumption 2 instead of both Assumptions 1 and 2, which allows the target MDP to have Tucker rank at most $(S, S, dM)$ if the source subspaces are disjoint.

$\tilde{G}_h$ is not a set; it is a $S \times dM$ matrix. In step 4 of Algorithm 1 (line 287), to construct $\tilde{G}\_h$, we concatenated the estimated singular vectors $\tilde{G}_h = \text{Concat}(\hat{G}\_{1, h}, \hat{G}\_{2, h}, \ldots, \hat{G}\_{m, h})$ from each source MDP so that $\tilde{G}\_h$ has dimension $S \times dM$. 

This approach as stated cannot distinguish between the two cases you presented, i.e., whether the subspaces of the feature mappings from the source MDPs are disjoint or not, and the constructed feature mapping has dimension $dM$ in both cases. Nonetheless, this issue can be readily fixed, as we described below.

To improve our results in the case when the feature mappings from the source MDPs lie in the same d-dimensional subspace, we can add the following procedure: after computing $\tilde{G}\_h$ via concatenation of $\hat{G}\_{m, h}$ for all $m \in [M]$, we perform a singular value decomposition of $\tilde{G}\_h$ and threshold the singular values to remove unneeded dimensions; the constructed feature mapping is then the concatenation of the singular vectors of  $\tilde{G}\_h$ with sufficiently large singular values. Specifically, a short calculation shows the following: we can zero out the  singular values smaller than  $$\sqrt{\frac{d \mu H S}{\alpha^2 T A M}}, $$ and doing so would remove the dependence on $M$ in the target phase regret bound. 

However, in the case when the feature mappings from each source MDP lie in orthogonal d-dimensional subspaces, we cannot discard any unique dimension of the $M$ subspaces as we cannot tell which of the $d$ dimensions match the ones in the target MDP without interacting with it. Thus, we need to include all of them, which still results in at worst a $dM$ dimensional feature representation.

Thank you for pointing out the issue in lines 290-291, we will fix it to use the correct dimension.


**Q1**: If the learner had access to representations  of $\phi(\cdot,\cdot):\mathcal{S}\times\mathcal{S}\to\mathbb{R}^d$ and $\mu(\cdot):\mathcal{A}\to\mathbb{R}^d$ for MDPs with $(S,S,d)$-Tucker rank, we agree that the algorithm from [4] would work in the source phase provided that one adapts the algorithms and analysis to the $(S, S, d)$-Tucker rank setting. However, one must still use our target phase algorithm to get the $\sqrt{A}$ dependence in the regret bound. Using the target phase algorithm from [4] results in a $\sqrt{A^3}$ regret bound. We also note that with this modification, it is possible that the source sample complexity will depend on $S$, unlike the vanilla linear MDP setting where the regret/complexity is independent of $S$.

**Q4**: Thank you for catching this typo, we have corrected it for the final version.
I thank the authors for their answers to my questions. I am really satisfied with the explanation regarding the lower bound which was my main concern. A precise reference to Lemma 5.1 in [5] was undoubtedly the missing ingredient to make it clear and convincing. I think there remains a small typo in that the "magnitude of the largest entrywise difference" (l.524) is $\Omega(1/\alpha)$, not $\Omega(1/\alpha^2)$, the square coming from the application of the lemma.

The other (less important) points raised have also found satisfying clarification. I'll add the remark however that these were intended to be "samples" of what I considered flaws in the paper, so that "more intermediate steps and clarification" do not need to restrict to these of course.
I really appreciate your detailed response to my questions. After reading the authors' responses and comments from other reviewers, I will keep my score.
I thank the authors for their in-depth responses to my questions. Responding:

**Dependence on $M$:** I am confused by the statement "...the feature mapping we learn in the source phase has dimension $dM$". Do you mean the feature mapping $\tilde{G}_h$ computed in Line 4 of Algorithm 1 has dimension $dM$ (but the equation between Lines 290 and 291 implies that $\tilde{G}_h\in\mathbb{R}^d$)? Also, the definition of $\tilde{G}_h$ is a bit confusing. Is it a set?

My understanding is that when the features lie in the same $d$-dimensional space (i.e., linear combination), then $\tilde{G}_h$ would be $d$-dimensional; however, without such prior knowledge (i.e., disjoint subspaces), then we need to construct a $dM$-dimensional $\tilde{G}_h$. Is my understanding correct? 

I am also wondering whether the algorithm can distinguish between these two cases (and hence remove the dependence on $M$).


**Q1.** Can the algorithm in [4] assume access to representations of the form $\phi(\cdot,\cdot):\mathcal{S}\times\mathcal{S}\to\mathbb{R}^d$ and $\mu(\cdot):\mathcal{A}\to\mathbb{R}^d$ for MDPs with $(S,S,d)$-Tucker rank? I think this would work.

**Q4.** Is there a typo in the second equation between Lines 505 and 506, where $Q\_{1,2}^{\*,1}$ on the LHS should be $Q\_{2,1}^{*,1}$?