Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: **Summary:**

This paper attempts to unify prior work on fixed-dataset (aka "batch" or "offline") reinforcement learning. Specifically, it emphasizes the importance of pessimism to account for faulty over-estimation from finite datasets. The paper shows that naive algorithms (with no pessimism) can recover the optimal policy with enough data, but do so more efficiently. The pessimistic algorithms are divided into "uncertainty-aware" and "proximal" algorithms where the uncertainty-aware algorithms are shown to be more principled, but most prior work falls into the computationally easier proximal family of algorithms that is closer to imitation learning. These insights are proven both theoretically and with some small experiments.

--------------------------------------------------------------------

**Strengths:**

1. A nice decomposition of suboptimality. The main workhorse of the paper is the decomposition provided in Lemma 1 which is novel and can provide some good intuition about the necessity of pessimism (although the intuition is only given in appendix G.3, which should definitely find it's way into the main text). The Lemma cleanly and formally demonstrates why we may expect over-estimation to be more damaging than under-estimation.
2. A clear framework to examine prior work. The paper does well to capture the majority of recent work into a few broad families of algorithms: naive, proximal pessimistic, and uncertainty-aware pessimistic. The bound derived from the main Lemma for each algorithm family provide evidence to prefer uncertainty-aware algorithms. This is supported by the tabular experiments.
3. The formal statements of Lemmas and Theorems seem to be correct and experimental methodology seems sound.

--------------------------------------------------------------------

**Weaknesses:**

1. I am wary of the comparison of upper bounds done in the paper. Just because one algorithm has a lower upper bound does not prove superior performance. I agree that since all the proofs are derived from Lemma 1 and are very similar, the differences are indeed suggestive. However, the bound in Theorem 3 seems to be more loose than the others. For example, when $\alpha = 0$ it does not recover the bound for the naive algorithm as would be expected. A more measured tone and careful description of these comparisons is needed. Claims like "uncertainty-aware algorithms are strictly better than proximal algorithms" in the conclusion are not substantiated. 
2. Lack of discussion of issues with implementation and function approximation. As the authors get into in Appendix G.6 and Appendix F.2 and briefly in the paper it is not clear how to implement the uncertainty-aware family of algorithms in a scalable way. I am not saying that this paper needs to resolve this issue (it is clearly hard), but this drawback needs to be made more clear in the main text of the paper, so as to not mislead the reader.
3. Notation is heavy and sometimes nonstandard. I understand that the nature of this paper will lead to a lot of notation, but I think the paper could be made more accessible if the authors go back through the paper and remove notation that may only be needed in the proofs and may be unnecessary to present the main results. For example, the several different notions of uncertainty funtions might be useful in the appendix, but do not seem to all be necessary to present the main results. Similarly, the notion of decomposability is introduced and then largely forgotten for the rest of the paper. Some notation is nonstandard. For example: $d$ is used for number of datapoints (usually it would be dimension) and $ \Phi$ is used as the data distribution (usually if would be a feature generating function or feature matrix).
4. Abuse of the appendix. While I understant that the 8 page limit can be difficult, this paper especially abuses the appendix often sending important parts of the discussion and intuition for the results into appendix G. The paper would be stronger with some editing of the notation and organization of the main text to make room for more of the needed discussion and intuition in main body of the paper.

--------------------------------------------------------------------

**Recommendation:**

I gave the paper a score of 7, and recommend acceptance. The paper provides a nice framing of prior work on fixed-dataset RL. While it leaves some things to be desired in terms of carefulness, scalability, and clarity, I think it provides a solid contribution that will be useful to researchers in the field.

If the authors are able to sufficiently improve the clarity of presentation as discussed in the weaknesses section, I could consider raising my score.

--------------------------------------------------------------------

**Questions for the authors:**

1. It is natural to think that a practical proximal pessimistic algorithm would reduce the level of pessimism with the dataset size (so that it approaches the naive algorithm with infinite data). Do approaches like this resolve many of the issues that you bring up with proximal pessimistic algorithms (albeit by introducing another hyperparameter to tune)?

--------------------------------------------------------------------

**Additional feedback:**

Typos:

- The first sentence on page 4 is not grammatically correct.
- In the statements of Lemma 1 and Theorem 1, $ \pi^*_D$ is defined and never used.
- In the statement of Theorem 1 $ u_{D,\delta}^\pi$ is defined but then only $ \mu_{D,\delta}^\pi$ is used without being defined.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

The paper proposes a theoretical framework for analyzing the error of reinforcement learning algorithms in a fixed dataset policy optimization (FDPO) setting.  In such settings, data has been collected by a single policy that may not be optimal and the learner puts together a model or value function that will have explicit or implicit uncertainty in areas where the data is not dense enough.  The authors provide bounds connecting the uncertainty to the loss.  They then show that explicitly pessimistic algorithms that fill in the uncertainty with the worst case can minimize the worst case error.  Similarly, proximal algorithms that attempt to adhere to the collection policy (as often the case in model-free batch RL) have improved error compared to a naive approach but not as good as an explicitly pessimistic approach.


Review:

The paper provides a general description of the pessimism performance bounds.  The theorems appear to be correct and the reasoning sound.  I also like the connection to the proximal approach, which is how most model-free batch RL algorithms approach the problem (by sampling close to the collection policy).

However, the paper does need some improvement.  Specifically, a connection should be made to more existing literature on pessimism in safe, batch, or apprenticeship RL.  In addition, the paper spends a lot of time on definitions and notation that are not explicitly used while the most interesting empirical results are relegated to the appendix, which seems backwards.

On the connections to the literature, the idea of using pessimism in situations where you are learning from a dataset collected by a non-optimal teacher has been investigated in previous works in apprenticeship RL:
http://proceedings.mlr.press/v125/cohen20a/cohen20a.pdf
or
https://papers.nips.cc/paper/4240-blending-autonomous-exploration-and-apprenticeship-learning.pdf 

Specifically, the first (Bayesian) paper explicitly reasons about the worst of all possible worlds mentioned in the current submission and seems to have a lot of overlap in the theory.  Can the authors distinguish their results from Cohen et al.?  The second paper is an example where model-learning agents keep track of the uncertainty in their learned transition and reward functions and use pessimism to fill in uncertainty.  So the idea here is not quite new and better connections to this literature need to be made.

The other issue with the paper is its organization and writing. The theoretical results, while general, are not particularly complicated and don’t seem to warrant the amount of notation and definitions on pages 1-3.  Specifically, the bandit example isn’t really mentioned in the paper but the figure takes up a lot of valuable space.  Over a full page is used to define basic MDP and dataset terms that are widely known and commonly used.  The footnotes are whole paragraphs that seem to be just asides.  Finally, the grid word results are presented in a figure without any real associated text except for some generalities about what algorithms worked well,  Meanwhile, the most interesting and novel contributions of the paper, including the concrete algorithms for applying pessimistic learning, and the empirical analysis on Atari games, are stashed in the (very long) appendix.  I strongly suggest the authors reorganize the paper to highlight these strengths instead of notation and footnotes that are tangential to the paper.

review_title: needs better organization and some missing related work

final_score: rating: 6: Marginally above acceptance threshold
review_content: The message of this paper is that naive policy evaluations common in current (deep) RL algorithms, can lead to a dangerous overestimation of the value function. This overestimation of the value function can then lead to policy improvements with poor theoretical guarantees. To combat overestimation, the authors propose to penalize state-action pairs that are rarely visited. As an easier to implement alternative, and closer to existing algorithms in the literature, the authors also study another penalty term that penalizes deviation from the data generating policy. The authors show on a numerical example that the more principled penalty term that depends on visitation counts is better performing, and that the proximal penalty term only yields minor improvements over imitation learning (i.e. returning the data generating policy).

The main contribution of the paper is to decompose the sub-optimality upper bound into terms that either overestimate or underestimate the total reward that can be collected in the true MDP. The authors argue that the overestimation is especially problematic for (the many) RL algorithms that are subject to such overestimation, as there is a high chance of existence of a policy that performs poorly on the true MDP but has high reward on the empirical MDP (the MDP with empirical estimates of the reward and transitions), resulting in a large sub-optimality. 

As far as I am aware, this decomposition is new. But I wonder if beyond formalizing the sub-optimality of naive algorithms, it has other theoretical or practical applications. The notion of pessimism is typical in the analysis of theoretically grounded algorithms (e.g. CPI in
Approximately Optimal Approximate Reinforcement Learning, Kakade et al. 2002), where deviation from ‘known’ state-action pairs is typically maximally penalized with the worst possible value (i.e. a sub-optimality of 1 / (1-\gamma)). So I wonder if the decomposition in overestimation/underestimation terms in Lemma 1 allows for new theoretical insights and algorithmic developments or if it is more of a rewriting, and similar results can be obtained by more carefully choosing the empirical MDP D, such that the overestimation term disappears with high probability even in the worst case and only the underestimation term remains. As is, I understand the reasons for exhibiting both underestimation/overestimation terms in order to analyze ‘naive’ algorithms in the sense of Sec. 4, but is there an advantage for this decomposition and for the algorithm in Sec. 5.1 compared to choosing the optimal policy without an penalty term but in a more carefully constructed MDP D’ that doesn’t allow for overestimation? Similarly, is there any benefit in not choosing \alpha = 1 in Sec. 5.1? Is there an optimal choice for \alpha for Sec. 5.2?

As for the practical implications, the results in Sec. 6 are quite depressing since algorithms with a proximal penalty are easier to implement than with the uncertainty penalty. What was the \alpha in the experiments? I wonder if the results can be improved for the proximal algorithm if a better choice of \alpha is used depending on the optimality of the data generating policy or on the size of the dataset.

Overall, the paper is an interesting read and its message is well presented and supported. However, I am wondering if the theoretical contributions can serve another purpose than warning about the poor theoretical guarantees of ‘naive’ algorithms, and hope the authors can correct me if I underappreciated the importance of these derivations.
review_title: What are the implications of the decomposition?

Meta-review: The reviewers agree in their positive evaluation of the paper. A weakness of the paper pointed out by several reviewers was its presentation, which has hovewer improved. Thus, I'm glad to recommend acceptance.
Decision: Accept (Poster)