Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduce a Bayesian perspective on the application of Bellman operators to estimated Q-functions. The posterior distribution over the operator application is described, a Bernstein-von Mises-style frequentist analysis is undertaken, a variety of approximate approaches are proposed, and the methods are evaluated on a variety of prediction & control tasks.
main_review: Post-rebuttal:

I thank the authors for their detailed responses to the queries I raised. Many of the points I mentioned in the original review were clarified, and in my opinion the paper contributes several interesting ideas and algorithmic developments, and I am happy to recommend acceptance for the paper.

---

The paper is generally written clearly (although is somewhat dense). Bayesian approaches to reinforcement learning have theoretically interesting properties but without approximation are computationally extremely costly, so the general topic of the paper is likely to be of interest to the RL community at NeurIPS.

This is a dense paper with several distinct contributions. I liked the discussion around distinguishing dependence on bootstrapping in calculating the posterior distribution for the parameters phi and downstream estimators. I felt some sections of the paper were too terse, such as Section 4.2, where the details of the proposed algorithm, RP-BBAC, are given almost entirely in the appendix. There is also an extensive set of experiments carried out (and primarily reported in the appendices). While some of the experimental results in the main paper potentially leave questions open as to why BBO provides stability in comparison to TD (i.e. is it a case of regularization rather than uncertainty estimates?), the authors do provide further analysis (e.g. in Section H.1) that delves into this question further and does seem to support the hypothesis that uncertainty quantification is important.

I have a few questions about some of the contributions of the paper - these are the primary reason for not giving a higher rating, and I would be happy to revise my rating once the authors have responded to these:
 * The sentence beginning after Eqn (4) seems crucial. At this point, I felt the narrative was a little unclear as to what predictions the posterior distribution is to be used for. A natural estimate in Bayesian RL might be of Q^*, but the authors focus on T^pi Q_\omega - presumably this is much easier computationally, but I wasn't sure what the end-goal of this prediction would be at this stage. Similarly, I wasn't sure why there was a focus on the posterior mean at this point. The posterior mean is often motivated as the Bayes estimator for squared loss in non-sequential settings, but I wasn't sure what the motivation is for its consideration here.
 * I didn't see much discussion of how the prior should be set in the paper. This seems to be an important issue, since unlike Bayesian approaches that specify e.g. a single prior over the optimal Q-function, here the prior depends on the function approximation parameters omega, so it is potentially a more difficult decision to decide how to set it.
 * Can the authors clarify what aspects of the analysis leading to Theorem 1 is novel beyond standard applications of Bayesian consistency analysis? Also further comments on the strength of the assumptions/applicability of the results would be useful here - assuming a density for p(b | s , a, phi) seems somewhat strong, and I think rules out the environments considered in the experiments.
 * Experimental details: I found some of the experiments in the main paper to be missing, even when consulting the appendix. For example, I couldn't details of the prior (or the assumed likelihood hyperparameters) for the Tsitsiklis example in the main paper or the appendix.

Minor comments:
 * Line 200: This claim (that derived properties such as optimal policies are also consistent) requires some more justification/qualification (i.e. that the function of the Bellman operator under consideration is continuous, for example); the claim does hold for value functions, but even for optimal policies requires some care.
 * In Figure 3, BBO seems to start with better MSE than GTD2/TDC; is the improved performance explainable due to better initialization?
limitations_and_societal_impact: As mentioned above, further discussion of the limitations of the work would be welcome.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a novel approach to model-free Bayesian reinforcement learning by directly modelling the uncertainty over the Bellman operator in a Markov decision process given experience data. The proposed approach accounts for the fact that unbiased estimates of the true Q-function are usually unavailable and instead relies on estimates of a model-dependent Bellman operator. Theoretical results prove the asymptotic consistency of the posterior over such operator, which allows for learning the Bellman operator of the true system via stochastic gradient descent whenever possible to sample directly from this posterior. The paper also provides an implementable algorithm for cases when the true posterior needs to be approximated, which comes equipped with theoretical convergence guarantees. Experimental results complement the theoretical analysis showing that the proposed framework outperforms conventional frequentist baselines in continuous control tasks.
main_review: The paper is well written and provides an interesting solution to drawbacks in existing Bayesian reinforcement learning frameworks. Bayesian RL methods have the potential to provide robust solutions to real-world RL applications by directly taking into account both epistemic and aleatoric uncertainty. The theoretical contributions are clear and provide insights into existing frameworks. Experimental results, though limited, demonstrate the potential of the proposed framework for RL applications. Therefore, I believe this paper should be accepted. However, I elaborate below on a few issues.

