Provable Benefits of Representational Transfer in Reinforcement Learning
Authors: Alekh Agarwal
Yuda Song
Wen Sun
Kaiwen Wang
Mengdi Wang
Xuezhou Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning theory
representation learning
transfer learning

Abstract: We study the problem of representational transfer in RL, where an agent first pretrains in a number of source tasks to discover a shared representation, which is subsequently used to learn a good policy in a target task. We propose a new notion of task relatedness between source and target tasks, and develop a novel approach for representational transfer under this assumption. Concretely, we show that given a generative access to source tasks, we can discover a representation, using which subsequent linear RL techniques quickly converge to a near-optimal policy, with only online access to the target task. The sample complexity is close to knowing the ground truth features in the target task, and comparable to prior representation learning results in the source tasks. We complement our positive results with lower bounds without generative access, and validate our findings with empirical evaluation on rich observation MDPs that require deep exploration.


Under review as a conference paper at ICLR 2023
PROVABLE BENEFITS OF REPRESENTATIONAL TRANSFER IN REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We study the problem of representational transfer in RL, where an agent first pretrains in number of source tasks to discover shared representation, which is subsequently used to learn a good policy in a target task. We propose a new notion of task relatedness between source and target tasks, and develop a novel approach for representational transfer under this assumption. Concretely, we show that given generative access source tasks, using which subsequent linear RI. techniques quickly converge to a near-optimal policy, with only online access to the target task. The sample complexity is close to knowing the ground truth features in the target task, and comparable to prior representation learning results in the source tasks. We complement our positive results with lower bounds without generative access, and validate our findings with empirical evaluation on rich observation MDPs that require deep exploration.
discover representation,
INTRODUCTION
Leveraging historical experiences acquired learning past skills to accelerate the learning of new skill is a hallmark of intelligent behavior. In this paper, we study this question in the context of reinforcement learning (RL). Specifically, we consider a setting where the learner is exposed to multiple tasks and ask the following question:
Can we accelerate RL by sharing representations across multiple related tasks?
There is rich empirical literature which studies multiple approaches to this question and various paradigms for instantiating it. For instance, in multi-task learning scenario, the learner has simultaneous access to different tasks and tries to improve the sample complexity by sharing data across them (Caruana, 1997). Other works study a transfer learning setting, where the learner has access to multiple source tasks during a pre-training phase, followed by a target task (Pan and Yang, 2009). The goal is to learn features and/or policy which can be quickly adapted to succeed in the target task. More generally, the paradigms of meta-learning (Finn et al., 2017), lifelong learning (Parisi et al., 2019) and curriculum learning (Bengio et al., 2009) also consider related questions.
On the thcoretical side, questions of representation learning have received an increased recent emphasis owing to their practical significance, both in supervised learning and RI. settings. In RI,, limited form of transfer learning across multiple downstream reward functions is enabled by several recent reward-free representation learning approaches (Jin et al., 2020a; Zhang et al., 2020; Wang et al., 2020; Du et al., 2019; Misra et al., 2020; Agarwal et al., 2020; Modi et al., 2021). Inspired by recent treatments of representation transfer in supervised (Maurer et al., 2016; Du et al., 2020) and imitation learning (Arora et al., 2020), some works also study more general task collections in bandits (Hu et al., 2021; Yang et al., 2020, 2022) and RL (Hu al., 2021: Lu al., 2021). Almost all these works study settings where the representation is frozen after pre-training in the source tasks, and linear policy or optimal value function approximation is trained in the target task using these learned features. This setting, which we call representational transfer, is the main focus of our paper.
crucial question formalizing representational transfer settings is the notion of similarity between source and target tasks. Prior works in supervised learning make the stringent assumption that the covariates x follow the same underlying distribution in all the tasks, and only the conditional P(y|æ) vary across tasks (Du et al., 2020). This assumption does not nicely generalize to RL settings, where state distributions are typically policy dependent, and prior attempts to extend this assumption to RL (Lu et al., 2021) result in strong assumptions the learning setup. Other works (Hu et al.,

---

Under review as a conference paper at ICLR 2023
2021: Yang et al., 2020, 2022) focus on linear representations only, which limits the expressivity of the feature maps, and does not adequately represent the empirical literature in the field.
Our contributions. In this context, our work makes the following contributions:
We propose a new linear span assumption of task relatedness for representational transfer, where the target task dynamics can be expressed as deeendeet))))) linear span of source task dynamics, in addition to the dynamics being low-rank under a shared representation. We give examples captured by this assumption, and it generalizes all prior settings for representational transfer in RL. We do not make any linearity assumptions on our feature maps.
When we have generative access source tasks, we provide a novel algorithm REPTRANSFER that successfully pretrains a representation for downstream online learning in any target task (i.e., no generative access in target task) satisfying the linear span assumption, when the source tasks satisfy a common latent reachability assumption. The regret bound of learning in the target task is close to that of learning linear MDP equipped with the ground truth features, the strongest possible yardstick in our setup. The additional terms in our regret largely arise out of the distributional mismatch between source and target tasks, which is expected. We complement the theory with an empirical validation of REPTRANSFER on the challenging rich observation combination lock benchmarks (Misra et al., 2020), confirming our theoretical findings.
Without generative access to source tasks, we show the statistical hardness of representational transfer under the linear span assumption, and confirm this hardness in our empirical evaluation. We show that additional assumption that every observed state is reachable in every source task is sufficient for allowing fully online learning in source tasks.
The new task relatedness assumption, reward-free learning result for low-rank MDPs and our analysis of LSVI-UCB under average case misspecification may be of independent interest.
2 RELATED WORK
In this section, we focus on survey related works that obtained concrete PAC or regret guarantees, and we defer discussion of the empirical literature to the appendix.
Multi-task and Transfer Learning in Supervised Learning. The theoretical benefit of represen- tation learning are well studied under conditions such as the i.i.d. task assumption (Maurer et al., 2016) and the diversity assumption (Du al., 2020; Tripuraneni et al., 2020). Many works below successfully adopt the frameworks and assumptions to sequential decision making problems.
Multi-task and Transfer Learning in Bandit and small-size MDPs. Several recent works study multi-task linear bandits with linear representations (ø(s) = A with unknown A) (Hu et al., 2021; Yang et al., 2020, 2022). The techniques developed in these works crucially rely on the linear structure and can not be applied to nonlinear function classes. Lazaric et al. (2013) study spectral techniques for online sequential transfer learning. Brunskill and Li (2013) study multi-task RL under fixed distribution over finitely many MDPs, while Brunskill and Li (2014) consider transfer in semi-MDPs by learning options. Lecarpentier et al. (2021) consider lifelong learning in Lipschitz MDP. All these works consider small size tabular models while we focus on large-scale MDPs
Multi-task and Transfer Learning in RL via representation learning. Beyond tabular MDPs, Arora et al. (2020) and D' Eraam et al. (2019) show benefits of representation learning imitation learning and planning, but do not address exploration. Lu et al. (2021) study transfer learning in low-rank MDPs with general nonlinear representations, but make generative model assumption on both the source tasks and the target task, along with other distributional and structural assumptions. We do not require generative access to the target task and make much weaker structural assumptions on the source-target relatedness. Recently and independently. Cheng et al. (2022) also studied transfer learning in low-rank MDPs in the online learning setting, identical to the setting we study in Section 5. However, their analysis relies the population TV error, which we show is in fact not necessary (details in Appendix C).
additional assumption that bounds the point-wise TV error with
Efficient Representation Learning in RL. Even in the single task setting, efficient representation learning is an active area witnessing recent advances with exploration (Agarwal et al., 2020; Modi al., 2021; Uehara et al., 2021; Zhang et al., 2022) or without (Ren et al., 2021). Other papers study feature selection (c.g. Farahmand and Szepesvári, 201 Jiang et al.. 2015; Pacchiano et al., 2020; Cutkosky et al., 2021; 1; Lee al., 2021; Zhang al., 2021) or sparse models (Hao et al., 2021a.b).
2

---

