The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure
Authors: Tyler Sam
Yudong Chen
Christina Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Transfer Learning
Representation Learning
Primary area: reinforcement_learning

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$.

The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure
Tyler Sam Cornell University tj s33550corme111.om edu
Yudong Chen
Christina Lee Yu Cornell University
University of Misconsin-MMdiion wwrhonn.chenwiie..
cleeyu@cornell.co edu
Abstract
Many reinforcement learning (RL) algorithms too costly to use in practice due to the large sizes S, A of the problem's '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 a that measures the difficulty of representational transfer. Our algorithm learns latent representations each source MDP and then exploits the linear structure to remove the dependence 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 a.
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 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 horiz-horizon online episodic MDP setting with A episodes, any algorithm must incur regret of at least Ø(v5 AHH*
time.
[8]. This regret bound is often too large 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 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 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Tucker Rank
Source Sample Complexity
Target Regret Bound
Theorem
2
(S,S,d)
Ô O((1+)/SMMHHHH
(dMH)&ST
Theorem 10
(S, d, A)
Ô ((M(S/A+))MPP
dMH))AA
Theorem 14
(d, (4,S;4) A)
((PdMMTSA)) (5
Ô
VdMMHYT
Theorem 15
(d, (d,d,c) d)
de MOTT
Theorem 3.1 [4
Ad
O(VdHH+T)
Table I: Theoretical guarantees of our algorithms alongside results from literature in the different Tucker rank settings. See Table the regret bounds 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.c., with Tucker rank (d, A) where d < min[S, A}; this is also referred to 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 (d, d, d) Tucker rank setting, where we can further exploit the low rank structure improve performance in the target problem. (As elaborate later, up to factor of d, the (d, d, d) setting subsumes the remaining settings with Tucker ranks (d, d, A), (S, d) and (d, S,d).
The different modes are not interchangeable algorithmically as there is directionality due to the time of the transition between the current and future state. Additionally, the algorithm 4 is not computationally tractable it utilizes 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 transfer learning approach depends on the similarity between the source and target problems, we introduce the transfer-abillty coefficient a, 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. addition, we introduce the transfer-ability coefficient a that measures the ease of transferring 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 a² while [4] is sub-optimal with dependence on a..
Table summarizes our main theoretical results, suppressing the dependence on common matrix estimation terms, and compares them with the results from 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
Since à 2 a. moving & into the source sample complexity yields a sample complexity that scales with a @ and I' refer to the function classes that contain the true é and μ. respectively. As we make no assumptions on the function class of o, replace log(19) @[|[')) with [S|[AA].

---

that the dynamics are linear with respect to 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 of the latent space 17 36
34 The work 13 proposes an algorithm that admits regret bound of
(TVd2122)) 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 linear MDPs but assume that I is unknown. To avoid dependence on the size of the state space, many works in this setting construct algorithms that utilize computationally inefficient oracle to admit sample complexity 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 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.
3 33 26 40.
study representational transfer in low rank MDPs. The work most closely related to ours is 4, which performs reward- ffree 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 our transfer- abbility coefficient but differs as our low rank assumption is imposed on different modes of the probability transition
Transfer RL: As feature learning in low rank MDPs is difficult, 10 23 15
tensor. Their algorithm admits a source sample complexity bound of Ó(A a 2 K2T log( ( ([[1))
with target regret bound of Ō ((v HTT). Other transfer RL works [10] 23 require reach-ability
assumptions to learn the latent representations in the source phase. Similar 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 good policy when given multiple reward functions [19 39 I1 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 330 introduces the RL setting in which the transition kernel has Tucker rank (S, d, A) or (S,S, d). Assuming access generative model, their algorithms learn near-optimal polices with sample complexities that scale with S + A. thereby circumventing the S.A 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.
3 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 E Z, Let = {rr heeHH] be the deterministic unknown reward function of the target MDP, where T4 : S x A - [0, 1). For m E [M] let rm = (
he[H] be the deterministic unknown reward function for the mith source MDP, where Tm. S x A + [0, 1] Let P = } is the probability of transitioning to be the transition kernel for the target MDP, where (s'[ s. a)
state s' from itate-action pair (s, a) at time step h. Similarly, for m E [M], Pm. is the transition kernel for mth source MDP and defined in the same way as P. An agent's policy has the form . Ta S + A(A), where (a]s) is the probability that the agent chooses action at state s and time step h.
(mA 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
V (s) = E EH re(Se, me(s:)) = s). (T, = E ΣH re(St, ax) 8h. = 8, 0n
Itt possible to relax the assumption 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. OOu results can easily be extended to stochastic reward functions.
3

---

where ~ Te(s)), St+1 ~ Pt(-|st. ot). The optimal value function and action value function are (s) == , V. (s) and 0 (s,a) == sup, Q7, (s. a) for all (s, a, h) E S x A [H]. They satisfy the Bellman equations V = m (s, a), (5, = (8, a) + Pa [V (s') for all (s, h) E S x A x [ We define an e-optimal policy π for e > 0 as any policy that satisfies (s) (s) I c for all E S, [H] Similarly, Q c-optimal if (7, a) (s. a) c all (s,a.h) E SSS x A [H] Also, we use the shorthand PA (s a) = Ev (s').
In the transfer RL problem, the learner first interacts with the M source MDPs without access 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 state-action pair (s, a) and time step and outputs r (8, a) and an independent sample from (- (-(ss a) (20) Access to a generative model in the source phase is necessary; in particular, has been shown in Theorem 4.1] that without access to 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., (T) = EkE[K] (8) VT (s), where xe is the learner's policy in episode k, and ii) the number of samples taken in the source phase.
3.1 The Tucker Rank of a Tensor
For the reader's s convenience, we first recall the standard definition of the Tucker rank of tensor. Definition 1 (Tucker Rank (24). A tensor M E R X22 has Tucker rank (d1, d2, da) if (d1, d2, da) is the smallest such that there exists a core tensor X E RRd xd2xda and matrices G2 E R agnixee dd for E [3] with orthonormal columns such that
b(a [=e(a))JE(())N)))) ki,,,, (63340G((3300000))00000
()2(())))((()))
We note in passing that all our sample complexity and regret bounds in Table remain valid when d is an upper bound on the exact rank. In standard MDPs, the transition kernel can have Tucker rank S, A) as there is no low rank structure imposed the benefits of assuming that the transition kernel is low rank along each mode/dimension of the transition kernel, which corresponds the (S, d, A), (8, S,d), 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 ① 2 and (3. respectively:
the tensor. In this work, we investigate
Tucker rank (S, 1, A):
P(s'|s, a) = p(8))(s',a) .), P(s'ls, a) = u(a))(s'.s)
Tucker rank (5 1):
(2)
Tucker rank (1, (,A):
P(s'(s, = ((s'))(ss a))
(3)
for some functions μ., e defined on the appropriate domains. Figure I pictorially displays the (S,S, S, d) Tucker rank assumption 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 significant as each setting requires different algorithms in the target problem and construction for the lower bounds.
Additionally, we analyze the (d, d, d) Tucker rank setting, where the transition kernel fully factorizes, in which case the next state, current state, and action all have separate low rank representations. This assumption allows to further exploit the low rank structure to improve the regret bound in the target phase when compared to the (S, d, A) and (S, d) Tucker rank settings. Note that this (d, d, d) Tucker rank assumption is equivalent to imposing low rank along any two modes of the transition kernel, up to factors of in the sample complexity and regret bounds. For example, for an (S, d, d) Tucker rank transition kernel P. one can factor the S x d x d core tensor into a S x d orthonormal matrix and d² x d x d core tensor, which implies P has Tucker rank (d², d. d).
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

---

Ph(s', ss,))
Gr [0. 1]
G2 = lv1 1/a 1/al
G1 [100]
A
Figure 1: Transition kernel with Tucker rank (S, d,))
Figure 2: A hard transfer learning example where one estimates GT with G and G2
representation. One potential application of this setting is personal movie recommender system. Specifically, the states are user's different states of mind while each action chooses a movie from a large collection. As movies in the same genre evoke similar responses, each action can be mapped to a lower dimensional space with the axis being each genre. In contrast, each state of mind is distinct. In the (S, d, A) Tucker rank setting, one assumes that the state one transitions from has low rank representation. The (d, d, d) Tucker rank setting combines the two previous assumptions and asserts that current states and actions have separate low dimensional representations while low rank MDPs with (d, S. A) Tucker rank assume that each action pair has joint low rank representation. 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.
3.2 Low Tucker Rank MDPs
We first define the incoherence y of a matrix, which is used in the regularity conditions of our Tucker rank assumption.
Definition 2 (Incoherence). Let X RRmx have rank d with singular value decomposition UEVT with U E Rm V E Raxd, Then, X is p-incoherent if for all E [m].j E [n]. [[, ll2 S du/m and (V((..) S /du/n.
small ju guarantees that the signal in and is sufficiently spread out among the rows 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 is that for any value function V, the Bellman update of any value function, Qn = Th + P2V, 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 exists S x S x tensors Um,h, S S x d' tensors Un s, A x d ji-incoherent matrices Gm,h with orthonormal columns, A x d' u-incoherent matrices Gy with orthonormal columns, and S x matrices Wm, S x d' matrices Wa. such that
(s (8) = Eie(d) (a,(a,,))m,,a ()m,,) 8,5), (m, a) = Eveta Gm, (a, (,mmm...,
Pa(S'1s,, a) Eiejan (n 8, (n( - Gn (s,
where 11 E g(5 (s'm :22 Eves (s',), (s) [ (m,n(s))l V (ddp)) for all s E S, E A, h E [H) and m E [Mr any function g S + [0.
The latent representations of the reward function and transition kernel are not unique under our assumption. Figure I visualizes the low rank structure Assumption [ jimposes on the transition kernel. While Assumption 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), the space spanned by the target latent factors is a subset of the space spanned by the latent factors from all the source MDPs.
5

---

Assumption 2. Suppose Assumption 7 holds. The target MDP latent factors GR. and source MDP la- tent factors Gm,,h satisfy for all h E [H], Span((G (ee(a)) S Span( [Gm, h (e))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 {Gm.b) of the source MDPs, we can construct approximation of the target features [G without interacting with the target MDP, which is essential to transfer learning. Assumption Tonly upper bounds the rank of Qmn, by d. However, to learn each source latent factor, one needs to obtain good estimate of rank 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.
ssumptton For each m E [M, E [H], the optimal Q-function of the m-th source MDP at step h satisfies rank(Q = d and [|Q m ol C. for some C IR+.
This assumption allows one to learn the near-optimal Q-functions from noisy samples of the source MDPs. Assumption and its variants are common in the literature of noisy low-rank estimation [ Without the above assumption (the rank of Q' is strictly less than d), then one cannot learn every latent factor Gm.a( i) since it may have a zero singular value, and thus using the approximate feature mapping would result in regret linear in T. Similarly, ||@"||>o 2 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.
4 Transfer-ability
Our transfer-ability coefficient is motivated by the following observation. Under Assumption we can construct each target latent factor Gs, with linear combination of the source latent factors Gm,b- The magnitudes of the coefficients correspond to the difficulty in estimating the target latent factor because the estimation error of m. is amplified by its coefficient. Thus, when these coefficients too large, transfer learning is essentially impossible; one example is when the source latent factors almost identical parallel 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 QT,,, , and target latent factors {Gr} are not unique, each choice of latent factor results in a different set of coefficients. Thus, we introduce B3 as the set containing all such coefficients given the subspaces from the target and source MDPs. Let Gs.A be the set of all 5 orthonormal latent factor matrices with columns that span the column space of Q
for all m e [M], and let Gr. be the set of all 5xd' orthonormal latent factor matrices with columns ) for all s' e S. Then, we define the set B, (G G5,,) to contain all such coefficients, i.e., B, Rdd d.MM and B, E (9 . Gs,s) if there exists G2, E Gr. Gm,,h E Gs.k such that for all i E [d']. h E [H] () ΣEe [. Ba (t, m.).m.(-...) Now, we define which precisely measures the challenge involved in transferring the latent representation.
that span the column space of (s')
Definition 3 (Transfer-ability Coefficient). Given a transfer RI. problem that satisfies Assumptions ! and3 with the definition of B₁, above, we define a as
a max H
min (9 (Ed1)
max B(i, J.)]
Note that the minimum is taken over all latent factor matrices. When there is only one source MDP. is small, i.e., less than equal to one, because the columns of G form orthonormal basis of the space containing the target latent factor. In the best case, a is 1/ddM) (see Appendix D). On the other hand, when there multiple source MDPs, case, the estimation error of G and G2 are amplified by a when estimating GT using G and G2- We remark that adding more source MDPs or increasing the rank of Q will not increase can use the same set of coefficients without the additional source MDP larger subspace of Q Or... See Appendix D for more discussion a.
be arbitrarily large as in Figure in this
one

---

Our transter-ability coefficient is similar to the quantity Omax defined in 44. While these terms both quantify the similarity between the source and target MDPs, our setting, we allow for the source MDPs' state latent factors, (Gm,h), ), to differ from target MDP's state latent factors while [4] assumes that all MDPs share the same latent representation σb Our setting more general than the one even when assuming the same Tucker rank assumption.
4.1 Information Theoretic Lower Bound
To formalize the importance of a, we prove a lower bound that shows that a dependence on a in the sample complexity of the source phase necessary to benefit from transfer learning. Before proving our main result, we first present an intermediate lower bound to provide intuition on how a measures the difficulty in transferring learned representation.
Theorem 1. There exist two transfer RL instances such that (i) they satisfy Assumptions and (ii) they cannot be distinguished without observing S2(a²) 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 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 states that without observing !?(a?) samples in the source MDPs, one cannot learn good policy in the target phase with or G", and one should disregard the information from the source MDPs and use non-transfer learning RL algorithm to achieve regret bound that scales with VT. Therefore, (2(a2) samples are required benefit from transfer learning.
To prove Theorem 1 we construct two S,) transfer RL problems that satisfies Assumption 2 with similar source action latent representations G E G but orthogonal target action latent representations G for E [1,2]. To avoid learning the incorrect representation, one must identify the transfer RL problem by differentiating the Q"s. s. By construction, the Q's for the two transfer RL problems differ by at most 1/a entrywise, so one must observe (?a²) samples in the source problem from standard hypothesis testing lower bounds [5]. Observing less samples in the source problem results in an estimate orthogonal the true target representation with constant probability. See Appendix for the formal proof. One can easily prove 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) and G
Algorithm
We now present our algorithm that achieves the optimal dependence In the source phase, algorithm can use any algorithm that learns c-optimal Q functions on each source MDP. As the error bound on the estimated feature representation depends the incoherence of Q" Q use LR-EVI,
which combines empirical value iteration with low rank matrix estimation (30 After obtaining estimates Qm,h Q'm, our algorithm computes the singular value decompositions (SVDs) of
each Qm.h construct the latent feature representation G' by scaling and concatenating the singular vectors. Then, in the target phase, our algorithm deploys 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 define k. (K' [k]] $ s), which is the set of episodes before k. in which one at time step h.
Algorithm 1 Source Phase
Input: {Nuhne(m)
1: for m E [M] do
2: Run L.R-EVI((NNA)eeei))) on source MDP m to obtain Qm.h-
3: Compute the singular value decomposition of Qm.h. Fm Sm.h GT
m.h
4: Compute feature mapping & (G (Gr)netm with G 1 du [G1,
GmA..
LSVI-UCB-(S, S, d) uses the same mechanisms as LSVI-UCB, but we compute coefficients and Gram matrices for each action. Specifically, we update the weights wi with the solution to the
7

---

Algorithm 2 Target Phase: LSVI-UCB-(S, S.
Input: X. 1. G 1: for E [K]d do
2: Receive initial state st.
3: for = H..... do
4:
for s E do /* Compute Gram matrix A for each state s */
5:
6:
Set Ag, + EiETy (n(d)) AI
7:
/* Estimate wh. via regularized least squares */
Set " + (AA) " Ex(ah) [ra(s, (/) + max (s+ a')
8:
9:
/* Estimate Q' via the low rank structure with optimism */
10: Set Qu(-,)) min (1, (wh, Gn(+) + PK. VGN()
for [H] do Take action a + max,cd Qs a), and observe +/111
regularized least squares problem,
- < arg min Eiery, (rn(s, + max.'e (1+2($h+1, w Gn(a))) WER'
A//w112
using the reward when was observed and add an exploration bonus 32,, to our estimate of Q", which common linear MDP/bandits algorithms 1 Multiplying the latent factors by / (A/(du) 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.
( (A.))
While one may wonder why modification of LSVI-UCB necessary, Algorithm 2 improves the regret bound by factor vS compared to using any linear MDP algorithm off the shelf; reducing our setting to a linear MDP results in using feature mapping with dimension dS. Thus, using any linear MDP algorithm results in a target regret bound of S2 H2T) [4]] However, our algorithm shaves off factor of vS as our algorithm computes S copies of d x d dimensional gram matrices in contrast to the d2 52 dimensional gram matrices used in linear MDP algorithms.
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 and A in the target problem. We first state our main result in the (S, d) Tucker rank setting.
Theorem 2. Suppose Assumptions 2 and 3 hold, and set ō E (0,1) 1). Furthermore, assume that, for any E (0, /SH/T), Qm,h Tmm + Pm. Vn,h+1 has rank and is p-incoherent with condition number K for all c-optimal value functions V1+1- Let = and Sh.n be function of [S),M. d, H, (T 1S), M,T. T. Then, for Z in the source problems, our algorithm has regret ((V(dMH)AST) with probability at least 5.
S a² using at most O(d' ((d")(²ne n A/S) aT) samples
Theorem 2 states that using transfer learning improves the performance 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 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 El for the proof of Theorem 2
For sake of brevity, we present our results our other Tucker rank settings in Table (see Appendices G and H for the formal statements and proofs). In each of our Tucker rank settings, our algorithms use transter 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 and 10 may seem to not scale linearly in A and S, respectively, we require the horizon in the target phase be large enough, i.e. (S/A + 1) 2 S + A and (1 + A/S) 2 S + A, respectively, so that one observes at least Q(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 d.M 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 -iM-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 the cost of an increased sample complexity (by factor of A) in the source phase (see Appendix C
Comparison with [4]: In comparison Theorem 3.1 from [4) our result, Theorem 14 has similar dependence on A, d, H, and T while our dependence on a is optimal compared to their a dependence g While our dependence on M in the regret bound is worse, this is due our transfer learning setting being more general; we only require that the space spanned by the target features be 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 2 Theorem 10 15 and 14 synthesize the theoretical guarantees of LR-EVI, singular vector perturbation bounds, and LSVI-UCH or our modification of L.SVI-CB.. Given N samples from the source MDPs, we first bound the error between the singular subspaces up to a rotation by M + 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 is dominated by the original regret of using the true representation.
6.1 Discussion of Optimality
In the 4), (S, S, d), S, and (d, d) Tucker rank settings, the source sample complex- ity's scalings concerning S, A, H. and T are reasonable when learning VA/T, VS/T, VI/T, and /I/T-optima Q functions, respectively, given the Q learning lower bounds in [30]. Similarly, the dependence on μ and
standard for RL algorithms incorporating matrix estimation.
In the (S, A), (S, S, d), and (d, S, A) Tucker rank settings, our a² dependence in the source sample complexity is optimal due to our lower bounds. In the (d, d, d) Tucker rank setting, our a' dependence is likely optimal when eliminating the dependence on and A the target problem; one must combine both sets of singular vectors together, F S - RRM and G A + RdM, to create feature mapping é= : S x A + Rd which causes the a dependence in our upper bound. However, if a² is too large, one can use the algorithms from the (5, d, A) or (5, S, d) Tucker rank settings to benefit from transfer learning. Proving an a 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 of M² dimensional space in contrast
space with dimension d.M.
The regret bounds of our algorithms used in the target phase, i.c., Algorithm 2 Algorithm 4 and LSVI- UCB [17, in each Tucker rank setting 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 ((VdS H2T). However, our dependence on d and H are sub-optimal. The extra factor of /H HH is likely due to our use of Hoeffding's '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- sub-optimal with respect to d; for linear MDPs, LSVI-UCB++
1 admits a regret bound of Ó(V H2T), 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.
'Since 2 moving & into the source sample complexity yields sample complexity that scales with a².

---

7 Conclusion
We study transfer RL, in which one transfers latent representation between source MDPs and target MDP with Tucker rank (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 kemel is low rank. Furthermore, we propose the transfer-ability coefficient that quantifies the difficulty transferring latent representa- tions between the source and target problems with information theoretic lower bounds. We propose computationally simple algorithms that admít regret bounds that are independent of S, A, or SA depending 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] to our setting, which is an interesting open problem. Furthermore, proving theoretical guarantees of other forms of transfer RL is worthwhile and an interesting future direction.
Acknowledgements::
Y. Chen is partially supported by NSF CCF-1704828 and NSF CCF- 22.3123
References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. ShawerTaylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. hmtps:/aarti.orrgaa///0000000000 48, 09 2017.
[3] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20095-20107. Curran Associates, Inc., 2020.
[4] Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning, 2023.
[5] Martin Authony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, USA, 1st edition, 2009.
[6] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. On the sample complexity of reinforcement learning with a generative model. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, page 1707-1714, Madison, WI, USA, 2012. Omnipress.
[7] Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111-11,, 2012.
[8] Emmanuel Candes and Justin Romberg. Sparsity and incoherence in compressive sampling. Inverse problems, 23(3):969, 2007.
[9] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM Journal Optimization, 30:3098-311 3121, 01 2020.
[10] Yuan Cheng, Songtao Feng, Jing Yang. Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning, 2022.
[11] Yuan Cheng, Ruiquan Huang, Jing Yang, and Yingbin Liang. Improved sample complexity for reward-free reinforcement learning under low-rank mdps, 2023.
[12] Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An fox eigenvector perturbation bound and its application to robust covariance estimation, 2016.
10

---

[13] Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforce- ment learning for linear markov decision processes, 2023.
[14] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
[15] Haque Ishfaq. Thanh Nguyen-Tanne Songtao Feng, Raman Arora, Mengdi Wang, Ming Yin, and Doina Precup. Offline multitask representation learning for reinforcement learning, 2024.
[16] Yassir Jedra, William Réveillard, Stefan Stojanovic, and Alexandre Proutiere. Low-rank bandits via tight two-to-infinity singular subspace recovery, 2024.
[17] Chi Jin. Provably efficient reinforcement learning with linear function approximation. 2020.
[18] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient?, 2018.
[19] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In ICML, 2020.
[20] Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. In M. Kearns, S. Solla, and D. Cohn, editors, Advances in Neural Information Processing Systems, volume 1. MIT Press, 1999.
[21] Jens Kober, J. Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11): 2013.
[22] Tor Lattimore, Csaba Szepesvari, and Gellent Weisz. Learning with good feature representations in bandits and in rl with generative model, 2020.
[23] Rui Lu, Gao Huang, and Simon S. Du. On the power of multitask representation learning in linear mdp, 2021.
[24] Osman Asif Malik and Stephen Becker. Low-rank tucker decomposition of large tensors using tensorsketch. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
and
[25] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013.
[26] Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. CoRR, abs/2102.07035. 2021.
[27] Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 12(10):1345-135, 2010.
(28) Sergio Rozada and Antonio G. Marques. Tensor and matrix low-rank value-function approxi- mation in reinforcement learning, 2022.
[29] Sergio Rozada, Victor Tenorio, and Antonio G. Marques. Low-rank state-action function approximation. In 2021 29th European Signal Processing Conference (EUSIPCO), pages 1471-1475, 2021.
[30] Tyler Sam, Yudong Chen, and Christina Lee Yu. Overcoming the long horizon barrier for sample-efficient reinforcement learning with latent low-rank structure, 2023.
[31] Kun Shao, Zhentao Tang, Yuanheng Zhu, Nannan Li, and Dongbin Zhao. A survey of deep reinforcement learning in video games, 2019.
[32] Stefan Stojanovic, Yassir Jedra, and Alexandre Proutiere. Spectral entry-wise matrix estimation for low-rank reinforcement learning. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances Neural Information Processing Systems, volume 36, pages 77056-77070. Curran Associates, Inc., 2023,

---

[33] Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps 2021.
[34] Bingyan Wang, Yuling Yan, and Jianqing Fan. Sample-efficiet reinforcement learning for linearl-parammeterized mdps with generative model, 2021.
[35] Xumei Xi, Christina Lee Yu, and Yudong Chen. Matrix estimation for offline reinforcement learning with low-rank structure, 2023.
[36] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10746-10756. PMLR, 13-18 Jul 2020.
[37] Lin F. Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In ICMI,, 2019.
[38] Yuzhe Yang. Guo Zhang, Zhi Xu, and Dina Katabi. Hamesssing structures for value-based planning and reinforcement learning. In International Conference on Learning Representations, 2020.
[39] Xuezhou Zhang, Yuzhe ma, and Adish Singla. Task-agnostic exploration in reinforcement learning, 2020.
[40] Xuezhou Zhang, Yuda Song, Masatoshi Uchara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach, 2022.
[41] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes, 2021.
12

---

Contents
Introduction
2
Related Work
3
Preliminaries
The Tucker Rank of a Tensor
Low Tucker Rank MDPs
Transfer-ability
Information Theoretic Lower Bound
Algorithm
6
Theoretical Results
6.1 Discussion of Optimality
7
Conclusion
10
Notation Table
14
Table of Regret Bounds with Known Latent Representations
15
Thresholding Procedure in the (S,S.d) d) Tucker Rank Setting
15
Thresholding Procedure without Knowledge of d"
15
D Properties of the Transfer-ability Coefficient
16
Omitted Proofs the (S,S.d) Tucker Rank Setting
18
Proof of Theorem
19
Proof of Theorem
20
Proof of Theorem
(S,d, Tucker Rank Setting
24
Information Theoretic Lower Bound
25
F2 Simulator to Simulator Transter RL.
29
(d, S, A) Tucker Rank Setting
33
H (d, dd Tucker Rank Setting
39
eigen perturbation bound with non-uniform noise: rank-r case
42
Proofs of LSVI-UCB-SS, d, A) and LSVI-UCB-SS. d)
44
J.1 LSVI-UCB-(S. A)
45
13

---

J.2
(S
54
A
Notation Table
Symbol
Definition
S,8
State space, Cardinality of
A, A
Action space, Cardinality of AA
H,K
Finite Horizon, Number of Episodes (T KH)
M
Number of Source MDPs
Tm,hs Pn,hs-Pm.h
Reward Function, Transition Kernel for Source MDP m at step
The Pa
Reward Function, Transition Kernel for the Target MDP at step h
Q me Q
Action-value Function Step h Following for Source MDP and the Target MDP
Vm Qi
Optimal Action-value Function at Step for Source MDP m and the Target MDP Value Function at Step Following π for Source MDP m and the Target MDy
V he VÆ
V m,ko VR
Optimal Value Function Step h for Source MDP and the Target MDP Rank the Low-dimensional Mode Pm,h Rank the Low-dimensional Mode Pa. Transfer-ability Coefficient
d
d'
a
(a),
True Latent Representation of Each Action in the Source and
Target MDPs the (S, S, d) Tucker Rank Setting Concatenation of Gm,h for m E [M]
G On LR-EVIO.)
Latent Representation Estimate Computed in the Source Phase
Low Rank Empirical Value Iteration
Ag
Gram Matrix for State at Step f
wf
Regularized Least Squares Solution for State Step h Episodes before Episode in which one was at State s Step h
T
p(X)
Incoherence Matrix
<(X)
Condition Number of Matrix X
xx(
i-th Singular Value of X
|
Operator Norm of Matrix
||
Maximum of the Absolute Value of Each Entry of X
Table 2: List of notation
14

---

B
Table of Regret Bounds with Known Latent Representations
Tucker Rank
Regret Bound with Known Latent Representation
Theorem Theorem g
S,
(S, A)
O(Vd&1+AT)
Theorem 3.1
[d, S, A)
O(vdHHT
Theorem 5.1 [13.. Theorem 5.6 [41]
(d)
è VVHHTT
Table 3: Theoretical guarantees of algorithms alongside results from literature in the different
Tucker rank settings. To the best of our knowledge, there are no algorithms tailored to the (d, d, d) Tucker rank setting. Instead, one should use linear MDP algorithm.
Since each Tucker rank setting captures tabular MDPs, we can construct lower bounds with a reduction from the bound in [8]: in the (S, d, .A) Tucker rank setting, the regret is at least (VdAHT))) and in the (S, S,d) d) setting, the regret is least 92 ((dAHTT)) As mentioned, our dependence d and H are sub optimal because we modify LSVI-UCB [17], which has sub-optimal dependence on d and H. Modifying the algorithm from [13 achieve the optimal dependence d and in the
(S, S, d) and (S, d, A) Tucker rank settings is an interesting problem for future research.
C Thresholding Procedure in the S,, Tucker Rank Setting
When the feature representations of each source MDP lies in orthogonal d-dimensional subspaces, 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.,
(VT
rank (Gn) rank
[Gi,1 du
GMr,A] d"
for d' S d" < dM (recall the target MDP has Tucker rank (S, S,d'), we use the following procedure: after computing G via concatenation of Gm,, for all m E [M], we perform singular value decomposition of Gj and threshold the singular values to keep only d" dimensions. With this procedure, our regret bound now depends on d" instead of dM at the cost of an increased source sample complexity. We only present the theorem and proof in the (S, S, d) Tucker rank setting, but our results and methods extend to the other Tucker rank settings.
2 and 3 hold, and assume the source MDP latent factors span a d" dimmensioonnl space. Let å E (0, 1). Furthermore, assume that, for any e (0, / (SH/TT) Qm,h- Tm,h + Panti V Vm,++1 has rank d and is p-incoherent with condition number for all optimal value functions VA+1- Let X = and 3%, J. be a function of d, H, HT,Ti [S], M,T. Then, for T 2 3. using at most ( ( A H H* (Sdd)( samples in the source problems, our algorithm has regret Ö (d(d ST) with probability at least
Theorem 3. Suppose Assumptions
The proof Theorem 3 follows the proof of Theorem 2 except we require a larger source sample complexity guarantee with high probability that the d' 1-th singular value of the concatenated fea- ture representation sufficiently small. With this procedure, we ensure that our feature representation removes the unneeded dimensions. See Appendix E for proof of the above theorem.
C.1 Thresholding Procedure without Knowledge of 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 the misspecification enror will still be small. The specific procedure is follows:
15

---

after performing the singular value decomposition on the concatenation of Gm, we first find the smallest value of E [dM] that satisfies
tHSdp
0++1
S
and threshold 0111..... OdM- Let
E S
LHS aTT t)MP
T =
be the set of that satisfies the inequality on the singular values. Then, with the specified procedure, our algorithm admits target regret bound that depends instead of d.M Note that t is minimally 1 and at most d.M.
Theorem Suppose Assumptions 7 and Phold. Let ô (0,1) and mingeT t. Furthermore, assume that, for any E (0, WS/HSTT =m.==mmm Tm.h Pm,h Vm,b+1 has rank d and is p-incoherent with condition number K. for all e-optimal value functiinn Vn+1- Let X and fk.h be a function of
d, H, [ IS),, M,T. T. Then, for T 2 az using at most ((d 1t Af + A in the source problems, our algorithm has regret ((((H))55 with probability least 5. 5.
samples
With an increase in 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 for the proof of the above theorem.
D Properties of the Transfer-ability Coefficient
In this section, we prove properties of and provide easy and hard instances. values of a.
We first bound the
Lemma 1. Let a be defined according to Definition Then, we have that aMd S a < cc.
Proof. Since Assumption holds and that the latent factors are normalized, it follows that for all i [d"] and any latent factor matrix,
[L 0) =11
Σ
Ba(i, j, (;..)ll
mE[d)
15
Σ
(B)
jE(d).mE[MM]
Σ
(B),,
SE(d).EE[M)
Given that Eyeld mE[a) (B, it follows that the minimum of 1
maxje(d]mmE[M) (I, m)l is attained when [B (i, m)] aM Thus, 2 aM
Let y E 10. Consider the construction where the target latent factor is Fr [1, 0] and the source latent factors from source MDPs one and two are
F
7.7 1].
Fg = 7, -7-7V//7> 1].
Clearly, the latent factors are orthonormal. Then, it follows that the only linear combination of Fi and Fg that results in is
Fj cFi + cF2,
which implies that 2-25 Thus, 2ー and it follows that we can make arbitrarily large because for any positive constant C, we can choose 7 that C.
16

---

As the proof of Lemma] Juses a construction in which a 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 a M. Next, we consider the construction where
1
Fr.
v
vd
and there are M source MDPs with the standard basis vectors in I' as the latent factors equally distributed among the .M rank one source MDPs. Thus,
Vd
Fr = Σ MEM
Fm.
M
and a = vd/M.
We next present transfer RL instance with large a. Consider the following construction with the goal of trying to transfer the state latent factors. Without loss generality, let the size of the state space and action space be 4n for
N+- Furthermore, we refer the i-th quarter of the states as 8; for E [4] and the i-th half the actions as a; for E [2] because our construction is a block MDP with four latent states and 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 of notation, refer to the i-th as any state in 8 and the i-th column as any state in ag. The target MDP's latent factors are
(2n)
0
(2)
0
(1)(2n)
/8())) V/((8n] ].
VI/(8n) VT/(8n)
1/(2n)
Fb
W1
W2
1/(2n)
v1/(2n)
/1/(2n)
1/(2n)
for all h E [H). and
(si)) (n(22/a1) 1V22((8/).
(21 (02) = (n(22/22) 322
(n(ss)a1) = (n(ssla1) [322/
(2) (s4l2)))) 32
Thus, the reward functions and transition kernels for the target MDP are
2p
4n
2
4p
4p
4p
1p
2p
2p
4m
2n
2n
and the transition kernels are
3
8g
87
:h(sils))) (s2l::))
(r(ss))))) = Ph(sal:))
8p
8gi
8n
8n
8n
for all h E [M]. Using the Bellman equations, it follows that the optimal Q function for the above MDP
13
15.
1
16gg
16m
47
47
Qi
16m
16m
Qi
4p
4p
16/1
I6m
275
27
16n
and both Q's have Fù as orthonormal latent factors. Next, we present the orthonormal latent factors for the first source MDP
1/v2n
1/ 44n
- 1/222m
1/
3/V4n
3/V4n 1/V4n
1//4n
1/V4n
FiA
Wi,1
,
1/v4n
1/v4n
2/v4n
2/ V 4n
1/v4n
17

---

It follows that the reward functions are
(3 + 3v2) (/2) (4n) (1 + (4))
(1+ v (2))
(1 + 22)/(2n)
(3 - (3-3v2) 3/2)/
(1 (2)
(1 v (4m)))
(1
(2)/(2n)
11,1
(4n)
1/(4n)
112
(4n)
1/ 12(2))
3/(4n)
1/(4n)
1/(4n)
1/(2n)
with (-).(-):-)- = 1/4)... Since PL, is the uniform transition kernel (which has the second column of Fi,h its latent factor), it follows that (V (.,)) is rank matrix with every entry being the
same positive constant. Thus, Qi, = T1,1 + Pi, V12 and Qi.2 = 71,2 are rank two matrices with Fi,A latent factors.
The second source MDP has the following latent factors
I cBvan
1/v4n 1/v4n
<v2n
1/v2n 0
0
0
1/v2n 2n
F2,1
2/2n
cBvan
12,1
W2.2
-1/lc3v /4n) 4n) -1/Cc3
1/v4n
1/v2n 2n
1/v2n
0
1/v4n
where V 1//2 for all h E [H] with :). = = 1/(4n). Since P2,1 is the uniform transition kernel (which has the second column of F2, as latent factor), follows that (-))( a rank one matrix with every entry being the same positive constant. Thus, Q2, 2, P2. 22 and Q2 r2,2 are rank two matrices with 2 as latent factors. Now, we prove that (2()).
Corollary 1. Consider the above construction that satisfies Assumptions and Definition satisfies a E (233).
Then, defined in
Proof. Consider the above construction with 3 > O. First, we show that when expressing the first
column of Fú, as a linear combination of the columns of Fi, and F2, one coefficient (
We first note that one must use the first column in F2,1 or else the system of linear equations is inconsistent. Thus, solve
1/ 2n
1/ /4
0svan cv 2n
+
1/ 222
- lv 2n
1/ V 44n
1 V
+ b
+d
cv2n covin
0
1/v4n
-1/(cBV4n)
0
0
1/v4n
11(cBV/Am)
0
It follows that d = bcB. Thus, 1/V2, and d ((3) because < 1.
To show that E (().). we assume for sake of contradiction that there exists some set of basis vectors Fy, and F2, that span the subspace defined by Fi, and F2, respectively, such that we can express the any rotation of the first column of F3 as a linear combination of the columns of Fí,,, and F2, using coefficients a, c, d such that |a]. [b], |cl, |d E o(3). Since Fn, Fin, and Fe, orthonormal latent factors, it follows that there exist rotation matrices R. R2, R2 with || R Iloo R2 bl O(1) such that FL, R2 F1, and 22,, Rg F2 It follows that R-1 exists and has entries with constant magnitude. By construction we have
(r aR- R2 (1. bR- Fi, cR R2 dR R2F2
Since the entries of the rotation matrices and their inverse are bounded by a constant, the above equation states that can represent the first column of FA a linear combination of the columns of Fi, and F2, using only constant coefficients. Thus, we reach a contradiction because we' ve shown that one entry of dR R2 E 2(3). Therefore, a E 0(3).
E Omitted Proofs in the (S,S.d) Tucker Rank Setting
We first prove our lower bound.
18

---

E.1 Proof of Theorem 1
Proof. Suppose all source and target MDPs A. P. share the same state space, action space, and horizon H = 1 and assume that S = A = [2n] for some n E N For case of notation, we let 81 and 01 refer to any state and action in [n)] respectively, and 82 and ag refer to any state and action in {n + .... 2n). respectively. We will present the latent factors and optimal Q functions as block vectors and matrices with 81, 82, 01, 42 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 81, 82 and columns 11 (2) that satisfy Assumptions] orthogonal target state latent factors. For ease of notation, the superscript i of Q 2, denotes transfer RL problem for i E (1. Then, the optimal Q functions for transfer RI. problem one are
[anttiiooonnnn] and but have
V/nn
v1/(2m) = 1/v2
1/v2
21, n
[vI/(2n)
0
0
0
0
0
0
22
[v1/(2m)
v1/(2n) = 1/V2
1/n
1/v2
(2()2)
1/2
1/2
o1
[VI/(2n)
11((2)] =
-V11(22)
-1/2
- 11/2
and the optimal Q functions for transfer RL problem two are
1/n
1//2 1/v2 0
07,1 = n
vI/(2n) 1/(2n)
=
0
[
[
0
0
221 = n
G' =
1/n
(1+1/a)/
(1 - (1-1/)/(cV2)
V (2)(2)
1/2 -1/2
01 2
11/(2))
[2n)
(27)
-1/2
1/2
where
G' = (22)) + 1/(2na²)) /) 1111/22 (vI/(2n)
(2(2222)) //
+ 1/02
and c= c= /1+ 1/22. Note that C (1, 2dM) because a 2 1/(dM) from Lemma for a >> 0. The incoherence μr, rank d, and condition number of the above Q functions are O(T). Furthermore, the above construction satisfies Assumption with Tucker rank (s, S, 1) and Assumption because the source and target MDPs share the same action latent factor [VI/(2n) transfer RL problem while in the second transfer RL problem,
vI/(2n)
in the first
[V2/(2))
[V/((2)] = =a [ 1/2m)
V + acG'.
Note that G¹ factors of the different transfer RL problems are orthogonal to each other.
[22)(2n)
vI/(2n) and G² [VI/(2m)
-V1/(2n)] the target latent
The learner is given either transfer RL problem one or two with equal probability with generative model in the source problem. When interacting with the source MDPs, the learner specifies state- action pair (s, a) and source MDP m and observes a realization of shifted and scaled Bernoulli random variable X. The distribution of X is that X with probability (QTi, (s, a) + 1)/2 and
X = 1 with probability (1 Q'i, (s, a))/2. Furthermore, the learner is given the knowledge that the state latent features lie in the function class G {G', G2) } 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 Q711 and I. By construction, the magnitude of the largest entrywise difference between Q and Q is lower bounded by 2(1/a).
If the learner observes Z samples in the source MDPs, where Z < O(a²) for some constant C > 0. then the probability of correctly identifying
upper bounded by 0.76 (Lemma 5.1 with 8 = 0.24 5).. Thus, if the learner does not observe 12(a²) 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.
D
19

---

E.2 Proof of Theorem 2
We first present the theoretical guarantees LSVI-UCB-(S, S. d) and defer their proofs to Appendix M
Theorem 5. Assume that Assumption holds and the learner is given the tuee latent action repre-
sentation G [Gn ( Then, there exists constant > 0 such that for any ó E (0, 1), if we
sel X = 1, 38., cdH VL. log(2dTS/)) S/6), then with probability at least 1 - 6, the total regret of Algorithm is O(VdSSHTT)
Theorem states that LSVI-UCB-(S, S, d) completely removes the regret bound's dependence the size of the state space by utilizing the latent action representation G. Similarly, the algorithm is robust misspecification error.
Assumption 4 (6-approxemate (S, S. d) Tucker rank MDP). Assume & E [0. 1]. Then, an MDP (8, A,P,P,P Prr, r H) a E-approximate (S, S, d) Tucker rank MDP with given feature map G if there exist H unknown S-by-d matrices W = (Wn (W.heEHH) hE[H and S-by-S-by- tensors U = (Un.)eett such that
(r)(s,a) Wa((s) Gn(a)) E
Σ (Ph(5'ss, - Un ())((a) SE
R'ES
for all h E [H] where ||Wall2, E ( (s a)ll s v VA/(du) for any function : S [0, 1].
Theorem 6. Under the Assumption for any 8 E (0, for X 1,8%, = O(Hd + EVidH) for S/68), the regret of Algorithm is Ö EdHT) with probubility at least 1-6. 6.
We now prove Theorem
Suppose the assumption stated in Theorem hold. Then, from 30,, running LR-EVI with a sample complexity of C'd C"ddtu"n' ( + A)M H (2g on each source MDP results in Qm,b functions with singular value decomposition Qm,h Fm, Em.h that are (H6/(1aapp (MT))-optima with probability at least - 8/2.
Proof.
Since our estimates are VHS/ /HS//116aws (16ok) (MT))-opimall it follows that 7 < 1/2 in the singular vector perturbation bound, Corollary 3 Since ||Q oo 2 C, from Corollary follows that there exists rotation matrices Rm,, such that
dvHpS
(GG.ABmm - Gm,.)(a)l22
av AMT
for all E A where the optimal Q function have singular value decomposition Q Fm, Emm. GT m.h.
Let & be the dM matrix from joining all the source action latent factor matrices, and &₁ be the A x dMM matrix from joining all Gm..h- Let R, be the d dM matrix that joins Rm,, for all and Definition 3 it follows that for all (s', 8, s, SSX A,
m E [M]. Then, from Assumption 2 that
The (s a) Σ is
tE|d
Σ Σ
Bl..j. in(s,
mEld #Eld
Bl..j.m)GmAaa..WW....
20

---

and ...) (s)) (with the same argument) for some S x dM matrices W U (/((') with entries bounded by a. Note that Wi and (s') are matrices that join W Wn,h and U un (5').
respectively, with entries that at most a times larger than the original entry.
Therefore, it follows for all (5', 8,,8,,, E
A [M].
rh (8, a) (..s.,))GGr(a))AAA ((( (G((a)WX(t) - (
= - (asla)--nnoaa ((())))W((()
S al Σ (Gm,((a) Gm, (m.
Σ [[mm,((a) Gm,m Rm (
A
[[mm,((a) (m)
MEM
dHMS
T
from the Cauchy-Schward inequality and our singular vector perturbation bound. From the same logic,
Σ
= Σ (n(a)U((((s)) - C
EES
s'ES
(Gn(la) Gn(a)Ra) Σ U)(
E'ES
al Σ (Gm,h(a) (a), Σ (
meM
s'ES
Σ Il(Gm,((a) Gm, Rmm
Σ Um,n('', TT
s'ES
dHMS
T
Therefore, (a) satisfies Assumption 4 with JMHS
Then it follows that rumning LSVI- UCB-TR using Ga((a with 8' 5/2 during the target phase of the algorithm admits regret bound of
|MHH
(egret(T) S C" (VTM3H2ST + dMHT
E Ö(VIMM>HPST)
T
with probability at least - 8 from final union bound. Furthermore, the sample complexity in the source phase is
d' (S AAMM)
which proves result.
E.3 Proof of Theorem 3
Proof. Let the assumptions of Theorem hold. Then, from 30 running LR-EVI with a sam-
ple complexity of C'd' pº A(S a AdMH (5/HH/////0/ 50//55/((( each source MDP results in Qm, functions with singular value decomposition Qm,h Fm &mm that are / VHd"S (11Ga/M rdd / -optimall with probability at least 8/2.
Since our estimates are H S/ (7rd"5//(11gg/aaa (16guMad2 VAT) ooptimal,, follows that 7 < 1/2 the singular vector perturbation bound, Corollary Since ||Qr, ll C, from Corollary it follows that there
21

---

exists rotation matrices Rm.h such that
uS Il Rm.h Gm,l)aa)llz - aAM vdT
for all E A where the optimal Q function have singular value decomposition Qm.A
Fm, Sm.GGmm
Let G be the A x dM matrix from joining all the source action latent factor matrices, and Gn be the x dM matrix from joining all Gm.h- Let R2 the dM matrix that joins Rmnh for all E [M]. Then, from Assumption and Definition 3 it follows that for all (s', 5, E S A. that
(s, a) Wx(s,
EEI
Σ
B(i,j,m) (l..jam) (s)
jEld,mE[M
E
Bl..j.m)G,plaa.)WW..
mE(
((a))
and -) (s) (with the same argument) for some S x dM matrices W (6))) with entries bounded by a. Note that Wi, and (s') are matrices that join W m. and U respectively, with entries that at most a times larger than the original entry.
- Let F= Gr Gn. where [ ..i Em]. We next bound the d" smallest singular value of G₁ with our singular vector perturbation bound ( [| S (1
(.)4)(Gh)) a. -ar + |op S F| S AVAMT
VHd"
With singular value decomposition &n XΣYT, let Gt be the thresholded feature representation estimate, i.c., G = X(:,: d') d d (;, dT. Therefore, follows for all (s', 8, a, h) e
S SxSxAL Ax [H].
(s) Gh (s.,: I')
= (S) T - G (a)Ra d')Ti
(+) - -.(())RAW()))) + (( G d")
sal
Σ (a) -mm, -m,, Rm.) (G, +1:)WA(s,d d" +1:)
mEM
< a
Σ [[Gm, Gm.n(a))an
ao (IGh)VVM
Σ
[Wm,blll
mEM
me [M]
< a
Σ
[[Gm,((a) -
+ (6
dj
MEM
d" HS
T
from the Cauchy-Schwarl incquality and our singular vector perturbation bound. From the same logic,
d HS
Σ (Pa(s')s, Un(s', s) (a) &
T
S'ES
22

---

Then it follows that running LSVI- Therefore, G (a) satisfies Assumption with ç = V
UCB-TR using G (a) with 8' = 6/2 during the target phase of the algorithm admits regret bound of
H"
Regret(T) - (V (d'")'HHTTT + HT
HT
E (dv(d")HHTT)
T
with probability at least 8 from final union bound. Furthermore, the sample complexity in the source phase is
δ d 1 pu (A A H
Sd"
which proves our result.
We now prove Theorem
Suppose the assumption stated in Theorem 4 holld Then, from 300, running LR-EVI with sample complexity of C' d'd'pt d'd"yrn*"S + A)M² H a AGM on each source MDP results Qm,b functions with singular value decomposition Qm, Fm. Em & that are MPT) -pptimal with probability at least 1 5/2.
Proof.
it follows that < 1/2 in the singular vector perturbation bound, Corollary Since [Qm,, 2 C, from Corollary follows that there exists rotation matrices Rm,n such that
Since our estimates are / (P
VHdpS
[lGm.B (m)a) S
av AVAM2T
for all E A where the optimal Q function have singular value decomposition Q Fmch Fmm G m.h-
Let & be the x dM matrix from joining all the source action latent factor matrices, and Gb be the x d.M matrix from joining Gm... Let R2 be the dMM matrix that joins Rm, for and Definition 3 it follows that for all (s', 8, S X S A.
E [M]. Then, from Assumption 2 that
(n a)
Σ (alaaa)
1E|4
Σ
Σ
B(i,j.m) (r.m Wn(s,
E
ME(d
Σ
mEIM
(()
and -(s (s) (with the same argument) for some S x dM matrices W/, (s'))) with entries bounded by a. Note that W/, and (s,(")) are matrices that join Wm.h. and U (s'),
respectively, with entries that at most a times larger than the original entry. Let & be the thresholded feature mapping, where is defined as t minger for
tHSdjt
T
t t [M 1 1
adT(dM M2A
23

---

Therefore, with the same logic as the previous proof. it follows for all Exx
("(s,a)-G((a)BwWa (a()) (G)( - (RRR)
((Ga(a) - + -
HS
+ + 1:
T
HS
T
HS
tHS
T +V
T
1HS
T
where the second and third inequalities comes from the same logic used in the proofs of Theorems and and the fourth inequality comes from the definition of L. From the same logic,
IHS
Σ (Pr(5'ls, unsss
2
Therefore, (a) satisfies Assumption 4 with &
Then it follows that running LSVI- UCB-TR using (a) with 8' = 8/2 during the target phase of the algorithm admits regret bound of
UHS.
tHS T
Regret(T) S C" (V+S 2HH
Õ(VE
with probability at least ô from final union bound. Furthermore, the sample complexity in the source phase is
F (P A)M AMMT
δ
S
which proves our result.
F (S) Tucker Rank Setting
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' d.M. Thus, there exists S x d x A tensors U mnh x d' x A tensors Un. S x d p-incoherent matrices Fm,h. S x d' p-incoherent matrices Fy. with orthonormal columns, and A X d matrices W Wm, A x d' matrices Wn. such that
P (m',(s'(ssaa) = ='Eeg (), i)
am) = -E Fm, (s, W),m),
and
= (a( Eiejar (1, i) rn(s,)) = Eiety (a,
where IIvrss g(8 as);;,))ll, ('s)Aaas a) IW (a) ll2 (m,a(a)l S (d) for all S, a A. h E [H), and m [M] any function g S [0, 1].
Similarly, to allow transfer of a latent representation between the source and target MDPs, we assume that the subspace spanned by the set of all source latent factors contains the space spanned by the set of target latent factors.
Assumption 6. Suppose Assumption holds. The target MDP latent factors Fú, and source MDP latent factors Fm.h satisfy for all h E [.). Span(1Fa (;, (ejaa))) Span( Fm, (i, (E(M))))
24

---

Before defining our transfer-ability coefficient, we first introduce the following notation. We define the set Br (Fh: (Fh.mmmEM to contain all coefficients of the linear combinations, i... BR, E Rdd d.M and B₁ E (Fh,,, Fh.m IMEM) if for all i E h h E [H] Fn(;,t) = Eje(4 ( f.m.).mm.... (-..) Furthermore, as the source MDPs latent factors of Qm,h are
not unique, we define a to measure the difficulty given the best 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 c and [
let FF be the set of all IRSxx mairices with orthonormal columns that span the column space of Qm,h for all m [M] h E [H]. Then, we define a as
=
max min min he[H] PEF BEB.(PP.FF (ed mm (i,
max
We now prove our lower bound in this Tucker rank setting.
F.1 Information Theoretic Lower Bound
To formalize the importance of a 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 (ii they cannot be distinguished without observing M(a² samples in the source phase, and (3) they have target state latent features that are orthogonal to each other.
r) share the same state space, action space, and horizon H and assume that S A = [2n] for some n N... For ease of notation, we let 81 and #1 refer to any state and action in [ni]. respectively, and 82 and d2 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 $2, 01, 42 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 81, 82 and columns 01 (2) that satisfy Assumptions and but have orthogonal target state latent factors. For ease of notation, the superscript i of Q Qi denotes transfer RL problem. Then, the optimal Q functions for transfer RL problem one are
Proof. Suppose all source and target MDPs (S,
(2n
1/V2 0]
(2)(2n) [11(22))
0 1/v2
2111 (1/(2n)
I//nn 0]
22.1
00 v1/Tl
1/V2
0]
1/v2
2 = n
(1/(2n)
[VA
1/2 -1/2]
[I/(2m]
=
1/2
-1/
and the optimal Q functions for transfer RL problem two are
(1)(2n) [1/(2n)
1/V2
0]
0 (1 (1+1/a)/(ov2)
27.
Iv1/n o] =
22, -
nF'
1o v1/n|
1
0]
(1 (1-1 (--1a)/(cV2
(2) V1/(2n)
[V= -v:]
1/2
-1/2
0 n
-1/2
1/2
where
F" [(v(((/)(2m) +
(V1/(2m) /1/(2na²)/ /1+ 111++/// 1/a²]
and (1,)d because 2 1/ddM) from Lemma 1 for a > 0. The incoherence μ., rank d, and condition number of the above Q functions are (1). Furthermore, the above construction satisfies Assumption 5 with Tucker rank (S, 1, A) and Assumption 6 because the source and target MDPs share the same state latent factor [v//(2n), vI/(2n) in the first transfer RL problem while in the second transfer RL problem.
[VI/(2n) -V1/(2n)] - [//((2) Furthermore, note that the target latent factors,
v1/(2n) + acF'T.
[2)(2 and F22
v1/(2n)
F
[I/(2n)
-V/((2))
25

---

are orthogonal to each other.
The learner is given either transfer RL problem or with equal probability with 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 realization of shifted and scaled Bernoulli random variable X. The distribution of X is that X with probability (Qmi (s, a) 1)/2 and
X = -1 with probability (1 Q a))/2)) Furthermore, the learner is given the knowledge that the state latent features lie the function class F {F*, ,F? 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, needs differentiate between Q2 and Q21 By construction, the magnitude of the largest entrywise difference between Q and Q2,1 is lower bounded by (21/aa).
If the learner observes Z samples in the source MDPs, where Z S (a²)) for some constant C 0, then the probability of correctly identifying F upper bounded by 0.76 (Lemma 5.1 with = 0.24 [5). Thus, if the learner does not observe (?(a²) 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 states that unless one incurs a sample complexity 12(a²) )) in the source phase, the latent representation F learned in the source phase is useless in the target phase one would incur linear regret using F.
Our algorithm in this setting is essentially the same as the one used in the (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.
Algorithm 3 Source Phase
Input: {No
1: for m E [M] do
2: Run LR-EVI([N,, ( on source MDP to obtain Qm,h-
3: Compute the singular value decomposition of Qm, = F Fm Em GT
m.
4: Compute feature mapping f FR]ne(H) with Fr. {
S Fm Pm, i)li [d] [M]
du
Algorithm 4 Target Phase: LSVI-UCB--S, d, A)
Input: X, A,, 1: for E [K] do
2: Receive initial state st.
3: for h H..... do
4: for a E A do
Set Ag + Eiery (shh)) + AI.
5:
6:
/* Compute Gram matrix Ag +/
7:
Set wh + (Ag) - 1a
(it) (ra(sh, a) + max. Q ( /* Estimate wh via regularized least squares */
8:
Set Qx(:.)) min [I, (wi, (.)) PR, -
9:
10:
/* Estimate w via regularized least squares */
11:
for h [H] do
12: Take action af +- maxaeA Qn a), and observe s
We first present the theoretical guarantees I L.SI--CC--S, A) and defer their proofs to Appendix
26

---

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 Sholds and the learner given the true latent state represen- tation F = (Fr (EE)) Then, there exists a constant > O such that for any 8 E (0,1), if we set A 1, = cdH VL, log(2dT A(8), then with probability at least 1 - 6, the total regret of LSVI-UCB-IR is O(Vd&HHHT)
Theorem g states that LSVI- 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 '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 [7]).
Assumption 7 (E-approximate (S, d,, A) Tucker rank MDP). Let & E [0,1]. Then, MDP (S, A, Prr,
; H) is a E-upproximate (S, d, A) Tucker rank MDP with given feature map F if there exist H unknown A-by-d matrices W = [WaheeeH) hE(H and S-by-d-by-A tensors U = {Un)eE such that
(r)(8,)) Fa(() (a(a))
Σ (P,(5'ss,)) -n)(s) Un a)) SE
EES
for all h E [H] where [1W (( 2) S VS/(du) for any function 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 sutisfies Assumption 0 Then, using F (F) as the feature mapping for any ö E (0, 1) and X = 1, & O(Hd/i
EV (H) for + log(2dT A/8), the regret of LSVI-UCB-TRE Ö(V@ + (dHT) with probability least 8.
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., & so small that there exists some positive constant e such that &dHT S cv H AT, then LSVI-UCB-(S, d, A) admits regret bound that is independent of the state space, which is the motivation for main result. We now present our main theorem.
Theorem 10. Suppose Assumptions
6 and hold, and set E (0. Furthermore, assume that, for any e E (0, AH//T) Qm,h -m. + Pm. Vm, has rank and is ş p-incoherent with condition number for all c-optimal value functions V1+1. Also, let x = 1 and Sh, be a function of samples
d, H, (T k. IA), M,T. T. Then, Z A. using at most Ô (d A (S/A + 1)M² in the source problems, algorithm has regret at most Ô (d( AT) with probability at least 1 8.
Theorem 10 states that using transfer learning improves the performance on the target problem by removing the regret bound's dependence 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 [0
Proof. Suppose the assumption stated in Theorem 10 hold. Then, from (3), running LR-EVI with a sample complexity of C' ( + A) a log AdS H/M// on each source MDP results in Qm,h functions with singular value decomposition Qm, h Fm Lm Gm that are /HA/ (16opx
with probability at least 1 8/2.
27

---

Since our estimates are perturbation bound, Corollary 3 Since ||Qm,, oo 2 C, from Corollary 3 follows that there exists
it follows that 7 < 1/2 in the singular vector
rotation matrices Rm,h such that
dvHpA
[l Fm,A)()ll
QV SMT
for all E S where the optimal Q function have singular value decomposition Q Fm, Em,nh Gm,
Let F be the S x dM matrix from joining all the source state latent factor matrices, and Fh be the x dM matrix from joining all Fm. Let Rd be the x dM matrix that joins Rm. for all m E [M]. Then, from Assumption 6 and Definition 4 it follows that for all (s', a) E S x S x A, that
Th (s
Σ iE|d
Fs ((,
Σ
B(i,j, Fh..msss) Wh(a.i)
EE|d]
E
m)i Fm, Fm..m))))m)))
(a)
and P()'l:.)) = =(("::))-PP,(()) (with the same argument) for some A x dM matrices W₁. (8)) Note that W/ and (s") are matrices that join Wm,h and Um,x(s') respectively, with entries that at most times larger than the original entry.
Therefore, follows for all (s', s, s,a.M. h) E S 8 Ax [M].
(x, - (x()) = =IFa(s) - WW(
=I(Fn(s) - (((()
S al
Σ (Fmmn (s) - Fm.t Rm. (mal))
mEM
< a
Σ
(s) - Fm, R Relll))mmmlllllm
mEM
S
0
Σ
[Fmm - (s)
dp
MEM
dHMA
T
from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,
Σ (Pa(s')s,a) Fa(s) Un(s', T .)) S'ES
=1) (A()))
= -1(E((s) (())) [U((s'a)7)
s'ES
S al
Σ (F).) - (mm,(s)
Σ Um.(ds),a)
MEM
s'ES
< a
Σ (()
Fm.h(s) Rm, llzll Σ
Um,l(s',on a)
mEM
s'ES
MA
T
28

---

Therefore, (s) satisfies Assumption 7 with ç
V
dMHA
Then it follows that running LSVI-
UCB-TR using (s) with 8' = 6/2 during the target phase of the algorithm admits regret bound of
dMHA
Regret(T) S C (V V
E H(VVPM**HATT)
T
with probability at least å from final union bound. Furthermore, the sample complexity in the source phase is
d' dd A)M 2 H²a²T)
δ
A
which proves our result.
F.2 Simulator Simulator Transfer RL
In this section, we consider the same transfer reinforcement learning setting with the low Tucker rank assumptions except the learner is given access the generative model 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 learn an 6-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 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 p our latent factors F alloww us to construct good estimate of Q" over all state-action pairs. The optimal design problem that we solve in this algorithm is
G(p) (())) SES
((p) max || ((()))))+ SES
where p probability distribution over S. From Theorems 4.3 and 4.4 [22). one compute a p such that g(p) < 2d, with the core set of states, or anchor states, S# (x E S)p(s) > 0} having size at most 4d log((og(()) + 16 in polynomial number of computations. This ensures that both the eтror amplification from using the low-rank structure and the number of states we need to observe Q' is too large. Our algorithm is tailored the (S, d, A) Tucker rank setting but can easily be modified for the other Tucker rank settings.
Algorithm 5 Target Phase
Input: (N))eet)) P 1: for h h= H,..., do
2: Compute Si according to the above optimal design problem with A...
3: for (s, S x A do
4: Collect NJ, samples of the reward function and one-step transition to estimate Q (8,
with
(n a) = a) + (erePAtteeee
where (s,s,a) a) denotes the empirical average of the N₁, samples of the reward function, and Pp (-Is, a) denotes the empirical distribution over the Nj samples.
5: Use the linear structure to estimate Q over all state-action pairs with
0 G(p)-1 Σ ((S)),)))
Qn(s, - Pr(s)0an
SE
6: Compute the value function and policy using the Q function.
(x(s) = max Qn(s,a), #n(s) = arg max Q (s, aEAA
a

---

In the source phase, our algorithm learns estimates of Qm.A and then computes the singular value decomposition to construct approximate feature mappings using the singular subspaces with respect 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 c-optimal Q function in the target phase.
Theorem 11. Suppose Assumptions 5 6 and 3 hold, and set ó E (0, 1). Furthermore, assume that for any e > O, Qm.h = Tm.h Pm.h m,h++ has rank and is y-incoherent with condition number is for all e-optimal value functions V1+1- Then, for e I add, using at most
δ d (S + a2
2²
samples in the source problems, Algorithm learns an c-optimal policy in the target MDP using at most
δ 2 2
22
samples with probability at least 1 8.
Theorem I 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 observe at least (2(d( A)H$/c²) samples from generative model to learn an c-optimal policy. Furthermore, the source sample complexity's 's dependence on S, A, and H are reasonable while the dependence easily construct similar algorithms that admit the corresponding theoretical guarantees in the other Tucker rank settings. We now prove Theorem
is optimal due lower bound. We
Proof. In the source phase, using
(
6²
samples guarantees that we learn c/(128H 3/ ooptimall Qm,h F Pm GT m. functions for each source MDP with probability at least - 5/2. Since ad2 2 by assumption, we have 1/2 in the singular vector perturbation bound, Corollary 3 Since 10m, C, it follows from Corollary 3 that there exists rotation matrices Rm,, such that
c/P
[ h Pm,, R112,00
811"aM3//2
holds for all m E [M]. & E [ with probability at least 1 5/2.. Let F be the S x dM matrix from joining all the source state latent factor matrices, and Fj, be the x dM matrix from joining all Fm.h. Let R, be the d x dM matrix that joins Rmn, for all m [M]. Then, from Assumption 6 and Definition 4 follows that for all (s', 8, E S x S x A, that
Th (s,
Σ (W,,(, iE|d
Fh. Wn(a,
iE|d
jEld),
Σ
(a)
and P(s')...) (s)) (with the same argument) for some d.M matrices W Ug (s"). Note that W% and (s') are matrices that join W Wm,h and Um.n(s"), respectively, with entries that at most
30

---

times larger than the original entry. Therefore, it follows for all (s',s,a,h) E S x Ax [H].
(r)(s,a) - WX()) (F)()) - (X())
((FA((s) - ((
<al
Σ (Fm,n P' Rm)))
MEM
S a
Σ ( -
mEM
S
S a
Σ
Rmm
du
MEM
8vdM
from the Cauchy-Schwarz inequality and our singular vector perturbation bound. From the same logic,
(V -(A...
V(5) Σ Fn(s)U V() - seES
Σ Pa(s''s,
s'ES
(((F(()) ()())R) Σ Uk(s'aa)
eEES
Ha E [L)m(()) (s)
Σ s'E8
(m,
MEM
HayS
Σ (Fm. Fm,
ddp
MEM
8dMMH
From the above result, follows that for any value function V, the misspecificatiion error of using the approximate feature mapping of the corresponding Q function Q' = r + PV satisfies
(8, (haa(s, S (8) - (s) (a)) + (s, -F.
82 8VUMH
4H
To prove main theorem, we first present the following helper lemma and defer the proof to later in this section.
Lemma 2.
Suppose the setting Theorem [7 and that the misspecification error of the bellman update for any value function using an approximate feature mapping satisfies
10', (s, a) Qh.a(s,a))
4HvdM
Then, the learned Q function from our algorithm at time step satisfies
1Q 2o 1Q, 1i < e(H (1H-++)) h
for h E for N₁ = H d log( (SAHH)) with probability at least 1 - 1- - -
From a union bound and applying Lemma 2 it follows that Linear Q-Learning learns an coptimal policy with probability at least 6. Therefore, the sample complexity of the algorithm is
dl 22 A
No # A
22
NEH
31

---

It follows from the triangle inequality that the learned policy is 2e-optimal by replacing 2e with c'.
n
We now prove Lemma
2
Proof. We proceed via induction. At time step H (the base case), it follows from Hoeffding's inequality for Nu = HAAM log(SAH/8)/e for some constant C > 0,
1Q a) Qir
for (8, E S x A. From Proposition 4.5 from [2] and our assumption on the misspecification
error of the approximate feature mapping, it follows that
1Q - QH(,, H
Since Q Q/ it follows that the base case holds.
Next, assume that
1Q++1 - 1241 llo, [1Q 12411 S c(H h)
H
holds with probability at least 1 - (H h2H. We define Q2 as Q, rh + PA Ve+1. Let Pha FW, Eves (s+1(s")unss'),, Then, it follows that from Hoeffding's inequality for N₁ logPAMog for some constant C > 0, for all (8,a) E S A, in step (b) of our algorithm,
(s. - - (s,,a))
4l1 vdM
From assumption on the misspecification error of the approximate feature mapping. it follows [22 we have
that |/%/ - Qh.all> I 4нvlM Then, from Proposition 4.5
(n((, - Cha(lsa))
2H
2H
H
for all (8, S A. Since
e(H -h) h)
(Q)(,,a) Qh(s,aa) S / (V/+z166)) - - (6--( S
H
E'ES
and
(s,(s) (s, S Σ (Viii (s+ <(H - h)
H
S'ES
holds from the inductive hypothesis for all (s, a) E S x A, it follows that
(Q)(s,))
(8) (Q((sa)) ((((s,)) S (x, a)l + 14 (8, (8.
<( hh) <H 1)
s H
+
H
H
and similarly,
(s, a) Qn(s,a) (( - 11
Thus, the inductive hypothesis holds as union bound asserts that the above result holds with probability least 1 - (H h + (2H))
32

---

G (d, S, Tucker Rank Setting
In the low-rank MDP transfer RL setting, provide algorithm that admits source sample complexity of O(Aa² MT log(+)) and target regret of O( /TT with high probability in the transfer RL setting with low-rank MDPs. We first present the transfer learning assumptions [4] needed prove lower bound in their setting. Low rank MDPs assume the following stucutre with shared latent representation o,
(m, a) (sm, (s, Pa( = (n(('') (1(s, (M(,s') a).
where 1 (s, a)ll2 < and [ ((s)g())dz122 s vd for any function S + [0, [3] for all m E [M, E [H]. To allow transfer learning to occur, assume the following:
Assumption 8 (Assumption 2.2 (4). For any h E [M]] and s' S, there exists (sm) IR such that (s)) = Emela 1m (8' (s',
and define the task-relatedness coefficient as a = maxme maXme[MM,A<(M)) MA a They leave deter- mining the optimal dependence a as interesting open question. Similarly lower bound in Theorem 1 we prove that one must incur a source sample complexity of M(a²) to benefit from using transfer learning. Note that in this version of transfer RL, there is reward function in the source tasks.
Theorem 12. There exist two transfer RL instances such that (i) they satisfy Assumptions and (ii they cannot be distinguished without observing 32(a?) samples in the source phase, and (3) they have target state-action latent features that are orthogonal to euch other.
Proof. We consider low-rank transfer RL problems, in which the source MDPs have similar transition kernels but differing ø. All source and target MDPs (S, P, H,r) share the same state space, action space, and horizon H with M = 2. The learner is given access model in the source problems. To introduce the MDPs (without loss of generality assume that [S], |A] even), first define the feature representations: the feature mapping for transfer RL problem i is
generative
s (81, = (1 a2) [1, T. , (81, 02) = Φ2(82, a1) (0,1)
(2(81,a1) = 02(82, 02) = = (2(11 (22 a1) [1,0)
where refers to states 1,...,,11 1,...,111/2,, refers to states |S|/2 + +1, 1,..., S| and similarly for actions.
We will present the transition kernels matrices with 81, 82, 41, dg as the blocks containing |SS// or |A//2 entries. Clearly, the two feature representations orthogonal to each other. Next, the
33

---

transition kernels P m,1 for transfer RL problem i and source MDP m are
(1i(s1l:s)) [1/2, 1/2 1/a]01(s.)
1/2
1/2 1/a
1/2-1/a
1/2
P1 (12((22)))) = 11/2,1/2+ 1//a]/((:.)
1/2
1/2+1/a
1/2+1/a
1/2
P ((,1(51):)) = 11/2,1/2-
1/al)/((/)))
1/2-1/a
1/2
1/2
1/2 1/a
Pf (s2l:-)) 11/2,1/2 1/a)02(.))
1/2++1/a
1/2
1/2
1/2 1/2+1/a.
(21(s1 = (221()2):)) (2.1(221.-)= = (82l))))))
= =11/2, (1).)=())))1/))pb(((((
1/2 1/2
= 1/2 1/2
(+ = pr (:)))))))
where pr(() [0, 1] in both transfer RL problems. It follows that
pT(s1) (s) ri a(1ā()1) ( (s
and similar results hold for so satisfies the definition of the task-relatedness coefficient. It follows that in both settings, Q'ax = a. The target phase reward functions are defined
( = r3 = 1000111111 [1. ()))(:))
-())))r((.))) = [L. OjØ2(..-)
and the initial state distribution is uniform across all states. By construction, in transfer RL problem the only state action pairs that receive reward are ($1,a1), a1), ($2, 02). In contrast, in transfer RL problem 2, the only state action pairs that receive reward are ($1, a1). (82,41).
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 transition from Pi Furthermore, the learner given the knowledge that the state latent features lic in the function class & = {Φ1. )2) and must use the knowledge obtained from interacting with the source MDP to choose one 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, needs to differentiate between PI, and Pf.1- By construction, the magnitude of the largest entrywise difference between Pi, and P? lower bounded by ((1/a²). If the learner observes Z transitions in source MDPs, where 2 < ((a²) for some constant C >> 0, then the probability of correctly identifying á is upper bounded by 0.76 []. Thus, if the learner does not observe (2(a)) samples in the source phase, then the learner returns the incorrect feature mapping that is orthogonal the true feature mapping with probability at least 0.24.
Theorem 12 states that one must incur dependence in the source sample complexity benefit from transter 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.
34

---

Assumption 9. In each of the M source MDPs, the reward functions have rank d, and the transition kernels have Tucker rank (d. S, A). Let the target MDP's reward functions have rank d' and transition kernels have Tucker rank (d', S, A) where d' S d.M Thus, there exists S x d tensors Um.h, S x d' tensors Un. S matrices with orthonormal columns Om, hs SA d' matrices with orthonormal columns 0h and d-dimensional vectors W and d' o'-dimnnsionl vectors Wn, such that
(m ss, a) = =Eieig @m, a, m (s), (m, Eiijd Am, i) m.,
and
Pa(s'|s,a) EiElar (,,,
(n(s,a)= Eietan a,
where I sles ( 9('
S vd, (Wall, and [| (8)]l2 S for all E a E A. h E [H], and m for any function S - [0, 1].
While 4 assume that the target latent representation is linear combination of the source latent representation, we allow for 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 Pholds. For latent factors on from the target MDP and @m.h for the source MDPs, let oh- = (wh, Ph.m Ime[M) Then, there exists a non-empty set B(or) such that the elements in B((n)) are Bn TRd d.M such that
(n(8, EjEld Ba m) m))m,
for all i E [dd], E
As in the previous Tucker rank settings, we present the transfer-ability coefficient quantify the difficulty transfer learning.
Definition 5. Given transfer RL problem that satisfies Assumptions 9 and 10 Let & be the set of all SAx latent factor matrices with orthonormal columns that span the column space of Pm, for all m [M]. h E [H). Then, define
= min min +E BEB(O) jEld".EEdd ME(M
max
BB(,j,
4 provide an alternate definition of a, which also measures the difficulty of transfer RL, and leave determining the optimal dependence on bound in Theorem 1 we prove that one must incur a source sample complexity of (aa²) 2) to benefit from using transfer Tearning. Note that in this Tucker rank setting, there is reward function in the source tasks.
interesting open question. Similarly to our lower
Theorem 13. There exist two transfer RL instances such that (i) they satisfy Assumptions 9and 10
(ii) they cannot be distinguished without observing M((2)) samples in the source phase, and (3) they featurrs have target state-action latent features that are orthogonal to each other.
Proof. Consider the construction where all source and target MDPs (S, P,1,1, share the same state space, action space, and horizon with
As the horizon is one, use the construction used to prove Theorem 7 We consider two transfer RL problems i, i', in which the source MDPs have similar Q7. but with orthogonal target Φr. For ease of notation, we let aj refer to any action in [n], and d2 refer to any action in {n +1.. 2n}, respectively. The initial state distribution in the target MDP uniform over We now present two transfer RL problems with similar Q functions that satisfy Assumptions ond have orthogonal target state latent factors. For ease of notation, the superscript i of " m, Q" denotes transfer RL problem. Then, the optimal Q functions (with
but
35

---

columns representing d1 and d2 and the row being any state) for transfer RL problem one are
01 W LA 111
v1/(2n)
v1/(2n)
[1/V2 1/v2],
021 11
[v1((2)
[1/V2 1/v2]. v1/(2n)
VT
Vn [V/((2n
Q W
VT/(2n) 11V2 1/v2
[v
and for transfer RL problem two are
011 W II
oi,
(11(22) v1/(2n) [1/v2 1/v2],
221
W 2
G' = [[1+1/0)//oV)) (1- (1-1/a)/(ev2))
2,4
Q 1 Wno
[VI/(2n) -V1/(2n) 11/V2 -1/V2
and c= /1 1/a2. Note that c (1,2dM) because a 2 1/(dM) from Lemma for >> 0. The incoherence μr, rank d, and condition number x of the above Q functions are O(1). Furthermone, the above construction satisfies Assumption with Tucker rank (1, A) and Assumption 10 because the source and target MDPs share the same feature representation Φf = oi, in the first transfer RI. problem while in the second transfer RL problem,
$ = - 2 + 2022.11
Note that o and d2 are orthogonal each other by construction.
The learner is given either transfer RL problem one or two with equal probability with generative model in the source problem. When interacting with the source MDPs, the learner specifies state- action 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, (s, a) + 1)/2 and
X with probability (1 - Q'ni, (s, a2) Furthermore, the learner is given the knowledge that the state latent features lie in the function class = { Φ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 differentiate between Q and 22.7 By construction, the magnitude of the largest entrywise difference between Q711 lower bounded by M(1/a).
1 and ?x is
If the learner observes Z samples in the source MDPs, where Z S Oaa)) for some constant C > then the probability of correctly identifying G is upper bounded by 0.76 (Lemma 5.1 with 8 = 0.24 (S). Thus, if the learner does not observe (2(a²) 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.
Thcorem 13 states that one must incur dependence on a in the source sample complexity to benefit from transfer learning. With this lower bound, we' we've shown in all three Tucker rank settings that determines the effectiveness transfer learning under our transfer learning assumptions. We now present our algorithm that admits 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 minme[M J.E [m a) loc. and the dependence on D is unsurprising as one needs to ensure the noise is sufficiently small to learn the latent representations from P Pm.h- We now present and prove the main result in this Tucker rank setting.
36

---

Algorithm 6 Source Phase
Input: N
I: for (s E A, [ [M] do
2: Collect N transitions from source MDP m at time step / at state-action pair (s, a).
3: Use the samples to estimate the transition kernel with
(s
Σ 1x = SE[N]
N
where Xi, ~ a). 4: Compute the feature mapping å (ôn)ne(an with
{
V$ dp
Pm (t, ()) [d,,,, m, n E [M]]
Algorithm 7 Target Phase: L.VVI-UBB
Input: X, A,Bk, 3
1: Run LSVI-UCB with X, Be, and
Theorem 14. Suppose Assumptions 6 and hold in the (d, S,A) A) Tucker Rank setting, and set E (0, Furthermore, assume that for any E (0, /H/T), Pm, a) has rank d and is j--inohherett with condition number is for all A. Let D (e) (1 a) Then, for T 2 H/o?, using at most
δ 2 dd
D2
samples in the source problems, our algorithm has regret at most
δ (V(AMHyTT)
with probability at least 1 for and Br,k, which function of H, H,T,TTT M.
Proof. Suppose the setting Ae] [|,m, (-) a) Then, observing N transitions from each state-action pairs ensures that for each (s',s, s, a) S xSxxxx Sx A and for each source MDP at each time step.
Theorem
holds. Recall that we let
VH
(m (mmn(s'|s,all app.VaaT
with probability at least - 6/(282 AMH) where Pm,n(olss,a + Eie(M 1x((s,))=/ and X, ~ P(.(s,a) for
= a² a²dp²² M'2 (oo
2HD2
Let Pm.,a-l (-), fra Smm.Gmm. be the singular value decomposition of our estimate where f corresponds to the state one transitions from. Since T > a²/H, it follows that 7 S. 1/2. Thus, states that there exists rotation matrices Rm,ha such that
m.h
dyHp
[[ (Eu mih Rm,hia Fu (s) S aVMTS'
for all E S where the the true transition kernel Pm,. (-1., a) has singular value decomposition (m a)) = F Fmnth m.h We can re-express our terms the more common Low rank MDP setting with (m,n(s,,), a) F (s) and Mm,h (s') Em, GT
37

---

Let F be the SA x dM matrix from joining all the source state latent factor matrices from P(-l, a) for each a E A, and Fj, be the SA x dM matrix from joining all Fm... Let R be the d x dMM matrix that joins Rm.h for all m E [M]. Then, from Assumption 6 and Definition 4 follows that for all (s', s, a) E S X S x A, that
(n(
Σ
i)(s,))W((()
sE|d]
Σ
Σ
B(i, F... (h())
El
jE(d).E||M
B(i,j, m) Fm. (8,
[E(
Fs)
and p)) (3( (with the same argument) for some dM-dimension vector W (s)) Note that W and (s') are vectors that join Wm.hh and (s'),, respectively, with entries that most a times larger than the original entry.
Therefore, follows for all (s', s, a, h) E S x x A x [H].
[n a) Wo) = ()) (
= ((F (s
S a Σ (F (s) (s)-Fff Fm h (5) Rm W mm.
S a
F (s) F0 Rm W
mEM
S
Fra (s) (s)
dp
MEM
dH
T
from the inequality and our singular vector perturbation bound. From the same logic,
Σ (Ph(s'(s,a) - ()))))
< Σ Pa(s'(s,
(
FES
Σ (s))))
(666)
F (s) pu Rm)k))
(m))
meM
s'ES
| in (s) Faa (s) Rm Il2ll Σ (m) l|2
mg
s'ES
dHM
T
Therefore, (s) satisfies Assumption B in 17 with &
Then it follows that running LSVI-UCB using (s) with 8' = 5/2 during the target phase of the algorithm admits a regret bound
dMH
the total variation distance, they refer to as EEves P(s'ls, a) P(s' s, a.) in the second to last inequality in the proof of Lemma C. and the second to last equation page 23
Shhile the misspecified assumption in 17
38

---

of
dMH
and (T) S C" (VPMMHHT + dMH
) O
T
with probability at least 5 from final union bound. Furthermore, the sample complexity in the source phase is
2 du M
D)2
which proves result.
H (d, d, d) Tucker Rank Setting
In this section, we present the assumptions, algorithm, and proof for Theorem 15 In the (d, d, d) Tucker rank setting. we assume the following low-rank structure on the MDPs.
Assumption 11. In each of the M source MDPs, the reward functions have rank d, and the transition kernels have Tucker rank (d, d. d). The target MDP's reward functions have rank d' and transition kernels have Tucker rank (d, d', d') where d' I dM. Thus, there exists d d x d' x d' tensors Un, S x d matrices Vm,h: h: S x d' matrices Vn, S x d matrices Fm,h. S x d' matrices Pr,
tensors U mm.
matrices Gm,b and d' matrices Gn. all with orthonormal columns, and sequences of non-innnnnnn con-increasing singular values (0m,)(i) 2 RR+ Heed, {or (t) 2 RR+ )iela)) such thut (m,n(''ls, a) Liedddje(r)))edd (i (.).., i) n (s,j)Gmmt m,, (m, = Eield mm (i) n8 i)Gm
Ph(s'|s, a) (s,
where
g( g(s
())1 E g(d')Un(i,;;; for all S. E A. E [H]. m [M]. and
Viils, i)lle, om,n (i), (1) S
VSA
du
i [d] for any function g S + [0,1].
To allow transfer learning occur, assume that the latent factors from the source MDPs span the space spanned by the target latent factors.
Assumption 12. For latent factors Fs. from the target MDP and Fm for the source MDPs. let F (Fr, Fn.m hee [H) mE(M]- For latent factors Gb. from the target MDP and Gm for the source MDPs, let G {Gn, GR.m ) hellH) Then, there exists non-empty set C(G) such that the elements B(F) are B E gdd d.M and the elements in C(G) are C E Idd ,dM such that
Fn(s, Ejelq,mein) B(i,j, Fmn, (8,j)
and
Gn(a,t) Σ mejM) C(i, ((i,j.) (...m,a),,n(a))))
for all i [d'), S,
Similarly to the (S, A) and (S,S, d) Tucker rank settings, introduce the transfer-ability coeffi- cient that measures the difficulty applying transfer learning.
Definition (Transfer-ability Coefficient). Given a transfer RL problem that satisfies Assumptions 77 12 and 3 let F be the set of all S xd latent factor matrices with orthonormal columns that span the
column space of Qin, for all m [M], E [H). Let G be the set of all Axd latent factor matrices with orthonormal columns that span the row space of Qi, for all m [M], h E [H]. Then, we define a as
a = max
min min PEF BEB(F) iE(d") ME)
max
[Bi,j.m)
max GE9 CEC(F) Je[[
min min
|C ((..m.m)))
39

---

In contrast to the definition in the other Tucker rank settings, bounds the largest coefficient used in the linear combination F₁, and GG.- The algorithm that we use in this setting runs LR-EVI on each the source MDPs, constructs a feature mapping & using the singular vectors from the singular value decomposition mm and runs LSVI-UCB with é. Since we use both sets singular vectors to construct e our feature mapping has latent dimension d
Algorithm 8 Source Phase
Input: [NeE)
1: for E [M] do
2: Run LR-EVI(( hejHa) on source MDP m to obtain Qm,h.
ÔT 3: Compute the singular value decomposition of Qm,h F F, Em m.h."
4: Compute the feature mapping à = {&h NE(H with
VSA
Pm.l) 14, E dp
Algorithm 9 Target Phase: LSVI-UCB
Input: X, BK. 3
1: Run LSVI-UCB with X, Bk, and
The above algorithm admits the following result.
Theorem 15. Suppose Assumptions II
12 and hold in the (d, d, d) Tucker Rank setting, and
E (0, 1). Furthermore, assume that for any e E (0, HH/T), Qmah Tm,h + Pm,, Vnn has rank d and is p-incoherent with condition number is for all c-optimal value functions Vi+1- Then, assuming 2 H/a², using most
Ie A)M
samples in the source problems, algorithm has regret at most
(V
with probability al least 1 - for = and 8i,ks which is a function of d, H, T, M.
now prove Theorem 15 using a similar argument to the one used the proof of Theorem T0 except we show that the target MDP with our feature mapping satisfies Assumption B in [17 and apply LSVI-UCB.
Suppose the assumptions stated in Theorem 15 hold. Then, from Theorem 9 30 it follows Proof.
that LR-EVI returns near-optimal Q functions @m, functions with singular value decomposition
Qm.h = Em, Emm that are /H (saa Mdd'py' -opttmml with probability at least 1 5/2 using
Ô (d' AS A)MH*a*T)
samples each source MDP. Since T > H/a., from 7 S in Proposition 2 Thus, states that there exists rotation matrices Rm, I Rm,h.g such that
VI I - (s))) at a& /TS
VH
(.Gm,Bnm.te Gm,n) < af TA
for all E S where the optimal Q function have singular value decomposition Q = Em. G
40

---

Then, from Assumption 6 and Definition 4 it follows that for all (s', E S x S x A, that
()) = Σ
Th i))
=E|d
= Σ (i)
Σ
B(i, m)) Fl.
Σ
(E/d),ne(a))
Fm. (m.
Σ (( iE|d
mee(M = On)(s,a)h
where On -
and Φn {Fm. Gn, (3. and -)) (n()')0) (with the same argument) mee m.ne[ It follows that express Th F2 FR where F3 be the S x df matrix from joining all Fm,h dM times, Gh be the A M2 matrix from joining all Gm,, dM times, and E. is the diagonal matrix with entries (j. I, m, n) for all j. E [d]. m, n E [M]. Note that the entries of Σ, and ph are at most da² larger than their original value.
for (s (Ei,Aeej kili,, ()
Let Pr the S x 22 matrix from joining all Rm.., dM times, and Go be the M² matrix from joining all Gm, Rm dM times. Let 0% satisfy
0 C.
Therefore, follows for all (s', 8, a, h) E S A x [H).
(rn(s, a) 0, (s, a)l = |R, (s, E (s)
- SA GT (s, F. (s, a)) &I -
mEM < dM Σ (s)m,(() - P A Rm, || En lop
max VellGGm,tllo.
MEM
+ Vd max mEal
|| (L.mmlll ao /hplop Gm,n (m) (m)
< 3
Σ [Fma(s) Fm (s) (5) r Illll/ flop max 11Gm, mEM
MEM
+ max mEM
[|| + ||Fm, Foo Elllop Gm, Rm,
S SC M VS
Σ
[[ - (t)
Vi
MEM
dMVH
VT
where the second inequality comes from the triangle inequality and Cauchy-Schwar 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 our singular vector perturbation bounds. Similarly.
(P,((l))))) - (o))))) (8, TTTTIm 1|T S SO dM
VT
for some absolute constant C > where (s(')) satisfies (,") and (s') is the d x d² 2 diagonal matrix with entries un (s', hi m, n) with the same argument using the regularity condition on ph-
41

---

Therefore, å satisfies Assumption B in 17 with & = O(dM admits regret bound of
H/)). (H/T)
Running LSVI-UCB with
(T)rel(T) sc sesoocovvvo ( CCVVVMHHTT de H
VT E Ò @d
for some absolute constant C' > 0 with probability at least 1 - 5 from final union bound. The sample complexity in the source phase is
Ô
which completes the proof.
I too eigen perturbation bound with non-uniform noise: rank-r case
Rmxx, where A" is the true rank-r matrix and D is the noise matrix. Suppose A" has SVD A' = U'E'V*, where U e V* enxr are orthonormal matrices containing the left and right singular vectors, respectively, and E- diag(of..... ................................ o,,) is diagonal matrix of the singular values. Similarly, suppose A has SVD A = UEVT + U'E'V", where U EXxr, V gaxr and Σ ( ...,,,..,,,,, G,) correspond to the top-r singular vectors/values, and U (mx(m-r) V E x (m-r) and ((m-r)x(n-r) correspond to the bottom singular vectors/values.
Suppose A =
+ A
The following proposition is generalization of the perturbation bound in 12 to the setting with non-uniform noise.
Proposition 2. Suppose 7 == ||
2. There exist two orthonormal matrices R.R exxr such that
07 07(1- - -) [I(U R² ,112 < | 87 + +
Vi [m].
(V-VRR),.l - 1 87 |D o; -7)
1
Vj [n].
To prove Proposition
2 we need some notations. Let H == UT gxxr and its SVD be H AAB", Exxr is diagonal matrix. Similarly, let H. = y exxr and its SVD be H AAB Finally, define the orthonormal matrices
where A, B gxxr are orthonormal, and A diag(o 1,..., ,,)
sgn H = AB and (H) == AB (The function sgn(-) is called the matrix sign function.)
We need technical lemma, which generalizes [2] Lemma 3] to the asymmetric
Lemma (Properties of matrix sign function). We have | S
and | loop
S
When
7
we have
max |
|IU'DIlap
DIl
|| 1l
H sgn H 1lap I -U- ll.p
1 ?
7)
1-77 7
max |1 D
|V 11
|| sgn(H)) S |V
V-VaT 11
(1-7)07
and
ΣH
HE 2
H Σ ΣH
2
and
(1 - 7)²
(1-
H
H op (1 27)
27)
op
Proof. We prove the bounds for H. The proof for H is identical. Clearly
H op S U |1
1.
42

---

By Weyl's inequality, we have loy-- - -0,l S |Pllpp Vi E [ml, hence
- 2 of - 11 = (1 - 7); 2 0
..... by assumption. On the other hand, by standard perturbation theory. 12 2..2... J. 2 0 are the cosines of the principal angles 0 < 01 S ... ...5. 0 S 4/2 between the column spaces of U and U* and sin 0, JUUT - -UU up Hence
sgn H) - HH,, up cos 0,. By Wedin's sin +
Theorem, have
max { Dilop ||D sin 0, v
max DIuap || llop }
op
0, 0r+1
(1 7)
Since cos 0, 2 cos² 0r = - sisn-nnn 8,, we obtain
max |10*D11 1I
1lpp
| up
v //gg(())
H) H lpp
1 cos c, I sin
1 7
(1-7)o7
(1 7)0
Note that
DV
- HE
and
Hence
- ΣH H 1m + |H - -
op
= |UT DV
11 + -->-->>)ll. E)plupp
< || D D1lpp op + || op 11-0 - 2illop
$ 2 |DIl ollop
where we use | | mp S and ||- Ellop $ |ID|lpp Similarly,
U DV = U (A A*) V = U T US - -T -
so similar argument above gives
H T Σ EH
< 2 D
op
Finally, recall that |H sgn H
and note the simple identity X-1 y-1
op
1-5
x- x) follows that
H sgn H -1 op
H
H sgn sgn(H)) (1) 1lmp |sgn (H)) 'l.pp
op
[o,
(sgn(H) + (H -gg((H)) || (inssgHHH))..
7 =
72
1 - マ
1 25
1
T
7-7
It follows that
72
(1-7)
H 11op op
sgg
H
11
+
H
sgn
H
11
op
1- 27
1 1-27
This completes the proof of Lemma
3
We are now ready to prove Proposition
We have
U U sgn H))
AVE U (H) T
4= UEV
(A' + D-V--- U sgn H))
=U'E''" -V--- U sgn H + DVE-1
= U'E'TT
=U'E' x-1 U (H)
T + DVE
H =
43

---

But H =
ΣH - + +--- -2) H. Hence
U U- ( = U* H + - + H Σ- U² sgm sgn (H) + DVE-1
-. T + U (.. Σ Σ- + x (Σ+ - H Σ U² sgn (g) + DVE
U - sgn + IM - H -لا - + U 12- - 2 1 Σー
DVM-!
For each i E [m]], we can bound the i-th row of U - U* sgn H) T as
[I U sgn (H) (H) >)ll s |102122
I sgn
-gg 11 + EH H
Σ op
| |
+1E Ellop
H op
+ |Diill
olop
|
(1--)
7
2
1
0, 7) )
12
(1-
+
Dllpp op
D
+
||D1l
-1.
+ -Daalll
0 - 7)
07 -)
7
2
37
1
| l2
1-
+ 1 1-7
1D
0,² (1
1
| 2 88
[D
0, 7)
where step (i) follows from Lemma and the bound
1
up Gr oF 1|D1lpp 0, 7)
and step (ii) holds since 7 Σ
2. Setting R sgn (H) proves the first incquality 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 p--
incoherent with condition number and ||o C for some constant C. > O. Then, there exist two orthonormal matrices Exx such that
[I(U UU)))ll1 16x(ud)3/211
Vi E [m],
Cvm
v)-- 16x(Hd)3/3111 Cyn
Vj [n].
Proof. From the definition of the tx norm, there exists Then, follows that
(i,j) [m] x [m]] such that || = |Aigl.
|1 = |nas
IU (V-VAV+ kaol
||
lopl U/ 12
o ud
mnn
kaaud
Vmn
Furthermore, note that || < |1 /mn. Thus, the result follows from Proposition 2 and using the definition of incoherence and the above inequalities.
Proofs of LSVI-UCB-(S, d, A) and LSVI-UCB- d)
In this section, we present the proofs of Theorem g and and the related lemmas. The proofs,
theorems, and lemmas are modifications of the analogous result/proof in 11 tailored to our Tucker rank settings.
44

---

J.1 LSVI-UCB-(S, d, A)
To prove Theorem 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 copies of the weight vectors and gram matrices. We let A h.k: Wh Qh VA TH as the parameters/estimates at episode k. Furthermore, let V m Q% a) and Th be the greedy policy w.n.t O% We let F/ := (s).
To prove the desired regret bound, we first need to prove that PV PV concentrates about 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 function class of mappings from S to I with the following parametric form
v(+) min max W. F(-) BV F() (FF)), aEA
where the parameters Wa 3, Ag satisfy |wall I L all a E A. 3 E [0, B). and the minimum eigenvalue of Au is greater than x. Assume that [|F(s)]] < 1 for all s E S, and let Ne be the e-covering number of V with respect to the distance dist V, V*) = sup, (V(s) - (s). Then,
log(N.) S dllog(1 4L/e) de log(1 (1+ + 8 B² /(xet)
Proof. Equivalently, we reparameterize the function class by D. = B²
v(-) = min max i. TF(+) + (F)TDa(()) aEA
where ||wa|| < L and |Daall S B for all a E A. For any V1, V2 V, let them take the form in the above equation with parameters (Wa, Da) and (w', Da). Since min(,, H) and maX.e.4 are contraction maps,
dist(V - 122) s sup (w F(s)) + / s.a
- (w. F()) + / ((F())
1( F / V D.F) (w/d F VETDEE)
sup PISI
max
sup [w., - F1
sup P:1
IV FT -
max
||wa- wall + Da D'll
I
max BEA
I1wa- w'all + VILAa D2llF
where the holds because V/ V S V - y for any v, 2 0. Let Ci be an e/2-cover of {w E Rd|] w|ll < L} with respect to the 2-norm, and Cn be an e² 244-cooer (D E [Rdx DII S d 21/222/X) with respect to the Frobenius norm. By Lemma D.5 from 17] we know that,
|Cwll S (1 +1+ 4L/e)*, |Col S (1 + 8d /22 (
Hence, for any Vi, there exists a w/ E C. and D' E Cp for all a E A such that V/2 parameterized by (w',, D',) satisfies disi(V,, V22) S e. Hence, No S [Cml which gives:
log(N.)) < log((Ca)) 1) + log( (Col) S dlog(1 4cL/e) + d log(1 + (2²
We next bound the no-m of the weight vector of any policy. Lemma 5. Let {wg} } be the weight vector of some policy m, i.e., (8, Fn(s)) Twf, Then,
|uill < 22HV
45

---

Proof. Note that Q7 a) = (r, + E.. (s a), so, using the low-rank representa-
tions of Th. Ph. it follows that
|lu l = [h )+) Σ (s')UU a, )l1 - [W )1l+
V" (s''' a. )l22 S Vd+HVa.
Recall that since the feature mapping was scaled up (Fi- - W. U are on the same scale, follows that [W)(all2 - and Eves (544((5Uu a)ll s H. Therefore, it follows that || l|2 S 2H
S
F") to ensure the max entries of F and
dp
We next bound the 2-norm of the weight vector from the algorithm. Lemma 6. For any k, h, the weight vector from the above algorithm satisfies 1 1 2H dk//X.
Proof. For any Fa(s) f, we have for any E A
If w% = 1f (AR) (A
E (1hh TET
(n((sh
max Q1+1(sh+1) a'EA
f FA
1ET
S 2H
Σ (T(A))
E 1ET7
IETT,A-1
< 2H 22115122 / /// 2H 222kH//k dak/X,
where the second to last inequality is due to Lemma D.I from [7 and that Rayleigh quotients are upper bounded by the largest eigenvalue of the matrix (Theorem 4.2.2 from [14). The last inequality due to [ I and - S 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 3h c'd Vt. Then, there exists a constant C > O that is independent of d' such that for any E (), if we let the event X be
V(a,k,h) E Exx( Ax
Σ
(V(5%)VV++++)+++1 PA Vi
CdH VX
LETR
(NG.))
where X = log(2(e + A/5), then P(X)21- 1-/22
Proof. From Lemma we have ||wffelll S 2H / dk/A. By construction, the minimum eigenvalue of Af, is lower bounded by X. Then, from Lemma D.4 in [17 (with = 6/A), Lemma 4 and taking a union bound over actions, we have that with probability at least 1 - -5//2, for all a E and 0,
[ log((k: + ()/A)) + log(2AN./8)
(V PAV. (s), P
I 4H²
+8k22//.
2
EET
(Ag.))
Then, from Lemma follows that with probability least 1 8//2, for all A and 0.
((( - PAV
IETO
(AE,))
d
S 2
log( + X)/A)) + log(2A/6) + d log(1 + 4L/e)) + d2 log(1 + /8/123//(22)) + -88222//
2
46

---

Choosing À = 1, 1,, CdHL, = dH/k gives that there exists some constant C" such that
Σ 1
S Hog +1/TA/0)) (Ag.))
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 constant such that P A = cadHl vi Viwhee t log(2dAT/p) and for any
fixed policy π, on the event X defined in Lemma 7 we have for all (s, a. h. E S x A [H] x [K]:
Fh(() Whik - (% 1 - ())
where (+) S PE, (AW
Proof. From our low-rank assumption, follows that
(7 a) = Fs( wht (rh + Pa PAV (s..),
which following the steps from the proof of Lemma B.4 in 17 gives
wh.k wh
--AAA
wh R,
+ (A)
Σ
(V - P
TET
+ (A)
Σ
(i+1)(sh, a)
11T1-1,A
Now, we bound each term (gf 0 4 individually, for the first term, note for all a E A
(x) T ofl = (AF (s) T (A% ) w. a. S W x II (A (s)
For the second term, given the event X, we have from Cauchy Schwarz
(s) T Ø < CaH VX (AR.
where X = log(2(c3 + A/d)A/p). For the third term,
Fh(s) == (AR,)--) Σ FN(S)) Vitil6h..o)
IETR-I.h
=p(s))
(AR,)) Σ ((( Σ (v (3
TET
e'ES
T
(V/++ - VT -V
WES
T
(AR,a)-)
Σ
(V (441 (
NEES
We note that
TT(S)T Σ
( (1)
Pa(V (s,
47

---

and
h+t V ( F(G) V
IAFa(s) (AR,)))) Σ
S'ES
Since
[s) whi (T( (1((s) ( - -0 F)(ss) (q -2 95).
follows that
(s) whe (s) - PA h+1 (s, & C" dH vX (AR,) (s).
Similarly as in 17 we choose Cp that satisfies C" Vlog(2) + log Cp + 1) S saavlogg ll)(().
This lemma implies that by adding the appropriate bonus, Q is always upperhound of Qi with high probability, i.c., achieving optimism.
Lemma 9. On the event X defined in lemma we have Q a) 2 Qi a) for all (s, h. k) E S x A x [H] [
Proof. We prove this with induction. The base case holds because step H + 1, the value function zero, so from Lemma
(s( WH - Qir(s, Ph, Fu(() -M
and thus,
(s & min (H) + Si,n
= (s, a).
From the inductive hypothesis (assuming that +
(s, a) 1h+ a)), it follows that Ps h+1
Vi++1)s, a) 2 O. From Lemma (s) wh. 27 S fg, (((s)T(Ag,)))) (1)
follows that
(% a) I min H,, (R)) wh, + PR FN)
= a).
We next show that Lemma 8 transforms to the recursive formula 5): = (s - Vi (s%) which is used in proving regret bound.
Lemma 10. Let 6% (stt) Vi (st) and ch+1 E h+ st a - 6 h Then, the event X defined in Lemmal have for any (h, k):
* < 6h + chi1
Pk. V T
Proof. From Lemma we have for any (s, a, h k) that
-1 (s, a) O. S Pa Vo (s, + BR (AR)) (s)..
From the definition of y* we have
8) = (ht at - 2 (sh..
Finally, we prove the main theorem, Theorem which asserts that the regret bound of our algorithm is efficient with respect to A and T.
48

---

Proof. Suppose that the Assumptions required in Theorem 8 hold. We condition on the event X' from Lemma with p 5/2 and use the notation for 0% <% as in Lemma 10 From Lemmas and 10 we
have
Regret(K) Σ -V (51) 3 k=1
Σ kE[K] AE(M]
E
5% +
V (P -F RE(K AE(H)
E
E
k=
Since the observations at episode & are independent of the computed value function (this uses the trajectories from episodes I to h 1. it follows { is a martingale difference sequence with 1sh1 < 2H for all (k, ht. Thus, from the Azuma Hoeffding inequality, we have
E kE|K]
log sh s 2og 2HVTI
with probability least 1 1 8/2. For the second term, that the minimum eigenvalue of A least one by construction and [s)]l s we have for all E A and h E [H).
From the Elliptical Potential Lemma (Lemma D.2
K
FA(S)) (AA) (sw) s (
Furthermore, we have | = ((( + XI S + (TRA S K. It follows that
K ((( (A1 < 2d + K/A) S 2d.
Next, by Cauchy-Schwand and grouping the regret by each action, it follows that
1/2
ΣΣ
FA( FFFF <
Σ
VK
- (x(
kE|K] bE[H]
hE[H]
KE[K]
1/2
Σ
VK
Σ
Σ
(A
he(m]
WEA LET
1/2
Σ
VK
Σ
2de
hE(H]
aa
Since 36 cdH Li for some constant from a union bound and the previous bounds, it follows that
RKg & 2H 32 H 22 Ö(V@HBAT)
with probability at least 8.
To use LSVI-UCB-(S, d, A) in our transfer RL setting, we next show that is robust to misspecifica- tion error. Similarly, first prove the helper lemmas needed in the misspecified setting and follow the proof structure and techniques used in [17]
a Lemma 11. For a E-approximate (S, d, A) Tucker rank MDP (Assumption 7) then for any policy
there exists corresponding weight vectors {wf} where wf, (a(a) Eves (s')Uns such that for all (s, a) S x A
(x, FR(S)uN 3HE.
49

---

Proof. Note that Q a) = (s, + E.. V a), so, using the low-rank representa-
tions of Th. Ph. it follows that
(s, a) (s) (n((s, a) - (a(s))a(aa')
Σ (T Fh((s) Σ (5)
8'83
< 3Hg
Lemma 12. Suppose Assumption holds. Let {wh} be the weight vector of some policy n, i.e.
(7, = Fa(s)) wh Then,
| 2Hd..
Proof. Recall that w Wh(a) Eres (s')
UU (s', a). Since the feature mapping sealed du F') ensure the max entries F and W, U are on the same scale, it follows that (a)ll S 1 and Eves (s')uu(, a))l2 I И. Thus, || 2Hd.
up (F), V 8
Similarly, we bound the stochastic noise but account for the misspecification error.
Lemma 13. Suppose Assumption
7 holds. Let 6m be the constant in the definition of $2.n
én Hdvi Ev
/ E [TT,ld)) Then, there exists constant C > 0 that is independent of em such that
for any 8 E (0, 1), if we let the event X be
V(a,k,h) E Ax|K]x[H]]
Σ
((( Pa PPViita
<dH
LETS
(AG.))
where X log(2(c), + 1)dTA/5), then P(X) 2 - - 8/2.
Proof. The proof is the same as the proof Lemma except we increase $2, to account for misspecifiction error. Since ç < by assumption, the modification to $8,,, only affects C.
nI
We next account for the noise being adversarial due to the misspecification error. Lemma 14. Let {ct} be any sequence such that |c-| S B for any t. Then, for any (h, a)
[M] x [K] x A and F E Rdd, we have
FF (AR
Σ
Fn(s))ed S B L LF..
1ETS
Proof. From the Cauchy-Schwarc inequality and Elliptical Potential Lemma (Lemma D.I have
17
|F (A
Σ
Ph(s))alS SB
Σ
FT
Σ
BETE
IET
IET
S B d
|F (Ag
Next, we bound the error between policies Q function and our low-rank estimate.
50

---

Lemma 15. There exists a constant ón such that Pin CdVi + < (T where
(2g(2dAT/p)) and for any fixed policy n. on the event X' defined Lemma 13 we have for all (s, a, h, E S x Ax [H] x [K]
(h(() Thi - a) Pr - VV,t))(s ( where (s, S PE, (s) (AR
+ 4HC.
Proof. From Lemma 12 it follows that there exists a weight vector wf Wh(l)
Eves V (s')(ss)nss'' a). such that for all (s,a) E S x A.
(Q%(,, (s) wfl S 2H
Let P(.|s, a) = F Un( a), so we have for any (s, a) E S x A. Fa(s) = (s(()) ((()))W((a)) + PV (s,a). Therefore,
a, -(A -
a.
Whik 1
+ +A
Σ
(s
LETE-1A
+ (A
Σ (a - V (5t
TE
+ (A
Σ
Fa(s
a) - (o)) (Pr P a))
tE 1-
Now, we bound each the four terms above (of 1e, 43, 94) individually, for the first term, note for all E A
(s) T of = (s) (w, S V P- /l FA(s) -
For the second term, given the event X, we have from Cauchy Schwarz
(s) T 18 < CaH P -
where X log(2(ca A/p) For the third term,
(s) 08 = FT()))
(A) Σ
P. - (iti)(hh.
LET
1.A
=F((s)
(A) Σ ((
T
-
DET 1-1A
S'ES
=F((s)
Σ YES
(V/ h+t (ittil3)Ua((s'aa)
XFF(s)
(Ah.a)
Σ Σ (v/t (1
e'ES
and note that
TT(S)T Σ
(V/ VT (1) = P (ss
WES
and
TsF (AR Σ h+1 W 122IVVA/ S'ES
51

---

Since [|Ph(-ls,a) Px(-ls,))ll I for all (s. E S x A, it follows that
[Pa 4+1 - (8, - Pa(V - (z,1)( & [Pp - Pa)(V R+1 - (iti) a)) & 2Hg.
From Lemma
14 we have (sh(s). 0f) S 2H
(s). Since
Fi((s
T wh [T( = FA(s)) (Wh, - "h = Fi((s) (oft + 12 + 43 + (2);
it follows that
VX(C=
(E) FA(() (A -F + 4HŞ.
Similarly in 17 we choose cp that satisfies C" llo((2) log(ce + 1) S cp v llo(2).
Now, we prove that Q is an upperbound of Q7 conditioned on the event in Lemma 13
Lemma 16. Suppose Assumption holds. On the event X' defined in lemma 13 have (8)
() -
+ 1 - h)g for all (s, a, k, E S x Ax H x [K]. (H -
Proof. We prove this with induction. The base case holds because at step H + 1, the value function zero, so from Lemmal [5]
(s(()) WH
S PR, (i)
4HE
and thus,
Qi((s,a) AHE s min (H. (n)) wh. + 9h, (i((s) ( (s,
From the inductive hypothesis (assuming that (8, > (8, 4H(H - 1))(), follows that Pa(Vit - (s, 2 -4g. From Lemma 15 Fi(s) wh, - (%(3,a) S
PK,Y (s(ss) ()) + 4HŞ. It follows that
(H(5,))-4((H-AA41) min (H, (x)) wh + PR,
This completes the proof.
Similarly, to the regular case, the gap in the misspecified setting has a recursive formula.
Lemma 17, Let & X defined Lemma we have for any (h, k):
(s
Vi (st) and ch+t E(8h 10 ax) 2 Then, on the event
t/ < s + chi1 + Ph
+ +HE
Proof. From Lemma 15 we have for any (s, a, h k)) that
(+(s, (s, PA Vitt + P2, (A FF)(s)) + 4HE.
From the definition of V*a, we have
8 = (h - O (sh,
and substituting this into the first equation finishes the proof.
Finally, prove the main result in the misspecified setting Theorem g
52

---

Proof. Suppose that the Assumptions required in Theorem 9 hold. We condition on the event X' from
Lemma 13 with p 8/2 and use the notation for 6% 5% as in Lemma From Lemma 16 we have
Q (s, a) 2 (s, a) g. which implies (s) VI (s) S 8f + 4H2g. Thus, from Lemma 15 on the event X' it follows that
K
Regret(K)
-VTh))
of + 4
k=1
E Σ AE|H]
+
PR kE|K]
V (A + 4HT5 hе[H]
Σ
since HK = T. Since the observations at episode k are independent of the computed value function (this uses the trajectories from episodes to 1, follows (4%) is a martingale difference sequence with | s 2H for all (k, h). Thus, from the Azuma Hoeffding inequality, we have
c S kE|K]
Σ
S
with probability at least - 5/22. By construction of 3 we have
Σ RE[K]
BE, (n( - SCH()
Σ dvy (A(
kE(K]
Σ KE[K
EV ETTn T -1
From the Cauchy-Schward inequality, it follows that
(V V
= (VK)
Σ KE|KI
FA(S))T(ARE)) Fn
KE|K]
Since the minimum eigenvalue A is at least one by construction and [F) S 1, from the Elliptical Potential Lemma (Lemma D.2 (7]), we have for all a E A and E [M].
FA(())T(AR,N) FF (52) & 2ooggde((N
Furthermore, have ||AR = 11 11EETT ((( + 11 S ITR S + K. follows that
Fa(ss) (((x))(AA,))) (A 2d K/A)) S 2di,
so grouping the episodes by actions gives
1/2
1/2
Σ Fa(s)) (1.5))
Σ
Σ FA(S)) -1E(sh)))())))
$ 2dAi.
=
kE[K]
REALETK...
53

---

For the next term, let ka.; refer to the episode in which action was taken at time step h for the ith time. Then, we first re-index the summation and then use the Bauchy-Schware inequality to get
R
TTEA Fh(( (A 1
(h(()))
Σ AEA
Vi
kE[K]
1/2
1/2
Σ
Σ
(A
REA
IETRA
1/2
C
TK.l
Σ
(
REA
KETRI
C"
where the last incquality comes from holds from the above elliptical potential lemma. Applying the results to the initial inequality, we have
Σ Phn V Br (A S CC(.2 AKG--RAAKKK KE[K]
Σ
[ ( S 2 AMTT
aEA
Substituting these results into the original regret bound gives
RKgret(K)) S C (V + dTHEVO..
for some constant C"" >> with probability least 8.
J.2 LSVI-UCB-(S, d)
We reiterate that the steps and analysis in this subsection are essentially the same the proofs in [7], except we have copies of the weight vectors and gram matrices. The results and proofs follow the same structure and logic 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 A A Wh,K. 2h VAA nh as the parameters/estimates episode k. Furthermore, let V max (s, a) and x be the greedy policy w.r.t. Q We let G := (a
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 's estimate, which allows us prove our concentration result the value function estimate is not constant.
Lemma 18. Let V denote a finction class of mappings from S to R with the following parametric form for all S
(ss = min max W G(a) A3 aEA
where the parameters We 3, Ag satisfy I|wall < L for all s E S, 3 [0, B). and the minimum eigenvalue of A, is greater than x. Assume that ||G(()]] < for all E S, and let N. be the c-covering number of V with respect to the distance dist(V. V') = sup, (V(s) (s)) Then,
log(N.) S dlog(1 4L/c) d log(1 + 8d. Rd (Ac2))
Proof. Equivalently, we reparameterize the function class by D, 3 A for all s
(ss) = min max w G(a)) + (G(a)TD.G(a)) a
54

---

where ||,,1| I L and | & / for all E S. For any V1, 1/2 E V, let them take the form in the above equation with parameters (w,, D,) and (w,, Dz). Since min(., H) and max are contraction maps,
d V2) s sup (w, G(a) + (.GG) - + (G(a)),,GGGa)))))
8,0
1w VG D.G) (w. VGTD.G)
sup s,G:I|G]s]
max #E8
sup
- (w,-
sup
(D, - (DD.-Dr)G
G:||GE1
G: G||
< max
[|w, - -wll + VIID, - -Dx11 S max #ES
[|w, [|w,, - w.sll + VID, - Dx
#ES
where the third inequality holds because / v S v - yl for any x, 2 0. Let C. be an e/2-cover of {w E [| S I.} with respect to the 2-norm, and Cp be an e²/ 22/4-ooer of
{D E Rddd |D| & d2 />} with respect to the Frobenius norm. By Lemma D.5 from [17] we
know that,
|Cwll 1 (1 4L/e)", |CDl S (1 + 8d /32 />xe))
Hence, for any Vi, there exists war E C and D, E Cp for all E A such that V2 parameterized by (wy,, Dx/) satisfies dis((Vi, 1/2) S e. Hence, N₁, 2 |C.n | [pl. which gives:
(og( S log((C, ) + log( (Dl) S dlog(1 + 4cL/e) + de log(1 + B3
We next bound the fo-morm of the weight vector of any policy. Lemma 19. Let {wf,) be the weight vector of some policy n, Le. (8, Gk((a) wf. Then,
| ll S 2HVd.
Proof. Note that QR a) = (s) E. V (s (s'|s, a), so, using the low-rank representa-
tions of The Pr. it follows that
w l2 (s, ) + Σ (" s, lll - (s, ll2 + Σ V (s))un(ssss,
s,
Recall that since the feature mapping scaled up (G₁, v du
A')") to ensure the max entries of G
and W. U are on the same scale, it follows that [s)l( S and Eves Vitta (s')U s)| <
H. Therefore, follows that || S 2H
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 | s 2H /k//.
Proof. For any Gb (a) = we have for all S.
g wh = 1g (AR)
Σ Gnlah) (r(lsaat) + max Qu+ ( deA
IETI_LA
< Σ
g (
BETE_LA
< 2H
g (TAA)) ')(( Σ (Az))))(AA)-GG))))
VETi
BETÉ-N
< 2211lll2y /dle dITE- 2H dk//
55

---

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 The last inequality is due to ||al|2 I and [T k.
next prove the main concentration lemma that controls the estimate.
Lemma 21. Let e' be the constant the definition of BE, =ddH Vt. Then, there exists a constant C 0 that is independent of d such that for any (0, 1), if we let the event X be
E [x]
Σ
Gn (1 PaVit
S CdHlxx
LETT-1AA
(AG
where X log(2(d + 1)dTS/6), then P(X) 1 8/2.
Proof. From Lemma 20 we have |elf S 2H Vak/A X. By construction, the minimum eigenvalue of a is lower bounded by A. Then, from Lemma D.4 in (17] (with 8' =6/S), Lemma [8| and taking union bound over all states, we have that with probability at least 1 82/2, for all E S and e 0,
d log A)/A) log(2SA../)) +
Σ GNlo))(Vi-((s-..)) PA PAV
I 4H²
2
KETY-IAA
(Ag.))1
Then, from Lemma 18 it follows that with probability at least 81/2, for all E S and c > 0,
Gr(ch)(V - Ps V
LETE-LA
(AT,))-
2/1
2 log((k: + 2)/A)) + log(2S/6) + dlog(1 + 4L/e) + df log(1
+ 8k222/1
Choosing 11 Cddli,E dH/k gives that there exists some constant C" such that
Σ
Gh(ah)(V V.Vini
CCdd 1))TT//0))))
LET? 1.A
(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 bounded with high probability.
cadHi Vi where 1og(2dST/p) and for Lemma 22. There exists constant cg such that B
any fixed policy n, on the event X defined in Lemma 21 we have for all hs,a,h,k) E SxSx H [K]:
Ga(a) WH - a))
(s,
where (8)( a) < 3E, (N
Proof. From our low-rank assumption, follows that
()) Gn(a) wf (rn + (s,
56

---

which following the steps from the proof of Lemma B.4 in [17
gives
Whe h R.
S.
+ (A
E
Ph Ga(oh)Pa
TET E-LA
(Aj
(x++)(8,
LET
Now, we bound each term (oi 92. 93) individually, for the first term, note for all S,a A
(G)(a) of (a) (Af,)) S Villoo (A For the second term, given the event X, we have from Cauchy Schwarz
(G)(a) of s CdHl ( (G((()
where X = 1og(2(c3 + 1)dTS/p). For the third term,
Ga Gr(())
(A)w)-))
Σ
GA(d)) Vitt)(s,
IET
Ga(aa
(A Σ
Gn(d))Gh(ah)
Σ (vht (V
TET RETR-I,M 1.4
#ES
Gi(aa)
Σ
(V h+1 VT -5
WES
AGa(a)T
(ARra)
Σ (V (i
s'ES
We note that
Ga(a)²
Σ
(V/2 (iti(())un(ssss)
Pr (s,t))ss
and
[AG((a) (ARr))- Σ (V V/l (
s'ES
Since
(Ga(a) whi (T(s)))) Gn(a) (wh, - w + 99)
it follows that
(G) w - (s, - (itt)ss 0" HH VX Gn Ga)
Similarly in 17 we choose cæ that satisfies O" Vlog(2) log(ce + 1) < ca Iog(2).
This lemma implies that by adding the appropriate bonus, Q is always upperbound of Q7 with high probability
Lemma 23. On the event X' defined lemma 21 we have (8 a) 2 Qi, a) for all (s, h. k) S Ax x [H] x [K].
57

---

Proof. We prove this with induction. The base case holds because at step H + 1, the value function zero, so from Lemma 22
[Gn(a) wh
and thus,
(i)(s, S min (H)) wh + 5R. (AA
(s. a).
From the inductive hypothesis (assuming that Q ah+1 (s,a) 2 12+1 (8, a)), it follows that Ps h+1 (s, a) 2 O. From Lemma 22 Ga(a) T wh. (x S B V (N (A
follows that
(x( S min (H,Gr(a) wh. + SR.
= ())
We next show that Lemma 22 transforms the recursive formula 6) (s
Vn V (s)))
Lemma 24, Let 6% X' defined in Lemmal
Vi (s%)
V (s%) and 4 = 18(0% + 10% s op Then, on the event
we have for any (h, k):
ch+1 + BR, TA
Proof. From Lemma 22 have for any (s, a, h, that
()( - Q (s, PN -
V (itt)(s, +
(a).
From the definition of V**, we have
8 (s at) 2 (sh, at))
Finally, we prove the main theorem, Theorem
5
Proof. Suppose that the Assumptions required in Theorem 5 We condition on the event X' from Lemma 21 with p = 6/2 and use the notation for ot. 5% as Lemma 24 From Lemmas and 24 we have
K Regret(K) = -
K
Σ
ck B
Σ
Σ
Ga(at)
k=1
1=1
kE[R] KE(m)
kE(K] KE(H]
Since the observations at episode k are independent of the computed value function (this uses trajectories from episodes 1 to A 1, it follows ( is martingale difference sequence with |sh1 < 2H for all (ke, h). Thus, from the Azuma Hoeffding inequality, we have
Σ kE
ch S 2/2TH2log(2//) < 2H
with probability least 1 5/2. For the second term, we note that the minimum eigenvalue of A least one by construction and |G,, (a)]l 1. From the Elliptical Potential Lemma (Lemma D.2 17), have for all S and f E [H].
K
Ga(a)t (Ai,,) (A s (A dct(Af.o))
58

---

Furthermore, we have ||A M 1aad11l1En |IEETT Gala))Gh(aa) + XI & A T & SA+K.
=
follows that
Σ (r s 2d + K/A) S 2d.
Next, by Cauchy-Schward and grouping the regret by each state, it follows that
1/2
Σ Σ kE|K] AE(H]
(A
<
E
VK
Σ KE[K]
(n(a))
(A
(A
hE(M]
1/2
E
VK
Σ
E
(A2,)
NE[H]
SES LETR
1/2
Σ
VK
Σ
2dl
NE(M
- HVSKdd.
Since 3i. edH V for some constant c, from a union bound and the previous bounds, it follows that
Regret & 2H 8 H HV2KS E ((V
with probability at least 6.
Next, we prove the helper lemmas needed in the misspecified setting and follow the proof structure and techniques used in [17.
Lemma 25. For É-approximate (S, S,d) Tucker rank MDP (Assumption 4), then for any policy there exists corresponding weight vectors {wff where wf, = En Ws(s)) + Eves V (s' such that for all (s, a) E E A
-Gnsaa) S 3HE.
Proof. Note that a) rs, + E, 1 (s a), so, using the low-rank representa- tions of rh: Ph. it follows that
QT a) Ga(a)uū"
Σ [Vi1(66)P(((11100) Ga(a) Σ (it $ (1)(8, a) (+)
e'ES
S +H2
< 3HG.
Lemma 26. Suppose Assumption 7 holds. Let {wi}} be the weight vector of some policy n, i.e.
(T = (a) wi. Then,
|wg|| < 2H.d.
Proof. Recall that wf, EnWa(s) Eves V (s))U((' 8). From the argument used prove Lemma 19 it follows that || 2 < 2H
Similarly, we bound the stochastic noise but account for the misspecification error.
59

---

Lemma 27. Suppose Assumption 7 holds. Let ém be the constant in the definition of Pk.
én (dvi + Ev 1/TTA Then, there exists constant >> 0 that is independent of Cn such that for any 5 E (0, 1), if we let the event X be
ki, E [
Σ
Ga(ot)(V++s(hhh)) - Ps Po
S cdH
BETE-LA
(A6,0)
where X 1og((2((,,, L)dTS/6), then P(X) 2 88/2.
Proof. The proof is the same as the proof of Lemma 21 except we increase 3h,n to account for the misspecifiction error. Since ç < 1 by assumption, the modification to 38, only affects C.
Next, we account for the adversarial misspecification error.
Lemma 28. Let } be any sequence such that |erl S B for any t. Then, for any (h, k, [H] x [K] x S and G E Rd, we have
|G (ALA)
Σ
Ga(o)all S / (AT
BET
Proof. From the Sauchy-Schwarr inequality and Elliptical Potential Lemma (Lemma D.1 have
17
|G (AR
Σ
GaldNaal
Σ rET L.
GT(AL
(A TET7
Σ
BETE
S B B (A (AEW)-GG.
Next, we bound the error between policies Q function and our low-rank estimate.
Lemma 29. There exists a constant ém such that $2,n = c,, (dV/ + Ev [T dd) where 1
log(2dST) /p) and for any fixed policy n, on the event X defined Lemma 27 we have for all (s, h k) SSS S [H] [K]:
(a wh - ()) = PP
+ (
where (s, a)l < 3
+ 4HE
Proof. From Lemma 25 it follows that there exists a weight vector wa Wh(a) Eves Vil (s')Un(s' 5), such that for all (s,a) E S A.
(x, TT < 2HC.
Let P(-|s, a) = Gn(a) Un(,, so we have for any (8, E x Gn(a) Twf =Gaaa
PV h++1 as, Therefore,
Wh wh ->(A
-
5.
+ (Aj..)
Σ
Gn
- (s,
TET
+ (AAA))
Σ Go(o)))a
(o, ah)
LET
+ +(AA,))
Σ
Gn(af)) (ra(s, Ga(ah)Wa(() + (Pr P,)
LET
60

---

Now, we bound each of the four terms above (9ì: 92. 93. 92) individually, for the first term, note for all E
(G)(a) di (aG (AR,)) "
V Iv y (AR,))
For the second term, given the event X, we have from Cauchy Schwarz.
[Ga(a) Øf - CCHlxy/GalaTTT
where X 1og(2(c3 + 1)dTS/p). For the third term,
Gn(a) 23 = =G(aaa
(Aj,a) E
Gald - Vitt)(s,
RETE-LA
=G(aa)
(Ap
Σ Gn(ah)Ga(ah)) T
(V Σ
h+1 (171)(6)000(66600)
LET E-1A
r'ES
=G((a)
Σ
h+1 (
N'ES
(AAI.)
AG
(V Σ
Vh (5
2'ES
and note that
Gn(a)
Σ
V ( -Pa - (8,1)
WES
and
(AGa(a) (NiLw)
(V/1 V V1++)(6))
| /22IINNN/CCTTAAN
S'ES
Since [|Pa(-1s,a) PP a) I for all (s, E x A, it follows that
[Pa (s. Pa (V V (s, (P,, PA) - 1 a)l s 2HE
From Lemma 28. we have (Gn(a), 47l - 2HE / GTT))
Since
(G) T = (wi, - - = (gf + 4 + +2)
it follows that
(G) wf,A Px.
Vx(C"dxx+22 v (T (d) (AR, (AR,))
Similarly as in 17 we choose eæ that satisfies C" (log(2) logica + S ca l2o
Now, we prove that Q is an upperbound of Qi, conditioned on the event in Lemma 27
Lemma 30. Suppose Assumption 7 holds. On the event X defined lemma 27 we have (s,
-H
- h)g for all (s, a, k,) E S Ax H x []]
Proof. We prove this with induction. The base case holds because at step H + 1, the value function zero, so from Lemma
(a) T whe - (s. <
+ 4HE
61

---

and thus,
Qn((s,) 4HŞ < min HH GH()) whi + SR, (i(l)) ()
G)((()) = (s.
From the inductive hypothesis (assuming that Qh (s, a) 2
Q (5, 411 h))))
follows that PA - (i+ a) 2 -45. From Lemma
29 Gn((a) T wh - (h(s,a) -
P V (aa(a)((f..)) ( 4Hg. It follows that
a)) (H - min H, Ha))) whe + /
= ( (s,a) a).
Similarly, to the regular case, the gap in the misspecified setting has recursive formula.
Lemma 31. Let 6% v (s V (s%) and ch+1 El sh. agi tht Then, on the event X defined in Lemmal 27 have any (h, k):
Sh+1 + P.. Gn ( (Ga(()))) + +HHE 8/ - 8h
Proof. From Lemma 29 have for any (s, h., k:) that
VTt (s, (,, a) - 2 (8 Pa(V -
+ B Gn(a) --Gn)))) 4HE.
From the definition of V we have
8f Qh (sh at) Q (sh, af),
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 holdd. We condition on the event X' from
Lemma 27 with p 8/2 and use the notation for 6t 5% in Lemma 31 From Lemma [6 we have
Q a) (s, a) 4. which implies (s)(s 29 on the event X, it follows that
Vi (s)
I 5 A11 Thus, from Lemma
K
Regrel(K)
Σ (V - VT
S
4H2g
1=1
3 S Σ [E(
SEA Σ
( GG 4HTE hE(M]
V
kE[R] NE(M]
since HK- T. Since the observations episode is independent of the computed value function (this uses the trajectories from episodes to k - 1, it follows {$A] is a martingale difference sequence with | < 2H for all (k, h). Thus, from the Azuma Hoeffding inequality, we have
Σ kElR],kEn
t S (ogH2)og(2ppp s 2H
with probability at least - Noe that
Bi V GA
RE(K]
<CH( E CT
Σ /
KE(K]
kE[K]
62

---

From the Cauchy-Schwarz Schwarz inequality, it follows that
(1
Σ (V - (VK) [E[K]
Σ kE[K]
Gn(af)
-
Let k; refers to the episode in which state s was seen at time step for the ith time. Then, for the other term, first rndix the summation and then use the Cauchy-Schin Schwarz inequality to get
Tkaal E
E ke[K]
TEaly
Σ
viv
GT
(A2. GG
(A
ITaal
1/2
Σ i
Σ TETRA
1/2
S k.
Σ TETRA
CL Gk,h
for some absolute constant C > 0. Since the minimum eigenvalue A, is at least one by construction and [ < 1, from the Elliptical Potential Lemma (Lemma D.2 177). we have for all E and h [H]
Σ GRR) (AA) -G s 2lggdde(((
Furthermore, have 11i, 1EEETT Cn( + XIll S + IT S K. It follows that
K Σ (A) S 2dlog(1 + K/A) s 2di
A=
so grouping the episodes by actions gives
1/2
1/2
Σ Gn(att (AA -G
Σ
Σ
S 2dSt
KE[A]
SES DETKi.
Thus,
Bh,n (a(a))TAA - < CH + +EVaC" Σ
IT (TE.IV/dd 2di
K
SES
C(V208HI2 + ( (V
Substituting these results into the original regret bound gives
Regrel( K) S C"" (" + dTH.V)).
for some constant C" 0 with probability least 1-6 8.
63

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our claims in the abstract and introduction reflect our theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the optimality of our theoretical guarantees with respect to the parameters of the problem. We highlight that our algorithm is sub-optimal with respect to the rank and horizon of the MDP.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
64

---

Answer: [Yes]
Justification:
We include all assumptions and proofs for each theorem in this work.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: There experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
65

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
There is no data or code used in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cippscc/puullc//uuu /otee//guudddeeeeoSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experiments or data used in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: There are no experiments or data used this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
66

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative enrrr rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: There are no experiments, so there were 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 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 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:/pp///aaoroo.c.cccaaaaaaaaa
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 NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. 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 foundational research by proving theoretical bounds trans- fer 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 why the paper does not address societal impact.
67

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe 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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA].
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
68

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: Our paper's 's contribution is theoretical and does not realease new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
69


Reviews:
[{"review_id": "7XNOdWHRtF", "reviewer": "Reviewer_Stu9", "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.", "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?\n2. 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?\n3. 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.\n4. 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? \n5. To improve interpretability, I suggest adding a column in Table 1 and listing the target regret bounds with known latent representations.", "limitations": "The limitations are addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(+) The paper considers different types of low-Tucker-rank MDPs, corresponding to different factorizations of the transition kernel, which can provide new insights into the literature.\n\n(+) The derived source sample complexity does not scale with the size of the given function class.\n\n(+) An information-theoretic lower bound is derived for the source sample complexity, and the proposed algorithm for $(d,S,A)$-Tucker-rank is minimax optimal respecting the transfer-ability coefficient $\\alpha$.", "weaknesses": "(-) The target regret bound grows polynomially in the number $M$ of source MDPs.\n\n(-) 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate reviewer Stu9’s feedback and suggestions on how to improve our paper. We completely agree that our paper would benefit from adding a column listing the target regret bounds in Table 1 and will add it to the final version.\n\n**Weakness 2:** We realize that our terminology is misleading in Assumption 3. Our “full-rank” $Q^*$ assumption asserts that $rank(Q^*) = d$, not that $rank(Q^*) = \\min(S, A)$. We have fixed this for the final version and have removed the mention of “full-rank”.\n\n**Q1:** The algorithm from [4] does not work in the $(S, S, d)$ and $(S, d, A)$ Tucker rank settings due to the difference in structural assumptions on the transition kernel. Specifically, [4] assumes low rank structure across the transition forward in time (between $s’$ and $(s, a)$) whereas in our work, we assume that there is low rank structure between $(s, s’)$ and $a$ or $(a, s’)$ and $s$. As a result, our algorithm learns feature mappings and weight vectors with different dimensions than in [4]. In the $(d, d, d)$ Tucker rank setting, one could use the algorithm in [4], which admits a target regret bound that matches ours with respect to $d, T, S, A$. However, our source sample complexities differ as the one using algorithm [4] depends on the size of the function class that the feature representations belong to instead of $\\mathcal{S}$ or $\\mathcal{A}$, and our algorithm does not require a computationally inefficient oracle in the source phase. \n\n**Q3:** We apologize for the typo/mistake as they mean the same thing. The main difference in our models is that in [4] each MDP, source and target, share the same d-dimensional feature mapping while ours only assumes that the space spanned by the target feature mapping lies in the space spanned by the source feature mappings. This means that our results actually allow the target MDP to have up to $dM$-feature mapping if each of the $M$ source MDP subspaces are disjoint. \n\n**Q4:** In our lower bound, the learner is given one of two transfer RL problems, 1 and 2, with equal probability where the one latent feature is optimal in problem 1 and the other is optimal in problem 2. The two latent factors are orthogonal to each other, so choosing the wrong latent feature is no better than randomly guessing a latent feature. Thus, to benefit from transfer learning with high probability, one must identify which transfer RL problem they are dealing with. To do so, one must determine if the $Q$ function from the second source MDP is $Q_{2, 1}^{ \\*, 1} $ or $Q^{\\*, 2}_{2, 1}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LQJ4e0UYZZ", "reviewer": "Reviewer_nw9E", "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", "questions": "- The paper assumes specific structures for the MDPs. How robust are the proposed methods to deviations from these assumptions?\n- 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?\n- 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.\n- Could the authors clarify the practical implications of the transfer-ability coefficient in real-world scenarios? How can one estimate this coefficient in practice?\n- 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?\n- Typos\n    - Inconsistency in Line 150 and Figure 1 caption. It seems $(S, S, d)$ Tucker rank.\n    - Line 352: Algorithm 2, 2,", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The work introduces novel algorithms for transfer RL with latent low-rank structures. It explores multiple Tucker rank settings, offering a comprehensive framework not fully addressed in prior works.\n- The introduction of the transfer-ability coefficient $\\alpha$, which quantifies the difficulty of transferring latent representations, is a novel concept that enhances the understanding of transfer dynamics in RL.\n- The submission is technically sound, with rigorous theoretical analyses supporting the claims, though the reviewer couldn’t check the correctness of all details. The problem is well-formulated, and the methods used are appropriate and well-executed, indicating a complete work.", "weaknesses": "- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate reviewer nw9e’s feedback and suggestions on how to improve our paper. We completely agree that our paper would benefit from numerical experiments and will look into running simulations to illustrate the benefits of our algorithm. \n\n**Q2&4:** Regarding estimating $\\alpha$, $\\alpha$ is a fundamental quantity in each transfer RL problem. The significance of $\\alpha$ is that for large $\\alpha$, transfer learning approaches will perform worse than tabular MDP algorithms which ignore the source MDPs. While our source sample complexity and target regret bound depend on $\\alpha$, we emphasize that **one does not need to know $\\alpha$ to run our algorithm.** When running our algorithm in practice, one should observe as many samples in the source phase as allowed by their computational budget/constraint to obtain the best performance on the target problem. \n\n**Q5:** Our approach will work for a multi-task learning setting with multiple target MDPs, as long as each of the target MDPs satisfy our transfer learning assumption (Assumption 2), i.e., each target task’s feature representation lies in the space spanned by the source MDP feature representations. Our algorithm would proceed in the same way to estimate the subspaces in the source phase, and then would run LSVI-UCB-(S, S, d) on each target MDP subsequently, assuming that all MDPs have transition kernels with Tucker rank $(S, S, d)$. The same approach works in the other Tucker rank settings. \nOur approach differs from policy distillation algorithms as we only require the feature representation from the target MDP to be contained in the space spanned by the source MDP feature representation. While one typically transfers a policy or $Q$ function from a teacher (source MDP) to a student (target MDP) in policy distillation, in our setting, the optimal $Q$ function and policy in the source MDPs can be very different from the optimal $Q$ function and policy from the target MDP. Therefore, with our assumptions, transferring only a policy or $Q$ function can lead to no improvement on the student or target MDP.\nOur setting is similar to the meta RL setting as the agent attempts to learn information from the source MDPs or meta tasks to improve the efficiency of learning in the target MDP. By learning a sufficient feature representation from the source MDPs (meta tasks), one can learn a good policy with significantly fewer samples, which is the goal in meta RL.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lFzJ92bOjz", "reviewer": "Reviewer_LmTe", "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.", "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. \n\n1. I do not understand the proof of Theorem 1:\n\na. 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$. \n\nb. In line 508 $c = \\sqrt{1+1/\\alpha^2}$ is not bounded by $2$ as $\\alpha \\rightarrow 0$...\n\nc. 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'$.\n\nd. 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.\n\ne. 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. \n\n 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]\"?\n\ng. Theorem 1 requires Assumptions 1 and 2 but the proof involves Assumptions 5 and 6 \n\nh. Assumptions 1 and 2 are assumptions on transition matrices but in the proof these are deduced directly from the form of the $Q$-functions\n\n 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?\n\nj. 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}$.\n\n2.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)\n\n3. 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\n\n4. 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)$\n\n5. 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)$...\n\n6. 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.\n\n7. p.7 l.281 $Q_{h,m}^{\\ast}$ should be $Q_{m,h}^{\\ast}$\n \n8. p.7 l.290: I think $s_{h+1}^{k}$ should be $s_{h+1}^{t}$.\n \n9. p.9 l.352 \"Algorithm 2, 2\": remove one 2\n\n10. 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?\n\n11. 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.\n\n12. 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. \n \n12. p.36 in Prop.2 the second bound should involve $V_j^{\\ast}$ instead of $U_j^{\\ast}$ in the right hand side\n\n13. 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}$.\n\n14. p.39 l.1131 in the first equation there is a $\\top$ sign that should be in exponent\n\n15. p.48 l.1323 $s$ appears both as an argument of $V$ and in the maximum\n\n16. p.49 l.1331 a word is missing in \"where the holds\"\n\n17. p.49 l.1340 I do not understand where the last inequality comes from\n\n18. 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\n\n19. p.49 in the 3rd equation of l.1345, there is no $\\top$ on the second $g$ term", "limitations": "The authors addressed the limitations of the paper.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The numerous results are novel and of interest. The paper is really complete in considering basically all the possible assumptions of low-rank that can be made on the transition matrix.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer LmTe for the suggestions on how to improve the presentation of our paper and have made the modifications for the final version. We have corrected the typos addressed by points 1a, 1c, 1g, 1j, 3, 4, 5, 6, 7, 8, 9, 13, 15, 16, 17, and 20. \nRegarding Theorem 1, the key idea is that we can construct two transfer RL problems with similar source $Q^*$s but use orthogonal feature representations in the target phase. As the learner is given one of the transfer RL problems with equal probability, they must identify which one it is to avoid using an orthogonal feature mapping with high probability. To identify the transfer RL problem, one must distinguish between the $Q^*$ from the different source MDPs, which depends on $\\alpha$, the parameter to the result. From standard hypothesis testing sample complexity lower bounds (we need the noise variable to be Bernoulli to use this result), one must incur a sample complexity of $o(\\alpha^2)$ to identify the correct transfer RL problem and feature mapping.  \n\n1b: Thank you for pointing this out. We will clarify that $\\alpha$ is lower bounded by 1/(dM) (see Lemma 2). With a loose upper bound, it follows that $c \\in (1, 2dM)$. As $d, M > 1$, we have that $2\\alpha dM > \\alpha$ and still require that one must observe $o(\\alpha^2)$ samples to benefit from transfer learning.\n\n1e: The Bernoulli variable specifies the noise model in our setting; one observes a realization of a Bernoulli random variable when specifying a $Q^*$ and state-action pair to observe from. We chose Bernoulli random variable as our noise model to use the result from [5].\n\n1f: Thank you for pointing this out. The relevant result is Lemma 5.1 from [5] by setting $\\delta = 0.24$, and we have added this to our paper.\n\n1i: Yes, these matrices are block matrices. Thank you for your suggestions. We will emphasize this. Also, as the matrices are rank 1, the columns are orthogonal to each other. Furthermore, the norm of each block vector is 1 when accounting for the size of the blocks. \n\n10: First, note that from Assumption 3, $\\|Q^\\*\\|\\_{\\infty} \\geq C$, so $\\frac{1}{\\sigma\\_d} \\leq  \\frac{\\|Q^\\*\\|\\_\\infty }{ C\\sigma\\_d}$. From the last equation on page 48 from [28], we have that $\\frac{\\|Q^\\*\\|\\_\\infty}{C\\sigma\\_d} \\leq \\frac{\\kappa d \\mu}{\\sqrt{S A} C}$. Thus, we have $\\bar{\\gamma} \\leq \\frac{ \\kappa d \\mu }{ (\\sqrt{S A} C)}  \\sqrt{S A} \\|D\\|\\_\\infty$. From the source sample complexity, it follows that $\\|D\\|\\_\\infty \\leq \\frac{C}{2d\\mu}$, which proves that $\\bar{\\gamma} \\leq \\frac{1}{2}$. Thank you for pointing this out, we will add more intermediate steps and clarification in the text. We have updated Corollary 3 as it was missing a factor of $\\mu$.\n\n11: Thank you for catching these errors. We have redefined our definition of misspecified low Tucker rank MDPs to $| \\sum\\_{s’ \\in \\mathcal{S}} P(s’|s, a) - G(a)U(s’, s) | \\leq \\xi$ instead of using the total variation distance as our analysis holds with the above definition. \n\n14: We first show that $\\bar{\\gamma} = \\frac{\\|D\\|\\_{op}}{\\sigma\\_r} = \\frac{\\kappa d \\mu \\|D\\|\\_\\infty}{C}$. Combining this with the definition of incoherence and Proposition 2, we get the result of Corollary 3. \n\n18: recall that since the feature mapping was scaled up ($G_h = \\sqrt{\\frac{A }{d\\mu}} G'$) to ensure the max entries of $G$ and $W, U$ are on the same scale, it follows that $|W\\_{h}(s)|\\_2 \\leq 1$ and $ \\|\\sum\\_{s' \\in \\mathcal{S}} V\\_{h+1}^\\pi(s') U\\_{h}(s', s) \\|\\_2 \\leq H$. Therefore, it follows that $\\|w\\_h^s\\|\\_2 \\leq 2H\\sqrt{d}$.\n\n19: The rightmost term is upper bounded by $\\sqrt{d}$ from Lemma D.1 in [15]. As $|T_{k-1, h}^s| \\leq k$, it follows that $\\sqrt{ \\sum_{t \\in T_{k-1, h}^s} g^\\top (\\Lambda\\_h^s)^{-1} g} \\leq \\sqrt{k  g^\\top (\\Lambda\\_h^s)^{-1} g}$. Since $ \\Lambda\\_h^s $is real and symmetric with smallest eigenvalue lower bounded by $\\lambda$, it follows that the largest eigenvalue of $(\\Lambda\\_h^s)^{-1}$ is upper bounded by $\\lambda$. It follows that  $g^\\top (\\Lambda\\_h^s)^{-1} g \\leq \\|g\\|_2^2/\\lambda$ from the fact that the maximum value a Rayleigh quotient $ (g^\\top (\\Lambda\\_h^s)^{-1} g/ g^\\top g) $is the largest eigenvalue of $(\\Lambda\\_h^s)^{-1} $(see Theorem 4.2.2 from Matrix Analysis by Horn et al).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewer’s feedback and suggestions. We discuss the primary shared concerns of the reviewers below, and have deferred addressing clarification questions to the individual reviewer rebuttals. We will incorporate the below discussion into the final paper.

**Intellectual novelty (nw9E):** Our major contribution is understanding the benefits of assuming low-rankness along any one of the three modes of the transition kernel in transfer RL, whereas [4] only considers a single mode of low rank structure. Our algorithms in the $(S, S, d)$ and $(S, d, A)$ Tucker rank settings are novel as directly using any linear MDP algorithm, e.g., UCB-LSVI from [15] used in [4], does not achieve our $\sqrt{S}$ or $\sqrt{A}$ dependence (it attains a suboptimal scaling of $S$ or $A$). Additionally, we provide information theoretic lower bounds that prove the optimality of our algorithms with respect to $\alpha$, which is an open question posed in [4], and extend the concept of the transferability coefficient to the additional modes of low rank structure beyond what is considered by [4]. Finally, in contrast to the algorithm in [4], our algorithm does not require access to a computationally inefficient oracle.

**Motivation of our low Tucker rank and incoherence assumptions (Stu9, nw9E):**  Any block MDP satisfies our low Tucker rank assumption, whether the block membership is known or not, as the complexity of the problem scales with the number of latent states/actions (i.e. blocks) instead of the size of the observable spaces. As long as the blocks are not too small, then the MDP will also satisfy incoherence. Another example in which approximately low rank structure will likely hold is a discrete MDP with state and action spaces that can be well approximated by a smooth continuous population distribution. For example, a large population of users and products from a recommender system could likely be approximated by a smooth distribution of user types and product types. Alternatively, the MDP could have been constructed by a discretization of a continuous MDP, e.g. stochastic control tasks. In these MDPs, the complexity of the discrete state and action space depends primarily on the smooth continuous distribution instead of the size of the discretized space. Thus, the complexity, or rank or Tucker rank, of the reward function and transition kernel, respectively, is likely to be approximately low dimensional, i.e. independent of $S, A$. [Udell et al. 2018] formalized this argument for matrices, showing that smoothness conditions lead to approximate low rank structure; a slight modification of their analysis should also extend to tensors. Additionally, due to the smoothness conditions, the MDP would likely satisfy incoherence as there cannot be a small number of states or actions that deviate significantly from all other states and actions. 

When the MDPs have only approximately low Tucker rank, our results degrade smoothly with respect to the misspecification error. In particular, assuming that the source MDP’s and target MDPs’ reward functions are $\tau$ away from a low rank matrix with respect to the $\ell_\infty$ norm and the transition kernels are $\tau$ away from a low Tucker rank transition kernel with respect to the total variation distance (see Assumption 5 from [29]), in the $(S, S, d)$ Tucker rank setting, our algorithm’s source sample complexity remains the same while the target regret bound becomes 
$$
{O}(\sqrt{(dMH)^3A T} + \kappa^3\mu^3d^4M^2H^3 \tau T \sqrt{\frac{A }{S }}).
$$
Thus, if the cardinality of the state and action space are proportional to each other, our algorithm degrades smoothly with respect to the misspecification error, incurring an additional regret of ${O}(\tau T \text{poly}(d, \kappa, \mu, M , H))$.
	Determining which of our algorithms to use depends on what structure is present in the problem. For example, if one believes that only the actions live in a much smaller dimensional space, then one should use the $(S, S, d)$ Tucker rank algorithm. However, if both states and actions have low rank representations, one should use the $(d, d, d)$ Tucker rank algorithm. 

**Dependence on $M$ (Stu9):** Our target regret bound grows polynomially in $M$ because the feature mapping we learn in the source phase has dimension $dM$ as we take the union of the feature mappings from each of the $m \in [M]$ source MDPs. As one has not interacted with the target MDP, they cannot identify which of the $dM$ dimensions of the learned feature mapping are unnecessary, and removing a necessary dimension will lead to a linear in $T$ regret bound. Thus, one must use the full $dM$ feature mapping to ensure the feature mapping is sufficient. We remark that our results hold for relaxed assumptions when the Tucker rank of the source MDPs are $(S, S, d)$ and the Tucker rank of the target MDP can be as large as $(S, S, dM)$, as the main assumption we need is only that the feature mapping in the target MDP can be represented by a linear combination of the feature mappings from the source MDPs.

Finally, we thank the reviewers for catching mistakes and typos and have fixed them in the final version.

Meta-review: 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.
Decision: Accept (poster)