# PAC-Bayesian Soft Actor-Critic Learning

Bahareh Tasdighi  Abdullah Akgül  Kenny Kazimirzak Brink  Melih Kandemir

###### Abstract

Actor-critic algorithms address the dual goals of reinforcement learning,
policy evaluation and improvement, via two separate function approximators.
The practicality of this approach comes at the expense of training
instability, caused mainly by the destructive effect of the approximation
errors of the critic on the actor. We tackle this bottleneck by employing an
existing Probably Approximately Correct (PAC) Bayesian bound for the first
time as the critic training objective of the Soft Actor-Critic (SAC)
algorithm. We further demonstrate that the online learning performance
improves significantly when a stochastic actor explores multiple futures by
critic-guided random search. We observe our resulting algorithm to compare
favorably to the state of the art on multiple classical control and locomotion
tasks in both sample efficiency and asymptotic performance.

MBRL, PAC-Bayes, …

##  1 Introduction

The process of searching for an optimal policy to govern a Markov Decision
Process (MDP) involves solving two sub-problems: i) policy evaluation, and ii)
policy improvement (Bertsekas & Tsitsiklis, 1996). The policy evaluation step
concerns with identifying a function that maps a state to its value, i.e. the
total expected reward the agent will collect by following a predetermined
policy. The policy improvement step seeks for an update on this policy such
that the visitation frequencies of the states with larger values according to
the value function learned at the policy evaluation step are increased.

Modern actor-critic methods (Peters et al., 2010; Schulman et al., 2015;
Lillicrap et al., 2016; Schulman et al., 2017; Haarnoja et al., 2018) address
the two-step nature of policy search by allocating a separate neural network
for each step, a critic network for policy evaluation and an actor network for
policy improvement. It is often straightforward to achieve policy improvement
by taking gradient-ascent steps on actor parameters to maximize the critic
output. However, as being the goodness score for actor training, the accuracy
of the critic sets a severe bottleneck for the success of the eventual policy
search algorithm at the target task. The state of the art attempts to overcome
this bottleneck via using copies of critic networks or Bellman target
estimators whose parameters are updated with time lag (Lillicrap et al., 2016)
and using the minimum of two critics for policy evaluation to tackle
overestimation due to the Jensen gap (Fujimoto et al., 2018; Haarnoja et al.,
2018).

The Probably Approximately Correct (PAC) Bayesian theory (Shawe-Taylor &
Williamson, 1997; McAllester, 1999) develops analytical statements about the
worst-case generalization performances of Gibbs predictors that hold with high
probability (Alquier, 2021). The theory assumes the predictors to follow a
posterior measure tunable to observations while maintaining similarity to a
desired prior measure. In addition to being in widespread use for deriving
analytical guarantees for model performance, PAC Bayesian bounds are useful
for developing training objectives with learning-theoretic justifications in
supervised learning (Dziugaite & Roy, 2017) and dynamical systems modeling
(Haußmann et al., 2021). To date, their potential in the reinforcement
learning setups has remained relatively unexplored.

In this paper, we demonstrate how PAC Bayesian bounds can improve the
performance of modern actor-critic algorithms when used for robust policy
evaluation. We adapt an existing PAC Bayesian bound (Fard et al., 2012)
developed earlier for transfer learning for the first time to train the critic
network of a Soft Actor-Critic (SAC) algorithm (Haarnoja et al., 2018) and
discover the following remarkable outcomes:

  * a)

The training objective naturally overcomes the notorious value overestimation
problem of approximate value iteration methods (Van Hasselt et al., 2016) and
lifts the need of training twin critics.

  * b)

The randomized critic expedites policy improvement when used as a guide for
random optimal action search.

Putting together these two observations, we devise a novel algorithm called
PAC Bayes for Soft Actor-Critic (PAC4SAC). Figure 1 illustrates its main idea.
We observe the PAC4SAC algorithm to bring about consistent performance gains
in six continuous control tasks with varying level of difficulty against its
state-of-the-art counterparts in terms of both sample efficiency and
asymptotic control performance.

Figure 1: We introduce Probably Approximately Correct Bayes for Soft Actor
Critic (PAC4SAC), a novel reinforcement learning algorithm that trains a
critic with probabilistic parameters $\theta$ for the first time using a PAC
Bayesian bound as its loss. The probabilistic nature of the critic also
enables effective random optimal action search when used as a guide for a
stochastic policy. The resulting algorithm exhibits significant speed-up in
online learning without a sacrifice from asymptotic performance.

##  2 Method

###  2.1 Problem statement

We model a learning agent and its environment as a Markov Decision Process
(MDP), which can be expressed as a tuple
$(\mathcal{S},\mathcal{A},p,r,\gamma)$ comprising a $d_{s}-$dimensional
continuous state space $\mathcal{S}:=\\{s\in\mathbb{R}^{d_{s}}$ }, a
$d_{a}-$dimensional continuous action space
$\mathcal{A}:=\\{a\in\mathbb{R}^{d_{a}}\\}$, a reward function with bounded
range $r:\mathcal{S}\times\mathcal{A}\rightarrow[r_{min},r_{max}]$, a reward
discount factor $\gamma\in(0,1]$, and a state transition distribution
$p(\cdot|s_{t},a_{t})$. Our goal is to fit the parameters $\psi$ of a policy
distribution $\pi_{\psi}$ so that it has the largest possible spread and it
maximizes the expected cumulative reward from minimum number of environment
interactions. For convenience, we denote the visitation frequency of a state
$s^{\prime}$ at time step $t+1$ as the recurrence relation below

$\displaystyle p_{t+1}^{\psi}(s^{\prime})=\mathbb{E}_{s\sim
p_{t}^{\psi}(s),a\sim\pi_{\psi}(\cdot|s)}\Big{[}p(s^{\prime}|s,a)\Big{]}$

for an assumed initial state distribution $p_{0}(\cdot)$. Denoting the entropy
of the policy distribution
$\mathbb{H}[\pi_{\psi}(\cdot|s)]=\mathbb{E}_{a\sim\pi(\cdot|s)}[-\log\pi_{\psi}(a|s)]$
for input state $s$, our objective in formal terms is to maximize

$\displaystyle J(\pi)$ $\displaystyle=\sum_{t=0}^{\infty}\mathbb{E}_{s\sim
p_{t}^{\psi},a\sim\pi_{\psi}(\cdot|s)}\Big{[}\gamma^{t}r(s,a)+\alpha\mathbb{H}[\pi_{\psi}(\cdot|s)]\Big{]},$
(1) $\displaystyle=\sum_{t=0}^{\infty}\mathbb{E}_{s\sim
p_{t}^{\psi},a\sim\pi_{\psi}(\cdot|s)}\Big{[}\gamma^{t}r(s,a)-\alpha\log\pi_{\psi}(a|s)\Big{]}$

with respect to $\pi$ where, the coefficient $\alpha>0$ is a parameter that
regulates the importance of the policy entropy on the training objective, and
$\mathbb{E}_{x\sim p(x)}[\cdot]$ is the expectation with respect to the
measure denoted in its subscript. We study the case where the true state
transition distribution $p(s^{\prime}|s,a)$ and the true reward function
$r(s,a)$ are unknown to the agent and they are estimated during training from
the observed state, action, reward, and next state tuples
$(s,a,r,s^{\prime})$.

#### Actor-critic learning.

Define the true value of a state-action pair under policy
$\pi_{\psi}(\cdot|\cdot)$, referred to as the actor, at time step $t$ of an
interaction round with an environment as

$\displaystyle Q^{{\pi_{\psi}}}(s,a):=r(s,a)$
$\displaystyle~{}~{}+\sum_{j=t+1}^{\infty}\mathbb{E}_{s^{\prime}\sim
p_{j}^{\pi},a^{\prime}\sim\pi(\cdot|s^{\prime})}\Big{[}\gamma^{j-t}r(s^{\prime},a^{\prime})-\alpha\log\pi_{\psi}(\cdot|s^{\prime})\Big{]}$

with $p_{t+1}^{\pi}:=p(\cdot|s,a)$, which satisfies the Bellman equation

$\displaystyle Q^{{\pi_{\psi}}}(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a),a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}[Q^{{\pi_{\psi}}}(s^{\prime},a^{\prime})].$

As the true value function is unknown to us, we approximate it by a
parameteric function $Q_{\theta}^{{\pi_{\psi}}}(\cdot,\cdot)$ which is for
instance a neural network, referred to as the critic. One incurs a Bellman
error when $\exists(s,a)\in\mathcal{S}\times\mathcal{A}$ such that
$Q_{\theta}^{\pi_{\psi}}(s,a)\neq Q^{\pi_{\psi}}(s,a)$, which can be
quantified for each observed tuple $x:=(s,a,r,s^{\prime})$ as

$\displaystyle
L_{B}(\theta;x)=\Big{(}\mathbb{E}_{a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}\Big{[}r+\gamma
Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})\Big{]}-Q_{\theta}^{\pi_{\psi}}(s,a)\Big{)}^{2}.$

The Bellman error of a sample set $\mathcal{D}=\\{x_{i}|i=1,\ldots,N\\}$,
called a replay buffer, can then be expressed as

$\displaystyle
L_{B}(\theta;\mathcal{D})=\frac{1}{N}\sum_{i=1}^{N}L_{B}(\theta;x_{i}).$

The soft actor-critic algorithm is trained by alternating between policy
evaluation $\arg\min_{\theta}L(\theta;\mathcal{D})$ which aims to minimize the
Bellman error and policy improvement

$\displaystyle\arg\max_{\psi}\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s_{i})}[Q_{\theta}^{\pi_{\psi}}(s_{i},a)-\log\pi_{\psi}(a|s_{i})]$

which builds on the heuristic of minimizing the Kullback-Leibler (KL)
divergence between the policy distribution and a Gibbs distribution derived
from the value predictor

$\displaystyle\arg\min_{\psi}D_{KL}\left(\pi_{\psi}(\cdot|s)\Bigg{|}\Bigg{|}\frac{\exp(Q_{\theta}^{\pi_{\psi}}(\cdot|s))}{\int\exp(Q_{\theta}^{\pi_{\psi}}(a^{\prime}|s)da^{\prime}}\right)$

where $D_{KL}(q(x)||p(x))=\mathbb{E}_{\theta\sim q}\left[\log q(x)-\log
p(x)\right]$ is the KL divergence for two measures $q(x)$ and $p(x)$.

#### The importance of accurate value estimation.

It is well known that using the same critic $Q_{\theta}^{\pi_{\psi}}$ for both
prediction and target estimation impairs performance, as a) the value of the
target state is likely to be overestimated (Haarnoja et al., 2017), b)
updating $\theta$ to reduce the Bellman error of a small group of states with
poor value estimations affects also the other states, many of which may
already have accurate value estimations. The latter phenomenon is called
catastrophic interference (Pritzel et al., 2017). The commonplace solutions to
mitigate these problems are two-fold and are typically used complementarily:

  * i)

Learning two critics concurrently $Q_{\theta_{1}}^{\psi}$ and
$Q_{\theta_{2}}^{\psi}$ and using
$\min(Q_{\theta_{1}}^{\psi}(s,a),Q_{\theta_{2}}^{\psi}(s,a))$ for all state-
action pair evaluations to reduce overestimation error.

  * ii)

Using copies of critics $Q_{\theta^{\prime}}^{\psi}$ for target evaluation
when calculating Bellman errors, whose parameters are updated with time lag
using Polyak averaging $\theta^{\prime}:=\tau\theta+(1-\tau)\theta^{\prime}$
where $\tau\in(0,1)$.

The standard Soft Actor-Critic (SAC) algorithm (Haarnoja et al., 2018) applies
both techniques at the same time. We demonstrate in this paper that more
accurate value estimations than the above two solutions can be obtained by
training a single critic with a loss function derived from learning-theoretic
first principles using the PAC Bayesian theory. We first recapitulate its
fundamental concepts briefly.

###  2.2 PAC Bayesian data analysis

Assume a prediction task from input an $x\in\mathcal{X}$ to an output
$y\in\mathcal{Y}$ with an unknown joint distribution $x,y\sim P$, the
performance of which is quantified by a bounded loss functional
$L(h(x),y):\mathcal{X}\times\mathcal{Y}\rightarrow[0,L_{max}]$, where $h$ is a
prediction hypothesis. A main concern of statistical learning theory is to
find the tightest possible bound for the risk functional

$\displaystyle R(h)=\mathbb{E}_{x,y\sim P}[L(h(x),y)]$ (2)

that holds with highest possible probability based on its empirical estimate

$\displaystyle R_{N}(h)=\frac{1}{N}\sum_{i=1}^{N}L(h(x_{i}),y_{i})$ (3)

for a sample set $\mathcal{D}=\\{(x_{i},y_{i})|i=1,\ldots,N)\\}$ consisting of
$N$ independent and identically distributed (i.i.d.) observations taken from
$P$. Bounds that satisfy these desiderata are referred to as Probably
Approximately Correct (PAC) (Kearns & Vazirani, 1994). They follow the
structure below

$\displaystyle Pr[R(h)\leq C(R_{N}(h),\delta)]\geq 1-\delta$ (4)

where $C(\delta)$ is an analytical expression dependent on the empirical
estimate $R_{N}$ and a tolerance level $\delta\in(0,1)$.

PAC Bayesian bounds (Shawe-Taylor & Williamson, 1997; McAllester, 1999) extend
the PAC framework to the case where the hypothesis is assumed to be a Gibbs
predictor that follows a distribution $h\sim q$, hence the corresponding risk
functional and its empirical estimate respectively are

$\displaystyle R(q)=\mathbb{E}_{h\sim q}[R(h)]\text{ and
}R_{N}(q)=\mathbb{E}_{h\sim q}[R_{N}(h)].$ (5)

The distribution $q$ is called the posterior, which should desirably be
similar to a prior distribution $p$ that represents domain knowledge or design
choices that are to be imposed to the learning process. Differently from
Bayesian inference, the relationship between the prior and the posterior
distributions does not necessarily follow the Bayes theorem in the PAC
Bayesian framework. It is sufficient that $p$ is decided before data
collection and $q$ is fit to data. A typical PAC Bayesian bound follows the
structure

$\displaystyle Pr[R(q)\leq C(R_{N}(q),\delta,D_{KL}(q||p))]\geq 1-\delta$ (6)

which is akin to Eq. 4 with the key difference that it makes a statement about
a distribution $q$ on the hypothesis space rather than a single hypothesis,
hence it involves a complexity penalty at the scale of distributions
$D_{KL}(q||p)$.

###  2.3 PAC-Bayesian soft policy evaluation

We define our risk functional as the soft Bellman error

$\displaystyle R(\theta;\psi):=\mathbb{E}_{s\sim
p_{\infty}^{\psi},a\sim\pi_{\psi}(\cdot|s),s^{\prime}\sim
p(\cdot|s,a),a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}$ (7)
$\displaystyle\quad\quad\Big{[}(r+\gamma
Q_{\theta}^{\psi}(s^{\prime},a^{\prime})-Q_{\theta}^{\psi}(s,a)-\log\pi_{\psi}(a^{\prime}|s^{\prime}))^{2}\Big{]}.$

where $p_{\infty}^{\psi}$ is the stationary distribution of the state
transition kernel $p(\cdot|s,a)$ under policy $\pi_{\psi}$ and its empirical
estimate

$\displaystyle R_{N}(\theta;\psi)=\frac{1}{N}$
$\displaystyle\sum_{i=1}^{N}\Big{(}r_{i}+\gamma\mathbb{E}_{a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime}_{i})}[Q_{\theta}^{\psi}(s^{\prime}_{i},a^{\prime})]$
$\displaystyle-
Q_{\theta}^{\psi}(s_{i},a_{i})-\log\pi_{\psi}(a^{\prime}|s^{\prime}_{i})\Big{)}^{2}$

for a replay buffer
$\mathcal{D}=\\{(s_{i},a_{i},r_{i},s^{\prime}_{i})|i=1,\ldots,N\\}$ comprising
a non-i.i.d. set of observations collected from the target control
environment. We choose the hypothesis space in a parameterized fashion as
$\mathcal{H}_{\psi}:=\\{Q_{\theta}^{\pi^{\psi}}|\theta\in\Theta\\}$. For a
chosen measure $q$ on $\Theta$, we attain the Gibbs risk functional and its
empirical estimate respectively

$\displaystyle R(q;\psi)=\mathbb{E}_{\theta\sim
q}[R(\theta;\psi)],~{}~{}~{}R_{N}(q;\psi)=\mathbb{E}_{\theta\sim
q}[R_{N}(\theta;\psi)].$

Let us introduce the soft Bellman backup operator with respect to a stochastic
policy with density function $\pi_{\psi}$ as

$\displaystyle T_{\pi^{\psi}}$ $\displaystyle
Q_{\theta}^{\pi^{\psi}}(s,a)=r(s,a)+$ (8)
$\displaystyle\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a),a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}[\gamma
Q_{\theta}^{\pi^{\psi}}(s^{\prime},a^{\prime})-\log\pi_{\psi}(\cdot|s^{\prime})].$

Then provably we have that

$\displaystyle(T_{\pi^{\psi}}Q_{\theta}^{\pi^{\psi}}(s,a)-$ $\displaystyle
Q_{\theta}^{\pi^{\psi}}(s,a))^{2}=0,\quad\quad\forall(s,a)$ $\displaystyle\iff
Q_{\theta}^{\pi^{\psi}}=Q^{\pi^{\psi}}$

which holds only under no approximation error and no estimation error, that is
a hypothesis space that contains $Q^{\pi^{\psi}}$, a consistent learning
algorithm, and infinite amount of data. Hence it is crucial for a
reinforcement learning algorithm to robustly handle a level of approximation
error. Our goal is to upper bound this error with high probability.

Defining $||.||_{p}^{2}$ as a squared weighted $L_{2}$ norm
$||A||_{p}^{2}=\int(A(s))^{2}dp(s)$ where $A(\cdot)$ is a function measurable
by $p$, we get

$\displaystyle\Big{|}\Big{|}Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}$
(9)
$\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\Big{|}\Big{|}\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)]\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}$

which characterizes an upper bound on the value approximation error in terms
of the Bellman error. See Lemma A.1 in Appendix for the proof. We can
construct a PAC-Bayesian bound by relating this inequality to the risk
functional:

$\displaystyle\Big{|}\Big{|}$ $\displaystyle
T_{\pi^{\psi}}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}$
(10) $\displaystyle=\mathbb{E}_{s\sim
p_{\infty}^{\psi},a\sim\pi_{\psi}(\cdot|s)}\Big{[}\Big{(}T_{\pi^{\psi}}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)\Big{)}^{2}~\Big{]}$
$\displaystyle=\mathbb{E}_{s\sim
p_{\infty}^{\psi},a\sim\pi_{\psi}(\cdot|s)}\Big{[}\Big{(}r(s,a)+\mathbb{E}_{s^{\prime},a^{\prime}}[\gamma
Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})$
$\displaystyle\qquad\qquad-\log\pi_{\psi}(a^{\prime}|s^{\prime})]-Q_{\theta}^{\pi_{\psi}}(s,a)\Big{)}^{2}~\Big{]}$
$\displaystyle=R(\theta;\psi)-\mathbb{E}_{s,a\sim
p_{\infty}^{\psi},\pi_{\psi}(\cdot|s)}\Big{[}r(s,a)+$
$\displaystyle\qquad\qquad\gamma\mathbb{V}_{s^{\prime}\sim
p(\cdot|s,a)}[\mathbb{E}_{a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}[Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})]]\Big{]}$

where $\mathbb{V}_{x\sim p(x)}[f(x)]$ denotes the variance of $f(x)$ dependent
on a random variable $x$ distributed as measure $p(x)$. For convenience, we
further compress the notation for mean and variance respectively as
$\mathbb{E}_{x\sim p(x)}[f(x)]:=\mathbb{E}_{x}[f(x)]$ and $\mathbb{V}_{x\sim
p(x)}[f(x)]:=\mathbb{V}_{x}[f(x)]$ when required. This construction allows us
to straightforwardly adapt the PAC Bayesian bound below developed by Fard et
al. (2012):

$\displaystyle Pr\Bigg{[}\mathbb{E}_{\theta\sim
q}\Big{|}\Big{|}T_{\pi_{\psi}}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}\leq\frac{1}{(1-\gamma)^{2}}$
(11)
$\displaystyle\times\Bigg{(}R_{N}(q;\psi)-\mathbb{E}_{\theta,s,a}\Big{[}r(s,a)+\gamma\mathbb{V}_{s^{\prime}}[\mathbb{E}_{a^{\prime}}[Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})]\Big{]}$
$\displaystyle+\sqrt{\frac{\log\Big{(}\frac{c_{2}N}{c_{1}(r_{max}+|r_{min}|)^{2}\delta}\Big{)}+D_{KL}(q(\theta)||p_{0}(\theta))}{\frac{N}{(r_{max}+|r_{min}|)^{2}c_{1}}-1}}\Bigg{)}\Bigg{]}$
$\displaystyle\geq 1-\delta$

for some prior measure $p_{0}$ defined on $\Theta$ and predetermined constants
$c_{1},c_{2}>0$.

###  2.4 The PAC4SAC algorithm

Assume a parametric family of measures defined on $\Theta$, i.e.
$\\{q(\theta;\phi)|\phi\in\Phi\\}$ for some parameter space $\Phi$. For
instance if $q$ is chosen to be normal distributed, then $\Phi$ is the set of
all possible mean and variance values it may take. The choice of coefficients
$c_{1},c_{2}$ would affect the outcome when the goal is to provide
quantitative performance guarantees. As our concern is to develop a training
objective for the critic, we simplify the bound while keeping it monotonic
with respect to its original form. Choosing $c_{1}=N/(r_{max}+|r_{min}|)^{2})$
and $c_{2}=1$ and neglecting the effect of $\log(\delta)$ in the numerator we
attain the loss below

