Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the capacities and limitations of return-conditioned supervised learning (RCSL) methods and illustrates their relationship to behavior cloning (BC) and dynamic programming (DP). The main conclusion is that RCSL methods are theoretically incapable of achieving high performance when the underlying environment is non-deterministic and the return coverage is insufficient. These findings are both intuitive and theoretically sound.
strengths_and_weaknesses: The novelty of this paper lies in the theoretical part. The authors start with the setting with infinite data and a fully expressive policy and then extend the derived theorems to a more practical setting with finite data and a limited policy class. The theoretical derivations are solid and the theorems are easy to understand. The core conclusion is that RCSL is fundamentally limited when the environment is stochastic and the return coverage is insufficient, which is intuitive and theoretically sound. However, from my perspective, I think the authors should strengthen the experimental parts. For example, to verify that RCSL is indeed limited to near-deterministic environments, the authors should conduct experiments in environments with different stochasticity.
questions: 1. In the training phase, RCSL minimizes the empirical negative log-likelihood loss described by Equation (1), while the test-time policy is defined as Equation (2). It seems that there is a mismatch between the training-time policy and the test-time one: the training-time policy is conditioned on the return of an entire trajectory $g(\tau)$ but the test-time policy is conditioned on a condition function $f(s)$ which varies with the states in a trajectory. The authors should explain it. Besides, will this discrepancy affect the conclusion?
2. The authors did not pre-define the variable $N$, which firstly appears in line 182 and Equation 9. (I guess it refers to the dataset size)
3. Though the authors claim that RCSL is incapable of learning high-performance policies when the environment is stochastic, which is described by Theorem 1 and explained by Figure 1, I think the authors may construct toy MDPs to provide experimental evidence in the experimental part.

limitations: It would be better if the authors could conduct experiments to support their theoretical claims. For example, experiments investigating the return coverage and stochasticity of the dataset and the environment, respectively.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper theoretically analyzes a new popular class of RL algorithms, referred to as Return-Conditioned Supervised Learning (RCSL). The paper theoretically shows that this class of method requires stronger assumptions than standard DP-based approaches for learning the optimal policy. The paper shows that RCSL method requires near-deterministic dynamics as well as a priori knowledge of the optimal conditioning function to perform well, and construct examples where the stated assumptions are necessary for empirical performance. 
strengths_and_weaknesses: Strength:
1. This paper is solid in all four axis: originality, quality, clarity, and significance. It is the first paper to provide a theoretical analysis of a new class of practically relevant RL algorithms. The exposition is clear, and the theoretical results are mostly proper (though, I did not check the supplement fully). The experiments are well thought out, and complement the theoretical analysis. Given that this class of algorithm has received significant attention from the RL community, this work is timely and relevant. 

Weakness:
1. It's unclear that under deterministic dynamics, RCSL can recover the optimal policy, is a novel result. Under this assumption, the return can be practically treated as a new state-dimension, and RCSL reduces to Behavior Cloning with an augmented state space.
2. The dependence on the size of the policy class needs to be clarified when comparing RCSL and DP-based algorithms in Section 5. Even in the tabular case, just to represent the policy, it would require a lookup table that is exponentially larger than what is required to represent a standard policy for DP approaches (i.e, |S||A|). For this reason, it's not clear that the comparison is super meaningful. 

questions: 1. It's unclear what insight Section 6.2 adds; I believe similar findings have already been reported in prior papers, for example, https://arxiv.org/abs/2112.10751. 

I am willing to increase my score if the authors can address my qualm about the theoretical analysis in the above section. Overall, this is a sound paper. 
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper discuss the conditions that return-conditioned supervised learning (RCSL) work for offline reinforcement learning (RL). This paper mainly contributes theoretically on the optimality of the RCSL algorithms and the sample complexity of the RCSL algorithms. Under some strong assumptions, they present theoretical guarantees for RCSL given both infinite data and finite data. Furthermore, empirical evidence on failure and success of RCSL methods are provided.
strengths_and_weaknesses: **Originality and Significance**: this paper is quite original, which theoretically studies a very new topic in RL. The conclusions in this paper is of importance to the RL community, and can benefit the progress of offline RL

**Quality**: this paper has a good quality overall. The theoretical results seem sound to some extent. The reviewer randomly checked some proofs in the appendix (but not all of them), and they seem correct, despite some minor errors in some of them. For example, in appendix Eq. (56), the reviewer thinks it ought to be $\epsilon (\frac{1}{\alpha_p}+1)$ instead of $2\epsilon (\frac{1}{\alpha_p}+1)$. The theoretical contribution of this paper is clear. While the empirical experiments are kind of disappointing

