Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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).

Significance: 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.

Clarity: This paper is very well written, despite its theoretical nature. In addition, the proofs in the appendix are well organized as well.

Quality: 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. 

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

2. 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?

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

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

limitations_and_societal_impact: Yes, although the wording about the condition for the upper bound can be more precise.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
 
The 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: 
 
(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.
 
(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.
 
Both 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.

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.
 
Below are specific strengths and weaknesses that were considered for my rating.
 
## Strengths
1. 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.
 
2. 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.
 
3. The paper is very well-written and excels in clarity, flow and intuitive motivations and explanations of each property, definition and result.


## Weaknesses

As stated in my summary, the only weaknesses of this paper lie in the assumptions made. 
 
1. 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.
 
2. 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.

limitations_and_societal_impact: The authors have adequately addressed limitations and potential negative societal impacts in the Discussion section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

main_review: Strengths

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

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

- Technical correctness: I didn’t spot any errors in the proofs included in the appendix. 

Weaknesses:

- 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?

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

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

Minor points:

I 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. 
limitations_and_societal_impact: Theoretical work, N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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).

Similarly, 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.

The 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? 
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_title: null

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)