1. The proposed approach does not directly model a (prior) distribution over $\omega$, the parameters of the Q-function, relying instead on (stochastic) gradient descent to approximate the true Q-function with a point estimate at an $\omega^*$ minimising a squared error term (MSBBE). Have the authors considered a more complete Bayesian approach where a distribution over $\omega^*$ would be estimated?
2. There are no theoretical results on how far the Q-function formulated with the minimiser of MSBBE is to the true Q-function. I believe the paper would benefit of a discussion on this final Q-function approximation error, which I have missed.
3. The experiments section could benefit from comparisons against other Bayesian RL approaches, such as VariBAD [81], since currently it only presents comparisons against traditional frequentist baselines.
4. Some of the notation is confusing in equations which end up somewhat cluttered, leading to a few possible typos. For instance, in Eq. 1's expectation subscript, should it be $a'$, instead of $a$, in the probability? In line 119, should it be a conditional probability $P^\pi(s',a'|s,a)$? Theorem 1, line 193, apparently has $\phi^*$ missing $\omega$ in the subscript. Lastly, Eq. 9 is quite confusing. It'd be better to use another notation for the argmin solution, not the same as the argument $\phi$. Also, $\hat{B}_\phi$ is the same notation inside the set and in the subscript of $\mathcal{P}_{\hat{B}_\phi}$.
5. Ref. 22 is missing a full authors list.
limitations_and_societal_impact: Limitations of the proposed framework were not thoroughly discussed. For instance, there was no discussion on computational complexity of the proposed RP-BBAC algorithm in the estimation of the Bellman operator posteriors, though a per-step complexity of the gradient descent method is briefly commented on (line 268). The plausibility of some of the assumptions (esp. 4 and 5) in practical applications could be discussed. Societal impact is discussed in Appendix A.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a novel Bayesian treatment of the Bellman operator. The proposed formalism helps overcome significant limitations of previous approaches, where one typically infers a posterior over state-action values or transition functions. Instead, the authors focus on inferring posteriors over the Bellman operators (b = r_s’as + γ Q(s’, a’)). This formulation is attractive as it is free of strong assumptions and is malleable to theoretical analysis. The authors provide concrete (approximate and exact) instantiations of RL methods relying on the Bayesian Bellman operator (BBO), and demonstrate their empirical efficacy.

main_review: ## Significance

The paper satisfactorily addresses an important problem in Bayesian RL. All formulations I know of that combine bootstrapping with Bayes make strong assumptions that do not hold typically, which is often detrimental to the quality of the resulting algorithms. The formulation proposed by the authors overcomes these problems, is sound, and is supported by theoretical as well as empirical results. This is a very significant contribution.

## Originality

Even though bootstrapping and Bayesian inference have been combined before, it was done so somehow inadequately. This paper proposes a better way of treating bootstrapping in a Bayesian framework. The ideas are novel.

## Quality

The authors are rigorous in evaluating their proposal, especially theoretically. The experimental evidence could be stronger, but this is not a major issue, as the theoretical contributions are strong. The paper is rich in new theoretical results and insights, examples, and implementations.

A concern I have is that $\phi^*_\omega$ can be non-unique, especially with neural networks. How does this affect stability? 


## Clarity

The paper is written somewhat clearly, but I had occasional trouble understanding the formalism. The notation gets complicated quite quickly in Section 3, and some variables aren’t introduced very clearly. For instance, $\hat{B}_\phi$ is defined as a conditional expectation over b. But then, what does “The conditional mean of the distribution $\hat{B}_\phi$” (line 134) mean? 

It is not always clear what is a random variable and what is a value. For instance, what “$\hat{Q}_\omega$ is known but we are uncertain of its value under the Bellman operator …” means is unclear to me. 

Notation is sometimes overridden. Eg, $b_\omega$ is a function but $b_i$ is random variable. This further complicates things.

A table of notation would help the exposition greatly. 
limitations_and_societal_impact: The limitations and potential negative societal impact is adequately addressed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a novel approach to the problem of model-free bayesian reinforcement learning. Interpreting the **update** of the current Q-Function via the Bellman operator as uncertain due to a finite amount of samples, the authors propose to not keep a posterior distribution over Q-Functions but over Bellman operators. This view allows to model the dependency between the posterior over Bellmann operators and the current Q-Function estimate, introducing correction terms to the otherwise ad-hoc bootstrapping common in model free RL. The authors present proofs that the estimated posterior distributions convege to the true Bellman Operator in the limit of infinite data and that gradient-based algorithms for minimizing the mean-squared (bayesian) bellmann error converge.
main_review: Strenghts: 
- The Bayesian Bellmann operator framework presented in Section 3 is an elegant and theoretically well-motivated view on model-free Bayesian RL. To my knowledge, this view has not been previously proposed in the literature and is a clear and highly important novelty.
- The resulting approximate implementation in Section 4 is also novel and yields further interesting theoretical insights, motivating empirically successful techniques like lagged critics. However, reading up on previous related works (TDC, GTD(0)/GTD(2)) I realized that these interpretations were also existent, although not in a Bayesian setting.
- The presented experiments particularly in sparse-reward, continuous control environments give additional empirical evidence that the proposed method works in practice and further has the promised explorative behaviour.