$\displaystyle L_{PAC}(\phi):=$
$\displaystyle\underbrace{R_{N}(q;\phi)}_{\mathrm{\leavevmode\hbox
to9.6pt{\vbox to9.6pt{\pgfpicture\makeatletter\hbox{\hskip
4.80205pt\lower-4.80205pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.60205pt}{0.0pt}\pgfsys@curveto{4.60205pt}{2.54167pt}{2.54167pt}{4.60205pt}{0.0pt}{4.60205pt}\pgfsys@curveto{-2.54167pt}{4.60205pt}{-4.60205pt}{2.54167pt}{-4.60205pt}{0.0pt}\pgfsys@curveto{-4.60205pt}{-2.54167pt}{-2.54167pt}{-4.60205pt}{0.0pt}{-4.60205pt}\pgfsys@curveto{2.54167pt}{-4.60205pt}{4.60205pt}{-2.54167pt}{4.60205pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}Data~{}fit}}+\underbrace{\sqrt{\frac{D_{KL}(q(\theta;\phi)||p_{0}(\theta))}{N}}}_{\mathrm{\leavevmode\hbox
to9.6pt{\vbox to9.6pt{\pgfpicture\makeatletter\hbox{\hskip
4.80205pt\lower-4.80205pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.60205pt}{0.0pt}\pgfsys@curveto{4.60205pt}{2.54167pt}{2.54167pt}{4.60205pt}{0.0pt}{4.60205pt}\pgfsys@curveto{-2.54167pt}{4.60205pt}{-4.60205pt}{2.54167pt}{-4.60205pt}{0.0pt}\pgfsys@curveto{-4.60205pt}{-2.54167pt}{-2.54167pt}{-4.60205pt}{0.0pt}{-4.60205pt}\pgfsys@curveto{2.54167pt}{-4.60205pt}{4.60205pt}{-2.54167pt}{4.60205pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}Complexity~{}penalty}}$
(12)
$\displaystyle-\underbrace{\mathbb{E}_{\theta,s,a}\Big{[}r+\gamma\mathbb{V}_{s^{\prime}}\big{[}\mathbb{E}_{a^{\prime}}[Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})]\big{]}\Big{]}}_{\mathrm{\leavevmode\hbox
to9.6pt{\vbox to9.6pt{\pgfpicture\makeatletter\hbox{\hskip
4.80205pt\lower-4.80205pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.60205pt}{0.0pt}\pgfsys@curveto{4.60205pt}{2.54167pt}{2.54167pt}{4.60205pt}{0.0pt}{4.60205pt}\pgfsys@curveto{-2.54167pt}{4.60205pt}{-4.60205pt}{2.54167pt}{-4.60205pt}{0.0pt}\pgfsys@curveto{-4.60205pt}{-2.54167pt}{-2.54167pt}{-4.60205pt}{0.0pt}{-4.60205pt}\pgfsys@curveto{2.54167pt}{-4.60205pt}{4.60205pt}{-2.54167pt}{4.60205pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
The terms constituting this loss play complementary roles:

  * 1

$~{}\mathrm{Data~{}fit}$ minimizes the empirical risk by fitting the
parameters $\phi$ to values that best explain the observations in the replay
buffer $\mathcal{D}$.

  * 2

$\mathrm{Complexity~{}penalty}$ encourages predictors that are similar to the
ones generated by the prior $p_{0}$. This way the modeler can inject domain
knowledge or desiderata such as simplicity into the model as inductive bias.
Note that the effect of this term on learning shrinks as the agent collects
more observations, i.e. as $N$ grows. Hence the agent is geared mainly by
prior knowledge in the early episodes and by observations in the later ones.
While excluded in this work, the prior $p_{0}$ may be chosen as the posterior
of the previous episode to build a trust region based algorithm as in Peters
et al. (2010); Schulman et al. (2015, 2017). Put together, terms 1 and 2
minimize the structured risk (Vapnik, 1999).

  * 3

$\mathrm{Overestimation~{}correction}$ discounts a magnitude from the loss
proportional to the expected uncertainty of the value of the next state. This
way, the loss corrects a potential overestimation of the value of the current
state, which would otherwise require introducing double critics as in plain
SAC. Remarkably, this correction term appears in the loss as a natural
consequence of the derived PAC Bayes bound as opposed to the heuristics
developed in prior work such as introducing twin critics and operating with
the minimum of their estimations (Fujimoto et al., 2018; Van Hasselt et al.,
2016).

While exact calculation of the variance term is not tractable in the absence
of an accurate environment model, an empirical approximation to it can be
efficiently calculated from the minibatch
$\\{(s_{i},a_{i},r_{i},s^{\prime}_{i}|i=1,\ldots,M)\\}$ taken from the replay
buffer to calculate $R_{N}(q;\psi)$ as below

$\displaystyle\mathbb{E}_{s,a}[\mathbb{V}_{s^{\prime}}[\mathbb{E}_{a^{\prime}}[Q(s^{\prime},a^{\prime})]]]\approx\mathbb{V}_{s}[\mathbb{E}_{a}[Q(s,a)]]$
(13)
$\displaystyle\approx\frac{1}{M}\sum_{i=1}^{M}Q_{\widetilde{\theta}}^{\pi_{\psi}}(s_{i},a_{i})^{2}-\Bigg{(}\frac{1}{M}\sum_{i=1}^{M}Q_{\widetilde{\theta}}^{\pi_{\psi}}(s_{i},a_{i})\Bigg{)}^{2}$

where $\widetilde{\theta}$ is a reparameterized sample from $q(\theta;\phi)$.
Note that the terms $Q_{\widetilde{\theta}}^{\pi_{\psi}}(s_{i},a_{i})$ are
required also in the critic predictions computation of a vanilla SAC
implementation. It is possible to reuse the same samples for the expected
variance calculation, making its computational overhead negligible.
Furthermore, since the overestimation correction term appears in the loss
subtractively and variance is a positive quantity, multiplying it with any
regularization coefficient $\xi\in(0,1]$ would still upper bound the
generalization error. Hence it can be treated as a regularization parameter
the strength of which could be tuned.

#### Critic-guided random optimal action search.

Supplementing the probabilistic actor of SAC with a probabilistic critic has
interesting benefits while choosing actions at the time of real environment
interaction. When at state $s$, the agent can simply take an arbitrary number
of samples from the actor
$\widetilde{a}_{1},\ldots,\widetilde{a}_{R}\sim\pi(\cdot|s)$, take as many
samples from the critic parameter distribution
$\widetilde{\theta}_{1},\ldots,\widetilde{\theta}_{R}\sim q(\theta;\phi)$,
evaluate
$Q_{\widetilde{\theta}_{i}}^{\psi}(s,\widetilde{a}_{i}),~{}i=1,\ldots,R$ and
act $\widetilde{a}_{*}$ which gives the maximum
$Q_{\widetilde{\theta}_{*}}^{\psi}(s,\widetilde{a}_{*})$ value. It is possible
to view model-based multiple shooting as an approximate solution to the
Q-learning target
$Q_{\theta}^{\pi_{\psi}}(s^{\prime},\arg\max_{a^{\prime}}(s^{\prime},a^{\prime}))$
where the actor and critic co-operate to solve the inner $\arg\max$ problem by
guided random search. While a model-guided random search has widespread use in
the model-based reinforcement learning literature (Chua et al., 2018; Hafner
et al., 2019, 2020; Levine, 2013), it is a greatly overlooked opportunity in
the realm of model-free reinforcement learning. This is possibly due to the
commonplace adoption of deterministic critic networks, which are viewed as
being under the overestimation bias of the Jensen’s gap (Van Hasselt et al.,
2016). Hence their guidance at the time of action might have been though to
further increase the risk of over-exploitation. Our main finding is that when
trained with a loss function derived from learning-theoretic first principles,
a probabilistic critic network is both sufficient to stabilize training and
helpful for model-based random search of optimal action.

#### Convergence properties.

The single shooting version of PAC4SAC, i.e. $R=1$, satisfies the same
convergence conditions as given in Lemma 1, Lemma 2, and Theorem 1 of Haarnoja
et al. (2018), since the proofs apply to any value approximator
$Q_{\theta}^{\pi_{\psi}}$. For $R>1$, we essentially have a critic that
evaluates the policy

$\displaystyle a\sim$ $\displaystyle\pi_{\psi}^{R}(\cdot|s)$ (14)
$\displaystyle:=\arg\max_{a_{1},\ldots,a_{r}\sim\pi_{\psi}(\cdot|s)}\\{(a_{i},Q_{\theta}^{\pi_{\psi}}(s,a_{i}))|i=1,\ldots,R\\}$

but improves $\pi_{\psi}(\cdot|s)$ assuming $R=1$. We can show that
convergence still holds under such mismatch between policies assumed during
policy evaluation and improvement simply by redefining the soft Bellman backup
operator as

$\displaystyle T_{\pi_{\psi}^{R}}$ $\displaystyle
Q_{\theta}^{\psi}(s,a):=r(s,a)+$ (15) $\displaystyle\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a),a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}[\gamma
Q_{\theta}^{\pi_{\psi}^{R}}(s^{\prime},a^{\prime})-\log\pi_{\psi}(\cdot|s^{\prime})]$

highlighting the nuance that $Q_{\theta}$ is now under $\pi_{\psi}^{R}$,
although the current action is taken with $\pi_{\psi}$. Redefining also the
reward function as $r_{\pi}(s,a):=r(s,a)-\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a),a^{\prime}\sim\pi_{\psi}(\cdot|s^{\prime})}[\log\pi_{\psi}(\cdot|s^{\prime})]$,
the classical policy evaluation proof of Sutton & Barto (2018) also adopted in
Lemma 1 of Haarnoja et al. (2018) directly applies. Hence, when trained with
the loss in Eq. 12, $Q_{\theta}^{\pi_{\psi}^{R}}$ converges to
$Q^{\pi_{\psi}^{R}}$. Our random search algorithm also satisfies the policy
improvement theorem as stated below.

######  Theorem 2.1.

Let

$\displaystyle\psi_{new}:=\arg\min_{\psi}D_{KL}\left(\pi_{\psi}(\cdot|s)\Bigg{|}\Bigg{|}\frac{\exp(Q_{\theta}^{\pi_{\psi_{old}}^{R}}(\cdot|s))}{\int\exp(Q_{\theta}^{\pi_{\psi_{old}}^{R}}(a^{\prime}|s)da^{\prime}}\right)$

then $Q_{\theta}^{\pi_{\psi_{new}}^{R}}(s,a)\geq
Q_{\theta}^{\pi_{\psi_{old}}^{R}}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

We present the proof in Appendix A.2, which is a simple adaptation of Lemma 2
of Haarnoja et al. (2018) to the case that the optimizer $\psi_{new}$ improves
not only $Q_{\theta}^{\pi_{\psi_{new}}}(s,a)$ but also
$Q_{\theta}^{\pi_{\psi_{new}}^{R}}(s,a)$. Putting the result of this theorem
with the policy evaluation proof sketched above guarantees the convergence of
the PAC4SAC algorithm to an optimal policy following the identical
argumentation to Theorem 1 of Haarnoja et al. (2018).

Algorithm 1 The PAC4SAC algorithm

0: Polyak parameter $\tau\in(0,1)$, Learning rate $\eta>0$, Prior distribution
$p_{0}(\theta)$, Minibatch size $M>0$, Entropy coefficient $\alpha>0$,
Regularization coefficient $\xi>0$

1: $\mathcal{D}=\emptyset$ $\triangleright$ Initialize replay buffer

2: $s:=$ env.reset()

3: repeat

4:
$a:=\arg\max_{a_{1},\ldots,a_{r}\sim\pi_{\psi}(\cdot|s)}\\{(a_{i},Q_{\theta}^{\pi_{\psi}}(s,a_{i}))|i=1,\ldots,R\\}$
$\triangleright$ Critic-guided random action search

5: $(r,s^{\prime}):=$ env.step($a$) $\triangleright$ Take action

6: $\mathcal{D}:=\mathcal{D}\cup(s,a,r,s^{\prime})$ $\triangleright$ Store new
observation in replay buffer

7:
$\widetilde{\mathcal{D}}:=\\{(s_{i},a_{i},r_{i},s^{\prime}_{i},a^{\prime}_{i})~{}|~{}(s_{i},a_{i},r_{i},s^{\prime}_{i})\sim\mathcal{D},~{}~{}a^{\prime}_{i}\sim\pi_{\psi}(\cdot|s^{\prime})$,
$i=1,\ldots,M$} $\triangleright$ Sample batch and next actions

8: $\hat{q}_{i}\leftarrow r_{i}+\gamma
Q_{\widetilde{\theta}}^{\psi}(s^{\prime}_{i},\widetilde{a}^{\prime}_{i})-\alpha\log\pi_{\psi}(\widetilde{a}^{\prime}_{i}|s^{\prime}_{i}),\quad\widetilde{\theta}_{i}\sim
q(\theta;\phi^{\prime}),\quad\forall i=1,\ldots,M$ $\triangleright$ Calculate
soft Bellman targets

9: $q_{i}\leftarrow
Q_{\widetilde{\theta}_{i}}^{\psi}(s_{i},a_{i}),\quad\widetilde{\theta}_{i}\sim
q(\theta;\phi)\quad\forall i=1,\ldots,M$ $\triangleright$ Predict state-action
values

10:
$L_{PAC}(\phi)\leftarrow\frac{1}{M}\sum_{i=1}^{M}(q_{i}-\hat{q}_{i})^{2}+\sqrt{\frac{D_{KL}(q(\theta;\psi^{\prime})||p_{0}(\theta))}{|\mathcal{D}|}}-\gamma\xi(\frac{1}{M}\sum_{i=1}^{M}q_{i}^{2}-(\frac{1}{M}\sum_{i=1}^{M}q_{i})^{2}))$
$\triangleright$ Build critic loss

11: $\phi\leftarrow\phi-\eta\nabla_{\phi}L_{PAC}(\phi)$ $\triangleright$
Policy evaluation

12:
$\psi\leftarrow\psi+\eta\nabla_{\psi}\Big{(}\frac{1}{M}\sum_{i=1}^{M}Q_{\widetilde{\theta}_{i}}^{\psi}(s_{i},\widetilde{a}_{i})\Big{)},\quad\widetilde{a}_{i}\sim\pi_{\psi}(\cdot|s_{i}),\quad\widetilde{\theta}_{i}\sim
q(\theta;\phi),\forall i=1,\ldots,M$ $\triangleright$ Policy improvement

13: $\phi^{\prime}\leftarrow\tau\phi+(1-\tau)\phi^{\prime}$ $\triangleright$
Target critic update

14: $s:=s^{\prime}$ $\triangleright$ Jump to next state

15: until convergence

##  3 Prior Art

#### Actor-critic algorithms.

The Deep Deterministic Policy Gradient (DDPG) algorithm (Lillicrap et al.,
2016) is among the pioneer work to adapt actor-critic algorithms to deep
learning. The algorithm trains a critic to minimize the Bellmann error and a
deterministic actor to maximize the critic, following a simplified case of the
policy gradient theorem. The Twin Delayed Deep Deterministic Policy Gradient
(TD3) algorithm (Fujimoto et al., 2018) improves the robustness of DDPG by
adopting twin critic networks backed up by Polyak averaging updated target
copies. Trust region algorithms such as Relative Entropy Policy Search (REPS)
(Peters et al., 2010), Trust Region Policy Optimization (TRPO) (Schulman et
al., 2015), and Proximal Policy Optimization (PPO) (Schulman et al., 2017) aim
to explore while guaranteeing monotonic expected return improvement and
maintaining training stability by restricting the policy updates via a KL
divergence penalty between the policy densities before and after a parameter
update.

#### Maximum entropy reinforcement learning.

Incorporation of the entropy of the policy distribution into the learning
objective finds its roots in inverse reinforcement learning (Ziebart et al.,
2008), which maintained its use also in modern deep inverse reinforcement
learning applications Wulfmeier et al. (2015). The soft Q-learning algorithm
(Haarnoja et al., 2017) uses the same idea to improve exploration in forward
reinforcement learning. Soft actor-critic (SAC) (Haarnoja et al., 2018)
extends the applicability of the framework to the off-policy setup by also
significantly improving its stability and efficiency thanks to an actor
training scheme provably consistent with a maximum entropy trained critic
network.

#### PAC Bayesian learning.

Introduced conceptually by Shawe-Taylor & Williamson (1997), PAC Bayesian
analysis has been used by McAllester (1999, 2003) for stochastic model
selection and its tightness has been improved by Seeger (2002) with
application to Gaussian Processes (GPs). The use of PAC Bayesian bounds to
training models while maintaining performance guarantees has raised attention
since the pioneer work of Dziugaite & Roy (2017). Reeb et al. (2018) show how
PAC Bayesian learning can be extended also to hyperparameter tuning. The first
work to develop a PAC Bayesian bound for reinforcement learning is Fard &
Pineau (2010). This bound has later on been extended by the same authors to
continuous state spaces Fard et al. (2012). PAC Bayesian bounds start to be
used in classical control problems for policy search (Veer & Majumdar, 2021),
as well as for knowledge transfer (Majumdar, 2018; Farid & Majumdar, 2021).
There is no prior work using PAC Bayesian bounds for policy evaluation as part
of an actor-critic algorithm.

Figure 2: The effect of critic-guided random optimal action search on the
performance of our PAC4SAC algorithm demonstrated on the cartpole environment.
The model learns faster by taking more actor samples (top), while stably
reaching the maximum asymptotic performance (bottom).

| Pendulum | Cartpole Swingup |  | Inverted Double
---
Pendulum
Half Cheetah | Ant | Humanoid
| $(d_{s}=3,d_{a}=1)$ | $(d_{s}=5,d_{a}=1)$ | $(d_{s}11,d_{a}=1)$ | $(d_{s}=17,d_{a}=6)$ | $(d_{s}=111,d_{a}=11)$ | $(d_{s}=376,d_{a}=17)$
Num training steps | 10k | 30k | 40k | 100k | 300k | 500k
Area Under Episode Reward Curve ($\uparrow$)
PPO | $-1036.5\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>25.0$ | $-17.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>82.4$ | $379.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>44.4$ | $634.1\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>50.1$ | $811.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>85.3$ | $1730.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>38.3$
DDPG | $-664.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>47.9$ | $577.3\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>19.5$ | $551.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>25.1$ | $374.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>104.5$ | $1946.5\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>60.3$ | $1683.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>15.4$
SAC | $\bf-539.8\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>11.9$ | $571.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>11.2$ | $750.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>41.1$ | $947.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>61.1$ | $1970.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>10.6$ | $2405.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>32.9$
PAC4SAC (Ours) | $-553.7\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>14.6$ | $\bf 582.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>13.7$ | $\bf 831.4\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>30.6$ | $\bf 1052.3\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>25.2$ | $\bf 2131.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>20.3$ | $\bf 2422.5\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>67.5$
Highest Episode Reward ($\uparrow$)
PPO | $-652.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>83.6$ | $477.3\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>80.6$ | $2321.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>483.8$ | $1421.8\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>54.6$ | $1645.4\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>216.3$ | $2136.5\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>90.7$
DDPG | $-178.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>21.9$ | $847.1\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>22.3$ | $1670.4\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>96.6$ | $756.8\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>156.7$ | $2827.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>99.5$ | $2306.8\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>91.0$
SAC | $-146.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>12.3$ | $875.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>6.4$ | $6191.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>749.7$ | $1565.4\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>32.3$ | $2606.4\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>29.6$ | $3451.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>45.4$
PAC4SAC (Ours) | $\bf-111.7\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>9.9$ | $\bf 886.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>2.4$ | $\bf 6926.3\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>639.8$ | $\bf 1656.7\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>37.4$ | $\bf 2860.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>39.8$ | $\bf 3572.6\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>90.8$

Figure 3: Learning curves of our PAC4SAC and the baselines (top) and their
statistics (bottom). Our PAC4SAC improves the state of the art in both sample
efficiency as visible from the area under episode reward curve scores and
asymptotic performance as visible from the highest rewards. Its consistent
improvement over SAC demonstrates the effect of PAC Bayesian critic training
on performance.

##  4 Experiments

With experiments, we aim to demonstrate that

  * a)

Training a single probabilistic critic with a loss function derived from a PAC
Bayesian bound is sufficient for, and even superior to training double
critics,

  * b)

Using a probabilistic critic also for random optimal action search brings an
additional performance boost.

We evaluate the performance of an online trained agent with respect to its
Area Under Curve (AUC) of per-episode rewards as a measure of learning speed
and the highest per-episode reward as a measure of asymptotic performance. We
report experiments in six continuous state and action space environments with
varying levels of difficulty: pendulum, cartpole swingup, inverted double
pendulum, half cheetah, ant, and humanoid. We use the PyBullet physics engine
(Coumans & Bai, 2016–2019) under the OpenAI Gym environment (Brockman et al.,
2016) with PyBullet Gymperium library (Ellenberger, 2018–2019). Our method can
essentially be extended to any actor-critic algorithm, yet we choose
SAC(Haarnoja et al., 2018) as our base algorithm due to its wide reception as
the state of the art, hence take it as our main benchmarking target. We
compare also against Proximal Policy Optimization (PPO) (Schulman et al.,
2017) and Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2016)
as representatives of alternative actor-critic designs for deep reinforcement
learning.

We train all algorithms with step counts proportional to the state and action
space dimensionalities of environments: $10000$ for pendulum, $30000$ for
cartpole swingup, $40000$ for inverted double pendulum, $100000$ for half
cheetah, $300000$ for ant, and $500000$ for humanoid. Having observed no
significant improvement afterwards in preliminary trials, we truncate training
at these step counts to keep the AUC scores more interpretable. We repeat
pendulum, cartpole swingup, inverted double pendulum, and half cheetah
experiments $10$ times, whereas the larger ant and humanoid environments $5$
times. We take $500$ action samples for PAC4SAC in all experiments unless
stated otherwise. We give further details of the experiments in Appendix A.1.

#### Ablation Study.

We quantify the effect of individual loss terms on the performance by an
ablation study in the cartpole environment reported in Table 1. When used
alone, the data fit term learns faster but limits the asymptotic performance.
All three terms are required for the best asymptotic performance. We also
observe in Figure 2 that PAC4SAC learns faster and reaches higher episode
rewards with increased sample size.

|  | Data
---
Fit
1
| Complexity
---
Penalty
2
| Overestimation
---
Correction
3
| Area Under
---
Episode Reward
Curve
| Highest
---
Episode
Reward
PAC4SAC | $\checkmark$ | $\times$ | $\times$ | $\bf 592.5\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>24.3$ | $860.9\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>18.4$
$\checkmark$ | $\checkmark$ | $\times$ | $584.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>24.9$ | $841.7\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>32.2$
$\checkmark$ | $\checkmark$ | $\checkmark$ | $582.2\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>13.7$ | $\bf 886.0\pm\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>2.4$

