Bayesian Bellman Operators
Authors: Matthew Fellows
Kristian Hartikainen
Shimon Whiteson
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Bayesian Reinforcement Learning
Reinforcement Learning

Abstract: We introduce a novel perspective on Bayesian reinforcement learning (RL); whereas existing approaches infer a posterior over the transition distribution or Q-function, we characterise the uncertainty in the Bellman operator. Our Bayesian Bellman operator (BBO) framework is motivated by the insight that when bootstrapping is introduced, model-free approaches actually infer a posterior over Bellman operators, not value functions. In this paper, we use BBO to provide a rigorous theoretical analysis of model-free Bayesian RL to better understand its relationship to established frequentist RL methodologies. We prove that Bayesian solutions are consistent with frequentist RL solutions, even when approximate inference is used, and derive conditions for which  convergence properties hold. Empirically, we demonstrate that algorithms derived from the BBO framework have sophisticated deep exploration properties that enable them to solve continuous control tasks at which state-of-the-art regularised actor-critic algorithms fail catastrophically. 

Bayesian Bellman Operators
Matthew Fellows" Kristian Hartikainen Shimon Whiteson Department of Computer Science University of Oxford
Abstract
We introduce novel perspective on Bayesian reinforcement learning (RL); whereas existing approaches infer posterior over the transition distribution or Q-function, we characterise the uncertainty in the Bellman operator. Our Bayesian Bellman operator (BBO) framework is motivated by the insight that when bootstrap- ping introduced, model-free approaches actually infer a posterior over Bellman operators, not value functions. In this paper, use BBO to provide rigorous theoretical analysis model-free Bayesian RI. better understand its relationship to established frequentist RI. methodologies. We prove that Bayesian solutions are consistent with frequentist RL solutions, even when approximate inference is used, and derive conditions for which convergence properties hold. Empirically, we demonstrate that algorithms derived from the BBO framework have sophisticated deep exploration properties that enable them to solve continuous control tasks at which state-o taite-of-thar of-the-art regularised actor-critic algorithms fail catastrophically.
1 Introduction
A Bayesian approach to reinforcement learning (RL) characterises uncertainty in the Markov decision process (MDP) via posterior 355 78. great advantage of Bayesian RL that it offers a natural and elegant solution to the exploration/exploitatio problem, allowing the agent to explore to reduce uncertainty in the MDP, but only to the extent that exploratory actions lead to greater expected return; unlike in heuristic strategies such as e-greedy and Boltzmann sampling, the agent does not waste samples trying actions that it has already established are suboptimal, leading to greater sampling efficiency. Elementary decision theory shows that the only admissible decision rules Bayesian 22 because a non-Bayesian decision can always be improved upon by a Bayesian agent [4]. In addition, pre-existing domain knowledge can be formally incorporated by specifying priors.
In model-free Bayesian RL, a posterior inferred over the Q-function by treating samples from the MDP as stationary labels for Bayesian regression. A major theoretical issue with existing model-free Bayesian RL approaches is their reliance on bootstrapping using a Q-function approximator, as samples from the exact Q-function are impractical to obtain. This introduces error as the samples are no long estimates of a Q-function and their dependence on the approximation not accounted for. It is unclear what posterior, if any, these methods inferring and how it relates to the RL problem.
In this paper, we introduce Bayesian Bellman Operators (BBO), novel model-free Bayesian RL framework that addresses this issue and facilitates a theoretical exposition the relationship between model-free Bayesian and frequentist RL approaches. Using our framework, we demonstrate that, by bootstrapping, model-free Bayesian RL infers posterior over Bellman operators. For our main contribution, we prove that the BBO posterior concentrates on the true Bellman operator (or the closest representation our function space of Bellman operators). Hence Bayesian method using the BBO posterior is consistent with the equivalent frequentist solution in the true MDP. We derive convergent gradient-based approaches for Bayesian policy evaluation and uncertainty estimation. Remarkably, our consistency and convergence results still hold when approximate inference is used.
*Correspondence to mat matthew www.wwwwwwwwww.....e...e.wowowww fellowsecs. ox ax.ac.ul
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our framework is general and can recover empirically successful algorithms such as BootDQNpriort [57. We demonstrate that BootDQNprior+'s 's lagged target parameters, which are essential to its performance, arise from applying approximate inference to the BBO posterior. Lagged target parameters cannot be explained by existing model-free Bayesian RI. theory. Using BBO, we extend BootDQNprior+ to continuous domains by developing an equivalent Bayesian actor-critic algorithm. Our algorithm can learn optimal policies in domains where state-of-the-art actor-critic algorithms fail catastrophically due to their inability to properly explore.
like soft actor-critic
39)
2
Bayesian Reinforcement Learning
To aid the reader with notation, provide mathematical glossary in Appendix A
2.1 Preliminaries
Formally, an RL problem is modelled as a Markov decision process (MDP) defined by the tuple
(S. A, r, Po. 7) 722 60, where S is the set of states and A the set of available actions. At time an agent in state E S chooses an action de E AA according to the policy
n m(-(s.). The
agent transitions to a new state according to the state transition distribution 81+1 P(-]st, az)
which induces a scalar reward == rr(t-11, 0z, 8x) E R with supy',a. Ir(s', , 8)] <c. The initial state distribution for the agent is 8g ~ Po and the state-action transition distribution is denoted as (s(s', a'I ds|s,)), a). which satisfies d/= (s',a''ss, ad's,,)
d (a') |s") |s)dd((s'\ss [s, a).. As the agent interacts with the environment gathers a trajectory: (5g, ao, To, 81, 01 (1, $2...) .) We seek an optimal policy r" arg max, JR that maximises the total expected discounted return: J = E, EE== 7'r,] where E,, is the expectation over trajectories induced by π. The Q- f-fuctiion is the total expected reward as function of a state-action pair: Q" a) == EE roolso 8, ag a]. Any Q-function satisfies the Bellman equation B[Q²] = Q" where the Bellman operator is defined as:
B(Q*)ss,)) a) = (p (s [r(s', ,a,s) (Q"
2.2 Model-based vs Model-free Bayesian RL
are framework for model-based Bayesian reinforcement learning where a posterior marginalises over the uncertainty in the unknown transition distribution and reward functions derive Bayesian MDP. BAMDP optimal policies are the gold standard, optimally balancing exploration with exploitation but require learning a model of the unknown transition distribution which is typically challenging due its high-dimensionality and multi-modality (67]. Furthermore, planning in BAMDPs requires the calculation of high-dimensional integrals which render the problem intractable. Even with approximation, most existing methods are restricted to small and discrete state-action spaces 6 38 One notable exception is VariBAD [22] which exploits a
Bayes-adaptive MDPs (BAMDPs) p
meta learning setting to carry out approximate Bayesian inference. Unfortunately this approximation
sacrifices the BAMDP's theoretical properties and there are no convergence guarantees.
Existing model-free Bayesian RL approaches attempt to solve Bayesian regression problem infer a posterior predictive over a value function 78 B5). Whilst foregoing the ability to separately model reward uncertainty and transition dynamics, modelling uncertainty in value function avoids the difficulty of estimating high dimensional conditional distributions and mimics a Bayesian regression problem, for which there are tractable approximate methods 44
IC 47 61 [k] 51 These methods
assume access to a dataset of N samples: DN = {= from a distribution over the true Q- function each state-action pair: qi P- a.). Each sample is an estimate of point of the true Q-function qi = (* a:) + Tı corrupted by noise n7. By introducing a probabilistic model of this random process, the posterior over the Q-function P(Q* [s, a, DD) can be inferred, which characterises the alcatoric uncertainty in the sample noise and epistemic uncertainty in the model. Modeling aleatoric uncertainty is the goal of distributional RL M. In Bayesian RL we are more concerned with epistemic uncertainty, which can be reduced by exploration [57].
2.3 Theoretical Issues with Existing Approaches
Unfortunately for most settings it is impractical to sample directly from the true Q-function. To obtain efficient algorithms the samples qi are approximated using bootstrapping: here a parametric function approximator Qw S A + R parametrised by w Q is learnt as an approximation of the Q-function Q_ R Q" and then a TD sample is used in place of g:- For example one-step TD estimate approximates the samples as: di R rs + 7Q (ss, as), introducing an error that dependent on w. Existing approaches do not account for this error's dependency on the function approximator.
2

---

Samples are no longer noisy estimates of point Q* ai) and the resulting posterior predictive is not |sQ D.) as it has dependence on Qw due to the dataset. This problem is made worse when a posterior is inferred over an optimal Q-function as it is impossible to sample from the optimal policy a priori to obtain unbiased samples. This is major theoretical issue that raises the following questions:
1. Do model-free Bayesian RL approaches that use bootstrapping still infer a posterior?
2. If it exists, how does this posterior relate solving the RL problem?
3. What effect does approximate inference have on the solution?
4. Do methods that sample from approximate posterior converge?
Contribution: Our primary contribution is to address these questions by introducing the BBO framework. In answer to Question 1, BBO shows that, by introducing bootstrapping, we actually infer a posterior over Bellman operators. We can use this posterior to marginalise over all Bellman operators to obtain Bayesian Bellman operator. Our theoretical results provide answers to Questions 2-4, proving that the Bayesian Bellman operator can parametrise a TD fixed point as the number of samples N - Do and is analogous the projection operator used in convergent reinforcement learning. Our results hold even under posterior approximation. Although our contributions are primarily theoretical, many of the benefits afforded by Bayesian methods play a significant role in wide range of real-world applications of RL where identifying decisions that are being made under high uncertainty crucial. We discuss the impact our work further in Appendix
3 Bayesian Bellman Operators
Detailed proofs and a discussion of assumptions for all theoretical results are found in Ap- pendix G
To introduce the BBO framework we consider the Bellman equation using a function approximator:
B[Q,] Q.. Using Eq. 1. we can write the Bellman operator for Qw as an expectation of the empirical Bellman function bz:
BiQ a) = Ep (a)aaa) (b, a)), (u', s, = r(8, a, + Qwi d').
(2)
When evaluating the Bellman operator to solve the Bellman equation, we can evaluate the function approximator (s. a) but we cannot evaluate B[Qw](s, a) due to the uncertainty in reward function
and transition distribution. In BBO capture this uncertainty by treating the empirical Bellman function as transformation
variables ( a): S x A R for each (s, a). The transformed variable B IR + I has conditional distribution (b]s,,, w) which is the pushforward of pa (s', a' d'Is,, a) under the transformation (,,,,,), a). For any Pna-integrable function f R - R. the pushforward satisfies:
(bbls,a.)))))
[f(b]] (' [f (s',, a', s,a].
As the pushforward Pr (b|s, a, is a distribution over empirical Bellman functions, each sample b ~ PB.-|s, a, w) is noisy sample of the Bellman operator a point: b, = BlQ,)(ss, a.) + n/. To prove this, observe that taking expectations of b recovers B[QwI(s, a))
E (Pe(t)s [b]
E Eps (st,aa)))ss [b s. ((Q.)
E4.
As the agent interacts with the enviromment, it obtains samples from the transition distribution s P(-Is,, a;) and policy af ~ 7 (-1s()). From Eq. a sample from the distribution b; ~ PB(- s;, a,, w) is obtained from these state-action pairs by applying the empirical Bellman function b; r; (w, af). As we discussed in Section 2.3 existing model-free Bayesian RL approaches incorrectly treat each b; sample from distribution over the value function Po (Q" a). BBO corrects this by modelling the true conditional distribution: Pp (b)s, a, w) that generates the data.
N
The graphical model for BBO shown Fig. T
To model (b|b,s, a, w) we assume parametric conditional distribution: P a, Φ) with model parameters
Figure I: Graph- ical Model for BBO.

---

à E i and a conditional mean: EP(M)....)) [b] = Bs(s, It is also possible to specify nonparametric model: P(bls,a). The conditional mean of the distribution B3 defines function space of approximators that represents space of Bellman operators, each indexed by ø E t. The choice of P(b) 8; 0, #) should therefore ensure that the space of approximate Bellman operators characterised by B& is expressive enough to sufficiently represent the true Bellman operator. As we not concerned with modelling the transition distribution in our model-free paradigm, assume states are sampled either from an ergodic Markov chain, or i..d. from a buffer. Off-policy samples can be corrected using importance sampling.
Assumption (State Generating Distribution). Each state 8; is drawn either i) Li.d. from a distribu- tion pls) with support over S or from an ergodic Markov chain with stationary distribution p(6) defined over a a-algebra that is countably generated from S.
We represent our preexisting beliefs in the true Bellman operator by specifying a prior P(ő) with a density p()) which assigns mass over parameterisations of function approximators E in accordance with how well we believe they represent B[Qw]. Given the prior and a dataset D.N == {b,, 84, as )=IN of samples from the true distribution Pg. we infer the posterior P(e using Bayes' rule which has the density (sce Appendix D.I for a derivation using both state generating distributions of Assumption
M Ih p(b ss, a. Φ)p(o)
(4)
Jo II= as ())P(()
To be able to make predictions, we infer the posterior predictive: p(b s. = So p(bls, a, ()dP
Unlike existing approaches, our posterior density is a function of w. which correctly accounts for the dependence on Q. in our data and the generating distribution (bb(,s, a, w). We highlight that is possible to define likelihood and prior that are functions of to encode any prior knowledge of how the underlying Bellman operator varies with w, however this is not strictly necessary as the posterior automatically accounts for this dependence due to its conditioning on DN As we anticipate that most applications of BBO will seek to learn an optimal policy, and hence and optimal Q-function, a prior that incorporates any knowledge available about the optimal Bellman operator will speed learning and give the agent an advantage.
As our data depends on Q... we must introduce a method of learning the correct Q-function approxi- mator. As every Bellman operator characterises an MDP, the posterior predictive mean represents Bayesian estimate of the true MDP by using the posterior to marginalise over all Bellman operators that our model can represent according to our uncertainty in their value:
B (8, a) = =EE s.a) (b) E [Bo(s,a))
(5)
For this reason, we refer to the predictive mean B as the Bayesian Bellman operator and our Q- function approximator should satisfy a Bellman equation using B Our objective is therefore to find wn such that Qw = B .N- A simple approach to learn w" is to minimise the mean squared Bayesian Bellman error (MSBBE) between the posterior predictive and function approximator:
MSBBE (w) = Qw -BEN
(6)
Here the distribution the fg-norm is p(s)=(als) where recall p(s) is defined in Assumption Although the MSBBE has a similar form to a mean squared Bellman error with a Bayesian Bellman operator in place of the Bellman operator, our theoretical results in Section G.T show its frequentist
interpretation is closer to the mean squared projected Bellman operator used by convergent TD algorithms
70
We derive the MSBBE gradient in Appendix D.3
V sa (SB
[(--- EP(OIDy) (Ba)) (v- EP(OrD Va logr(d1DN))) })]]
=Ep.7
If we can sample from the posterior then unbiased estimates of V V..MSBBEW (w) can be obtained, hence minimising the MSBBE via a stochastic gradient descent algorithm convergent the standard Sobbins-Munte conditions are satisfied [2] When existing approaches are used, the posterior has

---

no dependence on w and the gradient V p(g is not accounted for, leading to gradient termss being dropped in the update. Stochastic gradient descent using these updates does not optimise any objective and so may not converge to any solution. The focus of our analysis in Section 4.1 is to extend convergent gradient methods for minimising the MSSBE to approximate inference techniques in situations where sampling from the posterior becomes intractable.
Minimising the MSBBE also avoids the double sampling problem encountered in frequentist RL where to minimise the mean squared Bellman error, two independent samples from P(s'[s, a) are required obtain unbiased gradient estimates [77. In BBO, this issue avoided by drawing two independent approximate Bellman operators Bø, and B from the posterior 01, 02 ~ )) instead.
3.1 Consistency of the Posterior
To address Question 2, develop set of theoretical results to understand the posterior's 's relationship to the RL problem. We introduce some mild regularity assumptions on our choice of model:
Assumption 2 (Regularity of Model). i) Qu bounded and (Φ, do) and (9, dg) are compact metric spaces; ii) B& is Lipschitz in o. P(b]s, 0, Φ) has finite variance and a density p(b]s, a, 6) which is Lipschitz in & and bounded; and iii) p()) exp (-R(6)) where R(Ø) is bounded and Lipschitz.
Our main result is Bernstein- von- wow- -ore--soo------------- Misss--tspeeeeeee theorem [9] applied to reinforcement learning. We prove that the posterior asymptotically converges to Dirac delta distribution centered on the set of parameters that minimise the KL. divergence between the true and model distributions, which are the frequentist maximum likelihood parameters:
O == arg min (L(P (b, 8, alw) || P(b, s, al)) arg min BP w) [- log p(b, s, alo)], deΦ
(8)
de
where the expectation is taken with respect to distribution that generates the data: (b 8, alw) that satisfies d.P (b, s, a/w) = dPP((bss, a, w dr (a) s)dp(s). We make simplifying assumption that there is single maximum likelihood parameter, which eases analysis and exposition of our results.
We discuss the more general case where it does not hold in Appendix
Assumption 3 (Single Minimiser). The set of maximum likelihood parameters &% defined in Eq. exists and is a singleton.
5 in the limit -> Do the posterior concentrates weakly on Φi= i) P)) = 8(0 = o%) a.s.; tn) B a.S., Bøy; and iit) MSBBE, (w) 9.3 112w - Bøy 11
Theorem 1. Under Assumptions
If
sufficiently represent the true conditional distribution then (L(Pa(b,& 8, alw) || P(h, 8, alot)) = 0 = Pb(b,s, a, w) = P(b]s, a, (t)- Theorem D proves that the posterior concentrates on the frequentist solutionn ot and hence the Bayesian Bellman operator con-
model
verges to the true Bellman operator: Bø: (s, a) = Ep(bls...z.)1
(pg((,),, [b] (iQ21(s. a).
As every Bellman operator characterises an MDP, any Bayesian RL solution obtained using the BBO posterior such as an optimal policy or value function is consistent with the true RL solution. When the true distribution is not in the model class, Bøg converges to the closest representation of the true Bellman operator according to the parametrisation that maximises the likelihood (bs(bbs,)))) [log p(b, s, al@)]. This is analogous frequeentit convergent TD learning where the function approximator converges to a parametrisation that minimises the projection the Bellman operator into the model class 77 12]
We now make this relationship precise by considering
Gaussian model.
3.2 Gaussian BBO
To showcase the power of Theorem and to provide a direct comparison to existing frequentist approaches, we consider the nonlinear Gaussian model P(b|s, a, Φ) (B o?) that is commonly used for Bayesian regression 55 33 The mean is a nonlinear function approximator
that best represents the Bellman operator B3 R BiQW] and the model variance o² > 0 represents the aleatoric uncertainty in our samples. Ignoring the log normaaaaaaisno constant Grom the log-posterior is an empirical mean squared error between the empirical Bellman samples and the model mean B& a:) with additional regularisation due to the prior (see Appendix D.2 for derivation):
NN
(b. BB( a,))
- log (D) = Caorm Σ
+ -R()), & E Argminn|BB. - BlQW1l (9)
202
deo
5

