Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This is a strong paper that is well-motivated and well-written. I enjoy reading the paper, thinking about the questions and learning the new results.

Contribution on problem formulation: The paper provides a new offline RL framework that accommodates the entire data composition range, smoothly interpolating between two regimes: expert data and data with uniform coverage. 

Contribution on algorithm design and the upper bounds: The paper provides a lower-confidence-bound algorithm that achieves almost optimal performance in multi-armed bandits and MDPs, and optimally solves the offline learning problem in contextual bandits. It is interesting to see that in all the three settings, LCB achieves a faster rate of 1/N for nearly-expert datasets compared to the usual rate of 1/\sqrt{N} in offline RL.

Contribution on the lower bounds: The paper provides information-theoretical lower bounds to capture the fundamental hardness for this new offline RL framework. The paper also has interesting discussion on whether the knowledge of C* is necessary to design optimal algorithm.
main_review: This paper is really well-written. The authors think about the questions throughly and do a very complete study. I particularly like the fact that the proposed LCB algorithm is very simple and intuitive. I think the paper is self-contained and addresses its two proposed questions very well. 

The paper make contributions in both the problem formulation and a bunch of new theoretical claims (some of them are insightful). On the other hand, it is not clear whether the existing theoretical claims have significant technical challenges that require very original methodology. If there are, it may be good to add some high-level descriptions in Section 6 and discuss whether the proof techniques can be used to analyze other problems. I appreciate that the author point out the technical hurdle to improve their current results and close the gap.

I did not read the proofs but the results looked solid (based on the writing and the organization of their theoretical claims). 
limitations_and_societal_impact: I like what the authors honestly point out in the checklist question 1(b). For me, a major limitation of the work is that all the results are limited to the tabular setting, which is fairly well-studied in both the realm of online RL and the realm of off-policy evaluation. It is not clear whether the new concept of C* is still fundamental and meaningful when the cardinality of states is very large. But this is still a clear accept given that the paper is already full and addresses the tabular setting throughly.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to bridge the gap between offline reinforcement learning algorithms that are “vanilla” (which perform well in the “diverse data” regime) and ones based on imitation learning (which perform well in the “optimal data” regime). They propose and study an algorithm with pessimism that performs well both in the diverse data regime and in the optimal data regime, and prove bounds on the error of their approach.
main_review: Strengths
- Important problem
- Interesting theoretical analysis
- Upper and lower bounds

Weaknesses
- Doesn’t compare to MOPO, even though the algorithms are similar
- Motivation is model-based vs. model-free, but they are purely studying model-based approaches

This paper is studying an important problem. There are significant differences between the two classes of algorithms (vanilla vs. imitation learning), and understanding which of these approaches is ideal or how to combine them is an important research direction.

However, I’m not sure this paper really addresses this problem. My main concern is that their algorithm closely resembles the MOPO algorithm [51], which uses a pessimism term to penalize parts of the state space with high uncertainty. In particular, for finite MDPs, this pessimism term can be instantiated with rigorous bounds based on the state-action visitation counts, which is similar to how the pessimism term in this paper is defined. Furthermore, the MOPO paper includes an error guarantee that appears to be quite similar to the one achieved by the authors (in particular, by using the total variation norm on the transition probability estimates). Thus, it is not clear to me that the authors’ algorithm and analysis are novel.

A related issue is that in their related work, the authors claim that there is a gap between model-free and model-based approaches in terms of pessimism, and that their work aims to clarify this gap. However, since the authors’ paper is model-based, I’m not sure how it achieves this goal.

Finally, the authors do not provide any experimental results to validate their approach. Given that the performance tradeoffs are primarily of interest from an empirical point of view, I think experiments would be very helpful in clarifying this paper’s insights.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors present a new offline RL framework that builds the gap between imitation learning (data are generated by experts) and vanilla offline RL (data are generated with large coverage). Under this framework, the authors consider the Lower Confidence Bound (LCB) algorithm and obtain adaptive optimality on Contextual Bandit problem, sub-optimality for Multi-arm Bandit problem and conjecturely adaptive optimality for MDP. 
main_review: Strength:
- The paper is very clear and well-written. Though many theorems are proposed, the paper is easy to follow by only listing the theorems and their intuitive explanations. 
- The new framework of constructing bounds on single policy concentrability assumption is neat and clean: it covers the entire data spectrum and is applicable to all three cases (MAB, CB and MDP)

Weakness:
- The adaptive optimality of LCB on MDPs is not proved completely.  



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work presents a simple algorithm for offline reinforcement learning based on optimizing the sum of lower confidence bounds of rewards for each transition (where the confidence bound is constricted using the offline dataset of transitions).  Theoretical bounds are given on the suboptimality of the resulting policy, based on the quantity $C^*$, which bounds the proportion of non-optimal transitions in the dataset.  Conditional on there being a finite ratio of non-optimal to optimal actions in each state, the presented algorithm has good performance in both the "expert data" case, in which the behavioral policy that generated the data is close to optimal, and the "uniform coverage" case, in which the behavioral policy covers all possible transitions.

main_review: Overall, the paper is clearly written, and the problem is important.  I did not carefully check the proofs, but clear intuitions are provided for the results.  The paper does a good job of focusing on the important details, and of expressing why the results are significant.

My main concern is with the novelty of the results; the following paragraph on p.3 is very worrying:

> A similar algorithm design has recently appeared in [16]. It turns out that such a simple algorithm—fully agnostic to the data composition—achieves almost optimal performance in multi-armed bandits and MDPs, and optimally solves the offline learning problem in contextual bandits.

This sounds like more or less exactly the results of the current paper.  Could the authors comment on the differences between [16] and this work?

I am going to rate the paper lower than I otherwise would in light of this question about novelty, but I am willing to increase my rating if the novelty question is addressed to my satisfaction.

#### Minor comments:

* p.2: "Assuming a finite $C^*$ is the weakest concentrability requirement [39, 12, 48] that is currently enjoyed only by some online algorithms such as CPI [17]": It's not clear what this means.

* p.6 L227: The subscripts on the expectation operator seem inconsistent; $\mathcal{D}$ is a random variable, and $\rho$ is a distribution, so what do these signify?

* p.7 L248-255: These paragraphs are very helpful and give exactly the right amount of detail.

* alg.2: Are rewards assumed to have a maximum magnitude of 1 here?  I can't make sense of $V_{max} = (1-\gamma)^{-1}$ otherwise.

* p.5: Should the inequality in equation (3) be $\lesssim$?

* p.7: Similarly, should the inequality in prop.3 actually be $\gtrsim$?

* p.9 L323: $a$ is free in the definition of $g(s)$; what is it meant to bind to?
limitations_and_societal_impact: The authors have done a good job of specifying the technical limitations of their work.  I do not see any societal impacts that require further comment.
review_title: null

Meta-review: Authors show novel and interesting theoretical results that provide scale-sensitive minimax upper and lower bounds to off-policy learning, which correctly quantify the difficulty of the problem as the behavior policy becomes near-optimal. I agree with the reviewers that the contributions are significant and substantive. 
Decision: Accept (Poster)