On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness
Authors: Haotian Ye
Xiaoyu Chen
Liwei Wang
Simon Shaolei Du
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Generalization
Learning Theory

Abstract: Generalization in Reinforcement Learning (RL) aims to train an agent during training that generalizes to the target environment. In this work, we first point out that RL generalization is fundamentally different from the generalization in supervised learning, and fine-tuning on the target environment is necessary for good test performance. Therefore, we seek to answer the following question: how much can we expect pre-training over training environments to be helpful for efficient and effective fine-tuning? On one hand, we give a surprising result showing that asymptotically, the improvement from pre-training is at most a constant factor. On the other hand, we show that pre-training can be indeed helpful in the non-asymptotic regime by designing a policy collection-elimination (PCE) algorithm and proving a distribution-dependent regret bound that is independent of the state-action space. We hope our theoretical results can provide insight towards understanding pre-training and generalization in RL.

Under review as a conference paper at ICLR 2023
ON THE POWER OF PRE-TRAINING FOR GENERALIZA- TION IN RL: PROVABLE BENEFITS AND HARDNESS
Anonymous authors Paper under double-blind review
ABSTRACT
Generalization in Reinforcement Learning (RL) aims to train an agent during training that generalizes to the target environment. In this work, we first point out that RL generalization is fundamentally different from the generalization in supervised learning, and fine-tuning on the target environment is necessary for good test performance. Therefore, seek to answer the following question: how much can we expect pre-training over training environments to be helpful for effi- cient and effective fine-tuning? On one hand, we give surprising result showing that asymptotically. the improvement from pre-training is at most a constant fac- tor. On the other hand, show that pre-training can be indeed helpful in the non-asymptotic regime by designing a policy collection-eliminatio (PCE) algo- rithm and proving distribution-dependeee state-action space. We hope our theoretical results can provide insight towards understanding pre-training and generalization in RL.
regret bound that is independent of the
INTRODUCTION
Reinforcement learning (RL) is concerned with sequential decision making problems in which the agent interacts with the enviromment aiming to maximize its cumulative reward. This framework
has achieved tremendous successes in various fields such as game playing (Mnih al. 2013 Sil-
ver et al. 20177 Vinyals et al.] 2019), resource management (Mao et al. 2016). recommendation systems (Shani et al. 2005] [ho5]Z Zheng al. 2018) and online advertising (Cai et al.) 2017). However, many empirical applications of RL algorithms are typically restricted to the single environment set- ting. That is, the RI. policy is learned and evaluated in the exactly same environment. This learning paradigm can lead to the issue of overfitting in RI. (Sutton, 1995 Farebrother et al. (018)) and may have degenerate performance when the agent is deployed to an unseen (but similar) environment.
The ability to generalize to test environments is important to the success of reinforcement learning algorithms, especially in the real applications such as autonomous driving (Shalev-Shwartz et al,, 2016 Sallab et al. 2017). robotics (Kober et al. [2013] Kormushev al. 2013) and health care (Yu et al. 2021). In these real-world tasks, the environment can be dynamic, open-ended and always changing. We hope the agent can learn meaningful skills in the training stage and be robust to the variation during the test stage. Furthermore, in applications such as robotics where we have simulator efficiently and safely generate unlimited data, can firstly train the agent in the randomized simulator models and then generalize it to the real environment (Rusu et al., 2017 Peng al. 2018 Andrychowicz al. 2020). An RL algorithm with good generalization ability can greatly reduce the demand of real-world data and improve test-time performance.
Generalization in supervised learning has been widely studied for decades (Mitchell et 1986 Bousquet & Elisseeff 2002 Kawaguchi et al.) 2017). For a typical supervised learning task such as classification, given a hypothesis space H and loss function f, the agent aims to find an optimal solution in the average manner. That is, we hope the solution is near-optimal compared with the optimal hypothesis ht" in expectation over the data distribution, which formally defined as h²* arg min New n. EE [E(()(X), Y)) From this perspective, generalization in RL is fundamentally different. Once the agent is deployed in the test environment M sampled from distribution D. it is expected to achieve comparable performance with the optimal policy in M. In other words, we hope the learned policy can perform optrmal compared with the optimal value VM in instance for the sampled test environment M.

---