Table 1: The effects of the critic training loss terms on performance. In the
absence of regularizers, the data fit term learns fastest, however saturates
prematurely. The complexity penalty term makes early saturation even more
pronounced. The highest asymptotic performance is reached when all three loss
terms are used together.

#### Computational Cost.

We measure the average wall clock time of 1000 steps in cartpole environment
with 20 repetitions to be
$11.95\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>0.08$ seconds for PPO,
$8.02\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>0.07$ seconds for DDPG,
$12.70\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>0.05$ seconds for SAC, and
$12.18\color[rgb]{0.2,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,0.2}\pgfsys@color@gray@stroke{0.2}\pgfsys@color<EMAIL_ADDRESS>0.05$ seconds for PAC4SAC with an Intel(R) Xeon(R) CPU E5-2650 machine. Our
PAC4SAC has comparable compute time to its counterparts.

#### Main results.

Figure 3 demonstrates a consistent performance improvement in favor of our
PAC4SAC in all six environments in terms of both learning speed and asymptotic
performance with the only exception of the AUC score in the pendulum
environment. We attribute this to the simplicity of the control problem,
making policy evaluation error less decisive. The improvement of PAC4SAC
especially over SAC gets more pronounced as the state and action
dimensionalities of the environments increase.

##  5 Discussion and Broader Impact

Our results demonstrate strong evidence in favor of the benefits of using the
PAC Bayesian theory as a guideline for deriving loss functions for critic
training. The tightness of the PAC Bayesian bound we used deserves dedicated
investigation. Following Fard et al. (2012), we adopt one specific PAC
Bayesian bound derived by Boucheron et al. (2005) due to its convenience for
use in the Markov process setting. There may however be alternative approaches
to bound the expectation of a Markov chain more tightly. Such theoretical
considerations are topics for follow-up work. The sample efficiency
improvement attained thanks to a PAC Bayes trained critic may be amplified
even further by extending our findings to model-based and multi-step
bootstrapping setups.

The strong empirical results of this work encourages exploration of venues
beyond reinforcement learning, where the PAC Bayesian theory may be useful for
training loss design. For instance, diffusion models (Berry & Berry, 2018) may
derive PAC Bayesian loss functions to improve the notoriously unstable
training schemes of deep generative models by semi-informative priors.

## References

  * Alquier (2021) Alquier, P.  User-friendly introduction to PAC-Bayes bounds.  _arXiv preprint arXiv:2110.11216_ , 2021.
  * Berry & Berry (2018) Berry, F. and Berry, W.  Innovation and diffusion models in policy research.  _Theories of the policy process_ , 2018.
  * Bertsekas & Tsitsiklis (1996) Bertsekas, D. and Tsitsiklis, J.  _Neuro-dynamic programming_.  1996\.
  * Boucheron et al. (2005) Boucheron, S., Bousquet, O., and Lugosi, G.  Theory of classification: A survey of some recent advances.  _ESAIM_ , 2005.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  OpenAI Gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Chua et al. (2018) Chua, K., Calandra, R., McAllister, R., and Levine, S.  Deep reinforcement learning in a handful of trials using probabilistic dynamics models.  _NeurIPS_ , 2018.
  * Coumans & Bai (2016–2019) Coumans, E. and Bai, Y.  PyBullet: a Python module for physics simulation for games, robotics and machine learning.  http://pybullet.org, 2016–2019.
  * Dziugaite & Roy (2017) Dziugaite, G. and Roy, D.  Computing non-vacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  In _UAI_ , 2017.
  * Ellenberger (2018–2019) Ellenberger, B.  PyBullet Gymperium.  https://github.com/benelot/pybullet-gym, 2018–2019.
  * Fard & Pineau (2010) Fard, M. and Pineau, J.  PAC-Bayesian model selection for reinforcement learning.  _NeurIPS_ , 2010.
  * Fard et al. (2012) Fard, M., Pineau, J., and Szepesvári, C.  PAC-Bayesian policy evaluation for reinforcement learning.  In _AISTATS_ , 2012.
  * Farid & Majumdar (2021) Farid, A. and Majumdar, A.  Generalization bounds for meta-learning via PAC-Bayes and uniform stability.  _NeurIPS_ , 2021.
  * Fujimoto et al. (2018) Fujimoto, S., Hoof, H., and Meger, D.  Addressing function approximation error in actor-critic methods.  In _ICML_ , 2018.
  * Haarnoja et al. (2017) Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement learning with deep energy-based policies.  In _ICML_ , 2017.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft Actor-Critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _ICML_ , 2018.
  * Hafner et al. (2019) Hafner, D., Lillicrap, T., Fischer, I., Villegas, R., Ha, D., Lee, H., and Davidson, J.  Learning latent dynamics for planning from pixels.  In _ICML_ , 2019.
  * Hafner et al. (2020) Hafner, D., Lillicrap, T., Ba, J., and Norouzi, M.  Dream to control: Learning behaviors by latent imagination.  In _ICLR_ , 2020.
  * Haußmann et al. (2021) Haußmann, M., Gerwinn, S., Look, A., Rakitsch, B., and Kandemir, M.  Learning partially known stochastic dynamics with empirical PAC Bayes.  In _AISTATS_ , 2021.
  * Kearns & Vazirani (1994) Kearns, M. and Vazirani, U.  _An introduction to computational learning theory_.  MIT press, 1994.
  * Kingma & Ba (2015) Kingma, D. and Ba, J.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Levine (2013) Levine, S.and Koltun, V.  Guided policy search.  In _ICML_ , 2013.
  * Lillicrap et al. (2016) Lillicrap, T., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  In _ICLR_ , 2016.
  * Majumdar (2018) Majumdar, A.and Goldstein, M.  PAC-Bayes Control: Synthesizing controllers that provably generalize to novel environments.  In _CoRL_ , 2018.
  * McAllester (1999) McAllester, D.  PAC-Bayesian model averaging.  In _COLT_ , 1999.
  * McAllester (2003) McAllester, D.  PAC-Bayesian stochastic model selection.  _Machine Learning_ , 2003.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _NeurIPS_. 2019.
  * Peters et al. (2010) Peters, J., Mulling, K., and Altun, Y.  Relative entropy policy search.  In _AAAI_ , 2010.
  * Pritzel et al. (2017) Pritzel, A., Uria, B., Srinivasan, S., Badia, A., Vinyals, O., Hassabis, D., Wierstra, D., and Blundell, C.  Neural episodic control.  In _ICML_ , 2017.
  * Reeb et al. (2018) Reeb, D., Doerr, A., Gerwinn, S., and Rakitsch, B.  Learning Gaussian processes by minimizing PAC-Bayesian generalization bounds.  _NeurIPS_ , 2018.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _ICML_ , 2015.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Seeger (2002) Seeger, M.  PAC-Bayesian generalisation error bounds for Gaussian process classification.  _Journal of Machine Learning Research_ , 2002.
  * Shawe-Taylor & Williamson (1997) Shawe-Taylor, J. and Williamson, R.  A PAC analysis of Bayesian estimator.  In _COLT_ , 1997.
  * Sutton & Barto (2018) Sutton, R. and Barto, A.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Van Hasselt et al. (2016) Van Hasselt, H., Guez, A., and Silver, D.  Deep reinforcement learning with double q-learning.  In _AAAI_ , 2016.
  * Vapnik (1999) Vapnik, V.  _The nature of statistical learning theory_.  Springer science & business media, 1999.
  * Veer & Majumdar (2021) Veer, S. and Majumdar, A.  Probably approximately correct vision-based planning using motion primitives.  In _CoRL_ , 2021.
  * Wulfmeier et al. (2015) Wulfmeier, M., Ondruska, P., and Posner, I.  Maximum entropy deep inverse reinforcement learning.  _arXiv preprint arXiv:1507.04888_ , 2015.
  * Ziebart et al. (2008) Ziebart, B., Maas, A., Bagnell, J., Dey, A., et al.  Maximum entropy inverse reinforcement learning.  In _AAAI_ , 2008.

