Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a simple offline RL algorithm based on Q-learning that instead of computing the exact maximum over actions, takes the sample maximum when sampling from an learned estimate of the behavior policy. Experimental results are quite promising (competitive with previous algorithms in both offline and online settings). The authors demonstrate that utilizing autoregressive models significantly improves over simple VAEs when used to model the behavior policy in offline learning (both for the proposed method as well as prior work), highlighting the need to place more focus on how we model the behavior policy in offline RL.

The article is clearly written, and the analysis of the proposed backup is original to the best of my knowledge.
However, with how important the choice of model used to model the behavior policy appears to be, I am unsure as to how significant the new proposed backup operator is. While I feel the paper clearly highlights the importance of how we model the behavior $\mu(a\vert s)$, I don't see particularly strong evidence, either theoretically or empirically, why one should prefer using the EMaQ backup. 

Regarding the simplicity of the proposed algorithm compared to previous ones, EMaQ does use one fewer network since it does not need to explicitly model a separate policy. However, in order to achieve competitive performance, EMaQ did require a more complicated model for the behavior policy, and the increased sensitivity to that perhaps counteracts the benefits of not having an explicit policy. Additionally, EMaQ also needs to sample multiple actions for each backup and when executing the learned policy, incurring more computational costs in sampling compared to using an explicit policy network. 

One thing to potentially examine more closely is how EMaQ and the regularization from choosing small $N$ relates to previously used forms of regularization. We could consider an alternate procedure where instead of sampling N samples from $\mu(a\vert s)$ and taking the max, we instead sample from the distribution $\mu(a\vert s) \exp(\alpha Q(s,a))$ (using something like self-normalized importance sampling for example) for some temperature $\alpha$. This corresponds to the policy that simultaneously maximizes the expected Q-value as well as  a KL divergence penalty against the original policy $\mu(a\vert s)$, and would resemble the sample maximum as the temperature increases. The key difference from other methods using KL-regularization against the behavior policy would be that it relies on samples solely from the behavior model, similarly to EMaQ. Comparing these two procedures with different parameters could perhaps give us a better understanding of how implicit regularization by choosing small $N$ in EMaQ relates to explicit regularization via KL.

**Complexity Measure**: I strongly disagree that $\Delta(s, N)$ is a useful notion of complexity for offline RL. While it captures a notion of how well the behavior policy covers good behaviors, it uses the exact $Q*$ or $Q_{\mu}^N$ values. However, the difficult part in offline RL is to accurately estimate those Q values, and the proposed complexity term has no way to account for sources of complexity such as stochasticity or the horizon of the MDP. For example, an MDP with only 2 actions per state can be potentially very complex, but all 2-action MDPs would presumably look trivial just judging by how fast $\Delta(s, N)$ decreases with N.

**Misc. Comments:**
With regards to the inductive and the choice of model class for the behavior policy, what if we did actually have access to the behavior policy that generated the data? Would EMaQ perform better with oracle access to the behavior policy, or is there something about behavior model learned from the actual transitions in the dataset that would allow for better learning? Perhaps such a question would be useful for examining what sorts of inductive biases should go into the behavior model.

**Updates after Author Response:**

*Complexity Measure*: My concern with the complexity measure is that it seems to me that the biggest difficulty in reinforcement learning is in actually being able to estimate accurate value functions, while proposed complexity measure really only vaguely captures how far optimal policies are from the behavior distribution. 
In particular, at each state, it only depends on the true values of Q for each action, and can't capture how hard it is to estimate them.
Even among similarly structured MDPs, we can consider a 2-action MDP with a behavior policy that was simply uniform. 
We could have one extremely simple MDP that was simply composed of independent deterministic bandit problems at each state with no transitions (always remain in your starting state), which would be trivial to solve even from offline data with full support.
On the other hand, we could have a much more complex MDP with meaningful stochastic transitions, random rewards and so on. 
If we simply match the Q values in the two MDPs, they appear to be equally complex from this measure, despite the fact that the bandit MDP is far simpler to solve.
As such, I think the proposed complexity measure doesn't really reflect the real challenges of an offline RL problem, and am not sure how one would extend it to be useful.

*Re misc comments and access to true behavior policies:* My thinking here was that if we had a very stochastic behavior and finite samples, there would be actions that have reasonably high probability under the true behavior policy, but we never get to see in the data and wont' be able to evaluate well. One benefit of fitting the behavior model the the empirical data is that it would focus on those actions that do appear in the dataset (in an extreme case, we could simply have Dirac deltas on the observed data points), and so could benefit by restricting the actions to those that can be evaluated better.

*Overall Opinion:* In light of the empirical results mentioned in the author's response as well as the comparisons to KL regularization, I have raised my rating. I still do believe it is a very borderline paper, and would perhaps benefit from more careful analysis and focus on how the different behavior modelling choices influences offline. 