Under review as a conference paper at ICLR 2023
Unfortunately, discussed in many previous works (Malik al. 2021 Ghosh et al. 2021). the instance-optimal solution in the target environment can be statistically intractable without additional assumptions. We formulate this intractability into a lower bound (Proposition[] to show that it is im- practical to directly obtain a near-optimal policy for the test environment MM with high probability. This motivates to ask: in what settings can the generalization problem in RI. be tractable?
Targeting on RL generalization, the agent often allowed to further interact with the test environ- ment to improve its policy. For example, many previous results in roboties have demonstrated that fine-tuning in the test environment can greatly improve the test performance for sim-to-real trans- fer (Rusu al., 2017 James al., 2019 Rajeswaran et al. 2016). Therefore, one possible way to formulate generalization is to allow further interaction with the target environment during the test stage. Specifically, suppose the agent interacts with MDP M DD the test stage, and we mea- sure the performance of the fine-tuning algorithm A using the expected regret in K episodes, i.e. ( (MM)
Regx (D, = EM-D
VM J. In this setting, can the information obtained from pre-training hhelp reduce the regret suffered during the test stage?
Σ (VM
In addition, when the test-time fine-tuning is not allowed, what can we expect the pre-training to be helpful? As discussed above, we can no longer demand instance-optimality in this setting, but can only step back and pursue a near-optimal policy expectation. Specifically, our goal is to perform near-optimal in terms of the optimal policy with maximum value in expectation, i.e. π (DD arg m EM-DV VM- Here VM the value function of the policy ι in MDP M. We seek to answer: is it possible to design a sample-efficient training algorithm that returns a e-optimal policy V.
t in expectation, i.e. EM-n
VM <?
Main contributions. In this paper, we theoretically study RL generalization in the above two set- tings. Our contributions can be summarized as follows:
When fine-tuning is allowed, we study the benefit of pre-training for the test-time performance. Since all information we can gain from training is no more than the distribution D itself, we start with a somewhat surprising theorem showing the limitation of this benefit: there exists hard cases where, even if the agent has exactly learned the environment distribution D in the training stage, it cannor improve the test-time regret up to a universal factor in the asymptotic setting (K + oc). In other words, knowing the distribution D' cannot provide more information in consideration of the regret asymptotically. Our theorem proved by using Radon transform and Lebesgue integral analysis to give global level information limit, which we believe are novel techniques for RL communities.
Inspired by this lower bound, we focus on the non-asymptotic setting, and study whether and how much we can reduce the regret in this case. We propose an efficient pre-training and test-time fine- tuning algorithm called PCE (Policy Dollection-Eliminttio
By maintaining minimum policy set that generalizes well, achieves a regret upper bound Ô ( (VC(D)K in the test stage, where C(D))
is complexity measure of the distribution ID. This bound removes the polynomial dependence on the cardinality of state-action space by leveraging the information obtained from pre-training. We give fine-grained analysis the value of C(I)) and show that our bound can be significantly smaller than actennction space dependent bound in many settings.
When the agent cannot interact with the test environment, we propose an efficient algorithm called OMERM (Optimistic Model-based Empirical Risk Minimization) to find a near-optimal policy in expectation. This algorithm is guaranteed return e-optimal policy with O (log (NZ) /²²) c/(12 is the complexity of the policy class. This rate matches the traditional generalization rate in many supervised learning results (Mohri et al. 2018 Kawaguchi et al. 2017).
sampled MDP tasks in the training stage where AT
2 RELATED WORKS
Generalization and Multi-task RL. Many empirical works study how to improve generalization
for deep RL algorithms (Packer al. 2018 Zhang et al. 2020 Ghosh et al. 202T). We refer readers
We call the training stage "pre-training" when interactions with the test environment are allowed.
2

---

Under review as a conference paper at ICLR 2023
to recent survey Kirk et al. (2021) for more discussion empirical results. Our paper is more closely related to the recent works towards understanding RL generalization from the theoretical perspective Wang al. (2019) focused
special class of reparameterrizalle RL problems, and derive generalization bounds based on Rademacher complexity and the PAC-Bayes bound. [Mlik] et al. (202T); Duan et al. (20T) also provided lower bounds showing that instance-optimal solution is statistically difficult for RL generalization when we cannot access the sampled test environment. Further, they proposed efficient algorithms which is guaranteed to return a near-optimal policy for deterministic MDPs under the strong proximity condition they introduced. Our paper is also re- lated to recent works studying multi-task learning in RL (Tirinzoni et al., 2020 Hu et al., [02T]] Zhang & Wang, 2021: Lu et al. (02I), in which they studied how to transfer the knowledge learned
from previous tasks to new tasks. Their problem formulation different from ours since they study the multi-task setting where the MDP is selected from given MDP set without probability mech- & Li 2013). In addition, they typically assume that all the tasks have similar transition dynamics or share common representations.
Provably Efficient Exploration in RL. Recent years have witnessed many theoretical results study- ing provably efficient exploration in RL (Osband et al. 22013] / Azar et al. 2017,Osband Osband & Van Roy 2017 Din et al.] 2018 20206] Wang et al. 2020 Zhang et al., 2021) with the minimax regret for tabular MDPs with non-stationary transition being ((v AK). These results indicate that poly- nomial dependence on the whole actt-actionn space is unavoidable without additional assumptions. Their formulation corresponds to the single-task setting where the agent only interacts with a single environment aiming maximize its cumulative rewards without pre-training. The regret defined in the fine-tuning setting coincides with the concept of Bayesian regret in the previous literature (Os- band et al., 2013 Osband & Van Roy 2017 O DDnoghuee 202I). The best-known Bayesian regret for tabular RL O(y SLVHSAN AK) when applied to our setting (O OO'Dnnoghue 2021
PRELIMINARY AND FRAMEWORK
Notations Throughout the paper, we use [N] to denote the set {1. N where N E N.. For an event &, let T[Σ be the indicator function of event &, i.e [[E] = 1 if and only & is true. For any domain 22 we use C(2) to denote the continuous function on Ω. We use (-)) to denote the standard big O notation, and (-) to denote the big O notation with log(-) term omitted.
3.1 EPISODIC MDPs
An episodic MDP M is specified as a tuple (S, IP M, RM,H), H). where S, A are the state and action space with cardinality S and A respectively, and H is the steps in one episode. PMM S x A + ASS) is the transition such that (s'I a) denotes the probability to transit to state if action is taken in state in step h. R.M, S x A + A(R) is the reward function such that RM, a) is the distribution of reward with non-negative mean T & (8, , a) when action a is taken in state at step h. In order compare with traditional generalization, we make the following assumption:
Assumption 1. The lotal mean reward is bounded by 1, iee. VM Ω E I (8),))) S 1 for all trajectory (81,01,- 01. ,8H aH) with positive probability in M; The reward mechanism RMMss, a) is 1-subgaussian, i.e. Ex [exp(A[X (M, a))] S exp x²
2/ for all X E R.
The total reward assumption follows the previous works on horizon-free RL (Ren et al. 2021 Zhang et al. 2021 Li et al.) (2022) and covers the traditional setting where (MM a) E [0. by scaling H, and it is more natural in environments with sparse rewards (Vecerik et al., 2017 Riedmiller let al. 2018). In addition, it allows us to compare with supervised learning bound where // =T and the loss bounded by [0, 1]. The subgaussian assumption more common in practice and is widely used in bandits (Lattimore & Szepesvári, 2020). It also covers traditional RL setting where RM,a(s,)) a)) E ([0 and allows us to study MDP environment with a wider range. For the convenience of explanation,
assume the agent always starts from the same state 81- It is straightforward to recover the initial state distribution j from this setting by adding an initial state
so with transition μ (Du al. 2019 Chen et al., 2021).
Policy and Value Function. A policy л is set of H functions where each maps a state to an action distribution, i.e. = {m) [m:) Th S A(A) and can be stochastic. We de-
3

---

Under review as a conference paper at ICLR 2023
note the set of all policies described above II. We define A the e-covering number of the policy space w.n.. distance d(π' x²²) = max,es, [E(M] (+|s) - --(ss])]l Given and h E [H), we define the Q-function Uu.n : S A + R4, where Qm,n(s, and the V-function VM. :S + R+, where (8) = (-lan QM, (8, a) for I H and (1. = O. We abbreviate 1 (81) as Vi which can be interpreted as the value when executing policy π in M. Following the notations in previous works, we use PA V (s, a)) as the shorthand of Es's Ps a)) in our analysis.
(s, + EV'S (M M.
3.2 RL GENERALIZATION FORMULATION
We mainly study the setting where all MDP instances we face in training and testing stages are L.d. sampled from distribution ID supported on (possibly infinite) countable set Q2 For an MDP M E Ω we use P(M) to denote the probability of sampling M according to distribution DD. For an MDP set Ω C S2 we similarly define P( = Eme P(M). We assume that A, H is shared by all MDPs, while the transition and reward are different. When interacting with sampled instance M, one does not know which instance it is, but can only identify its model through interactions.
In the training (pre-training) stage, the agent can sample i.i.d. MDP instances from the unknown distribution D. The overall goal is to perform well in the test stage with the information learned in the training stage. Define the optimal policy as
(MM arg max VM, n (D) arg max EM VM-
xell
Tell
We say policy a is e-optimal in expectation, if EM-D [ [M - e-optimal in instance, if BMAD VM (M)
VV S e. We say a policy π is
(M VM S.
Without Test-time Interaction. When the interaction with the test environment is unavailable, optimality in instance can be statistically intractable, and we can only pursue optimality expecta- tion. We formulate this difficulty into the following proposition.
Proposition 1. There exists an MDP support Ω such that for any distribution D with positive p.d.f. p(r), Reo and for any deployed policy t,
EM (M²) VM- co.
Proposition D is proved by constructing Ω as set of MDPs with opposed optimal action, and the complete proof can be found in Appendix A When Ω is discrete, there exists hard instances where the proposition holds for co 2 1. This implies that without test-time interactions special knowl- edge on the structure of f2 and 1b, it is impractical to be near optimal in instance. This intractability arises from the demand on instance optimal policy, which is never asked in supervised learning.
With Test-time Interaction. To pursue the optimality in instance, we study the problem of RL generalization with test-time interaction. When our algorithm is allowed to interact with the target MDP MM ~ DD for K episodes in the test stage, we want to reduce the regret, which is defined as
Regæ (D. EMTND Regx (M", A), RM A) & V (M')
M
V
where Fe is the policy that A deploys in episode k. Here M is unknown and unchanged during all K episodes. The choice of Bayesian regret is more natural in generalization, and can better evaluate the performance of an algorithm in practice. From the standard Regret-to-PAS technique (Jin al.) 2018 Dann al. (017),, an algorithm with Ö(VK) regret can be transformed to an algorithm that returns an e-optimal policy with ((1/22) trajectories. Therefore, we believe regret can also be good criterion to measure the sample efficiency of fine-tuning algorithms in the test stage.
4 RESULTS FOR THE SETTING WITH TEST-TIME INTERACTION
In this section, we study the setting where the agent is allowed to interact with the sampled test MDP M When there is pre-training stage, the typical regret bound in the test stage is
4

---

Under review as a conference paper at ICLR 2023
(AYSSHHK)ZZaang et al. 2021). For generalization in RL, we mainly care about the performance in the test stage, and hope the agent can reduce test regret by leveraging the information learned in the pre-training stage. Obviously, when Ω is the set of all tabular MDPs and the distribution ID is uniform over Ω, pre-training can do nothing on improving the test regret, since it provides no seek distribution-dependenn improvement that
extra information for the test stage. Therefore, is better than traditional upper bound in most of benign settings.
4.1 LOWER BOUND
We start by understanding how much information the pre-training stage can provide at most. One natural focus is on the MDP distribution TD, which is sufficient statistic of the possible environment that the agent will encounter the test stage. We strengthen the algorithm by directly telling it the accurate distribution D3 and analyze how much this extra information can help to improve the regret. Specifically, we ask: Is there a multiplied factor C(D) that small when ID enjoys some benign properties (e.g. D is sharp and concentrated), such that when knowing D, there exists algorithm that can reduce the regret by a factor of C(D for large enough K?
Perhaps surprisingly. our answer towards this question is negative for all large enough K in the asymptotic case. As formulated in Theeore [ the importance of is constrained by a universal factor oo asymptotically. Here co implies that no matter what distribution ID is, for sufficiently large K, any algorithm can only reduce the total regret by at most a constant factor with the extra knowledge of D.
holds universally and does not depend on ID. This theorem
Theorem 1. There exists an MDP instance set Q, a universal constant co To and an algorithm Á that only inputs the episode K, such that for any distribution ID with positive p.d.f. p(r) E C()) (which Å does NOT know), any algorithm A that inputs D and the episode K,
1. Q is not degraded, i.e. lim Regx (I, A(D, t00.
2. Knowing the distribution is useless up to a constant, i.e.
Regx ATD, K)) 2 Co-
lim inf K K
Regx (D), A(K))
In Theorem Point (1) avoids any trivial support Q where 3 that is optimal for all M Ω, in which case the distribution is of course useless since Á can be optimal by simply following n" even it does not know D. Note that our bounds hold for any distribution D. which indicates that even very sharp distribution cannot provide useful information in the asymptotic case where K + co. We point out that the value of co depends on the coefficient of previous upper and lower bound, and we conjecture that it could be arbitrarily close to 1.
We defer the complete proof to Appendix B and briefly sketch the intuition here. The key ob- servation is that the information provided in the training stage (prior) is fixed, while the required information gradually increase as K increases. When K = 1, the agent knowledge of DD. Without this knowledge, all it can do is a random guess since it has never interacted with M before. However, when K is large, the algorithm can interact with M many times and learn M more accurately, while the prior ID will become relatively less informative. As a result, the benefits of knowing D vanishes eventually.
clearly benefit from the
Theorem I lower bounds the improvement of regret by constant. As is commonly known, the regret bound can be converted into a PAC-RL bound (Jin et al.) 2018 Dann al. 2017). This implies that when 6 0, in terms of pursuing e-optimal policy to π (M*), pre-trainigg cannot help reduce the sample complexity. Despite negative, we point out that this theorem only describe the asymptotic setting where K + co, but it imposes constraint when K is fixed.
4.2 NON-ASYMPTOTIC UPPER BOUND
In the last subsection, we provide a lower bound showing that the information obtained from the training stage can be useless in the asymptotic setting where K + In practice, near-optimal regret in the asymptoiii setting is also desirable in many applications. In this section, we fix the value of K and seek to design an algorithm such that it can leverage the pre-training information
5

---

Under review as a conference paper at ICLR 2023
and reduce K- Keepisode test regret. To avoid redundant explanation for single MDP learning, formulate the following oracles.
Definition 1. (Policy learning oracle) We define (M, (og()))) as the policy learning oracle which can return policy that is e-optimal w.t.. MDP M with probability at least 1 6, i.e. V S... 6. The randomness of the policy n due to the randomness of both the oracle algorithm and the environment.
Definition 2. (Policy evaluation oracle) We define C,(M, T,, (log(1/))) as the policy evaluation oracle which can return value v that is e-close to the value function (s) with probability at least 1 - 6, i.e. |V VV-VMM (s1)) S 6. The randomness of the value v is due to the randomness of both the oracle algorithm and the environment.
Both oracles can be efficiently implemented using the previous algorithms for single-task MDPs. Specifically, we can implement the policy learning oracle using algorithms such as UCBVI (Azar al. 2017). LSVI-UCB (Jin et al. 2020b) and GOLF (Jin et al. 2021) with polynomial sam- ple complexities, and the policy evaluation oracle can be achieved by the standard Monte Carlo method (Sutton & Barto 2018).
4.2.1 ALGORITHM
There are two major difficulties in designing the algorithm. First, what do we want to learn during the pre-training process and how to learn it? One idea to directly learn the whole distribution D, which is all that we can obtain for the test stage. However, this requires O([S2//88 samples for required accuracy 8, and is unacceptable when [S2] is large even infinite. Second, how to design the test-stage algorithm to leverage the learned information effectively? If we cannot effectively the information from the pre- pre-training, the regret samples required in the test stage can be (poly(SS, A)) in the worst
Algorithm PCE (Policy Collection-Ellne Elimination)
Pre-training Stage
Input: episode number K, policy learning oracle O2 and policy evaluation oracle 0g
2: Initialize: å e 1/ //V K, the number of the sampled MDPs N log((1))/82
3: for phase = 1, ... do
4: Sample MDP set Ω with N MDPs (M1, ,Mx) from distribution ID
5: for jo N do
6: Calculate π, e/2
for the MDP M,
7:
for 1, .N
8:
Calculate U4 0g (M,, my e/2, log, /6)) to evaluate the policy тr the MDP M, Call Subroutine to find a set il that covers (1 36)-fraction the MDPs ②
9:
iu 1og(2N/6) N-11
10:
if
< then
11:
Output: the palicy-value set = [TTY, Uy,)), Vj u Double the number of the sampled MDP, i.e. N 2N
Test Stage
1: Input: the valicy-value set from the Pre-train Stage, Episode number K
2: Initialize: the MDP set i IT, the phase counter / = 1, ko 1, -- 1/VK
3: for episode 1, 1.................... K do
4: Calculate (T,, v1) = arg (x,,)n i
5: Execute the optimal policy Tı, and receive the total reward G
6: if
W - Σ Et G5 ty
> 4e
/ -1
(2log(4K/8) then
7: Eliminate (T,, v7) from the instance set II, denote the remaining set as 7441
8: Set kn = k 1, and
To tackle the above difficulties, we formulate this problem as a policy candidate collection- elimination process. Our intuition is find minimum policy set that generalize most

---

Under review as a conference paper at ICLR 2023
MDPs sampled from D. In the pre-training stage, maintain a policy set that can perform well on most MDP instances. This includes policies that are the near-optimal policy for an MDP M with relatively large P(M), that can work well different MDPs. In the test stage, we sequentially execute policies in this set. Once we realize that current policy is not near-optimal for M we eliminate it and switch to another. This helps reduce the regret from the cardinality of the whole state-action space to the size of policy covering set. The pseudo code is in Algorithm I
Pre-training Stage. In the pre-training stage, we say policy-value pair (T, v) that covers an MDP M if π is Oepttmml for the MDP M and v is an estimation of the optimal value V (81) with at most (ee) error. For policy-value set II, we say the policy set covers the distribution I' with
probability at least 1 - O()) if PIM-D [(TT,)) u) I1, (π,, v) covers M) 2 1 1 The basic
goal in the pre-training phase is find a policy-value set Ii with bounded cardinality that covers IB with high probability. The pre-trate tre-training stage contains several phases. In each phase, we sample N MDPs from the distribution ID and obtain an MDP set {M1,, M2, ,MN' }. We call the oracle Oj to calculate the near-optimal policy π for each MDP Mj, and we calculate the value estimation
Vijj for each policy my on MDP M, using oracle Op. We use the following condition to indicate whether the pair (Ty, U35) covers the MDP M₁:
(nd Ut (j3) = 11 [[vs,, val < <]]n[[lu - مدين c].
The above condition indicates that πy is a near-optimal policy for M, and Us is an accurate esti- mation of the value VM, (81). With this condition, we construct policy-value set I' that covers (1 -fr--fraction of the MDPs in the sampled MDP set by calling Subroutine 4 We output the
policy-value set once the distribution estimation error
[ log(2N/8) is less than 6, and double the N 12
number of the sampled MDPs N to increase the accuracy of the distribution estimation otherwise. After the pre-training phase, we can guarantee that the returned policy set can cover D with proba- bility at least i.).
Pr.-D
((T, v) ii, [M (81) Vü,1 (s1) 22 [Vū, (s1) 1/ 2e 2 1 0()).
Fine-tuning Stage. We start with the policy-value set Iî from the pre-training stage and eliminate that covers the test MDP M Specifically,
the policy-value pairs until we reach a (m,v) we split all episodes into different phases. In phase 1, we maintain a set πT, that covers the real environment M with high probability. We select (m,, v)) with the most optimistic value es in I1; and execute the policy मं for several episodes. During execution, we also evaluate the policy ni on the MDP M (i.c. (s1)) and maintain the empirical estimation k- E GR. Once we identify that गy not npar-optimal for M we end this phase and eliminate (MT, 01) from fl.
4.2.2 REGRET
The efficiency of Algorithm is summarized in Theorem 2 and the proof is in Appendix C
Theorem 2. The regret of Algorithm 7 is al most
Reg ADA.lg. 7 o (VC())log(()) + ((T)
where C(ID) A min [ a complexity measure of D and ô 1/VK. In addition, with probability at least (5 log(C(D))/8)) samples required in the pre-training stage is O C(D)
Different from the previous regret bound when the pre-training is unavailable (Azar et al. 2017 Osband et al.] 2013; Zhang et al. 202I), this distribution-depender complexity measure of D defined as C(D). C(-) serves as multiplied
upper bound improves the
dependence S, factor, and can be small when ID enjoys benign properties as shown below.
First, when the cardinality of Ω is small, i.. [Ω]] < SA we have C(D) [Ω] and the pre-training can greatly reduce the instance space via representation learning or multi-task learning (Agar- wal al. 2020 Brunskill & Li 2013). Specificallyy, the regret in the test stage is reduced from
7

---

Under review as a conference paper at ICLR 2023
Ö(VSAHK) to Ōl ()) To the best of our knowledge, this is the first result that achieves de- pendence only on for any general distribution in RL generalization. We provide a lower bound in Appendix to show that our regret in the test stage is near-optimal except for logarithmic factors.
When [92] is large or even infinite, C(D) is still bounded and can be significantly smaller when IB enjoys benign properties. In fact, in the worst case, it is not hard to find that the dependence C(ID) unavoidable and there is no way to expect any improvement. However, in practice where [S2] is large, the probability will typically be concentrated outside, e.g. when D is subgaussian or mixtures of subgaussian. Specifically, if the probability of the i-th MDP P: S cre for some positive constant C1, X, then C(D) I Olog }) which gives the
several subset region of S and decay quickly
(V (VKlog((K))
upper bound O
It is worthwhile to mention that our algorithm in the pre-training stage actually finds policy cov- ering set, rather than an MDP covering set, despite that the regret in Theorem 2 depends on the cardinality of the MDP covering set. This dependence can possibly be improved to the cardinality of the policy covering set by adding other assumptions to our policy learning oracle, which we leave as interesting problem for the future research.
RESULTS FOR THE SETTING WITHOUT TEST-TIME INTERACTION
In this section, we study the benefits of pre-training without test-time interaction. As illustrated by Proposition 1 we only pursue the optimality in expectation, which is in line with supervised learn- ing. Traditional Empirical Risk Minimization algorithm can be e-optimal with O 102 and we expect this to be true in RL generalization as well. However, a policy in RL needs to se- quentially interact with the environment, which is not captured by pure ERM algorithm. In addition, different MDPs in Ω can have distinct optimal actions, making it hard to determine which action is better even in expectation. To overcome these issues, we design an algorithm called OMERM in Algorithm? 2 Our algorithm is designed for tabular MDPs with finite state-actions space. Neverthe- less, it can be extended the non-tabular setting by combining
samples,
ideas with previous algorithms for efficient RL with function approximation (Jin et al. 2020a Wang et al. 2020).
In Algorithm 2 we first sample N tasks from the distribution D the input. The goal of this algorithm is to find a near-optimal policy in expectation w.r.t. the task set (M, M J. In each episode, the algorithm estimates each MDP instance using history trajectories, and calculates the optimistic value function of each instance. Based on this, it selects the policy from II that maximizes the average optimistic value, i.c. NV >' VM, ($1). This selection objective is inspired by ERM, with the difference that we require this estimation to be optimistic. It can be achieved by planning oracle when II is all stochastic maps from (S, H) to A(A), by gradient descent when II is a parameterized model. For each sampled M,, our algorithm needs to interact with it for poly(S, A, H, times, which is a typical requirement learn model well.
Theorem 3. With probability Fl at least 2/3, Algorithm 2 can output a policy & satisfying EM-~D VV Vūr] S with O log (og.A7.aaan
MDP instance samples during training. The
number of episodes collected for each task is bounded by O 1 Alg((SHH)
We defer the proof of Theorem 3 to Appendix [ This theorem implies that Algorithm 2 needs approximately Olog (N'l )/²²) samples to return an e-optimal policy in expectation. Recall that 12x
गि7 loT is the log-covering number of II. When IT is all stochastic maps from S, to ((A),
is bounded by Ó(HSA). When is parameterized model where the parameter E Rd has finite norm and Ty satisfies some smoothness condition on 0, log(A/I 12M S Ó().. This result
Consider the bandit case where there are M arms. The optimal distribution over M MDPs. C(DD = M in this case, and the M dependence is unavoidable this hard instance since the agent has to independently explore and test whether each arm the optimal arm. This probability can be further improved to 1 8 by executing Algorithm 2 for log(1 /5) times and then returning policy with maximum average value. Please Appendix D22 for the detailed discussion.
arm in Ms. and Di is uniform
8

---

Under review as a conference paper at ICLR 2023
Algorithm 2 OMERM (Optimistic Model-based Empirical Risk Minimization)
Input: target accuracy > 0
Input: the sampled N MDPs denoted as M2, [My} from distribution D, with N
C1 log (A (II, (12H1) d)) / for a constant C >
K = C2S 2 log( (OSSAH//)) /e) for constants C2
for episode l . do
5:
for i 1,2, 2,
Denote NM,,.n a, 8) and NM.AA,(s, a) as the counter that agent encounters (s, s') and (s, a) at step h in M, till step k respectively
Estimate (M
NM, N.,.R.
for step h [H]
max max(L.NM,,
Estimate (M
Σ. TM (AMM
for step h [H]
max max M,
Define the UCB bonus (M.R,b(s,.)
88 (K
max max AMM
10:
Initialize V KM (8, a) 00, Vs, for = H, H , do
QM min { RM,,,.(sss) bM. + (M.AA,) (s) E.
Calculate the optimistic policy nih arg max N Σ ( for 1,2, .N do Execute the policy TR MDP M, for one episode, and observe the trajectory (sM,kkh aM T,M,,,))
15:
Output: policy selected uniformly randomly from the policy set {T [T=]R=I-
matches traditional bounds in supervised learning, and it implies that when we pursue the optimal in expectation, generalization in RL enjoys quantitatively similar upper bound to supervised learning.
CONCLUSION AND FUTURE WORK
This work theoretically studies how much pre-training can improve test performance under different generalization settings. we first point out that RL generalization is fundamentally different from the generalization in supervised learning, and fine-tuning on the target environment is necessary for good generalization. When the agent can interact with the test environment to update the policy, we first prove that the prior information obtained in the pre-training stage can be theoretically useless in the asymptotic setting, and show that in non- asymptotic setting we can reduce the test-time regret to (VC())) by designing an efficient learning algorithm. addition, when the agent cannot interact with the test environment, provide efficient algorithm called OMERM which returns a netr-optimal policy in expectation by interacting with O (A (1(m2)))²²) MDP instances.
Our work seeks a comprehensive understanding on how much pre-training can be helpful to test performance theoretically, and it also provides insights on real RL generalization application. For example, when test time interactions are not allowed, one cannot guarantee to be near optimal in instance. Therefore, for task where large regret is not tolerable, instead of designing good algo- rithm, it is more important to find an environment that is close to the target environment and improve policies there, rather than to train policy in diverse set of MDPs and hope can generalize the target. In addition, for tasks where we can improve policies on the fly, we can try to pre-train our algorithm in advance to reduce the regret suffered. This corresponds to the many applications where test time interactions are very expensive, such autonomous driving and robotics.
There are still problems remaining open. Firstly, we mainly study the i.i.d. case where the training MDPs and test MDPs are sampled from the same distribution. It is interesting problem to study the dfitt--diitributtinn generalization in RL under certain distribution shifting. Secondly, there is still room for improving our instance dependent bound possibly by leveraging ideas from recent Bayesian-optimal algorithms such as Thompson sampling (Osband et al. 2013). We hope these problems be addressed in the future research.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning of low rank mdps. Advances neural information processing systems, 33:20095-2000 20107,, 2020.
OpenAI: Marcin Andrychowicz. Bowen Baker, Macick Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20, 2020.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. arXiv preprint arXiv:1309.688 2013.
Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo. Real- time bidding reinforcement learning in display advertising. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 661-670, 2017.
Xiaoyu Chen, Jiachen Hu, Lin F Yang, and Liwei Wang. Near-optimal reward-free frree exploration for linear mixture mdps with plug-in solver. arXiv preprint arXiv:21 2021.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
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, pp. 1665-1674. PMLR, 2019.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. International Conference on Machine Learning, pp. 2892-2902. PMLR, 2021.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and regularization in 2018.
dqn. arXiv preprint
Dibya Ghosh, Jad Rahme, Aviral Kumar, Amy Zhang, Ryan P Adams, and Sergey Levine. Why generalization in rl is difficult: Epistemic pomdps and implicit partial observability. Advances in Neural Information Processing Systems, 34, 2021.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learn- ing linear bandits and linear International Conference on Machine Learning, pp. 4349- 4358. PMLR, 2021.
Stephen James, Paul Wohlhart, Mrinal Kalakrishnan, Dmitry Kalashnikov, Alex Irpan, Julian Ibarz, Sergey Levine, Raia Hadsell, and Konstantinos Bousmalis. Sim-to-real via sim-to-sim: Data- efficient robotic grasping via coddomized-to-canonnee adaptation networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12627-12637, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi-
cient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 18530-18539, 2020a.
10

---

Under review as a conference paper at ICLR 2023
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR. 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418 2021.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint arXiv:
2017.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. survey of generalisation in deep reinforcement learning. arXiv preprint arXiv:21 2021.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcemeent learning in robotics: A survey, The International Journal of Robotics Research, 32(1 121112:128-1277, 2013.
Petar Kormushev, Sylvain Calinon, and Darwin G Caldwell. Reinforcement learning in robotics:
Applications and real-world challenges. Robotics, 2(3):122-148, 2013.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yuanzhi Li, Ruosong Wang, and Lin F Yang. Settligg the horizon-dependence of sample complexity in reinforcement learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 965-976. IEEE, 2022.
Rui Lu, Gao Huang, and Simon S Du. On the power of multitask representation learning in linear mdp. arXiv preprint arXiv:2106.08053, 2021.
Dhruv Malik, Yuanzhi Li, and Pradeep Ravikumar. When is generalizable reinforcement learning tractable? Advances in Neural Information Processing Systems, 34, 2021.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. In Proceedings of the 15th ACM workshop on hot topics in networks, pp. 50-56, 2016.
Tom M Mitchell, Richard M Keller, and Smadar T Kedar-Cabelli, Explanation-based generaizzatio:: A unifying view. Machine learning, 1(1):47-80, 1986.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Brendan O'Donoghue. Variational bayesian reinforcement learning with regret bounds. Advances in Neural Information Processing Systems, 34, 2021.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforce- ment learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Charles Packer, Katelyn Gao, Jernj Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song- Assessing generalization in deep reinforcement learning. arXiv preprint / 2018.
Xue Bin Peng, Marcin Andrychowicz. Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 20/8 IEEE international conference robotics and automation (ICRA), pp. 3803-3810. IEFE, 2018.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. arXiv preprint arXiv: 1610.01283, 2016.

---

Under review as a conference paper at ICLR 2023
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances in neural information processing systems, 34, 2021.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In International conference on machine learning, pp. 4344-4353. PMLR, 2018.
Andrei A Rusu, Matej Večerík, Thomas Rothörl, Nicolas Heess, Razvan Pascanu, and Raia Hadsell. Sim-to-real robot learning from pixels with progressive nets. In Conference on Robot Learning, pp. 262-270. PMLR, 2017.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19):70-6,,1 2017.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arxiv: 2016
Guy Shani, David Heckerman, Ronen Brafman, and Craig Boutilier. An mdp- base-baeed recommender system. Journal of Machine Learning Research, 6(9). 2005.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354335,, 2017.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. Advances in neural information processing systems, 8, 1995.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Andrea Tirinzoni, Riccardo Poiani, and Marcello Restelli. Sequential transfer in reinforcement learning with generative model. In International Conference on Machine Learning, pp. 9481 9492. PMLR, 2020.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nico- las Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstra- tions for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv:1707.08817 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-3544 2019.
Huan Wang, Stephan Zheng, Caiming Xiong, and Richard Socher. On the generalization gap in reparameterizable reinforcement learning. In International Conference on Machine Learning, pp- 6648-6658 PMLR, 2019.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the 11 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey, ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742, 2020.
Chicheng Zhang and Zhi Wang. Provably efficient multi-task reinforcement learning with model transfer. Advances in Neural Information Processing Systems, 34, 2021.
12

---

Under review as a conference paper at ICLR 2023
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp- PMLR, 2021.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. Drn: A deep reinforcement learning framework for news recommendation, In Pro- ceedings of the 2018 World Wide Web Conference, pp- 167-176, 2018.
A OMITTED PROOF FOR PROPOSITION 1
Assume Ω is the set of M MDP instances identical state $1 and their horizon otherwise. The optimal policy in M, is therefore taking action a and VMM (aa(M=)) = 1.
where all instances consist only one 1. In M; and state 81, the reward for action a, and
For any distribution ID, assume the probability to sample M₁ is pi 0. For any deployed policy #, assume the probability that स takes action ag is gt. then
M Σ
P.q. S max
iE[M]
Therefore, denote = 1 max > O, we have
EM (M')))) ViL 2 E0.
Notice that when D uniform distribution, 6n
M-1 which be arbitrarily close 1.
B OMITTED PROOF FOR THEOREM
To prove the theorem, we let Ω be a subset of MDP with H = S = 1, under which it becomes bandit problem, and it suffices prove the theorem in this setting. Below we first introduce the bandits notations, and give the complete proof.
B. NOTATIONS
To be consistent with traditional K-arm bandits problem, in this section notations from the main paper. An bandit instance can be represented as a vector r E Ω C [o, 1]* where тı is the mean reward when arm & is pulled. Inherited from previous MDP settings, assume that this reward is sampled from an 1-subgaussian distribution with mean rk- In each episode t [T') based on initial input and the history, an algorithm A chooses an amn a, to pull, and obtain a reward yo, ~ Da.. Similarly, assume is sampled from a distribution D supported on I, and we want minimize the Bayesian regret
slightly different
also
T
Regr (D, & ETED Regr(r, A), where Regr A) A E hr
ra.l
Here r" max Tk is the optimal arm. If we define ST (r. -t=1 Ila, k] the of how many times A has pulled arm & in episodes and A = px - Tk as the sub-optimal gap, we can decompose regret
Reg, (r, A)
Σ ANEIS Ar)
(1)
This identity is frequently used in the subsequent proof.
13

---

Under review as a conference paper at ICLR 2023
B.2 PROOF
We first specify the choice of support, constant and algorithm. Without loss of generality, we set ?= [0, 1]k which is quite common and general in bandit tasks. Let Co = 16 and A be the Asymp- On the other hand, let A be uniformly optimal, i.e. A(T), T) arg m Regr(D,, (D,, A). To prove the theorem, only need to show that
totically Optimal UCB Algorithm defined in Algorithm 3
Regr (D, ((D, T)) 2 CO:
in T-00
Reg- (D. ((T))
which is the major result (point (2)). Later, we show that limy- Regr (ID,, 7)) = +00 in Lemma 9 which proves point (1) in the theorem. When T is fixed, we abbreviate A(D, T), A.
Á enjoys well known instance dependent regret upper bound, which is copied below: Lemma (Theorem 8.1 in Lattimore & Szepesvári 2020 ). For all E Ω, vk E [K].
2 [[log(Tlog) + 1) + V log(T log" T + 1) + (Ax 8)²
EIST (r, A)] S mi, <E(0,Ax) (1+ 8²
inf
+
By Holder Inequality, we immediately have
A (r, A) s min(A,T, u(T) log
A },
where the coefficient function
(T) sup 12f logt t
[51/3 + (2log(t logg + + V log(tlog' t + 1) + 1)2/873
being non-increasing and lim u(T) = 2. For simplicity, we define e(T) & log T}. We can upper bound Regr(r, A) I DK
log
and
T-1
s(A, 7) A min(AT,A>
u(T)
kml s( ( T).
A
Decomposition of Inq. For [K], define 24 = (r e f: T- where po E (0, 2) is
a universal constant to be specified later. Further define A1 = fr E 22 41 < 1}. Using Eq. it suffices prove the lemma if vk E [K].
lim inf P(r) (r. A) T-2
(()) (r, A)jdr 2 co.
(3)
Fix & E [K] and c > 0 that is sufficiently small, we decompose Inq.
3 as below:
So p(r (r, A)jdr An (r, Arjrr
JaprIa p(r) (r. A)]dr
San nAz p(r)s(As, T)dr
Jay nAA p(r)s(As, T)dr
Soy p(r)s(Ax))))))) T)dr
Jny p(r)s(( T)dr ( T)
In ((r)sss(AR, T)dr
PAP(S) (r, (r,
Sequentially denote the four terms in the right hand side as M1 M4. M1 can be lower bounded by based on the Lemma 4 The rest three terms is bounded by the subsequent three lemmas.
Lemma S. Vk [K].
Joz p(r)s(( T)rr ((r)s((A.. T)dr 2 2po-
liminf
(4)
Lemma 5 lower bounds My, saying that the influence of instance in S2 \ 24 is negligible. The proof of this lemma needs theory on Lebesgue Integral and Radon Transform, which will be introduced in the Section B.3
14

---

Under review as a conference paper at ICLR 2023
Lemma 6. For any [ (0,1),
Sagn (Ar))(AA,))) Jaz. ((r)s(An.) T)dr
lim T-000
1.
Lemma 6 implies that M2 1, allowing us to focus the integral on calibrated smaller set 24 NAG. in which
use information theory to control E[s A)]- The following lemma the major lemma in proof, which the optimality of Á to analyze the global structure of (egr(r,A) A) for 22t n Ag. and lower bound term M1:
Lemma 7. For any E (0, 1). have
Jas p(r) (r. A)]rr 1 2po
inf
T0000
nA ((r)s(Ax.)))))))
(1 (1+
Combined together,
lim inf (r A)dr
2po( 2po Cep (1 E)²
(5)
In ((r) E|S7 (r, A)]rr
The proof of Inq. 2 is finished by selecting Po and letting 0.
Algorithm 3 A:: Asymptotically UCB
1: Input f = [0, 1)" total episode T .., K do
2: for step
3: Choose arm dt, and obtain reward
4: Set R; yt, S. = 1
5: for step = K + 1, . do
6:
f(t) + t log (t)
7: Choose
arg max
its
St
2log f(t) Sk
8: Set Rs = Rs + ye, S₁ = S₁
B.3 PROOF LEMMAS
Before proving all lemmas above, need to introduce theory Lebesgue Integral and Radon Transform. In K space where 2 when a function Riemann integrable, it is also Lebesgue integrable, and two integrals equal. Since assume p(r) C(S), the integral always exists. Below we always consider the Lebesgue integral. For a compact measurable set S, define (S(S) as the space of all measurable function in S with standard p-norm. Since the p.d.f of D is continuous in compact set Q and is positive, 3L, E R+, Vr E Ω. p(r) E U..
EkEIK] Jr, s(r)dr since m(T 0 T,) = 0, VT, * Tj. Here m(.) is the Lebesgue measure in R.K If we define Pt,y = {r E 2 r- 1) and % = (e: - ex), # k, then Pent nT= f T, A = t). According to Radon Transform theory, since T, is compact and p(r) E C(T))
Denote Te (r Ω Fk max(r)). Clearly, Sa f(r)dr
(1)) A I
p(r)dr,
JP nT.
is also continuous w.r.t variable t [0,1] for all & * siE E [K]. Here the integration is per- form in the corresponding 1 space, i.e. the plane Pengg and when mx mx-1(P.... (P TT)) > 0.
(9) mot (T)) E [T.
15

---

Under review as a conference paper at ICLR 2023
We further define (x) = Σisk P (t), which also belongs to C(JO, 1]). The continuity of qx(()
helps derive the following equation. For any f E (22) that relies only on A i.c. f(r) - f(Ar), we have
1 p(r))(()dr== (E[K]
/ p(r)f(r)dr
E
L, p(r)f(r: - -raddr
Σ
=
T.
[E[K]
v2
Σ (E(K]
J
V2 f(D)a 2 [.1]
(6)
2
|0.1]
Here the last line is because of Fubini Theorem, which states that the integral of function can be computed by iterating lower-dimensional integrals in any order. The factor y/2 arises because in 2 traditional Radon Transform require |/il2 but here ll || Ex112 V2.
B.3.1 PROOF OF LEMMA 5
Recall that s( ((A,7) 7)
min AT,
" A
log 7}. and AT < < " log 7 ++ A < e(()) where
e(T) defined as
[x(T log
When e(T) Po Eq.
implies that E 12
T-1
Say. ((r)s((kk))))) dr
Sa ((p(r)s( (A, T)I > do
lim inf T-
inf T-400
(.p((rs(AA))) T)dr
Jn (())s A d)
fo.11 2x (A) (( T)ITA ス IAA
lim T-400
[o.11 A s A T)dA
To prove the lemma, it suffices to show that
Jo.J1 2
0.5 - Po
lim sup
J0.I1 (<)))a(()))))))))))))))) T)T 7 5
T T-
Po
Define ET fo E [0. S ((T)) ex [0,1] : :T then
JE, q (A))
JE. yu (A)ATAA
lim
lim T
(8)
T T-000
Ja ah (A)s T)da
JE.VE ((A)(A wIT") )A
Je. (A)AdA
lim T (T) SRAF. (A) dd
(9)
We have shown that mx mx- P
E [L. With some calculation, m(t) A m mK-1(Pp 1 1T.)
- 1)U], and (0) lim, (t()) 2 L>> 0. By this continuity, for small enough & 0, 38 > 0, Vt E (1) gu (t) E [[1 (1)g: (1+
1-1--1 K-I Therefore, (t) E [m(t) - L,
E )1 (0)] As result,
lim 1 JE. 9h AA) (2(T) JELE. 9h (A) da
1 - 81
SE. AdA
lim
(T) +61) JELVE A
Ids
1 1-81
_e²
lim
T-x (T) + 61) log loy
T-1
Po log T
1-
1
lim
T-x 2(1 + $ ( -o) log 1
log
(T))log
7-1
0.
(10)
16

---

Under review as a conference paper at ICLR 2023
This implies that the limitation of 8 exisss and equals to O. Similarly, define GT for E [0, : log T J. then Gr, Fr C [O, 61] for sufficiently large T. This implies that
fo.1 ((())a(A,)))))))))))))()))))))) T < d limsup
JF. 9a (A)s(,, T)dA SO.IIA 9 (A) s A T)dA
lim sup sup
T+000 f0.11 qs (A))s(() TIIA 2 ro
T-200
JELVE au (A)( + "(T) log )d
lim lupsup sup
T-200
JO ON (A)(A
"(T T dA
JE.VE 9h (4) d
S lim sup
Sa. Th (A) _dA
T-
J..VE. A
+ 61
$
lum
Ja.VF _d
E1
T T-000
+ 61
log ((T) po log T Po log T log log(log T)
lum
1 -
T'+00
1 E1 2 -Po Po
1- 61 Po
Here the second equation comes from Inq. 10 The proof of Inq. is finished by letting E - 0.
B.3.2 PROOF OF LEMMA 6
Recall that A₁. is defined as {r E 9, Th + A&(1 +e) < 1}. For all t E (0, 7 k.
Peot
Ti A/ = (r E P :n; = maxxj, E A&. 3
{r E ::: : maxrry Tk = 1 E A1
frr E E = 3 maxx, ,, rj - 5k = rr r; + at < <}
=
fr E Pent
< TT:
This implies that
1-(1-a)K->
5 1 ltc
mIK-I(PEs) TTAAE) mk-i(tr E Ptrnt A : E {l1-el,
KT
K-1
O.w.
Notice that AS, is open, T, Ag compact, and (S1 S2) \ \Sa = =S \
(Sa). We have
(t)
p(r)dr E C(T.) \ A.).
P ((T.VA))
For all + l (Define 0= 1T 1))
Joy p(r)s(Ax,)) T)dr
So S (A)A
lim T- JagnT,P(1) (())s((x.))))))))))))))))))))) T)dr
lim
T-000
So s( (, (A)AA
So 1 (
lim
T
So K P (A)dA
U f ro.
1-(1-a)) K-1
A dA + S -|++
1-AK-1 ds
lim
7-000
L
5 1-AR-1 -AA
dA
S po + (K 1)edA + +[ 1dA
U
lim
T-00
L
Po oolog? T
k-1 (1 - T
1
U (K- - 1)e + log( + t) 0.
lim
T00
L
Po log K - To
Here the first equation is based on 6 and the second last Inq. comes from Bernoulli inequality.
17

---

Under review as a conference paper at ICLR 2023
B.3.3 PROOF OF LEMMA
To prove the lemma, We first reiterate an important lemma that lower bounds E.S (r, A)].
Lemma (Lemma 16.3 in Lattimore & Szepesvári (2020)). Let r, E Q be 2 instances that differs only in one arm & [K], where D > 0 in r and k uniquely optimal in r'. Then for any algorithm A,
2
log min(re- rk- Du. Au, Ant) + log T 1 log Mog(Regr(r:))) (r, + Regr (r', A))]
BISE (r, A)) (rk- r2)2
For fixed and r set r/2 + (1 AR)e, for A E Ω. On the other hand, when
T-Po e(T), Vr E O2f, s s(Ak: T) = DB +
"(T) According to Lemma for all r E Ag. As
A (r, (r) A) 2 Ax(1+c)2 log
( 4
+ log - (r, A) + Regr(r', (r,
Define 1 SanNi Ae
p(r) Tor 0c, and we have (r) = p/r)/ is thus p.d.f. in
24 NAG- We already know that for any 1-subgaussian bandit instance, the regret of UCB algo- rithm bounded by S/KT log T 3 > Au S logT..gT. The optimality of Å(D,, T) = arg A (eg (I) implies that Regr (D, A) S $9/KT log T. Due to the concavity of log(-),
/ ((r) (Rgg A) + Regt A))dr
- log / (re)())))) + Regr(r', A))dr
(
p(r)
[Reg, Ar) + Reg, A)) log /
p(r) dr
=log
A
24 nA A
/
S Sp log T + +log
(reg(())))) + Regr(r', ( - log
p(r)dr
244 n
S2t nA
((r) ((()) ((r") Regy (r' logg
S Pu Po log T + log
(Regr (D,
l0z n4
p(r)dr
S <log( 9(L + UVVK + log T) - log f 124 n1i
p(r)dr.
Therefore, we have
JaL P(r) A)drr
lim inf 70000
(11)
SOnNIN n. p(r)s(Ar, d'd
p(r) Ia naz As
log <Ae + log 7 log(Regr A) + Regr(r', ()))(r"))))) A)) dr
2
liminf 70000
(1+ + e)2
Sog nag A.
p(r)
( + u() (ouu((llgo' log lo)
(12)
+ lim inf 1 70 Th. aa nAz
p(r)
(log (rg + Regr(r', A)) dr)
e]+
Ab
(13)
lim /
1 - Pu-
log()o (r, A) + (e, A))dr
(14)
(1+ c)
T-000 nAj
9(L + UUVK
(1 + e)² Po limsup
(log(
T tro log log
p(r)dr)]
T000 log T
L
(15)
(1 (1+ 2po)
(16)
Here the last third line is because Phu Vr 04.
18

---

Under review as a conference paper at ICLR 2023
B.3.4 PROOF PART IN THEOREM |
Lemma 9, limy--o Regy A(D, T)) = +00.
Proof. In Lemma] 7 we already show that
SatM p(r)ArB[St (r, A)Jdr
1
lim inf T-000
(1 + c) 2 2po) 0.
JOh nAg ((r)s(Ak,) T)dr
To prove this lemma, if suffices to show that
lim T- N
p(r))(Ax; T)dr +00.
Notice that 2 A is non-decreasing in terms of T.
lim /
T. u(T) log T
p(r)s(Ax, T)dr 2 lim
dr
T T-000 24 n4
T+00 Joz n4g
DB
2 lim
(T( log Tdr J n&
T 10000
> Jim m(w n (A))Lu(T) log T +00.
T T=000
C OMITTED DETAILS FOR THEOREM
C.I SUBROUTINE FINDING THE COVER SET
This subroutine is used to find policy-value set I' such that 1i covers (1-36)-fraction of the MDPs in the sampled MDP set, i.c.
E 1B(T, 11, s.t. v) covers Mi]
36.
The algorithm is greedy algorithm consisting of at most N steps. As the beginning of the algorithm, we calculate a matrix A, where Ar, indicates whether (πJ, Uy) covers the MDP M₁, In each step find policy-value pair (T Uj with the maximum cover number in the uncovered MDP set T--1- We update the index set We and Te according to the selected index jr. We output the policy-value set Il once the cover size Et= 2 (1 N.
Algorithm Subroutine: Policy Cover Set
1: Input: Vi for i [N] and j E [N]
2: Initialize: the policy index set Uh = 0, the MDP index set To = [M]
3: Calculate the covering matrix A NxN where Ai, Cnd(Vi.j U1 Uj5)
4: for ... do
5: Calculate the policy index with maximum cover: arg wrggaanNnee. Σiet,, Aij
6: Set = U4-1 jr, Te [i: Ar, = 1}. the cover size n, = ΣieT.,, Aidi
7: The cover size Σt=1 n, (1 35) then
8: Denote U4 as U. then break the loop
9: Output: the policy-value set ń ((T,, v5.) uj
19

---

Under review as a conference paper at ICLR 2023
C.2 PROOF FOR THE PRE-TRAINING STAGE
During the proof, minimum cardinality, i.e. Q arg ( [5t]. As defined in Algorithm we use to denote the index of 92, which has the same cardinality Ω. We have the following lemma for the pre-training stage.
Ω denote the MDP satisfying the (1 -)-vverr condition with
Lemma 10 (Pre-training algorithm), With probability at least 1 0
(8 (oloog c( the pre-training
stage algorithm returns within log (Ō(C(D))) phases with total MDP sample complexity bounded
by Ô
C(D) 8
The return set Il satisfies
(),, it, (s) (iin(si) < 2e / o/ < <20] 2 21 60,
Pr MrB
(17)
and the size bounded by [il| < log
Proof. For each phase, we first define the in Appendix C.2.1
event Lemma [1 We prove the lemma
Lemma 11 (High Probability Events). For all phases, with probability at least 45, the following events hold:
1 N
I T[M -M) S8.
2. Vi E [N], is --pptimal for M, Vi,j E [N], Vis V 18)) S
3. For all index set U' C [N], we have
Pr MnD
3j
El (i (Vla
(1))
< Vil (82) ugs
<2
(18)
1
log 2N 8
max A 28 JEU
(19)
N
U'
N [44)]
According to Lemma the three events defined in Lemma 11 hold with probability 1 48. As stated in Lemma 12 condition on the first and second events, we have 14/ < (CD) log 1 for each 3 phase. We prove Lemma 12 in Appendix C.2.2 Note that these lemmas also hold for the last phase in which return the policy-value set IT.
Lemma 12. For all phases, if the first and second events in Lemma 17 hold, then the size of candi- date set U satisfies
U S (C(D) + (og()/)).
(20)
Since the stopping condition is
[ (og(2//))
R (og(2N/6) N-M
8 and we already know
N-
|4| < 2C(D) log J. the stopping condition is satisfied for N > doubling trick, we know that the number of total phases is bounded by log (Ō(C(D))) and the sample complexity is bounded by 2N (C(T))882)
4C(D) log? (C(D)/6) Based on the
8"
20

---

Under review as a conference paper at ICLR 2023
Therefore, by union bound across all phases, with probability least 1 Olog holds for all phases. Using the third event on the return set U, we know that
C(D) à 8). Lemma 11
PRMND
3j E u, (s1) - 1511
< 2En 1 (s)) 2j
< 2c
(21)
U log
Σ
max As, - 28
V
(22)
N [u
JeUI
N
[24]
VE[N]V
N N
U
35N
28
38 2 1 1668.
(23)
N
N U
Therefore, the property on il holds.
C.2.1 PROOF OF LEMMA
Proof. To prove this lemma, we sequentially bound the failure probability for each event.
Empirical probability of Ω²" Notice that since M, ~ D, the expectation of r.v. [[M, E 22' exactly P. According the Chernoff Bound, we have
n
Pr
[M, e e
s <exp(-2N66) < 6.
Therefore, the failure rate of the first event is bounded by 8.
Oracle error. For each E [NV], the failure rate O is at most -: For all i, [NV, the failure rate of 0g is most NT. Therefore, with probability least 26, we know that my indeed oopptiall for Mi, and By v < for all i,j E [N]. This implies that the failure rate of the second event is bounded by 26.
Covering probability of Lt. We first fix any index set 4' C [N] and define 4t = [N] \ U. For a policy-vales pair (x,, v) and MDP M, we define the following random variable
x( M) A Cnd Oe M,,,, n. c ( [loo((2/85)) v O₂ M. Or (M. y. log(N/6)) 5. log ( ())
e
e
Notice that A, is exactly instance of r.v. X( Uj, M,). For fixed index set 21' c [N]. each MDP M; with index E [N] \ 22 can be regarded as an i..dd sample from the distribution D. According to Chernoff Bound, with probability at least (2NjaT we have
1
Σ
max fx(T,, U3 My jeUr
[2' log 2N
max Aij S EMAD jELf
(24)
seye
21

---

Under review as a conference paper at ICLR 2023
On the other hand, use X to control the probability that Ty is near optimal for M,. Specifi-
cally,
EM-B
max yEUf
(x(TT
Ug. M)
(25)
max (x( Ug. MD} = 1
Pr
(26)
M-D
[EE
Σ P(M)
Pr
max jelr
{X(TT) Uy, M]} = 1Il
(27)
MEN
= Σ
P(M) Pr
Eje u' nt' = 0i (M.
E 2
(28)
MER
0= M, vT, 2 1og((> r' 0c [M,M 2. log(N2 /8)]
(29)
Cnd(v, v/ ,y)) = 1
(30)
Similar to the analysis in the second event of Lemma 11 with probability at least 1 - 28, for all j E UL the return T' is 2 s-optimal for M, and the estimated value and o' in the RHS is à --loos to their mean. Assume this event hold, we have
Fß E U', Cnd(v, v/, my) =1]
S I [3 E u', (x)) VM. (81) < 2e n (Mi - uز < <
Therefore, substitute the RHS in Eqn. 25 as (where 28 is the oracle failure probability)
E EMAD
max 1x(T,, MI. SEUr
(31)
< Σ P(M). ((1-20) 25)
(32)
MER
Pr
3j E U,; VMl (81) Vin((1)/ < 2e V (s1) (81)
Uj
< 26 2
+ +2)
(33)
3j E U/ (s)) vin(ss) < 22 / ( u//5 2E
< 28
+
Pr M
(34)
Combining Eqn. 24
and Eqn.
31 by the union bound, with probability at least
8 (2NY
1
Σ
| IN 1) 2 Σ
(2N) No 2 1 5,
1=
for all 21' [N], we have
Pr
] Eu', (M) Vin((s))
< 2e (s)) -js < 26
(35)
MND
1
[1'|log 2N
N - |
max Aig 25 Jelf
V
N 11
(36)
VE(NTIZe
C.2.2 PROOF OF LEMMA 12
Proof. For certain fixed phase, we define NM. = =EET, T[M; M] the population of M in
Tr. and Ô EN [M: E 22) We have Ô = EM NM.o. Thanks to the conditional events and
in Lemma 11 we have è P(22))
C N 2 1 11-28 28.
Notice that 2/ is generated by greedily selecting the best policy under current MDP remaining set T--1, f.e. the policy that covers most MDP in T.-1. On the other hand, since the second event in
22

---

Under review as a conference paper at ICLR 2023
Lemma 11 holds, for M, M,, we have Un. Vi, (5,5) and Cnd V1,e, Vj.5) are true and thus Ai, A = 1. Therefore, for each step and each M E Q if we have M₁ = M for some i Te-1 1 then in this round, we have
Σ Ar 2 NM
PET--1
Since we choose policy Ty instead of T. in step according to the greedy strategy, we have
Tt Σ Ar
Ar. Ar, NMI-1
(37)
MET-11
F'ET-1
for all M E Q.. The right term is 0 if M no longer exists in the remaining set, and the inequality still holds. Summing over all M Ω2, obtain
Σ NM
ne 2 C(D)
MEn
Σ
NM.0
E
(NM,0 NMAa2)
C(D)
MER
MEn
NM.
E
(NM.0 - -MM-II)
C(D)
Men-
MER
Σ
NM.0
Σ
"
C Σ C
C(D)
C(D)
MER-
where the last inequality is because Nu, is monotonically decreasing in l and the second last equation is because V n4 represents the population of MDPs that are covered in the first rounds. This implies that (notice that no = 0)
Σ
C(D) C(D)
Č- Σ 11 S S.... r=1
C(ID) )
C.
(C(D) +1
+1
which gives
nr 2 1- (-(00))))) c.
1=1
When 2 (C(ID) + log J, we have
U4 Σ n4 2 (1 exp (oo(((-()))))))) c C2
Ô N
2 (1 5) 26) 35.
Therefore, upon breaking, the size of U satisfies [4] [4,1 (C(ID) + 1) log 1
C.3 PROOF OF THEOREM 2
In Lemma 10 prove that with probability at least 1 - o (8 log C(B) the policy set i' returned
in the pre-trainig stage covers the MDPs M ~ D with probability at least 1 66, i.e.
Pr M-D
[( v) E (V, (=)) < 2e n (M,, wl < 2e 2 1 - 66.
Note that this event happens with high probability. If this event does not happen (w.p. O log e() the regret can still be upper bounded by K, which leads to an additional term
of K O ( (ólog (P)) o ( (VKlog log(KC(D))) in the final bound. This term is negligible com- pared with the dominant term in the regret. In the following analysis, we only discuss the case where the statement in Lemma 10 holds. We also assume that for the test MDP M²
(4",0") π1 V
(
2en ( 6 2c,
(38)
23

---

Under review as a conference paper at ICLR 2023
which will happen with probability 66 under the event defined in Lemma 10
We use L to denote the maximum epoch counter, which satisfies L [ii]. Lemma 13. (Optimism) With probability at least - 6/2, we have et 2 Vi.. 2e, 4I [4].
Proof. To prove the lemma, need to show that the optimal policy-value pair ( for M will never be eliminated from the set Il with high probability. Condition on the sampled M for fixed episode & E [K]. by Azuma's 's inequality, we have:
&
())(4K/))
Pr
Σ T=
Ga Vit- (81)
2
< 6/(2K).
(39)
kg
1:
1o
By union bound over all E [K], we know that
k
2 2log(4K/8)
Pr 3k
[K],
E
Gk - (81)
2
s 8/2
(40)
k: kin +
kn +
T=ka
By Inq. 38 we know that
V 1 - 0-1 < 4c. Therefore,
1
2 log( 4K/6)
Pr 3k [K],
Σ Gk 0* 2
ho 4e 8
(41)
Ko
By the elimination condition defined in line 6 of Algorithm in the fine-tuning stage, (**,0") will never be eliminated from the fi, with probability at least 1 6/2. By the definition that = max (z,))en we have vn 2 0* 2 1 - 2e.
Now we are ready to prove Theorem 2
Proof. We use Ti to denote the starting episode of epoch Without loss of generality, we set
TL+1 = K + 1.
we know that os Vur.i (s1) with high probability. Under this event, we can decompose the value gap in the following way:
By lemma 13
(31) VM (s1)
VM ( 2eK
1/
T-n-1
1 T11-1
(ur
G.)
Σ
Σ
CG--Va-, + 2cK
1=1
For the first term, by the elimination condition defined in line 6 of Algorithm I in the fine-tuning stage, we have
- (u) S 2(((41 - 7.) log(4K/0) + 4 - T) + 1.
For the second term, by Azuma's inequality and union bound over all episodes, with probability at least 1 8/2.
Σ
G- --- v(.))(s))) < 2 Ti) loog(K()) (K//))
T=R
24

---

The proof is from information theoretical perspective, which shares the similar idea with the lower bound proof for bandits (c.g. Theorem 15.2 in Lattimore & Szepesvári (2020) and Theorem 5.1 in Auer et al. (002 We first construct the hard instance and then prove the theorem. Since the bandit problem can be regarded as an MDP with horizon 1, our hard instance is constructed using distribution over bandit instances. For a fixed algorithm Alg, we define f2 be a set of M multi-armed bandit instances. For bandit instance V; E Ω there are M arms. The reward of arm j is a Guassian distribution with unit variance and mean reward 1 + Al(i = j}. The parameter A E j0, 1/2) will be defined later. We use vo to denote the bandit instance where the reward of each Under review as a conference paper at ICLR 2023
Therefore, by Seuchy-Schwazzine inequality,
M- 1 0o ( ( + [
(8)) (M
$ 0
log |KC (/
The last inequality is due to | & 2D) log(1/6) by Lemma 10 Finally, we take expectation over all possible M and get
Reg( (k) (VV))==(((C)KK))(())))))))) C(D))
(42)
C.4 LOWER BOUND FOR THEOREM
In this subsection, we provide a lower bound show that the regret upper bound in Theorem tight except for logarithmic factors. The lower bound is stated as follows.
Theorem 14. Suppose [S2] 2 2 and K 2 5. For any pre-training and fine-tuning algorithum Alg, there exists distribution ID over the MDP class Qt such that the regret in the fine-tuning stage is at least
Regx (D),lg) 2 Ω (min (VC(D),,K))
This lower bound states that no matter how many samples are collected the pre-training stage, the regret in the fine-tuning stage is at least ? (VC(D)K). which indicates that upper bound is near-optimal except for logarithmic factors.
arm a Guassian distribution with unit variance and mean reward 2. We set to be a uniform distribution over the MDP set Ω.
We use r² = (f1,-.. .......TT .kk) to denote the sequence of rewards received up through step k e [K]. Note that any randomized algorithm Alg is equivalent to a-prior random choice from the set of all deterministic algorithms. We can formally regard the algorithm Alg as a fixed function which maps the reward history - the action aş in each step k. This technique is not crucial for the proof but simplifies the notations, which has also been applied in Auer et al. (2002).
Reg (M;; Alg ) to denote the regret of algorithm Alg in bandit instance Vi. Therefore, we have Reg (D, Alg + EM Regx (v;, Alg ). We use P., and E.,, to denote the probability and the expectation under the condition that the bandit instance in the test stage 74, respectively. We use D (P1 P2) to denote the KL-divergence between the probability measure F, and Pp. We use (,( to denote the number of times arm i is pulled in the K steps.
With slight abuse of notation,
We first provide the following lemma to upper bound the difference between expectations when measured using Ey, and Exp-
Lemma 15. Let f R + [o. K] be any function defined on the reward sequence r. Then for any action i,
KA
Es, [f(r)) & E,g [f(r)]
Evn [T((K]]
4
25

---

Under review as a conference paper at ICLR 2023
Proof. We upper bound the difference En - Evo [f(r](]]] by calculating the expectation w.r..
different probability measure.
Ex,(((r)]- Evp [fr)] / (r))dPP.())) ((t))),,()--f,(tteeeaa
((T))dPss()) (r)
K 1 (d (1) dP2, (x))
Here !,r (dFF,. dl (r)) is the TV-distance between the two probability measure Pr, (r) and Pe. (r). Note that 24 and Mo only differs in the expected reward of arm By Pinsker's inequality and Lemma 15.1 in Lattimore & Szepesvári 2020). we have
1. (dde.. (x) dlP. no (r)) S
2
K
P No (ap = (NO 1))
2
k=1
Evo T [T(K) A
The lemma can be proved by combining the above two inequalities.
Now we can prove Theorem 14
Proof. By definition, we have
M Reg (Vi, Alg
Reg (D, Alg
(43)
M
1=1
M
1
(K - En, [T((K))
(44)
M
M
AK
E., [T((K]
(45)
M
We apply Lemma 15 to (K), which is function of the reward sequence since the actions of the algorithm Alg are determined by the past rewards. We have
KA Ex, [T((K) SEn, [T((K] + V ENg [Ti(K)]
We sum the above inequality over all vi Ω2 then we have
M
KA
E [T(()]
Σ Evn [T.
V E (T(K)
4
KK KA
MK,
where the second inequality is due to the Cauchy- Sehha- inequality and the fact that Enen E,, [T.(K) = K. Plgging this inequality back to Inq.
43
we have
K M
KA
K
Rega (D, Alg >A
K
M
Since K > 5, we know that C(D) has the same order as M. If K < M, we know that
VC(DD) R(K). We choose A 1/2 and know that Reg (TD, Alg 2 9(K). Therefore,
26

---

Under review as a conference paper at ICLR 2023
we have (Dg Alg) 2 (min (V)()),k))) IF 2 M, we choose
4d. K
Since
M 2 2, also prove that
Regx (D, 2 Ω min (VC(D),K))
D OMITTED PROOF FOR THEOREM 3
We define π² = arg man EM-D VM, M, (81) and A arg max aE N E ( For the returned policy म, we can decompose the value gap into the following terms:
EM (s)) - (s11 BMM-DVMilS
N E (51
(46)
V MM (51) -EM-D V (
(47)
N
N
1 N
1
M
(
Σ
V
(81)
(48)
N
N
N
VM
1 (81)
Σ
V
(49)
N
N
Note that the first and the second terms are generalization gap for a given policy, which can be upper bounded by Chernoff bound and union bound. The third term is the value gap during the training phase. The last term is less than 0 by the optimality of n*
Upper bounds the first and the second terms We can bound these terms following the gen- eralization technique. Define the distance between polices d(r') 2²) max,es,te(1) (-1s)
(1)))l.. We construct the co-coveiing set w.r.t. such that
VT E IT. 3# E ग. s.t. d(T, #) S co.
(50)
By Inq.
50
we have
VT E IT, 3Ā E fi, 8. (81) (s) S Hep.
(51)
By definition of the covering number, | = NII, co. d). By Chernoff bound and union bound over the policy set f1, we have with prob. 81, for any f1
N
2 2lgg eo. d)/61)
V V (81) VEMWDVM.I... s
(52)
N
By Inq. 51 and Inq. 52 for VT II,
1
V (s1) EMED Vin((s))
V VM.
EM VM-DVVilsss)
(53)
N
N
N
VM
Σ
v
(11)
(54)
N
N
i=1
+
E M, (s1) - -EM~D BEMDVVIL (5
(55)
2lo co. d)/51)
2
+ 2H
(56)
N
27

---

Under review as a conference paper at ICLR 2023
We can 6g 12ff and d1 1/6. Since N Cog (II, (I2,) d)) /e2 and n², ; II, we know that with probability at least 5/6,
N
( BM V. (.
S 3
(57)
N
V
(8))
S
(58)
N
Upper bound the third term subsections. Lemma 16.
We have the following lemma, which is proved in the following
With probability least 5/6, Algorithm can return a policy ă satisfying
Σ (
Σ (si) 3
where tt is the empirical maximizer, Lee. 4* = arg max wnl N
E (
Pluging the results in Lemma T6 Inq. 57 and Inq. 58 back into Eq. 46
we know that with probability
at least 2/3,
MMD (Mi((1)
Vii(si) Sc.
D.I PROOF OF LEMMA 16
We first state the following high-probability events.
Lemma 17. With probability at least 1 2HK the following inequality holds for any i E [N],
E
[K] h [H] E S,a A.
25 28log(8AANHK)
(M..a(((3s,)) - -Pm.((ls,a))
(59)
max NM.
2 log(SSANHK)
(60)
Proof. According to Weissman et al. 2003). the Lı-deviation of the true distribution and the em-
pirical distribution over m distinct events from n samples is bounded by
ne" 2
P ()))(-)) p(-I1ı 2 2 s (2th 2 exp
our case where m = S, for any fixed i, k; h 8, a, we have
25 log(1/8)
P PM..n. a) PM S
(61)
with probability at least
Taking union bound over all possible i, k, ft, know that Inq. 61 holds for any i, ft, with
probability at least 1 - K. ASAS. We reach Inq. 59 by setting I
For the reward estimation, we know that the reward is 1-subgaussian by definition. By Hoeffding's inequality, we have
log(2/8)
S max 1, (s,,)
with probability at least 8 for any fixed i, k. h, s, a. Inq. 60 can be similarly proved by union bound over all possible i, kt h. 8, a and setting 5 TNK*
28

---

Under review as a conference paper at ICLR 2023
Lemma 18. The following inequality holds with probability at least 1 2KH*
K N
ΣΣΣ
VM (TMA(M))))))) (Q (oMath aMM (MM.lMM.Ah..M... V (MM,RN)
2N HK (og(HHH),
K N
ΣΣΣ P.M (VTL
M.EAHI VM..)) (s..th.am.nn)) (aaan))((VMMMa (V
S 22NNHK 18g(8KH)
Proof. For the above two inequalities, the RHS can be regarded as the summation of Martingale differences. Therefore, the above inequalities hold by applying Azuma's inequality.
We use A to denote the events defined in the above lemmas. Now we prove the optimism of our algorithm under event A1.
Lemma 19. Under event AG, we have V (..k,1s1 (81) 2 (s) any i E [N], k E [K], e II.
Proof. We prove the lemma by induction. Suppose Q (MMeHi() (M..+ if (M, L, then we trivially have QM, 2 (s.a) If (M 1, then
For h e [M],
(M, Qm,a(s,a)
- (M,,b((aa) - - -MM RMissn(s a) (M.nkh(sss) P PM.KA MM.AA
(M, a)
zbMGAM(s,a) [ -rman(s, - - (M,.A(()s, - (M.n(11,
+PM (VMIANN1 V(nn+i) (s)a)
2log(8SANHK)
25log(8SANHK)
2bM.An((,,))
Ma
+ PM.M (V (Viiietta (ūūhht)) (s,a)
PP
VIT M. VT(,++1) (8)
20,
where the second inequality is due to Lemma 17 and the third inequality is derived from the defi- nition of (, a). The last inequality is from the induction condition that (T 2 (s, a). Therefore, for step h, we also have (M, 2 (s,
From the induction, know that QM,R( 2 (s, By definition, have (M 2 ($1).
Now we prove Lemma 16
Proof. (Proof of Lemma 16 By Lemma 19 and the optimality of #t.
K
( (81) - V (81))
(8 - Vol. (s)..
(62)
i=
29

---

Under review as a conference paper at ICLR 2023
We decompose the value difference using Bellman equation. For each episode & [K]:
(innnl V Mi
(VMinhhsMMikk V. (MMalMM))h))) ( (OMA - (MMAA -MMMM aMMNNN))
VTL (MAAM(MMAAA) ONULe (MMMAAAMMMMM))) -
- Q aM
+ RM.EA aMinaN) TMI. (SMMAN + (PMIRA- -PMM)) V Miihi i (SM aMaka)
+ PMIn (VML vM..)) a.M.en (WW.AAI11MMMMHH V. (MM,(MM,
+ bM,AnleM;Ah,
+ (MM (SM.RR))
Therefore,
K
N
(ai, Viln (s1)
N
(MAAA)MAAN) V (enaalmmen)) ( amikn) (SM.k
(PM.RA-PMM. - -PM,.) (SM.AnHHSMMM.....MMM a
Σ
(PMin (VMLMiTII Viiin) (sM.Rhi amax.)) (MM,) (M VMu (8++1.841))
k=
RM..A(SMiAh aM.K,N) -M,.ASMM.nn + (PMi.eh - -PMen)) V Vicketi (SM amckk))
ΣΣΣ
by. (SM,,,,,,,,MM + O( NogKHKK
The last inequality is due to Lemma undde event A₁. By Lemma
17 we have
K N
ΣΣΣ
(Mw.aalsMMARRMMaa. - -aw. (MM, aM,.))) + (PMinn -PMin) VTT Vilcet (SM.,, am.i)))
K
N
#
k=
K
ΣΣΣ T PM. -Pw.alll.laaalaaaaaaaaaa (at.ssaaaaaaamaaa
30

---

Under review as a conference paper at ICLR 2023
We
can
upper
bound Ex En (V),, - (s1)
by the
summation of
bM..Mlssu.khh d.M.).)) By definition, we have
K
N
K ΣΣ
25 (ogg(88ANNK)
ΣΣ (s1) (s))
+O(v OOL/NHK logllogoooH (og(K
max
By Cauchy- Hanehy-Schwwrz inequality, we have
K
N
ΣΣ (s1) - (s)) (NNNVISSAA HASSAK (og(SAHNK) + NNHS
k=
Since uniformly selected from the policy inequality holds with probability at least 5/6.
{T 18
By Markov's inequality, the following
N
K
N
Σ
(s))
V v
(+), - 181).
6K
1=1
With our choice of K C252 AHI log(SAlt/ee/e² we have
(si ( -i.
s//3.
D.2 HIGH PROBABILITY BOUND
To obtain high probability bound with probability least 1 8. Our idea is first execute Algo- rithm indepeendnnyy for (log((/))) times and obtains policy set with cardinality Ollog(1/)). the sampled M MDPs, and then return the policy with the maximum empirical value. The algorithm is described in Algorithm 5
We evaluate the policies in the policy
Algorithm 5 OMERM with High Probability
Input: target accuracy > high probability parameter
N = C1 log (N (TI, c (122) (5) /e2 for a constant C1 > 0
N1 (2g((/8)/ log(1 1 66, N₂ = C2 (NNN,)/)) for constant C2 Sample N tasks from the distribution DD, denoted as (M, ,MN]
5: for 1, Ni
Execute Algorithm 2 with target accuracy e/2 and task set (Mi, M2,... ,NN). and ob-
tain a policy Fe for task index i 1,2, .N do
Execute me on task M, for N₂ times, denoted the average total rewards as Ve,
Calculate the average value Vgg 1/ EN Vg,s
10: Output: the policy σe. with e* arg [e[N] Ve
We have the following theorem for Algorithm 5
Theorem 20. With probability at least 1 - 6, Algorithm can output a policy î satisfying
MDP instance samples during training. (M>>D[VX'' (D) V e with O (on(N")
The number of episodes collected for each task is bounded by O H² Alog(SAH) log(1/8)
The proof follows the proof idea of Theorem 3 with only the difference in the bound on the empirical risk. We first prove the following lemma.
31

---

Under review as a conference paper at ICLR 2023
Lemma 21.
With probability least 1 - 82. Algorithm
5
can return policy we. satisfying
N
N
( (81)
e 3' Σi= (
N
where ft is the empirical maximizer, i.e. 7 = arg max ell N
Proof. By Lemma 16 for each E [Ni], the following inequality holds with probability at least 5/6,
M.l (81)
VM.. M., (81) S 9
(63)
N
N
In Algorithm 5 we evaluate the policies in the MDPs by executing the policies for N2 times. By Hoeffding's s inequality and the union bound over all & E [N1] and E [M], with probability least 1 62/2, we have
VE
Σ
Min (s1)
I 9. V4 E (Ni). [M]
N
We denote the above event as A2. For each & E [N1], we define as the event that 1 Eie V (51) V/ 2c By Inq. 63 we have Pr(m) 2 5/6 under event A2. Note N₁ that the event {n { are independent with each other. Therefore, with probability at least (1/6) = 02/ there exists Eo. such that the event 7s happens. That is, there exists
policy Tes such that
2e M (81) Vis -
N
9
By definition, 5* = arg meX Ve. Therefore, we have N Σ Vi, (81) Ve- S 2: Under the event of A2, we have the following inequality holds with probability at least 52/2,
(s1)
V (81)
Proof. (Proof of Theorem 20) The proof follows the proof idea of Theorem We bound the empir-
3
ical risk by Lemma 21 With our choice of 62 = 8/3, we have with probability at least 1 - -0/2,
M..1 (81)
V (s1) V
(64)
Following the proof Theorem can similarly show that the following inequalities hold with probability 1 5/2,
V (81) -EMOE VM,
(65)
3'
N
V (s)) -EM Vh.
$ 3
(66)
N
Combining the results in Inq.
65
Ing 66 and Inq. 64 we know that with probability at least 1 - 8,
EM-D
( - v <c.
32


Reviews:
[{"review_id": "ntcLNRMEeiw", "reviewer": "Reviewer_SxSR", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 addresses a generalization problem in RL, in which the agent interacts with a set of MDPs taken from an unknown task distribution during training, and subsequently minimizes the (expectation) of the regret in a test MDP taken from the same distribution. The paper first studies an asymptotic setting in which the number of test episodes goes to infinity, showing that the benefit of pre-training is at most a constant factor. Then, it considers a non-asymptotic setting through an algorithm, called PCE, that pre-trains a set of policies to achieve a regret upper bound that depends on the complexity of the task distribution but not on the number of states and actions in the MDPs. Finally, the paper studies an additional setting in which no interactions can be taken at test time, for which it provides an algorithm (OMERM) achieving near-optimal zero-shot adaptation to the test MDP by taking a polynomial number of samples during training.", "summary_of_the_review": "*After discussion*\n\nAfter a fruitful discussion with the authors, I have a better understanding of the contributions of the paper. Most of my concerns have been solved, and I am updating my evaluation to accept.\n\n---\n\n\nThis paper is in many ways interesting. Generalization in RL is an extremely relevant problem, while the algorithmic procedures and the problem formulations seem to introduce original ideas. Especially, the idea of achieving guaranteed test-time sub-optimality/regret by covering the space of instance-optimal policies looks very promising to me. \n\nHowever, the presentation is less than ideal, and as a result there is a good chance I am missing crucial parts of this submission. The reported results seem sometimes unreasonable to me (especially Theorem 3), and I cannot see how this problem can be solved without strong structural assumptions on the task distribution and the underlying MDPs. \n\nI am currently providing a borderline evaluation that reflects my skepticism about some of the claims. I will revaluate my score upon a due inspection of the proofs, which I could not check given the limited reviewing window, and clarifications from the authors' response.", "strength_and_weaknesses": "Strengths\n- (Relevance) The paper addresses the interesting problem of pre-training a set of policies for efficient RL at test time;\n- (Originality) The paper introduces several original ideas, including interesting problem formulations and algorithms to pre-train policy sets.\n\nWeaknesses\n- (Presentation) The paper is not an easy read. The notation is not always sharp, the claims are sometimes sloppy and not clearly supported, and some of the comments on the theoretical results can be confusing;\n- (Odd evaluation choices) The benefit of pre-training is studied either in a bizarre asymptotic formulation of the regret or compared against a RL baseline that learns from scratch neglecting the samples complexity of the pre-training itself;\n- (Unreasonable results) Some of the theoretical statements are so strong that look unreasonable (though I am probably missing something);\n- (Non-asymptotic lower bound) There is a clear mismatch between the provided lower bound (on the asymptotic cumulative regret) and the regret upper bounds of the proposed algorithms, which instead come from non-asymptotic analysis;\n- (Related works) Only a few related works are reported, and the relations with some relevant pieces of the literature, such as multi-task RL (e.g., Brunskill & Li, Sample complexity of multi-task reinforcement learning, 2013), are not discussed well-discussed.\n\nComments\n\n(Lower bound) I am wondering what is the purpose of the asymptotic setting. Regret minimization is usually interesting in finite time, what is the point of comparing the infinite values of the asymptotic cumulative regrets? Moreover, all of the other results are reported on finite-time settings, for which a lower bound is not formally provided. This makes unclear how to evaluate the obtained upper bounds.\n\n(Measure of performance) I am not sure the test-time regret alone is a good measure to uphold the importance of pre-training. It is clear that pre-training can provide some benefits at test time, but what is the point in comparing the $O(\\sqrt{SAHK})$ regret of RL from scratch with the $O(\\sqrt{\\mathcal{C}(\\mathbb{D}) K})$, when the PCE algorithm still suffers $O(|\\Omega| \\sqrt{SAHK})$ regret in the pre-training phase (or, alternatively, sample complexity)?\n\n(Algorithm 1) Is the PCE algorithm always guaranteed to find a suitable set of policies during pre-training? I.e., the condition at line 10 is guaranteed to be verified eventually?\n\n(Theorem 3) I am in all likelihood missing something here, but the result in Theorem 3 seems to be so strong to be unreasonable. In particular, when the covering number on the policy space is finite the output of OMERM can generalize to any unseen task without further interactions. The following thought experiment suggest otherwise: If I sample a test task from $\\mathbb{D}$ and then a policy uniformly at random from the obtained policy set, in all likelihood the policy will not be good for the specific instance. If I repeat this process several times (then converging to the expectation) I cannot see how the average sub-optimality can be small. What is wrong with my thought experiment?\n\n(Non-Markovian policies) The paper seems to be only considering Markovian policies, but I am wondering whether this setting necessitates history-based policies. From my intuition, the test task is akin to a partially observable MDP, where the information on the specific instance is hidden to the agent. Do the authors think that Markovian policies are sufficient instead?", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "Pln3sngx_b", "reviewer": "Reviewer_s13Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 studied the generalization problem in RL and used Bayesian regret as a performance measure. The authors considered if the agent is allowed to use the data from interaction with the testing environment.  ", "summary_of_the_review": "This is an interesting paper but the theory part is less strong. ", "strength_and_weaknesses": "I feel this is an interesting paper. Considering testing time interaction is the right way to think about generalization in RL. The lower bound in Section 4.1 is not surprising and intuitive. I am glad the author can make it formal. I have two major concerns about this work:\n \n1. The authors mentioned in the training stage, the agent can sample i.i.d MDP instances from the unknown distribution. I can not understand why the agent has such power. This can only happen in a highly-simulated environment and I am not aware any real-application can satisfy this requirement. Algorithm 1 needs to sample a large number of MDPs. If the state space is infinity, how can the agent do that? For example, if I want to train an agent to play Atari, how Algorithm 1 samples MDPs?\n \n2. Theorem 2 is less satisfactory, especially for C(D) term. This complexity measure is not interpretable and so far it's only better than SA in a very extreme case. I feel this should explicitly depend on some quantities that describe the distribution of D. Usually for a tabular MDP, people put Dirichlet prior on the dynamic, which is continuous. Then C(D) should depend on the Dirichlet parameters. It's unclear how good C(D) is and how it reflects the intermediate regime. \n \nIn the end of Section 4.2.2, the author mentions \"when D is subgaussian or mixtures of subgaussian\". What does it mean? The dimension of a MDP is a SxAxS tensor then how do you define sub-gaussian here?\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": "Not applicable"}, "extra_text": {}}, {"review_id": "HU_s4ykCiG", "reviewer": "Reviewer_tCeD", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 theoretically investigates the implications of pre-training for generalization in RL in terms of possible benefits and limitations. Specifically, the paper shows that in an asymptotic limit (where the agent can interact $K \\rightarrow \\infty$ times with its environment and knows the MDP distribution D) pre-training can improve the regret only up to a constant. In the non-asymptomatic case, the authors propose an algorithm for which pretraining can help, by deriving a regret bound that depends on the complexity of the (MDP) distribution D. Finally, authors propose a second algorithm that pursues optimalitiy in expectation for the case where the agent is not allowed for further test-time interactions after pretraining.", "summary_of_the_review": "This paper offers a range of novel theoretical insights regarding the benefits (or impossibilities) of leveraging pretraining for generalization in RL where the pretraining and test environments are sampled from the same distribution. While the paper is purely theoretical and I believe such insights to be helpful in general, it is unclear how much those particular insights help in practice where pre-training is already a frequently used technique for RL. I would have expected the authors to at least empirically prove the effectiveness of the suggested algorithms on RL test beds. I, therefore, lean towards rejecting the paper.", "strength_and_weaknesses": "Strength\n- The paper offers a more precise understanding of the best-case benefits of pretraining over no pretraining when fine-tuning is allowed for $K \\rightarrow \\infty$ episodes at test-time.\n- Extensive theoretical investigation of the benefits of pretraining in RL with the help of two proposed algorithms for the setting with finetuning or test-time interaction in the non-asymptotic case and without further test-time interactions.\n- The authors do a good job at contextualizing and explaining the theoretical implications and ramifications of their derived bounds.\n- The paper is well-structured and clearly written.\n- Appropriate literature review to contextualize the contributions\n\nWeakness\n- While I appreciate the extensive analysis and theoretical nature of the proposed algorithm my biggest concern is that the benefits and usefulness of these bounds in practical pretraining settings in RL are not very clear from the paper. I would have hoped the authors could at least implement their algorithm and test how well it actually works in popular RL environment test beds, e.g. the Arcade Learning Environment. Without such experiments or empirical results, my worry is that the algorithms and bounds are of limited use. As an example, how effective and computationally expensive would the algorithm be in practice over naively pretraining an agent on the subset of MDP environments, and then adapting to a new environment of the same distribution?\n- The proposed bounds and algorithms assume the pretraining and test environments are sampled iid while pretraining is especially hoped to help in OoD scenarios.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject