Deep Exploration with PAC-Bayes

## Abstract

Abstract Reinforcement learning for continuous control under sparse rewards is an under-explored problem despite its significance in real life. Many complex skills build on intermediate ones as prerequisites. For instance, a humanoid locomotor has to learn how to stand before it can learn to walk. To cope with reward sparsity, a reinforcement learning agent has to perform deep exploration. However, existing deep exploration methods are designed for small discrete action spaces, and their successful generalization to state-of-the-art continuous control remains unproven.
We address the deep exploration problem for the first time from a PAC-Bayesian perspective in the context of actor-critic learning.
To do this, we quantify the error of the Bellman operator through a PAC-Bayes bound, where a bootstrapped ensemble of critic networks represents the posterior distribution, and their targets serve as a data-informed function-space prior.
We derive an objective function from this bound and use it to train the critic ensemble. Each critic trains an individual actor network, implemented as a shared trunk and critic-specific heads.
The agent performs deep exploration by acting deterministically on a randomly chosen actor head. Our proposed algorithm, named PAC-Bayesian Actor-Critic (PBAC) , is the only algorithm to successfully discover sparse rewards on a diverse set of continuous control tasks with varying difficulty.

## 1 Introduction

Complex control tasks commonly presuppose the completion of a sequence of sub-tasks. For example, winning a chess game involves following a theoretically correct opening, a middle game with a chain of creative tactical combinations, and an error-free endgame. Similarly, in Montezuma’s Revenge, an agent must visit multiple rooms and collect keys in the correct order. A genuinely intelligent agent is expected to identify and solve these sub-tasks based solely on the final reward. Deep reinforcement learning (RL) has been highly successful in handling such sparse reward scenarios. AlphaZero (Silver et al., ) and Random Network Distillation (RND) (Burda et al., ) reach super-human level performance scores in chess and Montezuma’s Revenge, respectively, despite receiving zero reward for long interaction sequences.

Continuous control tasks share a similar modular structure. There is strong evidence that biological systems execute complex movements through robust and stable building blocks, known as motion primitives (Flash & Hochner, ). Application of the same idea to robotics, called dynamic movement primitives (Schaal, ), demonstrated remarkable success when unit movement patterns are fit to observations separately and an agent is trained to apply them in a sequence.
This recipe works well when the target environment is well-understood and eligible for a rigorous engineering effort.
However, performing loosely defined tasks in open-world scenarios requires tabula rasa approaches that both invent these primitives from authentic environment interactions and use them in an optimal order for task completion within feasible sample complexity limits. Reinforcement learning has not yet delivered success stories in continuous control setups with sparse rewards.

The common ground of reinforcement learning approaches developed for sparse reward setups is to quantify the uncertainty on the Bellman target and use it for exploration. The exploration scheme should aim for multi-step information gains by propagating uncertainty across Bellman backups, a notion known as deep exploration (Osband et al., ).
There exist several model-free approaches that treat deep exploration as a Bayesian inference problem on the Bellman target (Osband et al., ; ; Touati et al., ; Fellows et al., ).
Additionally, model-based approaches explore learning a distribution over the state transition kernel and propagating its uncertainty through the value function to estimate the Bellman target uncertainty (O’Donoghue et al., ; Luis et al., ). Finally, there are pseudo-count-based approaches in the middle ground of model-based and model-free approaches that aim to estimate the visitation count of state-action pairs by distilling a randomly initialized predictor into a parametric auxiliary network (Nikulin et al., ; Yang et al., ; Burda et al., ). Among all these approaches, only a few recent model-based approaches (Luis et al., ) show success in continuous control tasks at the expense of a prohibitive computational overhead for model learning and a strong dependency on learnable environment dynamics, which would essentially make model predictive control sufficient for many real-world applications.

##### Contribution.

We formulate the deep exploration problem for the first time from a Probably Approximately Correct (PAC) Bayesian (McAllester, ; Alquier et al., ) perspective and develop an actor-critic algorithm that reaches unprecedented performance in continuous control with sparse rewards.
To do this, we quantify the Bellman operator error using a generic PAC-Bayes bound formulation (Germain et al., ) for the first time in a policy evaluation context.
We treat a bootstrapped ensemble of critic networks as an empirical posterior distribution and build a data-informed function-space prior from their corresponding target networks.
To train this ensemble, we derive a simple and intuitive objective function.
As the actor, we use a deterministic network with a shared trunk and multiple heads, each assigned to a separate critic.
We apply posterior sampling during training time for exploration and Bayesian model averaging during evaluation time.
Finally, we conduct experiments on a diverse set of continuous control tasks, both established and novel, some of which have reward structures significantly more challenging than the prior art.
Our PAC-Bayesian Actor-Critic (PBAC) algorithm is the only model capable of solving these tasks, whereas both state-of-the-art and well-established methods fail in several. For example, Figure 1 visualizes PBAC’s deep exploration followed by effective exploitation, in contrast to two baselines.

Figure: Figure 1: *Deep exploration.* State exploration patterns of the state and angle dimension in the cartpole environment are visualized as training progresses (every 500th state throughout the training is recorded and visualized in five groups, left to right). After an initial phase of broad exploration, PBAC quickly discovers the reward region (top middle in each of the scatter plots) and learns to exploit it while continuing to explore to a small amount. DRND (Yang et al., ) and BootDQN-P (Osband et al., ) on the other hand struggle with this task. DRND gets stuck early on, while BootDQN-P manages to find the reward region but continues to explore excessively, preventing full exploitation. See the experimental section (Section 4) for more details.
Refer to caption: x1.png

## 2 Background and prior art

### 2.1 Reinforcement learning

Consider a measurable space $(\mathcal{S},\sigma(\mathcal{S}))$ of a set of states $\mathcal{S}$ an agent may be in and its corresponding $\sigma$-algebra $\sigma(\mathcal{S})$ comprising all measurable subsets of the state space $\mathcal{S}$ and an action space $\mathcal{A}$ from which an agent can choose an action to interact with its environment. We define a Markov Decision Process (MDP) (Puterman, ) as a tuple $M=\langle\mathcal{S},\mathcal{A},r,P,P_{0},\gamma\rangle$, where $r:\mathcal{S}\times\mathcal{A}\rightarrow[0,R]$ is a bounded reward function, $P:\mathcal{S}\times\mathcal{A}\times\sigma(\mathcal{S})\rightarrow[0,1]$ is a state transition kernel conditioned on a state-action pair, meaning that $P(\cdot|s,a)$ is the probability distribution of a next state $s^{\prime}\in\mathcal{S}$ when starting from a current state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$. $P_{0}:\sigma(\mathcal{S})\rightarrow[0,1]$ is an initial state distribution, and $\gamma\in(0,1)$ is a discount factor.
We denote a policy as a map ${\pi:\mathcal{S}\rightarrow{\mathcal{A}}}$.
Reinforcement learning aims to learn a policy that maximizes the expected sum of discounted rewards,
$\pi^{\prime}:=\operatorname*{arg\,max}_{\pi\in\Pi}\mathds{E}_{\tau_{\pi}}\left
[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t})\right]$ where the expectation is taken with respect to the trajectory $\tau_{\pi}:=(s_{0},a_{0},s_{1},a_{1},s_{2},a_{2},\ldots)$ of states and actions that occur when a policy $\pi$ chosen from a feasible set $\Pi$ is employed. The exact Bellman operator for a policy $\pi$ is defined as

$$ $T_{\pi}Q(s,a)=r(s,a)+\gamma\mathds{E}_{s^{\prime}\sim P(\cdot|s,a)}\left[Q(s^{ \prime},\pi(s^{\prime}))\right],$ $$

for some $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathds{R}$. The unique fixed point of this operator is the true action-value function $Q_{\pi}$ that maps a state-action pair $(s,a)$ to the discounted reward a policy $\pi$ collects when executed starting from $(s,a)$, that is $T_{\pi}Q(s,a)=Q(s,a)$ if and only if $Q(s,a)=Q_{\pi}(s,a),\forall(s,a)$. Any other $Q$ incurs an error $T_{\pi}Q(s,a)-Q(s,a)$ referred to as the Bellman error. Define the squared $P_{\pi}$-weighted $L_{2}$-norm as $\lVert f\rVert_{P_{\pi}}^{2}=\int_{s\in\mathcal{S}}\lvert f(s)\rvert^{2}dP_{
\pi}(s)$ for some $f:\mathcal{S}\rightarrow\mathds{R}$. We aim to approximate the true action-value function $Q_{\pi}$ by one-step Temporal Difference (TD) learning that minimizes

$$ $\displaystyle L(Q):=||T_{\pi}Q-Q||_{P_{\pi}}^{2}$ (1) $$

with respect to $Q$ given a data set $\mathcal{D}$. In customary setups, the transition kernel is not known, hence only a stochastic version of this loss can be calculated via Monte Carlo samples

$$ $\displaystyle\widetilde{L}(Q):=\mathds{E}_{s\sim P_{\pi}}\left[\mathds{E}_{s^{ \prime}\sim P(\cdot|s,\pi(s))}\left[(\widetilde{T}_{\pi}Q(s,\pi(s),s^{\prime}) -Q(s,a))^{2}\right]\right],$ $$

with the *sample Bellman operator*, defined as

$$ $\widetilde{T}_{\pi}Q(s,a,s^{\prime})=r(s,a)+\gamma Q(s^{\prime},\pi(s^{\prime} )).$ $$

A deep reinforcement learning algorithm fits a function approximator $Q$ to a set of observed tuples ${(s,a,s^{\prime})}$ stored in a replay buffer $\mathcal{D}$ by minimizing an empirical estimate of the stochastic loss:

$$ $\displaystyle\widehat{L}_{\mathcal{D}}(Q)$ $\displaystyle:=\frac{1}{|\mathcal{D}|}\sum_{(s,a,s^{\prime})\in\mathcal{D}} \left(\widetilde{T}_{\pi}Q(s,a,s^{\prime})-Q(s,a)\right)^{2}.$ $$

If the function family contains the true action-value function, the optimization problem above can be solved in full precision, and the environment is explored with a behavior policy that has full coverage on the state-action space. Temporal difference learning is then guaranteed to converge to the true solution asymptotically (Bertsekas & Tsitsiklis, ). Because these conditions are rarely satisfied in practice, reinforcement learning algorithms commonly suffer from sample inefficiency which amounts to prohibitive costs in real-world applications.

### 2.2 Deep exploration

The classical optimal control paradigm prescribes a rigorous design of cost functions, i.e., negative rewards, that give a dense signal about model performance at each stage of model fitting (Stengel, ; Kirk, ). This approach is akin to detailed loss designs in the common practice of deep learning. However, next-generation AI problems demand agents with high cognitive capabilities that can autonomously learn smart strategies to reach distant high rewards without being trapped by intermediate small rewards or prematurely giving up searching. These approaches are commonly known as *deep exploration* (Osband et al., ). Their common ground is to estimate how often a state-action pair has been visited until a certain training step and direct the exploration towards unvisited ones. Deep exploration approaches can be classified into four categories based on how accurate knowledge of environment dynamics they assume to make this estimation:

*(i) Model-based approaches*
learn to infer the state transition kernel by a function approximator $P_{\phi}(\cdot|s,a)\approx P(\cdot|s,a)$ and use its uncertainty to generate intrinsic rewards (Chentanez et al., ) to perform curiosity-driven exploration, which has remarkable roots to biological intelligence (Schmidhuber, ; Modirshanechi et al., ). VIME (Houthooft et al., ) incentivizes exploration of states that would bring more information gain on the estimated transition kernel, while BYOL-Explore (Guo et al., ) and BYOL-Hindsight (Jarrett et al., ) choose states with higher prediction error. Approaches such as UBE (O’Donoghue et al., ), Exact UBE (Luis et al., ), and QU-SAC (Luis et al., ) choose the target quantity as the sample Bellman operator $\widetilde{T}_{\pi}Q$. MOBILE (Sun et al., ) and MOPO (Yu et al., ) are the respective offline RL counterparts of these strategies.

*(ii) Pseudo-count approaches*
learn to predict only the relative visitation frequencies of state-action pairs without needing to predict the state transitions. These frequencies are then used to generate intrinsic rewards to direct the exploration towards less frequent state-action pairs. The commonplace approach, called Random Network Distillation (RND) (Burda et al., ), distills a fixed network with randomly initialized weights into another network with learned parameters. It uses the success of the distillation as a pseudo-count to generate intrinsic rewards. State-of-the-art variants include SAC-RND (Nikulin et al., ) and SAC-DRND (Yang et al., ).

*(iii) Randomized value iteration approaches*
learn to estimate the uncertainty around the approximate $Q$ function by modeling it as a random variable and performing posterior inference based on the observed Bellman errors. Proposed inference methods include Bayesian linear regression (Osband et al., ), mean-field (Lipton et al., ) or structured (Touati et al., ) variational inference on Bayesian neural networks, Bayesian deep bootstrap ensembles with flat priors (Osband et al., ) and informative priors (Osband et al., ). Fellows et al. () find out that these approaches actually infer a posterior on the Bellman target $T_{\pi}Q$ instead of the intended $Q$ and propose to overcome the consequences of this mismatch by training a separate $Q$ network on the posterior predictive mean of $T_{\pi}Q$. A more advanced version of this approach, named *Bayesian Exploration Networks (BEN)* (Fellows et al., ), fits a Bayesian heteroscedastic neural net on the Bellman target using structured variational inference.

*(iv) Policy randomization approaches*
propose different perturbations on the learned models to randomize the employed policy without aiming to quantify the uncertainty of a quantity. Proposed solutions include perturbing the $Q$-network weights for discrete action spaces (Fortunato et al., ), actor-network weights (Plappert et al., ) for continuous control, and transforming the policy distribution by normalizing flows (Mazoure et al., ).

In this work, we follow the randomized value iteration approach due to the balance it grants between computational feasibility and theoretical soundness. Notably, Bayesian model averaging gives the optimal decision rule for an approximate $Q$ function with partial observation on an MDP with reliable uncertainty estimates (Cox & Hinkley, ). We approach the deep exploration problem for the first time from a PAC-Bayesian perspective. The use of PAC-Bayes in reinforcement learning is limited to theoretical analysis (Fard et al., ) and preliminary developments aiming to improve training robustness (Tasdighi et al., ).

### 2.3 PAC-Bayesian analysis and learning

Given inputs $\mathcal{Z}$, outputs $\mathcal{Y}$, a set of hypotheses $\mathcal{H}=\{h:\mathcal{Z}\rightarrow\mathcal{Y}\}$ that map inputs to outputs, and a loss function $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow[0,B]$, we define the empirical risk $\widehat{L}$ for a set of observations $\mathcal{O}=\{(z_{i},y_{i}):(z_{i},y_{i})\sim P_{D},i\in[n]\}$(^1^11Here and below $[x]$ denotes the set $\{1,\ldots,x\}$ for integer $x$.) containing $n$ samples obtained from a distribution $P_{D}$,
and the corresponding true risk $L$ as

$$ $\displaystyle\widehat{L}_{\mathcal{O}}(h)=\frac{1}{n}\sum_{i=1}^{n}\ell(h(z_{i }),y_{i}),\qquad\qquad L(h)=\mathds{E}_{(z,y)\sim P_{D}}\left[\ell(h(z),y) \right].$ $$

PAC-Bayesian analysis (Shawe-Taylor & Williamson, ; Alquier et al., ) characterizes an upper bound $C$ of the form $d(\mathds{E}_{h\sim\rho}\left[L(h)\right],\mathds{E}_{h\sim\rho}[\widehat{L}_{
\mathcal{O}}(h)])\leq C(\rho,\rho_{0},\delta)$ that holds with probability at least $1-\delta$ for any error tolerance $\delta\in(0,1]$ and any prior probability measure $\rho_{0}$ and posterior probability measure $\rho$ chosen from the set of all measures $\mathcal{P}$ feasible on the hypothesis space $\mathcal{H}$ for a given convex distance metric $d(\cdot,\cdot)$. The choice of the posterior measure $\rho$ can depend on the data $\mathcal{O}$ while the prior measure $\rho_{0}$ cannot, hence their names.
However, unlike in Bayesian inference, the posterior and the prior do not need to relate to each other via a likelihood function. The prior serves as a reference with respect to which a generalization statement is made. Various well-known PAC-Bayes bounds (such as McAllester (); Seeger (); Catoni ()) can be shown as instances of the generic form below, the proof of which we present in Appendix A for completeness.

###### Theorem 1 ( Germain et al. ( 2009 ) ) .

For any convex function $d:[0,B]\times[0,B]\rightarrow\mathds{R}$, distributions $\rho,\rho_{0}$ measurable on the hypothesis space $\mathcal{H}$, and error tolerance $\delta\in(0,1]$, simultaneously, the following inequality holds with probability at least $1-\delta$:

$$ $\displaystyle d\left(\mathds{E}_{h\sim\rho}\left[\widehat{L}_{\mathcal{O}}(h) \right],\mathds{E}_{h\sim\rho}\left[L(h)\right]\right)\leq\frac{1}{n}\left( \mathrm{KL}\left(\rho\;\|\;\rho_{0}\right)+\ln\left(\frac{1}{\delta}\mathds{E} _{\mathcal{O}\sim P_{D}}{\mathds{E}_{h\sim\rho_{0}}{e^{nd(\widehat{L}_{ \mathcal{O}}(h),L(h))}}}\right)\right).$ $$

In the bound, $\mathrm{KL}\left(\rho\;\|\;\rho_{0}\right)=\mathds{E}_{h\sim\rho}\left[\log
\rho(h)-\log\rho_{0}(h)\right]$ stands for the Kullback-Leibler divergence between two probability measures.

Since a PAC-Bayes bound holds for any posterior, a parametric family of posteriors can be chosen and its parameters can be fit to data by minimizing the right-hand side of the bound. This approach, called PAC-Bayesian Learning, demonstrated remarkable success in image classification (Dziugaite & Roy, ; Wu et al., ) and regression (Reeb et al., ). There exist only preliminary results such as Tasdighi et al. () that use this approach in deep reinforcement learning. The tightness of the bound is determined by the choice of $d$, as well as additional assumptions and algebraic manipulations on the second term on the right-hand side of the inequality. Remarkably, this term does not depend on $\rho$, and hence does not play any role in a PAC-Bayesian learning algorithm. Our solution instrumentalizes this simple but often overlooked observation.

###### Theorem 1 ( Germain et al. ( 2009 ) ) .

## 3 Deep exploration with a PAC-Bayesian actor-critic

### 3.1 Theory

We aim to build an actor-critic algorithm able to perform deep exploration in continuous control setups with sparse rewards. We consider a model-free and off-policy approximate temporal difference training setup. The only existing prior work at the time of writing that addresses this setup with a PAC-Bayesian analysis is by Fard et al. ().
They use PAC-Bayes to directly bound the value of a policy from a single chain of observations. The Markovian dependencies of these observations necessitate building on a Bernstein-like concentration inequality that works only for extremely long episodes, prohibiting its applicability to PAC-Bayesian learning (Tasdighi et al., ). We overcome this limitation by instead developing a PAC-Bayes bound on the Bellman operator error.
See Appendix A for proofs on all results presented in this section.

We assume the existence of a replay buffer $\mathcal{D}$ containing samples obtained from real environment interactions.
Following Fard et al. (), we assume for convenience that the policy $\pi$ being evaluated always induces a stationary state transition kernel, that is $P_{\pi}(s^{\prime})=\int P(s^{\prime}|s,\pi(s))P_{\pi}(s)ds$ for every $s\in\mathcal{S}$ in all training-time environment interactions, where $P_{\pi}$ denotes the state visitation distribution for policy $\pi$.
This is essentially a hidden assumption made by the commonplace off-policy deep reinforcement learning algorithms that take uniformly random batches from their replay buffers. The difference between the sample Bellman operator and the Bellman operator, $\widetilde{T}_{\pi}Q(s,a,s^{\prime})-T_{\pi}Q(s,\pi(s))$, is known to tend to an accumulating positive value when $Q$ is concurrently used as a training objective for policy improvement, leading to the phenomenon known as the overestimation bias (Thrun & Schwartz, ). The problem is tackled by approaches such as double $Q$-learning (Van Hasselt, ) and min-clipping (Fujimoto et al., ).
We define with

$$ $X(s,a)\overset{d}{=}Q(s,a)+\widetilde{T}_{\pi}Q(s,a,s^{\prime})-T_{\pi}Q(s,a), \qquad\forall(s,a)\sim\mathcal{S}\times\mathcal{A}$ $$

a new random variable, where $\overset{d}{=}$ denotes equality in distribution. This is a hypothetical variable that predicts from $(s,a)$ the value of the observed Bellman target caused by the randomness of $s^{\prime}$. It is related to the action-value function approximator as follows

$$ $\displaystyle Q(s,a)$ $\displaystyle=Q(s,a)+\mathds{E}_{s^{\prime}\sim P(\cdot|s,a)}\left[\widetilde{ T}_{\pi}Q(s,a,s^{\prime})\right]-T_{\pi}Q(s,a)$ $\displaystyle=\mathds{E}_{s^{\prime}\sim P(\cdot|s,a)}\left[Q(s,a)+\widetilde{ T}_{\pi}Q(s,a,s^{\prime})-T_{\pi}Q(s,a)\right]=\mathds{E}\left[X(s,a)\right].$ $$