**Clarity**: this paper is of medium clarity. The reviewer likes the way the authors tell a story like this. While the figures are of poor quality, which negatively affect the clarity of this paper. Some figures, e.g. figure 3 and 4, are sort of blur.

**Summary of Strengths**:

a) the discussed topic is important and interesting. It is vital to figure out when and under what conditions will RCSL work for offline RL

b) the theoretical contribution of this paper is of importance to better understand "when return-conditioned supervised learning work for offline reinforcement learning"

c) the toy examples presented in the paper is quite helpful to understand why RCSL fail in stochastic environments

**Weaknesses**:

a) some of the figures are blur.

b) there are some grammatical issues, e.g., line 199 "To see why this is the case, consider the MDP illustrated" --> "To see why this is the case, we consider the MDP illustrated". Please do not use colloquial expressions in submitted papers. While this is just a random example. Please double check the paper to ensure that there are no grammatical issues.

c) the discussion lacks depth. For example, in Section 5.1, the authors compare the sample complexity bound of RCSL and dynamic programming (DP). The reviewer cannot tell what is the point here, since the basic assumptions for these bounds are different. Whereas the bound for top-%BC are omitted in the main text. Meanwhile, the discussion in Section 5.1 does not reveal why RCSL fails while DP-based methods work.

d) the empirical evidence is expected to be enriched. Currently, RCSL is only tested on some selected datasets, e.g., 1 D4RL MuJoCo dataset, 1 D4RL Adroit dataset, and 2 D4RL Antmaze datasets. RCSL fails/underperforms baselines on 3 out of 4 datasets. The reviewer agrees that MuJoCo/Antmaze datasets come from "stochastic" environments. While there is only one single test on datasets with narrow distribution (e.g., human). The reviewer cannot say that it can convince readers on the proposed claims in the paper.
questions: The reviewer has the following several questions:

a) why discussing the connection of RCSL to distributional RL? They actually lie in quite different categories.

b) the theoretical results in appendix (on top-%BC) also involve the assumption of "near determinism". Then will top-%BC fail on stochastic environments? If we include all the data, i.e., top-100% BC or vanilla BC, are the derived bounds still meaningful? Any discussion here?

c) the authors claim that DP-based methods are often "unstable and difficult to debug" (line 371-372), then are RCSL methods easy to debug and exhibit stability during training? Why RCSL methods are easy to debug? It is hard to say that decision transformer (DT) is easy to tune and debug.

d) what is the benefits of RCSL on earth? Since IQL, a DP-based method, shows very good performance over all of the tested datasets. Does there exist some methods that can make RCSL work in stochastic environments? The authors mention that trajectory transformer works on MuJoCo datasets as it involves planning, will planning breaks this dilemma?
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers return-conditioned supervised learning (RCSL), a class of methods that learn a return-conditioned policy from offline data and recover the evaluation policy by conditioning on a given desired return. It then analyzes these method theoretically, bounding the regret of RCSL policies under the assumption of close-to-deterministic transitions&rewards and return-coverage of the behavior policy. Moreover, the paper provides examples of MDPs where RCLS is not able to recover the optimal policy, which demonstrate that the additional assumptions are required. Lastly, in the experimental evaluation the paper shows on a toy-example scenarios where dynamic programming has advantages over RCSL and also evaluate performance on the D4RL dataset.
strengths_and_weaknesses: The paper is clearly written, easy to follow, and studies a class of methods that has been of interest lately. The theoretical analysis clearly illustrates when we can expect RCSL to work and the example-MDPs are useful to understand when it doesn't. The comparison to dynamic programming and behavior cloning is interesting, but comparing lower-bounds would probably be more convincing. The experiment section illustrates the main points of the paper, but is relatively limited in scope.
questions: Overall I think this is a well-written and interesting paper. It would perhaps be useful to explicitly state a lower-bound on performance given that the introduction is largely motivated from that perspective. It would be nice to expand the experiment section a bit further: For the toy-example and ablation study on how performance changes depending on the behavior policy would be useful and more D4RL baselines could be run. For the latter it would be particularly interesting how performance compares on different behavior datasets for the same environment.
limitations: While the theory clearly states its assumptions, limitations of the analysis are not discussed.
review_title: null

Meta-review: metareview: This paper theoretically analyzes a new popular class of RL algorithms, referred to as Return-Conditioned Supervised Learning (RCSL). The paper theoretically shows that this class of method requires stronger assumptions than standard DP-based approaches for learning the optimal policy. The paper shows that RCSL method requires near-deterministic dynamics as well as a priori knowledge of the optimal conditioning function to perform well, and construct examples where the stated assumptions are necessary for empirical performance.

This paper is solid in all four axes: originality, quality, clarity, and significance.  All reviewers advocated for acceptance.


confidence: Certain
Decision: Accept