Bayesian Bellman Operators
Year: 2022

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.

heading: 1 Introduction
text: A Bayesian approach to reinforcement learning (RL) characterises uncertainty in the Markov decision process (MDP) via a posterior [35, 78]. A great advantage of Bayesian RL is that it offers a natural and elegant solution to the exploration/exploitation 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 "-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 are Bayesian [22] because a non-Bayesian decision can always be improved upon by a Bayesian agent [24]. In addition, pre-existing domain knowledge can be formally incorporated by specifying priors.
In model-free Bayesian RL, a posterior is 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 is not accounted for. It is unclear what posterior, if any, these methods are inferring and how it relates to the RL problem.
In this paper, we introduce Bayesian Bellman Operators (BBO), a novel model-free Bayesian RL framework that addresses this issue and facilitates a theoretical exposition of the relationship between model-free Bayesian and frequentist RL approaches. Using our framework, we demonstrate that, by bootstrapping, model-free Bayesian RL infers a posterior over Bellman operators. For our main contribution, we prove that the BBO posterior concentrates on the true Bellman operator (or the closest representation in our function space of Bellman operators). Hence a 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 matthew.fellows@cs.ox.ac.uk
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Our framework is general and can recover empirically successful algorithms such as BootDQNprior+ [57]. We demonstrate that BootDQNprior+’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 RL 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 like soft actor-critic [39] fail catastrophically due to their inability to properly explore.

heading: 2 Bayesian Reinforcement Learning
text: To aid the reader with notation, we provide a mathematical glossary in Appendix A.

heading: 2.1 Preliminaries
text: Formally, an RL problem is modelled as a Markov decision process (MDP) defined by the tuple hS,A, r, P, P0, i [72, 60], where S is the set of states and A the set of available actions. At time t, an agent in state st 2 S chooses an action at 2 A according to the policy at ⇠ ⇡(·|st). The agent transitions to a new state according to the state transition distribution st+1 ⇠ P (·|st, at) which induces a scalar reward rt := r(st+1, at, st) 2 R with sups0,a,s|r(s0, a, s)| <1. The initial state distribution for the agent is s0 ⇠ P0 and the state-action transition distribution is denoted as P⇡(s0, a0|s, a), which satisfies dP⇡(s0, a0|s, a) = d⇡(a0|s0)dP (s0|s, a).. As the agent interacts with the environment it gathers a trajectory: (s0, a0, r0, s1, a1, r1, s2...). We seek an optimal policy ⇡⇤ 2 argmax⇡ J⇡ that maximises the total expected discounted return: J⇡ := E⇡ [ P1 t=0
trt] where E⇡ is the expectation over trajectories induced by ⇡. The Q-function is the total expected reward as a function of a state-action pair: Q⇡(s, a) := E⇡[ P1 t=0 rt|s0 = s, a0 = a]. Any Q-function satisfies the Bellman equation B[Q⇡] = Q⇡ where the Bellman operator is defined as:
B[Q⇡](s, a) := EP⇡(s0,a0|s,a) [r(s0, a, s) + Q⇡(s0, a0)] . (1)

heading: 2.2 Model-based vs Model-free Bayesian RL
text: Bayes-adaptive MDPs (BAMDPs) [27] are a framework for model-based Bayesian reinforcement learning where a posterior marginalises over the uncertainty in the unknown transition distribution and reward functions to derive a 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 to 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 [82] which exploits a 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 a Bayesian regression problem to infer a posterior predictive over a value function [78, 35]. Whilst foregoing the ability to separately model reward uncertainty and transition dynamics, modelling uncertainty in a 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, 10, 47, 61, 33, 51]. These methods assume access to a dataset of N samples: DN := {qi}i=1:N from a distribution over the true Qfunction at each state-action pair: qi ⇠ PQ(·|si, ai). Each sample is an estimate of a point of the true Q-function qi = Q⇡(si, ai) + ⌘i corrupted by noise ⌘i. By introducing a probabilistic model of this random process, the posterior over the Q-function P (Q⇡|s, a,DN ) can be inferred, which characterises the aleatoric uncertainty in the sample noise and epistemic uncertainty in the model. Modeling aleatoric uncertainty is the goal of distributional RL [11]. In Bayesian RL we are more concerned with epistemic uncertainty, which can be reduced by exploration [57].

heading: 2.3 Theoretical Issues with Existing Approaches
text: 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 Q̂! : S ⇥A ! R parametrised by ! 2 ⌦ is learnt as an approximation of the Q-function Q̂! ⇡ Q⇡ and then a TD sample is used in place of qi. For example a one-step TD estimate approximates the samples as: qi ⇡ ri + Q̂!(si, ai), introducing an error that is dependent on !. Existing approaches do not account for this error’s dependency on the function approximator.
Samples are no longer noisy estimates of a point Q⇡(si, ai) and the resulting posterior predictive is not P (Q⇡|s, a,DN ) as it has dependence on Q̂! 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 a 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 to solving the RL problem?
3. What effect does approximate inference have on the solution?
4. Do methods that sample from an 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 a 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 !1 and is analogous to 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 a wide range of real-world applications of RL where identifying decisions that are being made under high uncertainty is crucial. We discuss the impact of our work further in Appendix B.

heading: 3 Bayesian Bellman Operators
text: Detailed proofs and a discussion of assumptions for all theoretical results are found in Appendix C.
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 Q̂! as an expectation of the empirical Bellman function b!:
B[Q̂!](s, a) = EP⇡(s0,a0|a,s) [b!(s0, a0, s, a)] , b!(s0, a0, s, a) := r(s0, a, s) + Q̂!(s0, a0). (2)
When evaluating the Bellman operator to solve the Bellman equation, we can evaluate the function approximator Q̂!(s, a) but we cannot evaluate B[Q̂!](s, a) due to the uncertainty in reward function and transition distribution. In BBO we capture this uncertainty by treating the empirical Bellman function as a transformation of variables b!(·, s, a) : S ⇥A! R for each (s, a). The transformed variable B : R ! R has a conditional distribution PB(b|s, a,!) which is the pushforward of P⇡(s0, a0|s, a) under the transformation b!(·, s, a). For any PB-integrable function f : R! R, the pushforward satisfies:
EPB(b|s,a,!) [f(b)] = EP⇡(s0,a0|s,a) [f b!(s0, a0, s, a)] . (3)
As the pushforward PB(b|s, a,!) is a distribution over empirical Bellman functions, each sample b ⇠ PB(·|s, a,!) is a noisy sample of the Bellman operator at a point: bi = B[Q̂!](si, ai) + ⌘i. To prove this, observe that taking expectations of b recovers B[Q̂!](s, a):
EPB(b|s,a,!)[b] =|{z} Eq. (3) EP⇡(s0,a0|s,a) [b!(s0, a0, s, a)] =|{z} Eq. (2) B[Q̂!](s, a).
si
ai
bi N
Figure 1: Graphical Model for BBO.
As the agent interacts with the environment, it obtains samples from the transition distribution s0i ⇠ P (·|si, ai) and policy a0i ⇠ ⇡(·|s0i). From Eq. (3) a sample from the distribution bi ⇠ PB(·|si, ai,!) is obtained from these state-action pairs by applying the empirical Bellman function bi = ri+ Q̂!(s0i, a0i). As we discussed in Section 2.3, existing model-free Bayesian RL approaches incorrectly treat each bi as a sample from a distribution over the value function PQ(Q⇡|s, a). BBO corrects this by modelling the true conditional distribution: PB(b|s, a,!) that generates the data.
The graphical model for BBO is shown in Fig. 1. To model PB(b|s, a,!) we assume a parametric conditional distribution: P (b|s, a, ) with model parameters
2 and a conditional mean: EP (b|s,a, )[b] = B̂ (s, a). It is also possible to specify a nonparametric model: P (b|s, a). The conditional mean of the distribution B̂ defines a function space of approximators that represents a space of Bellman operators, each indexed by 2 . The choice of P (b|s, a, ) 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 are not concerned with modelling the transition distribution in our model-free paradigm, we assume states are sampled either from an ergodic Markov chain, or i.i.d. from a buffer. Off-policy samples can be corrected using importance sampling.
Assumption 1 (State Generating Distribution). Each state si is drawn either i) i.i.d. from a distribution ⇢(s) with support over S or ii) from an ergodic Markov chain with stationary distribution ⇢(s) defined over 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 2 in accordance with how well we believe they represent B[Q̂!]. Given the prior and a dataset DN! := {bi, si, ai}i=1:N of samples from the true distribution PB , we infer the posterior P ( |DN! ) using Bayes’ rule which has the density (see Appendix D.1 for a derivation using both state generating distributions of Assumption 1):
p( |DN! ) = QN i=1 p(bi|si, ai, )p( )R
QN i=1 p(bi|si, ai, )dP ( ) . (4)
To be able to make predictions, we infer the posterior predictive: p(b|DN! , s, a) :=R p(b|s, a, )dP ( |D
N ! ). Unlike existing approaches, our posterior density is a function of !,
which correctly accounts for the dependence on Q̂! in our data and the generating distribution PB(b|s, a,!). We highlight that it is possible to define a likelihood and prior that are functions of ! to encode any prior knowledge of how the underlying Bellman operator varies with !, 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 approximator. As every Bellman operator characterises an MDP, the posterior predictive mean represents a 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?!,N (s, a) :=EP (b|DN! ,s,a)[b] = EP ( |DN! ) h B̂ (s, a) i . (5)
For this reason, we refer to the predictive mean B?!,N as the Bayesian Bellman operator and our Qfunction approximator should satisfy a Bellman equation using B?!,N . Our objective is therefore to find !? such that Q̂!? = B?!?,N . A simple approach to learn !? is to minimise the mean squared Bayesian Bellman error (MSBBE) between the posterior predictive and function approximator:
MSBBEN (!) := Q̂! B?!,N
2 ⇢,⇡ (6)
Here the distribution on the `2-norm is ⇢(s)⇡(a|s) where recall ⇢(s) is defined in Assumption 1. 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 3.1 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:
r!MSBBEN (!)
= E⇢,⇡ h⇣ Q̂! EP ( |DN! ) h B̂ i⌘⇣ r!Q̂! EP ( |DN! ) h B̂ r! log p( |DN! ) i⌘i . (7)
If we can sample from the posterior then unbiased estimates of r!MSBBEN (!) can be obtained, hence minimising the MSBBE via a stochastic gradient descent algorithm is convergent if the standard Robbins-Munro conditions are satisfied [62]. When existing approaches are used, the posterior has
no dependence on ! and the gradientr! log p( |DN! ) is not accounted for, leading to gradient terms 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 (s0|s, a) are required to obtain unbiased gradient estimates [7]. In BBO, this issue is avoided by drawing two independent approximate Bellman operators B 1 and B 2 from the posterior 1, 2 ⇠ P (·|DN! ) instead.

heading: 3.1 Consistency of the Posterior
text: To address Question 2, we develop a set of theoretical results to understand the posterior’s relationship to the RL problem. We introduce some mild regularity assumptions on our choice of model:
Assumption 2 (Regularity of Model). i) Q̂! is bounded and ( , d ) and (⌦, d⌦) are compact metric spaces; ii) B̂ is Lipschitz in , P (b|s, a, ) has finite variance and a density p(b|s, a, ) which is Lipschitz in and bounded; and iii) p( ) / exp ( R( )) where R( ) is bounded and Lipschitz. Our main result is a Bernstein-von-Mises-type theorem [49] applied to reinforcement learning. We prove that the posterior asymptotically converges to a 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: ?! := argmin
2 KL(PB(b, s, a|!) k P (b, s, a| )) = argmin 2 EPB(b,s,a|!) [ log p(b, s, a| )] , (8)
where the expectation is taken with respect to distribution that generates the data: PB(b, s, a|!) that satisfies dPB(b, s, a|!) = dPB(b|s, a,!)d⇡(a|s)d⇢(s). We make a simplifying assumption that there is a 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 C.3. Assumption 3 (Single Minimiser). The set of maximum likelihood parameters ?! defined in Eq. (8) exists and is a singleton. Theorem 1. Under Assumptions 1-3, in the limit N !1 the posterior concentrates weakly on ?!: i) P ( |DN! ) =) ( = ?!) a.s.; ii) B?!,N a.s. ! B̂ ?! ; and iii) MSBBEN (!) a.s. ! kQ̂! B̂ ?!k 2 ⇢,⇡ .
If our model can sufficiently represent the true conditional distribution then KL(PB(b, s, a|!) k P (b, s, a| ?!)) = 0 =) PB(b|s, a,!) = P (b|s, a, ?!). Theorem 1 proves that the posterior concentrates on the frequentist solution ?! and hence the Bayesian Bellman operator converges to the true Bellman operator: B̂ ?! (s, a) = EP (b|s,a, ?!)[b] = EPB(b|s,a,!)[b] = B[Q̂!](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 ?! converges to the closest representation of the true Bellman operator according to the parametrisation that maximises the likelihood EPB(b,s,a|!) [log p(b, s, a| )]. This is analogous to frequentist convergent TD learning where the function approximator converges to a parametrisation that minimises the projection of the Bellman operator into the model class [70, 71, 12]. We now make this relationship precise by considering a Gaussian model.

heading: 3.2 Gaussian BBO
text: To showcase the power of Theorem 1 and to provide a direct comparison to existing frequentist approaches, we consider the nonlinear Gaussian model P (b|s, a, ) = N (B̂ (s, a), 2) that is commonly used for Bayesian regression [55, 33]. The mean is a nonlinear function approximator that best represents the Bellman operator B ⇡ B[Q̂!] and the model variance 2 > 0 represents the aleatoric uncertainty in our samples. Ignoring the log-normalisation constant cnorm, the log-posterior is an empirical mean squared error between the empirical Bellman samples and the model mean B̂ (si, ai) with additional regularisation due to the prior (see Appendix D.2 for a derivation):
log p( |DN! ) = cnorm + NX
i=1
(bi B̂ (si, ai))2 2 2 +R( ), ?! 2 argmin 2 kB̂ B[Q̂!]k2⇢,⇡. (9)
Theorem 1 proves that in the limit N ! 1, the effect of the prior diminishes and the Bayesian Bellman operator converges to the parametrisation: B?!,N a.s. ! B̂ ?! . As ? ! is the set of parameters that minimise the mean squared error between the true Bellman operator and the approximator, B̂ ?! is a projection of the true Bellman operator onto the space of functions represented by B̂ :
B̂ ?! = PB̂ B[Q̂!] := {B̂ 0 : 0 2 argmin 2 kB̂ B[Q̂!]k2⇢,⇡}. (10)
Finally, Theorem 1 proves that the MSBBE converges to the mean squared projected Bellman error MSBBEN (!) a.s. ! MSPBE(!) := kQ̂! PB̂ B[Q̂!]k 2 ⇢,⇡. By the definition of the projection
operator in Eq. (10), a solution Q̂! = PB̂ B[Q̂!] 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 a case study in Appendix E, allowing us to derive a regularised Bayesian TDC/GTD2 algorithm [71, 70].

heading: 4 Approximate BBO
text: We have demonstrated in Eq. (7) that if it 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 are often too simple to accurately represent the Bellman operator for domains of practical interest in RL. We now extend our analysis to include approximate inference approaches.

heading: 4.1 Approximate Inference
text: To allow for more expressive nonlinear function approximators, for which the posterior normalisation is intractable, we introduce a tractable posterior approximation: q( |DN! ) ⇡ P ( |DN! ). In this paper, we use randomised priors (RP) [57] for approximate inference. Randomised priors (PR) inject noise into the maximum a posteriori (MAP) estimate via a noise variable ✏ 2 E with distribution PE(✏) where the density pE(✏) has the same form as the prior. We provide a full exposition of RP for BBO in Appendix F, including derivations of our objectives. RP in practice uses ensembling: L prior randomisations EL := {✏l}l=1:L are first drawn from PE . To use RP for BBO, we write the Qfunction approximator as an ensemble of L parameters ⌦L := {!l}l=1:L where Q̂! = 1L PL l=1 Q̂!l and require an assumption about the prior and the function spaces used for approximators:
Assumption 4 (RP Function Spaces). i) Q̂!l and B̂!l share a function space, that is Q̂!0l = B̂!0l for any !0l 2 ⌦, where = ⌦ ⇢ Rn is compact, convex with a smooth boundary. ii) E ✓ Rn and R( ✏) is defined for any 2 , ✏ 2 E . For each l 2 {1 : L}, a set of solutions to the prior-randomised MAP objective are found:
?l (!l) 2 argmin 2 L( ;DN!l , ✏l) := argmin 2
1
N
R( ✏l)
NX
i=1
log p(bi|si, ai, ) ! . (11)
The RP solution ?l (!l) has dependence on !l that mirrors the BBO posterior’s dependence on !. To construct the RP approximate posterior q( |DN! ), we average the set of perturbed MAP estimates over all ensembles: q( |DN! ) := 1L PL l=1 ( 2 ?l (!l)). To sample from the RP posterior
⇠ q(·|DN! ), we sample an ensemble uniformly l ⇠ Unif({1 : L}) and set = ?l (!l). 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 1:
Corollary 1.1. Under Assumptions 1-4, results i)-iii) of Theorem 1 hold with P ( |DN! ) replaced by the RP approximate posterior q( |DN! ) both with or without ensembling. In answer to Question 3), Corollary 1.1 shows that the difference between using the RP approximate 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 empirical performance in RL [57, 58] for the Gaussian model that we study in this paper.
The RP approximate posterior q( |DN! ) depends on the ensemble of Q-function approximators Q̂!l and like in Section 3 we must learn an ensemble of optimal parametrisations !?l . We substitute
for q( |DN! ) in place of the true posterior in Eqs. (5) and (6) to derive an ensembled RP MSBBE: MSBBERP(!l) := kQ̂!l B̂ ?l (!l)k 2 ⇢,⇡. When a fixed point Q̂!l = B̂ ?l (!l) exists, minimising MSBBERP(!l) is equivalent to finding !?l such that ? l (! ? l ) = ! ? l . To learn ! ? l we can instead minimise the simpler parameter objective !?l 2 argmin!l2⌦ U(!l; ? l ):
U(!l; ?l ) := k!l ?l (!l)k22 such that ?l (!l) 2 argmin 2 L( ;DN!l , ✏l), (12)
which has the advantage that deterministic gradient updates can be obtained. U(!l; ?l ) 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 MSBBERP(!l) for sufficiently smooth B . Solving the bi-level optimisation problem in Eq. (12) is NP-hard [8]. To tackle this problem, we introduce an ensemble of parameters L := { l}1:L to track ?l (!l) and propose a two-timescale gradient update for each l 2 {1 : L} on the objectives in Eq. (12) with per-step complexity of O(n):
l P⌦ ( l ↵kr l (R( l ✏l) log p(bi|si, ai, l))) , (fast) (13) !l P⌦(!l k(!l l)), (slow) (14)
where ↵k and k are asymptotically faster and slower stepsizes respectively and P⌦(·) := argmin!2⌦k· !k22 is a projection operator that projects its argument back into ⌦ if necessary. From a Bayesian perspective, we are concerned with characterising the uncertainty after a finite number of samples N <1 and hence (bi, si, ai) should be drawn uniformly from the dataset DN!l to form estimates of the summation in Eq. (11), which becomes intractable with large N . When compared to existing RL algorithms, sampling from DN!l 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 (bi, si, ai) ⇠ PB in the limit N !1. We discuss this frequentist interpretation further in Appendix C.5.
To answer Question 4), we prove convergence of updates (13) and (14) using a 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 ⌦ using standard martingale arguments, viewing the parameter !l as quasi-static as it behaves like a constant. Since the perturbations are relatively small, the separation of timescales then ensures that l tracks ?l (!l) whenever !l is updated in the slower timescale update (14), viewing the parameter l as quasiequilibrated [14]. We introduce the standard two-timescale regularity assumptions and derive the limiting ODEs of updates (13) and (14) in Appendix C.3: Assumption 5 (Two-timescale Regularity). i) r lR( l ✏l) and r l log p(bi|si, ai, l) are Lipschitz in l and (bi, si, ai) ⇠ Unif(DN!l); ii)
~(!l) and !~l are local aysmptotically stable attractors of the limiting ODEs of updates (13) and (14) respectively and ~l (!l) is Lipschitz in !l; and iii) The stepsizes satisfy: limk!1 k↵k = 0, P1 k=1 ↵k = P1 k=1 k =1, P1 k=1 ↵2k + 2 k <1. Theorem 2. If Assumptions 1 to 5 hold, l and !l converge to ~l (! ~ l ) and ! ~ l almost surely.
As !l are updated on a slower timescale, they lag the parameters l. When deriving a Bayesian actor-critic algorithm in Section 4.2, we demonstrate that these parameters share a similar role to a lagged critic. There is no Bayesian explanation for these parameters under existing approaches: when applying approximate inference to P (Q⇡|s, a,DN ), the RP solution ?l has no dependence on !l. Hence, minimising U(!l; ?l ) and the approximate MSBBE has an exact solution by setting !?l = ? l . In this case, Q̂!?l = B̂ ?l meaning that existing approaches do not distinguish between the Q-function and Bellman operator approximators.
4.2 Bayesian Bellman Actor-Critic B̂ l(s, a)
L
⇡✓†(a|s)
⇡✓l(a|s) L
Critics Exploration Policies
Behavioural Policy
a ⇠ ⇡✓i(a|s)
r = r(s0, a, s)
i ⇠ Unif([1, ...L])
Environment
Target Critics
s0 ⇠ P (s0|s, a)
Q̂!l(a, s) L
Figure 2: Schematic of RP-BBAC.
BootDQN+Prior [57, 58] is a state-of-the-art Bayesian model-free algorithm with Thompson sampling [74] where, in principle, an optimal Q-function is drawn from a posterior over optimal Q-functions at the start of each episode. As BootDQN+Prior requires bootstrapping, it actually draws a sample from the Gaussian BBO posterior introduced in Section 3.2 using RP approximate inference with the empirical Bellman
function b!(s0, a, s) = r(s0, a, s)+ maxa0 Q̂!(s0, a0). This empirical Bellman function results from substituting an optimal policy ⇡(a|s) = (a 2 argmaxa0 Q̂!(s, a
0)) in Eq. (3). A variable l is drawn uniformly and the optimal exploration policy ⇡?l (a|s) = (a 2 argmaxa0 B l(s, a0)) 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 an exploratory action on future learning. Due its use of the argmax operator, BootDQN+Prior is not appropriate for continuous action or large discrete action domains as a 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 BootDQN+Prior to continuous domains. A schematic of RP-BBAC is shown in Fig. 2 which summarises Algorithm 1. Additional details are in Appendix G.
Comparison to existing actor-critics: Using a Gaussian model also allows a direct comparison to frequentist actor-critic algorithms [50]: as shown in Fig. 2, every ensemble l 2 {1...L} has its own exploratory actor ⇡✓l , critic B l and target critic Q̂!l . In BBAC, each critic is the solution to its unique ✏l-randomised empirical MSBBE objective from Eq. (12): Lcritic( l) := 1 2 PN i=1(bi B̂ l(si, ai))2 + R( l ✏l). The target critic parameters !l for each Bellman sample bi = ri + Q̂!l(s0i, a0i) are updated on a slower timescale to the critic parameters, which mimics the updating of target critic parameters after a regular interval in frequentist approaches [54, 39]. We introduce an ensemble of parametric exploration policies ⇡✓l(a|s) parametrised by a set of parameters ⇥L := {✓l}l=1:L. Each optimal exploration policy ⇡?l (a|s) is parametrised by the solution to its own optimisation problem: ✓?l 2 argmax✓l2⇥ E⇢(s)⇡✓l (a|s)[B l(s, a
0)]. Unlike frequentist approaches, an exploratory actor is selected at the start of each episode in accordance with our current uncertainty in the MDP characterised by the approximate RP posterior.
Algorithm 1 RP-BBAC Initialise ⇥L,⌦L, L, EL, ✓† and D ? Sample initial state s ⇠ P0 while not converged do
Sample policy ✓l ⇠ Unif(⇥L) for n 2 {1, ...Nenv} do
Sample action a ⇠ ⇡✓l(·|s) Observe next state s0 ⇠ P (·|s, a) Observe reward r = r(s0, a, s) D D [ {s, a, r, s0}
end for ⇥L,⌦L, L UPDATEPOSTERIOR ✓† UPDATEBEHAVIOURALPOLICY
end while Exploration is thus both deep and adaptive as actions from an exploration policy are directed towards minimising epistemic uncertainty in the MDP and the posterior variance reduces in accordance with Corollary 1.1 as more data is collected. BBAC’s explicit specification of lagged target critics is unique to BBO and, as discussed in Section 4.1, corrects the theoretical issues raised by applying bootstrapping to existing model-free Bayesian RL theory, which does not account for the posterior’s dependence on Q̂!. Finally, exploration policies may not perform well at test time, so we learn a behaviour policy ⇡✓†(a|s) parametrised by ✓† 2 ⇥ from the data collected by our exploration policies using the ensemble of critics: {B̂ l}l=1:L. 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 benefits of Thompson sampling with the faster convergence rates and algorithmic stability of regularised RL [77].

heading: 5 Related Work
text: Existing model-free Bayesian RL approaches assume either a parametric Gaussian [34, 57, 32, 52, 58, 75] or Gaussian process regression model [28, 29]. Value-based approaches use the empirical Bellman function b!(s0, a, s) = r(s0, a, s) + maxa0 Q̂!(s0, a0) whereas actor-critic approaches use the empirical Bellman function b!(s0, a0, s, a) = r(s0, a, s) + Q̂!(s0, a0). 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 ) ⇡ P (b|s, a,DN! ). These methods minimise an approximation of the MSBBE where the Bayesian Bellman operator is treated as a 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 Q̂!k+1 B?!k,N . In both cases, the updates may not be a contraction mapping for the same reasons as in non-Bayesian TD [76] and so it is not possible to prove general convergence.
The additional Bayesian regularisation introduced from the prior can lead to convergence, but only in specific and restrictive cases [4, 5, 31, 17].
Approximate inference presents an additional problem for existing approaches: many existing methods naïvely apply approximate inference to the Bellman error, treating B[Q⇡](s, a) and Q⇡(s, a) as independent variables [32, 52, 75, 34]. This leads to poor uncertainty estimates as the Bellman error cannot correctly propagate the uncertainty [56, 57]. Osband et al. [58] demonstrate that this can cause uncertainty estimates of Q⇡(s, a) at some (s, a) to be zero and propose BootDQN+Prior 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+Prior derived from BBO specifies the use of target critics. Despite being essential to performance, there is no Bayesian explanation for target critics under existing model-free Bayesian RL theory, which posits that sampling a critic from P (Q⇡|s, a,DN ) is sufficient.
6 Experiments
Convergent Nonlinear Policy Evaluation To confirm our convergence 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-
mous counterexample task of Tsitsiklis and Van Roy [76], in which the TD(0) algorithm is provably divergent. The results are presented in Fig. 3. As expected, TD(0) diverges, while BBO converges to the optimal solution faster than convergent frequentist nonlinear TDC and GTD2 [12]. We also consider three additional policy evaluation tasks commonly used to test convergence of nonlinear TD using neural network function approximators: 20-Link Pendulum [23], Puddle World [16], and Mountain Car [16]. Results are shown in Fig. 11 of Appendix H.3 from which we conclude that i) by ignoring the posterior’s dependence on !, existing model-free Bayesian approaches are less stable and perform poorly in comparison to the gradient based MSBBE minimisation approach in Eq. (7), ii) regularisation from a prior can improve performance of policy evaluation by aiding the optimisation landscape [26], and iii) better solutions in terms of mean squared error can be found using BBO instead of the local linearisation approach of nonlinear TDC/GTD2[12].
Exploration for Continuous Control In many benchmark tasks for continuous RL, such as the locomotion tasks from MuJoCo Gym suite [18], the environment reward is shaped to provide a smooth gradient towards a successful task completion and naïve Boltzmann dithering exploration strategies from regularised RL can provide a strong inductive bias.
In practical real-world scenarios, dense rewards are difficult to specify by hand, especially when the task is learned from raw observations like images. Therefore, we consider a set of continuous control tasks with sparse rewards as continuous analogues of the discrete experiments used to test BootDQN+Prior [57]: MountainCar-Continuous-v0 from Gym benchmark suite and a slightly modified version of the cartpole-swingup_sparse from DeepMind Control Suite [73]. 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 a directed manner for hundreds of steps until it reaches the rewarding region of the state space. We compare RP-BBAC with two variants of the state-of-the-art soft actor-critic: SAC, which is the exact algorithm presented in [40]; and SAC*, a tailored version which uses a single Q-function to avoid pessimistic underexploration [20] due to the use of the double-minimum-Q trick (see Appendix I for details). To understand the practical implications of our theoretical results, we also compare against BAC which is a variant of RP-BBAC where Q̂!?l = B̂ ?l . 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-functions used by existing model-free Bayesian approaches with bootstrapping.
The results are shown in Fig. 4. Due to the lack of smooth signal towards the task completion, SAC consistently fails to solve the tasks and converges to always executing the 0-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
MountainCar-Continuous-v0 Appendix I.1. The final plots are shown in Fig. 5 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 RL 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 in Appendix I.1 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 is 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.
V is it at io n Fr eq ue nc y
Our results in Fig. 4 demonstrate that the theoretical issues with existing approaches have negative empirical consequences, verifying that it is essential for Bayesian modelfree RL algorithms with bootstrapping to sample from the BBO posterior as BAC fails to solve both tasks where sampling from the correct posterior in RP-BBAC succeeds. In Appendix I.2, we also investigate RP-BBAC’s sensitivity to randomized prior hyperparameters. The range of working hyperparameters is wide and easy to tune.

heading: 7 Conclusion
text: 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+Prior to continuous domains. Our experiments in environments where rewards are not hand-crafted to aid exploration demonstrate that sampling from the BBO posterior characterises uncertainty correctly and algorithms derived from BBO can succeed where state-of-the-art 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 !, or extend our convergence analysis to the actor-critic algorithm.

heading: Acknowledgements
text: This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement number 637713). Matthew Fellows and Kristian Hartikainen are funded by the EPSRC. The experiments were made possible by a generous equipment grant from NVIDIA. We would like to thank Piotr Miłoś, whose proof for a similar problem inspired our proof of Lemma 3.

Review summaries:
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.

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. 

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.