review_title: Demonstrates the importance of how we model behavior policies in offline RL, but not sure of the significance of proposed algorithm

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The paper proposes the expected-max operator to address the problem of distribution shift in offline RL (which could also be applied in online RL). The paper establishes theoretical analysis of the proposed operator in convergence, sub-optimality, etc. A practical algorithm is proposed based on previous techniques (an ensemble of Q-functions) and a different generative model using an autoregressive architecture. Experiments demonstrate the effectiveness of EMaQ. 

Strong points: The paper studies the important problem of how to mitigate distribution shift in offline RL, and proposes a simple but effective algorithm. The paper conducts extensive experiments comparing with state-of-the-art algorithms, with in-depth ablative studies of the effect of each component.

Concerns:
- I am surprised by the result in Figures 1 and 2 that EMaQ performs very well with a small value of N=5 (as the upper bound in Theorem 3.5 would be not very meaningful given a small N and gamma close 1). Could authors investigate the sampled 5 actions? Are they diverse enough to represent the entire action space well, considering the action space is continuous?

- The performance of EMaQ strongly relates to how good \mu is learned. What if \mu is close to a deterministic policy (e.g., \mu is not learned well and is close to a deterministic policy)? How to guarantee this diversity?

- Could authors compare the performance of EMaQ when N is 1 and an extremely large value, which could better justifies the performance in extreme cases. 

- How are the computation time and learning curve (besides the final performance shown in the paper) of EMaQ compared with other methods? 

- In Section 3.5, it is not clear how a small value of N could serve as a regularizer and smoothen the incorrect values.
review_title: The paper proposes a simple but effective algorithm. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper analyzes off-policy algorithms using a sampling-based maximization of the Q function over a behavior policy for both Bellman targets and for policy execution, introducing the “Expected Max Q-learning” operator EMaQ for analysis. The paper then proposes to use more expressive autoregressive models (MADE) for learning the behavior policy from replay buffer data (either online or offline), which turns out to be very important, especially on harder tasks in the D4RL benchmark. The method is relatively novel - it is close to other methods in the literature, but they make and evaluate important design decisions that are valuable for the community. The results are quite strong, matching or exceeding BEAR on D4RL while at the same time matching SAC for online learning.

The proposed method is simple yet effective: they learn a behavior policy on offline data. Then they learn a Q-function by Bellman bootstrapping, using max of N samples from the behavior policy for the target step. Then for executing the policy, the method again uses the argmax of N samples from the behavior policy. As mentioned in the related work, prior work such as BCQ and QT-Opt has studied sample-based policies, and it has also been common to mix the two decisions: eg. BEAR uses a parametric policy for bootstrapping but then reports a boost from sampling for policy execution. But the proposed method is perhaps the simplest of these from an RL point of view, which is a good thing - and the juice really comes from the proposal to use MADE for modeling the behavior policy. This also suggests clear future directions for research - to explore other, better generative models (AR models in particular are probably a poor long-term solution because of slow sampling).

The analysis centers around the EMaQ operator, which is a nice representation for thinking about the maximization problem in Bellman bootstrapping. The paper proves the convergence of the operator in the tabular setting, and some intuitive theorems that larger values of N result in policies with better Q values (for policy evaluation), and thus better policy improvement. One issue though with N -> inf, is that it would tend to exploit function approximation errors of the Q function, and this is borne out in some of the results. Theoretical results along these lines would significantly strengthen the paper.

The highlight of the paper is results on both offline and online RL. In offline RL, EMaQ roughly matches the performance of BCQ and BEAR while being significantly simpler to implement (except perhaps the MADE model) and exceeds BCQ and BEAR in some environments and depending on the underlying implementation. In online RL, EMaQ roughly matches SAC, being slightly worse when updating the policy frequently and slightly better when updating the policy less frequently. As far as I know, no prior method has been able to show good performance on both: SAC is poor on offline training and BCQ/BEAR is poor on online training. This is the strongest positive for the paper.

Minor comments:

There are a couple of references to “number of samples” in the intro that do not make sense until reading the method. Perhaps you need to outline the method in the intro, instead of just hinting at it, if you want to discuss these details. “As an example, we observe that while a HalfCheetah random policy obtains a return of 0, a policy that at each state uniformly samples only 5 actions and chooses the one with the best value obtains a return of 2000.” - I’m not sure if I understood the setup here, or the significance. Is the value estimated with samples from the random behavior policy? Is the second policy you refer to your method (so fit a behavior policy on the random behavior data, then do Q learning + sample 5 actions for maximizing it), or something else? Moreover, I did not really understand why this is too surprising, since the bulk of the work is really being done by learning a good Q function and even on random-action data, learning a behavior policy would help you stay constrained to the data.

Deferring the full related work to the appendix skirts the page limit rules and is somewhat unfair to other submitters, and also made it hard to read since the links do not cross-reference between PDFs.

“Importantly, our theoretical analysis on the family of TD operators described by EMaQ apply beyond BCQ and can also provide new perspectives on some of the highly successful sample-max Q-learning algorithms (Kalashnikov et al., 2018a; Van de Wiele et al., 2020) – particularly on how the proposal distribution affects convergence.” Not sure if I missed this, but I didn’t exactly see such a result or know what this is referring to, which I would expect to be something like lower D(pi* || mu) implies faster convergence.
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposed EMaQ, an approximation of Bellman operator, and thus yields a variant of deep Q learning algorithms in both online and offline settings. In tabular settings, several properties of the EMaQ operator such as the convergent guarantee, fixed point, and finite-sample error bounds were studied. Then the author shows the empirical performance of a deep learning approximation of the proposed algorithm on a standard batch RL benchmark. The authors also provide some analysis of the effect of different implementation choices on empirical performance, by ablation study.


A key fact is that the proposed method can be directly got from BCQ by settings the perturbation parameter to zero. Thus, the originality here is quite little. The proposed algorithm is a simplification compared with BCQ. However, in terms of both theoretical and empirical contributions, this paper does not show a significant improvement compared with BCQ. In general, the findings of this paper seem not surprising at all given BCQ and BEAR paper.

Pros:
1. Compared with BCQ, the proposed EMaQ operator has a simpler form with similar performance. In some sense, it is a Q learning analog of BCQ (which is actually an actor-critic algorithm).
2. There is some ablation study on the choice of generative model for $\mu(a|s)$, the number of action to sample, etc. which are missed in the original BCQ paper.

Cons:
1. As I mentioned in the summary, the biggest issue is that as a very simple and incremental algorithmic change, this paper also failed to provide additional discussion in either theory or experimental that can provide significantly more insight and inspiration to people. There are many potential directions where the discussion can go: 
(1) In some sense it is a Q learning analog of BCQ (which is actually an actor-critic algorithm). It will be very interesting to discuss the effect of the difference between Q learning and actor-critic on BCQ v.s. EMaQ comparison. Unfortunately, I did not see enough in-depth discussion on that.
(2) The new algorithm is more closed the tabular settings. So does that yield stronger theoretical guarantees in function approximation settings? Or is there a conceptual experiment to demonstrate where the perturbation model is a bad idea/approximation and cause the failure of the algorithm?
(3) Does this very simple algorithmic choice lead to very different behavior of the algorithm (e.g. optimization path of the parameters, behavior of the resulting models other than just reward)? Why there is or is not a very different behavior of the algorithm?

2. According to the paper a key contribution of the empirical part is the importance of careful generative model design for
estimating behavior policies. This seems very straightforward as the BCQ/BEAR algorithm is using $\mu(a|s)$. Given that $\mu(a|s)$ is a plug-in module in those algorithms, new advances in the generative model can be immediately applied there so the significance and novelty of this finding are very limited.

3. A general problem of this paper is over-claiming. For example: 
(1) "EMaQ matches and outperforms the prior state-of-the-art in the D4RL benchmarks" -- It matches (and did not outperform by any statistically significant margin) BCQ and BEAR. There are other baselines in D4RL that are better than BCQ/BEAR: BRAC, CQL, MOPO, MoRel. The former two are also model-free, and those numbers are all reported in the D4RL whitepaper.
(2) "EMaQ provides a quite intuitive and surprising measure of the complexity for offline RL problems." To claim that, I think it needs to show that  $\Delta$ is related to some general structure of the problem (theoretically) or some general phenomenon for a large group of algorithms (empirically).
These two claims can also be a potential improvement of this paper if they are really achieved.

review_title: An incremental algorithm changes compared to BCQ; Small empirical improvement

Meta-review: **Overview** The paper provides a simplified offline RL algorithm based on BCQ. It analyzes the algorithms using a sampling-based maximization of the Q function over a behavior policy for both Bellman targets and for policy execution -- the EMaQ. Based on this, the paper then proposes to use more expressive autoregressive models (MADE) for learning the behavior policy from replay buffer data. The methods work well for harder tasks in the D4RL benchmark. 

**Pro** 
- The method is relatively novel 
- Algorithms are simple modifications of existing ones
- Empirical results are strong, matching or exceeding BEAR on D4RL while at the same time matching SAC for online learning
- Work for both and offline
- ablation study on the choice of generative model for μ(a|s)

**Con**
- The current form of the complexity measure is somewhat not practical.
- Theoretical results are not strong enough
- Algorithmic contributions appear incremental

**Recommendation** The paper is on the borderline. It contributes simple and nice algorithmic ideas and these ideas work well empirically. These results demonstrate that a good choice of the behavior policy generative model is important for some tasks. At the same time, the reviewers are concerned about the theoretical parts, e.g., issues relates new complexity measure. Overall, the meta-reviewer believes that the paper might not be in a status ready for publication.
Decision: Reject