---

Theorem proves that in the limit N + oc, the effect of the prior diminishes and the Bayesian Bellman operator converges the parametrisation: B - Bag. As o% is the set of parameters that minimise the mean squared error between the true Bellman operator and the approximator, Bøg a projection of the true Bellman operator onto the space of functions represented by Bg: -Bi@ull
B PB, BlQu] == {Bs ø' arg Srggmin||
(10)
PE#
Finally, Theorem proves that the MSBBE converges to the mean squared projected Bellman error -PP
(SBBEx(w) (SPBE(W) = 11Qu - PB, B[@_]l| By the definition of the projection
operator in Eq. 10 a solution Qu PBB BlQ is a TD fixed point; hence any asymptotic MSBBE minimiser parametrises a TD fixed point should it exist. To further highlight the relationship between BBO and convergent TD algorithms that minimise the mean squared projected Bellman operator, we explore the linear Gaussian regression model as case study in Appendix allowing us to derive a regularised Bayesian TDC/GTD2 algorithm
4 A Approximate BBO
We have demonstrated in Eq. 7 that if is tractable to sample from the posterior, a simple convergent stochastic gradient descent algorithm can be used to minimise the MSBBE. We derive the gradient update for the linear Gaussian model as part of our case study in Appendix E Unfortunately, models like linear Gaussians that have analytic posteriors Bellman operator for domains of practical interest in RL. We now extend our analysis to include approximate inference approaches.
often too simple to accurately represent the
4.1 Approximate Inference
To allow for more expressive nonlinear function approximators, for which the posterior normalisation intractable, we introduce a tractable posterior approximation: (())D.) s ). this paper, we use randomised priors (RP) S for approximate inference. Randomised priors (PR) inject noise into the maximum a posteriori (MAP) estimate via a noise variable e E & with distribution Pg(e) where the density Pg(e) has the same form the prior. We provide full exposition of RP for BBO in Appendix F including derivations of our objectives. RP in practice uses ensembling: L prior randomisations &, == f=
first drawn from PE. To use RP for BBO, write the Q-
function approximator as an ensemble of L parameters Q2 == fwi hE=1L where Q = 1 E' Qu and require an assumption about the prior and the function spaces used for approximators:
Assumption 4 (RP Function Spaces). i) Qun and Ba, share function space, that is Qw; Bug for any w/ E Ω2 where & = Q C R" is compact, convex with a smooth boundary. ii) E C IR" and R( <) defined for any ø E &,
E. E
For each 1 E (1 T.), a set of solutions to the prior-randomised MAP objective are found:
(5 E arg L(0;; DN 4) = arg min Φe
N R(o -1) Σ log p(p 88, (s,
(11)
ΦEΦ
The RP solution ot (wi) has dependence on Wi that mirrors the BBO posterior's dependence on w. To construct the RP approximate posterior q(olD))) ), we average the set of perturbed MAP estimates over all ensembles: ((()D))= =
E vo (wi)). To sample from the RP posterior E 8(6 =
q(-1110 (D),,, we sample an ensemble uniformly ~ Unif([1: L)) and set Φ = vot (wi). Although BBO is compatible with any approximate inference technique, we justify our choice of RP by proving
that it preserves the consistency results developed in Theorem
Corollary 1.1. Under Assumptions the RP approximate posterior q( ((olD) both with or without ensembling.
results i)-iii) of Theorem hold with P( replaced by
In answer to Question 3), Corollary posterior and the true posterior lies in their characterisation of uncertainty and not their asymptotic behaviour. Existing work shows that RP uncertainty estimates are conservative (59] 21 with strong
shows that the difference between using the RP approximate
empirical performance in RL [57] 58
for the Gaussian model that we study in this paper.
The RP approximate posterior ( depends on the ensemble of Q-function approximators Q.., and like in Section we must learn ensemble of optimal parametrisations wf. We substitute

---

for q( ) in place of the true posterior in Eqs. 5 and )) to derive an ensembled RP MSBBE: MSBBERP (wr) == I!Q., Bet (wx) (w)) When a fixed point Qwi Bey (ma) exists, minimising
MSBBERr (wy) is equivalent to finding wj such that (wF) wT. To learn w/ can instead minimise the simpler parameter objective wf E arg minween ((Wi vt)):
(wwr (8) | 48 (w)) such that (1(()) E arg min L(o; D 1 Ez),
(12)
oeo
which has the advantage that deterministic gradient updates can be obtained. U(wr v/) can still provide an alternative auxilliary objective when a fixed point does not exist as the convergence of algorithms minimising Eq. (12) does not depend on its existence and has the same solution as minimising (SB for sufficiently smooth Bg. Solving the bi-level optimisation problem Eq. (12) is NP-hard [. To tackle this problem, we introduce an ensemble of parameters V == fub to track 27 (wr) and propose a -wo-timescale gradient update for each E {1 : L} on the objectives in Eq. 12 with per-step complexity of (n)):
4/2 + Pa (ahr ag Ve, (R( (1/ q)) log p(b; (s,, ag, vr))), (fast)
(13)
W1 - Pa(wi - Bu( v))),, (slow)
(14)
where 0g and Bg are asymptotically faster and slower stepsizes respectively and Pa(+) = arg min -Wll is projection operator that projects its argument back into f2 if necessary. From a Bayesian perspective, we are concerned with characterising the uncertainty after a finite number of samples N < oo and hence (b,, 8c, ai) should be drawn uniformly from the dataset D.N to form estimates of the summation in Eq. [T]. which becomes intractable with large N. When compared to existing RL algorithms, sampling from D.,, is analogous to sampling from a replay buffer [54]. A frequentist analysis of our updates is also possible by considering samples that are drawn online from the underlying data generating distribution (b;, 8,, 0.)) ~ PB in the limit N + co. We discuss this
wi
frequentist interpretation further in Appendix
To answer Question 4), we prove convergence of updates
and 14) using straightforward
application of two-timescale stochastic approximation 15 14 42 to BBO. Intuitively, two timescale analysis proves that the faster timescale update (13) converges to an element in P using standard
martingale arguments, viewing the parameter w/ quasi-static as it behaves like a constant. Since the perturbations are relatively small, the separation of timescales then ensures that t/ tracks vo (wi) whenever is updated in the slower timescale update (14), viewing the parameter th quasi- cquilibrated [E]] We introduce the standard two-timescale regularity assumptions and derive the limiting ODEs of updates (L) and (4 in Appendix
C.3
Assumption (Two-timescale Regularity). i) V R(gh - e1) and V blggp(bsss as th1) are Lips- chitz in thr and (b,, 8,, a:)) Unif(DM) wi ); ü) t (wi) uf are local aysmptotically stable attractors of the limiting ODEs of updates
13 and 14 respectively and w/ (wi) is Lipschitz in wi; and ii) The stepsizes satisfy: limg Be
Dc
Crk Em 3a =0, E (ak - -BR) < co.
Am
Theorem 2. If Assumptions
hold, di and wi converge to 3i (w) and w almost surely.
As W/ are updated on a slower timescale, they lag the parameters 1hy When deriving a Bayesian demonstrate that these parameters share similar role to a lagged critic. There is no Bayesian explanation for these parameters under existing approaches: when applying approximate inference P(Q" a, DVN. the RP solution dij has dependence on w/. Hence, minimising U(w;; vi7 and the approximate MSBBE has an exact solution by setting wi -o. In this case, Qw, Bey meaning that existing approaches do not distinguish between the Q-function and Bellman operator approximators.
actor-critic algorithm in Section 42
4.2 Bayesian Bellman Actor-Critic
BootDQN+Prior (57 58 state-of-the-ar Bayesian model-free algorithm with Thompson sampling [74] where, in principle, an optimal Q-function is drawn from posterior over optimal Q-functions at the start of each episode. As BootDQN+Prior requires boot- strapping, it actually draws sample from the Gaus- sian BBO posterior introduced in Section 3.2 using RP approximate inference with the empirical Bellman
Bog (nis)
(mls)
Tireet Crities
Critios
Exploration Policios
Fi (...(()....))
Par(fie)
a (els)
Behortoural
Policy
= r()
Rextronment
Figure 2: Schematic of RP-BBAC.
7

---

function .s..,,.ss) = (ss, a, +y max, Qw(('s
This empirical Bellman function results from substituting an optimal policy a(a(s) 8(a arg m (s, )')) in Eq.
B A variable I is drawn uniformly and the optimal exploration policy n (als) ō(a E arg max, Bş, (s. d')) is followed. BootDQN+Prior achieves what Osband et al. [58] call deep exploration where exploration not only considers immediate information gain but also the consequences of exploratory action future learning. Due its use of the arg max operator, BootDQN Prior is not appropriate for continuous action or large discrete action domains as nonlinear optimisation problem must be solved every time an action is sampled. We instead develop a randomised priors Bayesian Bellman actor-critic (RP-BBAC) to extend BootDON+Prior to continuous domains. A schematic of RP-BBAC is shown in Fig. 2 which summarises Algorithm Additional details are in Appendix
Comparison to existing actor-crities: Using a Gaussian model also allows direct compari- son frequentist actor-critic algorithms [50]: as shown in Fig. every ensemble I E {1...} has its own exploratory actor Te,, critic By, and target critic Qwi- In BBAC, each critic is the solution its unique <-randomised empirical MSBBE objective from Eq. 12): Lense = - Ei= (b, B (s;, R(er G). The target critic parameters wi for each Bellman sample b, = =;; + (s/, af) are updated on slower timescale to the critic parameters, which mimics the updating of target critic parameters after a regular interval in frequentist approaches 154 39]. We introduce an ensemble of parametric exploration policies Te, (a|s) parametrised by a set of parameters O, = (-.... Each optimal exploration policy कद (a(s) is parametrised by the solution to its own optimisation problem: 0, E arg maxg,ce (p(()) [Bor (s, a')]. Un- like frequentist approaches, an exploratory actor is selected at the start of each episode in accor- dance with our current uncertainty in the MDP characterised by the approximate RP posterior. Exploration is thus both deep and adaptive actions from an exploration policy are directed towards min- imising epistemic uncertainty in the MDP and the posterior variance reduces in accordance with Corol- lary as more data is collected. BBAC's explicit specification of lagged target critics is unique to BBO and, as discussed in Section 4. corrects the theo- retical issues raised by applying bootstrapping to ex- isting model-free Bayesian RL theory, which does not account for the posterior's dependence Finally, exploration policies may not perform well test time, so we learn behaviour policy T&i (als) parametrised by Øt E ④ from the data collected by our exploration policies using the ensemble critics: (B&,, 1 Theoretically, this is the optimal policy for the Bayesian estimate of the true MDP by using the approximate posterior to marginalise over the ensemble of Bellman operators. We augment our behaviour policy objective with entropy regularisation, allowing us to combine the exploratory bene- fits of Thompson sampling with the faster convergence rates and algorithmic stability of regularised
Algorithm RP-BBAC
Initialise L,, Lz, EL. H and D t- Ø
Sample initial state Po
while not converged do
Sample policy O₃ Uni for n E (1,....Nemv) do
Sample action To, (-1s) Observe next state s' ~ P(.
Qu-
Observe reward r(s' a,
DD x- 'D (8, end for
Oz, lzg V t UPDATEPOSTERIOR +- UTDATBELLAIIOURAPPOLLYY end while
RL
5
Related Work
Existing model-free Bayesian RL approaches assume either a parametric Gaussian +
58 75
or Gaussian process regression model 28 29 Value-based approaches use the empirical
Bellman function (s',, s) = r(s', a, + max, (s', a') whereas actor-critic approaches use the empirical Bellman function (s', a', s,a) = r(s', a.s) s) + Qw a'). In answering Questions 1-4, we have shown existing methods that use bootstrapping inadvertently approximate the posterior predictive over Q-functions with the BBO posterior predictive P(Q (s, a, DN) se P(b]s, a, D ). These methods minimise an approximation of the MSBBE where the Bayesian Bellman operator is treated as supervised target, ignoring its dependence on gradient descent approaches drop gradient terms and fitted approaches iteratively regress the Q-function approximator onto the Bayesian Bellman operator Qua++ 1 +- B In both cases, the updates may not be a contraction mapping for the same reasons in non- Bayyssann TD 76 and it is not possible to prove general convergence.
8

---

The additional Bayesian regularisation introduced from the prior can lead to convergence, but only in specific and restrictive cases
Approximate inference presents an additional problem for existing approaches: many existing methods naïvely apply approximate inference to the Bellman error, treating [(Q"](s, a) and (* a) This leads to poor uncertainty estimates as the Bellman error cannot correctly propagate the uncertainty [50 57 Osband et al. [38 demonstrate that this can cause uncertainty estimates of Q* (s, a) at some (s, a) to be zero and propose BootDQN+Prrior as an alternative to achieve deep exploration. BBO does not suffer this issue as the posterior characterises the uncertainty in the Bellman operator directly. In Section 4.2 we demonstrated that BootDQN+Prinn derived from BBO specifies the use of target critics. Despite being essential to performance, there no Bayesian explanation for target critics under existing model-free Bayesian RI theory, which
as independent variables 32
2
7
34
posits that sampling a critic from P(Q") [s, a, DN)
) is sufficient.
6 Experiments
Y.MSE
10a
GTD2
BBO
10a
TD(0)
Convergent Nonlinear Policy Evaluation To confirm our con- vergence and consistency results under approximation, we evaluate BBO in several nonlinear policy evaluation experiments that are constructed to present a convergence challenge for TD algorithms. We verify the convergence of nonlinear Gaussian BBO in the fa- Figure 3: Tsitsiklis counterexample.
100 0
TDC
2
Training Steps [10P]
mous counterexample task of Tsitsiklis and Van Roy 77). in which the TD(0) algorithm is provably
divergent. The results are presented in Fig. S As expected, TD(0) diverges, while BBO converges to the optimal solution faster than convergent frequentist nonlinear TDC and GTD2 ([22) We also consider three additional policy evaluation tasks commonly used to test convergence of nonlinear TD using neural network function approximators: 20-Link Pendulum 2 Puddle World [I and Mountain Car [6.. Results are shown in Fig. [ of Appendix H.3 from which we conclude that i) by ignoring the posterior's dependence on w, existing model- Bayesian approaches are less stable and perform poorly in comparison to the gradient based MSBBE minimisation approach in Eq. D ii) regularisation from prior improve performance of policy evaluation by aiding the optimisation landscape 2 and iii) better solutions in terms of mean squared error can be found using BBO instead of the local linearisation approach of nonlinear [DC/GTD2(2])
Exploration for Continuous Control In many benchmark tasks for continuous RL, such as the locomotion tasks from MuJoCo
0 100
BAC
-10 return
500
BRAC
SAC
SAC'
BAC BBAC
SAC
Gym suite [I8.. the environment reward is shaped to provide a smooth gradient towards successful task completion and naïve Boltz- mann dithering exploration strategies from reg- ularised RL can provide strong inductive bias. In practical real-world scenarios, dense rewards are difficult to specify by hand, especially when the task learned from raw observations like images. Therefore, we consider set of continuous control tasks with sparse rewards as continuous analogues of the discrete experiments used to test from Gym benchmark suite and slightly modi- fied version of the cartpole-swingu sparse from DeepMind Control Suite 7A Both environments have a sparse reward signal and penalize the agent proportional to the magnitude of executed actions. As the agent is always initialised in the same state, it has to deeply explore costly states in directed manner for hundreds of steps until it reaches the rewarding region of the state space. We compare RP- with two variants of the state-of-the-an soft actor-critic: SAC, which is the exact algorithm presented in 40 and SAC*, tailored version which uses a single Q-function to avoid pessimistic underexploration 120 due to the use of the couble-minimumg Q trick (see Appendix for details). To understand the practical implications of our theoretical results, we also compare against BAC which is a variant of BBC where Q., = Bey. As we discussed in Section 4.1 BAC is the Bayesian actor-critic that results from applying RP approximate inference to the posterior over Q-funtioons used by existing model-free Bayesian approaches with bootstrapping.
SAC"
50
100
3
samples [1e3]
samples [1e6]
(a) MountainCar
(b) Cartpole
Figure 4: Continuous control with sparse reward.
BootDQN+Prior [57]
The results are shown in Fig. Due to the lack of smooth signal towards the task completion, SAC consistently fails to solve the tasks and converges to always executing the O-action due to the action cost term, while SAC* achieves the goal in one out of five seeds. RP-BBAC succeeds for all five seeds in both tasks. To understand why, we provide a state support analysis in for

---

Appendix I.I The final plots are shown in Fig. and confirm that the deep, adaptive exploration carried out by RP-BBAC leads agents to systematically explore regions of the state-action space with high uncertainty. The same analysis for SAC and SAC* confirms the inefficiency of the exploration typical of RI. as inference: the agent repeatedly explores actions that lead to poor performance and rarely explores beyond its initial state. The state support analysis for BAC Appendix L. confirms that by using the posterior over Q-functions with bootstrapping, existing model-free Bayesian RL cannot accurately capture the uncertainty in the MDP. Initially, exploration similar to RP-BBAC but epistemic uncertainty estimates are unstable and cannot concentrate due to the convergence issues highlighted in this paper, preventing adaptive exploration.
MountainCar-Contin
Our results in Fig. 4 demonstrate that the theoretical issues
1.0
1.0
with existing approaches have negative empirical conse- quences, verifying that is essential for Bayesian model- free RI. algorithms with bootstrapping to sample from the BBO posterior as BAC fails to solve both tasks where sam- pling from the correct posterior in RP-BBAC succeeds. In Appendix L.2 we also investigate RP-BBAC's sensi- tivity to randomized prior hyperparameters. The range of working hyperparameters is wide and easy to tune.
Valtatoo Hequiay
0.5
0.5
0-10
Pootiam
Figure 5: State
Support for RP-
BBAC (left)
and SAC (right) in
7 Conclusion
By introducing the BBO framework, we have addressed a major theoretical issue with model-free Bayesian RL by analysing the posterior that is inferred when bootsrapping is used. Our theoretical results proved consistency with frequentist RL and strong convergence properties, even under posterior approximation. We used BBO to extend BootDQN+ continuous domains. Our experiments in environments where rewards not hand-crafted aid exploration demonstrate that sampling from the BBO posterior characterises uncertainty correctly and algorithms derived from BBO can succeed where state-of-the-arr algorithms fail catastrophically due to their lack of deep exploration. Future research could experiment with novel inference techniques, more complex priors and likelihoods, especially if they depend on w, extend our convergence analysis to the actor-critic algorithm.
Acknowledgements
This project has received funding from the European Research Council (ERC) under the Euro- pean Unions Horizon 2020 research and innovation programme (grant agreement number 637713). Matthew Fellows and Kristian Hartikainen are funded by the EPSRC. The experiments possible by generous equipment grant from NVIDIA. We would like to thank Piotr Miloš, whose proof for similar problem inspired our proof of Lemma
made
References
[1] Daron Acemoglu and Pascual Restrepo. Artificial intelligence, automation, and work. In The Economics of Artificial Intelligence: An Agenda, pages 197-236. National Bureau of Eco- nomic Research, Inc, 2018. URL
repec. org/ /wt//eeeeeeeeeeeeeeeeeeeeeeeeeee ReePeePPeec :nbr
bberch: 14027
B
[2] Daron Acemoglu and Pascual Restrepo. Unpacking skill bias: Automation and new tasks. AEA Papers and Proceedings, 110:356-61, May 2020. doi: 10. 20112///dddd2222200066 URL.
www. httpoe/swww..eeeurooorrrrrrreeee
B
[3] Donald Andrews. Generic uniform convergence. Econometric Theory, 8(2):241-257) 1992.
[4] András Antos, Rémi Munos, and Csaba Szepesvári. Fitted q-iteration in continuous action-space mdps. In Proceedings of the 20th International Conference on Neural Information Processing Systems. NIPS' 07, page 9-16, Red Hook, NY, USA, 2007. Curran Associates Inc. ISBN 978 9781605603520.
[5] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-122 -299 2008. doi: 10. 10.10077750099440070-008-----
10

---

[6] John Asmuth and Michael Littman. Learning is planning: near bayes-optimal reinforcement learning via monte-carlo tree search. Proceedings of the Aventy-Seventh Conference on Uncer- lainty in Artificial Intelligence, pages 19-26, 01 2011. 2.2
[7] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. Machine 00043702. doi: 10.1...48.3256 g
Workshop Then Conference-, pages 30-37, July 1995. ISSN
[8] F. Bard. Some properties of the bilevel programming problem. J. Optim. Theory Appl., 68(2):
371-378, February 1991. ISSN 0022-3239. 4.1
[9] R.F. Bass. Real Analysis for Graduate Students, chapter 21. Createspace Ind Pub, 2013. ISBN 978 1481 4881869140. M
[10] Matthew James Beal. Variational algorithms for approximate Bayesian inference. PhD thesis, Gatsby Computational Neuroscience Unit, University College London, 2003. 2.2
[11] Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on rein- forcement learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 449-458, International Convention Centre, Sydney, Australia, 06-11 Aug 2017.
PMLR.
2.2
[12] Shalabh Bhatnagar, Doina Precup. David Silver, Richard S Sutton, Hamid R. Maei, and Csaba Szepesvári. Convergent temporal-differenn learning with arbitrary smooth function approximation. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1204-1212. Curran Associates, Inc., 2009. 3.1 6 C.3
H.2.
H.2.2 H.2.3
[13] Patrick Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York, second edition, 1999. ISBN 0-471-19745-9 A Wilee--nterscience Publication.
[14] Vivek Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Book Agency, 01 2008. ISBN
doi: 10.1007/978-99-8827999
[15] Vivek S. Borkar. Stochastic approximation with two time scales. Syst. Control Lett., 29(5): 291-294, February 1997. ISSN 0167-6911. doi: 10. (0.0006650166-661117799900333330 4.1
[16] Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In G. Tesauro, D. S. Touretzky, and T. K. Leen, editors. Advances in Neural Information Processing Systems 7, pages 369-376. MIT Press, 1995. 6
1KLI
[17] David Brandfonbrener and Joan Bruna. Geometric insights into the convergence of nonlinear td learning. In ICLR 2020, 2019. S
[18] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 1506.0:4000.114000 2016. L.I
[19] Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In 7th International Conference on Learning Repre- sentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https://cpenreviiet net forum idd eN2
C.3
[20] Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. optimistic actor-critic. arXiv preprint 19t:::190..88800 2019.
Better exploration with
[21] Kamil Ciosek, Vincent Fortuin, Ryota Tomioka, Katja Hofmann, and Richard Turner. Conser- vative uncertainty estimation by fitting prior networks. In Eighth International Conference on Learning Representations, April 2020. 4.
[22] David Roxbee Cox and David Victor Hinkley. Theoretical statistics. Chapman and Hall, London, 1974. ISBN 0412124203, |
11

---

[23] Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences:
survey and comparison. Journal of Machine Learning Research, 15:809-888 883, 2014. 6 H.1
H.3.1
H.3.2
H.3.2
[24] Brumo de Finetti. La prévision : ses lois logiques, ses sourees subjectives. Annales de l'institut Henri Poincaré, 7(1):1-66 168. 1937. D
[25] Y. Deng, F. Bao, Y. Kong, Z. Ren, and Q. Dai. Deep direct reinforcement learning for financial signal representation and trading. IEEE Transactions on Neural Networks and Learning Systems, 28(3):653-664, 2017.
[26] Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In Doina Precup and Yee Whye Teh, editors, Proceed- ings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1049-1058, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[27] Michael O' Gorddon Duff and Andrew Barto. Optimal Learning: Computational Procedures for Bayes-Adaptive Markov Decision Processes. PhD thesis, University of Massachusetts Amherst, 2002. AA13039353. 2
(28) Yaakov Engel, Shie Mannor, and Ron Meir. Bayes meets bellman: The gaussian process approach to temporal difference learning. In Proceedings of the Twentieth International Conference International Conference Machine Learning, ICML'03, page 154-161, 2003. ISBN 1577351894.
[29] Yaakov Engel, Shie Mannor, and Ron Meir. Reinforcement learning with gaussian pro- cesses. In Proceedings of the 22nd International Conference on Machine Learning, ICML '05, page 201-208, New York, NY. USA, 2005. Association for Computing Machinery. ISBN 1595931805. doi: 10.1145/1102351 102377. URL
1102351. 1102377
[30] Matthew Fellows, Kamil Ciosek, and Shimon Whiteson. Fourier Policy Gradients. In ICML,
2018. G
[31] Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 15456-15467. Curran Associates,
Inc., 2019. 5
[32] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alexan- der Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. Proceedings of the International Conference on Representation Learning (ICLR 2018), Vancouver (Canada), 2018. 5
[33] Yarin Gal. Uncertainty in Deep Learning. PhD thesis, University of Cambridge, 2016.
[34] Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML'16, page 1050- 1059. JMLR.org, 2016.
[35] M. Ghavamzadeh, S. Mannor, J. Pineau, and A. Tamar. Bayesian Reinforcement Learning: Survey. now, 2015. ISBN null. 2.2
[36] W.R. Gilks, S. Richardson, and D. Spiegelhalter. Markov Chain Monte Carlo in Practice, chapter Introduction General State-Space Markov Chain Theory. Chapman & Hall/CRC Interdisciplinary Statistics. Taylor & Francis, 1995, ISBN 9780412055515 U
[37] Adam Greenfield. Radical Technologies: The Design of Everyday Life. Verso, 2018 ISBN 1784780456. B
12

---

[38] Arthur Guez, David Silver, and Peter Dayan. Scalable and efficient aaweeevv reinforcement learning based on monte-carlo tree search. Journal of Artificial Intelligence Research, 48:841- 883, 10 2013. doi: 10. 16116633310 10.16//jair.4111 2.2
[39] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Muchine Learning Research, pages 1861-1870, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[40] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic algorithms and applications. CoRR, abs/1812.0500 2018.
[41] Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 1944-2952 Curran Associates, Inc., 2015. G
[42] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge local nash equilibrium. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6626-6637, Curran Associates,
Inc., 2017.
[43] Zhengyao Jiang, Dixing Xu, and Jinjun Liang. A deep reinforcement learning framework for the financial portfolio management problem. 06 2017. B
[44] Michael I. Jordan, editor. Learning in Graphical Models. MIT Press, Cambridge, MA, USA, 1999. ISBN 0-262-60032-33,
[45] Prasenjit Karmakar and Shalabh Bhatnagar. Two time-scale stochastic approximation with controlled markov noise and off-policy temporal-differrecce learning. Math. Oper. Res., 43(1): 130-151, February 2018 ISSN 0364-765X. doi: 10. 1287/mmoo:2011.088885 201.0085.
URL https
//doi.org/// 1287 /ww.r/oo..////////oooo/oo.ooo..m 2017 0855
C.5
[46] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv:1412.69880 2014. H.3.4
[47] Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun, editors, ICLR, 2014. 2.2
[48] Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab. Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey,
2020. 3
[49] B.J.K. Kleijn and A.W. van der Vaart. The bernstein-von-mine theorem under misspecification. Electron. J. Statist., 6:354-381, 2012. doi: 10.1214/12-E/565. B.1
[50] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12, pages 1008-1014. MIT Press, 2000.
[51] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable pre- dictive uncertainty estimation using deep ensembles. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems 30, pages 6402-6413. Curran Associates, Inc., 2017. 2.2
[52] Zachary Lipton, Xiujun Li, Jianfeng Gao, Lihong Li, Faisal Ahmed, and li Deng. Bhq-networks: Efficient exploration in deep reinforcement learning for task-oriented dialogue systems. AAAI, 11 2018.
[53] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina I Lerman, and Aram Galstyan. survey bias and fairness in machine learning. 08 2019. B
13

---

[54] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller. Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King. Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 5 (18(5540)5529533. February 2015. ISSN 002800866.
[55] Kevin P. Murphy. Machine Learning: A Probabilistic Perspective, chapter 7. The MIT Press, 2012. ISBN 0262018020, 9780262018029. 3.2
[56] Brendan O'Donoghue, Ian Osband, Remi Munos, and Vlad Mnih. The uncertainty Bellman equation and exploration. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3839-3848, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018.
PMLR.
5
[57] lan Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforce- ment learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 8617-8629. Curran Associates, Inc., 2018
G
[58] Ian Osband, Benjamin Van Roy, Daniel J. Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124): 2019.
[59] Tim Pearce, Mohamed Zaki, Alexandra Brintrup, and Andy Neely. Uncertainty in neural networks: Bayesian ensembling. ArXiv Preprint, abs/1810.00546, 10 2019.
[60] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779,
2.1
[61] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. Interna- tional Conference on Machine Learning, 37:1530-1553 1538, 07-09 Jul 2015. 2.2
[62] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3) 407, 1951. doi: 10. /111////m//1177///90 URL URLhttps
//doi.org/1..110 1ttp:/10.1111111 aoms 1tt.2//////////17795523132 1177729586
[63] R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer Verlag. Heidelberg, Berlin, New York, 1998.
[64] Alexander Shapiro. On differentiabiliiy of metric projections in m, Boundary case. Proceed- ings of the American Mathematical Society, 99(1):13--228, 1987. ISSN 00029939, 10886826.
URL http://///// wwww wwt.srooor//ttalle/ee/e
[65] Alexander Shapiro. Directional diffcrentiability of metric projections onto moving sets at boundary points, Journal of Mathematical Analysis and Applications, 131(2):392-403 1988.
ISSN 0022-247X. doi: http:/ocww....cooococc.....eeeed
URL https:////// //www www
sciencedirect. com/ /cl.aaneeirreettco//////eaaaaaar
C.3
[66] Adam Smith and Janna Anderson. Ai, robotics, and the future jobs. 2017.
[67] L. Song, K. Fukumizu, and A. Gretton. Kernel embeddings of conditional distributions: A unified kernel framework for nonparametric inference in graphical models. IEEE Signal Processing Magazine, 30(4):98-111, 2013. doi: 10. 10.1109/MSP.2013.2252777
[68] Thomas Spooner, Rahul Savani, John Fearnley, and Andreas Koukorinis. Market making via reinforcement learning. In /7th International Conference on Autonomous Agents and Multiagent
Systems, 07 2018. B
[69] Nick Srnicek and Alex Williams. Inventing the future: postcapitalism and a world without work. Verso, 2015. ISBN 9781998888 178478066. B
14

---

[70] Richard S Sutton, Hamid R. Maei, and Csaba Szepesvári. A convergent o(n) sumporal-difereent algorithm for off off-po learning with linear function approximation. In D. Koller, D. Schuur- mans, Y. Bengio, and I.. Bottou, editors, Advances in Neural Information Processing Systems 21, pages 1609-1616. Curran Associates, Inc., 2009.
F.2
[71] Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast pradient-descent methods for lemporal-differene learning with linear function approximation. In Proceedings of the 26th Anmual International Conference on Machine Learning, ICML '09, pages 993-10000 New York, NY, USA, 2009. ACM. ISBN 978-1-60558-516-1 doi: 10. 145//555334.155330000
[72] Csaba Szepesvári. Algorithmss for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 4(1):1-103, 2010. ISSN 1939-4608. doi: 10.2200/ S00268ED1 VO1 Y201005AIM009.
[73] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv: 1801:0000000000 2018.
I.2
[74] William R Thomson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22 294, 12 1933. ISSN 0006-3444. doi: 10. 1093/biomeee2533-42255.
[75] Ahmed Touati, Harsh Satija, Joshua Romoff, Joelle Pineau, and Pascal Vincent. Randomized value functions via multiplicative normalizing flows. In Amir Globerson and Ricardo Silva, editors, UAI, page 156. AUAI Press, 2019.
[76] N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674-690, May 1997. ISSN 2334-3303. doi: 10. N..110099588777
H.2.1
[77] Nino Vieillard, Tadashi Kozuno, B. Scherrer, O. Pietquin, Rémi Munos, and M. Geist. Leverage the average: an analysis of regularization in rl. Advances in Neural Information Processing Systems, 33, 2020. 4.2
[78] Nikos Vlassis, Mohammad Ghavamzadeh, Shie Mannor, and Pascal Poupart. Bayesian Re- inforcement Learning, pages 359-386. Springer Berlin Heidelberg, 2012. ISBN 978-3-642- 27645-3. doi: 10.1007/978-3 0-17788--664-27766-- 11.
2.2
[79] David Williams. Probability with Martingales. Cambridge mathematical textbooks. Cambridge University Press, 1991. ISBN 978-0-521-40605-
[80] Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning healthcare: a survey. arXiv preprint 10Xxv:990.088707 2019. B
[81] EDUARDO H. ZARANTONELLO. Projections convex sets in hilbert space and spectral theory:
Part i. projections on convex sets: Part ii spectral theory. In Eduardo H. Zaran- tonello, editor, Contributions to Nonlinear Functional Analysis, pages 237-424. Academic doi:
Press, 1971. ISBN 978-0-12-775850:
3.50013-3 URL https : www. wwt.://ceeeeeeett.cooooaaaeeeeee 29780127758503500
[82] Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: A very good method for bayes-adaptive deep rl via meta- learning. 8th International Conference on Learning Representations, ICLR 2020, Virtual Conference, Formerly Addis Ababa ETHIOPIA, 2020. 2.2
Checklist
1. For all authors...
15

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] In this work we identified major theoretical issue with existing model-free Bayesian RI. approaches that claim to infer a posterior over Q-functions. We answered Questions to 2 of Section in Section and Questions 3 to 4 in Section g
(b) Did you describe the limitations of your work? [Yes] The purpose of this work about addressing a major theoretical limitation with existing model-free Bayesian RL. We show that this limitation can have profound empirical consequences in Section 6 As we have discussed, the assumptions of our theories are relatively weak and apply to wide range of settings and function approximators used for RL including nonlinear neural networks.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 2.3 and the further discussion in Appendix
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions to and our extensive discussion in Appendices and
(b) Did you include complete proofs of all theoretical results? [Yes] We provide a high level intuitive explanation of our theorems in the main text (see Section 3.1 and Section 4.1
with rigorous and detailed proofs in Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Provided in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "n-yRk_Jj6X", "reviewer": "Reviewer_Zz7u", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Post-rebuttal:\n\nI 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.\n\n---\n\nThe 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.\n\nThis 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.\n\nI 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:\n * 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.\n * 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.\n * 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.\n * 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.\n\nMinor comments:\n * 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.\n * In Figure 3, BBO seems to start with better MSE than GTD2/TDC; is the improved performance explainable due to better initialization?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, further discussion of the limitations of the work would be welcome.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UEV31SeHhNt", "reviewer": "Reviewer_TpMr", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n1. 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?\n2. 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.\n3. 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.\n4. 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}$.\n5. Ref. 22 is missing a full authors list.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "S_97AScUg-", "reviewer": "Reviewer_8tDK", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strenghts: \n- 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.\n- 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.\n- 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.\n\nWeaknesses:\n- 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:\n    - 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.\n    - 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.\n- W.r.t to the approach itself, I have only a few points that may turn out as weaknesses:\n    - 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?\n    - 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?\n    - 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?\n    - 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}?\n    - 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?\n\nCorrectness:\n- 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.\n\nClarity:\n- 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.\n- 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.\n\nOther:\n- The equation in line 1147 of the appendix misses a bracket\n- 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?\n- In line 262 of the main text: \"minimise\" instead of minimising\n\t", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The Impact has been adequately addressed, especially given that the authors propose an abstract method for reinforcement learning.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "R39YL5XNLLI", "reviewer": "Reviewer_NoL3", "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.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Significance\n\nThe 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.\n\n## Originality\n\nEven 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.\n\n## Quality\n\nThe 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.\n\nA concern I have is that $\\phi^*_\\omega$ can be non-unique, especially with neural networks. How does this affect stability? \n\n\n## Clarity\n\nThe 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? \n\nIt 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. \n\nNotation is sometimes overridden. Eg, $b_\\omega$ is a function but $b_i$ is random variable. This further complicates things.\n\nA table of notation would help the exposition greatly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential negative societal impact is adequately addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)