##  Appendix A Appendix

######  Lemma A.1.

For the squared weighted $L_{2}$ norm and Bellman operator defined as

$\displaystyle T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)=r+\mathbb{E}[\gamma
Q_{\theta}^{\pi_{\psi}}(s^{\prime},a^{\prime})-\log\pi_{\psi}(\cdot|s^{\prime})]$
(16)

value approximation error is bounded as below:

$\displaystyle\Big{|}\Big{|}$ $\displaystyle
Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}\leq\frac{1}{(1-\gamma)^{2}}\Big{|}\Big{|}\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)]\Big{|}\Big{|}_{p_{\infty}^{\psi},\pi_{\psi}}^{2}$

###### Proof.

Given the contraction inequality (Bertsekas & Tsitsiklis, 1996)

$\displaystyle||[T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)]||_{p_{\infty}^{\psi},\pi_{\psi}}$
$\displaystyle\leq\gamma||Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}$

we have that

$\displaystyle||Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}=||Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)+T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}$
$\displaystyle\leq||Q_{\theta}^{\pi_{\psi}}(s,a)-T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}+||T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}\qquad\qquad$
$\displaystyle\leq||Q_{\theta}^{\pi_{\psi}}(s,a)-T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}+\gamma||Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}.$

Arranging the terms we get

$\displaystyle||Q_{\theta}^{\pi_{\psi}}(s,a)-Q^{\pi_{\psi}}(s,a)||_{p_{\infty}^{\psi},\pi_{\psi}}\leq\frac{1}{1-\gamma}||[T_{\psi}Q_{\theta}^{\pi_{\psi}}(s,a)-Q_{\theta}^{\pi_{\psi}}(s,a)]||_{p_{\infty}^{\psi},\pi_{\psi}}.$

Taking the square of both sides gives the desired result. ∎

######  Theorem A.2.

Let

$\displaystyle\psi_{new}:=\arg\min_{\psi}D_{KL}\left(\pi_{\psi}(\cdot|s)\Bigg{|}\Bigg{|}\frac{\exp(Q^{\pi_{\psi_{old}}^{R}}(\cdot|s))}{\int\exp(Q^{\pi_{\psi_{old}}^{R}}(a^{\prime}|s)da^{\prime}}\right)$

then $Q^{\pi_{\psi_{new}}^{R}}(s,a)\geq
Q^{\pi_{\psi_{old}}^{R}}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

###### Proof.

Denote
$V^{\pi_{\psi}^{R}}(s)=\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[Q^{\pi_{\psi}^{R}}(s,a)-\log\pi_{\psi}(a|s)]$
and the optimization objective

$\displaystyle J(\psi)$
$\displaystyle:=D_{KL}\left(\pi_{\psi}(\cdot|s)\Bigg{|}\Bigg{|}\frac{\exp(Q^{\pi_{\psi_{old}}^{R}}(\cdot|s))}{\int\exp(Q^{\pi_{\psi_{old}}^{R}}(a^{\prime}|s)da^{\prime}}\right)$
$\displaystyle=\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[\log\pi_{\psi}(a|s)-Q^{\pi_{\psi_{old}}^{R}}(s,a)]+\mathrm{const}.$

Since $J(\psi_{new})\leq J(\psi_{old})$, we have

$\displaystyle\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[Q^{\pi_{\psi_{old}}^{R}}(s,a)-\log\pi_{new}(a|s)]$
$\displaystyle\geq\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[Q^{\pi_{\psi_{old}}^{R}}(s,a)-\log\pi_{old}(a|s)]$
$\displaystyle=V^{\pi_{\psi_{old}}^{R}}(s).$

Policy improvement theorem (Sutton & Barto, 2018) states that
$Q^{\pi}(s,\pi^{\prime}(s))\geq V_{\pi}(s),\forall s\in\mathcal{S}\Rightarrow
V_{\pi^{\prime}}(s)\geq V_{\pi}(s),\forall s\in\mathcal{S}$ holds for any
state-action value function $Q^{\pi}(s,\pi(s))$, the corresponding state value
function $V_{\pi}(s)$ and any pair of policies $\pi$ and $\pi^{\prime}$.
Choosing $\pi^{\prime}:=\pi_{\psi_{new}}$, $\pi:=\pi_{\psi_{old}}^{R}$,
$V_{\pi}=V^{\pi_{\psi_{old}^{R}}}$, and
$Q^{\pi}(s,\pi(s)):=\mathbb{E}_{a\sim\pi_{\psi}(\cdot|s)}[Q^{\pi_{\psi_{old}}^{R}}(s,a)-\log\pi_{new}(a|s)]$,
we get $V^{\pi_{\psi_{new}}}(s)\geq V^{\pi_{\psi_{old}^{R}}}(s)$. What remains
only is to show that taking $R$ samples from $\pi_{\psi_{new}}$ improves its
value

$\displaystyle V^{\pi_{\psi_{old}^{R}}}(s)\leq V^{\pi_{\psi_{new}}}(s)\leq
V^{\pi_{\psi_{new}^{R}}}(s)=Q^{\pi_{\psi_{new}}}\left(s,\arg\max_{a_{1},\ldots,a_{r}\sim\pi_{\psi_{new}}(\cdot|s)}\\{(a_{i},Q^{\pi_{\psi_{new}}}(s,a_{i}))|i=1,\ldots,R\\}\right).$

∎

###  A.1 Experimental details

We implement all experiments with PyTorch (Paszke et al., 2019) version
$1.13.1$.

#### Environments.

For experiments, we use PyBullet Gymperium library except for only pendulum
which is from OpenAI Gym library. The environment names that we use are:
Pendulum-v1 for Pendulum, InvertedPendulumSwingupPyBulletEnv-v0 for Cartpole
Swingup, InvertedDoublePendulumMuJoCoEnv-v0 for Inverted Double Pendulum,
HalfCheetahMuJoCoEnv-v0 for Half Cheetah, AntMuJoCoEnv-v0 for Ant, and
HumanoidMuJoCoEnv-v0 for Humanoid.

#### Hyper-parameters.

We use Adam optimizer (Kingma & Ba, 2015) with a learning rate of $0.001$ for
all architectures. We set the length of experience replay as $25000$ and batch
size as $32$. For PAC4SAC we set the regularization parameter to $\xi=0.01$.

#### Architectures.

We use the same architecture for all the environments. There are two main
architectures which are actor and critic and we provide the details of the
architectures in Table 2.

Actor |  | Critic
---|---|---
| PPO
---
SAC
PAC4SAC
DDPG |  | PPO
---
SAC
DDPG
PAC4SAC
| Linear($d_{s}$, 256)
---
LayerNorm(256)
Silu()
| Linear($d_{s}$ \+ $d_{a}$, 256)
---
LayerNorm(256)
Silu()
| Linear(256, 256)
---
LayerNorm(256)
Silu()
| Linear(256, 256)
---
LayerNorm(256)
Silu()
| Linear(256, 256)
---
LayerNorm(256)
Silu()
| Linear(256, 256)
---
LayerNorm(256)
Silu()
| Linear(256, 2$\times d_{a}$, $\theta$)
---
Linear(256, $d_{a}$) | Linear(256, 1) | GaussLinear(256, 1)
SquashedGaussian(2$\times d_{a}$, $d_{a}$) | Tanh() |  |

Table 2: Architecture details based on environments. The SquashedGaussian
module implements a Gaussian head that uses the first $d_{a}$ of its inputs as
the mean and the second $d_{a}$ as the variance of a heteroscedastic normal
distribution. The GaussLinear module implements a fully connected layer with
weights that follow independent normal distributions.