Weaknesses:
- Unfortunately, the paper is not easy to parse for a reader that is not strongly experienced in both Bayesian RL and theoretical analysis of RL algorithms. Having spent at least some time with Bayesian modelling (although not so much in the RL setting) and quite some time with RL methods (although not their theoretical analysis), I could understand the paper well, although especially parsing details is very hard because it requires a lot of going back and forth between the appendix and the paper. A reason for that may be that the authors have gathered a lot of evidence, maybe even too much to put into a single conference paper. The urge to at least still hint to all that evidence sometimes results in an unsatisfying presentation of certain aspects. To put an example:
    - In Secton 4.2 the authors only spend three lines (314-316) talking about their RP-BBAC algorithm after talking for a much longer time about its connection to BootDQN+Prior. While I personally encourage highlighting such connections, I think that due to the limited space, such connections should have sometimes rather been moved to the appendix in order to allow for more detailed explanations of the proposed approach.
    - I also think that the policy evaluation results in the 20-link pendulum, puddle world and mountaincar environment should have made it into the main paper, given that the Tsitsiklis counter example is clearly important but also more detached from real world applications than the other environments.
- W.r.t to the approach itself, I have only a few points that may turn out as weaknesses:
    - The authors motivate that a Bayesian viewpoint allows to incorporate priors into the method. However, when using complicated approximators such as neural networks, specifying priors in the weight space is fairly unintuitive. So the question is, is the prior in these more complicated architectures really useful from a practical perspective?
    - In Objective (10), the term R(\phi - \epsilon_l) leaves me a bit puzzled. In Section 3, R has been introduced via the prior on the parameters of the posterior approximation, i.e. p(\phi) = exp(-R(\phi)). So what is the meaning of R in objective (10). I assume that this formulation has to do with the use of Randomized Priors but is this rather some ad-hoc choice or does R(\phi - \epsilon_l) in (10) results form re-formulations of the prior in the RP framework?
    - In the continuous control experiments: Why was it necessary to learn the behavioral policy from an average over the Q functions in the ensemble? Did the posteriors and the corresponding Q functions not collapse as nicely as suggested by the theory? Or was there a different reason for learning a policy from the averaged critics?
    - Is it really necessary that \psi_l^*(\omega_l) = \omega_l such that the MSBBE_{RP} is minimized? With a complicated DNN and all its parameter symmetries, shouldn't it be possible to find two values \omega_1 and \omega_2 such that the corresponding Q functions predict the same value? In this case, wouldn't the substitute objective (11) be a more restricted version of objective MSBBE_{RP}?
    - While the authors proof that the approximate inference scheme presented in Section 4 converges, I guess that this does, however, "only" mean that policy evaluation converges? Hence, the RP-BBAC in Section 4.2 is not necessarily guaranteed to converge, although it seems to do in the experiments. Or am I missing something?

Correctness:
- I did not check the individual proofs in the appendix (epsecially not the convergence proofs since this is out of my currernt knowledge of theoretical RL) in all detail. The simpler derivations of e.g. gradients and other formulas in the main paper that I checked looked, however, correct to me.

Clarity:
- What exactly is meant with the statement "\hat{Q}_{w_l} and \hat{B}_{w_l} share a function space" in line 242? Given the following discussion, I guess that it means that the two approximators need to not only be parameterized in the same way but also need to yield the same predictions for the same parameters? For default NNs this would mean that not only the dimensions of the hidden layers need to match but that also the same non-linearities are used? If so, a short clarifying sentence may help. Alternatively, it could also be mentioned in lines 260-262 that this is the reason why the surrogate objective is an interesting idea.
- There are certain formulas which I think are only defined in the appendix, such as \rho(s) in Assumption 1. While readers familiar with RL will probably know how to interpret \rho(s), I think it would be a big help to quickly mention the symbol in lines 139-141, i.e. right before Assumption 1.

Other:
- The equation in line 1147 of the appendix misses a bracket
- In line 234 of the main text, p(\phi \vert D) is written with capital p but it was introduced with lower case p in Eq. 4. Or should capital p indicate an approximation?
- In line 262 of the main text: "minimise" instead of minimising
	
limitations_and_societal_impact: The Impact has been adequately addressed, especially given that the authors propose an abstract method for reinforcement learning.
review_title: null

Meta-review: All of the reviewers agree that the paper presents a novel approach to model-free Bayesian RL that distinguishes itself from previous work with a clear theoretical construction and empirical evidence to support the approach. Given the potential importance and interest to the community, I recommend acceptance as a spotlight.
Decision: Accept (Spotlight)