Let $\rho$ denote the distribution of $X$, then the one-step TD learning loss can be expressed as

$$ $\displaystyle L(Q)$ $\displaystyle=||T_{\pi}Q-Q||_{P_{\pi}}^{2}=||T_{\pi}Q-\mathds{E}\left[X\right] ||_{P_{\pi}}^{2}$ $\displaystyle=\mathds{E}_{s\sim P_{\pi}}\left[\Big{(}\mathds{E}_{s^{\prime} \sim P(\cdot|s,\pi(s))}\left[\big{.}r(s,\pi(s))+\gamma\mathds{E}\left[X(s^{ \prime},\pi(s^{\prime}))\right]\right]-\mathds{E}\left[X(s,\pi(s))\right]\Big{ )}^{2}\right]$ $$

with the corresponding stochastic variant(^2^22A single realization of $X$ shares the same domain and range as $Q$. Hence it can be passed through the sample Bellman operator $\widetilde{T}$.)

$$ $\displaystyle\widetilde{L}(\rho)$ $\displaystyle=\mathds{E}_{s\sim P_{\pi}}\mathds{E}_{s^{\prime}\sim P(\cdot|s, \pi(s))}\mathds{E}_{X\sim\rho}\left[\left(\widetilde{T}_{\pi}X\left(s,\pi(s),s ^{\prime}\right)-X(s,\pi(s))\right)^{2}\right].$ $$

This optimization problem no longer fits a deterministic map $Q$ but instead infers a distribution $\rho$ that best describes the action-value function perturbed by the Bellman operator error. The loss can be interpreted as the true risk of a Gibbs predictor $X\sim\rho$. The corresponding empirical risk is

$$ $\widehat{L}_{\mathcal{D}}(\rho)=\frac{1}{|\mathcal{D}|}\sum_{(s,a,s^{\prime}) \in\mathcal{D}}\mathds{E}_{X\sim\rho}\left[\left(\widetilde{T}_{\pi}X(s,a,s^{ \prime})-X(s,\pi(s))\right)^{2}\right].$ $$

We formulate our learning problem as choosing $\rho$ from a feasible set $\mathcal{P}$ that gives the tightest PAC-Bayes bound on $\widetilde{L}(\rho)$ with respect to data set $\mathcal{D}$ and a prior $\rho_{0}\in\mathcal{P}$ on the distribution of $X$. This bound should give generalization guarantees about how well $X$ can predict a noisy Bellman operator output. However, in a reinforcement learning setup, our final quantity of interest is the value estimation error $\lVert Q_{\pi}-Q\rVert_{P_{\pi}}=\lVert Q_{\pi}-\mathds{E}\left[X\right]\rVert
_{P_{\pi}}$, upper bounded via Jensen’s inequality by $\mathds{E}_{X\sim\rho}\lVert Q_{\pi}-X\rVert_{P_{\pi}}$. Prior work (Fellows et al., ) addresses the mismatch between the target and inferred quantities of interest in probabilistic reinforcement learning and its consequences. We propose a different solution by establishing the link using the contraction property of Bellman operators and the following result.

###### Lemma 1 .

For any $\rho$ defined on $X$, the following identity holds

$$ $\displaystyle\widetilde{L}(\rho)=\mathds{E}_{X\sim\rho}||T_{\pi}X-X||_{P_{\pi} }^{2}+\gamma^{2}\mathds{E}_{X\sim\rho}[\mathds{V}\mathrm{ar}_{s\sim P_{\pi}} \left[X(s,\pi(s))\right]].$ $$

Applying the contraction property of Bellman operators to $||T_{\pi}X-X||_{P_{\pi}}^{2}$ (see Lemma 2) and plugging all quantities into the generic PAC-Bayes bound presented in Theorem 1, we arrive at

###### Theorem 2 .

For any posterior and prior measures $\rho,\rho_{0}\in\mathcal{P}$, error tolerance $\delta\in(0,1]$, and deterministic policy $\pi$, simultaneously, the following inequality holds with probability at least $1-\delta$:

$$ $\displaystyle\mathds{E}_{X\sim\rho}||Q_{\pi}-X||_{P_{\pi}}^{2}$ (2) $\displaystyle~{}\leq\frac{1}{(1-\gamma)^{2}}\Bigg{(}\widehat{L}_{\mathcal{D}}( \rho)+\frac{1}{n}\left[KL(\rho||\rho_{0})+\ln\frac{1}{\delta}+\frac{nR^{2}}{(1 -\gamma)^{2}}\right]-\gamma^{2}\mathds{E}_{X\sim\rho}\mathds{V}\mathrm{ar}_{s \sim P_{\pi}}\left[X(s,\pi(s))\right]\Bigg{)}.$ $$

This bound is vacuous due to the term $(nR^{2})/(1-\gamma)^{2}$. However, it is free from the limitations specialized bounds introduce, for instance, the boundedness of the loss to the unit interval (McAllester, ; Seeger, ) and the choice of a multiplier on the empirical risk term (Catoni, ). Our main concern is to develop an algorithm using learning-theoretic tools and not to provide tight performance guarantees. However, tighter guarantees can be given by plugging the learned posterior of our algorithm into an existing bound rigorously developed for a specific purpose.

###### Lemma 1 .

###### Theorem 2 .

### 3.2 Implementation

We take the following steps to implement the bound:

##### 1)

We model the posterior distribution as an empirical distribution comprising an ensemble of $K$ critic networks, $\mathcal{X}:=\{X_{k}:\mathcal{S}\times\mathcal{A}\rightarrow\mathds{R},k\in[K]\}$, with corresponding weights $\theta_{k}$.
That is, we have
$\rho(A):=\frac{1}{K}\sum_{k=1}^{K}\delta_{X_{k}}(A)$
for $A\in\sigma(\mathcal{S})$ and Dirac measure $\delta$.
We also introduce a target copy, $\bar{X}_{k}$, for each ensemble element with parameters updated by Polyak averaging as $\bar{\theta}_{k}\leftarrow(1-\tau)\bar{\theta}_{k}+\tau\theta_{k}$ for some $\tau\in[0,1]$. The resulting empirical risk term for a single observation is
$\frac{1}{K}\sum_{k=1}^{K}\big{(}r+\gamma\bar{X}_{k}(s^{\prime},\pi(s^{\prime})
)-X_{k}(s,a)\big{)}^{2}$
where $\bar{X}_{k}$ are used in the target computations to ensure robust training (Lillicrap et al., ).

##### 2)

We model the distributions $\rho,\rho_{0}$ directly on the function space due to multiple reasons. Deep reinforcement learning setups use action-value functions in downstream tasks during training, e.g., exploration, bootstrapping, and actor training.
Design choices such as how much to explore and how conservatively to evaluate the Bellman target can only be made on the function space. Furthermore, according to the data processing inequality (Polyanskiy & Wu, , Theorem 6.2), the function-space view yields a tighter generalization bound than the weight-space view. The KL divergence between two measures $\rho,\rho_{0}$ defined on $\mathcal{H}$ can be expressed as (Rudner et al., ):

$$ $\mathrm{KL}\left(\rho\;\|\;\rho_{0}\right)=\sup_{\mathcal{D}\in\mathcal{B}} \mathds{E}_{s\in\mathcal{D}}\left[\mathds{E}_{X\sim\rho}\left[\log f_{\rho}(X| s,\pi(s))-\log f_{\rho_{0}}(X|s,\pi(s))\right]\big{.}\right],$ $$

where $f_{\rho}$ and $f_{\rho_{0}}$ are the probability density functions of the two measures evaluated at $X$ for a given state-action pair and $\mathcal{B}$ is the space of all possible data sets $\mathcal{D}$. As the $\sup$ calculation is intractable in practice, Rudner et al. () approximate it with

$$ $\sup_{B\in\{B_{j}:j\in[J]\}}\frac{1}{J}\sum_{j=1}^{|B_{j}|}\log f_{\rho}(s,\pi (s))-\log f_{\rho_{0}}(s,\pi(s)),$ $$

where $B_{j}$ are minibatches sampled from the available data set. It underestimates the true value at a degree inversely proportional to $J$. We introduce a simpler approximation that is more accurate for any fixed sample: $\sum_{j=1}^{J}\sum_{j=1}^{|B_{j}|}\log f_{\rho}(s,\pi(s))-\log f_{\rho_{0}}(s,
\pi(s))$ since the sum of a set of scalars upper bounds their supremum. We are not aware of any earlier application of function-space priors in the context of PAC-Bayesian learning, especially with application to reinforcement learning.

##### 3)

Inspired by prior work on PAC Bayes outside the reinforcement learning context (Ambroladze et al., ; Dziugaite & Roy, ), we adopt a data-informed prior $\rho_{0}$ to attain a tight PAC Bayes bound that can be used more reliably for policy evaluation. As the most recent and robust information about the action values are stored in the targets $\bar{X}_{k}$, we use them to build a maximum likelihood estimate of a normal density. Since the target networks are trained to evaluate the next state action-values, we choose $f_{\rho_{0}}(s^{\prime},\pi(s^{\prime}))=\mathcal{N}(\bar{\mu}_{\pi}(s^{\prime
}),\sigma_{0}^{2})$ where $\bar{\mu}_{\pi}(s^{\prime})=\frac{1}{K}\sum_{k=1}^{K}\bar{X}_{k}(s^{\prime},
\pi(s^{\prime}))$. Projecting the random variable one-time step backwards, we get $f_{\rho_{0}}(s,\pi(s)):=\mathcal{N}(r+\gamma\bar{\mu}_{\pi}(s^{\prime}),\gamma
^{2}\bar{\sigma}_{0}^{2})$ where $r$ is the reward observation related to state $s$. Note that the use of critic targets does not violate the assumptions of the PAC-Bayes bound as $\rho_{0}$ is built on the critic targets evaluated at the previous gradient step and the bound is given only for the current minibatch.

##### 4)

The posterior $\rho$ defined in Step 1 as an ensemble does not have a density function available in analytical form. We approximate its appearance in the logarithm term of the KL divergence by a normal density $f_{\rho}(s,\pi(s)):=\mathcal{N}(\mu_{\pi}(s),\sigma_{\pi}^{2}(s))$ where $\mu$ is calculated as in Step 3 but on the learned critic networks $X_{i}$ instead of their targets and $\sigma_{\pi}^{2}(s)=\frac{1}{K-1}\sum_{k=1}^{K}(X_{k}(s,\pi(s))-\mu_{\pi}(s))^
{2}$ on the current state $s$ instead of the next state $s^{\prime}$. Although $\mathrm{KL}\left(f_{\rho}\;\|\;f_{\rho_{p}}\right)$ has an analytical solution, we choose the following approximation to ensure that the computation stays closer to the true posterior:

$$ $\displaystyle\mathrm{KL}\left(\rho(s,\pi(s))\;\|\;\rho_{0}(s,\pi(s))\big{.} \right)\approx\frac{1}{2K}\sum_{k=1}^{K}\Bigg{(}\frac{(r+\gamma\bar{\mu}_{\pi} (s^{\prime})-X_{k})^{2}}{\gamma^{2}\sigma_{0}^{2}}-\log\sigma_{\pi}^{2}(s) \Bigg{)}+\text{const}.$ $$

See Appendix A for the full details of the derivation.

##### 5)

Since $\log(x)<x,\forall x\in\mathds{R}^{+}$, taking the logarithm of the expected variance term in Eq. 2 makes the right-hand side of the inequality larger. Hence, it keeps the bound still valid. We use this version to ensure that the impact of increased ensemble element variances on the loss diminishes gradually. We observed this approach to improve performance, although the former option also learns.

##### 6)

We apply bootstrapping to detach the correlation between the ensemble elements, which has significant practical benefits demonstrated in prior work on deep exploration (Osband et al., ; ). We pass each minibatch through a random binary mask which effectively filters some portion of the data for each ensemble element.

Putting all the pieces together, we arrive at the critic training objective

$$ $\begin{split}&L(\{X_{k}:k\in[K]\}):=\underbrace{\frac{1}{nK}\sum_{i=1}^{n}\sum _{k=1}^{K}b_{ik}\Big{(}r_{i}+\gamma\bar{X}_{k}(s^{\prime}_{i},\pi(s^{\prime}_{ i}))-X_{k}(s_{i},\pi(s_{i}))\Big{)}^{2}}_{\text{Diversity}}\\ &+\underbrace{\frac{1}{nK}\sum_{i=1}^{n}\sum_{k=1}^{K}\frac{b_{ik}\big{(}r_{i} +\gamma\bar{\mu}_{\pi}(s^{\prime}_{i})-X_{k}(s_{i},\pi(s_{i}))\big{)}^{2}}{2 \gamma^{2}\sigma_{0}^{2}}}_{\text{Coherence}}-\underbrace{\frac{\gamma^{2}+ \tfrac{1}{2}}{n}\sum_{i=1}^{n}\log\sigma_{\pi}^{2}(s_{i})}_{\text{Propagation} }\end{split}$ (3) $$

for binary bootstrap masks $b_{ik}\sim\mathrm{Bernoulli}(1-\kappa),~{}\forall~{}[n]\times[K]$ for a bootstrapping rate ${\kappa\in(0,1)}$.(^3^33We calculate $\bar{\mu}_{\pi}$ and $\sigma_{\pi}^{2}$ after applying the bootstrap masks.)
The loss is computed by one forward pass through each ensemble member and their targets per data point with additional constant-time operations. Hence its computation time is similar to any other actor-critic method. The loss comprises three terms with interpretable roles. The first induces *diversity* into the ensemble by training each member on its individual targets.
This way the model quantifies the uncertainty of its predictions as observations assigned to similar action values can only be those all ensemble elements are familiar with.
The second term ensures *coherence* among ensemble elements as it trains them with the same target.
The third term is a regularizer that repels ensemble elements away from each other in the absence of counter-evidence. This uncertainty *propagation* is maintained, as the model cannot find a solution to collapse the ensemble elements into a single solution. Propagation of uncertainties across time steps is known to have a critical role in deep exploration (Osband et al., ).
As the variance increases, the PBAC loss converges to BootDQN-P (Osband et al., ). As it shrinks, it converges to the deterministic policy gradient.

Note that the PBAC critic training loss also nicely unifies the advantages of variational Bayesian inference (Blei et al., ) and Bayesian deep ensembles (Lakshminarayanan et al., ) into a single theoretically backed framework.
Unlike variational Bayes, it works for density-free posteriors and unlike Bayesian deep ensembles, it permits a justified use of prior regularization via the Kullback-Leibler divergence term.

##### Actor training and behavior policy.

We devise an actor network with a trunk $g(s)$ shared across the ensemble and individual heads $\pi_{k}(s):=(h_{k}\circ g)(s)$ for each ensemble element. Since the optimal decision rule under uncertainty is the Bayes predictor, we train the actor on the average value of each state with respect to the learned posterior $\operatorname*{arg\,max}_{\pi}\mathds{E}_{s\sim P_{\pi}}\mathds{E}_{X\sim\rho}
X(s,\pi(s))$ and implement its empirical approximation as $\operatorname*{arg\,max}_{g,h_{1},\ldots,h_{K}}\frac{1}{nK}\sum_{i=1}^{n}\sum_
{k=1}^{K}X_{k}(s,\pi_{k}(s))$.
We perform posterior sampling for exploration counting on its demonstrated theoretical benefits (Strens, ; Osband et al., ; Grande et al., ) and practical success in discrete control (Osband et al., ; ; Fellows et al., ). That is, our behavior policy is randomly chosen among the available $K$ options and fixed for a number of time steps as practiced in prior work (Touati et al., ). In critic training, the Bellman targets are computed with the active behavior policy.
See Section B.4 for details of how the hyperparameters of our model are chosen and the pseudocode in Appendix C for further algorithmic details.

## 4 Experiments

Figure: Figure 2: *Ant reward curves.* As we increase the sparsity of the reward, the models start to struggle to learn, with PBAC remaining most stable. See Figure 4 for the remaining reward curves.
Refer to caption: x4.png

Table: Table 1: *Main results.* InterQuartile Mean (IQM) scores over ten seeds with [lower, upper] quantiles. A higher IQM indicates better performance. For each task, we make the IQM values bold if they fall within the range of the highest IQM score.

With the experimental evaluation, we aim to validate our theoretical claims on improved performance for challenging deep exploration tasks with sparse rewards.
Focusing on environments with nonlinear dynamics and continuous state and action spaces,
we rely on a mixture of established sparse benchmarks from the DMC suite (Tassa et al., ) and introduce new sparse reward benchmarks based on various MuJoCo environments (Todorov et al., ).
The aim is to evaluate whether PBAC improves performance in sparse reward setups while remaining competitive on their original standard dense reward counterparts.
In Section B.1 we discuss prior work on sparse environments.

To model reward sparsity in the MuJoCo environments, we explore the following two variations:

- *(i)*
A sparse version in which the health reward is always set to zero, therefore removing any incentive for the agent to maintain stability. This can cause the agent to prioritize speed (minimizing positional delay), potentially leading to inefficient movement patterns such as falling, rolling, or chaotic behavior. Without incentives for stability, the agent may fail to maintain balance or learn proper locomotion, resulting in suboptimal performance, harder training, and reduced overall effectiveness.
- *(ii)*
A very-sparse version in which the forward reward proportional to velocity is granted only if the agent reaches a distance threshold $c$. The degree of sparsity, hence the task difficulty, increases proportionally to $c$. This level of sparsity is applied on top of the zero health reward from the sparse modification. Although this incentivizes reaching the target, the lack of intermediate rewards for progress may lead the agent to struggle with exploration, resulting in slower learning and difficulty in discovering effective policies as the agent infrequently gains informative signals from the environment.

In these settings, the agent does not receive any positive reward and pays a penalty for using its actuators for failed explorations. Hence, they are well-suited for testing how directed the exploration scheme of a learning algorithm is. We use them to assess whether an exploration strategy can consistently promote effective exploration, when the agent encounters a lack of informative feedback during learning.

We build an ensemble of ten Q-functions and use a replay ratio of five to improve sample efficiency. This approach has been shown to achieve the same level of performance accuracy as state-of-the-art methods, effectively addressing sample efficiency, as demonstrated in Nauman et al. ().
More details on the reward structure of each environment and the remaining design choices are provided in Appendix B.
We provide a public implementation at anonymous.

##### Baseline models.

We compare our method with other state-of-the-art exploration approaches on three standard MuJoCo tasks and their sparse versions along with three sparse DMC tasks.
REDQ (Chen et al., ) serves as a state-of-the-art representative of ensemble-based maximum entropy methods.
We choose SAC-DRND (Yang et al., ) as the best representative of the RND family integrated to SAC, and BootDQN-P (Osband et al., ) as a close SOTA Bayesian model-free method to our model. Finally, BEN (Fellows et al., ) as the best representative approach that can learn the Bayes-optimal policies. More details about the selected baselines and design choices can be found in Appendix B.

Figure: Figure 3: *Ablation.* Varying bootstrap rate (BR), posterior sampling rate (PSR) and prior variance (PV) on cartpole.
Refer to caption: x7.png

##### Main results.

We summarize our results in Table 1, reporting the interquartile mean (IQM) (Agarwal et al., ) together with the corresponding interquartile range over ten seeds. Reported are both the reward on the final episode, as well as the area under learning curve (AULC) for the whole training period, which quantifies the convergence speed. See Figure 2 for reward curves on the ant environment throughout increasing sparsity. We provide the corresponding curves for all environments in Figure 4.
PBAC is competitive in most environmental settings and excels especially in the learning speed (subtable (b)) in sparse environments.

##### Effects of hyperparameters.

The three main hyperparameters of PBAC are the bootstrap rate (BR) $\kappa$, the posterior sampling rate (PSR), and the prior variance (PV) $\sigma_{0}$ of $\rho_{0}$.
An increase in the bootstrap rate enforces a higher diversity among the ensemble members. Decreasing the prior variance instead reduces diversity by pushing them towards a common mean. Lastly, the posterior sampling rate allows us to finetune the amount of exploration. While increasing the bootstrap rate and decreasing in the posterior sampling rate considerably slows down the learning process, PBAC remains robust to changes in the prior variance.
We visualize their relative influence on the learning process using the cartpole environment conceptually in Figure 3.
See Figure 7 and Figure 8 for more detailed figures on the cartpole and sparse ant environments.

##### Exploration patterns.

Figure 1 shows how PBAC explores the first two dimensions of the state space (position and angle) in the cartpole environment, throughout its training process. We describe this visualization in greater detail and include the remaining methods as well as a second environment (sparse ant) in Section D.2.

## 5 Conclusion

We introduced a method to do deep exploration in sparse reward environmental settings for the first time with a principled PAC-Bayesian approach. Comparing it to various state-of-the-art baselines, we demonstrated its superior performance on a wide range of continuous control benchmarks with various sparse reward patterns.

As the goal of our proposal is primarily to solve the task of deep exploration, PBAC’s performance is sensitive to hyperparameters in the dense reward environments. While performing competitively in two of them, *ant* and *hopper*, it struggles, as do several of the baselines in the dense *humanoid* environment. This is due to the very high health reward of $r=5$ an agent receives after every step, compared to $r=1$ in the other two. It is not surprising that in this situation random exploration is sufficient and more robust. However, as soon as the reward becomes sparse, PBAC remains the only method to learn the task.

A theoretical limitation is that our current work does not provide any convergence guarantees on PBAC’s behavior. This theoretical problem requires, and deserves, dedicated investigation. As PBAC builds on a sum of two Bellman backups and a regularizer, it will inherit similar properties to the convergence guarantees of stochastic iterative $Q$-learning variants. Generalization of these guarantees to continuous state spaces is known to be a nontrivial problem which we consciously keep outside our focus.

## Appendix A Proofs and derivations

For practical purposes, we assume in the proofs that all probability measures except $\rho$ have densities. The proofs can be straightforwardly extended by lifting this assumption.

##### Lemma 1 .

For any $\rho$ defined on $X$, the following identity holds

$$ $\displaystyle\widetilde{L}(\rho)=\mathds{E}_{X\sim\rho}||T_{\pi}X-X||_{P_{\pi} }^{2}+\gamma^{2}\mathds{E}_{X\sim\rho}[\mathds{V}\mathrm{ar}_{s\sim P_{\pi}} \left[X(s,\pi(s))\right]].$ $$

###### Proof of Lemma 1 .

For a fixed $X$ we have

$$ $\displaystyle\widetilde{L}(X)$ $\displaystyle=\mathds{E}_{s\sim P_{\pi}}\left[\mathds{E}_{s^{\prime}\sim P( \cdot|s,\pi(s))}\left[\left(\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})-X(s,\pi( s))\right)^{2}\Big{|}s\right]\right]$ $\displaystyle~{}=\mathds{E}_{s\sim P_{\pi}}\Big{[}\mathds{E}_{s^{\prime}\sim P (\cdot|s,\pi(s))}\big{[}\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})^{2}$ $\displaystyle\qquad\qquad\qquad\qquad+X(s,\pi(s))^{2}-2\widetilde{T}_{\pi}X(s, \pi(s),s^{\prime})X(s,\pi(s))|s\big{]}\Big{]}$ $\displaystyle~{}=\mathds{E}_{s\sim P_{\pi}}\Big{[}\mathds{E}_{s^{\prime}\sim P (\cdot|s,\pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})^{2}|s\right]$ $\displaystyle\qquad\qquad\qquad\qquad+X(s,\pi(s))^{2}-2\mathds{E}_{s^{\prime} \sim P(\cdot|s,\pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right ]X(s,\pi(s))\Big{]}$ $\displaystyle~{}=\mathds{E}_{s\sim P_{\pi}}\Big{[}\mathds{E}_{s^{\prime}\sim P (\cdot|s,\pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right]^{2}$ $\displaystyle\qquad\qquad\qquad\qquad+\mathds{V}\mathrm{ar}_{s^{\prime}\sim P( \cdot|s,\pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right]+X(s, \pi(s))^{2}$ $\displaystyle\qquad\qquad\qquad\qquad-2\mathds{E}_{s^{\prime}\sim P(\cdot|s, \pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right]X(s,\pi(s)) \Big{]}$ $\displaystyle~{}=\mathds{E}_{s\sim P_{\pi}}\Big{[}\left(\mathds{E}_{s^{\prime} \sim P(\cdot|s,\pi(s))}\left[(\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s \right]-X(s,\pi(s))\right)^{2}$ $\displaystyle\qquad\qquad\qquad\qquad+\mathds{V}\mathrm{ar}_{s^{\prime}\sim P( \cdot|s,\pi(s))}\left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right]\Big{]}$ $\displaystyle~{}=\mathds{E}_{s\sim P_{\pi}}\left[\Big{(}T_{\pi}X(s,\pi(s))-X(s ,\pi(s))\Big{)}^{2}+\mathds{V}\mathrm{ar}_{s^{\prime}\sim P(\cdot|s,\pi(s))} \left[\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})|s\right]\right]$ $\displaystyle~{}=||T_{\pi}X-X||_{P_{\pi}}^{2}+\mathds{E}_{s\sim P_{\pi}}\left[ \mathds{V}\mathrm{ar}_{s^{\prime}\sim P(\cdot|s,\pi(s))}\left[\widetilde{T}_{ \pi}X(s,\pi(s),s^{\prime})|s\right]\right]$ $\displaystyle~{}=||T_{\pi}X-X||_{P_{\pi}}^{2}+\mathds{E}_{s\sim P_{\pi}}\left[ \mathds{V}\mathrm{ar}_{s^{\prime}\sim P(\cdot|s,\pi(s))}\left[r(s,\pi(s))+ \gamma X(s^{\prime},\pi(s^{\prime}))|s\right]\right]$ $\displaystyle~{}=||T_{\pi}X-X||_{P_{\pi}}^{2}+\gamma^{2}\mathds{E}_{s\sim P_{ \pi}}\left[\mathds{V}\mathrm{ar}_{s^{\prime}\sim P(\cdot|s,\pi(s))}\left[X(s^{ \prime},\pi(s^{\prime}))|s\right]\right].$ $$

Since the Markov process is stationary we get

$$ $\displaystyle\mathds{E}_{s\sim P_{\pi}}\left[\mathds{E}_{s^{\prime}\sim P( \cdot|s,\pi(s))}\left[X(s^{\prime},\pi(s^{\prime}))|s\right]\right]=\mathds{E} _{s\sim P_{\pi}}\left[X(s,\pi(s))\right]$ $$

as well as

$$ $\displaystyle\mathds{E}_{s\sim P_{\pi}}\left[\mathds{E}_{s^{\prime}\sim P( \cdot|s,\pi(s))}\left[X(s^{\prime},\pi(s^{\prime}))^{2}|s\right]\right]= \mathds{E}_{s\sim P_{\pi}}\left[X(s,\pi(s))^{2}\right].$ $$

Hence, the variance term can be expressed as

$$ $\displaystyle\mathds{E}_{s\sim P_{\pi}}\left[\mathds{V}\mathrm{ar}_{s^{\prime} \sim P(\cdot|s,\pi(s))}\left[X(s^{\prime},\pi(s^{\prime}))|s\right]\right]$ $\displaystyle=\mathds{E}_{s\sim P_{\pi}}\left[X(s,\pi(s))^{2}\right]-\mathds{E }_{s\sim P_{\pi}}\left[X(s,\pi(s))\right]^{2}$ $\displaystyle=\mathds{V}\mathrm{ar}_{s\sim P_{\pi}}\left[X(s,\pi(s))\right].$ $$

Taking the expectation over $X$ with respect to $\rho$ concludes the proof.
∎

###### Lemma 2 .

For any $Q_{1},Q_{2}:\mathcal{S}\times\mathcal{A}\rightarrow\mathds{R}$ and stationary state visitation distribution $P_{\pi}$, the following inequality holds:

$$ $\displaystyle||T_{\pi}Q_{1}-T_{\pi}Q_{2}||_{P_{\pi}}\leq\gamma||Q_{1}-Q_{2}||_ {P_{\pi}}.$ $$

That is, the Bellman operator $T_{\pi}$ is a $\gamma$-contraction with respect to the $P_{\pi}$-weighted $L_{2}$-norm $\lVert\cdot\rVert_{P^{\pi}}$

###### Proof of Lemma 2 .

$$ $\displaystyle\lVert T_{\pi}$ $\displaystyle Q_{1}-T_{\pi}Q_{2}\rVert_{P_{\pi}}^{2}=\mathds{E}_{s\sim P_{\pi} }\left[\Big{(}T_{\pi}Q_{1}(s,\pi(s))-T_{\pi}Q_{2}(s,\pi(s))\Big{)}^{2}\right]$ $\displaystyle=\gamma^{2}\mathds{E}_{s\sim P_{\pi}}\Big{[}\Big{(}\mathds{E}_{s^ {\prime}\sim P(\cdot|s,\pi(s))}\left[T_{\pi}Q_{1}(s^{\prime},\pi(s^{\prime}))- T_{\pi}Q_{2}(s^{\prime},\pi(s^{\prime}))|s\right]\Big{)}^{2}\Big{]}$ $\displaystyle\leq\gamma^{2}\mathds{E}_{s\sim P_{\pi}}\Big{[}\mathds{E}_{s^{ \prime}\sim P(\cdot|s,\pi(s))}\Big{[}\Big{(}T_{\pi}Q_{1}(s^{\prime},\pi(s^{ \prime}))-T_{\pi}Q_{2}(s^{\prime},\pi(s^{\prime}))\Big{)}^{2}\Big{|}s\Big{]} \Big{]}$ (Jensen) $\displaystyle=\gamma^{2}\mathds{E}_{s^{\prime}\sim P_{\pi}}\Big{[}\Big{(}T_{ \pi}Q_{1}(s^{\prime},\pi(s^{\prime}))-T_{\pi}Q_{2}(s^{\prime},\pi(s^{\prime})) \Big{)}^{2}\Big{]}.$ (Stationarity) $$

Taking the square-root of both sides yields the result.
∎

###### Lemma 3 .

For any $\rho$ defined on $X$ the following inequality holds:

$$ $\mathds{E}_{X\sim\rho}\lVert X-Q_{\pi}\rVert_{P_{\pi}}\leq\frac{\mathds{E}_{X \sim\rho}\lVert T_{\pi}X-X\rVert_{P_{\pi}}}{1-\gamma}.$ $$

###### Proof of Lemma 3 .

For any fixed $X$ we have

$$ $\displaystyle\lVert X-Q_{\pi}\rVert_{P_{\pi}}$ $\displaystyle=\lVert X-T_{\pi}X+T_{\pi}X-Q_{\pi}\rVert_{P_{\pi}}$ $\displaystyle=\lVert X-T_{\pi}X+T_{\pi}X-T_{\pi}Q_{\pi}\rVert_{P_{\pi}}$ $\displaystyle\leq\lVert X-T_{\pi}X\rVert_{P_{\pi}}+\lVert T_{\pi}X-T_{\pi}Q_{ \pi}\rVert_{P_{\pi}}$ (Triangle ineq.) $\displaystyle\leq\lVert X-T_{\pi}X\rVert_{P_{\pi}}+\gamma\lVert X-Q_{\pi} \rVert_{P_{\pi}}.$ ( Lemma 2 ) $$

Rearranging the terms and integrating over all $X$’s weighted by $\rho$ yields the result.
∎

###### Proof of Lemma 1 .

###### Lemma 2 .

###### Proof of Lemma 2 .

###### Lemma 3 .

###### Proof of Lemma 3 .

##### Theorem 2 .

*For any posterior and prior measures $\rho,\rho_{0}\in\mathcal{P}$, error tolerance $\delta\in(0,1]$, and deterministic policy $\pi$, simultaneously, the following inequality holds with probability at least $1-\delta$:*

$$ $\displaystyle\mathds{E}_{X\sim\rho}||Q_{\pi}-X||_{P_{\pi}}^{2}$ (4) $\displaystyle~{}\leq\frac{1}{(1-\gamma)^{2}}\Bigg{(}\widehat{L}_{\mathcal{D}}( \rho)+\frac{1}{n}\left(\mathrm{KL}\left(\rho\;\|\;\rho_{0}\right)+\ln\frac{1}{ \delta}+\frac{nR^{2}}{(1-\gamma)^{2}}\right)-\gamma^{2}\mathds{E}_{X\sim\rho} \mathds{V}\mathrm{ar}_{s\sim P_{\pi}}\left[X(s,\pi(s))\right]\Bigg{)}.$ $$

###### Proof of Theorem 2 .

Choosing $d(a,b)=|a-b|$ and applying Theorem 1 we get with probability at least $1-\delta$

$$ $\displaystyle\mathds{E}_{h\sim\rho}[L(h)]$ $\displaystyle\leq\mathds{E}_{h\sim\rho}[\widehat{L}_{\mathcal{D}}(h)]+\frac{1} {n}\left(\mathrm{KL}\left(\rho\;\|\;\rho_{0}\right)+\ln\left(\frac{1}{\delta} \mathds{E}_{\mathcal{D}\sim P}\mathds{E}_{h\sim\rho_{0}}e^{nd(\widehat{L}_{ \mathcal{D}}(h),L(h))}\right)\right).$ $$

Since $(\widetilde{T}_{\pi}X(s,\pi(s),s^{\prime})-X(s,\pi(s)))^{2}\in[0,R^{2}/(1-
\gamma)^{2}]$ in the assumed discounted setup, we have

$$ $\displaystyle\ln\left(\frac{1}{\delta}\mathds{E}_{\mathcal{D}\sim P}\mathds{E} _{h\sim\rho_{0}}e^{nd(\widehat{L}_{\mathcal{D}}(h),L(h))}\right)$ $\displaystyle\leq\ln\left(\frac{1}{\delta}\mathds{E}_{\mathcal{D}\sim P} \mathds{E}_{h\sim\rho_{0}}e^{n\frac{R^{2}}{(1-\gamma)^{2}}}\right)=\ln\frac{1} {\delta}+\frac{nR^{2}}{(1-\gamma)^{2}}.$ $$

Plugging this result into the bound with $L(\rho):=\mathds{E}_{X\sim\rho}[L(X)]$ and ${\widehat{L}_{\mathcal{D}}(\rho):=\mathds{E}_{X\sim\rho}[\widehat{L}_{\mathcal
{D}}(X)]}$ gives

$$ $\displaystyle L(\rho)$ $\displaystyle\leq\widehat{L}_{\mathcal{D}}(\rho)+\frac{1}{n}\left(\mathrm{KL} \left(\rho\;\|\;\rho_{0}\right)+\ln\frac{1}{\delta}+\frac{nR^{2}}{(1-\gamma)^{ 2}}\right).$ $$

By Lemma 1 we get

$$ $\displaystyle\mathds{E}_{X\sim\rho}$ $\displaystyle||T_{\pi}X-X||_{P_{\pi}}^{2}$ $\displaystyle\leq\widehat{L}_{\mathcal{D}}(\rho)+\frac{1}{n}\left(\mathrm{KL} \left(\rho\;\|\;\rho_{0}\right)+\ln\frac{1}{\delta}+\frac{nR^{2}}{(1-\gamma)^{ 2}}\right)-\gamma^{2}\mathds{E}_{X\sim\rho}\mathds{V}\mathrm{ar}_{s\sim P_{\pi }}\left[X(s,\pi(s))\right].$ $$

Applying Lemma 3 on the left-hand side yields the intended result.
∎

###### Proof of Theorem 2 .

### A.1 Derivation of the approximation to the KL divergence term

$$ KL $\displaystyle\big{(}\rho(s,\pi(s))||\rho_{0}(s,\pi(s))\big{)}\approx\mathds{E} _{X\sim\rho}[\log f_{\rho}(X|s,a)-\log f_{\rho_{0}}(X|s,a)]$ $\displaystyle\approx\frac{1}{K}\sum_{k=1}^{K}\log f_{\rho}(X_{k}|s,\pi_{k}(s)) -\log f_{\rho_{0}}(X_{k}|s,\pi_{k}(s))$ $\displaystyle=\frac{1}{2}\frac{1}{K}\sum_{k=1}^{K}\left(-\log\sigma_{\pi}^{2}( s)-\frac{(r+\gamma\mu_{\pi}(s)-X_{k})^{2}}{\sigma_{\pi}^{2}(s)}+\log(\gamma^{2 }\sigma_{0}^{2})+\frac{(r+\gamma\bar{\mu}_{\pi}(s^{\prime})-X_{k})^{2}}{\gamma ^{2}\sigma_{0}^{2}}\right)$ $\displaystyle=\frac{1}{2}\Bigg{(}-\frac{1}{K}\sum_{k=1}^{K}\log\sigma_{\pi}^{2 }(s)-\frac{1}{\sigma_{\pi}^{2}(s)}\underbrace{\frac{1}{K}\sum_{k=1}^{K}(r+ \gamma\mu_{\pi}(s)-X_{k})^{2}}_{=\frac{K-1}{K}\sigma_{\pi}^{2}(s)}$ $\displaystyle\qquad+\log(\gamma^{2}\sigma_{0}^{2})+\frac{(r+\gamma\bar{\mu}_{ \pi}(s^{\prime})-X_{k})^{2}}{\gamma^{2}\sigma_{0}^{2}}\Bigg{)}$ $\displaystyle=\frac{1}{2K}\sum_{k=1}^{K}\Bigg{(}\frac{(r+\gamma\bar{\mu}_{\pi} (s^{\prime})-X_{k})^{2}}{\gamma^{2}\sigma_{0}^{2}}-\log\sigma_{\pi}^{2}(s) \Bigg{)}+\text{const}.$ $$

## Appendix B Experimental details

### B.1 Prior work on reward sparsity in continuous control

How to structure a sparse reward environment is a matter of debate.
We identify two broad groups of environments in the current state-of-the-art literature, without claiming this to be an exhaustive survey.
These consist either of native, i.e., inherent sparsity in the original environment or are custom modifications of dense reward environments made by the respective authors.
We follow the naming convention for each of the environments as used in the Gymnasium (Towers et al., ) and DMControl (Tassa et al., ) libraries unless otherwise noted.

##### i) Binary rewards based on proximity to a target state.

Houthooft et al. () and Fellows et al. () study Mountain Car continuous and sparse cartpole swing up.
Fellows et al. () reach a reward of around 500 in cartpole within more than 1.5 million environment interactions, far behind the levels we report in our experiments. Curi et al. () study reacher, pusher, a custom sparsified version of reacher with a reward squashed around the goal state and action penalty with an increased share. Houthooft et al. (), Mazoure et al. (), and Amin et al. () sparsify various MuJoCo locomotors by granting binary reward based on whether the locomotor reaches a target $x$-coordinate. This reward design has limitations: i) Since there is no action penalty, the locomotor does not need to aim at its actuators in the most efficient way, ii) Since there is no forward reward proportional to velocity, the locomotor’s performance after reaching a target location becomes irrelevant. For instance, a humanoid can also fall down or stand still after reaching the target.

##### ii) Increased action penalties.

Curi et al. () study cartpole and MujoCo HalfCheetah with increased action penalties. Luis et al. () use pendulum swingup with nonzero reward only in the close neighborhood of the target angle. They also apply an action cost and perturb the pendulum angle with Gaussian white noise. They also report results on PyBullet Gym locomotors HalfCheetah, Walker2D, and Ant with dense rewards. Their follow-up work (Luis et al., ) addresses a larger set of DMC environments where locomotors are customized to receive action penalties. The limitation of this reward design is that increasing the action penalty is not sufficient to sparsify the reward as the agent can still observe relative changes in the forward reward from its contributions to the total reward. In some MuJoCo variants, the agent also receives rewards on the health status, which is a signal about intermediate success against the sparse-reward learning goal. Furthermore, action penalties are typically exogeneous factors determined by energy consumption in the real world, making the challenge artificial.

In Section 4, we report results on the most difficult subset of some natively sparse environments and devise new locomotion setups that overcome the aforementioned limitations. We discuss them in the next subsection.

### B.2 Experiment pipeline design

The whole experiment pipeline is implemented in PyTorch (Paszke et al., , version $2.4.1$). The experiments are conducted on eleven continuous control environments from two physics engines. MuJoCo (Todorov et al., ; Brockman, ), and DeepMind Control (DMControl) Suite (Tassa et al., ). All MuJoCo environments used are from version 4 of the MuJoCo suite (V4), and sparse DMControl environments.

#### B.2.1 MuJoCo

From the two locomotors that can stand without control, we choose *ant* as it is defined on the $3D$ space compared to the $2D$ defined *halfcheetah*. From the two locomotors that have to learn to keep their balance, we choose *hopper* instead of *walker2d* as hopping is a more dexterous locomotion task than walking. We also choose *humanoid* as an environment where a $3D$ agent with a very large state and action space has to learn to keep its balance. The reward functions of the MuJoCo locomotion tasks have the following generic form:

$$ $r:=\underbrace{\frac{dx_{t}}{dt}}_{\text{Forward Reward}}-\underbrace{w_{a}||a _{t}||^{2}}_{\text{Action cost}}+\underbrace{H}_{\text{Health reward}}.$ $$

*Forward reward* comes from the motion speed of the agent towards its target direction and drives the agent to move efficiently toward the goal.
*Health reward* is an intermediate incentive an agent receives to maintain its balance. The *action cost* ensure that the agent solves the task using minimum energy. We implement sparsity to the locomotion environments in the following two ways using the following reward function template:

$$ $r_{\mathrm{sparse}}:=\underbrace{\frac{dx_{t}}{dt}\mathbf{1}_{x_{t}>c}}_{\text {Forward Reward}}-\underbrace{w_{a}||a_{t}||^{2}}_{\text{Action cost}}.$ $$

This function delays forward rewards until the center of mass of the locomotor $x_{t}$ reaches a chosen target position $c$, which we call as the positional delay. This reward also removes the healthy reward to ensure that the agent does not get any incentive by solving an intermediate task. It is possible to increase the sparsity of a task by increasing the positional delay. Detailed information on the sparsity levels we used in our experiments are listed in Table 2. For each environment, we chose the largest positional delay, i.e. maximum sparsity, where at least one model can successfully solve the task. Beyond this threshold, all models fail to collect positive rewards within $300000$ environment interactions. The structure of these experiments follows the same structure as what is known as the $n$-chains thought experiment, which is studied extensively in theoretical work. The essential property is that there is a long period of small reward on which an agent can overfit. See, e.g., the discussion by Strens () or Osband et al. () for further details. Information on the state and action space dimentionalities for each of the three environments is available in Table 3.

Table: Table 2: *MuJoCo environment reward hyperparameters.* See the description in the text for an explanation on each of the parameters.

#### B.2.2 Deepmind control

From DMControl, we choose *ballincup*, *cartpole*, and *reacher*, as they have sparse binary reward functions given based on task completion. In *ballincup*, the task is defined as whether the relative position of the ball to the cup centroid is below a distance threshold. In the *cartpole*, it is whether cart position and pole angle are in respective ranges $(-0.25,0.25)$ and $(0.995,1)$. Finally, in the *reacher*, it is the the distance between the arm and the location of a randomly placed target coordinate. Information on the state and action space dimentionalities for each of the threee environments is available in Table 3. We did not consider the DMC locomotors as they use the same physics engine as MuJoCo and their reward structure is less challenging due to the absence of the action penalty and the diminishing returns given to increased velocities.

Table: Table 3: *State and action space dimensionalities for MuJoCo (MJC) and DMControl (DMC).*

### B.3 Evaluation methodology

##### Performance metrics.

We calculate the *Interquartile Mean (IQM)* of the final episode reward and of the *area under learning curve (AULC)* as our performance scores where the former indicates how well the task has been solved and the latter is a measure of learning speed. The AULC is calculated using evaluation episodes after every 20,000 steps.
We calculate these rewards over ten repetitions on different seeds, where each of the methods gets the same seeds. All methods, including our approach and the baselines, utilize the same warmup phase of 10,000 steps to populate the replay buffer before initiating the learning process.

### B.4 Hyperparameters and architectures

##### PBAC specific hyperparameters.

PBAC has three hyperparameters: bootstrap rate, a posterior sampling rate, and prior variance. We observe PBAC to work robustly on reasonably chosen defaults. See Section D.3 for an ablation on a range of these for the cartpole and sparse ant environments. We list the hyperparameters we used for each environment in Table 4.

Table: Table 4: *Hyperparameters specific to PBAC.* The chosen bootstrap rate (BR), posterior sampling rate (PSR), and prior variance (PV) for each of the eleven environments. Changes from the defaults are marked in bold.

##### Shared hyperparameters and design choices.

We use a *layer normalization* (Ball et al., ) after each layer to regularize the network, and a *concatenated ReLU (CReLU)* activation function  (Shang et al., ) instead of the standard ReLU activation which enhances the model by incorporating both the positive and negative parts of the input and concatenating the results.
This activation leads to potentially better feature representations and the ability to learn more complex patterns.
Moreover, we rely on a high *replay ratio (RR)* and a small *replay buffer* size, which reduce the agent’s dependence on long-term memory and encourage it to explore different strategies.
These are employed to improve the plasticity of the learning process. Recently, Nauman et al. () showed that a combination of these design choices can overall greatly improve the agent learning ability.
Additionally, we opted to use the Huber loss function for all baseline models after observing in our preliminary trials that it consistently provided performance advantages across different baselines.
All design choices found advantageous for our model and not harmful to other have also been applied to the baselines.
Table 5 provides details on the hyper-parameters and network configurations used in our experiments.

Table: Table 5: *Shared hyper-parameters.* Hyperparameters used by all methods.

##### Actor and critic networks.

Our implementation of PBAC along with proposed baselines share the architectural designs provided in Table 6 for each critic network in the ensemble and actor network. The quantities $d_{s}$ and $d_{a}$ denote the dimension of the state space and the action space, respectively.
The output of the actor network is passed through a $\tanh(\cdot)$ function for deterministic actor networks used in PBAC, BEN, and BootDQN-P. We implemented the probabilistic actors of REDQ and DRNB as a *squashed Gaussian head* uses the first $d_{a}$ dimensions of its input as the mean and the second $d_{a}$ as the variance of a normal distribution.

Table: Table 6: *Actor and critic architectures.* Here, $d_{s}$ and $d_{a}$ are the dimensionalities of the state and action spaces.

#### B.4.1 Baselines

We compare PBAC against a range of state-of-the-art general purpose actor-critic methods that are all empowered by ensembles.
All design choices mentioned above found advantageous for our model and not harmful to other have also been applied to the baselines. Below we also explain further changes compared to the original works that we found to be benficial in preliminary experiments.

##### BEN.

Bayesian Exploration Networks (BEN), introduced by Fellows et al. () serve as the best representative that can learn a Bayesian optimal policy and handle the exploration vs. exploitation tradeoff.
We modify BEN by relying on Bayesian deep ensembles (Lakshminarayanan et al., ) instead of the normalizing flow-based approach used in the original work.
An ensemble of $K-1$ heteroscedastic critics learns a heteroscedastic univariate normal distribution over the Bellman target, while the $K$th critic, regularized by the ensemble guides the actor network.

##### BootDQN-P.

Bootstrapped DQN with randomized prior functions (Osband et al., ), a Bayesian model-free approach, serve as a close relative to our method. Throughout all environments we share most parameters with PBAC. Changes for specific parameters are discussed in Table 7, and rely on a Thompson sampling actor.
Its randomized priors allow the model to explore even in the presence of sparse reward.
A prior scaling (PS) parameter regulates their influence.

Table: Table 7: *Hyperparameters specific to BootDQN-P.* The chosen bootstrap rate (BR), posterior sampling rate (PSR), and prior scaling (PV) for each of the eleven environments. Changes from the defaults are marked in bold.

##### DRND.

Distributional randomized network distillation (DRND) (Yang et al., ), model the distribution of prediction errors from a random network. This distributional information is used as signal to guide exploration. As in the original work, we integrate it into a soft actor-critic (SAC) (Haarnoja et al., ) framework.
This random predictor network is trained via the same objective and uses the same architecture as proposed by Yang et al. (). Actor and critic networks follow the architectural choices described above. Additionally, we optimize the $\alpha$ scaling parameter in the SAC as is common practice.

##### REDQ.

Randomized ensemble double Q-learning (REDQ) (Chen et al., ) is the most competitive variant of the ensemble version of SAC as it incorporates both double Q-learning and randomization to address value estimation and exploration.
For this method all design choices are aligned with our method.
REDQ relies only on the shared parameters.

## Appendix C Pseudocode

We provide pseudocode for our model in Algorithm 1.

Figure: Algorithm 1 PAC-Bayesian Actor Critic (PBAC)

## Appendix D Further results

### D.1 Reward curves

See Figure 4 for the full reward curves of all environments corresponding to the results presented in Table 1 in the main text.

Figure: Figure 4: *Reward curves.* The reward curves for all environments throughout training corresponding to the results presented in Table 1. Visualized are the interquartile mean together with the interquartile range over ten seeds.
Refer to caption: x8.png

### D.2 State space visualizations

Throughout the training, we record the currently visited state at regular intervals and plot them in five groups, for PBAC and each of the baselines.
We visualize two environments: cartpole and sparse ant.
In each case we record every 500th step over the whole training process and record the corresponding state. The whole set is split into five groups and each is plotted as its own scatter plot.

#### D.2.1 Cartpole

Figure: Figure 5: *State visitation frequency for cartpole.* The visualization shows seed 1.
Refer to caption: x19.png

Of cartpole’s five state dimensions, only the first two are interpretable, giving us the position of the cart and the cosine of the angle of the pole. We visualize them in Figure 5. As discussed above, the agent gets rewarded only if it manages to stay close to the zero with an upwards pole, i.e., an angle close to one.

PBAC is able to quickly explore the state space and then concentrate on visiting the states with hight reward (i.e., the top middle).
Similar to it, BootDQN-P has no problem in exploring the state space, however it never manages to find the narrow target and thus never converges.
BEN starts exploring a wide range of states, but ultimately gets stuck in this seed without being able to find the target. As shown in Figure 4 BEN’s performance varies greatly depending on the random initial seed in this environment. As such, this is a random representative of a failure case, not of its general performance on cartpole.
DRND and REDQ quickly get stuck as well within a small subset of the state space, essentially just exploring the position of the cart within ever being able to significantly change the angle of the pole.

#### D.2.2 Sparse ant

Figure: Figure 6: *State visitation frequency for sparse ant.* The visualiztion shows seed=1.
Refer to caption: x24.png

The ant environment has a 27 dimensional state space. In order to properly visualize what is happening we rely on TSNE (Van der Maaten & Hinton, ) and compute a two dimensional embedding, which we visualize in five subsets as for the cartpole environment.
Note that due to the inherent stochastisity of TSNE, visual consistency only exists within the scatter plots of one environment (the whole sequence is mapped jointly), but not between the methods, as each learns its own transformation.
As before we see that BootDQN-P seems to effortlessly explore a consistent area of the state space, however it never reaches an area of high reward.(^4^44Due to the nature of TSNE the visualized area might be a large one of the original observation space, or a small one, i.e., the extend of the exploration can’t be fully judged.)
DRND as well shows a similar pattern to its behavior in cartpole. It explores, but is again stuck into clusters that it can’t escape from.(^5^55The corresponding cluster in cartpole is around an angle of -1.)
BEN, REDQ, and PBAC both show a similar pattern of exploration and subsequent exploitation.

### D.3 Ablation

We evaluate the sensitivity of the training process of PBAC with respect to its three main hyperparameters, bootstrap rate, posterior sampling rate, and prior variance, on two environments.
Depending on the environment, PBAC is sensitive to their choice (see Figure 7 on the cartpole environment), and shows clearly interpretable patterns, or it remains insensitive to their choice as in the sparse ant environment visualized in Figure 8.

Figure: Figure 7: *Ablation results on cartpole.* We show varying bootstrap rates (BR), posterior sampling rates (PSR), and prior variances (PV). While PBAC is mostly robust in terms of varying prior variances, increases in the bootstrap rate and decreases in the posterior sampling rate delay the learning process. Visualized are the interquartile mean together with the interquartile range over three seeds.
Refer to caption: x29.png

Figure: Figure 8: *Ablation results on sparse ant.* We show varying bootstrap rates (BR), posterior sampling rates (PSR), and prior variances (PV). Compared to the ablation on cartpole (see Figure 7), PBAC is robust against variations in all three hyperparameters in the sparse ant environment. Visualized are the interquartile mean together with the interquartile range over three seeds.
Refer to caption: x30.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: See Weaknesses.
soundness: 2
strengths: The PAC-Bayes perspective has not been given significant attention in the RL community, and this work takes a step towards addressing that. Furthermore, the proposed algorithm does indeed appear to solve sparse-reward settings effectively.
summary: This paper studies RL in continuous spaces, and is specifically motivated by sparse-reward problems that require exploration. They take a PAC-Bayesian perspective, and derive an algorithmic approach motivated by a PAC-Bayes analysis to address such hard exploration problems. Experimental results are given illustrating its performance on several Mujoco tasks, and that it is able to solve problems with sparse rewards.
weaknesses: 1. The main theoretical result (Theorem 2) is vacuous, as is noted by the authors. It is not clear to me what purpose this result serves given this—it is trivially true that $\| Q_\pi - X \|_{P_\pi}^2 \le \frac{R^2}{(1-\gamma)^2}$, which is all this bound claims to show (unless the negative variance term can be shown to cancel out this term, but this avenue is not pursued here). Furthermore, this bound is used to motivate the algorithm, yet given that it is vacuous, one cannot draw any real conclusions from it, and thus the motivation for the algorithm becomes unclear. I would suggest removing this result and cleaning up the algorithmic motivation.
2. The experimental evaluation is limited, only considering DMC environments, and several other Mujoco tasks. Furthermore, the gains over existing methods are relatively marginal—in the majority of examples, it performs comparably to existing methods (or the stochasticity is high enough that it is not possible to give a clear ranking). 
3. The writing of this paper could be improved and the overall story made more explicit. In particular, as I understand it, the main idea is to apply a PAC-Bayes analysis to get a measure of uncertainty, then use this measure of uncertainty to induce exploration in a UCB-like manner. This was not clear, however, from reading the paper. For example, there are statements like “implement the bound” (line 306) which seem to imply this but are ambiguous (what does it mean to implement a bound?). I would encourage the authors to tighten the story and make connections between the analysis and resulting algorithm more explicit. There were various other unclear statements or issues with the exposition, for example:
	* Line 266: It was not clear to me why a function is replaced by a distribution here. This may be standard in PAC-Bayes analysis (I am not too familiar with PAC-Bayes), but is not standard in the RL literature, and I would suggest further exposition here to make clear why the loss is now over a distribution.
	* Line 302-303: In the sentence starting with “However…”, what is an “existing bound rigorously developed for a specific purpose”? Some explanation of this statement (or relevant citations of such a bound) would be helpful.
	* It was difficult to parse what the final algorithm actually is. Many of the details given in Section 3.2 are not necessary for the main body, and make it difficult to determine which points are the most salient. It would be very helpful to give an algorithm box putting all the pieces together.
4. Another paper that would be good to compare against is [1].

[1] Lee, Kimin, et al. "Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning." International Conference on Machine Learning. PMLR, 2021.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: A discussion of the weaknesses above would be highly appreciated for me to raise my score. Additionally I have a problem in understanding one crucial part of the paper:
- The authors mention that due to the long episodes in RL a PAC-Bayesian treatment has to be done based on TD errors (and these only consider consecutive state-action-state tuples and not trajectories). This makes intuitive sense to me, however I could not fully understand how the treatment still captures the uncertainty over the full trajectory space when the estimator used for bootstrapping (i.e. of the Bellman error) conflates everything to the expectation over future trajectories. Could the authors help me understand this more clearly?
soundness: 3
strengths: - This is a relevant problem in the field of reinforcement learning and from the reviewers limited exposure to PAC-Bayesian theory the derivation seems sound and is intuitive. 
- The empirical results showcase the algorithms effectiveness particularly in tasks where existing methods for deep exploration struggle (i.e. very sparse 'ant' target finding domain, humanoid etc.) which gives a convincing picture.
- I have limited understanding of PAC-Bayesian methods but am an expert on off-policy RL. From what I can tell the derivations do indeed seem novel and the idea of modelling the error of the TD-operator with a PAC-Bayesian approach seems highly promising and worthwhile for the community.
summary: The paper addresses the challenge of efficient exploration in reinforcement learning with sparse reward tasks. This is a challenging problem that has wide reaching applications in continuous control domains. They review the literature on (Bayesian inspired) deep exploration algorithms that are designed to find solutions in this setting. They then propose a novel algorithm called PAC-Bayesian Actor critic that leverages a PAC bound to achieve efficient exploration. In practice their method involves fitting a bootstrapped ensemble of function approximators (neural network) regressed to represent the error of the one-step TD Q-learning objective. This is the first principled PAC Bayesian treatment of an Actor-Critic algorithm and it seems to perform well (albeit the evaluations are on relatively standard 'simple' control domains).
weaknesses: - The practical implementation of the well motivated general algorithm requires a series of approximations (e.g. ensemble of networks, Gaussian assumption on the adaptive prior etc.) which are well described in the paper but strike me as somewhat complicated and ad-hoc. It would have been great to see some ablations of different choices here and provide the reader with understanding of why these choices are reasonable (I understand at least the ensemble of networks follows prior art. but the rest seems not already well established).
- The core derivation is relatively simple and clear, but the resulting method (due to the points above) becomes quite complicated. Making me wonder how easy it would be to reproduce and built on top of it.
- The empirical results still only consider fairly low-dimensional domains and no vision based policies/critics (perhaps with the exception of the humanoid domain which is fairly high-dimensional). And the domains are also mostly not naturally sparse reward problems but have been 'sparsified' from their dense reward versions. I have some concerns whether the presented method would also work in more relevant modern settings such as learning vision based policies in e.g. robotics and or more expressive function approximator classes such as using transformers or other large models. Do the authors have any intuitions on these and/or could one more relevant complex domain be considered? E.g. as in recent papers on RND etc.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: - There are several established sparse reward testbeds in robotics. I’m curious why the authors opted to modify Gym environments for sparse rewards. Sparse reward testbeds, such as Meta-World and D4RL, naturally simulate environments with sparse feedback. These frameworks offer realistic benchmarks that directly address sparse rewards, enabling comparison with other established state-of-the-art methods on these platforms without the need for manual modifications.

- Choice of IQM over Reward Plots: Could you elaborate on the decision to present performance results in Table 1 using IQM scores rather than traditional reward plots? I’m curious if this choice was intended to mitigate variability across seeds or to provide a more concise comparison across tasks. Would reward plots offer additional insights, or do IQM tables capture the main performance differences effectively? I understand that reward plots can sometimes be misleading due to high variability across seeds, especially in sparse reward environments where performance can vary significantly. 


**Miscellaneous Comments**
- Table 1: In the table description, "IQM of the area under learning curve" should be corrected to "area under the learning curve."
soundness: 2
strengths: - The PAC-Bayesian framework provides a flexible way to assess generalization, allowing any posterior distribution to be optimized for data, making it highly adaptable. It's a nice area of research.
- The paper covers aspects of PAC-Bayesian RL, ensuring the bound’s validity and robustness in training.
- Applying the PAC-Bayesian framework for exploration in RL is novel and challenging. So I appreciate the effort.
- Empirical across various continuous control tasks with different reward structures.
summary: This paper proposes an approach for deep exploration in sparse reward environments by applying a PAC-Bayesian framework in RL. Empirical results are presented in sparse reward environments however this method does not work in dense reward environments and lacks theoretical convergence guarantees.


Modeling the Posterior Distribution consists of the following pieces: The posterior distribution is represented as an ensemble of $K$ critic networks, each weighted equally. Distributions $\rho$ and $\rho_0$ are modeled directly in function space rather than weight space.
A data-informed prior $\rho_0$ is constructed based on the critic targets, providing the most recent information about action values. This prior is modeled as a normal distribution estimated from the critic targets. The KL divergence between $\rho$ and $\rho_0$ 
is then calculated using probability density functions evaluated at the outputs of the critic ensemble.
weaknesses: - PBAC’s structured exploration approach is less effective in dense reward environments, particularly when high rewards are frequent. In these settings, random exploration often performs as well or better.
- The method lacks convergence guarantees,  limiting confidence in its stability and long-term performance across diverse tasks. 
- Looking at the results, particularly the reward plots and Figure 4, it seems that the complexity of this method outweighs its advantages. The performance improvements shown aren’t particularly impressive, and given the considerable complexity involved.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Experiments questions:
 * Can you give more intuition for how to interpret the positional delay parameter $c$? You say in the paper that it is 2 and 1 for ant and humanoid respectively but what do these values mean? How many timesteps does it take for the agent to reach these distances? Can they be reached occasionally through random actions or do they absolutely require an exploration bonus?
 * Why no very sparse version for the humanoid environment?
 * How are hyperparameters tuned for comparison algorithms? Is there any chance that if you tuned their hyperparameters to the extent that you tuned yours then you would see similar performance? I see you tuned BootDQN-P but how about important exploration benchmarks like DRND?
 * Why does your method perform better on the sparse version of humanoid than the original?

Tiny notes / questions:
 * Figure 3 needs axis labels
soundness: 2
strengths: Originality:
 * The method is the first to formulate the deep exploration problem from a PAC-Bayesian perspective and overall their method seems original.

Quality:
 * Overall the paper is well written. They achieve decent results, especially in their custom environments.

Significance:
 * Exploration continues to be a difficult problem in a variety of settings. I believe that the problem setting is well motivated and the paper has the potential to be significant from this perspective.
* The paper has some decent results
summary: The paper presents a novel method for exploration in deep reinforcement learning. The method uses a PAC-Bayesian perspective to derive a novel critic update rule, which it then uses as part of an actor-critic setup. They actualize this using a bootstrapped ensemble of critics
weaknesses: Some key issues:
 * The paper lacks any real analysis of the results. The main takeaway seems to be "our method is better" and that's it. Why does PBAC outperform baselines in the environments where it does? Why doesn't it see a similar improvement for the other benchmarks? Are there any other insights you can share
 * I find it concerning that the main place you see a win is in your own custom environments, because it's difficult to know if this win is because of your algorithm truly doing better or if the baselines could be tuned to achieve similar performance. I think it would be good to see some other common exploration benchmarks.

Meta-review: This paper derives a deep exploration method from the perspective of PAC-Bayes. They treat an ensemble as an empirical estimate of a posterior, and apply posterior sampling during training time for exploration and Bayesian model averaging during evaluation time. They show results on a number of continuous control tasks. 

Strengths: 
The problem of deep exploration is important and the authors have an interesting take on it
The method does seem to have better performance on some tasks
The PAC-Bayes approach is underappreciated

Weaknesses:
The bound as noted by the authors themselves is vacuous, and the justifications with Reviewer NDSb were not very convincing
The simplification from the insight to the actual practical method is pretty hard to parse and non-intuitive, as noted by reviewers
The results on the benchmarks are not that compelling, REDQ does very comparably. 
The paper could benefit from some additional analysis of the results. 

The vacuous bound and relatively small gains over baselines prompt me to recommend paper rejection, but the work has high potential in the future!

Decision: Reject