Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: Strengths
- (Relevance) The paper addresses the interesting problem of pre-training a set of policies for efficient RL at test time;
- (Originality) The paper introduces several original ideas, including interesting problem formulations and algorithms to pre-train policy sets.

Weaknesses
- (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;
- (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;
- (Unreasonable results) Some of the theoretical statements are so strong that look unreasonable (though I am probably missing something);
- (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;
- (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.

Comments

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

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

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

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

(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?
clarity,_quality,_novelty_and_reproducibility: The presentation is overall confusing, and it does not help evaluating the contribution of this paper. Notation is not always sharp or intuitive, some symbols are never defined, there are a few sloppy claims and confusing comments. Presentation issues include:
- The paper often refers to "learning/knowing $\mathbb{D}$", but the algorithms actually learn set of policies and not the task distribution;
- The cardinality of the set of MDPs is denoted sometimes with $\Omega$ and sometimes with $M$ (I am not sure the latter symbol have been introduced actually);
- Algorithm 1 reports a symbol $\mathcal{U}$ that is defined in the appendix. The Subroutine 4 is only reported in the appendix though it is crucial to understand the algorithm;
- It is not clear how many times the loop at line 3 of Algorithm 1 has to be executed.
- "We select $(\pi_l, v_l)$ with the most optimistic value $v_l \in \Pi_l$". It is not clear how the value can be (optimistically) estimated without knowing the true test MDP;
- "$\mathcal{C} (\mathbb{D})$ is still bounded". Not clear why.
summary_of_the_review: *After discussion*

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

---


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

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

I 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength
- 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.
- 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.
- The authors do a good job at contextualizing and explaining the theoretical implications and ramifications of their derived bounds.
- The paper is well-structured and clearly written.
- Appropriate literature review to contextualize the contributions

Weakness
- 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?
- The proposed bounds and algorithms assume the pretraining and test environments are sampled iid while pretraining is especially hoped to help in OoD scenarios.

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, and the theorems are well-presented and contextualized. The derived regret bounds in the particular pretraining setting with test-time interaction considered by the authors are novel to the best of my knowledge.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
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:
 
1. 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?
 
2. 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. 
 
In 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?
 

clarity,_quality,_novelty_and_reproducibility: Good. 
summary_of_the_review: This is an interesting paper but the theory part is less strong.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the theoretical benefits and limitations of pre-training on generalization of RL. It shows that asymptotically, the improvement from pre-training and knowing the MDP distribution D is at most a constant factor when the agent can interact with the environment at test time. The authors then designed algorithms in the non-asymptomatic case, for which pre-training helps and  derived a regret bounds depending on the complexity measurement on the MDP distribution D. 

 The reviewers remained split after the rebuttal and offline discussion. One reviewer consider it an important theoretical work "establishing (previously unknown) statistical barriers on RL generalization across environments", while the other reviewers remain skeptical on the "applicability and usefulness of the presented algorithms". The paper follows closely prior work on "When Is Generalizable Reinforcement Learning Tractable?", which also 1) studies generalization of RL across environments, 2) points to the conclusion that "tractable generalization is impossible in the worst case" despite strict conditions on the environments, and 3) proposes algorithms that improves generalization under strong proximity condition. Unfortunately the authors only mentioned the prior work in related work section and fail to address the connection and difference of the proposed work vs prior work. IIUC, the paper designed algorithms and derived regret bound under weaker conditions on the environments. But it is hard to compare generalization of the proposed algorithms vs prior work say under the same condition. Without properly setting the context and comparing to the related work, it is hard to gauge how much additional theoretical value is provided. With the additional caveat of missing any empirical validation of the proposed algorithms, we are not comfortable accepting the paper as is.
justification_for_why_not_higher_score: Missed connection and comparison to important related work. Missed empirical validation of the applicability of the proposed algorithm.
Decision: Reject