Under review as a conference paper at ICLR 2023
3 PRELIMINARIES
We denote total variation distance of P1 and P2 by ||P - Pallrv. Given a vector a, define |||| vol T Ba. co. CI. are universal constants. We use a S b mean a S Cb for some universal constant C. Also, [K] {1...., }} and Amin is the smallest eigenvalue of matrix A. Please see Table for a full list of notations and Table for a list of algorithms.
Notations:
Low-rank Markov Decision Processes: We consider mnite-horizon episodic Markov Decision
Process M = (H, A, { Jo.H-- (rx do), specified by the episode length H, state space S, discrete action space A of size A, transition models P : x A + (SS), reward functions rh S [0, 1]. and an initial distribution dg E (SS). Occasionally. we use Ps to denote (P% Jo:H-1 and to denote {rA H Starting from initial state so do. an agent chooses actions 0₁2 step h upon observing the state 8s. receives a reward rh (8h, ag.), and transitions to 8h+1 ~ PV (- (1, ap)- We assume that r and do are known. Given policy : 8 ((A) and transition kernel P. we use the notation E, P [-] to denote expectation under the distribution of trajectories when ' is executed in
P. The value function Prrr (s) = ET, Σ (+(8,, a+) | 8%2 = gives the expected reward-to- go of under the MDP with transitions P. rewards r. starting at state s in step h. Similarly, we define the Q function Q? (s, a) ;= TA (s, a) + (-)saa) V 1 (s'). The expected total reward of a policy under transitions P and rewards is denoted as ppr :- Ex V.rr:o We define the state-action occupancy distribution d' (s, a) as the probability of æ visiting (s, a) at time step h under and P. a (s) is the marginal state visitation, which is equal to EuEA (s,
We study low-rank MDPs defined as follows (Jiang et al., 2017; Agarwal et al., 2020). The conditions on the upper bounds of the norm of o*, n² are just for normalization.
Definition 3.1 (Low-rank MDP) A transition model P% S x A + ASS) admits low rank decomposition with rank d E N if there exist two unknown embedding functions of : S x A + R. 1 : S H Rdd such that Vs, E E, E A: (s ss,)) = p4, (s)) of (s,a). where || (s. a)ll2 S 1 for all (s.a) a) and for any function g S - 10 |J g(s) (p)) S vd. An MDP is a low rank MDP if P7 admits such a low rank decomposition for all h = 0, 0........, 1
Low-rank MDPs capture the latent variable model (Agarwal et al., 2020) where db (s. a) is a distribu- tion over discrete latent state space Z, and the block-MDP model (Du al., 2019) where o" (s, a) is a one-hot encoding vector. Note that the linear MDP model (Yang and Wang, 2020; Jin et al., 2020b) assumes known o², which significantly simplifies the algorithm design.
Transfer Learning: In contrast to the classic single-task learning setting, in this paper, we explore the setting of transfer learning. where learning consists of two phases: (1) the pre-training phase where the agent interacts with K - 1 source tasks with dynamics PE. and (2) the deployment phase where the agent is deployed into the K-th target task and no longer has access to the source tasks. The performance is measured mainly by the regret incurred in the target task upon deployment, while we also desire small sample complexity in the source tasks. We denote dh., := dpp..
In order for the pre-training phase to help with learning in the target task, we must make assumptions on the connections between tasks. In this work, we make the following fundamental structural assumption on all the tasks at hand, namely that they share the same underlying representation ø². Assumption 3.1 (Common representation) We assume that all tasks PŁ are low-rank MDPs with a shared representation of (s. a) but distinct (irn(s)) that is P (s'|s, a) = o (s.a) (
Assumption 3.2 (Realizability) For any source task k E [K 1] and any E [H], we assume that the agent has access to realizable function classes 4;, and Ykc such that o7 E 2n and High E Ya.h- For normalization, assume that for all k, h, all & E 4h satisfy [|ō(s, a)ll S 1, and for all kkc and any function g : S + [0, 1], [IJ ((s)p(((ss)
Vd.
Assumption 3.2 is a standard realizability condition in the function class which is made in almost all prior works on RL with linear and nonlinear function approximation.
Under Assumption 3.1, we expect the agent to learn a good representation during the pre-training phase by interacting with the source tasks, and then leam good policy for the target task using this representation in the deployment phase. In order to realize this intuition though, we need two additional assumptions which we describe next.
3

---

Under review as a conference paper at ICLR 2023
Assumptions for representational transfer. In addition standard assumptions in the source tasks, we make the following structural and relatedness assumptions on the source and target tasks. Assumption 3.3 (Feature reachability in the source tasks) We assume that vb == min max; Amin (EE,,p (5h, an an)oz (5h, a,) 1) is strictly positive.
Assumption 3.3 intuitively requires that no subspace in IR is unreachable in the source tasks, as otherwise it's impossible to guarantee the quality of the learned representation in that subspace which may contain high rewards in the target task. Note that no reachability is required in the target task.
The next assumption quantifies the relatedness of the target task and the source tasks. Assumption 3.4 (Relatedness: Point-wise Linear span) For any h E [H] and s' E Sk+1. there is a vector (s') E IR 1ak- such that ( = Ei=r (x:a(s")Pe) with amax = maNp,a,.'s (s') and ā max; EK=1 max (s))
Assumption 3.4 ensures that if s' is reachable from an (s, a) pair in the target task, then it must be reachable from the same (8, a) pair at least one of the source tasks. This intuitively is also necessary for transfer learning, as s' could be a high rewarding state in the target. A special case is the convex combination, i.c., for any s' E SS ht (s') = Py with pk 2 0, E. Ps- = 1, which implies Omax S and ā = 1. On the other hand, if the target task largely focuses on observations quite rare under the source tasks, then ā can grow large, and this is unavoidable in a transfer learning setting.
We remark that unlike prior work (Du et al., 2020; Tripurameni et al., 2020; Lu et al., 2021), we do not make any assumption on the data generating distribution in either the source or the target tasks. Instead, our approach is end-to-end, i.e., we collect our own data from scratch for representation learning by doing strategic exploration in the source tasks (see Section C for a detailed discussion). In fact, in The- orem D.I we show that the above assumptions do not permit successful transfer in the supervised learn- ing setting, thus establishing an interesting separation between supervised and reinforcement learning.
We conclude this section with couple of examples where our assumptions are satisfied.
Example 3.1 (Mixture of source tasks). Perhaps the simplest example of our assumptions is where PR (s/1s, a) = Ekn ag Px (s'ls, with the coefficients independent of s', ar 2 0 and - 0g = 1. Such mixtures of base models have been considered in several prior works (Modi et al.. 2020; Ayoub et al., 2020). While prior works study the case of arbitrary, but known base models, we instead allow structured, unknown base models with a shared representation. Here ā 1.
Example 3.2 (Block MDPs with shared latent dynamics). In this example, each MDP PT is a Block MDP (Du et al., 2019) with a shared latent space Z and a shared decoder gi* S + Z. In block MDP, given state action pair (s, a). the decoder ai* maps to a latent state the next latent state is sampled from the latent transition 2' ~ P(-|2, a). and the next state is generated from an emission distribution s' ~ o(-1z)). Recall that o(s'l2') > O at only one 2' E Z for any s' E S for block MDP. We assume that the latent transition model P(='lz, a) is shared across all the tasks, but the emission process differs across the MDPs. For instance, in typical navigation example used to motivate Block MDPs, the latent dynamics might correspond to navigating in a shared 2-D map, while emission distributions capture different wall colors or lighting conditions across multiple rooms. Then Assumption 3.3 requires that the agent can visit the entire 2-D map. while Assumption 3.4 requires that the color/lighting conditions of the target task resemble that of at least source task. The coefficients a for any s' are non-zero on the source tasks which can generate that observation.
4 TRANSFER LEARNING WITH GENERATIVE ACCESS TO SOURCE TASKS
We first study a setting where we assume generative model access the source tasks, while having only online access to the target task.
Assumption 4.1 (Generative access to the source tasks) We assume that we have access to generative models for the K source tasks. Specifically, for any Pt with k E [K- - 1). we can query any (sh, an) pair, and the generative model will return next state sample 8h+1 Př,, (Sh, at))
Having generative model access is not unrealistic, especially in applications where a high-quality simulation environment is available. Generative access also does not trivialize the challenge of efficient exploration in the source tasks, since there are a potentially infinite number of states and the ground truth representation o² is unknown. Prior works using generative access typically
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Transfer learning with generative access (REPTRANSFER)
PRE- TRE-TRAIN PHASE
Input: exploratory policies [= size of cross-sampled datasets n, failure probability 6.
D cross sampling procedure 2: For each h E [H- 11, sample dataset D Dijch containing i.idd (s, s') tuples sampled as:
1: for task pairs j. i.e. for all i,j E [K - 1] s.t. i i do
(5, a) 1
()), U(A), s (-
(1)
Vh [H 1], learn 6) =Multi-task REPLEARN ([ ( K- Di ke(kk-))))))) (Algorithm DEPLOYMENT PHASE Additional Input: number deployment episodes
1: Set 8 = Hvd + adH /logddHT/8).
2: Rum LSVI-UCB (f = T,,,T,8 in the target task Pk (Algorithm 6).
require either a known representation o* (so that one can perform D-optimal design to construct an exploratory state-action distribution (Agarwal al., 2019)), or directly assume access diverse state-action distribution which provides coverage and from which one can sample. Neither o* nor such a diverse sampling distribution given our case. We also note that in Section 5 we will show that without any additional assumptions, generative access in source tasks is necessary.
Algorithm overview. Given the above setup, now we present our algorithm REPTRANSFER, detailed in Algorithm/ 1. REPTRANSFER takes representation learning approach to the transfer learning problem and operates two phases. During the pre-training phase, REPTRANSFER performs reward- free exploration in each of the source tasks to learn task-specific policies Th, which satisfies for all = 0, 1,... H 1, that Ex { (5p, )9j (8), an.) > Aminn for some Amin > We call such policies Amin exploratory and will use this definition in Lemma 4.1 and Theorem 4.1. In Section we present one particular algorithm that finds such T&' 's with a specific Amin but our main analysis below is modular to the choice of the reward-fres exploration algorithm.
Given the exploratory policies { (T x --1]-- REPTRANSFER collects a joint dataset across the source tasks using these policies and sooss-s across pairs of tasks (1), and then learns single representation T. In the deployment phase, REPTRANSFER runs optimistic least squares value iteration (Algorithm 6) using the learned representation
the target task!
The cross sampling procedure and learning a shared representation. We now describe the cross sampling procedure detail. Given an exploratory policy म for each source task k. the next step is to sample fresh data under a cross-sampling procedure using the generative model. Consider particular (ks, J) pair of source environments. For each h E [H] we first sample 8h-1, 4h-1 ~ d Then, in the simulator of task j. we reset to (8h,11 11- ) and perform a transition step to 8h, i.e. 8h ~ Pa (s)-1. on-1). Then we reset the simulator for task & to state Sh, sample a uniformly random action an and then perform another transition to Sh+1, i.c., Sh+1 ~ PH ax). Such a procedure only possible under the generative model setting. Intuitively, cross-sampling ensures that our training data contains all possible states that can be encountered in the target task, and failure modes without this can found the discussion following Theorem 5.
Given datasets, each of size collected using the cross-sampling procedure, we perform Maximum Likelihood Estimation (MLE)-based representation learning procedure (Algorithm 3) jointly on all
source tasks, with the goal of finding a representation function On that can predict the transition probability well across all source tasks. An existing MLE generalization analysis (Agarwal et al., 2020) guarantee that Multi-task REPLEARN (Algorithm 3) achieves the following total variation guarantee with probability at least 1 8:
K-
Eppa (2,(), a) (ima())) (s, a) Men S SNN = O (log(( TV
(2)
'Given any dataset, (s, a,r,s's feature o and reward LSVI learns Q function backward, i.e., at step via
whg = arg min E.a. I (w ((s.a) - Vi (s))) + w|l and set (s) = max, (r(s, a) + ū d(s, a)), Vs. UCB, short for Upper Confidence Bound, refers to an exploration bonus added basic I.S.I.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 REWARDFREE
1: Input: MDP Pa with online access, num. LSVI-UCB episodes NLsVI-Ucs, num. model-learinng episodes NREWARDFRER, failure probability 6.
2: Learn model (Pn- = (0h. ) H-1 by running REWARDFREE REP-UCB (Algorithm 4) in P* for NREWARDFREE episodes.
3: Set B = dH NL.w.tte//)))
4: Return م LSVI-UCB ((n))
0, Ni.svv 3, UNIFORMACTION TRUE) by sim-
ulating in the learned model P (Algorithm 6). Note this step requires no samples from P
where Mkc denotes the generating distribution of inputted datasets Da:h, each with size N. For example, in REPNRANFFE we have Dach- K- j=1 Daj.A. and N = n(KK 1).
Representational transfer. Next we transfer this guarantee to the target task via Assumption 3.4, a key insight of our work. Specifically, we show that under cross sampling and Assumption 3.4, @ also linearly approximates the true transition in the target task well, under the occupancy measure of any policy. Remarkably, this holds before the agent has ever interacted with the target task.
Lemma 4.1 Suppose Assumption 3.4 and that for all source tasks k E [K" - 1] we have Aminn exploratory policy mg- Then, for any 8 E (0, 1), learning features & using the cross-sampling
procedure of Algorithm I satisfies (2) w.p. 1 - 6. Furthermore, for any h = 0, 1,..,.., H 1, there exists uh S + Ie such that for any function g S -0, [ (()())()(((s)))
S avd and
sup Ex Pk [ an) T
(s,,,, a pisn()) S VlAla K Gn/Amin
Lemma 4.1 implies that @ is a feature such that Pk is an approximatly linear MDP in T. Learning in approximately linear MDPs has been studied in Jin et al. (2020b), but under much stronger foo. error bound rather than the average misspecification here. Our result for downstream task learning under such an average model misspecification case presents the strongest result for learning in an approximately linear MDP, and the result might be of independent interest.
Regret bound for REPTRANSFER. Putting things together, we obtain the following regret bound for online learning in the target task using our learned representation Ø.
Theorem 4.1 (Regret under generative source access) Suppose Assumptions 3.1.3.4 and 4.1, and sup- pose the input policies T are Amin explooratrr. Then, for any 8 E (0, 1), w.p. 1 1- 5, REPTRANSFER
when deployed in the target task has regret at most Ö (all2 (L12"dL./Tloog /T (1/5) with at most Kn
generative accesses per source task, with n. O (> Ao KT (log 10 + K log mi))
Remarkably, Theorem 4.1 on the target task to the setting of linear MDP with known 6² (Jin et al., 2020b), up to the additional factor. The scaling factor ā only depends on a itself and captures the hardness of transfer learning. For special cases such as convex combination, i.e., is state-independent and aa E A(K), then = 1. In the worst-case, some dependence on the scale a seems unavoidable as we can have state s' such that (s') observed state for the source task encountered often in the target, and our estimates of transitions involving this state can be highly unreliable if it is not seen in any other source, roughly scaling the error between target and source tasks as |o (s')]. Obtaining formal lower bounds that capture a matching dependence on structural properties of an interesting question for future research.
shows that with the pre-trained features, we achieve the same regret bound
and (1('s) < 1 with an (s') > 1. This corresponds to rarely
Reward-free exploration in the source environments. So far we have assumed that we have a reward-free exploration black box algorithm that can provide an exploratory policy Ty. for each source task A: In this section, we give detailed algorithm that achieves this goal.
Recall that our transfer learning algorithm, for source task Pt: relies on an exploratory policy n. such that the empirical covariance with respect to dj is lower bounded. This ensures good exploration in the underlying ground truth feature space in P Algorithm 2 achieves this goal by first invoking the REWARDFREE REP- UCB algorithm (Algorithm 4) to leamn estimated linear MDP model Pr for Pg. The REWARDFREE REP- UCB algorithm is reward-free generalization of the recent

---

Under review as a conference paper at ICLR 2023
REP-UCB algorithm (Uehara et al., 2021) that perform reward- free exploration in low-rank MDPs and can be of independent interest. Subsequently, we perform reward- free exploration (e.g., using LSVI-UCB with zero reward) within each Psc which involves no further environment interactions.
Lemma 4.2 (Reward-free Exploration) Fix any source lask & E [K - 1]. Suppose Assump- tions 3.2 and 3.3. Then, for any ő E (0,1), w.p.
6, REWARDFREE (Algorithm 2) with
NLSVI-UCH ê (A9
and NREWARDFREE - (A3d log ( Ni returns 1A-3d-3
a Xmin explorrapyyy policy TI where Amin = Ω (A S 25?) The sample complexity here is NREWARDFREE episodes in the source task.
To the best of our knowledge, Lemma 4.2 is the first result that finds full-rank policy cover in the low-rank MDP setting, and might be of independent interest. Wagenmaker et al. (2022) recently obtained related guarantee in the linear MDP setting with known features 6², Incorporating Lemma 4.2 and Theorem 4.1, we get our final sample complexity bound.
Theorem 4.2 (Regret for REPTRANSFER with REWARDFREE subroutine) Suppose Assump- tions 3.1-3.4 and 4.1 hold, and let 8 E (0, Let { K-1 be exploratory policies learned from running REWARDFREE on each source task with NISVI-UCR and NREwaRdFREE set as in Lemma 4.2. Then, w.p. 1 Ó, running REPTRANSFER with (TR)E= has regret in the target task of Ō (ali'd'. (1)))) with at most Ô (A d 1 KTT (log()41/0) + K log (T]) generative accesses per source task.
5 TRANSFER LEARNING WITH ONLINE ACCESS TO SOURCE TASKS
In the previous section, we show that efficient transfer learning is possible under very weak structural assumptions, with generative access to the source tasks. One natural question is whether transfer learning is possible with only online access to the source tasks. Somewhat surprisingly, we show that this is impossible without significantly stronger assumption.
Theorem 5.1 (Impossibility Result) Let MR be K-task multi-set that satisfies (1) all tasks are Block MDPs; (2) all tasks satisfy Assumption 3.3 and Assumption 3.4; (3) the latent dynamics are exactly the same for all source and target tasks. For any pre-training algorithm A which outputs feature à by interacting with the source tasks i E [K - -1], there exists {Pk ]eE[K] E MM, such that with probability at least 1/2,, A will output feature o, such that for any policy taking the functional form of (s))= = f (10(s, a)AA (r(s, d)]oEA), we have V VR 2 1/2.
The above theorem implies that a representation learned only from online access to source tasks does not enable learning in downstream tasks if the downstream task algorithm is restricted to use the representation as the only information of the state-action pairs (e.g., running LSVI-UCB with Φ).
We briefly explain the intuition behind the above lower bound. For a Block MDP, for any (s, a). we can model the ground-truth ø' as a one-hot encoding ((..)) corresponding to the latent state-action pair (z, a) with = = (s))s being the encoded latent state. The key observation here is that any permutation of 6" will also be a perfect feature in terms of characterizing the Block MDPs, since corresponds to simply permuting the indices of the latent states. Therefore, without cross referencing. the agent could potentially learn different permutations in different source tasks, which would collapse in the target task. A precise constructive proof of Theorem 5.1 can be found in Section D.
Part of the reason that the above example fails is that each source task has its own observed subset of raw states, which permits such permutation to happen. In what follows, we show that, indeed, under an additional assumption on the reachability of raw states, a slight variant of the same algorithm (Algorithm 5 in Section G) can achieve the same regret with only online access to the source tasks. Assumption 5.1 (Reachability in the raw states) For all source tasks is E [K- 1). any policy a and h 0, 1, ..... H- 1, we have inf,es, d (s,a) 2 Praandmi (Er.pg [ (sh, ax (x))%% (sh; an)) TI).
Assumption 5.1 implies that for each source task, any policy that achieves a full-rank covariance matrix also achieves global coverage across the raw state-action space. In addition, in order to apply importance sampling (IS) to transfer the TV error from source task to target task, we need to assume that the target task distribution has bounded density. This is true, for example, when S is discrete.
7

---

Under review as a conference paper at ICLR 2023
Source
O-RESTRANSPER
G-REETRANSPER
Target
Comblock
8006
7790
7048
181450
(294.7)
(267.6)
(1648)
(147600.2)
Comblock
7764
7336
85000
PO
(145.7)
(270.7)
(14469.8)
1-0
8/2
bei
(b)
(a)
Figure I: (a): A visualization of the rich observation comblock environment. Latent states (white and black) emit continuous high-ddimeniionl observations. The reward sparse (only in white states at H). Each white state has 10 actions where one of them is a good action that leads to the next two white states while the other lead to black states (good action for each white state is different). Once the agent is in black states, it stays stuck in black until the end of the episode. Thus, random exploration strategy has an exponentially small probability of hitting the goal (i.c., roughly (1/10)"). "I ). (b) Top: Number of episodes required to solve the target environment under the setting from Sec. 6. (b) Bot- tom: Number of episodes required to solve the target environment under the setting from Sec. 6. An algorithm solves the target task if it can achieve the optimal return (i.e., 1) for consecutive iterations with 50 evaluation runs each. We include the mean and standard deviation (in the brackets) for random seeds. oc denotes that an algorithm can not solve the target task within a fixed sample budget.
Assumption 5.2 (Bounded density) For all (x, h, s,)), we have dk (8, a) S 1.
Theorem 5.2 (Regret with online access) Suppose Assumptions 3.1-3.4,5.1,522 hold. W.p. 1 8, Algo- rithu 5 with appropriate parameters achieves regret in the target Ô (ad /
with at most poly (A, Omaxx d, H, K, T, 1 Vroww log( ( online queries in the source tasks.
Assumption 5.1 is satisfied in a Block MDP, when, for example, the emission function o(s|2) satisfies that Va, 3z, s.t., o[s]2) 2 c. That is, for any source task, any state in the state space can be generated by at least one latent state.
EXPERIMENTS
We investigate empirically the benefit of transfer learning under the Block MDP setting, on the challenging Rich Observation Combination Lock (comblock) benchmark. In this environment, one must recover the correct feature from rich observations and perform strategic exploration or otherwise pay for exponential sample complexity. We include visual overview in Fig. 1(a). This enviromment is uniquely challenging since it requires strategic exploration and latent state discovery at the same time, which results in failures of common deep RL methods (Misra et al., 2020), and theoretical RI. approaches based on linear function approximation (and kernels) (Zhang et al., 2022).
In particular, in this section study the following questions: i) what are the benefits of representa- tional transfer using multiple source tasks, and ii) whether generative access to source tasks is needed. We design two sets of experiments with various source and target environment configurations. We defer the details of the experiments (the design of vanilla comblock, hyperparameters, etc.) in Appendix and include the essential design information in the following two sections.
Baselines. We denote Source as the smallest sample complexity of LSVI-UCB using learned features as REPTRANSFER with only online access to
from any of the source tasks; the source tasks; G-REPTRANSFER as REPTRANSFER with generative access to the source tasks; Oracle as learning in the target task with ground truth features; and Target as running BRIEE (Zhang et al., 2022) the SOTA Block MDP algorithm, in the target task with no pretraining.
Comblock without partitioned observations In this section we start off with an easier setting: we use source tasks, each with horizon H/ = 25, 3 latent states per level and 10 actions. The latent transition dynamics are different for each source task, but notice that for comblock, the reachability assumption (c.r. Assumption 3.3) is always satisfied. The emission distribution of all the source and target tasks is identical, Assumption 5.1 holds here. For the construction of the target task, for each timestep h, we choose the latent transition dynamics from one of the sources uniformly at random (thus Assumption 3.4 is satisfied). We record the number of episodes in the
8

---

Under review as a conference paper at ICLR 2023
sThdo
MA
4.00
1008
CON
10007
1944
(a)
(b)
Figure 2: (a): Visualization of the decoder source (top) and G-REPTRANSFER (bottom). (b): Visualization of the decoder TRANSERN (top) and E-REETRANNSEER (bottom). For each baseline, The h-th column in the i-th image denotes the averaged decoded states from the 30 observations generated by latent state 2i,h, for E {0, 1, 2 and h E [25]. from the corresponding target environment. The optimal decoder should recover the latent states up to a permutation. In Fig a (top), note that the learned features in source task fail to solve the target because of the collapse at timestep 5: both observations from state 0 and are mapped to state O. Note in the source task where this feature is trained, such collapse can happen when state 0 and 1 have identical latent transition (for detailed discussion we refer to Misra et al. (2020)). In Fig (top), TRANSFER with only online access learns an incorrect decoder when the source tasks' observation spaces are disjoint. This is because the learned feature can decode each source task with a different permutation.
target environment that each method takes to solve the target environment in Table. 1(b). We first observe that Assumption 5.1 holds). Second, source task does not suffice to solve the target environment. This is because the representation learned from a single source task may collapse two latent states into single one during encoding (e.g.. if two latent states at the same time step have exactly identical latent transitions). See the visualization of comparisons between the learned decoders from a single source task and REPTRANSFER in Fig. 2(a). Third, the result shows that REPTRANFEE saves order of magnitude of target samples compared with training in the target environment from scratch using the SOTA Block MDPs algorithm BRIEE This set of results verifies the empirical benefits of representation learning from multiple tasks, i.e., resolves ambiguity and speeds up downstream task learning.
RANSFER with either online or generative access can solve the target task (since.
observe that directly applying the learned feature from any single
Comblock with partitioned observation space (Comblock-PO) In this section, following the intuition of our lower bound (Theorem 5.1), we construct a setting where the supports of the emission distributions from each task are completely disjoint, while the emission distribution in the target task is mixture of all source emissions and the latent dynamics are identical across tasks. Hence Assumption 3.4 holds while Assumption 5.1 fails. So we expect that an algorithm without generative access to source tasks will fail based Theorem 5.1. Specifically, under disjoint emission supports, a representation can decode the latent state correctly for each source, but permute latent state labels across sources, causing decoding errors the target. We record the number of target episodes for each method to solve the target task in Table. (bb). We observe that indeed the online version fails while the generative version still succeeds. We show the visualizations of O-REPTRANSPED and G-REPTRANSFER in Fig. 2(b), and we note that the empirical results exactly match our theoretical results. This ablation verifies that source generative model access is needed.
7 CONCLUSION
We study representational transfer among low rank MDPs which share the same unknown representa- tion. Under a reasonably flexible linear span task relatedness assumption, we propose an algorithm that provably transfers the representation learned from source tasks to the target task. The regret in target task matches the bound obtained with oracle access to the true representation, using only polynomial number of samples from source tasks. Our approach relies on the generative model access in source tasks, which we prove is not avoidable in the worst case under the linear span assumption. To complement the lower bound, we propose stronger assumption on the conditions of the reachability in raw states, under which online access to source tasks suffices for provably efficient representation transfer. Finding modalities other than generative access which avoid the lower bound, and a more extensive empirical evaluation beyond the proof-of-conee experiments here are important directions for future research
9

---

Under review as a conference paper at ICLR 2023
Reproducibility Statement: For theory. we include detailed and complete proofs for all of our claims in the appendices. For empirics, we include anonymized code in the supplement. Please refer to Appendix. for a comprehensive experimental setup and list of hyperparameters. All experiments were run on CPUs and no external datasets were used.
REFERENCES
Alckh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems, volume 33, pages 20095-20107, 2020.
Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In International Conference on Machine Learning, pages 367-376. PMLR, 2020.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474 PMLR, 2020.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pages 41 41-48, 2009.
Léonard Blier, Corentin Tallec, and Yann Ollivier. Learning successor states and goal-dependent values: A mathematical viewpoint. arXiv preprint arXiv:2101.07123, 2021.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning, arXiv preprint arXiv: 1309: 0821,682122222 2013.
Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning. In International conference on machine learning, pages 316-324. PMLR, 2014.
Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
Yuan Cheng, Songtao Feng, Jing Yang, Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning. arXiv preprint arXiv:2206.055: 05900, 2022.
Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano, and Manish Purohit. Dynamic balancing for model selection in bandits and rl. In International Conference on Machine Learning, pages 2276-2285. PMLR, 2021.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural computation, 5(4):613-624, 1993.
Carlo D' D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowledge in multi-task deep reinforcement learning. In International Conference on Learning Representa- tions, 2019.
Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.094344 2020.
Amir-massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Machine learning, 85(3):299-335 2011.
10

---

Under review as a conference paper at ICLR 2023
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning, pages 1126-1135. PMLR, 2017.
Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pages 4063-4073. PMLR, 2021a.
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 316-324.
PMLR, 2021b.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pages 4349-4358. PMLR, 2021.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In International Conference on Machine Learning, pages 179-188. PMLR, 2015.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 1704-1714 PMLR, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879. PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020b.
Alessandro Lazaric, Emma Brunskill, et al. Sequential transfer in multi-armed bandit with finite set of models. Advances in Neural Information Processing Systems, 26, 2013.
Erwan Lecarpentier, David Abel, Kavosh Asadi, Yuu Jinnai, Emmanuel Rachelson, and Michael L. Littman. Lipschitz lifelong reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8270-8278 2021.
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In International Confer- on Artificial Intelligence and Statistics, pages 3340-3348. PMLR, 2021.
Rui Lu, Gao Huang, and Simon S Du. On the power of multitask representation learning in linear 2021.
mdp. arXiv preprint
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption robust exploration in episodic reinforcement learning. Conference on Learning Theory, pages 3242-3245. PMLR, 2021.
Andreas Maurer, Massimiliano Pontil, and Bernardino Comera-Parededs The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pages 6961-6971. PMLR, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Aditya Modi. Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-frec representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.0703: 2021.
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:20/2. 33045, 2020.
11

---

Under review as a conference paper at ICLR 2023
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions on knowledge and data engineering, 22(10): (1110):134-135555 1359, 2009.
German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019.
Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimie: Deep multitask and transfer reinforcement learning. arXiv preprint arXiv:/51 2015.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. arXiv preprint arXiv:2111.111855 2021.
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprini arXiv: 04671, 2016.
Ahmed Touati and Yann Ollivier. Learning one representation to optimize all rewards. Advances in Neural Information Processing Systems, 34:13-23, 2021.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 33:7852-7866 2020.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. In International Conference on Learning Representations, 2021.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward- free rl is no harder than reward-aware in linear markov decision processes. arXiv preprint 1rXiv:2201./1206, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward- twarrd-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816-17888 2020.
Jiaqi Yang. Wei Hu, Jason D Lee, and Simon Shaolei Du. Impact of representation learning in linear bandits. In International Conference on Learning Representations, 2020.
Jiaqi Yang, Qi Lei, Jason D Lee, and Simon S Du. Nearly minimax algorithms for linear bandits with shared representation. urXiv preprint arXiv:2203. 15664, 2022.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Proceedings of the 37th International Conference Machine Learning, pages 10746-10756, 2020.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. COLT, 2021.
Weitong Zhang, Jiafan He, Dongruo Zhou, Amy Zhang, and Quanquan Gu. Provably efficient representation learning in low-rank markov decision processes. arXiv preprint arXiv: 1935, 2021.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:11734: 1743, 2020.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang. Wen Sun, and Alekh Agarwal, Efficient reinforcement learning in block mdps: A model-free representation learning approach. arXiv preprint X11:22222.00063 2022.
Zhuangdi Zhu, Kaixiang Lin, and Jiayu Zhou. Transfer learning deep reinforcement learning: survey, arXiv preprint 20X0:20009007888, 2020.
12

---

Under review as a conference paper at ICLR 2023
Appendices
A NOTATIONS
Table 1: List of Notations
S,A, A
State and action spaces, and A |A|. The of distributions supported by S. Smallest eigenvalue matrix A.
(S)
Amin (A)
ej
One-hot encoding of j, i.e. 0 at each index except the one corresponding to j.
Length of vector implied from context.
(v)
min y)-
H
Episode length of MDPs, a.k.a. time horizon. We index steps as = 0, 1, - 1. There are total of K tasks. The first = = I.... K are source tasks, and the K K-th task is the target task.
K
dimension of the low-rank MDP, i.e. dimension of 6*
Pki
Ground truth transition at time for task k.
Th
Reward function of the target task (i.e. task K). Expectation under the distribution of trajectories when is executed in P. We sometimes omit when the MDP clear from context.
Ex
d'ss
Occupancy distribution of æ under transitions at time
Occupancy distribution for the k-th task, i.. d'p.
of (s,a)
Embedding function for (s, a) at time h.
Realizable function class for oA.
@b
Defined as max (Px]-
(s))
Emission embedding function for s' at time for environment k.
Tks
Realizable function class for Migh.
[m]
Defined as maxi;; [a,hh
Feature reachability in the source task (Assumption 3.3).
Omax ā
Constants defined in point-wise linear span assumption (Assumption 3.4).
Drew
Raw states reachability parameter (Assumption 5.1)
Table 2: List of Algorithms
REPTRANSFER (Algorithm 1)
Transfer learning with generative access.
REWARDFREE (Algorithm 2)
Reward Free exploration in low-rank MDP.
Multi-task REPLEARN (Algorithm 3)
Multi-task Maximum Likelihood (MLE) Representation Learning.
REWARDFREE REP-UCB (Algorithm 4)
Modified REP-UCB for reward- -fee model learning.
REPTRANSFER for online access (Algorithm 5)
Simplified version of REPTRANSFER if we have
reachability under raw states (see Theorem 5.2).
LSVI-UCB (Algorithm 6)
Optimistmic Least Squares Value Iteration (with bonus).
13

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL RELATED WORKS
The idea of learning transferable representation has been extensively explored in the empirical literature. Here we don't It intend to provide comprehensive survey of all existing works on this topic. Instead, we discuss a few representative approach that may be of interest.
Towards transfer learning across different environments, progressive neural network (Rusu et al., 2016) is among the first seural-based attempt to learning a transferable representation for a sequence of downstream tasks that tries to overcome the challenge of catastrophic forgetting. It maintains the learned neural models for all previous tasks and introduce additional connections between the network of the current tasks to those of prior tasks to allow information reuse. However, drawback common to such an approach is that the network size grows linearly with the number of tasks. Other approaches include directly learning multi-task policy that can perform well set of source tasks, with the hope that it will generalize to future tasks (Parisotto et al.. 2015). Such an approach requires the tasks to be similar in their optimal policy, which is a much stronger assumption than ours.
Slightly off-topic are the works about "transfer learning" inside the same environment but across different reward functions, which is more restricted than the setting considered in this paper. Several prior works design representation learning algorithms that aim to learn a representation that generalize across multiple reward function/goals (Dayan, 1993; Barreto al., 2017; Touati and Ollivier, 2021; Blier et al., 2021). These are related to the REWARDFREE REP- UCB we developped in Section E. The key difference is that we concern representation learning along with efficient exploration to derive an end-to and-to-end polynomial sample complexity bound. These prior works do not consider exploration and do not come with provable sample complexity bounds. We refer interested readers to a recent survey (Zhu et al., 2020) for comprehensive discussion of other empirical approaches.
C COMPARISONS TO CLOSELY RELATED WORKS
Recall that addition to the commonly made shared representation assumption (Assumption 3.1), we made two additional structural assumptions: reachability (Assumption 3.3) and linear span on 4 (Asssupption 3.4). The reachability assumption is commonly made in prior works even in single agent RL, e.g. (Modi et al., 2021; Misra et al., 2020). It ensures that there is redundant dimensions in the ground-truth representation, which is a reasonable requirement. The linear span assumption is closely related the diversity assumptions made in prior works of transfer learning in both supervised learning (Tripuraneni et al., 2020) and reinforcement learning (Lu et al., 2021).
Lu et al. (2021): In the prior work of Lu et al. (2021), which also studies transfer learning in low- rank MDPs with nonlinear function approximations, they need to make the following assumptions:
1. shared representation (identical to our Assumption 3.1).
2. task diversity (similar to our Assumption 3.4).
generative model access to both the source and the target tasks. In contrast, we only require generative model access to the source tasks and allow online learning in the target task.
a somewhat strong coverage assumption saying that the data covariance matrix (under the genera- tive data distribution) between arbitrary pairs of features Φ, ø' E & must be full rank. In contrast, our analysis only requires coverage in the true feature o* in the source tasks.
5. the existence of an ideal distribution q on which the learned representation can extrapolate. We do not require an assumption of a similar nature. Instead, we show that the data collected from our strategic reward-free exploration phase suffices for successful transfer.
the uniqueness for each @ in the sense of transform equivalence. Two representation functions ó and o' can yield similar estimation result if and only if they differ by just an invertible linear transformation. In contrast, we do not make any additional structural assumptions on the function class & beyond realizability.
14

---

Under review as a conference paper at ICLR 2023
In summary, work present a theoretical framework that permits successful representation transfer based on significantly weaker assumptions. We believe that this is solid step towards understanding transfer learning in RL.
Cheng et al. (2022): A concurrent work of Cheng et al. (2022) also studies the exact same problem ours. Both works study the setting where the agent performs reward-free exploration in the source tasks for representation learning and used the learned representation for the target task. Both works achieves similar sample complexity in source and target tasks, albeit using very different algorithms. However, in addition to the assumptions that we made Cheng et al. (2022) has to make an additional assumption.
Assumption C.1. For any two different models in the model class x V, say (* a) = (s')) (. and (= all (s E S A and h E [H].
(0*(s, a),
there exists constant CR such that for
S SCE.L.....u.
This assumption ensures that the point-wise TV error is bounded, as long as the population-leved TV error is bounded. This assumption is used transfer the MLE error from the source tasks to the target task. This type of assumption is strong in the sense that we typically expect CR to scale with |S]. In contrast, our analysis (Lemma G.I) shows that this assumption is in fact not necessary assuming online access only to source tasks. The generative access to source task studied here, which enables transfer under weaker reachability assumptions not studied in their work.
It is worth noting that Cheng et al. (2022) also study offline RL in the target task which we not cover, while we mainly focus on the setting of generative models in the source tasks and demonstrating a more complete picture by proving generative model access in source tasks is needed without additional assumptions. Comparing (Cheng et al., 2022), we also further implement and perform experimental evaluations of our algorithm.
D IMPOSSIBILITY RESULTS
Here, present interesting result showing that the above assumptions make weak that they do not even permit efficient transfer in supervised learning:
Theorem D.1 (Counter-example in supervised learning) Assume that we want to perform conditional density estimation, where P (y)z) 6² (xx)))
T P (y). Under Assumption 3.1 (shared representation) and Assumption 3.4 (linear span), and assume that in each source task, one have access to data generating distribution pı(x) such that Amin (6) (x)Ø** (x)"] 2 v (reachability). No algorithm
can consistently achieve Ep Pl (u]xx) P [[]] < 1/2 on the target task using the feature learned from the source tasks with probability more than 1/2.
Proof of Theorem D.I. Consider the following example. X = IR_ and have the following sets.
S 111/2((-1,,1))))
S₂ (1/22(-22,-2))
S₃ / ((0,
where Ba( (xx y)) stands for the ball with radius a centered at (a, y). These will be the support of tasks: task 1 and 2 are two source tasks, task 3 is the target task. Let's assume that Pt (x) uniform distribution on St.
Suppose that the feature class only contains two functions:
Φ {x1 < 0 & 2 2 + (1, 0), and (0, otherwise
Φ 22 < &
x1 2 22) (0, 1). and (1, 0) otherwise
with the minor difference that they directly assume the space is compact with bounded measure
15

---

Under review as a conference paper at ICLR 2023
That is, the feature maps from I² to the set of binary encoding of dimension 2, i... ((1,0) (0. 1)). We further assume that μr = (P1 (p)())Pp(y) for some distributions P1.P2: P2, which is identical for all task k where [| P2 lrV 1. We also assume that fi is known to the learner prior, i..
YE = {ut} for all k E [K], so all the learner needs to do is to pick the correct & out of two candidates.
Given the above setup, it's easy to verify that both Assumption 3.1 and Assumption 3.4 are satisfied, because the decision boundary of both Φ1 and Ø2 passes through the support of the source tasks, and all 2 s are identical. However, Φ1 and Φ2 are equivalent in S1 and S₂ in terms of their representation power, therefore no algorithm can always pick the correct feature function with probability more than 1/2, regardless of the number of samples. Suppose Φ1 the true feature and the algorithm incorrectly chooses Φ2 Then, for x E S ((11 2 0} which has probability mass 1/2, Pa(ular) = P2 whereas P3 (y/x) P1. Thus, the expected total variation distance between Px and Pk is 1/2.
The above construction shows that assumption not sufficient to permit reliable representation transfer, even in the supervised learning setting. Yet, surprisingly, these assumptions are sufficient in the RL setting, implying somehow that transfer learning in RL in easier than transfer learning in SL. To understand this phenomenon, observe that in RL, the marginal distribution on (s, a) is not independent from the conditional density P(s'|s, a) we desire estimate. In particular, if one collects data in the source tasks in an online fashion via rumning a policy, p(s,, a) is structurally restricted be an occupancy distribution generated by the ground-trute transition P (s''ss ls/ss, a). Such a connection can only exist in Markov chains, and our analysis elegantly utilizes this additional structure to establish the soundness of the learned representation. Also note, crucially, that we never learn a representation to capture do. which would suffer from similar issues as the supervised learning setting, but is not necessary for sample-efficient RL.
Next, we prove the impossibility result in Theorem 5.1, restated below as Theorem D.3. This result shows that one not achieve online learning in the source tasks without significantly stronger assumptions such as Assumption 5.1. Before that, we provide a preliminary version, showing that the learned ø is not sufficient to fit the transition model in the target task, which motivates the construction in Theorem D.3.
Theorem D.2 (Impossibility Result: Model Learning) Let MM be the set of K-task multi-set that satisfies
1. all tasks are Block MDPs;
all tasks satisfy Assumption 3.3 and Assumption 3.4;
3. the latent dynamics are exuctly the same for all source and target tasks.
For any pre-training algorithm A, there exists (P7 E MM and an occupancy distribution PK on the target task, such that with probability at least 1/2, A will output a feature & and for any μs
Epx 16,s, a) ((()) (7((1s,a)llzz 2 1/2.
Proof of Theorem D.2. Consider tabular MDP with 2 latent states 21, 22 and an observation state R2 and in task 2 one can only observe B1 U B2. Correspondingly, o1 (s|2) is only supported on Rj U (i.c., or (R.[2,) = 1) and similar for task 2. Let the latent state transition be such that P(z [22]221,00 a) and P( (222/22,0) a) 1, ie. only self eef-trransiion regardless of the actions.
space S- R₁ U Re U B, U2, where in task 1 one can only observe R2 UR2
Now, consider 2-element feature class V = {1i1, } such that
1 {Ri + I, R2 + 2, B3 + B3 + 2} 4/2 [R1 + R. + 2, + 2, + 1} Denote (z(s, a) = (()(s)))) for i E [1, Consider for each task A: a 2-element Tç class in the form of Tr= ((ox())21) (5)22))) on (s|=1)))-
16

---

Under review as a conference paper at ICLR 2023
Notice that Φ1 and Φ2 merely permutations of one another and given any single task data, the two hypothesis will not be distinguishable by any means. Therefore, for any algorithm, there is at least probability 1/2 that it will choose the wrong hypothesis if the ground truth o* is sampled between Φ1 and Φ uniformly at random. Suppose Φ1 is the correct hypothesis and Φ2 is the one that the algorithm picks (i.e., Ø = Φ2). Let task 3 be such that any state emits to Ri U R2 and B1 B2, each with probability 1/2 (i.e., 0z R2 (4) og( 2z) 0.5). This construction satisfies Assumption 3.3 and Assumption 3.4.
Then, within task 3, one would encounter observations from both R1 and B2 which should be mapped to latent state 21 and 22 respectively by the true decoder $1, but are instead both mapped to latent state 21 by the learned decoder Φ2, and thus 21 and 22 become indistinguishable. Suppose Pk (21) = (x2) = 1/2, then
Epx [|l((, a) m(-) (* a)lrv)
- ( -(+))))))))))))))) - ((R)) 1e
AlTv (f ((((B1) (o((Bi)T(())))))))))) - (BB)) 10
()()))((()))()))))()))) u(()) o(B2)* ('llzv ||01 oillrv/ 4 + 00 oillrv /4+ + l|02 o5llTv/44 |oi oillTv/4
+ (1)()))) T u(+) o(22)* 4² (+)lvv + {10(B²)
1 Joi - oillrv + 4 |l01 0bllrv
2
4
where the last second inequality uses triangle inequality, and the last equality comes from the fact that (-1=a) and 0a(- (a(2 have disjoint support which implies that ||p] -Pillrv 1.
Now, we are ready to restate and prove Theorem 5.1. Theorem D.3 (Impossibilityy Result: Optimal Policy Identification) Let Mr be the set of K-task multi-sel that satisfies
1. all tasks are Block MDPs;
2. all tasks satisfy Assumption 3.3 and Assumption 3.4:
3. the latent dynamics are exactly the same for all source and target tasks.
For any pre-training algorithm A, there exists {P E .Mx, such that with probability at least 1/2, A will output a feature G, such that for any policy taking the functional form of T f (o(s,a))aeA) (r(s, ()EAA) we have
V V 2 1/2.
Proof of Theorem D.3. Consider tabular MDP with H two latent states 21, 22 for h 1 and two latent states 23, 24 for h = 2.
For h 1, let there be two actions d1, d2. Let the observation state space be S R1 U Bi B2, where in task 1 one can only observe R1 U R2 and in task 2 one can only observe B, UB2 Correspondingly, of (s|2) is only supported on R U (i.e., (Rg = 1) and similar for task 2. Let the latent state transition be such that P(zs|=1,()) (1) ) P(zalz2,
and P(zl a2) P(z4 a2) All rewards are
for h =
For h = 2. in state 23. all actions have reward 1, and in state 24 all actions have reward
The initial state distribution is do(21) do(22) 1/2.
17

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Multi-task REPLEARN
1: Input: Datasets {Dx} model class Φ, Tr, k = l...,KK K - 1.
K-1
2: Compute MLE (ò, (1:-11)1) ;= argmax PEO. k=1
ED. (
3: Return
Now, consider 2-element feature class V = (1h,, 1/2) for h 1, such that
1 {R] 1, R. + 2, B3 11, B2 2}
2/2 { + 1, R2 + 2, + 2, + +
Denote (s(s,)) = a()) for i E [1, In addition, define Y = ={ H2] where
M1 {23 + (1.0), (0. 1)}
A2 [24 (1,0),
(0,
Notice that Φ1 and d2 are merely permutations of one another and so given any single task data, the two hypothesis will not be distinguishable by any means. Therefore, for any algorithm, there is at least probability 1/2 that it will choose the wrong hypothesis. Suppose Φ1 is the correct hypothesis and d2 the one that the algorithm picks (i.e., ò- = Φ2). Let task 3 be such that any state emits to Ri R2 and B1 U B, each with probability 1/2 (i.e., 0g [ 24) = og (B, = 0.5). This construction satisfies Assumption 3.3 and Assumption 3.4.
Then, for any policy that only make decision based on 0(s, a) and r(s, a), would output the same action for observations in R₁ and B2, or for B₁ and Rg. However, notice that the optimal policy, which would try to go to 2y from either 21 or 2g. will pick a at R2 and B1 while picking dg at R and Bz, which means that the optimal policy will not agree on R₃ and B2, and it also will not agree on R₂ and B1. Thus clearly, no such policy as defined above is capable of capturing the optimal policy. From the reward perspective, notice that d= (z)) d (22) = 1/2 and d= (Rn) = d" (R2)) = dd (B,( d= (²(B) (B)) 1/4. Since π (R1) x (B2). the agent will only be able collect reward at one of the R1 and B2 (but not at both). Similarly, since x (R2) = π (B1). the agent will only be able to collect reward one of the R2 and B1 by reaching 23 (but not both). This means that i will have average reward 1/2. Since the optimal policy will be able to collect reward at all R1, R2, B1, B2, it will have average reward This concludes the proof.
Theorem D.2 and Theorem D.3 show that it's impossible to allow online learning in the source tasks without much stronger assumptions. In our paper, we show that our Assumption 5.1, which ensures reachability in the raw states, is sufficient to establish an end-to-ending online transfer learning result. However, is unclear if Assumption 5.1 is necessary for online learning. We leave this as an important direction of future work.
E REWARD-FREE REP-UCB
In this section, we adapt the Rep-UCB algorithm (Uchara et al., 2021) for reward-free exploration in single task. We drop all task subscripts as this section is for a single task only, i.e. think about the task as being each source task. The original Rep-UCB algorithm was for infinite-horizon discounted MDPs, so we modify it work for our undiscounted and smite-horizon setting. Our goal is to prove that Rep-UCB can learn a model that satisfies strong TV guarantees, i.c. Theorem E. and (5). Note that FLAMMBE (Agarwal et al., 2020, Theorem 2) can be used for this directly, but at a worse (polynomial) sample complexity. Thus, we do a bit more work to derive new model-learning algorithm for low-rank MDPs, based on Rep-UCB, that is more sample efficient in the source tasks.
A finite-horizon analysis of Rep-UCB was done in BRIEE (Zhang et al., 2022), so here we just need to replace BRIEE's 's Replearn Sn with that of the MLE, which is how we learn and f., as in Rep-UCB. Recall the notation of (Zhang et al., 2022).
(s a) Σ (s) (ni 0=
18

---

Under review as a conference paper at ICLR 2023
Algorithm 4 REWARDFRRE REP-UCB
1: Input: Regularizer An bonus scaling an, model class M + x Y, number of episodes N.
2: Initialize To as random and Da.o, 2/,0- 0.
3: for episode n ...,... do
4: Data collection from nn for h = - H 1,
8 h a Uni s' ~ (s)
3 -- -- Unif(AA,, 3 P - Unif(A), P
Dn,n Dh,n-1 {(8, a, 80)) a/,a = D (("',"',3""
For h only collect Po,n.
5: Learn model via MLE: for all h = 0, 0,1, H- -
Ph (on.ns Ah..)
argmax ED,,, [log (s, un (s'))
E.
6: Update exploration bonus: for all = 0,1,...,FF -1
b, a) = On
@nn(s a)
8-11
Enn
Σ
+ Aut.
(e,o,
7: Learn policy nn = argmax, V P..
and let Vn be its value.
8: Let ñ argmin Vn.
9: Output: ū, Pa.
(s
s Unir(())) (Pt(s á,ā) Unif(a)]
4m0
(8, a)
h (s,a) a)
==0
Σ P.o.n nEp [o(s, () a) A. By using MIE (Uehara et al., 2021, Lemma 18) to learn models, with probability at least 5, for any 1,2, N and 0,1, H 1, have
Esn.. (h,n(s ( } S Sn. (3)
max
E B
(s. (A,(ss))-PPsssaa a)
where
log (IMInHf/)) (lo8(MM]ll10)) S. o
n
and [M max | | |.). which we assume from now on.
We also adopt the same choice of any parameters as BRIEE,
An θ (c11g((M)1H110)
O₂ e (VnlAl2G, + +nnd)
As in Rep-UCB, we posit standard assumptions about realizability and normalization, on the (source) task of interest.
Assumption E.1 For any h 0,1,.., 1, have Oj ty, and pi E T For any & E t (lo(s, a)ll2 $ For all μ E Th and any function g S we have S. g(s)dp(s)) S I1olloo vd. Lemma E.1 Let r be any reward function. Suppose we ran Algorithm with line 7 having reward r + bn instead of just by. Then, for any E 10, w.p. at least 1 - ö, we have
N
vān
- VRr <0 / (N -
Paurtbn
0=0
19

---

Under review as a conference paper at ICLR 2023
Proof. Start from the third equation of Zhang al. (2022, Theorem A.4). Following their proof until the last page of their proof, we arrive at the following: for any n = 1,2, .N,,,
p
2-2
<
V And / |Alaîd/n
h=0
H-2
(2H 1)
E Baand | (3, (3,,))l>
vn|AIGa + And + (2H 1) AA
h=0
By elliptical potential arguments, we have
N
E saaddp (8,
S
dN log
1
dYi
Tha
==0
Thus, summing over n, noting that nnn; On: An are increasing in n, can combine the above to get,
N-1
prrrr
Pn
n=0
N
H (HVIAlaRdd+an ANd H² / NISN + ANd
2A
dN log
1+
dAi
N
2A
dN log
1+ dx1
(HVNIARSNd ANd + H² NIAINN + ANd
N
dN log
1+
d log((M
dy
E EO
(olo((M)NHH))
This gives the following useful corollary for reward free exploration. Lemma E.2 For any 8 (0,1) w.p. least 8 we have
Tog NH/00
Pa 5 0 HPASAp
N
Proof. By definition of Va have
N-1
N-1
Su P..
<
N/2/2
==0
which is bounded by the previous lemma and the fact that V reward function is zero.
Pr = 0, since in Algorithm 4, the
Conditioning this, now show that the environment P7. has low TV error for any policy-induced distribution.
Theorem E.1 For any policy we have
#-1
Tog(IM[NH//8) = EIV.
as) - Pn,n(s, a) l)lmn 50 HA
Eaz..
N
h=0
20

---

Under review as a conference paper at ICLR 2023
Proof. In this proof, let P = Pa. which is the returned environment from the algorithm. Let r(s,a)= = (s, a) Pr(3s a) || Lr
E [0, Then,
B Bag P.N [)]
h=0
Vp..r V.rr
H-1
Σ
Bgg
(Bpx(saa
BBiisaa)) V VT (.
(Simulation lemma)
P.l.
4=0
H-1
Σ Edg, Pp((, -Pa(s,a) TV
S 2H
h=0
Thus,
(s. P
h=0
H-1
(s))))) - Pa(s,a)
(2H 1)
Edg, P.N.
(by (Zhang et al., 2022, Lemma A.1))
h=
H
Σ
Edg [on vIAASS012
log log(I (MM
H
VJ Pba
+ V/ 2|A1|
log (H
H
V P.Da
2|A
log (
log log(IM (
H
H2 | A
(by Lemma E.2)
N
N
log([M[NNH08)
EO
N
This also gives guarantee on the TV distance between the visitation distributions induced by P* vs. by P. Lemma E.3 Suppose P satisfies the following for all 0, 1,
H --1 1, Shh
VT Edy.. a)) - (s)
TV
Then, for any h = 0, 1, .,... H 1, we have
h
VT : |
P. dp.
TV
Et:
1=0
Note, for O, the sum is empty the right hand side is O.
Proof. We proceed by induction for O, 1, ..., - 1. For the base case of 0, no transition has been taken, so that d di-..o P.o oo Now let h E 10,1, H - 2} be arbitrary, and suppose that the claim is true for (IH). We want to show the claim holds for + One key fact we'll use is that, for any measure μ,, have || supp///>> [f]. Below we use the notation that f(s 7) [s)
1| 1 dhillr
21

---

Under review as a conference paper at ICLR 2023
sup
Eay 1141
[f(s,a)] Buy, [f(s,a)]
sup
B (3,ā) P.N. (c.0))P (s( mh+1)] -
(eaa) [/(s, Tb+1]]
=1
(B(30)_ B(aaaraa) B [s,
sup
11
+ sup
B(za)ad
[ f(s
11
4
(ER - EPz f(s, ((t))
Et + ((sa)vd
sup I|
(by IH and Jensen)
A-1
Et + Eh.
(by (4) and [lf(s, mx41)ll s 1)
1=
as desired.
Thus, when combined with Theorem E.I, we have for h 0, 0,1, H
and any policy म.
d dp. wllTv so HPPLA|S log( ((
ETV.
(5)
N
In other words, the sample complexity needed for a model-error of erv
d A log( (
Note this is much better than FLAMBE's guarantee (Agarwal et al., 2020, Theorem 2) which requires,
O d A|s log((M)NHH6)
F REWARD-FREE EXPLORATION
In this section, we show that the mixture policy returned by Algorithm 2 has good coverage. Recall that Algorithm 2 contains two main steps:
Step Learn model P. This was the focus of the previous section, where our modified REP-UCB method obtained a strong TV guarantee ((5) by requiring number of episodes most,
NREWARDFREE = O H (0
evv
Step 2 Run LSVI-UCB (Algorithm 6) in the learned model P with reward at the e-th episode being TRUE. The optimistic bonus pushes the algorithm to explore
bR.e and directions that are not well-covered yet by the mixture policy up to this point. With elliptical potential, we can establish that this process will terminate in polynomial number of steps.
We now focus on Step 2. Let T, denote rolling-in π for h steps and taking uniform actions on the h + 1 step. thus inducing distribution over 8h+1, 0h41 We abuse the notation a little and use л +1 for policy that just takes one uniform action from the initial distribution do-
Lemma F.1 Let & E (0, 1) and run REWARDFREE (Algorithm 2). Let AR,N be the empirical covariance at the N-th iteration of LSVI-UCB (Algorithm 6). Then, w.p. least 1 8 we have,
H-1
sup
E
[ an)
S 5 /og(ddNH/8/N.
A
0=
22

---

Under review as a conference paper at ICLR 2023
Proof. In this proof, we'll treat the empirical MDP Pa, that is the environment we're running in. Thus, we abuse notation and Pr. is the model-based perpsective of the linear MDP, i.c. @hfihe where The is Ahe _k=1 on (s of (+))+))) Also, in Algorithm 2, we set reward to be zero, but for the purpose of this analysis, suppose the reward function is precisely the (unscaled) bonus in LSVI-UCB, i.e. (St: 0h) ( a4). This does not change the algorithm at all since the 9-scaling of the bonus dominates this reward in the definition of Qh,es but thinking about the reward in this way will make our analysis simpler.
Recall the high-level proof structure of reward free guarantee of linear MDP (with known features 3)) (Wang et al., 2020, Lemma 3.2).
Step Show that Vh E Vn and w.p. 1 - 8, for all h,e,
Ph. an) as) (sh. and f (sh an).
Vsh. ag
sup SEV.
This step only uses self-normalized martingale bounds. So, line 9 use any martingale se- quence of states and actions, and this claim still holds, with bonus br using the appropriate covariance under the data.
Step 2 Show optimism conditioned on Step 1. Specifically, for all = .N, have Edo Vo' (so, re) (so) S 0. To show this, we need that (s,) = (n,, मf, (sn)) 2 Qn,e mi (8))) (this is for the unclipped case of -ooptimism), which we have satisfied in the algorithm, i.e. nf. is greedy w.r.t. Qh.e-
Step Bound the sum E. Vh,er where decompose it as of expected bonuses with the expectation is under T..
Step 3 is the only place where we use the fact that s at are data sampled from rolling out क.. For Step 1 and 2, please refer existing proofs in (Agarwal al., 2019; Jin al., 2020b; Wang et al., 2020).
Now we show Step 3 for our modified algorithm with uniform actions. First, let us show simulation lemma. For any episode e = 1, 2..,, N, for any s, recalling definition of reward being bp we have
(50) S (1 + B)bu, (8o, (86)) + Po.e(su, T (s.)
I (1 + 2,3) (50. (s0)) + Po (=))s))
where the first inequality is due the thresholding on Vi, 's and the second inequality is due to Step 1. Continuing in this fashion, we have
#
Edd
[oo0( S
28)
Σ h=0
Ere (bn.ess,,a.)
Summing over e = 1,2, N, we have
N Σ
#-1
Edo
(Po.c(0))
3
Σ
En (nn, an)]
1=1
h=0 e=1
N
$ A6 Σ
E
(s [br.e (Sh, az)
For each h 0, 1,.,,,. 11 1, apply Azuma's inequality to the martingale difference sequence
Ae = E [ +1 (b.e((s 8h, an)] - br.e (5f, af,). The envelope is at most 2. So, w.p. 1- 8,
H 11 N
< AB Σ
Σ
(s ag) + AB N log(H(5))
h=0 c=1
23

---

Under review as a conference paper at ICLR 2023
Now apply a self-normalized elliptical potential bound to the first term, giving that
H-1
Σ
( ah)
5
Σ bn,e 02)2 3 x H dN log(N).
Thus, we finally have
Σ Edo [Pan(so)]
A3H dN log (H/6).
Consider any episode 1, .... N. By definition, AI,N ł An.: so for all s, a we have pointwise that bp. (s, I bh.e (s. Hence, for s, we have Vo r) I (s; and further using optimism, we have
2..,
N
dE Vo (80i [N) S
Σ
Ed [V (80; S Σ Edo
(8o) E A3H / dN log(N
6=1
e=1
Now consider any h and policy n, and consider rolling it out for steps and taking a random action. Then we have
E
@n an)
S
Edo
Vo
(s0:TT)
A8H (dlgg(NHH/)))
A
Summing over h incurs an extra H factor on the right. This concludes the proof.
Lemma F.2 (One-step back for Linear MDP) Suppose Ps = (oh, px)) is a linear MDP. Suppose is any mixture of n policies, and let Σn, := nE, (sn an (n) an T *1+ +X XI denote the unnormalized covariance. For any g S A R, policy n,, and h 0, 1, .... H 2, 2, we have
Ex (x S Ex ( allls, v /nAB 1 11 + Ad|igli
Proof.
En (sn, S g(sn41, Thti (d=l)dpa(sntt)
Bn 10($n+1,0041)
S Er ll and an)ls 11 mmn i Th
Ex
where
Mon ((ntt1, Th+t (dti)du (duux (sh+1)
=nEp
(Eennin [0( +
g(5h41, ah-1)d (Sn+2)
sh11
I <n|AAB pit (4+1) + Ad|[gll..
Under reachability, we can show that small (squared) bonuses and spectral coverage, in the sense of having lower bounded eigenvalues, Lemma F.3 Let E, be a symmetric positive definite matrix and define the bonus by (s a) |0o (s, a)l Then we have
somewhat equivalent.
1. For any policy n. Eag (s, a)] < XE) That is, coverage implies small squared bonus.
2. Suppose reachability under 0² (Assumption 3.3), then have the converse: there exists म., v
for any policy n, Egg [6] (s, a)] 2 Amin (E)
That is, small squared bonus implies coverage.
24

---

Under review as a conference paper at ICLR 2023
Proof. The first claim follows directly from Cauchy-Schwartz. Schwwrtzz.. Indeed, for any policy n, we have Eag I Edg, [1lo (x) 1 Amin (E)
For the second claim, Assumption 3.3 implies that there exist policy स such that for all vectors v IRd with ||o|| = 1, we have Edg [(0% (s, a) w)'] 2 th Now decompose = >í Acugo," where A are cigenvalue/vector pairs with 1lo/122 = 1 and Yy 2 X 2 Aa Then substituting this into the definition of the bonus, we have
Eug (8,
[10 a) a)),,)
X
i=1
B [[0% (s, a) vua)) va)
Ad
Ami (E)
We now prove our main lemma for reward-free free exploration, Lemma 4.2. Lemma 4.2 (Reward-free Exploration) Fix any source task k E [K 1]. Suppose Assump-
tions 3.2 and 3.3. Then, for any ô E (0, w.p. 6, REWARDFREE (Algorithm 2) with
NLSVI ULSVILUCB UcB 3 HA and NREWARDFREE = =O(30t (A3 log [1|T]
NEsvi-UC)) returns
Xumin explorrapyyy policy Th where Amin = á (A-33 - The sample complexity here is NREWARDFRES episodes in the source task.
Proof of Lemma 4.2. In this proof, let
A NE +1 [oh an (sho% an) "] + Al,
AΛ N.svi-Ue ph- (sh, an )n On (sh, an) +
where À dH (oog(NNsvv-ucn//)) 2 1. This setting of satisfies the precondition for the Concen- tration of Inverse Covariances Zanette et al. (2021, Lemma 39), which implies w.p. at least 1 that
Nismatca
An 22
Σ
Oi) aN) + +11)
3 2A N.Nsosue
where we've also used the fact that X > so (A A1) (A+1)-1
Under this event, for any æ,, we have,
" < Σ E
E
@n(sn an)
[o an)
(6)
Now let h 0,1, 1...... H be arbitrary. By Assumption 3.3 (there exists some policy with coverage) such that,
Amiu
A A
1h+ shtt an+1) 2 (Agn))'
< Ez
(by Lemma F3)
< Es | (S an+1) (Ai=r))
(by 1)
< E | an) x
A(2d + ETV Nisv-Uuu) + +ETV
(by Corollary F.1)
25

---

Under review as a conference paper at ICLR 2023
$ E / R 1
VA(2d + 1) + 1/NLsvi-UeD
(by ETV = 1/NLsvi-Uee)
A cl 113 1 /bggld//NNusss..cc////////////a
+ 1/Ntsvi-Uen
(by (6) and Lemma F.1)
S dL H²
Livv-UCC
Recall that À = dH log (og(NNssv-Uce//) we have,
(s, Amin (B (0) 1s,,))))
Amin (A1+1)- -
NLSVI-UCB
Ct
dll log log(NNsv.ucas/0)
LLvI-UCB
A15 H3
/log(dH NesvI. /6/ / Nisvv.
C
dH
12 H3 /Nisv-tte NIsvi-UCn where we' we've ve omitted the log terms for simplicity in the Z. Now we optimize Nisvi-UcB to maximize b. it's best to set xx such
this bound. For a, > O, to maximize a function of the form f(x) = V x.
that Vx resulting in value f(**)=
2h
ib. Setting,
a²
a = LLvI-UCBB
C
23
dH.
Hence, we need to set which results a Amin lower bound of
Ucs = ① (b2/22)= = AA
)
1/2
(
2/2
+1 [ (sn+1. (111))011)11000000) (8/+1, ) -d(2)))--i -
Aminn
H7
Finally, we used the fact that erV 1 1/C which is set by the choice of NREWARDFREE in the lemma statement satisfy (5).
The above proves coverage of p for = 1,., - 2. Finally to argue for p=1, which is simply taking a random action at time h, we can simply invoke Assumption 3.3 for h = 0 get a policy ă that
/
E Ep1 (so, ao) ao)o ao) T|
Ex
[s0 an)o6(50. ao)
A
A
Corollary F.1 Let X, Ar, An be defined as the proof of Lemma 4.2. For any 0, 1,..... and any policy we have
E, [1 an+1) ( s E...P [Iōncon an) |2, VlAl(2d + ETV NLSvI-UCU) ETV.
Intuitively, this means that coverage in the learned features implies coverage in the true features.
Proof. For shorthand, let NESVE.UOR. Apply Lemma F.2 (one-step back) to the learned model P and the function (s, a) + 11 a)ll (AR.I) which bounded by 112 < 1. We have.
E ExPP 1 (s an an- (1
<< E E (sh.
NIAIE Flloo "TAlB,,tt,llliiill alti)l? (ntt))((AEa))
26

---

Under review as a conference paper at ICLR 2023
S R x nn (sh.
an) (sh: an)
NIAAE :
11 (8h+1, 06+1)| (Aā+1) (Ak+1))
+ N|AlerV + d
3,
S E x
1x--
v
d.A N/ +d,
where we used the fact that
pp
ax+ 1l1 (A)_))-
=Ir E [oh+1 (sh+1 ant (04 an+1) (NE,t [on an) an) + 21) -)
d
N Tr(I M) S N
where M is a positive definite matrix. Thus, doing an initial change from dh to d PA++1 the proof.
concludes
G REPRESENTATION TRANSFER
First, prove Lemma 4.1, restated below.
Lemma 4.1 Suppose Assumption 3.4 and that for all source tasks h [K 1] we have Amin-
exploratory policy Tk- Then, for any 8 E (0, 1), learning features & using the cross-sampling
procedure of Algorithm I satisfies (2) w.p. 1- 6. Furthermore, for any h = 0, ..,,, H 1, there
exists jun S + He such that for any function g : S [0, ll g(s g(s)ddn(s)]l S avd and
sup Px ( an) (.)))) 0% (Sh, (n) (kaa 1 Serv ViAlo Ka/Aminn Amin-
Proof of Lemma 4.1. Fix an arbitrary æ. Denote pn(s) EK-1 assh (5 (s), First, note that
/ u (n(()))())(()))
max g:S (0,1)
K-1
/ (A: Aena())aan
max 8:8 0.1] k=0
max (n (8)V
(Since J (s)(())()))(s))) s by 3.2)
k=
avd
For any h = 0,1, ..., H we have
Ex.P 2r (Sh> an) (m(()) - 07 (sh, an) 1
EEx,
Σ Σ
an (sn+1)
(pn(s,, and (ash()ntz) Φ2 (n)) T (oott))))
R=1
< Er,
lon (sh+1) ea (8h, Teec (8nt())41) 2% (sn, (Mes (essa(8ntt)))
1=1
K-
(2n(sn, TT (sh, and phan ly
< O'max
E..P%
k=
First consider the case when 0. At h = 0, the distribution under Pk is the same as Vk,ks and so, directly get that the above quantity is most O'maxe
.1/2 which proves the h 0 case.
27

---

Under review as a conference paper at ICLR 2023
Now consider any 1,2, H 1. To simplify notation, let denote (5h an) ( an) (P.a)))) (sh, an) Mlnn (-) mv
wk:h = =f (
an);
ΣsAh = BrE.P (ok an 1 an) Note that Amiu (ER,h) 2 Amin by assumption. Now continuing from where we left off, we take one-step back as follows,
K-1
Omax
Ex erfich (Sh, ah))
1=1
K
Ex (0%-1 (sh-11 an-1), wksh)
Omax
k=1
Px 11 (s 111s))))
Iewn E
amax
k=1
By Amin guarantee of Ek,hs and Jensen's 's inequality to push the square inside,
K-1
Omax
E Lan- PPina Rih- (1 an -11, (T) CITki (8h, an)
Vmiin
k=1
11/20maxx
K-1
Bes--1.h P P (a. ( on)
Vunin
By Assumption 3.4, the expectation over P a linear combination of expectations over s jih-1
3/2 K-1
Ommax
Esn 1.th
1.ah (3e.=
Vunin
1/2 2 Omaa
3/2
K1/2
K
Σ
E
(sh 1.9h ( an
Vxmin
A 2 O'ax K1/2 11/2 1/2
3/2
Amiin where we used the MIE guarantee (2) in the last step.
Algorithm 5 Transfer learning with online access
TRA-ITRGN PHASE
Input: num. LSVI-UCB episodes NLSVI-UCS. num. model-learning episodes NREWARDFREE, size of sampled datasets n, failure probability
do 2: Find policy cover n& =REWARDFREE(P: NLSVI-UCB NREWARDFREE, 8). (Algorithm 2)
1: for source task & = 1, ...,
3: for source task l = 1, ..., K do
4: For each h 0, 1, ...,,..,... H sample D3. i.i.d. (sh, an, 88+1) tuples from ną-
5: For each 0, 1,.,,
1, learn On MMulii-task REPLEARN (eeKk-/- (Algorithm 3)
DEPLOYMENT PHASE Additional Input: number of deployment episodes T.
1: Set 8 = Hvd+ + adH Vlog(dHT/8),
2: Run LSVI-UCB ( TK, in the target task PE (Algorithm 6).
H-1
Next we state an analogous lemma for when we don't 't need generative access to the source task, but instead assume Assumption 5.1, and Assumption 5.2.
28

---

Under review as a conference paper at ICLR 2023
Lemma G.1 Suppose Assumption 5.1, and Assumption 5.2. Now take the setup Lemma 4.1 with the only difference being that & is learned in Algorithm 5. Then, the same guarantee of Lemma I holds with slightly different right hand side for the bound on the TV-error,
O'max K 11/22112
sup En, Pk (ou(s, an) pa))) (sh and picaO))
(#rra 1/2²
Proof of Lemma G.I. Fix an arbitrary Denote (n(ss) (s') algebra with importance sampling gives us the bound,
k== and (s (s)) Then, some
Ex
Tn (rr,aha T pn(+)) 0% (sh, an) picaa()
K-1
Ex
Σ
Σ
onsh (sn+1) (on(su, (aaa(8nt1) 22 (sns (())naa)))))))))) v (ont)))))
81
S Ommx
PT
pox (sh,
(nh, an) (es(()) (es (8,, an) T 1l (
k=1
K-1
< O'mxx K2/2
Σ
Ex,Px
| an) Tuap (.) $7 (sn, on) T (igh()) TV
k=1
Assumption 5.2, for any s,a, we have (s.a)
By
Assumption 5.1,
(e.0)
Praw where we used the coverage-under-Ti
Amin (er.nn (o
assumption in the last inequality. In other words, for each &o = 1,2, ..., K 1, we have hence we can importance sample,
dd Ksh
Prow Amina
amax K 1/2
K
Pt [ T 0% (sh, an) Mh (1)
(Wrow Amnn) 1//2
Qmax K 1/2 22/2
(rin))min) 1/2
H PROOFS FOR DEPLLOYMENT PHASE
H.1 ONLINE RL LEMMAS
Lemma H.1 (Self-normalized Martingale) Consider filtrations [Fi)i so that Ele; F and {e, Fi-1i==1.2
sub-Gaussian with parameter 0². Let {Xi) be random variables in hilbert space H. Suppose linear operator Co H + is positive definite. For any define Σ, = En + Ei=1 X,XP. Then w.p. at least 1 5, we have,
(dt((E.) dct(Eo)
2 1:
Σ X
S 2 log
82
Proof. Lemma A.8 of (Agarwal et al., 2019).
Lemma H.2 Let A, = AI + E 2.oe for E Rd and X > 0. Then +f (Ar) -'z; S d.
Proof. Lemma D. of (Jin al., 2020b).
29

---

Under review as a conference paper at ICLR 2023
H.2 PROOF OF MAIN RESULTS
Let {g) refer to the clamping operator, i.e. (z) min y). Let My be the maximum possible value in the MDP with the given reward function.
Algorithm 6 LSBI-UCB
1: Input: Features (oh J h O.1,,,,..,, -1 reward (ra yrn (r1.,..,1,...,.-11 H- number of episodes N, bonus
scaling parameter 3, UNIFORMACTIONS = FALSE.
2: for episode e 1, 2.., do
3: Initialize VH.
0,
4: for step h= - 1, 2..., do
5: Learn best predictor for Vi+
An,e
Σ 2n (sh a (s a + 1,
(s Whizee k=1
Whee
mee
6: Set bonus and value functions,
(s, = |[(((, | @
Ail Th (1, + as) + (s,,),
()) (n,
Vine(s) max ( SMV
7: Set (8) = argmax, (s,
8: Execute σ to collect trajectory (sh, o k====
H-1
9: If ANTIORMACTIONS TRUE, discard 0f and draw freshly sampled uniform actions indepen- dently for all h, i.e. of, Uni
10:
Return:
uniform mixture Uniform [ Jem
Previously, Jin et al. (2020b) analyzed LSVI-UCB under point-wise model-nisspeccficationn Here, we show that similar guarantees hold under more general policy-distribution model-misspecie podell-mispecificatiion Ema, captured by Assumption H.1.
Assumption H.1 Suppose for every h = 0, 1...,, H 1, there exist jún such that for any policy x,
Ex (T (sh: an) - (. (.1 sh:
S Ems-
We further assume that sup,,a a | ()) a S Mn and Tinll & M,valfll Af
+ R. for some positive constant Mμ.
In other words, we only need the model to be accurate on average under the occupancy distributions realizable by policies. We also make slight generalization the regularization constant Mμ, which set to 1 in the original linear MDP definition (Jin et al., 2020b). Later, we will later instantiate the above assumption with our transferred (s')s))= = Ex
K-1 alk. (s' PP.) (s'). then for any s, a, we have
(s, Σ
(s (s,
(o (sa)) (ss()
K
max la (s')l
(by | 1)
30

---

Under review as a conference paper at ICLR 2023
a.
Also,
| 1 1
ong (i
k
Σ max (o)))(('))
Σ Mann (m)n(s
S savalllle..
(by 11 P S Vlll)
So we will set M₁.- a.
Note that we only need the existence of jrn here, and (.) need not be a valid probability kernel. fact, it may even be negative valued.
In this section, we make a model- based analysis of LSVI. Similar approaches have been used in prior works, c.g. Lykouris et al. (2021); Agarwal et al. (2019); Zhang et al. (2022). For simplicity, suppose that S is finite, but may be exponentially large, as we suffer no dependence on (S]. The proof can be easily extended to infinite state spaces by replacing inner products with P by integrals.
Consider the following quantity,
PhLe Σ (o at))) (An,e) E argmin
Σ (s of)) (11/+1)ll2 + 1
MERSX
where 8(s) is one-hot encoding of the state In words, this is the best choice for linearly (in on (s, a)) predicting (p [ō(s') (s s,a). We highlight that this is just quantity for analysis and not computed in the algorithm. Finally, denote
Pr.,- Pn,ehh
Ph. = pu.
We will also sometimes use the shorthand ( for P(ta)))))()))))))
For each 0, 1, .... H 1, let VA denote the class of functions
max { " (s, a) + (a(s a) + 31lon(s (s, a)lla-
|woll - NMv, E [0, B), symmetric
SMV
The motivation behind this construction that Vn, satisfies the key property that all of the learned value functions Vh, during Algorithm are captured in this class.
Lemma H.3 For any h = 0, 1,.., H
1. sup, Pine(s) My.
2. For any = .., N, we have Vn, E Vn-
3. Vʃ E Vno we have sup, IS(x)) S Mv.
Proof. Recall that
Vn-(()= - (max To The (3. + (o()))) + (lna((,a)))) SMV
where Whe A (s Unere
From the thresholding, we have
Pino(s) < Mv.
31

---

Under review as a conference paper at ICLR 2023
We can bound the norm of Whe follows,
Lww ll - AT.
( s N sup ( s NMV.
We also required 8 < B, and we regularized the covariance with I, so Amin is at least 1. Hence Vi. satisfies all the conditions be in V/.
Now we control the metric entropy of V₁, in lo, i.e. f2) - sup, Ifi(s) - -2((s) for fa E Va. Lemma H.4 Let E > 0 be arbitrary and let Ng be the smallest E-net with foo Vh. Then,
log We I dlog(1 6L/E) + log(1 6B/s) df log(1 18B2 /d/=".
Proof. Let f1, Vh. Then,
[f(()) f2(8)]
I max (wi - w2) (8, + B1 a AA
a))
-B2
A7
1-
< ||l] -w2ll2 max (3) 32) (an( (3,
+ 82 m max
Tnn (8, a)
17 - -100((
15a
$ <|lw -22ll2 |81 - B21 + B max | a)
[ a)
A0mi(A1) 1)
A7
$ ||-] - w2ll2 + |81 - B21 + B || - Ar 11
where used for any a, b 2 0, we have |Va vbl
vā+vb V/a la - bj < V/a b/. Now
Ma-
proceeding like the Lemma 8.6 in the RL Theory Monograph (Agarwal et al., 2019), we have the result.
In this section, we'll use the following bonus scaling parameter,
8= O (VNde My + My Mady Mo.d//oo((NM//88)
The following high probability event (Emodet) is a key step in our proof. Essentially, Theorem H.1 guarantees that, for all functions in Vh. the model we learn is accurate predictor of the expectation, up to bonus and some vanishing terms.
For all the following lemmas and theorems, suppose Assumption H.1 and the bonus scaling 3 is set in (7). Throughout the section, (a(T)) refers indicator functions of the trajectory The where Th = (sp, $1,.,., 8.). ). As before, the expectations FF [9(T%)) are with respect to the distribution of trajectories when is executed in the environment P*
Theorem H.1 Let (0,1). Then, w.p. 8. for any time h, episode e, indicator functions SI,..., Sn. and policy we have
sup Ex (Phnc(ssh an) (7 and SGu(Th)] 1 EE (8h, (T)))(TT)) + [[ E sev
(Emodda)
Proof. Condition on the outcome of Lemma H.5, which implies that w.p. 8, for any h, e, n, Sh. we have
sup
E, (Phhe(on, un) (sn,, an)) SCA (Th)
SI (6) (n)))
SEV.
Also, for any h, Sh. by Assumption H.1, we have (w.p. 1) that < Ex,
Ex [Phhss, an) P (h)) fCr (TT(
(Ph(sh, an) - -P an)) s Ca(Tm))
sup SEV,
sup SEVi
32

---

Under review as a conference paper at ICLR 2023
sup ( (Pa(sh, (s an) / SeV,
S F
|| V/. Im0
Combining these two yields the result, as
Ex [Phheeshh an) (sh, an)) fCn(Tn)]]
sup feV.
Fg [(hh(sh: an) (sn, [SA(TT)]
B ((Phe(ss: an) - Pn (sn an) s(n(Tn)]
S sup feV.
sup
SeV.
Lemma H.5 Suppose Assumption I and the bonus scaling B is set as (7). For any 8 e (0, 1), w.p. at least - 6, we havefor any time h, episode e, and policy TT,
Vsh, On sup SEVA
(Phnl(n,,a)) an) Ph(ss, an) / S (bn,a(sh, un).
Consider any h e, æ. Define xx == - -5(( (s ( at)) so that Elet Hx-1] where Ha- contains the states and actions before episode k. In what follows, we slightly abuse notation, as P(s, a)Ø² "s, (s) will denote the outer product, and hence SSd quantity.
Proof.
An.
1) (hh, at)
Σ ( (5h atj Po aht) on Tn(sh (sh, aht
Σ
Ph - - sh) (sh. ot)
+
= Σ (Pr an) - Ps aht) at)) + +hn (An. - 1) Σ c (h) oht""
k=1
Rearranging, we have
uh. Thh
Σ
(s att) - (h ((1) Tn ((57) (Mmie)
k=0
pn (An,e)
Σ (hin aight) (dna)
Now let Vn be arbitrary. For any 8h, dh, multiply the above with on (8h, an) and multiply with f. we have
(h.c(sh)an) an) -P an) f
ST (Dn. (in)) on (sh. an)
TT
Pa (S att Pr (5 okt) dn Tn (
Term(a)
IT Jún "innA A (n an)
Term(b)
+
T
(s of)
Ant Sn (sh, an)
Am
Term(c)
33

---

Under review as a conference paper at ICLR 2023
We deterninistically bound Term (b) as follows,
f P A he on (sh, an)
sup feV,
(A "nn"" (Ai pn an))
sup SEV,
| | |1f (su
sup SeV,
|Vllla v ($h, ax).
(by Assumption H.1)
This term will be lower order compared to the other two.
We now derive the bound for Term (c) for any fixed f E Vu- Observe that
( st)) T
on att")) An.
=
Ap,e
1/2
Σ on (s a
(Ar.e 1/ (sns an))
(s
a (f
(ne an).
A
Now we argue w.p. 1- 8, for any e, have
Σ os (f
s (211ill V 2log(1/0) + dllo(NN + +1))
A5
which implies the claim about all 8h, ah. Indeed, we can apply Lemma H.I. Checking the precondi-
tions, (pg(ss.a.) [5 sk HH-11] = 0. S [ S | I S 21[Vil det( = det /
and dct(E.) det(An, S (e 1)d since the largest eigenvalue e 1. So, w.p. at least for all e, we have the above inequality.
Thus, for any fixed| Vh. w.p. 1 5, for all h we have,
(h (s))an) an) Pa (sh, an)) |
> Term(a) + Term(b) + Term(c)
x (4]]Vall + M₁) (ll())/ool///l/ll (og((1/) alool///))/oo(/(WV dllo(NN) +
AN ( bh.c(sh, an)
(Dalloo bn. (s. an.)
411 Voollloooog111 wlt////g/////// + dloo((V)) b (s.. an)
VaNiiIVilleenn [/ M,,
M log(110) +llog(NN) (s, an)-
Now we apply a covering argument. Namely, union bound the above argument to every element an Enet-net of Vn- For any f E Vn. let f be its neighbor in the net s.t. || Illo0 S Enats so we have
( (Ph an) (n,, an)) {
(Prie(sh; an) - Pr. (sh, an)) j| + ++|(PPnnn (Pne((n an) Pr (sn, an)) (ī (5- n)
and
( (Pn (Sh, an) - (sh, (F - 2 11- 1 + +1)
SnetN.
Setting Enet N, the metric entropy is of the order d log(NV (My (og B) + log(
The error incurred with this epsilon net a constant, which is lower order.
Thus, we have
Vsh. On sup (Pheess, an) Pn (Ph an)) feV,
34

---

Under review as a conference paper at ICLR 2023
24 (VdN (VillooE + My + +d dllogMMy) + d2 log (og()) bn (sn, an)
2 VaNNMeess + My log + + dlogg + d2 log (BdN)) ( an)
Note that/ 3 scales as Vlgg B, so one can find valid by solving / S for B.
Lemma H.6 Let f E Vn. For any å E (0, 1), w.p. at least 1 - 8, for any time h, episode e, we have
Ysh Op ft
EP Ph at) - Ph oit) ( ". (sn 2z
(4II + Mn) dlog(N)))) + vdNllDal ooems) (s an).
Proof. First observe that
fz
Σ
Ph at) T oz ott² Ano
A 1/2
Tn (0h d² (P2 o (oonishhot)) 2u
he
Σ in a
(sh an),
An.
where Ex (5t att
Pa att) f.
Now we will argue that w.p. 6, for all e, h.
(sh
E
S (4I1
+ VdN (ool
AT!
which will imply the claim for all 8h, Og.
Apply normanarml martingale concentration (Lemma H.I) to X, = (1 of))) and E = E. E [E H4-1]. where the expectation is over (s), af) in the definition of ē.. To see sub-Gaussianity, bound the envelope, ( < || ( -f))-nnnn(st ll) S (1+ |ēxl s 2// (1 + M,). Now compute the determinants: del(An.)) and since Amax (An,e) S
and thus <
+ 1, we have that log det(An,e) I d log(e + 1). Hence, w.p. at least 8, we have
Ve:
Σ (s at (Ex
1o Ha-1))
S 21ID + M,) /2)o/l111//// + dlog(N + 1).
Ag.c
By Assumption H.1 applied to x (the data-generating policy for episode 1)) we have
E Th H4-lll < |1 oo Ems- Recall for any scalars e and vectors F, we have 1, c.a. S
Σ, |e _ E, E, | Thus.
Σ
on ( (s of E
[R
Hu
A71
1 1121122
Σ E [E
H4-1)
35

---

Under review as a conference paper at ICLR 2023
S Vdd((e
(by Lemma H.2)
Combining these two bounds concludes the proof.
Lemma H.7 (Optimism) Suppose (Emodet) holds. Let e = 1,2,... N, we have
Then, for any episode
vh = 0. H - 1: Brr (0i())) Qn.c(ss, Ca(tn)] s (H h),,
and
Vh 1, 1..., H 1: Ey [(V%(s)) Phoc(s)) 5h- (T-I(Th-1) s (H -N)1,
where
(sh) == @n, (h())))) S Mv
(T.) II (sw))
Abusing notation, (-) is the constant function 1. In particular, we have that
Edo (So) - (o.)( S Hi.
Proof. Fix any episode e. We prove both claims via induction on h. = H, - 1, 2..., 1,0. The base case holds trivially since VH.e and V are zero at every state by definition. Indeed, we have that for any ıT, including क that
E (P
- (P
VHI.e) CH CH-I(TH-1)]
E. [00 - 0) ( =0
Now let's show the inductive step. Let h E (H - 1, H 2, .... 1.0} be arbitrary and suppose the inductive hypothesis. So suppose that V Vootimiism holds at + 1 (we don't even need Q-optimism in the future), i.c.
E. [ PP (sh an) Vitt,e)) Su(TH)) E., [(itt1(544)) - Vi+tee(n411) (a(Tn))
I (H - h 1-11 1)c
(IH)
Recalling that Qh, an) = rn(sn, an) + Phoo(sh, an) Vntia + Blhn an), we have
E,, [QQi(s). an) - Qn, an)) Sa(TT))
E., (Pin Ph.c(Sh; an) an Vntiae (hn. an)) Ca(Tn)]
< Er [(PP((5)) (s) (shn Vn+tle- (bn, an)) (a(TT)] + (H - h- 1)c
(by (IH))
< Bn ( (Phno(sh an) (Sh, VatILOS((Ta) Eyp [Bbn, (Sh, as (n (TA)] + (H h 1),
Si+ (H h 1)r = (H- 11-h) h)t,
(by (Emodat) and Va+i.e Vn. (Lemma H.3))
which proves the Qoottimism claim.
Now let's prove Voottimism.
Ex (Vi(st)) - Pholow) Çh- (n-1(Tm-1)
36

---

Under review as a conference paper at ICLR 2023
( @ an) (On ()(()))))))))))))))))))))))))(
Em.
SMv (h-1(Tm-1)
E (1) an) Mv) (Th (n(s)))]
( (oi ah) (nh Af (8h))) Ch-1(Th-1)6m
Ex
< En
(Q% ap) Qno(on. #h (sx)) (A()))
< E (% (5), an) Qn.c m (sw)) (T(T))
(H h)1,
by Q-optimism.
Remark H.1 We did not require Ph.ee to be valid transition! is in general unbounded and can even have negative entries!
Lemma H.8 (Simulation) For any episode & = 1,2,.., N, we have
11
Edg (so) - Vot (8u) $
Σ
Ege
(shh + (Pa(sn, an) (s an) on))
h=0
Proof. We progressively unravel the left hand side. For any 80.
(oo)(50) - V/ (so)
< (s. To (so) QT (su, ms(ss))
= (s)) + (Po.c =f(s)) (so, =8(50)) Vi + P (so: ao(sa)) (he V7*).
where the inequality is due to the thresholding the value function. Now, perform this recursively on the Po (So, (su))
(Fi - v/""
-17") term. Doing this unravelling h times gives the result. O
Theorem H.2 Suppose Assumption H.1 and let 3 and bonus be defined as in (7). Let E (0, 1). Then w.p. at least we have that the regret of LSVI is sublinear,
N V < Ö NV Σ
(JHNMvvToge (NN/)emms + t. HVNN Mng((HHNNN
0=0
where ① hides log dependence.
Proof. We first condition on the high-probability event (Emodet), which occurs w.p. at least 1 8. Fix any arbitrary episode e. By optimism Lemma H.7 and the simulation lemma Lemma H.8,
Edo (so) - v (so) < Edg
[o((s)) - -==((s)) + He
#-1
[b6 and + (Phe(sn, an) - (h an)) Vatile + He
Ep
h=
Applying (Emodet) with no indicators, i.c (T()T) always, gives,
H-1
(2 ax)] + 2H.
0=0
Now, summing over e = 1,2, ..., N, we have
N
Edto
Vo((s)) v0 (60)
Gml
2HN + 23
Ex (b, (Sh, )z)
A=U c=l
37

---

Under review as a conference paper at ICLR 2023
By Azuma's inequality applied the martingale difference A. -E (sh, an)l (h of.. which has envelope bounded by 2, implies w.p. 1- 8,
H-1
2HN + 23
ΣΣ 4=0
( af) + 43 Nlog
remains bound the sum of expected bonuses. By Lemma H.2, we know that almost surely,
H-1 N
Σ
(s. of) & H dN log(N).
h=0
So, putting everything together.
Edo ((o) -Vo' (5o)
HNL + 3H / log
log( (N) + BV N Vlog(HN/6)
< HN (VeNMvems Mm + My M (og(dHN(0) H ON log(HN/8)
HN dHNMV (log(HN/o)enn d HVNHHVNN M, 1/))
Note that H. HI My is of lower order (with respect to N), can simply drop it. This concludes the proof.
Corollary H.1 By setting 8 = 1/N, we have that expected regret also has the same rate as above.
Proof. The expected regret by law of total probability, since regret is at most H,
[Regy] < E [egg (Emodet)) + H - P((Emodet))
< E Regx (Emodet) + H.
Since H is loder,order, have the same rate.
I PROOF OF MAIN THEOREMS
First we prove Theorem 4.1 and Theorem 4.2.
Theorem 4.1 (Regret under generative source access) Suppose Assumptions 3. 3.143.4 and 4.1, and sup- pose the input policies T are Amin- exploorapl....rr. Then, for any 5 E (0. 1), w.p. 1 6, REPTRANSFER
when deployed in the target task has regret at most Ö (L /T log(110) with at most Kn
generative accesses per source task, with O (Xmt Aod KT (log | log m)):
Theorem 4.2 (Regret for REPTRANSFER with REWARDFREE subroutine) Suppose Assump- tions 3.1-3.4 and 4.1 hold, and let 8 (0, Let {T*] be exploratory policies learned from rumning REWARDFREE on each source task with NLSVI-UCH and NREWARDFREE set as in Lemma 4.2. Then, w.p. 1 1-6 6, running REPTRANSFER with {TR] K-1
has regret in the target task of Ō d (g1())) with at most ŌAAa (1 di H2 K2T (log(14)/8) + K log (T]
generative accesses per source task.
Proof of Theorem 4.1 and Theorem 4.2. For the regret bound, set My = H and M,, = ã and apply Theorem H.2. This choice of My is valid by the argument following Assumption H.1. This gives us regret bound of
δ (aH + ad. H5? (TTTo//11)))))
where Eyn can be made smaller than 1/vI in which the second term dominates.
Now, calculate the pre-training phase sample complexity in source task.
38

---

Under review as a conference paper at ICLR 2023
First, let's calculate the reward-free model learning sample complexity, i.. this is the number of samples required for learning Pk. Recall that need this to be sufficiently large such that еTV = 1/Nisvi-Ue- As required by Lemma 4.2, we need,
NREWARDFREE
log (|0) /|/)/ N NESV-UUR) Ô (4'd log
δ A 11 log [ (A ( 6-)
Ö (A' H log (1/8))
Second, we calculate the cross-sampling sample complexity. Recall that is the number of samples in each pairwise dataset. In order to reduce ms to 1/ VT, by Lemma 4.1, we need
1/VT S Ema-
(Aa max K/ (//in)))
1/2
VSn
(Aa K/ Amin)
1/2
log
K log |m]
(by (2))
V
which implies that we need
+ + log mm))
Xmi
Aa max
KT
log
Incorporating the coverage result from Lemma 4.2 gives,
4 δ + K log log (T)
A a d' H1 KT
log
Since each task is in at most K 2 pairwise datasets, each of size n, the total pre-training sample complexity per task is at most,
NRREARDFREE (K - 2)
= = 66(1166 11 log (|]/) + o
log + K log (oggTT]) (T))
Now we prove Theorem 5.2, restated below.
Theorem 5.2 (Regret with online access) Suppose Assumptions 3.1-3.4,5.1.522 hold. W.p. 8, Algo- rithm 5 with appropriate parameters achieves regret the target Ö (ād2- / (og((18)) with at most poly (A, (A, Omax, d, H, K, T, = wrrm log(((||TT)/)) online queries in source lasks.
Proof of Theorem 5.2. We follows the same format as the proof of Theorem 4.1. The regret bound is identical.
Now let's compute the pre-training sample complexity. The regret bound requires us set Ems S 1/ I/VT. Here, our Ems comes from Lemma G.I, so
Omax K1/2
+
I/V <
log
+ K Klogg MM)
(Wraw-mia) 1/2
5
which implies we need
a K
+ K log \T\
5
log
WranoAmin
Plugging in the coverage of Lemma 4.2,
n <
a KT
log
+ K log (
(A 33-36 7
Vraw A a 2 d0 H7 KT
+ K Klog mm)
log
Vraw 62
5
39

---

Under review as a conference paper at ICLR 2023
Here, we only collect one dataset, the total pre-training sample complexity is NREWARDFREE +
=ō -0(A'0 10'Ad' 10g + a &f HH' KTTTyaa 1/= (og {
(ogg/r)) (
+ K log (
J. EXPERIMENT DETAILS
J.1 CONSTRUCTION COMBLOCK
In this section we first introduce the vanilla Combination lock (Comblock) environment that is widely used the benchmark for algorithms for Block MDPs. We provide visualization of the comblock environment in Fig. (a). Concretely, the environment has a horizon H, and 3 latent states ZuA, E {0. 2] for each timestep h and 10 actions. Among the three latent states, denote 2o, #1 as the good states which leads to the final reward and 22 as the bad states. At the beginning of the task, the environment will uniformly and independent sample out of the 10 actions for each good state 20.4 and 21: for each timestep h. and we denote these actions ao:k. G1;h as the optimal actions (corresponding each latent state). These optimal actions, along with the task itself, determines the dynamics of the environment. At each good latent state S0;6 or 81:h, if the agent takes the correct action, the environment transits the either good state at the next timestep (i.e., 80,4+1, $1,++1 with equal probability. Otherwise, if the agent takes any 9 of the bad actions, the environment will transition to the bad state + deterministicly, and the bad states transit to only bad states at the next timestep deterministicly. There two situations where the agent receives reward: one is uponing arriving the good states at the last timestep, the agent receives a reward of 1. The other is upon the first ever transition into the bad state, the agent receives "anti-shaped" reward of 0.1 with probability 0.5. Such design makes greedy algorithms without strategic exploration such as policy optimization methods easily fail. For the initial state distribution, the environment starts in 80,0 or
$1.0 with equal probability. The dimension of the observation [log(H+ H+ [+++)+ For the emission distribution, given a latent state Sic,, the observation is generated by first concatenate the one hot vectors of the state and the horizon, adding i.i.d. A (0,001) noise at each entry, appending at the end if necessary. Then finally we apply linear transfermation on the observation with Hadamard matrix. Note that without good feature or strategic exploration, it takes 10 actions to reach the final goal with random actions.
J.2 CONSTRUCTION OF TRANSFER SETUP IN SECTION. 6
In this section we introduce the detailed construction of the experiment in Section. 6. For the source environment, we simply generate 5 random vanilla comblock environment described in Section.J.1 Note that in this way we ensure that the emission distribution shares across the sources, but the latent dynamics are different because the optimal actions are independently randomly selected. For the target environment, for each timestep h, we randomly acquire the optimal actions at h from one of the sources and set to be the optimal action the target environment at timestep h, the selected optimal actions different for the two good states. Otherwise we keep sampling until they different. Note that under such construction, since we fix the emission distribution, Assumption 3.4 satisfied if we for the other sources, at each timestep. To see how Assumption 5. is satisfied, recall that comblock environment naturally satisfies Assumption 3.3, and identical emission implies that the conditional ratio of all observations between source and target is I.
for the source environment where select the optimal action and
J.3 CONSTRUCTION OF TRANSFER SETUP IN SECTION.
Now we introduce the construction of the Comblock with Partitioned Observation (Comblock- PO) environment. Comparing with the vanilla comblock environment, the major difference is in
40

---

Under review as a conference paper at ICLR 2023
the observation space. In this setting, the size of the observation depends the number of source environments K. Let the size of the original observation space be O = [O], the size of the observation for comblock-PO is KO. For the k-thh source environment, where i [K], the environment first generates the O-dimensional observation vector as in the original comblock, and then embed it to the (k - 1)0-th to kO-th entries of the KO-dimensional observation vector, where it is O everywhere else. Thus we can see that the observation space for each source environment is disjoint (and thus the name partitioned observations). For the target enviormment, since the latent dynamcis are the same, we only need to design the emission distribution: for each latent state Sicb, we assign the emission distribution uniformly at random from one of the sources.
J.4 IMPLEMENTATION DETAILS
Our implementation builds on BRIEE (Zhang et al., 2022). In the Multi-task REPLEARN stage, we requires our learned feature to predict the Bellman backup of all the sources simultaneously. Therefore, in each iteration we have k discriminators and i sets of linear weights (instead of in BRIEE), where k is the number of source environments. For the deployment stage we implement LSVI following Algorithm 6.
To create the training dataset for Multi-task REPLEARN, for each (i.j) environment pairs where i # we collect 500 samples for each timestep h. For each (i, i) environment pairs, collect 500 x (k 1) x & samples for each timestep h, where & denotes the number of sources. Thus we ensure that the number of samples from cross transition of different environments is the same the number of samples from cross transition of the same environment For the online setting, we simply sample 1000 (k 1) k samples for each (i, i) cross transition ensure that the total number of samples is the same for G- REPTRANSSER and D-REETRANSFER.
To sample the initial state action pair (i.c., (3, â) pair as in (l)), for 90% of the samples, we follow the final policy from each source environment trained using BRIEF, For the remaining 10%, we follow the same policy state 8, and then take uniform random policy to get å. With this sampling scheme we ensure that Assumption 3.3 is satisfied. In the setting of Section. 6, we follow a more simple procedure to ensure that the samples are more balanced among the three states: we skip the first sampling step from environment é (i.e., sample given (š, a)), and simply reset environment i to s, where is one of the three states with equal probability, and generate the observation accordingly. Note that such visitation distribution is also possible in the online setting with a more nuanced sampling procedure, and in the experiment use the same sampling procedure for both G-REPTRA TREPTRANSSER and O-REPTR ANSFER for a fair comparison.
J.5 HYPERPARAMETERS
In this section, we record the hyperparameters we try and the final hyperparameter we use for each baselines. The hyperparameters for REPTRANSFER in Section. 6 is in Table. 3. The hyperparameters for REPTRANSFER in Section. is in Table. 4. The hyperparameters for BRIEE in Table. 5. We use the same hyperparameters for G-REPTRANSFED and O-REPTRANSFER.
41

---

Under review as a conference paper at ICLR 2023
Table Hyperparameters for REPTRANSFER in Comblock.
Value Considered
Final Value
Decoder learning rate Discriminator f learning rate Discriminator f hidden layer size RepLearn Iteration
[1e-2]
le-2
lc-2]
le-2
[256)
256
{30)
30
Decoder number of gradient steps Discriminator f number of gradient steps
[64)
64
(64)
64
Decoder é batch size
(256)
256
Discriminator f hatch size
(512)
512
RepLearn regularization coefficient
{0.01)
0,01
Decoder & softmax temperature
(1)
1
Decoder Φ softmax temperature
(0.1)
0.1
LSVI bonus coefficient
(1.
1
LSVI regularization coefficient À
{1)
1
Buffer size
[1e5}
le5
Update frequency Optimizer
(50)
50
(SGD)
SGD
Table 4: Hyperparameters for REPTRANSFER in Comblock-PO.
Value Considered
Final Value
Decoder ø learning rate Discriminator f learning rate Discriminator f hidden layer size Discriminator f hidden layer number RepLearn Iteration T Decoder o number gradient steps
[1e-2]
le-2
[le-2]
le-2
(256.512)
256
[2.3]
3
(30.40.50.100.150)
50
(64,80,128,255)
64
Discriminator number of gradient steps Decoder & batch size Discriminator f batch size
144,80,128,256
64
(256,512)
512
(256,512)
512
RepLearn regularization coefficient
{0.01)
0.01
Decoder softmax temperature
(1)
1
Decoder Φo softmax temperature
(0.1.1)
1
LSVI bonus coefficient /
(1,
1
LSVI regularization coefficient
(1)
1
Buffer size Update frequency Optimizer
(1e5)
1e5
(50)
50
(SGD, Adam]
Adam
J.6 VISUALIZATIONS
In this section we provide a comprehensive visualization of the decoders for all baselines in the target environment. We observe that the behaviors of all baselines similar across the 5 random seeds. Thus to avoid redundancy, we only show the visualization from random seed. We provide example in Fig. 3 how interpret the visualization: let the emission function of the target environment be o, and let the decoder that we are evaluating be Φ. and to generate the blue block in Fig. 3, we sample 30 observations {s.) = from the target environment 21.13, the latent state 1 (the title of the subplot) from timestep 13 (the x-axis). Concretely, { 130 o(. 21,1)). The blue block denotes the dirre-dimensional decoded latent states from these 30 observations:
30 > 1m ((sn).
42

---

Under review as a conference paper at ICLR 2023
Table 5: Hyperparameters for BRIEE in Comblock and Comblock-PO.
Value Considered
Final Value
Decoder & learning rate
[1e-2]
le-2
Discriminator learning rate Discriminator f hidden layer size RepLearn Iteration T
[le-2]
le-2
{256)
256
[30)
30
Decoder ø number of gradient steps Discriminator f number of gradient steps
{64)
64
[64]
64
Decoder Φ batch size
(512)
512
Discriminator f batch size RepLearn regularization coefficient À Decoder 6 softmax temperature
(512)
512
[0.01]
0.01
[1]
Decoder Φu softmax temperature
[0.1]
0.1
LSVI bonus coefficient B
LSVI regularization coefficient À
[1]
Buffer size Update frequency
[1e5)
le5
(50)
50
J.6.1 VISUALIZATIONS FROM SECTION.
We record the visualization of the 5 sources from Fig. 3 to Fig. 7; O-REPTRANSFER Fig.8; G-REPTRANSHE in Fig. running BRIEE target in Fig. 10.
state
state
state 2
1 4 1011
2223
Figure 3: Visualization of decoders from source 1. Note the collapse happens at timestep 5, and 17.
43

---

Under review as a conference paper at ICLR 2023
state
1011 12 14115
24
state
J0n des cae son cas son can cun Gon can uan
xoe con
oot
4
9 1011 13
14
16
18
19
20
222322222222
24
state
OM wwm coN
2 10111211111000 01111011111111111111111110222220
Figure 4: Visualization of decoders from source Note the collapse happens timestep I and 10. J.6.2 VISUALIZATIONS FROM SECTION.
We record the visualization of the sources from Fig. 11 and Fig. 12; O-REPTRANSFER in Fig. 13; G-REPTRANSFER in Fig. 14; running BRIEE on target in Fig. 15. Note that the features collapse some timesteps Fig. 14 and Fig. 15, but this acceptable because the optimal actions those timesteps are the same for the collapsed states.
44

---

Under review as a conference paper at ICLR 2023
state
1011 1213 2021
state 1
can eesocCa KOLESAN XX sox vat
state 2
Figure 5: Visualization of decoders from source 3. Note the collapse happens at timestep 14 and 15.
state
4
1011 13 16
20 2223
state 1
1011
state 2
1011 18112711112200 2223224
Figure 6: Visualization of decoders from source 4. Note the collapse happens at timestep 7, 16, 24.
45

---

Under review as a conference paper at ICLR 2023
state
4
1011 13 1415
2021
2223 24
state
1
con sow
state 2
Figure 7: Visualization of decoders from source 3. Note the collapse happens at timestep 13 and 16.
state
canciin
4
1011 13 15 16
18 20
22
state
1
1011 1213
state 2
1011 22232222444222
Figure 8: Visualization of decoders from O-REPTRANSEN
46

---

Under review as a conference paper at ICLR 2023
state
4
1011 12
2021 2223
state 1
state 2
Figure 9: Visualization of decoders from G-REPTRANSFER
state 0
4
2223 1011 12 14
18 20
state 1
1011
20
state 2
Figure 10: Visualization of decoders from running BRIEF on target.
47

---

Under review as a conference paper at ICLR 2023
state
1011
2021
state
state 2
Figure 11: Visualization of decoders from source environment 1.
state
10:11 12 14 16
20
2223
state 1
state 2
222324
Figure 12: Visualization of decoders from source environment 2.
48

---

Under review as a conference paper at ICLR 2023
state
1011 1215
state 1
state 2
2223244
Figure 13: Visualization of decoders from O-REPTRANSFER
state
1011 12 1415
1617 20
22
state
0
222322222222222222
state 2
1011 2021
2223
Figure 14: Visualization of decoders from G-REPTRAANSFE,
49

---

Under review as a conference paper at ICLR 2023
state
13
2021 2223
state
4
1011
182220211221 222324
state 2
1
4
1011 26111161111111222222222
Figure 15: Visualization of decoders running BRIEE in the target.
50


Reviews:
[{"review_id": "bbgFKdJC_hK", "reviewer": "Reviewer_F8xp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This work theoretically analyzes the applicability of feature/representation transfer from source tasks to a target task in RL, under the low-rank MDP setting (Def.3.1). It proposes an algorithm, RepTransfer (Algo.1), that learns the representations from cross-task samples, assuming one can sample from the transition kernel. It also shows that such cross-sampling is necessary (Thm.5.1) unless a stronger assumption is satisfied (Assumption 5.1). Experiments are conducted on the CombLock benchmark.", "summary_of_the_review": "This paper provides several theoretical results for representational transfer in RL. Such results are important, but the applicability of the algorithm is not very clear, especially due to the limited experiments.", "strength_and_weaknesses": "Strengths\n- Strong theoretical analysis\n- Clear writing\n\nWeaknesses\n- It remains unclear about the applicability of the results since one either has to sample from the transition kernel, or requires a stronger assumption. Both are not necessarily satisfied in many practical RL applications.\n- The experiments are only conducted on the CombLock benchmark, which is limited. Besides, the experiment results in Fig.2 are hard to parse because the description of the setup (even after reading some of the appendices) is not clear enough.\n\nTypo: In the “special case” after Assumption 3.4, there shouldn’t be summing over k for alphas and the sum for p_k should be over k instead of p.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UPK3cbrlRd", "reviewer": "Reviewer_WTGs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies provably efficient representation transfer in Low-rank MDPs, where multiple source tasks are used to train a shared representation based on which a good policy in the target task is expected to learn efficiently. Different from prior works, this work proposes a new theoretical scenario based on an (arguably more relaxed) assumption on relatedness. In this scenario, this work proposes a novel approach, called REPTRANSFER, consisting of 1) a modular reward-free exploration method for the policies in source tasks that satisfy feature reachability, 2) MLE-based representation pre-training with cross sampling, and 3) representation transfer and policy learning in target task. The sample complexity of the proposed approach with generative access to source tasks or with only online access to source tasks are presented. The theoretical results mainly show the sample complexity is close to knowing the ground truth representation in the target task with the generative access while efficient representation transfer is impossible with only online access if no additional stronger assumption is used. The proposed approach is empirical evaluated in COMBLOCK benchmark, demonstrating the supriority of REPTRANSFER and supporting the theoretical results.", "summary_of_the_review": "According to my detailed review above, I think this paper is above the acceptance threshold mainly due to the novel contribution made in theory and the high-quality presentation of the paper. Since I am not an expert in low-rank MDP theory, I make a conservative rating of 6 (marginally above the acceptance threshold).", "strength_and_weaknesses": "$\\textbf{Strengths:}$\n+ The paper is well written and organized. . The assumptions along with the limitations are well discussed. Although I am not an expert in low-rank MDP, the paper is still easy to follow.\n+ The new theoretical scenario (i.e., Assumption 3.3 and 3.4) makes sense to me (although being kind of limited, I think it is a reasonable choice). The sample complexity under both access settings are discussed in an organized order. The proposed approach is clear and neat to me.\n+ The related work and background are well enclosed and connected in the text.\n+ The experiments connect to and support the theoretical results well.\n\n&nbsp;\n\n$\\textbf{Weaknesses (and Questions): }$\n\n\nWhat if we consider a variant of REPTRANSFER that still has the generative access but does not do cross sampling? Does this variant degenerate to the online access case in the pratical implementation? If not, maybe taking this variant as an additional baseline helps the presentation of the experiments.\n\n&nbsp;\n\nAfter introducing Assumption 4.1, the authors metion ‘Prior works …. or directly assume access to a diverse state-action distribution which provides coverage and from which one can sample’. I am wondering why such a prior assumption is considered to be (maybe) stronger than the generative access.\n\n\n&nbsp;\n\n\nFor maybe a minor one, at the bottom of page 6, should it be ‘This ensures good exploration … in $P^{\\star}_{k}$’ (rather than $K$)?\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DtyO0Ku5Ui", "reviewer": "Reviewer_1Nh3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This work considers the question of learning shared representations in low-rank MDPs, so as to permit transfer between tasks. It considers the problem of transfer with access to a generative model for the source tasks, and the online case separately.\nContributions: exploit RepLearn (Agarwal 2020) for transfer, provide regret bounds for separate parts of the algorithm (representation learning, SxA coverage, etc.).", "summary_of_the_review": "Overall, this seems to be very solid work on deriving interesting bounds for re-using RepLearn in the context of low-rank feature transfer, with a limited experimental validation. But there is no take-away message for the reader and the paper is unreadable without the appendix. To me, that alone is a motive for rejection. I hope the detailed review will clarify this motivation.\n\nBesides this, despite the interesting contents and the (apparent) correctness of the points developed, I question the impact this will have on the community. I think this paper needs profound restructuring to make it valuable to the reader and encourage the authors to make this effort for the community. Thus, as is, this paper is not suited for publication.", "strength_and_weaknesses": "### Strengths\nInformative (although impossible to check in detail) bounds on the behaviour of the RepLearn and RepTransfer procedures which (seems to) permit principled transfer (exemplified on a limited example).\n\n### Weaknesses\nDisclaimer: my reviewing policy is always to try to find reasons to accept a paper (and not reasons to reject it), and I strongly believe we, as a community, should lay a kind look upon papers. This \"weaknesses\" section is long and took me a really long time to write. I hope it helps the authors.\n\nMy main concern is that the paper does not stand on its own. There are repeated references to elements of the Appendix. And these elements are not supplementary material, they are necessary to lay an informed eye on the main text's contents. This makes this paper rather difficult to access and to read, despite efforts made in the presentation.\n\nExamples of references to the appendix: Algorithms 3 (RepLearn), 4 (Rep-UCB), 5 (RepTransfer), 6 (LSVI-UCB) are necessary to understand algorithms 1 and 2 or the related theorems from the main text, and they are all in the appendix. The short discussion on transfer in supervised learning (page 4) does not make sense without reading appendix C. \n\nMy point is that this should be a conference paper. Not a textbook. Even if all these algorithms are not new contributions per se, the authors cannot expect them to be common knowledge, even within the RL community. So such elements should be part of a background section in the main text, even if in a light form, so that the paper is readable and stand on its own feet without requiring to go back and forth to the 37 pages long appendix.\n\nFor the same reason (and because of the insanely short timespan left to ICLR reviewers to complete their reviews), I cannot guarantee a fair evaluation of the proofs and the theoretical statements. In particular, theorems 4.1 and 4.2 (and lemma 4.2) *seem* relevant but I cannot guarantee their soundness. Again: this is a conference paper, not a book.\n\nI think the paper is missing important references and the authors only focus on the niche recent contributions in block MDPs and low rank MDPs. An important trend of research which learns task specific representations, and transfers them downstream to new tasks are progressive neural networks (Rusu et al, 2017). Similarly, the authors quote a number of reward-free exploration schemes (which are somewhat independent of representation learning per se) but dismiss the reward-free representation learning literature which includes at least successor representations (Dayan, 1993; Barreto et al., 2017; and many many others) and successor measures (Blier et al., 2021; Touati & Ollivier, 2021). Even if the paper considers transfer between different transition models, this literature is lacking in Sections 1 and 2 and this should be corrected, in particular given the strong connection with low-rank MDPs. Again, I am surprised to see no references to bisimulation metrics of MDP similarity metrics (e.g. Lecarpentier et al, 2021) when the authors talk about MDP similarity. Unfortunately, this confirms the impression that this paper is \"low-rank mdp theoreticians talking to only a very few other low-rank mdp theoreticians\" and does not consider the broader field of tranfer in RL (which is an effort other papers make). If that is the case, then this paper should go to a specialized workshop or journal or seminar on the topic (and this should be perfectly acceptable). Otherwise, it needs better foundations, motivation and connexions to work outside the comfort zone of the authors.  \nRusu, A. A., Rabinowitz, N. C., Desjardins, G., Soyer, H., Kirkpatrick, J., Kavukcuoglu, K., ... & Hadsell, R. (2016). Progressive neural networks. NeurIPS deep learning symposium.  \nDayan, P. (1993). Improving generalization for temporal difference learning: The successor representation. Neural computation, 5(4), 613-624.  \nBarreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., van Hasselt, H. P., & Silver, D. (2017). Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30.  \nBlier, L., Tallec, C., & Ollivier, Y. (2021). Learning successor states and goal-dependent values: A mathematical viewpoint. arXiv preprint arXiv:2101.07123.  \nTouati, A., & Ollivier, Y. (2021). Learning one representation to optimize all rewards. Advances in Neural Information Processing Systems, 34, 13-23.  \nLecarpentier, E., Abel, D., Asadi, K., Jinnai, Y., Rachelson, E., & Littman, M. L. (2021, May). Lipschitz lifelong reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 9, pp. 8270-8278).\n\nThe motivation for the cross-sampling part (section 4) is very unclear. Although, after dedicating a long time to understanding it, cross sampling with two successive transitions appears like a reasonable way to feed RepLearn (which is not a contribution from this paper since it is already the work of Agarwal (2020)). But really, the rationale behind this practice is unclear unless one (again) refers to the appendix and looks at the proofs. Not a single line on the topic in the paper: this strongly reduces the value for readers.\n\nConcerning the reward-free exploration part (section 4.1), LSVI-UCB seems a reasonable basis but it is not developped in the paper. Nor is its connection to recent work on reward-free exploration. E.g.:  \nKaufmann, E., Ménard, P., Domingues, O. D., Jonsson, A., Leurent, E., & Valko, M. (2021, March). Adaptive reward-free exploration. In Algorithmic Learning Theory (pp. 865-891). PMLR.  \nMénard, P., Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., & Valko, M. (2021, July). Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning (pp. 7599-7608). PMLR.  \nBadia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., ... & Blundell, C. (2020). Never give up: Learning directed exploration strategies. ICLR 2020.  \nDomingues, O. D., Tallec, C., Munos, R., & Valko, M. (2021, June). Density-Based Bonuses on Learned Representations for Reward-Free Exploration in Deep Reinforcement Learning. In ICML 2021 Workshop on Unsupervised Reinforcement Learning.  \nSo overall, besides the \"hey, this is an interesting setup upon which we can derive regret bounds\" side, this looks like an odd assembly of good ideas, without discussion on the rationale and I question what will remain of this paper in a few years (and this is in no way a negative judgment on the work done, i'm really questioning the impact this presentation will have).\n\nThere is a subsection numbered 4.1 but no 4.2. This is very odd and does not help structuring the paper. Either make it a separate section, or introduce a 4.1 at the beginning of section 4.\n\nIn theorem 5.1, what is the \"set of K-task multi-set\"?  \nIn theorem 5.1, the algorithm $\\mathcal{A}$ is said to interact with the source tasks, but the word \"online\" is never mentioned. As far as I understand, this theorem is specific to online interaction (it's the very motivation for this theorem), so this should be made explicit, otherwise the statement make no sense (interaction with the source tasks could use a generative model as in section 4).\n\nTheorem 5.2 directly refers (again) to algorithm 5 which is on page 28. No more comments on that.\n\nThere is no conclusion! Again: conference are not a patent registration desk for some new theorems. Papers should be reasonably accessible and feature hindsight views, perspectives, thoughtful discussion which leaves the reader bubbling with ideas and inspiration. It is not the case here. And although the work is of great quality, I strongly question its relevance for the reader.\n\nTypos and phrasing:  \nAbstract: weird sentence \"The sample complexity is close to knowing the ground truth features in the target task\". Close to that of learning the representations when knowing...?  \npage 3, \"transitions s_{h+1}\", the \"to\" is missing.  \npage 3, \\phi^* should be \\phi^\\star.  \npage 3, \"Assumption 3.2 is standard realizability condition\". is a standard   \npage 4, assumption 3.3 does not need the \"with \\alpha_{max}=...\" part. Please make it separate, it's confusing otherwise.  \npage 7, extra space after \"somewhat surprisingly\".  \npage 8, which results the failures -> which results in failure\n\nNotation:  \nP^\\star_h is the transition model at step k, while P^\\star_k is the full sequence of time-dependent transition kernels for task k. This is confusing. Why the \\star everywhere?   \nUsing \\Upsilon for the set of \\mu functions is confusing. Why not just M?   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject