Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors present a nearest neighbour method for learning a model offline from the statistics of the given data set. Representations are provided from other off-policy deep RL methods. Value iteration is used on top of the model to learn the final policy. The algorithm is tested in several Atari games over two data set sizes. 

Strengths:
- Overall, the proposed method is straightforward, intuitive, and outperforms baselines on a challenging task. The results are somewhat surprising given the simplicity of the approach. 
- With a few exceptions (discussed below), the presentation quality is high. Figures are clear/readable. Writing is clear.
- With a few easily fixed exceptions (discussed below), reproducibility is high. The appendix is detailed & includes additional experiments. Code is provided. Most algorithmic and experimental details are provided.

Weaknesses:
- Experimental results suggest the method requires a representation derived from other off-policy deep RL algorithms, meaning running the proposed method also requires running another deep RL method to simply learn the representation. At the same time, the performance gains seem incremental for a lot of additional complexity.
- I do feel like there is a contribution here, but novelty is not that high compared to other methods which build on tabular RL.
- Although I can (personally) infer the purpose of $d(s,a,s_i,a_i)$ in the reward function from related work in the field, the use of $d$ is not well motivated by the authors. At the same time, both the choice of $C$ and $d$ would seem to be important hyper-parameters relative to the scale of the reward function. A choice which is difficult to make without interacting with the environment. Furthermore, I was unable to find the description of the distance $d$ anywhere in the main body or appendix.
- The related work is missing discussion on recent offline RL methods such as [1,2,3,4].
- Baselines are limited to only two methods. Possible additions [1,3]. Additionally, although its nice that additional experiments were includes the gym mini-world experiments don't add much to the paper without baselines.
- Reproducibility Issues:
    - The use of $N_e$ is unusual. Its role is not well described in Section 2 without reading the appendix.
    - I was unable to find the number of seeds used in each experiment. Although error bars are provided in some figures, I was unable to find what quantity these error bars were describing.
    - As previously mentioned, I could not find which distance function $d$ was used in the experiments.

Minor Clarity Issues:
- Eqn (1) and (3) describe the bellman equation over Q functions, however the method relies on state value functions $V$ which are learned with a transition function (such as described in Pseudocode 1 in Appendix A.6). Fixing this along with a clearer description of the 1-step kNN look ahead step would improve clarity. 
- Typo: Figure 2: "Datset" version.
- Typo: A.2. "Theoritial Proofs".

Recommendation:

Overall, I think the results of the method are interesting, even if incremental. In its current state I would favor rejection, but I believe this would be a solid paper with enough corrections to the weaknesses I've listed. Either during the rebuttal phase of this conference or as a submission to a future conference. 

References:
- [1] Agarwal, Rishabh, et al. "An Optimistic Perspective on Offline Reinforcement Learning." 2020.
- [2] Fujimoto, Scott, et al. "Off-policy deep reinforcement learning without exploration." 2019.
- [3] Wang, Ziyu, et al. "Critic regularized regression." 2020.
- [4] Levine, Sergey, et al. "Offline reinforcement learning: Tutorial, review, and perspectives on open problems." 2020.

**Post-Rebuttal**

The authors have done well with their additional page, and many of the concerns I had have been dealt with the latest iteration of the paper. I have increased my score. 

Re: Motivation for c and d. The current *objective* for c and d is described in the paper, but the motivation is not. I hope the authors add to this discussion in the next iteration. 
review_title: Good results for a simple approach, but low novelty & a lot of minor issues

final_score: rating: 7: Good paper, accept
review_content: This paper proposes DeepAveragers: an adaptation of the "averagers" framework to the Deep RL setting.
Approximate dynamic programming is performed over a batch of observed (s,a,r,s') except with a distance penalty applied to states that are not close to those observed in the training data.
The authors show that this formalism can lead to better performance than learning without penalty, and also that better representations of "state similarity" lead this method to perform better in aggregate.

There are several things to like about this paper:
- The problem of "batch RL" is timely as people look to apply RL techniques in real world problems, where learning from tabula rasa may be prohibitive.
- The proposed method appears sound, general and well thought through.
- The experimental results provide a clear progression from theory -> didactic examples -> deep RL, and the approach performs well across the board.
- The paper is overall well-written and easy to follow.

However, there are a few places where it might be improved:
- The discussion and results of "3D navigation" are not well-presented... large paragraphs of texts with relatively arbitrary numbers (0.98 vs 0.96) do not make a convincing presentation. Can these be displayed better visually?
- I'm not convinced enough connection is given between the "averager" framework and the many other approaches to batch RL, which all essentially seem to work via a similar manner: give penalties to the state-actions that are poorly understood.
- I think that some of the GPU-specific discussion is a bit distracting/incidental to the core work of the apper.


Overall, I like the paper and think it seems like a strong contribution.
I'm slightly worried that the comparison to other related work is insufficient, as I am not well-versed in the area.
However, from what I can see it looks like it is suitable for the conference.
review_title: Better batch RL via penalizing poorly-understood state-actions

final_score: rating: 7: Good paper, accept
review_content: Summary
=========
Authors introduced the Deep Averagers with Costs MDP (DAC-MDP) as an offline approach for solving MDPs
They addressed the following planning challenges: difference in representation used by model and planner, and 2) planners exploit inaccuracies of models
To address (1) authors relied on a simple tabular representation. To address (2), the adopted pessimism in the face of uncertainty by encouraging the agent to focus on known areas. 

Pros / Cons
[+] Theoretical analysis of DAC-MDP

[+] Empirical results on toy domain (Cart pole), Atari and 3D first-person navigation task

[+] The idea is very simple 

[-] Some of the decisions made by the authors felt arbitrary (See details/questions)

[-] Authors used 3 seeds for empirical results which seems too small. Moreover, some plots lack statistical significance.

[-] As with any planning approach, these algorithms are expected to perform better than their counter part without planning. 
However, there is no free lunch and the boost will come at the expense of computation. Currently the paper does not discuss that critical angle. 

[-] The main idea does not seem very novel (see below)

Questions:
==========
Eqn. 2: Why not scale the rewards based on their distance to (s,a) instead of having the distance as a penalty?

Page 6: 
	- Atari domain has deterministic transition. How well this approach works for stochastic transitions?
	- The entire 100K iteration protocol was repeated 3 times => Is 3 times enough to provide statistical significance?
	- Figures 4 investigates the performance at the final iteration for different values of Ne. For Ne = 1 we use k=5,kπ =11,C=1 and 
for Ne =20 we expand on the parameter set used for Ne=6. => How did you select these parameters?

Figure 5: Where are the standard errors? Are all differences significant? Again you should also discuss wall clock time.

Page 8: The idea of moving non-core states to core states for planning using a metric is not new (e.g. [1])

Generic: I am not sure how easily this approach can scale to large stochastic domains with continuous state space. Was the 3D first-person navigation task included stochasticity in the transition function?

Details
=========
P3: "non-core state immediately transitions to the core for any action" => How do you calculate the corresponding core state? Is it the closest using KNN?
Figure 2: Where are the error bars?
Figure 3: What about computation time?

[1] J. Joseph, A. Geramifard, W. Roberts, J. How and N. Roy,  “Reinforcement Learning with Misspecified Model Classes”, IEEE International Conference on Robotics and Automation (ICRA), 2013


POST-REBUTTAL
==============
"First, we would argue that there are not many examples of planning approaches outperforming non-planning approaches when using imperfect learned models. Providing such a demonstration in challenging image-based benchmarks is one of the contributions of this work."
- I disagree with authors. The idea of planning using imperfect models have been explored as early as 1998 (e.g. Dyna algorithm in Reinforcement Learning: An Introduction by Sutton and Barto).

"computational analysis"
- Thank you for adding this section. It addressed my concern.

"non-determinism"
- Thank you for adding more clarity. It addressed my concern.

"Statistical significance"
- Great to see the extra runs. Please include the bars for Figures 5,7 in the final submission.

review_title: Reinforcement learning for scaling data-driven dialog policies

final_score: rating: 7: Good paper, accept
review_content: The authors propose to learn a non-parametric MDP model from batch data, which can be solved efficiently using discrete value iteration (by solving for the “core” states which are all the end-states in observed transitions) and which provides a Q-value defined over the full continuous space through a kNN lookup. There is an interesting penalty term when the estimate relies on far-away support data. The value of the optimal policy in the approximated MDP can be bounded, under some smoothness assumptions, in the original MDP.

My main concern about this first contribution is about novelty. The authors have not cited other classic papers on this topic which have similar results, for example: Kernel-Based Reinforcement Learning by Ormoneit and Sen, 2002 (see in particular Section 4 which also mentions how dynamic programming can be run on the “core” states). The authors should discuss the relation to this work and surrounding literature. Follow-up papers like (Tree-Based Batch Mode Reinforcement Learning, Ernst et al. 2005) have been applied to large domains and fitted Q-iteration (FQI) has been studied in many papers afterwards both empirically and theoretically. It would be great if the authors could comment on that. 

The second paper contribution is to explore the practicality of this approach using various ways to represent the state, including parametric functions as used in DeepRL. The studied domains are Cartpole, Atari (8 games) and 3D navigation tasks. The empirical results in Cartpole demonstrate the importance of the penalty term to obtain good performance. It would be nice to know the score of the pre-trained Cartpole policy for comparison in Fig 2 (same question for 3D nav domains). In Atari, it appears that the latent representation can be leveraged by the proposed approach to robustly improve the DQN score. In general these experiments are usefully presented, but some questions remains over how other approaches would do in similar settings. For example:
* Instead of using the learned representation outside of the original DeepRL setting, can that extra computation be used instead within the same DQN framework by replaying the same data and updating the network further? (cf paper When to use parametric models in reinforcement learning? by van Hasselt et al. 2019)
* Can LSPI be run using these representations? What are the accuracy/speed trade-offs there?
* What about other FQI-style methods like Extra-trees cited above? Or in general how do other batch RL methods compare?

3D Nav: “ For most offline RL approaches this would require retraining the agent on a modified dataset from scratch.” For this scenario, perhaps only the last layer could be retrained while keeping the same latent representation, which is similar to what is going on here? The DAC-MDP agent is retrained “from scratch” with this different cost function, though perhaps this is much faster in this case.

The 3D nav experiments are interesting, but it’s hard to know what to take away from them. If flexibility of task modifications using the same data batch + learned representation is the main point, it seems important to quantify this further (other approaches can do this zero-shot transfer, but perhaps not as well or quickly?). Also this method would presumably fail as the pre-learned representation becomes less relevant for the modified task.

Overall, the paper is written clearly and it revisits older RL work to demonstrate their practicality combined with modern tools. The experiments do a good job with ablations of the proposed method but without clear baselines to compare to. As mentioned above,  previous work in this area needs to be more thoroughly referenced and discussed, the small “Averagers Framework” Related Section is missing some connections to past work.


Minor points:

* I am not sure k_\pi is defined. Is it the k parameter in Eq 3?
* “eucledian” distance
* Fig 2 legend “parameter”
* Clarify iterations in the Atari setting (frames? steps?)
* “their optimal polcies are visualzed”


---- Post-rebuttal ----

Thank you for addressing my concerns and providing the additional experiments and baseline which I think make the paper stronger. I have updated my score as a result.

review_title: Review

final_score: rating: 7: Good paper, accept
review_content: The authors propose a method to construct non-parametric models for offline control based on the averager framework. The authors tested three typical latent representations including random projection, DQN representation, and BCQ representation. KNN is then used to construct the non-parametric model on the latent space. The reward function is augmented with a penalty term penalizing unseen transitions in the dataset. A novel GPU MDP solver based on value iteration is used to solve the non-parametric model. Theoretically, a performance lower bound is derived for the approximate MDP. Empirically, a thorough comparison with baselines is performed in the challenging Atari domains. I particularly like the case study in the 3D navigation domains, which highlights the flexibility of DAC-MDP.

Overall I think the paper makes a good contribution in offline RL. The ideas are intuitive and the empirical results are convincing. 

Minor comment:
(1) I can understand building the kNN table is a one time cost in offline setting as the dataset does not change. In the online learning setting, building such a kNN table is usually considered computationally intractable, so I think the paper may benefit from providing some statistics of the run time for compiling such a kNN table for 2.5M Atari frames, as well as the memory cost.
(2) The paper implements a hybrid version of Block Divided Iteration and Result Divided Iteration. I think the paper may benefit from some discussion about the convergence of this hybrid GPU value iteration algorithm.
(3) According to how I understand the paper, a Eucledian distance is used on the latent space. When random projection is used, I can see it can easily project (s, a) together. But when DQN or BCQ representation is used, I don't fully understand how they encode (s, a). In my understanding, the default DQN and BCQ encode only states, so how are actions encoded?
(4) Contrastive learning has recently achieved great success in representation learning, as well as reinforcement learning as auxiliary tasks. I'm wondering if it can help improve the performance of DAC-MDP.
review_title: A good paper

Meta-review: This paper proposes an algorithm for offline RL, that consists in solving a finite MDP derived from a fixed batch of transitions.
The initial reviews were overall positive, and the concerns raised at this stage were nicely addressed by the rebuttal and the revision from the authors.
The final discussion led to the consensus that this paper should be accepted at ICLR.
Decision: Accept (Spotlight)