When Is Generalizable Reinforcement Learning Tractable?
Authors: Dhruv Malik
Yuanzhi Li
Pradeep Kumar Ravikumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
generalization

Abstract: Agents trained by reinforcement learning (RL) often fail to generalize beyond the environment they were trained in, even when presented with new scenarios that seem similar to the training environment. We study the query complexity required to train RL agents that generalize to multiple environments. Intuitively, tractable generalization is only possible when the environments are similar or close in some sense. To capture this, we introduce Weak Proximity, a natural structural condition that requires the environments to have highly similar transition and reward functions and share a policy providing optimal value. Despite such shared structure, we prove that tractable generalization is impossible in the worst case. This holds even when each individual environment can be efficiently solved to obtain an optimal linear policy, and when the agent possesses a generative model. Our lower bound applies to the more complex task of representation learning for efficient generalization to multiple environments. On the positive side, we introduce Strong Proximity, a strengthened condition which we prove is sufficient for efficient generalization.

When Is Generalizable Reinforcement Learning Tractable?
Dhruv Malik
Yuanzhi Li Machine Learning Department Carnegie Mellon University Pittsburgh. PA 15213
Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213
Pradeep Ravikumar
Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213
Abstract
Agents trained by reinforcement learning (RL) often fail to generalize beyond the environment they were trained in, even when presented with new scenarios that similar the training environment. We study the query complexity required to train RL agents that generalize to multiple environments. Intuitively. tractable generalization is only possible when the environments are similar close in some sense. To capture this, we introduce Weak Proximity, a natural structural condition that requires the environments have highly similar transition and reward functions and share policy providing optimal value. Despite such shared structure, we prove that tractable generalization impossible in the worst case. This holds even when each individual environment can be efficiently solved to obtain an optimal linear policy, and when the agent possesses generative model. Our lower bound applies to the more complex task of representation learning for efficient generalization to multiple environments. the positive side, we introduce Strong Proximity, a strengthened condition which we prove is sufficient for efficient generalization.
1 Introduction
Reinforcement learning (RL) is the dominant paradigm for sequential decision making in machine learning, and has achieved success in variety of domains such as competitive gaming [33, 40] and robotic control [21, 22]. Despite this success, many issues prevent RL from being regularly used in the real world. For example, one typically trains and tests RL agents in the same environment. In such cases, an agent can memorize behavior that achieves high reward, without acquiring the true behavior that the system designer desires. This has raised concerns about RL agents overfitting to single environment, instead of learning meaningful skills [17].
Indeed, long line of work has noted the brittleness of RL agents: slight changes in the environment, such as those incurred by modeling or simulator design errors, or slight perturbations the agent's 'ss trajectory, lead to catastrophic declines in performance [36, 49, 23]. Furthermore, although RL agents can solve difficult tasks, they struggle to transfer the skills they learned one task to perform well in different but similar task [37, 48). Yet, in the real world, it reasonable expect that RL agents will see scenarios that are at least mildly different from the specific scenarios they trained for.
Hence, a desirable property of RL agents is that of generalization, broadly defined as the ability to discern the correct notion of behavior and perform well in semantically similar environments. We focus on two popular generalization settings. The Average Performance setting assumes there is an
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

underlying distribution over the environments that an agent might encounter. The agent's goal is to perform well on average across this distribution [35, 34, 11]. The Meta Reinforcement Learning setting is closely related [20, 10, 37J. Here an agent first learns from a suite of training environments sampled from a distribution. Then at test time the agent must leverage this experience to adapt to a new environment sampled from the same distribution, via only few queries in the new environment.
Of course, in full generality, both notions of generalization are impossible to achieve efficiently, This is especially true in the RL function approximation setting, where the cardinality of the state space is potentially infinite, and so we desire query complexity that scales (polynomially) with the dimensionality of the state space [13, 38, 14, 31, 46]. Hence, key to both lines of inquiry is the premise that the environments are structurally similar. For example, robot may face the differing tasks of screwing bottle cap and turning a doorknob, but both tasks involve turning the wrist [37]. The hope is that if the environments are sufficiently similar, then RL can exploit this structure to efficiently discover policies that generalize.
Yet, it remains unclear what kind of structure is necessary, and what it means for different environ- ments to be close or similar. Motivated by this, we ask the following question:
What are the structural conditions on the environments that permit efficient generalization?
This question underlies the analysis of our paper. We focus on environments that share state-action spaces, since even this basic case is not well understood the literature. Indeed, even in this simplified setting, efficient generalization can be highly non-trivial. We make the following contributions.
Our Contributions. We introduce Weak Proximity, a natural structural condition that is motivated by classical RL results, and requires the environments to have highly similar transition and reward functions and share optimal trajectories. We prove statistical lower bound demonstrating that tractable generalization is impossible, despite this shared structure. This lower bound holds even when each individual environment can be efficiently solved to obtain an optimal linear policy, and when the agent possesses a generative model. Consequentially, we show that a classical metric for measuring the relative closeness of MDPs not the right metric for modern RL generalization settings. Our lower bound implies that learning a state representation for the purpose of efficiently generalizing to multiple environments, is worst case sample inefficient - even when such a representation exists, the environments are ostensibly similar, and any single environment can be efficiently solved.
To provide a sufficient condition for efficient generalization. we introduce Strong Proximity. This structural condition strengthens Weak Proximity by additionally constraining the environments to share an optimal policy. We provide an algorithm which exploits Strong Proximity to provably and efficiently generalize, when the environments share deterministic transitions.
2 Related Work
Simulation Lemma. Many prior works define notions of statistical distance between Markov decision processes (MDPs), and measure the relative value of policies when deployed in different MDPs that are close under such metrics. The Simulation Lemma, which uses total variation distance between transitions and the absolute difference of rewards this metric, is well known formalization of this and has been very useful in classical prior work [26, 27, 6, 25, 1]. These works do not directly tackle generalization, but their analyses construct an approximate MDP that models the true MDP under the aforementioned metric. Solving this approximate MDP then corresponds to solving the true MDP. It is natural ask whether this metric is useful for measuring the similarity of MDPs in modern RL generalization settings. We show this metric is not appropriate for the settings we study.
Transfer & Multitask Learning. There are varying formalisms of both settings, we do not directly study them. However, they are broadly relevant, and we expect our theory to be useful for future studies of these settings. The works [32, 7, 24, 43] all study metrics for measuring variation between MDPs that are different from the metrics we study. A metric similar to the one used in the Simulation Lemma has also been studied [18], and show that this is inappropriate for our settings.
Average Performance & Meta RL Settings. We directly study these two settings, which have seen much empirical work [35, 11, 12, 37, 48). On the theoretical side, [5, 42) study an Average Performance setting where the agent receives a noisy observation in lieu of the actual state. We focus on the simpler setting where the agent knows its state. Recent works [16, 44] analyze the

---

MAML algorithm [20] in the context of Meta RL. In the worst case, their complexity bounds scale exponentially with the horizon, and they do not discuss structure which permits tractable Meta RL.
Representation Learning, A large body of work has focused on extracting a representation useful for single MDP [19, 8, 30, 50]. Some works extend this to multiple MDPs [9, 3, 41], but they are about learning shared representations for MDPs that appear similar (but not from a sample efficiency perspective), while we formalize what it means for MDPs to be similar (in sample efficient sense). Indeed, these works study the general case when the environments have distinct state spaces, but our lower bounds show generalization is non-trivial even when each MDP shares the same state space.
3 Problem Formulation
Notation & Preliminaries. Before describing our settings of interest, we establish notation and briefly review preliminaries. We always use M to denote a Markov decision process (MDP). Recall that an undiscounted finite horizon MDP is specified by a set of states S, a set of actions A, a transition function T which maps from state-action pairs to distributions over states, a reward function R which maps state-action pairs to nonnegative real numbers, and a finite planning horizon H. We assume that the state-action pairs are featurized, so that S x A C Rd, and that ()ls,))l22 Any MDP we consider is undiscounted and has a finite action space, but could have an uncountable state space. If we need to refer to the transition reward function of specific MDP M, then we shall denote this via T as or Ras. We will denote a distribution over MDPs as D. We also assume that S can be partitioned into H different levels. This means that for each s E S there exists unique E {0, 1..1.... H }} such that it takes timesteps to arrive at s from sy. We say that such a state lies on level h, and denote S₁ to be the set of states on level h. This assumption is without loss of generality, since we can always make the final coordinate of each state-action pair encode the number of timesteps that elapsed to reach the state. A "deterministic MDP" is one with deterministic transitions. For any MDP, we assume a single initial state Sp, which strengthens our lower bounds.
for all (s, a) E S x A.
A policy maps each state to a corresponding distribution over actions, and shall typically be denoted by π. The total expected reward accumulated by policy π when initialized at state 8 in MDP M is given by IE Diiteae [ RMr(sh an) π and will be denoted by V (T). Here the expectation is
over the trajectory {(sn, an)) H-11 ) [l=evel(s) given that the first state in the trajectory is s. So Vy (T) is the value of the policy π in MDP M with respect to (w.r.t) initial state Analogously, if a policy is parameterized by 0 = (0x [[>}/=] =1 then we denote it as T (0). and the notation V (T) is then replaced by Vi (0). We assume that the cumulative reward collected by any trajectory from any initial state in any MDP M is always bounded by 1. Hence the value of any policy in any MDP lies in the interval
[0, 1]. TV(P, Q) denotes the total variation (TV) distance between probability distributions P and Q.
3.1 Problem Settings
Average Performance Setting. There is fixed distribution D over a family of MDPs. One can sample MDPs from D. The algorithm can query states in the sampled MDPs, to learn some common structure. The goal is to solve
max EMND [V (T)).
(1)
Meta Reinforcement Learning Setting. There is a fixed distribution D over a family of MDPs. At training time, one sample MDPs from D. The algorithm can query states in the sampled MDPs, to learn some common structure between all the MDPs. Then at test time, an MDP Must. is sampled from the same distribution D. The goal of the algorithm is to learn subroutine, which with non-trivial probability over the selection of Meett can solve
max
50
Meea (TT),
significantly more efficiently than trying solve Mest without having seen any training MDPs
In both settings, "sampling an MDP" means drawing an MDP i.i.d from D. so that the agent can then interact with it by performing trajectories in it. Note that in Eqs. (1) & (2), in full generality the initial state sg is random and depends on M, Mestt- We focus on the case when the MDPs supporting
D share fate-action space, and hence share the same single initial so since we assume a single
3

---

initial state for any MDP. While such assumptions are already strong, they only strengthen our lower bounds. Furthermore, it is necessary to understand this simpler setting, before looking more complex scenarios. To the best of our knowledge, such study has not appeared in prior work.
To solve the problems described by Eqs. (1) & (2), need define appropriate query model for the algorithm. We consider two query models, the first of which is strictly stronger than the second.
Strong Query Model (SQM). Sampling an MDP from D incurs cost. The agent has generative model of any sampled MDP M. To interact with M, the agent inputs a state-action pair (s, a) of M into the model, and receives Rar (s, a) and a state sampled from T as (s, a). This incurs query cost of one. The goal is to solve Eqs. (1) & (2) with total query cost that is at most polynomial in [A], H.
Weak Query Model (WQM). Sampling an MDP from DD incurs a query cost of go 2 1. Within a sampled MDP M, the agent operates in the standard episodic RI. setup. Concretely, during each episode the agent interacts with the MDP by starting from sp, taking an action and observing the next state and reward, and repeating. Each action taken during an episode incurs a query cost of one. The goal is to solve Eqs. (1) & (2) with total query cost that is at most polynomial in qD, [A|, H,
Note that under both SQM and WQM, we desire query cost that is polynomial in the dimension d of the alate-action space, as opposed to the cardinality of the state space. This is standard for our function approximation setting [13, 38, 14, 31, 46], since the cardinality of the state space could be infinite. Also, we separate SQM and WQM because is well known that different query models can lead to various subtleties in analysis and sample complexity guarantees [13, 38, 14, 31, 46). The generative model that defines SQM assumes that we can simulate any state of our choice without performing a trajectory, which is unrealistic in practice, and is one of the strongest oracle models considered in prior literature [28, 4, 39, 14, 31, 2]. We shall present our lower bounds under SQM, which makes these results stronger, but shall present our upper bound under the natural and standard WQM.
Without any conditions on D. the Average Performance & Meta RL settings can be intractable, even under SQM. This will occur if the MDPs supporting D do not share structure. This will also occur if any individual MDP cannot be solved efficiently. Nevertheless, in practice one often deals with MDPs which share meaningful structure [11, 37]. For instance, the transition distributions of the MDPs may be close in a suitable metric. Similarly, the reward functions of the MDPs might be close in an appropriate norm, or each MDP may share set of optimal trajectories. And in practice, individual MDPs can usually be optimized efficiently [35, 48]. In such cases, it is reasonable to expect tractable generalization. We are interested in formalizing conditions that permit efficient generalization. We will particularly focus on conditions which capture shared structure of the MDPs and the tractability of individual MDPs. We now formally state the problem we consider throughout our paper.
Which conditions on DD allow us to solve the Average Performance & Meta RL. settings esficiently?
As mentioned above. there are two types requirements. The first requirement should ensure that the MDPs are meaningfully similar. We formalize such conditions in Section 3.2. The second requirement should ensure that any individual MDP is efficiently solvable, else there is no hope to efficiently find policies that generalize for many MDPs. We formalize such properties in Section 3.3.
3.2 Strong & Weak Proximity
We now identify conditions that capture when the MDPs supporting D share meaningful structure. Since MDPs are defined in terms of rewards and transitions, it is very natural to impose conditions directly on the rewards and transitions. To this end, we state the following condition.
Condition 1 (Similar Rewards & Transitions) The distribution D satisfies this condition with pa- rameters & Etr 2 0 when:
(a) Each MDP supporting 'D shares the same state-action space S A.
(b) For all M,, Mj supporting 'D and all (s, a) E SSa x A we have [RM, (8, RM, (8, Str
(c) For all M., My supporting D and all (s, a) E S x A we have TT M, (s, T TM, (s) Ew.

---

The parameters fr, ftr naturally quantify the similarity of different MDPs. Conditions of this form are canonical and have yielded fruitful research in classical RL literature [26, 27, 25, 1]. in the guise of the Simulation Lemma (see Section 2). To concretize this condition with an example, consider a suite of simulated robotic goal reaching tasks [48], where the physies simulator the same in each task, so the transitions are fixed and Çir 0. but the goal location changes from task to task, implying that We now establish our Weak Proximity condition, which strictly strengthens Condition
& >
Condition 2 (Weak Proximity) The distribution DD satisfies Weak Proximity with parameters fe, Ste, 2 0 when:
(a) D satisfies Condition with parameters Err 2
(b) There exists a deterministic policy n²' which for any MDP M satisfies VM (**) maxx V (r') aa.
>
Weak Proximity strengthens Condition 1 by additionally requiring (via part (b)) that there exists some policy x" which provides a-suboptimal value for each MDP supporting D. Intuitively, this condition implicitly constrains the MDPs to be similar, since there is single policy which provides (nearly) optimal value, irrespective of the MDP is deployed in. Furthermore, recall from Eqs. (1) & (2) that the objectives of the Average Performance & Meta RL settings are defined in terms of value w.r.t the initial state so- So it is natural to assume, as we do part (b), that there is one policy which provides good value w.r.t so for all MDPs. From an algorithmic perspective, this is helpful, because it ensures that we can restrict our search to those policies which perform well for many MDPs supporting D.
To concretize this condition in our aforementioned example of simulated robotic goal reaching tasks [48], consider suite of tasks where each task has multiple different equivalent goals (so the task is complete when the robot reaches any single one of these goals), but there is only one goal location that shared and invariant across each task. The trajectory that leads to this goal location from so defines policy x², such that for any task M we have V (T max, VM (T'), implying that Weak Proximity is satisfied with a = O.
A Although Condition 1 is natural and well motivated by classical RL literature, it (and Weak Proximity) may seem strong. This is because it requires that each MDP supporting 'D shares the same state space, which may not hold in practice. We stress that we will prove lower bound under Weak Proximity, showing that efficient generalization impossible even in the simpler regime of a shared state space.
We now present Strong Proximity, a condition which strictly strengthens Weak Proximity, We will later show that unlike its Weak counterpart, Strong Proximity indeed permits efficient generalization (when the environments are deterministic).
Condition 3 (Strong Proximity) The distribution D satisfies Strong Proximity with parumeters Ee, Eue, 2 0 when:
(a) D satisfies Condition with parameters Eir 2 O.
(b) There exists a deterministic policy x* which is a near optimal policy for each MDP. Concretely, the policy nt satisfies V (TT) Z max,' V+((=') for each state and each MDP M.
Let us compare Weak with Strong Proximity. Part (a) remains identical. But Weak Proximity (b) only requires a shared policy which provides u-suboptimal value with respect to 8g. This is in contrast to the shared policy in part (b) of Strong Proximity, which provides a-suboptimal value for any state.
3.3 Tractability of Individual Optimization
As discussed previously, in order to efficiently solve Eqs. (1) & (2), we require the property that each individual MDP supporting DD can be efficiently solved. It is natural to expect such property to hold in practice. For instance, the context of our earlier example of simulated robotic goal reaching tasks [48], any individual task can be efficiently solved via policy gradient methods. We now state two such properties, the first of which is strictly stronger than the second. Since these properties require notion of query cost, we state both of them with reference to generic query model QM, and when we later present our results we will instantiate QM to be either SQM or WQM. To avoid complicating notation in these statements, we assume in this subsection (as is our focus throughout
5

---

the paper) that all MDPs supporting D are defined on the same state-action space S x A C R
H=1 Recall that a linear policy π is parameterized by 8 = (OA, h=o where 0n E R and ||0, l|2 = 1 for
all 0 S h I H - 1, such that rTs) E a a) 0), 0n for any E Sn. Here x² y denotes the Euclidean inner product of z, y E R.. We use Ths to denote an arbitrary deterministic optimal policy of MDP M.
Property (Strong Individual Optimization (S1O)) Let the query model be QM. The distribution D satisfies SIO with parameters k > and S B 1/4 when:
(a) Any MDP M supporting D admits an optimal linear policy. Concretely, given any M, there exists 0+ 10% Miz such that for every state Sh, we have (5) E argmax a
(b) There exists a fixed and known algorithm, such that given any MDP M and any state s, this algorithm uses al most O() A H²) query cost (under QM) on M to identify (almost surely) a linear policy (0) parameterized by 0 = (0p 10 -H-1 which satisfies max (M( 2 VM (0) 2
maxx Vād (T²) B. This algorithm then oulputs π (0) as well as Vir
Let us discuss this property. Part (a) requires that for any MDP supporting D, there exists optimal linear policy. Part (b) requires that the user has knowledge of an algorithm, which can efficiently find a linear policy providing B-suboptimal value from any input state in any MDP M. The exponent k describes the (polynomially sized) complexity of this algorithm. We stated the SIO property with respect to generic efficient algorithm, since MDPs with different structures can require different types of algorithms to solve efficiently. Nevertheless, in our lower bound construction, the algorithm we provide to satisfy SIO is extremely simple and natural. It is simply greedy version of Monte Carlo Tree Search, which is extremely popular in practice [29, 40].
SIO is a fairly strong property, since it says that a linear policy is sufficient optimize any individual MDP, whereas in practice one typically requires nonlinear neural network policies. SIO also heavily constrains each individual MDP supporting 'D to be efficiently solvable from any initial state. We stress that we will prove our lower bounds under SIO, which makes our result stronger. Meanwhile, we prove our upper bounds under the following property, which is significantly weaker than SIO.
Property (Weak Individual Optimization (WIO)) Let the query model be QM. The distribution D satisfies WIO with parameter 0 S B < 1/4 when the following holds. There exists an oracle V. which takes as input a state s and MDP M, and outputs V satisfying max,' (T'( 2 V 2 , Vi (x') - 3, via query cost (under QM) on M that polynomial in A H.d.
WIO postulates the existence of an oracle V. which can efficiently approximate the optimal value that is achievable from an input state and MDP. To see that WIO is strictly weaker than SIO, simply note we can implement V by running the algorithm described in part (b) of SIO. Note that in certain states, a user may use domain knowledge implement V without solving an entire RL problem. Also note that WIO does not place (arguably unrealistic) linearity restrictions on the MDPs supporting D.
4 Main Results
We shall present our results in two subsections. In Section 4.1, we prove lower bounds which demonstrate that even under Weak Proximity, SQM and SIO, tractable generalization is worst case impossible. In Section 4.2, we prove that efficient generalization is possible under Strong Proximity, WQM and WIO, when the MDPs supporting 'D share a deterministic transition function.
4.1 Lower Bounds
Before stating our own results, we first state the following classical result which is known as the Simulation Lemma [26, 27, 6, 25, 1]. Recall that & fur are parameters used to satisfy Condition 1.
Lemma Consider any D satisfying Condition I with & Eir 2 0. For any policy n and any M1, M2 supporting D, we have that V M2 (TT) V.59 (T) < & H + En H.

---

This result is almost identical to the one given by [25], although there are some (minor) differences in assumptions so we provide a proof in Appendix D. This lemma shows that when D satisfies Condition 1 and Etr are each of ( ) then efficient generalization is trivial, at least in problems where H is large and we want to optimize to within a(1) tolerance. Concretely, take any M supporting D and use a standard RL method to find ıT which satisfies "M (Tr) z max=' VMP (T'). Then Lemma I
ensures V (I) 2 max, Va (T') o1) for any other MDP M' supporting D. This implies
EM-D M (T)) 2 max,' EM-D [V (m²) - o(1) and V (T) Z maxx Muea (T') ((1).
Since Weak Proximity implies Condition 1, Lemma I and all the above statements remain true when DD satisfies Weak Proximity. Naturally then, in our settings it is only interesting to consider problems when at least one of either & or fir is Q it)) ). Our next result is a lower bound which shows that when & = @ ) and ft. = O, then Weak Proximity is not sufficient to efficiently generalize in the Average Performance Setting. For the statement of this result, recall that &u. Eur, a are parameters used to satisfy Weak Proximity, while 3, k are parameters used to satisfy SIO.
Theorem Let the query model be SQM. For any h 2 3, there exists 'D satisfying Weak Proximity 0 and SIO with ing 'D are deterministic and the following holds. Any (possibly randomized) algorithm requires Q (min {IAA (M, )24) total query cost to find (with probability at least 1/2 over the randomness of the algorithm) policy x satisfying
with & O H ). Etr 0 &
0 & k. such that the MDPs support-
BM M (x)] Z
max lincar policy
EM [V (x') 1 1/4.
We defer the proof to Appendix 1. Let us discuss this theorem, which is stated for the Average Performance Setting, when the MDPs supporting DD all share a deterministic transition function. Recall that SQM is the stronger query model we consider, which strengthens this lower bound, and trivially implies a lower bound for when WQM is the query model. Also recall that SIO is the stronger individual optimization property that we consider, and it ensures that the user can efficiently find a linear policy providing optimal value w.r.t any initial state for any individual MDP, since / O. Moreover, Weak Proximity (b) ensures that each MDP supporting D shares a policy that provides optimal value (w.r.t so). since a = 0. And Weak Proximity (a) explicitly requires that the reward functions are (non-trivially) close, in the sense defined by Condition 1, because & O(+). ). Despite this significant structure, the theorem demonstrates that one can still require an exponential query cost to find policy that is nearly good the best linear policy (which is of course easier than finding the best generic policy). Note that this lower bound holds with a = B = Ete = O, and so implies lower bound for when any of a:, 3, Eir strictly positive. As we discuss at the end of Section 4.1, Theorem I (and its forthcoming corollaries) immediately applies to the task of learning a feature mapping which maps similar states to the same vector, for the purpose of efficiently solving Average Performance and Meta RL settings.
We note that in the construction used to prove the lower bound of Theorem 1, the algorithm we provide to satisfy the SIO property is extremely simple and natural. is simply a greedy version of Monte Carlo Tree Search, which is extremely popular in practice 40].
Let us provide some intuition for our proof of Theorem In the |Allary tree hard instance used in our proof, there are 22 A (") possible trajectories. The fact that &, = O ft)
1 allows us enough degrees of freedom to hide the policy that generalizes across D, so that identifying it requires querying each of the 2 A ( trajectories. We leverage recent techniques [14, 45] to construct suitable featurization of the state-action space, that is expressive enough to allow for efficiently finding an optimal linear policy for any single MDP, but does not leak any further information.
A similar result holds for the Meta RL setting. Recall that by SIO (b), the user has access to an algorithm which can solve any Mjett at test time in O() A ) queries, even if it does no training. So it only makes sense to train, if one can use this training to solve Mtest in o() AA| ( queries. The following corollary Theorem I demonstrates that this may require exponential query cost during training time. Its proof is presented in Appendix A.2.
Corollary Let the query model be SQM. For any k 2 3, there exists DD satisfying Weak Proximity
with &, ( ( Ear 0 & a O and SIO with 3 = 0 & k. such that the MDPs supporting 'D are deterministic and the following holds. I (possibly randomized) algorithm at test time can identify n satisfying
1.80
Maass (T))
max linear policy x"
Mucse (TT') - 1/1
7

---

in ofI ) queries, with probability at least 1/2 over the selection of Miest (and the randomness of the algorithm), then this algorithm must have required Q (min {IA | 24)) total query cost at training time.
So far we have presented results for when the MDPs supporting D share deterministic transition function but have (slightly) varying rewards. For the remainder of Section 4.1, we present analogous results for when the MDPs share a reward function but have (slightly) varying transitions, again under both SIO and SQM. Recall from our discussion of Lemma that when &, O, it is only interesting to consider problems when Şir is S2( / H. Unfortunately, our next result is a corollary of Theorem which shows that efficiently solving the Average Performance Setting is impossible in this regime.
Corollary Let the query model be SQM. For any k 2 3, there exists D satisfying Weak Proximity with & = 0, fur = = & a = O and SIO with B = 0 & k, such that the following holds. Any (possibly randomized) algorithm requires Qi (min [IA| 1a 223) total query cost to find (with probability at least 1/2 over the randomness of the algorithm) a policy x satisfying
E EM (M((T) (T)]
max linear policy of EM (=
We defer the proof to Appendix A.3. We recall the discussion of Theorem 1, and note that the same discussion applies here, after swapping &tr with &. An analogous result holds for the Meta RL setting. As we discussed before presenting Corollary 1, it only makes sense to train, if one can use this training in order to solve Mtet in o( A H queries. The following result shows that this is impossible without exponential total query cost training time. Its proof is presented in Appendix A.4.
Corollary 3 Let the query model be SQM. For any k 2 3, there exists D satisfying Weak Proximity
with & = 0. &tr = O x & 0 and SIO with 3 = & k; such that the following holds. If (possibly randomized) algorithm at test time can identify π satisfying
Menes
2
I88 linear policy x²
V
Viraune (TT) 1/4
in of1 A ) queries, with probability at least 1/2 over the selection of Meest (and the randomness of the algorithm),, then this algorithu must have required Q (min {IAA| |H 24)) total query cost at training time.
In conjunction with Lemma 1, the results of Theorem 1 and Corollaries 1, 2 & 3 suggest that the classical (and quite natural) way of measuring variation in MDPs using Condition I is not the right metric for the modern Average Performance & Meta RL settings. When both & and Eir are of ()), then these settings are trivially solvable. But when either & or for is O ( then these settings become exponentially hard, even under the additional Weak Proximity condition as well as SIO & SQM.
Note that Theorem and Corollaries 1, 2 & all hold in the setting where each MDP supporting D shares state-cction space. So these lower bounds immediately apply to more complex settings where the MDPs are defined on disjoint aatt-accionn spaces, and where learning an appropriate representation is necessary. Indeed, it is popular in practice to learn a feature mapping which maps similar states to the same vector. Our results show that such a mapping enables efficient solution of the Average Performance & Meta RL settings, then learning the mapping itself is worst case inefficient.
4.2
Upper Bound
We now show that Strong Proximity permits efficient generalization when the MDPs supporting D share deterministic transitions. While this setting is restricted, study it because Theorem I shows that even this setting can be worst case inefficient under strong assumptions. Furthermore, past literature even traditional RL with single MDP has often focused the deterministic setting [47, 15J. Notably, to prove our upper bound we only require the weaker WQM and weaker WIO. Our method is defined in Algorithm I. It exploits Strong Proximity, which requires the existence of a policy which provides optimal value for each MDP from any given initial state, even though the objectives in Eqs. (1) & (2) are defined only in terms of value w.r.t 80-
Let us describe Algorithm 1. It represents policy æ as a vector which stores one action for each timestep in (0, 10,1... 1........ H 1). It initializes arbitrary π and incrementally updates it at each timestep
8

---

Algorithm Inputs:
horizon length H. distribution D, sample size n, oracle V as defined in WIO
1: Initialize π as an arbitrary function from {0, 1........ /I 1} to A
2: for {0. 1..1.....
1} do
3: for (1.2...7 do
4: Sample M, ~
5: for a E A do
6:
Begin new episode in M, 80
7:
arrive at end if Take action a to arrive at = Tas, (3t, a) and receive Ry, (st, a)
if > 0 then Execute action sequence
8:
9:
Query V to obtain Vig and store Qi,a = RM, (sc. a) + VMs.
end for
11: end for
Store a argmax, ( Ei= Qiar and define T(t) = ae
13: end for
return π
f. At the beginning of any timestep & O, π has been constructed play the action r(t') ay each timestep /' < l. The algorithm then executes {>((") Josr' to arrive at 8t. Crucially, due to the assumption of shared state-action space and shared deterministic transitions, the state 8, is fully determined by æ and does not depend on the particular M, Exploiting WIO, the method queries V to estimate the value in M; of each child state of st. Averaging this estimated value over [M, } yields an estimate the expected value (over the randomness D) of each action at 8t. Finally, the algorithm picks the action d, with the highest estimated value, and updates to play a, at timestep I. This algorithm operates in the standard RL framework and falls under the purview of WQM.
The following result provides a performance guarantee for Algorithm 1. Recall that a, Eus & are parameters used satisfy Strong Proximity and / is parameter used to satisfy WIO.
Theorem 2
Let the query model be WQM. Consider any D satisfying WIO with 3 2 0 and Strong Proximity with Str = 0 and any a. S, 2 O, such that the MDPs supporting DD are deterministic. Fix 6,6 > O, and let be the output of Algorithm I when with
11² 2x log (2H)_4) A samples. Then
with probability at least 1 - 5, we are guaranteed that
EM-D [V (T)) 2 maxEM=D [V)((=)] - 3 H - -3
x!'
Hence the total query cost under WQM required to achieve this guarantee is polynomial in qD. A), H,
We defer the proof to Appendix B. A few comments are in order. First, note that Theorem 2 directly provides a guarantee for the Average Performance setting. It also provides a guarantee for the Meta RL setting, since the ı found by Algorithm will on average perform well for Mest and the user can use л to warm start any finetuning or adaptation at test time. Second, the specified value of n depends only quantities that either known priori chosen by the user. This makes Algorithm 1 parameter free- - the user does not need to know the values of a, 3, Er, Eir to run this method.
Third, note Theorem 2 holds under WIO. By contrast, Weak Proximity was insufficient for efficient generalization even when paired with SIO. This suggests that condition that is both necessary and sufficient for efficient generalization lies somewhere between Weak and Strong Proximity assuming, course, that we do not assume an individual optimization property that is even stronger than SIO. Indeed, SIO is already quite strong, since SIO says that a linear policy is sufficient to optimize any individual MDP, but in practice one typically employs nonlinear neural network policies.
Finally, observe that &. does not appear in the error bound. So & can be arbitrarily large, and Theorem requires no explicit conditions on the reward functions of the MDPs supporting D, as in the sense of Condition 1. Instead, the implicit reward structure induced by the shared nearly optimal policy required by Strong Proximity is sufficient. Comparing this observation with the result of Theorem suggests that the classical explicit constraints on rewards and transitions is not appropriate for modern RL gencralization settings. Instead, implicit constraints of the sort afforded by Strong Proximity offer more fine grained characterization of when efficient generalization is possible.

---

Recall from Theorem that lower bound holds for Weak Proximity and SIO even with a = 3 0. However, Strong Proximity and WIO provide enough structure that the error bound of Theorem can tolerate a, 3 2 O. But these a. 3 terms in the error bound of Theorem 2 scale linearly with H. It natural to question whether this scaling due to a suboptimality of Algorithm or looseness in our analysis. We provide partial answer to this question in Appendix C. where we prove that the dependency on given in the result of Theorem 2 tight within logarithmic factor in H.
5 Discussion
In this paper, we studied the design of RL agents that generalize. We proved that efficient general- ization is worst case impossible, even under structural conditions like Weak Proximity and strong assumptions the query model and tractability of individual MDPs. This result extends the task of learning representations for the purpose of efficient generalization. On the positive side, we pro- vided Strong Proximity, which permits efficient generalization, even under mild assumptions on the query model and individual tractability. Our analysis highlights that classical metrics for measuring similarity of MDPs are inappropriate for modern RI.. It also suggests that condition which is both necessary and sufficient for efficient generalization lies between Weak & Strong Proximity - unless we make (arguably unreasonable) assumptions on the tractability of individual MDPs.
Negative Societal Impacts. Our work theoretical, and we do not foresee any direct societal impacts, at least in the short term. In the long term, work may increase the technological feasibility of developing agents that can be deployed in society. In this scenario, a bad actor may deploy harmful, malicious agents. This must be prevented by properly understanding the technology (which our work aims to do), and working with policy makers to prevent bad actors from accessing it.
I Limitations of Our Work. The primary limitation of our work is that our upper bound has limited applicability. It holds only when the MDPs share a state-action space, and when the MDPs are determinstic, which is very restrictive in practice. Our rationale for working in this restricted setting was due to our lower bounds, which show that even this toy setting can be worst case inefficient, and because it is necessary understand the toy setting before looking more complex scenarios. Nevertheless, our upper bound is several steps removed from the practice of RL. It is best interpreted a preliminary sufficient condition for when efficient generalization is possible, albeit in toy setting, and is far from conclusive on this matter.
Future Work. Note that our upper bound might apply if we are priori given feature mapping which maps similar states different MDPs to the same state space. For example, in self driving, learning drive in different countries might be difficult because the images of traffic signs different. But a known feature map extracts the underlying meaning of these signs, then our upper bound could conceivably apply. The key direction for future work, is how to learn such feature mapping efficiently, while ensuring that it is still useful for generalization.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE1745016. We further acknowledge the support of NSF via RI 2007517 and IIS- 1909816. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
10

---

References
[1] Abbeel and Y. Ng. Exploration and apprenticeship learning reinforcement learning. In
Proceedings of the International Conference on Machine Learning, 2005.
[2] A. Agarwal, S. Kakade, and I.. F. Yang. Model-based reinforcement learning with a generative
model is minimax optimal. In Proceedings of the Conference on Learning Theory, 2020.
[3] R. Agarwal, M. C. Machado, P. S. Castro, and M. G. Bellemare. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. In International Conference on Learning Representations, 2021.
[4] M. G. Azar, R. Munos, and H. J. Kappen. On the sample complexity of reinforcement learning with generative model. In Proceedings of the International Conference on Machine Learning. 2012.
[5] M. Bertran, N. Martinez, M. Phiclipp. and G. Sapiro. Instance-based generalization in rein- forcement learning. In Advances in Neural Information Processing Systems, 2020.
[6] R. I. Brafman and M. Tennenholtz. R-max general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3:213-231, 2003.
[7] E. Brunskill and L. Li. Sample complexity of multi- task reinforcement learning. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2013.
[8] Castro. Scalable methods for computing state similarity deterministic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
[9] P. S. Castro and D. Precup. Using bisimulation for policy transfer in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, 2010.
[10] I. Clavera, A. Nagabandi, S. Liu, R. S. Fearing, P. Abbeel, S. Levine, and C. Finn. Learn- ing to adapt dynamic, real-world environments through metf-reinforcement learning. In International Conference on Learning Representations, 2019.
[11] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman. Quantifying generalization in reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2019.
[12] K. Cobbe, C. Hesse, Hilton, and J. Schulman. Leveraging procedural generation to benchmark reinforcement learning, In Proceedings of the International Conference on Machine Learning, 2020.
[13] S. Du, Y. Luo, R. Wang, and H. Zhang. Provably efficient q-learning with function ap- proximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems, 2019.
[14] S. S. Du, S. M. Kakade, R. Wang. and L. F. Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
[15) S. S. Du, J. D. Lee, G. Mahajan, and R. Wang. Agnostic q-learning with function approximation in deterministic systems: Near-optimal bounds on approximation error and sample complexity. In Advances in Neural Information Processing Systems, 2020.
[16] A. Fallah, A. Mokhtari, and A. Ozdaglar. Provably convergent policy gradient methods for model-agnostic meta-reinforcemmnt learning. arXiv preprint arxiv:2002.05 2020.
[17] J. Farebrother, M. C. Machado, and M. Bowling. Generalization and regularization in DQN.
arXiv preprint /rxiv:/810.001 181000// 2018.
[18] F. Feng, W. Yin, and I.. F. Yang. Does knowledge transfer always help learn better policy? arXiv preprint arxiv: /91200//9/.02986 2019.
[19] N. Ferns, P. Panangaden, and D. Precup. Metrics for finite markov decision processes. In Proceedings of the Conference on Unceriainty in Artificial Intelligence, 2004.
[20] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep
networks. In Proceedings of the International Conference on Machine Learning, 2017.
[21] S. Gu, E. Holly, T. Lillicrap, and S. Levine. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In Proceedings of the IEEE International Conference on Robotics and Automation, 2017.
11

---

[22] T. Haarnoja, V. Pong. A. Zhou, M. Dalal, P. Abbeel, and S. Levine. Composable deep reinforce- ment learning for robotic manipulation. In Proceedings of the IEEE International Conference on Robotics and Automation, 2018.
[23] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[24] N. Jiang. PAC reinforcement learning with an imperfect model. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[25] S. Kakade, M. Kearns, and J. Langford. Exploration in metric state spaces. In Proceedings of the Interaational Conference on Machine Learning, 2003.
[26] M. Kearns and Koller. Efficient reinforcement learning in factored mdps. In Proceedings of the International Joint Conference on Artificial Intelligence, 1999.
[27] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49:209 232, 2002.
[28] M. Kearns, Y. Mansour, and A. Y. Ng. A sparse sampling algorithm for near- near-optimal planning in large markov decision processes. Proceedings of the International Joint Conference on Artificial Intelligence, 1999.
[29] L. Koesis and C. Szepesvári. Bandit based monte-carlo planning. In Proceedings of the European Conference on Machine Learning, 2006.
[30] C. Lan, M. G. Bellemare, and P. S. Castro. Metrics and continuity in reinforcement learning. arXiv preprint arxiv:2102.01514 2021.
[31] T. Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in RL with a generative model. In Proceedings of the International Conference on Machine Learning, 2020.
[32] A. Lazaric and M. Ghavamzadeh. Bayesian multi-task reinforcement learning. In Proceedings of the International Conference on Machine Learning. 2010.
[33] V. Mnih et al. Human-level control through deep reinforcement learning. Nature, 518:529-533. 2015.
[34] A. Nichol, V. Pfau, C. Hesse, O. Klimov, and J. Schulman. Gotta learn fast: A new benchmark for generalization in RL. arXiv preprint 1o04v:/804.03777 2018.
[35] C. Packer, K. Gao, J. Kos, P. Krähenbühl, V. Koltun, and D. Song. Assessing generalization in deep reinforcement learning. arXiv preprint arxiv: 12282, 2018.
[36] A. Rajeswaran, K. Lowrey, E. V. Todorov, and S. M. Kakade. Towards generalization and simplicity in continuous control. In Advances Neural Information Processing Systems. 2017.
[37] K. Rakelly, A. Zhou, C. Finn, S. Levine, and D. Quillen. Efficient off-policy meta-reinforcement learning via probabilistic context variables. In Proceedings of the International Conference on Machine Learning, 2019.
[38] B. V. Roy and S. Dong. Comments on the du-kakade-wang -aaakade-wang-yang lower bounds. arXiv preprint arxiv: 191.011911.07910, 2019.
[39] A. Sidford, M. Wang, X. Wu, L. Yang, and Y. Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, 2018
[40] D. Silver et al. Mastering the game of go without human knowledge. Nature, 550:354-359, 2017.
[41] A. Sonar, V. Pacelli, and A. Majumdar. Invariant policy optimization: Towards stronger
generalization in reinforcement learning. arXiv preprint arxiv:2006. 200::9000000096, 2020.
[42] X. Song, Y. Jiang, S. Tu, Y. Du, and B. Neyshabur. Observational overfitting in reinforcement learning. In International Conference Learning Representations, 2020.
[43] H. Wang, S. Zheng, C. Xiong, and R. Socher. On the generalization gap in reparameterizable reinforcement learning, In Proceedings of the International Conference on Machine Learning. 2019.
[44] L. Wang, Q Cai, Z. Yang, and Z. Wang. On the global optimality of model-agnostic meta- learning. In Proceedings of the International Conference on Machine Learning, 2020.
12

---

[45] R. Wang, S. Du, L. F. Yang, and R. Salakhutdinov. On reward- seward-free reinforcement learning with linear function approximation. In Advances in Neural Information Processing Systems. 2020.
[46] G. Weisz, P. Amortila, B. Janzer, Y. Yadkor, N. Jiang, and C. Szepesvåri. On query- efficient planning in mdps under linear realizability of the optimal state-value function, arXiv preprint arxiv:2102 02049, 2021.
[47] Z. Wen and B. Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances Neural Information Processing Systems, 2013.
[48] T. Yu, D. Quillen, Z. He, R. Julian, K. Hausman, C. Finn, and S. Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Proceedings of the Conference Robot Learning, 2019.
[49] A. Zhang, N. Ballas, and J. Pineau. A dissection of overfitting and generalization in continuous reinforcement learning. arXiv preprint arxiv:1806. 07937, 2018.
[50] A. Zhang, T. McAllister, R. Calandra, Y. Gal, and Levine. Learning invariant repre- sentations for reinforcement learning without reconstruction, In International Conference Learning Representations, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes].
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 5.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes].
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4 for the complete statements of all the theoretical results, see the beginning of Section for notation and preliminaries, and see Sections 3.2 & 3.3 for the Conditions and Properties that are fundamental to our results.
(b) Did you include complete proof's of all theoretical results? dices A, B, C, & D.
[Yes] See Appen-
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A] No experiments
were run.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] No experiments were run.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] No experiments were run.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] No experiments were run.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] No such assets were used or created.
(b) Did you mention the license of the assets? [N/A] No such assets were used or created.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] No such assets were used created.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] No such assets were used or created.
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No such assets were used or created.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not crowdsource or conduct research with human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We did not crowdsource conduct research with human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did not crowdsource or conduct research with human subjects.
14


Reviews:
[{"review_id": "ojtwdTt5jDj", "reviewer": "Reviewer_yyWK", "summary": "This paper studies conditions on which generalization across tasks in RL is feasible. The authors introduce the concept of Weak Proximity to capture problems where MDPs are similar and each can be easily solved (for the initial state). They show despite such a nice assumption, to enable generalization over the MDP distribution or fast adaption requires exponential complexity (wrt horizon) in general. They further define a Strong Proximity assumption, which enables generalization, though being less practical.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The contribution here is original to my knowledge. The insights here are quite interesting, though in the hindsight obvious (because the authors did a good job in writing the proof).\n\nSignificance: Generalization is an important topic in RL. This paper provides basic principles under which generalization can be feasible in general. These insights would be valuable for future work.\n\nClarity: This paper is very well written, despite its theoretical nature. In addition, the proofs in the appendix are well organized as well.\n\nQuality: I could not find major mistakes in the paper, but I admit I was not able to go through the full appendix. Here're some remarks. \n\n1. The Average Performance setting is a not an MDP but a POMDP problem. I'm wondering if some existing results from POMDP would directly imply the learning difficulty here. \n\n2. Consider an alternate mixture setting where the reward and transition in every time step is independently sampled from a family of MDPs. This is also a common trick people use to enable generalization in practice. Does the learning difficulty still apply? If the MDPs are linear, finding a good policy seems easy. But maybe this is not true with Weak Proximity assumption. Or generally, if the MDPs have Weak Proximity and are linear MDPs of a known feature, does the difficulty still persist?\n\n3. The upper bound requires Strong Proximity \"and\" the MDPs sharing the same deterministic dynamics. However, in the introduction and many other places, it only mentions or only emphasizes the need of Strong Proximity. This can be confusing. Please highlight the two together or bring the assumption on dynamics as part of the Strong Proximity assumption, especially where the Limitation is mentioned.\n\n4. If the optimization oracle can efficiently return all the optimal policies of an MDP, then it seems the difficulty in the counterexample no longer applies? Though this is not provided by the Weak Proximity assumption.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, although the wording about the condition for the upper bound can be more precise.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_nJexlC1uXg", "reviewer": "Reviewer_WHS3", "summary": "The paper provides evidence, in the context of proving generalization in RL, for moving away from classical definitions of proximity typically derived from the simulation lemma (closeness in rewards and transitions across MDPs), and instead, adopting a more fine-grained notion called “strong proximity” which constraints the family of MDPs to have a shared policy with near-optimal value at any state. \n \nThe paper consists of two key results or bounds, assuming a family of MDPs with the same state-action space, deterministic transitions, and the usual simulation-lemma proximity parameters for reward and transitions: \n \n(a) An exponential lower bound on efficiency that uses the a traditional notion of “weak proximity” (assuming a shared policy with near-optimal value from the start state) along with strong assumptions on the solvability of each individual MDP in the family (“Strong Individual Optimization” property) as well as the availability of a generative model which can be queried at any arbitrary state and action (in contrast to episodic RL). This lower bound demonstrates that weak proximity does not admit efficient generalization in the worst case despite these strong assumptions.\n \n(b) A polynomial upper bound on efficiency with the proposed strong proximity property with weaker assumptions on the solvability of each individual MDP (“Weak Individual Optimization”) and relaxing the assumption of availability of a generative model (episodic RL setting). This result, with the proposed algorithm, demonstrates a sufficient condition for efficient generalization.\n \nBoth bounds are proven for the “Average Performance Setting” where the goal is to find an optimal policy over a distribution of MDPs and the “Meta Reinforcement Learning Setting” where the goal is to maximize performance on a test MDP sampled from the same distribution as train and with some fine-tuning.\n", "questions": "", "limitations": "", "rating": 7, "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": "Overall, the paper advances our understanding of the right set of proximity measures that are sufficient for guaranteeing generalization in RL. The lower bound on efficiency with strong assumptions provides a surprising negative result for generalization and the upper bound with weak assumptions paves a path forward given the proposed strong proximity condition. The paper is theoretically sound, very clear in terms of definitions, assumptions, motivations and provides well-written proofs that are accessible to a wider audience. The only weaknesses lie in the inherent assumptions made for each theoretical result in the paper. My rating for this paper is guided by these contributions.\n \nBelow are specific strengths and weaknesses that were considered for my rating.\n \n## Strengths\n1. As stated earlier, the first main result (Theorem 1) which is an exponential lower bound on efficiency with the strong assumptions of individual solvability (SIO) and the availability of a generative model (Strong Query Model) is a surprising negative result. The proof is well-written and constructs a worst-case scenario of a family of MDPs where at least an exponential number of queries need to be made to even reach the “hidden state” from which the shared optimal policy can be obtained. The binary-tree constructions of the MDP family and the featurization of the state-action space that does not leak the location of the “hidden state” (inspired from prior work) lead to an elegant proof of Theorem 1.\n \n2. The proposed strong proximity condition, along with the polynomial upper bound in efficiency given in Theorem 2 (with Algorithm 1) is the main positive result of the paper which hints towards the use of strong proximity-like measures as opposed to classical ones that simply assume similarity in rewards and transitions.\n \n3. The paper is very well-written and excels in clarity, flow and intuitive motivations and explanations of each property, definition and result.\n\n\n## Weaknesses\n\nAs stated in my summary, the only weaknesses of this paper lie in the assumptions made. \n \n1. One of the assumptions is already mentioned as a limitation in the discussion section -- the assumption that the MDPs share a state-action space, which does not hold in most real-life applications.\n \n2. The other weakness is that the lower bound is a “worst case” bound -- it is not often the case that the featurization of the state-action space completely hides the shared near-optimal policy for a family of MDPs. A more relevant (positive or negative) result would be something that relaxes this assumption i.e. allows for informative featurizations and studies similar proximity conditions for guaranteeing generalization efficiency.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed limitations and potential negative societal impacts in the Discussion section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "MP5lhcbLHQy", "reviewer": "Reviewer_q3V1", "summary": "This paper studies the sample complexity of reinforcement learning in families of MDPs that share some notion of structure. The paper considers different notions of structure and sample complexity, and finds that even a relatively strong notion of structure where all MDPs in the family share an optimal linear policy and similar reward/transition functions, finding this shared optimal policy can require time exponential in the horizon of the problem. The paper also presents a stronger notion of structure under which finding a policy that attains near-optimal returns in all environments is tractable. \n", "questions": "", "limitations": "", "rating": 7, "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": "Strengths\n\n- Clarity: the paper is very well-written and does a good job at motivating the problem setting. I found the proofs for the most part very clear and appreciated the intuition given in the main body\n. \n- Novelty: While prior work has studied the sample complexity of multi-environment RL, I am not aware of any existing literature that explicitly studies the type of shared structure needed for generalization to new environments to be tractable. \n\n- Significance and relevance to the community: a lot of the empirical meta-RL literature implicitly assumes some notion of shared structure between tasks but doesn’t quantify this explicitly. This paper seems like an interesting first step towards characterizing what kinds of shared structure are necessary for policies learned in one environment to generalize to others.\n\n- Technical correctness: I didn’t spot any errors in the proofs included in the appendix. \n\nWeaknesses:\n\n- The main “trick” to get lower bounds involves turning the problem of finding a shared optimal policy into a brute-force search over a set of states of size exponential in the horizon. While this is a nice proof of existence, most of the work on sample-efficient RL I’m aware of tends to include the size of the state space in the sample complexity. As a result, the exponential sample size requirement looks like it ends up becoming linear in the size of the state space, which doesn’t seem to be a particularly concerning lower bound. It seems like the increased sample complexity over the single-environment setting would then come from the power of the oracle being used to identify the policies. Would the exponential increase in sample complexity still hold if the query model assumes complexity linear in the size of the state space to compute the value of a state?\n\n- The Strong Proximity assumption is indeed very strong and severely limits the generality of Theorem 2. In most settings of interest we cannot say that a deterministic optimal policy is shared by all of the environments in all states, particularly when the rewards are permitted to vary .\n\n- The optimization oracles (even the weaker “WIO”) seem very strong. As mentioned previously, it seems like a fairly large assumption to assume that the value oracle can output the value of a state in sample complexity polynomial in the horizon and constant in the size of the state space. \n\nMinor points:\n\nI think a visualization of the MDP structure used for corollary 2 would be useful to improve clarity, as it took me a couple of reads to fully understand how all of the states were connected. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theoretical work, N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "Id9Zfgsh83", "reviewer": "Reviewer_q4SK", "summary": "This paper studies theoretically the challenge of learning policies that generalize and establish bounds showing (1) in the worst case tractable generalization is impossible; but (2) can be efficiently learnt in cases that meet the conditions proposed for strong proximity.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "The paper is timely given significant interest across the community in enabling reinforcement learning to generalize beyond the training environment and provides novel insights into when the task is and is not tractable. The clarity of the goals of this paper could be improved by formally establishing earlier on what conditions the authors have chosen for classifying a solution as tractable.\n\nThe bounds are limited in relevance to environments that share state-action spaces, but this assumption is clearly stated on page 2 of the paper, discussed in the limitations of the work and still provides novel insight.  The clarity of these assumptions could be improved by using a concrete example (e.g. a gridworld) throughout as a narrative tool (Please note I am not implying empirical results are needed, only that a concrete example can help readers quickly assess the relevance of theory to their applications).\n\nSimilarly, on page 5, the definition of strong individual optimization assumes there is an efficient algorithm for learning a policy to a single MDP without linking interested readers to existing published methods that have been proven to meet these requirements. If there are none, then this is an interesting point to highlight for others to pursue in future work. Negative examples of well established methods that do not meet these requirements could also be useful to help readers connect theory to practice.\n\nThe lower bound demonstrates worst case under weak proximity, strong query model and strong individual optimization but it remains unclear to me what happens under other combinations? In particular, as the upper bound is proven for strong proximity even with a weak query model and weak individual optimization, can it be implied that weak proximity alone makes generalization intractable? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper gives a refreshingly open-minded discussion of limitations and potential for long-term negative societal impacts. In particular, I appreciate the authors efforts to use this as a way to further clarify the limits of these findings and motivate future work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the important problem of generalization in RL. The authors proposed different metrics of similarity between MDPs and derive negative or positive results depending on the strength of the assumption. Based on reviews and rebuttal, I believe this a solid paper with interesting and non trivial results. Some assumptions seem rather strong but I'm persuaded that the paper is an interesting starting point for further research on the topic. So I'm proposing acceptance for it.


Decision: Accept (Poster)