# The Definitive Guide to Policy Gradients in Deep Reinforcement Learning:
Theory, Algorithms and Implementations

Matthias Lehmann
University of Cologne

###### Abstract

In recent years, various powerful policy gradient algorithms have been
proposed in deep reinforcement learning. While all these algorithms build on
the Policy Gradient Theorem, the specific design choices differ significantly
across algorithms. We provide a holistic overview of on-policy policy gradient
algorithms to facilitate the understanding of both their theoretical
foundations and their practical implementations. In this overview, we include
a detailed proof of the continuous version of the Policy Gradient Theorem,
convergence results and a comprehensive discussion of practical algorithms. We
compare the most prominent algorithms on continuous control environments and
provide insights on the benefits of regularization. All code is available at
https://github.com/Matt00n/PolicyGradientsJax.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Reinforcement Learning
      1. 2.2.1 Problem Setting
      2. 2.2.2 Value Functions
      3. 2.2.3 On-Policy Policy Gradient Methods
    3. 2.3 Deep Learning
  3. 3 Theoretical Foundations of Policy Gradients
    1. 3.1 Policy Gradient Theorem
    2. 3.2 Value Function Estimation with Baselines
    3. 3.3 Importance Sampling
  4. 4 Policy Gradient Algorithms
    1. 4.1 REINFORCE
    2. 4.2 A3C
    3. 4.3 TRPO
    4. 4.4 PPO
    5. 4.5 V-MPO
    6. 4.6 Comparing Design Choices in Policy Gradient Algorithms
  5. 5 Convergence Results
    1. 5.1 Literature Overview
    2. 5.2 Mirror Learning
      1. 5.2.1 Fundamentals of Mirror Learning
      2. 5.2.2 Policy Gradient Algorithms as Instances of Mirror Learning
      3. 5.2.3 Convergence Proof
  6. 6 Numerical Experiments
  7. 7 Conclusion
  8. A Hyperparameters
  9. B Extended Experiments
    1. B.1 Comparison to RL frameworks
    2. B.2 Entropy Bonus in A2C
    3. B.3 A2C and REINFORCE with Multiple Update Epochs
  10. C V-MPO: Derivation Details
  11. D Auxiliary Theory

##  1 Introduction

Reinforcement Learning (RL) is a powerful set of methods for an agent to learn
how to act optimally in a given environment to maximize some reward signal. In
contrast to other methods such as dynamic programming, RL achieves this task
of learning an optimal policy, which dictates the optimal behavior, via a
trial-and-error process of interacting with the environment [75]. Most early
successful applications of RL use value-based methods (e.g., [84, 79, 55]),
which estimate the expected future rewards to inform the agent’s decisions.
However, these methods only indirectly optimize the true objective of learning
an optimal policy [82] and are non-trivial to apply in settings with
continuous action spaces [75].

In this work, we discuss policy gradient algorithms [75] as an alternative
approach, which aims to directly learn an optimal policy. Policy gradient
algorithms are by no means new [7, 78, 87, 88], but this subfield only gained
traction in recent years following the emergence of deep RL [55] with the
development of various powerful algorithms (e.g., [54, 71, 73]). Deep RL is a
subfield of RL, which uses neural networks and other deep learning methods.
The increased interest in policy gradient algorithms is due to several
appealing properties of this class of algorithms. They can be used natively in
continuous action spaces without compromising the applicability to discrete
spaces [77]. In contrast to value-based methods, policy gradient algorithms
inherently learn stochastic policies, which results in smoother search spaces
and partly remedies the exploration problem of having to acquire knowledge
about the environment in order to optimize the policy [75, 77]. In some
settings, the optimal policy may also be stochastic itself [75]. Lastly,
policy gradient methods enable smoother changes in the policy during the
learning process, which may result in better convergence properties [77].

Our goal is to present a holistic overview of policy gradient algorithms. In
doing so, we limit the scope to on-policy algorithms, which we will define in
Section 2. Thus, we exclude some popular algorithms including DDPG [50], TD3
[24] and SAC [28]. See Figure 1 for an overview of RL and the subfields we
cover. Our contributions are as follows:

  * •

We give a comprehensive introduction to the theoretical foundations of policy
gradient algorithms including a detailed proof of the continuous version of
the Policy Gradient Theorem.

  * •

We derive and compare the most prominent policy gradient algorithms and
provide high quality pseudocode to facilitate understanding.

  * •

We release competitive implementations of these algorithms, including the, to
the best of our knowledge, first publicly available V-MPO implementation
displaying performance on par with the results in the original paper.

RL AlgorithmsModel-Free RLPolicy Gradient AlgorithmsOn-Policy
AlgorithmsREINFORCEA3C / A2CTRPOPPOV-MPO$\ldots$Off-Policy
AlgorithmsDDPGSAC$\ldots$Value-Based AlgorithmsDQNSARSA$\ldots$Model-Based
RLDyna-QMuZero$\ldots$ Figure 1: Simplified taxonomy of RL algorithms.
Subfields of RL we focus on are highlighted in gray.

The remainder of this paper is organized as follows. Section 2 introduces
fundamental definitions in RL as well as an overview of deep learning. Section
3 derives the theoretical foundations of policy gradient algorithms with a
special focus on proving the Policy Gradient Theorem, based on which we will
construct several existing practical algorithms in Section 4. In Section 5, we
discuss convergence results from literature. Section 6, presents the results
of our numerical experiments comparing the discussed algorithms. Section 7
concludes.

##  2 Preliminaries

In this section, we present prerequisites for subsequent chapters.
Specifically, we introduce our notation in Section 2.1 and present overviews
of RL in Section 2.2 and of deep learning in Section 2.3. Furthermore, we list
several well-known definitions and results from probability theory, measure
theory and analysis, which we use in our paper, in Appendix Appendix D.

###  2.1 Notation

We denote the set of natural numbers by $\mathbb{N}$, natural numbers
including zero by $\mathbb{N}_{0}$, real numbers by $\mathbb{R}$ and positive
real numbers by $\mathbb{R}_{+}$. We denote $d$-dimensional real-numbered
vector spaces as $\mathbb{R}^{d}$. By $\mathcal{P}(\mathcal{A})$, we denote
the power set of a set $\mathcal{A}$. Where possible, we denote random
variables with capital letters and their realizations with the corresponding
lower case letters. For any probability measure $\mathbb{P}$, we denote the
probability of an event $X=x$ as $\mathbb{P}(X=x)$. Similarly, we write
$\mathbb{P}(X=x\mid Y=y)$ for conditional probabilities. When it is clear,
which random variable is referred to, we regularly omit it to shorten
notation, i.e. $\mathbb{P}(X=x)=\mathbb{P}(x)$. We identify measurable spaces
$(\mathcal{A},\Sigma)$ just by the set $\mathcal{A}$ as we always use the
respective power set $\mathcal{P}(\mathcal{A})$ for discrete sets and the
Borel algebra for intervals in $\mathbb{R}^{d}$ as the respective
$\sigma$-algebra $\Sigma$. We express most Lebesgue integrals w.r.t. the
Lebesgue measure $\lambda$ using Theorem D.9. To simplify notation, we write
integrals for measurable functions $f$ on $\mathcal{A}$ as
$\int_{a\in\mathcal{A}}f(a)\>da\coloneqq\int_{a\in\mathcal{A}}f(a)\>d\lambda(a)$.
We denote that a random variable $X$ follows a probability distribution $p$ by
$X\sim p$. For any random variable $X\sim p$, we denote by $\mathbb{E}_{X\sim
p}[X]$ and $\mathrm{Var}_{X\sim p}[X]$ its expectation and variance. We denote
the set of probability distributions over some measurable space $\mathcal{A}$
as $\Delta(\mathcal{A})$. We write $\lvert\mathcal{A}\rvert$ for the
cardinality of a finite set $\mathcal{A}$ or area of a region
$\int_{a\in\mathcal{A}}da$. For any variable or function $x$, we commonly
denote approximations to it by $\hat{x}$.

###  2.2 Reinforcement Learning

In the following, we formally describe the general problem setting encountered
in RL, define fundamental functions and introduce the subfields of RL our work
is further concerned with. Sections 2.2.1 and 2.2.2 are based on [75], Chapter
3.

####  2.2.1 Problem Setting

Each problem instance in RL consists of an agent and an environment with which
he interacts to achieve some specific goal. The environment comprises
everything external to the agent and can be formalized as a Markov Decision
Process (MDP). Let an action space $\mathcal{A}$ be the set of all actions the
agent can take and let a state space $\mathcal{S}$ be the set of all possible
states, i.e. snapshots of the environment at any given point in time. State
and action spaces can be discrete or continuous111Here, we call a state/action
space continuous if it is an interval in $\mathbb{R}^{d}$ for
$d\in\mathbb{N}$. and we assume both to be compact and measurable. We write an
MDP as a tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},P,\gamma,p_{0})$, where
$P\colon\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S}\times\mathbb{R})$
is the environment’s transition function, which defines the
probability222Technically, this is the value of the probability density
function for continuous distributions. However, we unify terminology by
referring to the values of probability density functions as probabilities here
and in the following. $P(s^{\prime},r\mid s,a)$ of transitioning to a new
environment state $s^{\prime}$ and receiving reward $r\in\mathbb{R}$ when the
agent uses action $a$ in state $s$, $\gamma\in[0,1]$ is a discount rate and
$p_{0}\in\Delta(\mathcal{S})$ is a probability distribution over potential
starting states. We assume rewards $r$ to be bounded. In the following, our
notation assumes state and action spaces to be continuous.

We call sequences of states, actions and rewards
$(s_{t},a_{t},r_{t+1},s_{t+1},a_{t+1},r_{t+2},\ldots,\\\
s_{t+k-1},a_{t+k-1},r_{t+k},s_{t+k})$ trajectories. A one-step trajectory,
i.e. a tuple $(s_{t},a_{t},r_{t+1},s_{t+1})$ is called a transition. In this
work, we limit ourselves to episodic settings, where the agent only interacts
with the environment for a finite number of at most $T$ steps after which the
environment is reset to a starting state. An episode may however be shorter
than $T$ if a terminal state is reached. Therefore each episode consists of a
trajectory
$(s_{0},a_{0},r_{1},s_{1},a_{1},r_{2},\ldots,s_{\tilde{T}-1},a_{\tilde{T}-1},r_{\tilde{T}},s_{\tilde{T}})$,
with $\tilde{T}\leq T$. Rewards are occasionally omitted from the trajectory
notation since they do not influence future states. Correspondingly, we also
can compute the alternative transition probabilities $P(s^{\prime}\mid
s,a)=\int_{r\in\mathbb{R}}P(s^{\prime},r\mid s,a)\>dr$.

The main goal in reinforcement learning is to solve the control problem of
learning a policy $\pi\colon\mathcal{S}\rightarrow\Delta(\mathcal{A})$ to
maximize the expected return. The return
$G_{t}\coloneqq\sum_{k=0}^{T}\gamma^{k}r_{t+k+1}$ is the discounted sum of
rewards from timestep $t$ onwards. Note that $G_{t}$ is bounded since rewards
are bounded. We denote the probability of taking action $a$ in state $s$ under
policy $\pi$ with $\pi(a\mid s)$. For a policy $\pi$, its stationary state
distribution $d^{\pi}$ determines the probability of being in a specific state
$s\in\mathcal{S}$ at any point in time when following $\pi$.

Let $\Pi$ be the set of all possible policies. RL algorithms
$\mathfrak{A}\colon\Pi\rightarrow\Pi$ for the control problem now iteratively
learn policies by interacting with the environment using the current policy to
sample transitions, which are then used to update the policy. We will discuss
how these updates can look like in Section 2.2.3. A key characteristic of many
RL problems is a necessary trade-off between exploration and exploitation in
this learning process. The agent has no prior knowledge of the environment and
thus needs to explore different transitions in order to learn which states and
actions are desirable. As state and action spaces are typically large however,
exploiting the already acquired knowledge about the environment is also
crucial to guide the search process for an optimal policy to subspaces that
hold most promise. A common approach to this exploration problem is to add
noise to the policy.

####  2.2.2 Value Functions

Based on the return, we define the value and action-value functions, which are
fundamental in RL. The value function

$V_{\pi}(s)\coloneqq\mathbb{E}_{\pi}\bigl{[}G_{t}\mid S_{t}=s\bigr{]}$ (1)

gives the expected return from state $s$ onwards when following policy $\pi$,
which selects all subsequent actions. Thus, the value function states how good
it is to be in a specific state $s$ given a policy $\pi$. Note that here we
follow the general convention to write this just as an expectation over $\pi$.
However, it should be noted that this expectation integrates over all
subsequent states and actions that are obtained by following policy $\pi$,
i.e. Equation (1) computes the expected return given that all subsequent
actions are sampled from $\pi$ and all rewards and next states are sampled
from $P$. This is implicit in our notation here as well as in further
expectations.

Next, we define the action-value function

$Q_{\pi}(s,a)\coloneqq\mathbb{E}_{\pi}\bigl{[}G_{t}\mid
S_{t}=s,A_{t}=a\bigr{]},$

which differs from the value function in that the very first action $a$ is
provided as an input to the function and not determined by the policy. We
observe the following relation between $V_{\pi}$ and $Q_{\pi}$:

$V_{\pi}(s)=\int_{a\in\mathcal{A}}\pi(a\mid s)\>Q_{\pi}(s,a)\>da.$

Further, we call

$~A_{\pi}(s,a)\coloneqq Q_{\pi}(s,a)-V_{\pi}(s)$

the advantage function, which determines how good an action $a$ is in state
$s$ in relation to other possible actions.

From the definitions of $V_{\pi}$ and $Q_{\pi}$ we can derive the so-called
Bellman equations [9]. Starting from Equation (1), we use the definition of
the return $G_{t}$, explicitly write out the expectation for the first
transition and then apply the definition of $V_{\pi}$ again:

$\displaystyle V_{\pi}(s)$ $\displaystyle=\mathbb{E}_{\pi}\bigl{[}G_{t}\mid
S_{t}=s\bigr{]}$ $\displaystyle=\mathbb{E}_{\pi}\bigl{[}R_{t+1}+\gamma
G_{t+1}\mid S_{t}=s\bigr{]}$ $\displaystyle=\int_{a\in\mathcal{A}}\pi(a\mid
s)\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\biggl{(}r+\gamma\mathbb{E}_{\pi}\Bigl{[}G_{t+1}\mid
S_{t+1}=s^{\prime}\Bigr{]}\biggr{)}\>dr\>ds^{\prime}\>da$
$\displaystyle=\int_{a\in\mathcal{A}}\pi(a\mid
s)\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\bigl{(}r+\gamma V_{\pi}(s^{\prime})\bigr{)}\>dr\>ds^{\prime}\>da$

Thus, we find a formulation of the value function, which depends on the value
of subsequent states. Collapsing the expectation again yields the form known
as the Bellman equation of the value function:

$V_{\pi}(s)=\mathbb{E}_{\pi}\bigl{[}R_{t+1}+\gamma V_{\pi}(S_{t+1})\bigr{]}.$

Similarly, we can find the Bellman equation for the action-value function:

$Q_{\pi}(s,a)=\mathbb{E}_{\pi}\bigl{[}R_{t+1}+\gamma
Q_{\pi}(S_{t+1},A_{t+1})\bigr{]}.$ (2)

Now, we can formally define what optimality means in RL. An optimal policy
$\pi^{*}$ is defined by $V_{\pi^{*}}(s)\geq V_{\pi}(s)$ for all states $s$ and
policies $\pi$, i.e. any optimal policy maximizes the expected return. It can
be shown that in every finite MDP, a deterministic optimal policy exists [56].
All optimal policies share the same optimal value function
$V^{*}(s)\coloneqq\max_{\pi\in\Pi}V_{\pi}(s)$ and optimal action-value
function $Q^{*}(s,a)\coloneqq\max_{\pi\in\Pi}Q_{\pi}(s,a)$ and select actions
$a\in\operatorname*{arg\,max}_{a^{\prime}}Q^{*}(s,a^{\prime})$ for every
state. Applying this to Equation (2) yields the Bellman optimality equation

$\displaystyle Q^{*}(s,a)$
$\displaystyle=\mathbb{E}_{\pi^{*}}\bigl{[}R_{t+1}+\gamma
Q^{*}(S_{t+1},A_{t+1})\bigr{]}$
$\displaystyle=\mathbb{E}\bigl{[}R_{t+1}+\gamma\max_{a^{\prime}\in\mathcal{A}}Q^{*}(S_{t+1},a^{\prime})\bigr{]}$

We cite the following result without proof from [75] on how to obtain an
optimal policy, which we will revisit in Section 5.

######  Theorem 2.1.

(Generalized Policy Iteration) Let $\pi_{\text{old}}$ be the current policy.
Then, Generalized Policy Iteration updates its policy by

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\pi_{\text{old}}}(s,A)\bigr{]}$

for all $s\in\mathcal{S}$. Let $\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$ be a
sequence of policies obtained through Generalized Policy Iteration. Then, this
sequence converges to an optimal policy, i.e.

$\lim_{n\to\infty}\pi_{n}=\pi^{*}$

and

$\lim_{n\to\infty}Q_{\pi_{n}}=Q^{*}.$

####  2.2.3 On-Policy Policy Gradient Methods

Finally, we will delineate the subfields of RL on which our work focuses. In
this context, we will successively introduce function approximation, policy
gradient methods and the on-policy paradigm.

RL algorithms are mostly concerned with learning functions such as $\pi$,
$V_{\pi}$ or $Q_{\pi}$. Early reinforcement methods learn exact
representations of these by maintaining lookup tables with entries for each
possible function input [75]. While this approach yields theoretical
convergence guarantees [56], it is practically very limited. Similar states
are treated independently such that learnings do not generalize from one state
to others while specific states are only rarely visited in large state spaces
[75]. Moreover, this approach is not applicable to continuous spaces. Function
approximation remedies these shortcomings by parameterizing the function to be
learned. Let $f_{\theta}(x)$ be this learnable function, where $\theta$ are
the function’s parameters, which are adjusted over the course of learning, and
$x$ are the functions inputs such as states and actions or representations
thereof. By choosing $f_{\theta}$ to be continuous in its inputs, we can
ensure that $f_{\theta}$ generalizes across its inputs when we fit it to
sampled transitions [75]. $f_{\theta}$ can be as simple as a linear mapping,
i.e. $f_{\theta}(x)=\theta^{T}x$, however recent works mostly use neural
networks as function approximators (e.g., [55, 72]). The field using neural
networks as function approximators is coined deep RL [55]. For the remainder
of this paper, you can consider any learned function to be a neural network
unless explicitly stated otherwise, although all our statements apply to any
differentiable function approximators. We will introduce deep learning and
neural networks in detail in Section 2.3.

Policy gradient methods pose an alternative to value-based methods in RL. Most
early successes in RL use value-based methods such as Q-Learning [84] or SARSA
[67], that aim at learning a sequence of value functions converging to the
optimal value function, from which an optimal policy can then be inferred. In
contrast, policy-based RL, which we focus on in this work, directly learns a
parameterized policy $\pi_{\theta}$. The main idea in this learning process is
to increase the probability of those actions that lead to higher returns until
we reach an (approximately) optimal policy [75]. While this optimization
problem can be approached in several ways, gradient-based methods are most
commonly used [82]. Following [77], we define policy gradient methods as
follows.

######  Definition 2.2.

(Policy Gradient Algorithm) Let
$\pi_{\theta}\colon\mathcal{S}\rightarrow\Delta(\mathcal{A})$ be a fully
differentiable function with learnable parameters $\theta\in\mathbb{R}^{d}$
mapping states to a probability distribution over actions. Let
$J\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ be some performance measure of
the parameters. We call any learning algorithm a policy gradient algorithm if
it learns its policy $\pi_{\theta}$ by updating $\theta$ via gradient ascent
(or descent) on $J$, i.e. its updates have the general form

$\theta_{\text{new}}\leftarrow\theta+\alpha\nabla_{\theta}J(\theta),$ (3)

where $\alpha\in\mathbb{R}$ is a step size parameter of the algorithm.

In policy-based RL, two distinct ways exist to have the policy output a
probability distribution over actions, from which actions can be sampled [75].
For discrete action spaces, we construct a discrete distribution over the
action space by normalizing the policies’ raw outputs via a softmax function
[26]. In this case, we have

$\pi(a\mid s)=\frac{\exp(\pi_{\theta}(a\mid
s))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\pi_{\theta}(a^{\prime}\mid s))}.$

For continuous action spaces, we let $\pi_{\theta}$ output the mean $\mu$ and
standard deviation $\sigma$ of a Gaussian distribution, i.e.
$\pi_{\theta}(s)=\bigl{(}\mu_{\theta}(s),\sigma_{\theta}(s)\bigr{)}$ such that

$\pi(a\mid
s)=\frac{1}{\sigma_{\theta}(s)\sqrt{2\pi}}\exp\Biggl{(}-\frac{\bigl{(}a-\mu_{\theta}(s)\bigr{)}^{2}}{2\sigma_{\theta}(s)^{2}}\Biggr{)}.$

This parameterization of a Gaussian distribution for the policy was first
introduced by [87, 88]. As action spaces are commonly bounded, the actions
sampled from such a Gaussian are typically transformed to be within these
bounds either by clipping or by applying a squashing distribution [5].
Further, we highlight that the policies learned by policy gradient methods in
both the discrete and the continuous case are generally stochastic. This
stands in contrast to value-based methods which generally learn deterministic
policies [77]. Policy gradient methods are the core focus of this paper and
will be discussed in-depth in subsequent sections.

Lastly, we delineate on-policy from off-policy algorithms. In RL, we
distinguish between behavior and target policies [75]. A behavior policy is a
policy which generates the data in form of trajectories from which we want to
learn, i.e. this is the policy from which we sample actions when interacting
with the environment. Conversely, the target policy is the policy which we
want to learn about to evaluate how good it is in the given environment and
improve it. Algorithms where behavior and target policy are not identical,
e.g. Q-Learning [84] or DQN [55], are referred to as off-policy algorithms. In
this work, we only discuss on on-policy algorithms, where behavior and target
policy are identical. Hence, when speaking of policy gradient algorithms in
the following, we always implicitly mean on-policy policy gradient algorithms
if not mentioned otherwise.

###  2.3 Deep Learning

In this section, we introduce deep learning as a subfield of machine learning
since its methods are commonly used in policy gradient algorithms. In recent
years, deep learning has emerged as the premier machine learning method in
various fields, enabling state-of-the-art performance in domains such as
computer vision (e.g., [44, 29, 22]) and natural language processing (e.g.,
[83, 14]. Following [47] and [26], we define deep learning as a set of
techniques to solve prediction tasks by learning multiple levels of
representations from raw data using a composition of simple non-linear
functions. This composition of functions, that we will describe in detail
later, is referred to as (deep) neural network. Deep learning stands in
contrast to conventional machine learning techniques like logistic
regressions, which typically require hand-engineered representations as inputs
to be effective [47]. In the following, we introduce the general problem
setting of deep learning using the notation of [10], formalize neural networks
and describe how they are trained.

Consider measurable spaces $\mathcal{X}$ and $\mathcal{Y}$.
$\mathcal{Z}\coloneqq\mathcal{X}\times\mathcal{Y}$ is the data space with each
element $z=(x,y)\in\mathcal{Z}$ being a tuple of input features
$x\in\mathcal{X}$ and a label $y\in\mathcal{Y}$. Let
$\mathcal{M}(\mathcal{X},\mathcal{Y})$ be the set of measurable functions from
$\mathcal{X}$ to $\mathcal{Y}$. The problems we encounter in deep learning are
prediction tasks. Thus, the goal is to learn a mapping
$f\in\mathcal{M}(\mathcal{X},\mathcal{Y})$ from inputs to labels by minimizing
some loss function $\mathcal{L}$ over training data
$S=\\{z^{(1)},\ldots,z^{(m)}\\}$ such that it generalizes to unseen data
$z\in\mathcal{Z}$. To learn the function $f$, we first select a hypothesis set
$\mathcal{F}\subset\mathcal{M}(\mathcal{X},\mathcal{Y})$. Deep learning then
provides learning algorithms
$\mathfrak{A}\colon\mathcal{Z}\rightarrow\mathcal{F}$ that use training data
$S$ to learn the desired function $f=\mathfrak{A}(S)$. Before we discuss this
learning process, we will first further characterize the mapping to be
learned.

In deep learning, functions in the hypothesis set $\mathcal{F}$ represent
instances of neural networks. Note that here we limit ourselves to feedforward
networks, also called multilayer perceptrons (MLP), and will not discuss
transformers [83], recurrent (RNN) [32] or convolutional neural networks
(CNN)[44].

######  Definition 2.3.

(Feedforward Neural Network) A feedforward neural network
$f\colon\mathcal{X}\rightarrow\mathcal{Y}$ is a composition of functions

$f=f^{(n+1)}\circ\cdots\circ f^{(1)}$

that is differentiable almost everywhere. We refer to $f^{(i)},\ i=1,\ldots,n$
as hidden layers, whereas $f^{(n+1)}$ is the non-hidden output layer.
Consequently, $n$ denotes the number of of hidden layers in the network. Each
hidden layer is characterized by a layer width $N_{i}$. Let $N_{0}$ and
$N_{n+1}$ further be the size of the input and output vectors respectively.
Then, we can write each layer as

$f^{(i)}(x)=g\left(W^{(i)}x+b^{(i)}\right),$

where $x$ is the output of the previous layer or the network’s inputs for
$i=1$, $W^{(i)}\in\mathbb{R}^{N_{i}\times N_{i-1}}$ and
$b^{(i)}\in\mathbb{R}^{N_{i}}$ are the layer’s weight matrix and bias vector
respectively and $g\colon\mathbb{R}\rightarrow\mathbb{R}$ is a differentiable
activation function introducing non-linearity. $g$ is applied element-wise.

An MLP can be characterized by its architecture
$a=\bigl{(}(N_{i})^{n+1}_{i=0},\ g\bigr{)}$, consisting of layer sizes and the
activation function to be used. The number of layers $n+1$ is also referred to
as the depth of the network. The Universal Approximation Theorem [17, 35]
underpins the expressivity of neural networks: a two-layer network can already
approximate any measurable function arbitrarily well under weak conditions on
the activation function. Technically, each layer can feature a different
activation function albeit this is uncommon. The activation function of the
output layer is not defined by the architecture $a$ but is derived from the
prediction task. The standard choice for activation functions in the hidden
layers is a rectified linear unit (ReLU)333Note that the ReLU function is not
differentiable at 0. In practice, this is circumvented by using its sub-
derivatives. [57], due to typically fast learning [25]. See [48] for an
overview of other commonly used activation functions. The output layer
typically uses no activation function for regression tasks and sigmoid or
softmax functions for classification tasks. Each element of a layer $f^{(i)}$
is called a neuron. The outputs $a^{(i)}=\bigl{(}f^{(i)}\circ\cdots\circ
f^{(1)}\bigr{)}(x)$ of any layer are the learned representations of the inputs
$x$. We denote the outputs $f(x)$, i.e. the predictions, of the neural network
with $\hat{y}$. Figure 2 depicts a neural network as an acyclic directed
graph.

$x_{1}$$x_{2}$$x_{3}$$a^{(1)}_{3}$$a^{(1)}_{2}$$a^{(1)}_{1}$$a^{(1)}_{4}$$a^{(1)}_{5}$$a^{(2)}_{1}$$a^{(2)}_{2}$$a^{(2)}_{3}$$a^{(2)}_{4}$$\hat{y}_{1}$$\hat{y}_{2}$$f^{(1)}$$f^{(2)}$$f^{(3)}$
Figure 2: A neural network with hidden layers of sizes 5 and 4 as a directed
graph.

Selecting a hypothesis set $\mathcal{F}$ is done implicitly by specifying an
architecture $a$. Hence, we denote the hypothesis set for architecture $a$,
whose elements are all MLPs with that architecture, by $\mathcal{F}_{a}$. The
MLPs in $\mathcal{F}_{a}$ therefore differ only in their weights and biases.
We call these the (learnable) parameters of the network and typically collect
them in a flattened parameter vector $\theta\in\mathbb{R}^{d}$. We denote an
MLP with parameters $\theta$ as $f_{\theta}$.

Given a hypothesis set $\mathcal{F}_{a}$, we now aim to learn a neural network
$f_{\theta}\in\mathcal{F}_{a}$, i.e. to learn parameters $\theta$, such that
we reduce the expected loss or risk,

$\mathcal{R}(f)\coloneqq\mathbb{E}_{Z\sim\mathbb{P}_{Z}}\bigl{[}\mathcal{L}(f,Z)\bigr{]}=\int_{z\in\mathcal{Z}}\mathcal{L}(f,z)\>d\mathbb{P}_{Z}(z),$

over the data distribution $\mathbb{P}_{Z}$ for some appropriately chosen
differentiable loss function
$\mathcal{L}\colon\mathcal{F}\times\mathcal{Z}\rightarrow\mathbb{R}$ [10, 26].
Here $\mathbb{P}_{Z}$ is the image measure of $Z$ on $\mathcal{Z}$, from which
the training data $S=\\{z^{(1)},\ldots,z^{(m)}\\}$ and unknown out-of-sample
data $z$ is drawn. We generally assume that training $z^{(1)},\ldots,z^{(m)}$
and out-of-sample data $z$ are realizations of i.i.d. random variables
$Z^{(1)},\ldots,Z^{(m)},Z\sim\mathbb{P}_{Z}$ [10]. For a given MLP
$f_{\theta}=\mathfrak{A}(S)$ trained on $S$, the risk becomes
$\mathcal{R}(f_{\theta})=\mathbb{E}_{Z\sim\mathbb{P}_{Z}}\bigl{[}\mathcal{L}(f_{\theta},Z)\mid
S\bigr{]}$. In practice, noisy data results in a positive lower bound on risk,
i.e. an irreducible error [10]. Common loss functions are binary cross-entropy
loss,

$\mathcal{L}(f,(x,y))=-\bigl{(}y\cdot\ln(f(x))+(1-y)\cdot\ln(1-f(x))\bigr{)},$

for (binary) classification and mean squared error (MSE),

$\mathcal{L}(f,(x,y))=\bigl{(}y-f(x)\bigr{)}^{2},$

for regression tasks. Sometimes, loss functions are augmented by
regularization terms $\Omega(\theta)$ such as an L2-penalty of the parameters,
i.e. $\beta\lVert\theta\rVert^{2}_{2}$ with $\beta\in\mathbb{R}$ [26].

The data distribution $\mathbb{P}_{Z}$ is generally unknown. Hence, we replace
it by an empirical distribution based on the sampled training data $S$ and use
empirical risk minimization (ERM) as the learning algorithm to minimize it
[26, 10].

######  Definition 2.4.

(Empirical Risk). Given training data $S=\\{z^{(1)},\ldots,z^{(m)}\\}$ and a
function $f_{\theta}\in\mathcal{M}(\mathcal{X},\mathcal{Y})$, the empirical
risk is defined by

$\hat{\mathcal{R}}_{S}(f_{\theta})\coloneqq\frac{1}{m}\sum^{m}_{i=1}\mathcal{L}(f_{\theta},z^{(i)}).$
(4)

######  Definition 2.5.

(ERM learning algorithm). Given hypothesis set $\mathcal{F}_{a}$ and training
data $S$, an empirical risk minimization algorithm
$\mathfrak{A}^{\mathrm{erm}}$ terminates with an (approximate444In practice,
the empirical risk is generally highly non-convex prohibiting guaranteed
convergence to a global minimum [10].) minimizer
$\hat{f}_{S}\in\mathcal{F}_{a}$ of empirical risk:

$\mathfrak{A}^{\mathrm{erm}}(S)=\hat{f}_{S}\in\operatorname*{arg\,min}_{f\in\mathcal{F}_{a}}\hat{\mathcal{R}}_{S}(f).$

We approximately minimize empirical risk typically via gradient-based methods
due to efficient computation of point-wise derivatives via the backpropagation
algorithm [66, 40]. Backpropagation means the practical application of the
chain rule to neural networks. The gradient of the objective function
$\mathcal{L}$ with respects to the $i$-th layer’s inputs $a^{(i-1)}$ can be
computed by working backwards from the gradient with respects to the layer’s
outputs $a^{(i)}$ as
$\nabla_{a^{(i-1)}}\mathcal{L}=\sum_{j}(\nabla_{a^{(i-1)}}a^{(i)}_{j})\frac{\partial\mathcal{L}}{\partial
a^{(i)}_{j}}$. From these gradients, the gradients with respects to the
weights and biases in each layer can be calculated similarly. Due to this flow
of information from the objective function to each of the layers, the
optimization of MLPs is also referred to as backwards pass, in contrast to the
forward pass of calculating $\hat{y}=f(x)$. The full backpropagation algorithm
for MLPs is formulated in Algorithm 1.

Algorithm 1 Backpropagation, pseudocode taken from [26]

labels $y$, regularizer $\Omega(\theta)$, network outputs $\hat{y}$, activated
and unactivated layer outputs $a^{(k)}$ and $h^{(k)}$ for $k=1,\ldots,n$,
activation function $g$, loss $\mathcal{L}$

$\delta\leftarrow\nabla_{\hat{y}}\mathcal{L}$

for $k=n,\ldots,1$ do

$\delta\leftarrow\nabla_{h^{(k)}}\mathcal{L}=\delta\odot g^{\prime}(h^{(k)})$
$\triangleright$ hadamard product if $g$ is element-wise

$\nabla_{b^{(k)}}\mathcal{L}\leftarrow\delta+\nabla_{b^{(k)}}\Omega(\theta)$

$\nabla_{W^{(k)}}\mathcal{L}\leftarrow\delta
h^{(k-1)\mathsf{T}}+\nabla_{W^{(k)}}\Omega(\theta)$

$\delta\leftarrow\nabla_{a^{(k-1)}}\mathcal{L}=W^{(k)\mathsf{T}}\delta$

end for

The gradients computed via backpropagation are used to update the parameters
in each layer using gradient descent. However, due to the prohibitive
computational costs of evaluating the expectation in Equation (4), computing
gradients only on a subset of the training data is generally preferred and
typically also results in faster convergence [26]. At each iteration, a batch
$S^{\prime}$ of data with size $m^{\prime}\leq m$ (typically $m^{\prime}\ll
m$) is randomly sampled from the training data to conduct the update [10]

$\Theta^{(k)}\coloneqq\Theta^{(k-1)}-\alpha_{k}\frac{1}{m^{\prime}}\sum_{z\in
S^{\prime}}\nabla_{\theta}\mathcal{L}\Bigl{(}f_{\Theta^{(k-1)}},z\Bigr{)}.$
(5)

Here, $\Theta$ is a random variable whose realizations are neural network
parameters $\theta$. $\alpha_{k}$ is the step size or learning rate on the
k-th optimization step. The learning rate is commonly decayed over the
training process to help convergence [26]. The procedure using updates as in
Equation (5) is known as stochastic (minibatch) gradient descent
(SGD)555Sometimes SGD refers to updates which only involve a single data
point. We however follow the nowadays common terminology of calling any
sample-based gradient descent stochastic. [26] and dates back to [63, 41].
Using SGD has the additional benefit of introducing random fluctuations which
enable escaping saddle points [10]. SGD in its general form is depicted in
Algorithm 2, where in our context
$r(\theta)=\hat{\mathcal{R}}_{S}(f_{\theta})$. The neural network parameters
$\theta$ are set to be the realization of the final $\Theta^{(K)}$ or a convex
combination of $\bigl{(}\Theta^{(k)}\bigr{)}^{K}_{k=1}$ [10].

Algorithm 2 Stochastic Gradient Descent, pseudocode from [10]

Differentiable function $r\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$, step
sizes $\alpha_{k}\in(0,\infty)$, $k=1,\ldots,K$, $\mathbb{R}^{d}$-valued
random variable $\Theta^{(0)}$

for $k=1,\ldots,K$ do

Let $D^{k}$ be a random variable such that
$\mathbb{E}\bigl{[}D^{(k)}\mid\Theta^{(k-1)}\bigr{]}=\nabla r(\Theta^{(k-1)})$

$\Theta^{(k)}\leftarrow\Theta^{(k-1)}-\alpha_{k}D^{(k)}$

end for

Despite the stochasticity of SGD and highly non-convex loss landscapes, SGD’s
convergence can be guaranteed in some regimes [10], and it exhibits strong
performance in practice [26]. Hence, SGD and its variants are the default
choice to optimize neural networks. The most prominently used variant is Adam
[42], which uses momentum [59] and an adaptive scaling of gradients to
stabilize learning. Nonetheless, the initialization of $\theta$ is also
important for convergence. Biases are commonly initialized to 0 whereas
weights are randomly initialized close to 0 using various strategies [26].
Finally, note that regardless of the non-convexity of the loss landscapes,
local minima are not considered problematic if the neural networks are large
enough [18, 15]

In practice, the training of neural networks is an iterative process. We
alternate between choosing the network architecture $a$ as well as further
hyperparameters of the learning algorithm such as the learning rates $\alpha$,
and approximately minimizing the empirical risk for this set of
hyperparameters. This is generally a trial-and-error process to find a
suitable set of hyperparameters to maximize generalization performance, i.e.
to minimize risk. To approximate risk, the trained models are typically
evaluated by the empirical risk on a held-out test data set, which was not
seen during training [26]. The achieved empirical risk can be decomposed into
a generalization error, an optimization error, an approximation error and the
irreducible error [10]. The generalization error is the difference between
empirical and actual risk stemming from the random sampling of training data,
which may not be representative of the actual data distribution
$\mathbb{P}_{Z}$. The optimization error is the result of potentially not
finding a global mimimum during the learning process. The approximation error
is the difference between the minimum achievable risk over functions in
$\mathcal{F}_{a}$ and over all $f\in\mathcal{M}(\mathcal{X},\mathcal{Y})$.

##  3 Theoretical Foundations of Policy Gradients

Having introduced the fundamentals of deep RL, we can now discuss policy
gradient algorithms in detail. In this section, we derive their theoretical
foundations. Our main focus is going to be the Policy Gradient Theorem, on
which all policy gradient algorithms build. This theorem will be discussed in
Section 3.1. Furthermore, Sections 3.2 and 3.3 introduce the theoretical
justifications for additional methods that are frequently used in policy
gradient algorithms.

###  3.1 Policy Gradient Theorem

Given an MDP $\mathcal{M}=(\mathcal{S},\mathcal{A},P,\gamma,p_{0})$, consider
a parameterized policy $\pi_{\theta}$, which is differentiable almost
everywhere, and the following objective function $J$ for maximizing the
expected episodic return:

$\displaystyle J(\theta)$ $\displaystyle=\mathbb{E}_{S_{0}\sim
p_{0},\pi_{\theta}}\bigl{[}G_{0}\bigr{]}$ $\displaystyle=\mathbb{E}_{S_{0}\sim
p_{0}}\Bigl{[}\mathbb{E}_{\pi_{\theta}}\bigl{[}G_{t}\mid
S_{t}=S_{0}\bigr{]}\Bigr{]}$ $\displaystyle=\mathbb{E}_{S_{0}\sim
p_{0}}\Bigl{[}V_{\pi_{\theta}}(S_{0})\Bigr{]}$

The idea of policy gradient algorithms is to maximize $J(\theta)$ over the
parameters $\theta$ by performing gradient ascent [75]. Hence, we require the
gradients $\nabla_{\theta}J(\theta)$, however it is a priori not obvious how
the right-hand side $\mathbb{E}_{S_{0}\sim
p_{0},\pi_{\theta}}\bigl{[}G_{0}\bigr{]}$ depends on $\theta$ as changes in
the policy $\pi$ also affect the state distribution $d^{\pi}$. The Policy
Gradient Theorem [76, 52] yields an analytic form of
$\nabla_{\theta}J(\theta)$ from which we can sample gradients that does not
involve the derivative of $d^{\pi}$. Here, we focus on the undiscounted case,
i.e. $\gamma=1$. Note that any discounted problem instance can be reduced to
the undiscounted case by letting the reward function absorb the discount
factor [70].

######  Theorem 3.1.

(Policy Gradient Theorem) For a given MDP, let $\pi_{\theta}$ be
differentiable w.r.t. $\theta$ and $\nabla_{\theta}\pi_{\theta}$ be bounded,
let $Q_{\pi_{\theta}}$ be differentiable w.r.t. $\theta$ and
$\nabla_{\theta}Q_{\pi_{\theta}}$ be bounded for all $s\in\mathcal{S}$ and
$a\in\mathcal{A}$. Then, there exists a constant $\eta$ such that

$\nabla_{\theta}J(\theta)=\eta\>\mathbb{E}_{S\sim
d^{\pi_{\theta}},A\sim\pi_{\theta}}\Bigl{[}Q_{\pi_{\theta}}(S,A)\>\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\Bigr{]}.$ (6)

###### Proof.

We largely follow the proof by [75] albeit in a more detailed form and
extended to continuous state and action spaces. To enhance readability, we
omit subscripts $\theta$ for the policy $\pi$ and all gradients $\nabla$ but
both always depend on the parameters $\theta$.

Starting from the definition of the objective function, we explicitly write
out the expectation over starting states, use the relationship between value
and action-value function, $V_{\pi}(s)=\int_{a\in\mathcal{A}}\pi(a\mid
s)\>Q_{\pi}(s,a)\>da,$ and differentiate by parts.

$\displaystyle\nabla J(\theta)$ $\displaystyle=\nabla\mathbb{E}_{S\sim
p_{0}}\bigl{[}V_{\pi}(S)\bigr{]}$
$\displaystyle=\nabla\int_{s\in\mathcal{S}}p_{0}(s)\>V_{\pi}(s)\>ds$
$\displaystyle=\nabla\int_{s\in\mathcal{S}}p_{0}(s)\int_{a\in\mathcal{A}}\pi(a\mid
s)\>Q_{\pi}(s,a)\>da\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\biggl{(}\int_{a\in\mathcal{A}}\bigl{(}\nabla\pi(a\mid
s)\bigr{)}\>Q_{\pi}(s,a)\>da+\int_{a\in\mathcal{A}}\pi(a\mid s)\>\nabla
Q_{\pi}(s,a)\>da\biggr{)}\>ds.$ (7)

Note that in the last step via used the Leibniz integral rule (Theorem D.10)
to swap the order of integration and differentiation prior to applying the
product rule. The conditions for Leibniz are satisfied since $\pi(\cdot\mid
s)Q_{\pi}(s,\cdot)$ is integrable for any $s\in\mathcal{S}$ and its partial
derivatives exist and are bounded for all $s\in\mathcal{S}$ and
$a\in\mathcal{A}$ since $\pi$ and $Q_{\pi}$ are bounded and $\nabla Q_{\pi}$
and $\nabla\pi$ exist and are bounded by assumption.

Now, consider the recursive formulation of the action-value function

$Q_{\pi}(s,a)=\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>\bigl{(}r+V_{\pi}(s^{\prime})\bigr{)}\>dr\>ds^{\prime}.$

Due to the identity $\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>dr=P(s^{\prime}\mid s,a)$ and since realized rewards $r$ and environment
transitions for a given action no longer depend on the policy, we can
reformulate the gradients of $Q_{\pi}$ w.r.t. $\theta$, again using the
Leibniz integral rule.

$\displaystyle\nabla Q_{\pi}(s,a)$
$\displaystyle=\nabla\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>\bigl{(}r+V_{\pi}(s^{\prime})\bigr{)}\>dr\>ds^{\prime}$
$\displaystyle=\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>\nabla\bigl{(}r+V_{\pi}(s^{\prime})\bigr{)}\>dr\>ds^{\prime}$
$\displaystyle=\int_{s^{\prime}\in\mathcal{S}}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>\nabla V_{\pi}(s^{\prime})\>dr\>ds^{\prime}$
$\displaystyle=\int_{s^{\prime}\in\mathcal{S}}\biggl{(}\int_{r\in\mathbb{R}}P(s^{\prime},r\mid
s,a)\>dr\biggr{)}\>\nabla V_{\pi}(s^{\prime})\>ds^{\prime}$
$\displaystyle=\int_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid s,a)\>\nabla
V_{\pi}(s^{\prime})\>ds^{\prime}.$ (8)

Further, note that for all $s\in\mathcal{S}$

$\displaystyle\nabla V_{\pi}(s)$
$\displaystyle=\nabla\int_{a\in\mathcal{A}}\pi(a\mid s)\>Q_{\pi}(s,a)\>da$
$\displaystyle=\int_{a\in\mathcal{A}}\bigl{(}\nabla\pi(a\mid
s)\bigr{)}\>Q_{\pi}(s,a)\>da+\int_{a\in\mathcal{A}}\pi(a\mid s)\>\nabla
Q_{\pi}(s,a)\>da,$ (9)

which is equivalent to the inner expression in Equation (7). By using (8) and
(9), we can transform (7) into a recursive form, which we are then going to
unroll subsequently to yield an explicit form. In the following, we simply
notation by defining

$\phi(s)\coloneqq\int_{a\in\mathcal{A}}\bigl{(}\nabla\pi(a\mid
s)\bigr{)}\>Q_{\pi}(s,a)\>da.$ (10)

Applying (10) and (8) to (7) in order and rearranging the integrals gives

$\displaystyle\nabla J(\theta)$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\int_{a\in\mathcal{A}}\bigl{(}\nabla\pi(a\mid
s)\bigr{)}\>Q_{\pi}(s,a)da+\int_{a\in\mathcal{A}}\pi(a\mid s)\>\nabla
Q_{\pi}(s,a)\>da\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{a\in\mathcal{A}}\pi(a\mid
s)\>\nabla Q_{\pi}(s,a)\>da\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{a\in\mathcal{A}}\pi(a\mid
s)\>\int_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid s,a)\>\nabla
V_{\pi}(s^{\prime})\>ds^{\prime}\>da\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\int_{a\in\mathcal{A}}\pi(a\mid
s)\>P(s^{\prime}\mid s,a)\>da\>\nabla
V_{\pi}(s^{\prime})\>ds^{\prime}\biggr{)}\>ds$ (11)

In the final step, we switched the order of integration using Fubini’s Theorem
(Theorem D.11), which is applicable since $\nabla V_{\pi}$ is bounded and
$\pi(\cdot\mid s)P(\cdot\mid s,\cdot)$ is a probability measure on
$\mathcal{S}\times\mathcal{A}$ such that $\lvert\pi(\cdot\mid s)P(\cdot\mid
s,\cdot)\nabla V_{\pi}\rvert$ is integrable over the product space
$\mathcal{S}\times\mathcal{A}$. To unroll Equation (11) across time, we
introduce notation for multi-step transition probabilities. Let
$\rho_{\pi}(s\to s^{\prime},k)$ be the probability of transitioning from state
$s$ to $s^{\prime}$ after $k$ steps under policy $\pi$. We have that

$\rho_{\pi}(s\to s^{\prime},0)\coloneqq\begin{cases}1&\text{if
}s=s^{\prime},\\\ 0&\text{else}\end{cases}$

and $\rho_{\pi}(s\to s^{\prime},1)\coloneqq\int_{a\in\mathcal{A}}\pi(a\mid
s)\>P(s^{\prime}\mid s,a)\>da$. Now, we can recursively write

$\rho_{\pi}(s\to
s^{\prime\prime},k+1)=\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},k)\>\rho_{\pi}(s^{\prime}\to s^{\prime\prime},1)\>ds^{\prime}.$

Using this notation, iteratively substituting in (8) and (9) and applying
Fubini, we can unroll (11):

$\displaystyle\nabla J(\theta)$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\int_{a\in\mathcal{A}}\pi(a\mid
s)\>P(s^{\prime}\mid s,a)\>da\>\nabla
V_{\pi}(s^{\prime})\>ds^{\prime}\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\nabla V_{\pi}(s^{\prime})\>ds^{\prime}\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\Biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\biggl{(}\phi(s^{\prime})+\int_{a\in\mathcal{A}}\pi(a\mid
s^{\prime})\>\nabla
Q_{\pi}(s^{\prime},a)\>da\biggr{)}\>ds^{\prime}\Biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\Biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\biggl{(}\phi(s^{\prime})+\int_{s^{\prime\prime}\in\mathcal{S}}\rho_{\pi}(s^{\prime}\to
s^{\prime\prime},1)\>\nabla
V_{\pi}(s^{\prime\prime})\>ds^{\prime\prime}\biggr{)}\>ds^{\prime}\Biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\Biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\phi(s^{\prime})\>ds^{\prime}$
$\displaystyle\qquad+\int_{s^{\prime\prime}\in\mathcal{S}}\biggl{(}\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\rho_{\pi}(s^{\prime}\to
s^{\prime\prime},1)\>ds^{\prime}\biggr{)}\>\nabla
V_{\pi}(s^{\prime\prime})\>ds^{\prime\prime}\>\Biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\phi(s^{\prime})\>ds^{\prime}+\int_{s^{\prime\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime\prime},2)\>\nabla
V_{\pi}(s^{\prime\prime})\>ds^{\prime\prime}\biggr{)}\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\>\biggl{(}\rho_{\pi}(s\to
s,0)\phi(s)+\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime},1)\>\phi(s^{\prime})\>ds^{\prime}$
$\displaystyle\qquad+\int_{s^{\prime\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime\prime},2)\>\phi(s^{\prime\prime})\>ds^{\prime\prime}+\int_{s^{\prime\prime\prime}\in\mathcal{S}}\rho_{\pi}(s\to
s^{\prime\prime\prime},3)\>\nabla
V_{\pi}(s^{\prime\prime\prime})\>ds^{\prime\prime\prime}\biggr{)}\>ds$
$\displaystyle\;\;\vdots$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime}\in\mathcal{S}}\sum^{T}_{t=0}\rho_{\pi}(s\to
s^{\prime},t)\>\phi(s^{\prime})\>ds^{\prime}\>ds$

We set $\eta_{s}(s^{\prime})\coloneqq\sum^{T}_{t=0}\rho_{\pi}(s\to
s^{\prime},t)$, rearrange the integrals and multiply by 1 to obtain

$\displaystyle\nabla_{\theta}J(\theta)$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime}\in\mathcal{S}}\sum^{T}_{t=0}\rho_{\pi}(s\to
s^{\prime},t)\>\phi(s^{\prime})\>ds^{\prime}\>ds$
$\displaystyle=\int_{s^{\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\>\eta_{s}(s^{\prime})\>\phi(s^{\prime})\>ds\>ds^{\prime}$
$\displaystyle=\frac{\int_{s^{\prime\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime\prime})\>ds\>ds^{\prime\prime}}{\int_{s^{\prime\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime\prime})\>ds\>ds^{\prime\prime}}\int_{s^{\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\>\eta_{s}(s^{\prime})\>ds\>\phi(s^{\prime})\>ds^{\prime}$
$\displaystyle=\int_{s^{\prime\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime\prime})\>ds\>ds^{\prime\prime}\int_{s^{\prime}\in\mathcal{S}}\frac{\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime})\>ds}{\int_{s^{\prime\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime\prime})\>ds\>ds^{\prime\prime}}\>\>\phi(s^{\prime})\>ds^{\prime}$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime\prime}\in\mathcal{S}}\eta_{s}(s^{\prime\prime})\>ds^{\prime\prime}\>ds\int_{s^{\prime}\in\mathcal{S}}d^{\pi}(s^{\prime})\>\phi(s^{\prime})\>ds^{\prime}.$
(12)

In the final step, we used the identity

$d^{\pi}(s^{\prime})=\frac{\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime})\>ds}{\int_{s^{\prime\prime}\in\mathcal{S}}\int_{s\in\mathcal{S}}p_{0}(s)\eta_{s}(s^{\prime\prime})\>ds\>ds^{\prime\prime}},$

which can be seen as $\eta_{s}(s^{\prime})$ is the accumulate sum over
probabilities of reaching $s^{\prime}$ after any number of steps for a given
starting state. Integrating over the starting state distribution and
normalizing hence yields the probability of visiting state $s^{\prime}$ and
thereby the stationary distribution $d^{\pi}$ over states under the current
policy.

Finally, we can derive the canonical form of the Policy Gradient Theorem from
(12) by using the definition of $\phi(s)$, setting

$\eta\coloneqq\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime\prime}\in\mathcal{S}}\eta_{s}(s^{\prime\prime})\>ds^{\prime\prime}\>ds$

and multiplying with 1:

$\displaystyle\nabla J(\theta)$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime\prime}\in\mathcal{S}}\eta_{s}(s^{\prime\prime})\>ds^{\prime\prime}\>ds\int_{s^{\prime}\in\mathcal{S}}d^{\pi}(s^{\prime})\>\phi(s^{\prime})\>ds^{\prime}$
$\displaystyle=\eta\int_{s^{\prime}\in\mathcal{S}}d^{\pi}(s^{\prime})\int_{a\in\mathcal{A}}\bigl{(}\nabla\pi(a\mid
s^{\prime})\bigr{)}\>Q_{\pi}(s^{\prime},a)\>da\>ds^{\prime}$
$\displaystyle=\eta\int_{s^{\prime}\in\mathcal{S}}d^{\pi}(s^{\prime})\int_{a\in\mathcal{A}}\pi(a\mid
s^{\prime})\>\frac{\nabla\pi(a\mid s^{\prime})}{\pi(a\mid
s^{\prime})}\>Q_{\pi}(s^{\prime},a)\>da\>ds^{\prime}$
$\displaystyle=\eta\int_{s^{\prime}\in\mathcal{S}}d^{\pi}(s^{\prime})\int_{a\in\mathcal{A}}\pi(a\mid
s^{\prime})\>\bigl{(}\nabla\ln\pi(a\mid
s^{\prime})\bigr{)}\>Q_{\pi}(s^{\prime},a)\>da\>ds^{\prime}$
$\displaystyle=\eta\>\mathbb{E}_{S\sim
d^{\pi}}\biggl{[}\mathbb{E}_{A\sim\pi}\Bigl{[}Q_{\pi}(S,A)\>\nabla\ln\pi(A\mid
S)\Bigr{]}\biggr{]}.$

∎

The Policy Gradient Theorem provides us with an explicit form of the policy
gradients from which we can sample gradients. This allows the use of gradient-
based optimization to directly optimize the policy using the methods presented
in Section 2.3. Thus, the theorem serves as the foundation for the policy
gradient algorithms which we will discuss in Section 4.

We conclude this section with some further remarks on Equation (6). First, we
note that for any starting state $s\in\mathcal{S}$, we have that

$\displaystyle\eta$
$\displaystyle=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime}\in\mathcal{S}}\eta_{s}(s^{\prime})\>ds^{\prime}\>ds=\int_{s\in\mathcal{S}}p_{0}(s)\int_{s^{\prime}\in\mathcal{S}}\sum^{T}_{t=0}\rho_{\pi}(s\to
s^{\prime},t)\>ds^{\prime}\>ds$ $\displaystyle=\mathbb{E}_{S\sim
p_{0}}\Biggl{[}\sum^{T}_{t=0}\int_{s^{\prime}\in\mathcal{S}}\rho_{\pi}(S\to
s^{\prime},t)\>ds^{\prime}\Biggr{]},$

which is the average episode length666Note that $\rho_{\pi}(s_{t}\to
s_{t+1},1)=0$ if the episode already terminated due to reaching a terminal
state on any previous step. under policy $\pi$ [75]. Second, the use of
gradient-based methods makes it sufficient to sample gradients which are only
proportional to the actual gradients since any constant of proportionality can
be absorbed by the learning rate parameter of the optimization algorithms.
Hence, $\eta$ is commonly omitted [75], i.e.

$\nabla_{\theta}J(\theta)\propto\mathbb{E}_{S\sim
d^{\pi_{\theta}},A\sim\pi_{\theta}}\Bigl{[}Q_{\pi_{\theta}}(S,A)\>\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\Bigr{]}.$ (13)

We observe that all terms on the right hand side are known or can be estimated
via sampling.

###  3.2 Value Function Estimation with Baselines

In practice, the resulting estimates of the policy gradients can become very
noisy when sampling from Equation (13). Therefore, a main practical challenge
of policy gradient algorithms is to introduce measures to reduce the variance
of the gradients while keeping the bias low [77]. In this context, a well-
known and widely used technique is to use a baseline [88] when sampling an
estimate of the action-value function $Q_{\pi}$ [27]. In this section, we show
that using an appropriately chosen baseline does not bias the estimate but can
greatly reduce the variance of the sampled gradients.

Let $\hat{Q}(s,a)$ be a sampled estimate of $Q_{\pi}(s,a)$, assuming
$\mathbb{E}\bigl{[}\hat{Q}(s,a)\bigr{]}=Q_{\pi}(s,a)$. Then, we can construct
a new estimator $\hat{Q}_{b}(s,a)$ by subtracting some baseline
$b\colon\mathcal{S}\rightarrow\mathbb{R}$, i.e.
$\hat{Q}_{b}(s,a)=\hat{Q}(s,a)-b(s)$. Our only condition towards $b$ is that
it does not depend on the action $a$, though it can depend on the state $s$
and even be a random variable [75]. Our sampled estimate of the gradient
$\nabla_{\theta}J(\theta)$ becomes

$\hat{\nabla}_{\theta}J(\theta)=\nabla_{\theta}\ln\pi_{\theta}(a\mid
s)\bigl{(}\hat{Q}(s,a)-b(s)\bigr{)}.$

In expectation over the policy $\pi$, this yields

$\displaystyle\mathbb{E}_{\pi}\Bigl{[}\hat{\nabla}_{\theta}J(\theta)\Bigr{]}$
$\displaystyle=\mathbb{E}_{\pi}\Bigl{[}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\>\bigl{(}\hat{Q}(S,A)-b(S)\bigr{)}\Bigr{]}$
$\displaystyle=\mathbb{E}_{\pi}\Bigl{[}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\>\hat{Q}(S,A)\Bigr{]}-\mathbb{E}_{\pi}\Bigl{[}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\>b(S)\Bigr{]}$

using the linearity of the expectation. Now, we show that the second part is
0. Using the Leibniz integral rule, we have that

$\displaystyle\mathbb{E}_{S\sim
d^{\pi_{\theta}},A\sim\pi_{\theta}}\Bigl{[}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\>b(S)\Bigr{]}$
$\displaystyle=\int_{s\in\mathcal{S}}d^{\pi}(s)\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)\>\nabla_{\theta}\ln\pi_{\theta}(a\mid s)\>b(s)\>da\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}d^{\pi}(s)\>b(s)\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)\>\nabla_{\theta}\ln\pi_{\theta}(a\mid s)\>da\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}d^{\pi}(s)\>b(s)\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)\frac{\nabla_{\theta}\pi_{\theta}(a\mid s)}{\pi_{\theta}(a\mid s)}\>da\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}d^{\pi}(s)\>b(s)\>\nabla_{\theta}\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)\>da\>ds$
$\displaystyle=\int_{s\in\mathcal{S}}d^{\pi}(s)\>b(s)\>\nabla_{\theta}\>1\>ds$
$\displaystyle=0$

since $\pi(\cdot\mid s)$ is a probability distribution over actions. Thus,
subtracting an action-independent baseline $b$ from an action-value function
estimator $\hat{Q}$ does indeed not add any bias to the gradient estimate.
While here we have shown this for a baseline which only depends on the current
state, this result can be extended to baselines which depend on the current
and all subsequent states [70].

Next, we analyze the effect on the variance of the gradient estimates. Here,
we only provide an approximate explanation, see [27] for a more thorough
analysis which derives bounds of the true variance. We can compute the
variance using $\mathrm{Var}[X]=\mathbb{E}[X^{2}]-\mathbb{E}[X]^{2}$. Due to
the above, $\mathbb{E}[X]^{2}$ is independent of the baseline in our case.
This yields

$\displaystyle\operatorname*{arg\,min}_{b}\mathrm{Var}_{\pi}\Bigl{[}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\bigl{(}\hat{Q}(S,A)-b(S)\bigr{)}\Bigr{]}$
$\displaystyle=\operatorname*{arg\,min}_{b}\mathbb{E}_{\pi}\Bigl{[}\Bigl{(}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\bigl{(}\hat{Q}(S,A)-b(S)\bigr{)}\Bigr{)}^{2}\Bigr{]}$
$\displaystyle\approx\operatorname*{arg\,min}_{b}\biggl{(}\mathbb{E}_{\pi}\bigl{[}\bigl{(}\nabla_{\theta}\ln\pi_{\theta}(A\mid
S)\bigr{)}^{2}\bigr{]}\cdot\mathbb{E}_{\pi}\bigl{[}\bigl{(}\hat{Q}(S,A)-b(S)\bigr{)}^{2}\bigr{]}\biggr{)},$

where we approximated the variance by assuming independence of the two terms
in the second step. Under this approximation, the variance of sampled
gradients can be minimized by minimizing
$\mathbb{E}_{\pi}\bigl{[}\bigl{(}\hat{Q}(S,A)-b(S)\bigr{)}^{2}\bigr{]}$. This
is a common least squares problem resulting in the optimal choice of
$b(s)=\mathbb{E}_{\pi}[\hat{Q}(s,A)]$ (see Theorem D.8). This result indicates
that an appropriately chosen baseline can potentially significantly reduce
variance of the gradients. Using this choice for the baseline, we would like
to compute gradients for sampled states and actions as

$\displaystyle\nabla_{\theta}\ln\pi_{\theta}(a\mid
s)\bigl{(}Q_{\pi}(s,a)-\mathbb{E}_{A\sim\pi_{\theta}}[Q_{\pi}(s,A)]\bigr{)}$
$\displaystyle=\nabla_{\theta}\ln\pi_{\theta}(a\mid
s)\bigl{(}Q_{\pi}(s,a)-V_{\pi}(s)\bigr{)}$
$\displaystyle=\nabla_{\theta}\ln\pi_{\theta}(a\mid s)A_{\pi}(s,a).$

Here, we used the relation of the value function $V_{\pi}$ to $Q_{\pi}$ and
the definition of the advantage function $A_{\pi}$. Despite our
approximations, this choice of a baseline turns out to yield almost the lowest
possible variance of the gradients [70]. However, note that in practice the
advantage function must also be estimated. Learning this estimate typically
introduces bias [43, 76].

###  3.3 Importance Sampling

Importance sampling is a technique to calculate expectations under one
distribution given samples from another [65, 31, 75]. Traditionally, this is
only needed in off-policy RL, where we sample transitions using a behavior
policy $\beta$ but want to calculate expectations over the target policy
$\pi$. However, in some implementations of on-policy algorithms the policy may
be updated before all data generated by it is processed. This makes these
implementations slightly off-policy and thus importance sampling becomes
relevant even for theoretically on-policy algorithms [85]. We build our
presentation of importance sampling on [75], Section 5.5.

Given a behavior policy $\beta$, we want to estimate the value function
$V_{\pi}$ of our target policy $\pi$. Generally, we have

$V_{\beta}(s)=\mathbb{E}_{\beta}\bigl{[}G_{t}\mid S_{t}=s\bigr{]}\neq
V_{\pi}(s).$

We can calculate the probability of a trajectory
$(a_{t},s_{t+1},a_{t+1},\ldots,a_{T-1},s_{T})$ under any policy $\pi$ as

$\prod^{T-1}_{k=t}\pi(a_{k}\mid s_{k})P(s_{k+1}\mid s_{k},a_{k}).$

Now, we can define the importance sampling ratio.

######  Definition 3.2.

(Importance Sampling Ratio) Given a target policy $\pi$, a behavior policy
$\beta$ and a trajectory $\tau=(a_{t},s_{t+1},a_{t+1},\ldots,s_{T})$ generated
by $\beta$, the importance sampling ratio is defined as

$\rho_{t:T-1}\coloneqq\frac{\prod^{T-1}_{k=t}\pi(a_{k}\mid s_{k})P(s_{k+1}\mid
s_{k},a_{k})}{\prod^{T-1}_{k=t}\beta(a_{k}\mid s_{k})P(s_{k+1}\mid
s_{k},a_{k})}=\frac{\prod^{T-1}_{k=t}\pi(a_{k}\mid
s_{k})}{\prod^{T-1}_{k=t}\beta(a_{k}\mid s_{k})}.$

Let $\mathcal{T}$ be the set of possible trajectories. By multiplying returns
of trajectories $\tau\in\mathcal{T}$ generated by the behavior policy $\beta$
with the importance sampling ratio $\rho$ we get

$\displaystyle\mathbb{E}_{\beta}\bigl{[}\rho_{t:T-1}G_{t}\mid S_{t}=s\bigr{]}$
$\displaystyle=\mathbb{E}_{\beta}\bigl{[}\rho_{t:T-1}G(\tau)\mid
S_{t}=s\bigr{]}$
$\displaystyle=\sum_{\tau\in\mathcal{T}}\rho_{t:T-1}G(\tau)\prod^{T-1}_{k=t}\beta(a_{k}\mid
s_{k})\>P(s_{k+1}\mid s_{k},a_{k})$
$\displaystyle=\sum_{\tau\in\mathcal{T}}\frac{\prod^{T-1}_{k=t}\pi(a_{k}\mid
s_{k})}{\prod^{T-1}_{k=t}\beta(a_{k}\mid
s_{k})}G(\tau)\prod^{T-1}_{k=t}\beta(a_{k}\mid s_{k})\>P(s_{k+1}\mid
s_{k},a_{k})$
$\displaystyle=\sum_{\tau\in\mathcal{T}}G(\tau)\prod^{T-1}_{k=t}\frac{\pi(a_{k}\mid
s_{k})}{\beta(a_{k}\mid s_{k})}\beta(a_{k}\mid s_{k})\>P(s_{k+1}\mid
s_{k},a_{k})$
$\displaystyle=\sum_{\tau\in\mathcal{T}}G(\tau)\prod^{T-1}_{k=t}\pi(a_{k}\mid
s_{k})P(s_{k+1}\mid s_{k},a_{k})$
$\displaystyle=\mathbb{E}_{\pi}\bigl{[}G_{t}\mid S_{t}=s\bigr{]}$
$\displaystyle=V_{\pi}(s).$

The intuition behind this importance sampling correction is that, to evaluate
$\pi$, we want to weigh returns more heavily that are more likely under $\pi$
than under $\beta$ and vice versa. As an extension of the derivation above, we
also get the per-decision importance sampling ratio
$\rho\coloneqq\frac{\pi(a\mid s)}{\beta(a\mid s)}$ [75].

Using importance sampling, we can derive the following approximate policy
gradients of the target policy $\pi_{\theta}$ in an off-policy setting with
behavior policy $\beta$:

$\nabla_{\theta}J(\theta)\approx\eta\>\mathbb{E}_{S\sim
d^{\beta},A\sim\beta}\biggl{[}\frac{\pi_{\theta}(A\mid S)}{\beta(A\mid
S)}\>Q_{\pi_{\theta}}(S,A)\>\nabla_{\theta}\ln\pi_{\theta}(A\mid S)\biggr{]}.$

See [19] for a proof. Note that $\eta$ now is the average episode length under
$\beta$.

##  4 Policy Gradient Algorithms

Building on Theorem Theorem 3.1, several policy gradient algorithms have been
proposed, which compute sample-based estimates
$\hat{\nabla}_{\theta}J(\theta)$ of the actual policy gradients
$\nabla_{\theta}J(\theta)$. This is done by constructing surrogate objectives
$J_{*}$ such that
$\hat{\nabla}_{\theta}J(\theta)=\nabla_{\theta}J_{*}(\theta)$. Additionally,
most algorithms focus on stabilizing learning by regularizing the policy [5]
and reducing the variance of $\hat{\nabla}_{\theta}J(\theta)$ [77]. In this
section, we derive the most prominent777As determined by their impact on
subsequent research and the adoption rate by users. algorithms before than
comparing them in the final subsection.

###  4.1 REINFORCE

REINFORCE (REward Increment = Non-negative Factor $\times$ Offset
Reinforcement $\times$ Characteristic Eligibility) [88] is the earliest policy
gradient algorithm. While this algorithm precedes the formulation of the
Policy Gradient Theorem, REINFORCE can be seen as a straightforward
application of it. By using Monte Carlo methods [75] to estimate $Q_{\pi}$ in
Equation (13), i.e. by sampling entire episodes to compute the sample returns
$G_{t}=\sum_{k=0}^{T}\gamma^{k}r_{t+k+1}$, REINFORCE samples policy gradients

$\hat{\nabla}_{\theta}J(\theta)=G_{t}\nabla_{\theta}\ln\pi_{\theta}(a_{t}\mid
s_{t}).$

Using the generic policy gradient update from Equation (3) results in the
gradient ascend updates

$\theta_{\text{new}}=\theta+\alpha
G_{t}\nabla_{\theta}\ln\pi_{\theta}(a_{t}\mid s_{t})$

where $\alpha\in(0,1]$ is the learning rate determining the step size of the
gradient steps and is set as a hyperparameter. At times, REINFORCE is extended
by subtracting some baseline value from $G_{t}$ to reduce variance [88]. The
pseudocode for REINFORCE is presented in Algorithm 3.

Algorithm 3 REINFORCE

$\alpha\in(0,1],\gamma\in[0,1]$

Initialize $\theta$ at random

for all episodes do

Generate trajectory $s_{0},a_{0},r_{1},s_{1}\ldots,s_{T}$ under policy
$\pi_{\theta}$

for $t=1,\ldots,T$ do

$G_{t}\leftarrow\sum_{k=t}^{T}\gamma^{k-t}r_{k}$ $\triangleright$ estimate
expected return $Q_{\pi}$

$\theta\leftarrow\theta+\alpha G_{t}\nabla_{\theta}\ln\pi_{\theta}(a_{t}\mid
s_{t})$ $\triangleright$ update policy parameters

end for

end for

###  4.2 A3C

Instead of estimating $Q_{\pi}$ directly via sampling as in REINFORCE, we can
alternatively learn such an estimate via function approximation. Algorithms
that use this approach to learn a parameterized action-value function
$\hat{Q}_{\phi}$ or value function $\hat{V}_{\phi}$ (called critic) with
parameters $\phi$ in addition to learning the parameterized policy
$\pi_{\theta}$ (called actor) are referred to as actor-critic algorithms [75].
Note that in practice the actor and the critic may also share parameters.

The most archetypical representative of this class of algorithms is
Asynchronous Advantage Actor-Critic (A3C) [54]. A3C builds on two main ideas
from which the algorithm’s name originates. First, as suggested by the results
from Section 3.2, A3C learns an estimate $\hat{A}_{\phi}$ of the advantage
function indirectly by learning an estimate $\hat{V}_{\phi}$ of the value
function. Second, A3C introduces the concept of using multiple parallel actors
to interact with the environment to stabilize training. We will discuss both
ideas in detail below. The algorithm samples policy gradients

$\hat{\nabla}_{\theta}J(\theta)=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s,a\in\mathcal{D}}\hat{A}_{\phi}(s,a)\nabla_{\theta}\ln\pi_{\theta}(a\mid
s),$

where $\mathcal{D}$ is a batch of transitions collected by the actors. The
pseudocode for A3C is presented in Algorithm 4.

In the original work [55], the advantage function is estimated via

$\hat{A}_{\phi}(s_{t},a_{t})=\Bigl{(}\sum^{k-1}_{i=0}\gamma^{i}r_{t+i}+\gamma^{k}\hat{V}_{\phi}(s_{t+k})\Bigr{)}-\hat{V}_{\phi}(s_{t}).$
(14)

To understand this estimate, observe that

$\displaystyle A_{\pi}(s_{t},a_{t})$
$\displaystyle=Q_{\pi}(s_{t},a_{t})-V_{\pi}(s_{t})$
$\displaystyle=\mathbb{E}_{\pi}\Bigl{[}R_{t+1}+\gamma V_{\pi}(S_{t+1})\mid
S_{t}=s_{t},A_{t}=a_{t}\Bigl{]}-V_{\pi}(s_{t})$
$\displaystyle=\mathbb{E}_{\pi}\Bigl{[}R_{t+1}+\gamma
R_{t+2}+\gamma^{2}V_{\pi}(S_{t+2})\mid
S_{t}=s_{t},A_{t}=a_{t}\Bigl{]}-V_{\pi}(s_{t})$ $\displaystyle\;\;\vdots$
$\displaystyle=\mathbb{E}_{\pi}\Bigl{[}\sum^{k-1}_{i=0}\gamma^{i}R_{t+i}+\gamma^{k}V_{\pi}(S_{t+k})\mid
S_{t}=s_{t},A_{t}=a_{t}\Bigl{]}-V_{\pi}(s_{t}),$

for any $k\in\mathbb{N}$, which follows from the definition of the value and
action-value functions as well as their relationship. Sampling this n-step
temporal difference [75] expression and replacing $V_{\pi}$ with our learned
$\hat{V}_{\phi}$ yields Equation (14). Simultaneously to updating
$\pi_{\theta}$, we learn $\hat{V}_{\phi}$ by minimizing the mean squared error
loss

$\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\biggl{(}\Bigl{(}\sum^{k-1}_{i=0}\gamma^{i}r_{t+i}+\gamma^{k}\hat{V}_{\phi}(s_{t+k})\Bigr{)}-\hat{V}_{\phi}(s_{t})\biggr{)}^{2}$

over $\phi$ via SGD. Note that the inner expression is identical to the right
hand side in Equation (14). In Equation (14), we compute the difference
between the estimated return when choosing action $a_{t}$ in state $s_{t}$ and
the estimated return when in state $s_{t}$, under policy $\pi$ respectively.
However, $a_{t}$ is sampled from $\pi$ such that in expectation this
difference should be 0 for the true value function $V_{\pi}$. Hence, we
minimize this squared difference to optimize $\phi$ by treating the first
term, $\sum^{k-1}_{i=0}\gamma^{i}r_{t+i}+\gamma^{k}\hat{V}_{\phi}(s_{t+k})$,
as independent of $\phi$.

The use of multiple parallel actors is justified as follows. Deep RL is
notoriously unstable, which was first resolved by off-policy algorithms using
replay buffers that store and reuse sampled transitions for multiple updates
[55]. As an alternative, [54] propose using several actors
$\pi^{(1)}_{\theta},\ldots,\pi^{(k)}_{\theta}$ to decrease noise by
accumulating the gradients over multiple trajectories. These accumulated
gradients are applied to a centrally maintained copy of $\theta$, which is
then redistributed to each actor. By doing this asynchronously, each actor has
a potentially unique set of parameters at any point in time compared to the
other actors. This decreases the correlation of the sampled trajectories
across actors, which can further stabilize learning.

Algorithm 4 A3C

$n\in\mathbb{N}$, $\alpha\in(0,1],\gamma\in[0,1]$,
$t_{\mathrm{MAX}}\in\mathbb{N}$, $T_{\mathrm{MAX}}\in\mathbb{N}$

Initialize $\theta$ and $\phi$ at random

for $i=1,\ldots,n$ do $\triangleright$ in parallel

while $T\leq T_{\mathrm{MAX}}$ do

$d\theta\leftarrow 0,\ d\phi\leftarrow 0$ $\triangleright$ reset gradients

$\theta^{(i)}\leftarrow\theta,\ \phi^{(i)}\leftarrow\phi$ $\triangleright$
synchronize parameters on actors

$s_{t}\sim p_{0}$ $\triangleright$ sample start state

$t_{\mathrm{start}}\leftarrow t$

while $s_{t}$ not terminal and $t-t_{\mathrm{start}}\leq t_{\mathrm{MAX}}$ do

$a_{t}\sim\pi_{\theta^{(i)}}$ $\triangleright$ sample action

$s_{t+1},r_{t+1}\sim P(s_{t},a_{t})$ $\triangleright$ sample next state and
reward

$t\leftarrow t+1,\ T\leftarrow T+1$

end while

$R\leftarrow\begin{cases}0&\text{if }s_{t}\text{ is terminal}\\\
V_{\phi^{(i)}}(s_{t})&\text{else}\end{cases}$ $\triangleright$ bootstrap if
necessary

for $j=t-1,\ldots,t_{\mathrm{start}}$ do

$R\leftarrow r_{j}+\gamma R$

$A=R-V_{\phi^{(i)}}(s_{j})$

$d\theta\leftarrow
d\theta+\nabla_{\theta^{(i)}}\ln\pi_{\theta^{(i)}}(a_{j}\mid s_{j})A$
$\triangleright$ accumulate gradients

$d\phi\leftarrow d\phi+\nabla_{\phi^{(i)}}(R-V_{\phi^{(i)}}(s_{j}))^{2}$
$\triangleright$ accumulate gradients

end for

update $\theta$ and $\phi$ using $d\theta$ and $d\phi$ via gradient ascent /
descent

end while

end for

As a final implementation detail, the policy loss function of A3C, from which
the policy gradients are obtained, is typically augmented with an entropy
bonus for the policy. Thus, the policy gradients become

$\hat{\nabla}_{\theta}J(\theta)=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\Biggl{(}\biggl{(}\sum^{k-1}_{i=0}\gamma^{i}r_{t+i}+\gamma^{k}\hat{V}_{\phi}(s_{t+k})-\hat{V}_{\phi}(s_{t})\biggr{)}\nabla_{\theta}\ln\pi_{\theta}(a_{t}\mid
s_{t})+\beta\nabla_{\theta}H(\pi_{\theta}(\cdot\mid s_{t}))\Biggr{)},$

where $H$ is the entropy (see Definition D.4) and the entropy coefficient
$\beta$ is a hyperparameter. This entropy bonus, first proposed by [89],
regularizes the policy such that it does not prematurely converges to a
suboptimal policy. By rewarding entropy, the policy is encouraged to spread
probability mass over actions which improves exploration [54].

###  4.3 TRPO

Excessively large changes in the policy can result in instabilities during the
training of RL algorithms. Even small changes in policy parameters $\theta$
can lead to significant changes in the resulting policy and its performance.
Hence, small step sizes during gradient ascent cannot fully remedy this
problem and would impair the sample efficiency of the algorithm [3]. Trust
Region Policy Optimization (TRPO) [69] mitigates these issues by imposing a
trust region constraint on the Kullback-Leibler (KL) divergence (see
Definition D.5) between consecutive policies. In addition, TRPO uses an off-
policy correction through importance sampling as discussed in Section 3.3 to
account for the interleaved optimization and collection of transitions.

TRPO samples gradients

$\hat{\nabla}_{\theta}J(\theta)=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s,a\in\mathcal{D}}\hat{A}_{\phi}(s,a)\nabla_{\theta}\frac{\pi_{\theta}(a\mid
s)}{\pi_{\text{old}}(a\mid s)}$

and postprocesses them as detailed below to solve the approximate trust region
optimization problem

$\displaystyle\begin{split}\max_{\theta}&\quad\biggl{(}J_{\text{TRPO}}(\theta)=\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi_{\text{old}}}\biggl{[}\hat{A}_{\phi}(S,A)\frac{\pi_{\theta}(A\mid
S)}{\pi_{\text{old}}(A\mid S)}\biggr{]}\biggr{)}\\\ \text{subject
to}&\quad\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
S)\>\|\>\pi_{\theta}(\cdot\mid S))\bigr{]}\leq\delta\end{split}$

where $\pi_{\text{old}}=\pi_{\theta_{\text{old}}}$ is the previous policy and
$\theta_{\text{old}}$ the corresponding parameters. This optimization problem
is an approximation to an objective with convergence guarantees, which we will
show in the following. We start by presenting [69]’s main theoretical result.
Consider the objective of maximizing the expected return
$\mathbb{E}_{S_{0}\sim p_{0},\pi}\bigl{[}G_{0}\bigr{]}$ under policy $\pi$,
which we denote as $\eta(\pi)$ here. Let $L_{\pi}$ be the following local
approximation of $\eta$:

$L_{\pi}(\tilde{\pi})=\eta(\pi)+\int_{s\in\mathcal{S}}d^{\pi}(s)\int_{a\in\mathcal{A}}\tilde{\pi}(a\mid
s)A_{\pi}(s,a)\>da\>ds,$

with $L_{\pi_{\theta}}(\pi_{\theta})=\eta(\pi_{\theta})$ and
$\nabla_{\theta}L_{\pi_{\theta_{0}}}(\pi_{\theta})|_{\theta=\theta_{0}}=\nabla_{\theta}\eta(\pi_{\theta})|_{\theta=\theta_{0}}$
[38]. Based on the total variation divergence $D_{TV}$ (see Definition D.6),
we define

$D^{max}_{TV}(\pi,\tilde{\pi})\coloneqq\max_{s\in\mathcal{S}}D_{TV}(\pi(\cdot\mid
s)\|\tilde{\pi}(\cdot\mid s)).$

Then, we have [69]:

######  Theorem 4.1.

Let $\alpha=D^{max}_{TV}(\pi_{\text{old}},\pi_{\text{new}})$, then

$\eta(\pi_{\text{new}})\geq
L_{\pi_{\text{old}}}(\pi_{\text{new}})-\frac{4\varepsilon\gamma}{(1-\gamma)^{2}}\alpha^{2},$
(15)

where $\varepsilon=\max_{s\in\mathcal{S},a\in\mathcal{A}}\lvert
A_{\pi}(s,a)\rvert$.

See the appendix in [69] for a proof. By using the relationship between total
variation divergence and KL divergence $D_{TV}(\pi\|\tilde{\pi})^{2}\leq
D_{KL}(\pi\|\tilde{\pi})$ [58] and setting
$D^{max}_{KL}(\pi,\tilde{\pi})\coloneqq\max_{s\in\mathcal{S}}D_{KL}(\pi(\cdot\mid
s)\|\tilde{\pi}(\cdot\mid s))$ and
$C=\frac{4\varepsilon\gamma}{(1-\gamma)^{2}}$, we derive the following lower
bound for the objective from Equation (15):

$\eta(\pi_{\text{new}})\geq
L_{\pi_{\text{old}}}(\pi_{\text{new}})-CD^{max}_{KL}(\pi_{\text{old}},\pi_{\text{new}})$
(16)

Iteratively maximizing the right-hand side yields a sequence of policies
$\pi_{i},\pi_{i+1},\pi_{i+2},\ldots$ with the monotonic improvement guarantee
$\eta(\pi_{i})\leq\eta(\pi_{i+1})\leq\eta(\pi_{i+2})\leq\ldots$. This is
because we have equality in (16) for $\pi_{\text{new}}=\pi_{\text{old}}$ and
hence

$\eta(\pi_{i+1})-\eta(\pi_{i})\geq\Bigl{(}L_{\pi_{i}}(\pi_{i+1})-CD^{max}_{KL}(\pi_{i},\pi_{i+1})\Bigr{)}-\Bigl{(}L_{\pi_{i}}(\pi_{i})-CD^{max}_{KL}(\pi_{i},\pi_{i})\Bigr{)},$

which is non-negative as we maximize over $\pi$ each iteration. Thus, we could
construct a Minorization-Maximization-type algorithm [37] which maximizes the
right-hand side of Inequality (16) at each iteration and is thereby guaranteed
to converge to an optimum as the objective is bounded.

Such an algorithm would be impractical as it requires evaluating the advantage
function at every point in the state-action product space
$\mathcal{S}\times\mathcal{A}$ and the KL penalty at every point in the state
space $\mathcal{S}$. Hence, [69] apply several approximations to the objective
stemming from Inequality (16). We replace the KL penalty, which would yield
restrictively small step sizes given by $C$, by a trust region constraint:

$\displaystyle\begin{split}\max_{\theta}&\quad
L_{\pi_{\text{old}}}(\pi_{\theta})\\\ \text{subject to}&\quad
D^{\text{max}}_{KL}(\pi_{\text{old}},\pi_{\theta})\leq\delta.\end{split}$

To avoid computing $D^{\text{max}}_{KL}$, we use the average KL divergence

$\bar{D}^{\pi_{\text{old}}}_{KL}(\pi\|\tilde{\pi})\coloneqq\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}(\pi(\cdot\mid S)\|\tilde{\pi}(\cdot\mid
S))\bigr{]}$

between policies as heuristic constraint, which we can sample. Further, we
rewrite the surrogate objective
$\max_{\theta}L_{\pi_{\text{old}}}(\pi_{\theta})$ as an expectation over the
old policy $\pi_{\text{old}}$ via importance sampling. Note that
$\eta(\pi_{\text{old}})$ is a constant w.r.t $\theta$:

$\displaystyle\operatorname*{arg\,max}_{\theta}L_{\pi_{\text{old}}}(\pi_{\theta})$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\biggl{(}\eta(\pi_{\text{old}})+\int_{s\in\mathcal{S}}d^{\pi_{\text{old}}}(s)\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)A_{\pi_{\text{old}}}(s,a)\>da\>ds\biggr{)}$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\int_{s\in\mathcal{S}}d^{\pi_{\text{old}}}(s)\int_{a\in\mathcal{A}}\pi_{\theta}(a\mid
s)A_{\pi_{\text{old}}}(s,a)\>da\>ds$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\int_{s\in\mathcal{S}}d^{\pi_{\text{old}}}(s)\int_{a\in\mathcal{A}}\frac{\pi_{\text{old}}(a\mid
s)}{\pi_{\text{old}}(a\mid s)}\pi_{\theta}(a\mid
s)A_{\pi_{\text{old}}}(s,a)\>da\>ds$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi_{\text{old}}}\biggl{[}\frac{\pi_{\theta}(A\mid
S)}{\pi_{\text{old}}(A\mid S)}A_{\pi_{\text{old}}}(S,A)\biggr{]}.$

Using these modifications, we are now left with solving the trust region
problem

$\displaystyle\begin{split}\max_{\theta}&\quad\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi_{\text{old}}}\biggl{[}\frac{\pi_{\theta}(A\mid
S)}{\pi_{\text{old}}(A\mid S)}A_{\pi_{\text{old}}}(S,A)\biggr{]}\\\
\text{subject to}&\quad\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\Bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
S)\|\pi_{\theta}(\cdot\mid S))\Bigr{]}\leq\delta.\end{split}$ (17)

To approximately solve this constrained problem, [69] use backtracking line
search, where the search direction is computed by Taylor-expanding (see
Theorem D.12) the objective function and the constraint. Let
$g=\nabla_{\theta}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi_{\text{old}}}\Bigl{[}\frac{\pi_{\theta}(A\mid
S)}{\pi_{\text{old}}(A\mid S)}A_{\pi_{\text{old}}}(S,A)\Bigr{]}$.
Approximating $L_{\pi_{\text{old}}}(\pi_{\theta})$ to first order around
$\theta_{\text{old}}$ yields

$L_{\pi_{\text{old}}}(\pi_{\theta})\approx
g^{\mathsf{T}}(\theta-\theta_{\text{old}}),$

where we again ignored the constant $\eta(\pi_{\text{old}})$. The quadratic
approximation of the constraint at $\theta_{\text{old}}$ is

$\bar{D}^{\pi_{\text{old}}}_{KL}(\pi\|\tilde{\pi})\approx\frac{1}{2}(\theta-\theta_{\text{old}})^{\mathsf{T}}H(\theta-\theta_{\text{old}}),$

where $H$ is the Fisher information matrix, which is estimated via

$\hat{H}_{i,j}=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s\in\mathcal{D}}\frac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}D_{KL}(\pi_{\text{old}}(\cdot\mid
s)\|\pi(\cdot\|s)),$

albeit the full matrix is not required. We solve the resulting approximate
optimization problem analytically using Lagrangian duality methods [12]
leading to

$\theta_{\text{new}}=\theta_{\text{old}}+\sqrt{\frac{2\delta}{g^{\mathsf{T}}\hat{H}^{-1}g}}\hat{H}^{-1}g.$

However, due to the Taylor approximations, this solution may not satisfy the
original trust region constraint or may not improve the surrogate objective of
Problem (17). Therefore, TRPO employs backtracking line search along the
search direction $H^{-1}g$ with search parameter $\beta\in(0,1)$:

$\theta_{\text{new}}=\theta_{\text{old}}+\beta^{m}\sqrt{\frac{2\delta}{g^{\mathsf{T}}H^{-1}g}}H^{-1}g.$

We choose the exponent $m$ as the smallest non-negative integer such that the
trust region constraint is satisfied and the surrogate objective improves. We
circumvent the computationally expensive matrix inversion of $H$ for the
search direction $d\approx H^{-1}g$ by computing $d$ via the conjugate
gradient algorithm [30]. To further reduce the computational costs, the
Fisher-vector products in this process can also be only calculated on a subset
of the dataset $\mathcal{D}$ of sampled transitions.

Algorithm 5 TRPO

$\delta\in\mathbb{R}$, $b\in(0,1)$, $K\in\mathbb{N}$, $\alpha\in(0,1]$,
$U\in\mathbb{N}$, $T\in\mathbb{N}$

Initialize $\theta$ and $\phi$ at random

$t\leftarrow 0$

while $t\leq T$ do

for $i=1,\ldots,U$ do

$a\sim\pi_{\theta}$ $\triangleright$ sample action

$\beta(a\mid s)\leftarrow\pi_{\theta}(a\mid s)$

$s,r\sim P(s,a)$ $\triangleright$ sample next state and reward

$t\leftarrow t+1$

Store $(a,s,r,\beta(a\mid s))$ in $\mathcal{D}$

end for

for all epochs do

Compute returns $R$ and advantages $A$

$g\leftarrow\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\nabla_{\theta}\frac{\pi_{\theta}(a\mid
s)}{\beta(a\mid s)}A$

Compute $\hat{H}$ as the Hessian of the sample average KL-divergence

Compute $d\approx\hat{H}^{-1}g$ via conjugate gradient algorithm

$m\leftarrow 0$

repeat

$\theta\leftarrow\theta_{\text{old}}+b^{m}\sqrt{\frac{2\delta}{d^{\mathsf{T}}\hat{H}d}}d$

$m\leftarrow m+1$

until (sample loss improves and KL constraint satisfied) or $m>K$

$d\phi\leftarrow\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\nabla_{\phi}(R-V_{\phi}(s))^{2}$

Update $\phi$ using $d\phi$ via gradient descent

end for

end while

[69] do not specify an advantage estimator to be used in TRPO. The algorithm
is commonly used with either the estimator used by A3C or the one which we
present in the next subsection. TRPO is typically used with multiple parallel
actors as A3C. The pseudocode for TRPO is presented in Algorithm 5. We remark
that while being a policy-based algorithm, TRPO does not strictly adhere to
Definition 2.2 as it solves a constrained optimization problem via line
search. Yet, it does compute gradients of its objective function w.r.t. the
policy parameters and therefore we treat it as a policy gradient algorithm.

###  4.4 PPO

Given the complexity of TRPO, Proximal Policy Optimization (PPO) [71] is
designed to enforce comparable constraints on the divergence between
consecutive policies during the learning process while simplifying the
algorithm to not require second-order methods. This is achieved by
heuristically flattening the gradients outside of an approximate trust region
around the old policy. In addition, PPO uses a novel method to learn an
estimate of the advantage function.

Let $r_{\theta}(a\mid s)=\frac{\pi_{\theta}(a\mid s)}{\pi_{\text{old}}(a\mid
s)}$. Then, PPO uses the following estimate of the policy gradients:

$\hat{\nabla}_{\theta}J(\theta)=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s,a\in\mathcal{D}}\hat{A}_{\phi}(s,a)\nabla_{\theta}\min\biggl{\\{}r_{\theta}(a\mid
s),\text{clip}\Bigl{(}r_{\theta}(a\mid
s),1-\varepsilon,1+\varepsilon\Bigr{)}\biggr{\\}}.$ (18)

Here, the clip-function
$\text{clip}\colon\mathbb{R}\times\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$
is defined by

$\text{clip}(x,a,b)=\begin{cases}a&\text{if }x<a,\\\ x&\text{if }a\leq x\leq
b,\\\ b&\text{if }b<x.\end{cases}$

and is applied element-wise to $r_{\theta}$. $\varepsilon$ is a
hyperparameter.

This clipped objective conservatively removes the incentive for moving the new
policy to far away from the old one. Intuitively, this can be seen as follows.
We distinguish two cases: positive and negative estimated advantages
$\hat{A}(s,a)$, i.e. whether action $a$ is good or bad. If $\hat{A}(s,a)>0$,
the surrogate objective $J_{\text{PPO}}(\theta)$ increases when $a$ becomes
more likely. Similarly, if $\hat{A}(s,a)<0$, $J_{\text{PPO}}(\theta)$
increases when $a$ becomes less likely. Hence, we want to adjust the policy
parameters $\theta$ accordingly. However, by clipping the policy ratio
$r_{\theta}$, this positive effect on the objective function disappears once
we move outside the clip range. This clipping process is conservative as we
only clip if the objective function would improve. If the policy is changed in
the opposite direction such that $J_{\text{PPO}}(\theta)$ decreases,
$r_{\theta}$ is not clipped due to taking the minimum in Equation (18). Figure
3 illustrates this explanation. The pseudocode for PPO is presented in
Algorithm 6.

$0$$1$$1+\varepsilon$$r_{\theta}$$J_{\text{PPO}}(\theta)$ (a) $A>0$

$0$$1+\varepsilon$$1$$r_{\theta}$$J_{\text{PPO}}(\theta)$ (b) $A<0$

Figure 3: Illustration of the conservative clipping of PPO’s objective
function, which is shown as a function of the ratio $r_{\theta}$ for a single
transition depending on whether the advantages are positive (a) or negative
(b). Replicated from [71]. Algorithm 6 PPO

$\varepsilon\in\mathbb{R}$, $\alpha\in(0,1],\gamma\in[0,1]$,
$\lambda\in[0,1]$, $U\in\mathbb{N}$, $T\in\mathbb{N}$

Initialize $\theta$ and $\phi$ at random

$t\leftarrow 0$

while $t\leq T$ do

for $i=1,\ldots,U$ do

$a\sim\pi_{\theta}$ $\triangleright$ sample action

$\beta(a\mid s)\leftarrow\pi_{\theta}(a\mid s)$

$s,r\sim P(s,a)$ $\triangleright$ sample next state and reward

$t\leftarrow t+1$

Store $(a,s,r,\beta(a\mid s))$ in $\mathcal{D}$

end for

for all epochs do

$R,A\leftarrow\text{computeGAE}(v,r,\lambda,\gamma)$ $\triangleright$ Compute
returns and advantages

$d\theta\leftarrow\nabla_{\theta}\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\min\bigl{(}\frac{\pi(a\mid
s)}{\beta(a\mid s)},\text{clip}(\frac{\pi(a\mid s)}{\beta(a\mid
s)},1-\varepsilon,1+\varepsilon)\bigr{)}A$

$d\phi\leftarrow\nabla_{\phi}\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}(R-V_{\phi}(s))^{2}$

update $\theta$ and $\phi$ using $d\theta$ and $d\phi$ via gradient ascent /
descent

end for

end while

To compute the estimate $\hat{A}_{\phi}$ of the advantage function, PPO uses
generalized advantage estimation (GAE) [70] to further reduce the variance of
gradients. GAE computes the estimated advantage as

$\hat{A}_{\phi}(s_{t},a_{t})=\sum^{T-1}_{i=t}(\gamma\lambda)^{i-t}\delta_{i},$
(19)

where $\delta_{i}=r_{i}+\gamma\hat{V}_{\phi}(s_{i+1})-\hat{V}_{\phi}(s_{i})$.
The value function estimate $\hat{V}_{\phi}$ is learned by minimizing

$\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\Bigl{(}\bigl{(}\hat{A}_{\phi}(s,a)+\hat{V}_{\phi}(s)\bigr{)}-\hat{V}_{\phi}(s)\Bigr{)}^{2},$

where the first term is treated as independent of $\phi$. GAE relates to the
idea of eligibility traces [74] to use both the sampled rewards and the
current value function estimate on every time step. By computing such an
exponentially weighted estimator, GAE reduces the variance of the policy
gradients at the cost of introducing a slight bias to the value function
estimate [70]. The hyperparameters $\gamma$ and $\lambda$ both adjust this
bias-variance tradeoff. $\gamma$ does so by scaling the value function
estimate $\hat{V}$ whereas $\lambda$ controls the dependence on delayed
rewards. Note that GAE is a strict generalization of A3C’s advantage estimate
as Equation (19) reduces to Equation (14) when $\lambda=1$. The pseudocode for
GAE is presented in Algorithm 7.

Algorithm 7 GAE

$\gamma\in[0,1]$, $\lambda\in[0,1]$

rewards $(r_{k})^{t+n}_{k=t}$, values $(v_{k})^{t+n+1}_{t=k}$

$A_{t},\ldots,A_{t+n}\leftarrow 0$

$x\leftarrow 0$

for $i=t+n,\ldots,t$ do

if transition was terminal then

$\omega\leftarrow 1$

else

$\omega\leftarrow 0$

end if

$\delta\leftarrow r_{i}+\gamma\cdot v_{i+1}\cdot(1-\omega)-v_{i}$

$x\leftarrow\delta+\gamma\cdot\lambda\cdot(1-\omega)\cdot x$

$A_{i}\leftarrow x$

end for

for $i=t,\ldots,t+n$ do

$R_{i}\leftarrow A_{i}+v_{i}$

end for

Beyond these main innovations, PPO uses several implementational details to
improve learning. PPO conducts multiple update epochs for each batch of data
such that several gradient descent steps are based on the same transitions to
increase sample efficiency and speed up learning. Moreover, PPO commonly
augments its surrogate objective with an entropy bonus
$H(\pi_{\theta}(\cdot\mid s))$ and uses multiple actors similarly to A3C.
Lastly, we note that further algorithms have been proposed as modifications of
PPO, e.g. Phasic Policy Gradients [16] and Robust Policy Optimization [61],
which we will not discuss further as they only modify minor details.

###  4.5 V-MPO

In the previous algorithms, we learn a policy from the control perspective by
selecting actions to maximize expected rewards. In this subsection, we
consider an alternative formulation of RL problems, which casts them as
probabilistic inference problems of estimating posterior policies that are
consistent with a desired outcome [1]. This problem is then solved via
Expectation Maximization (EM) [20]. This procedure was first proposed in the
off-policy algorithm Maximum a-posteriori Policy Optimization (MPO) [2, 1].
Here, we discuss its on-policy variant V-MPO [73], where the "V" in the name
refers to learning the value function $V_{\pi}$ instead of $Q_{\pi}$ as in
MPO.

The main idea of V-MPO is to find a maximum a posteriori estimate of the
policy by sequentially finding a tight lower bound on the posterior and then
maximizing this lower bound. This problem can be transformed into the
objective function

$J_{\text{V-MPO}}(\theta,\eta,\nu)=\mathcal{L}_{\pi}(\theta)+\mathcal{L}_{\eta}(\eta)+\mathcal{L}_{\nu}(\theta,\nu),$

where $\mathcal{L}_{\pi}$ is the policy loss

$\mathcal{L}_{\pi}(\theta)=-\sum_{a,s\in\tilde{\mathcal{D}}}\frac{\exp\Bigl{(}\frac{\hat{A}_{\phi}(s,a)}{\eta}\Bigr{)}}{\sum_{a^{\prime},s^{\prime}\in\tilde{\mathcal{D}}}\exp\Bigl{(}\frac{\hat{A}_{\phi}(s^{\prime},a^{\prime})}{\eta}\Bigr{)}}\ln\pi_{\theta}(a\mid
s),$ (20)

$\mathcal{L}_{\eta}$ is the temperature loss

$\mathcal{L}_{\eta}(\eta)=\eta\varepsilon_{\eta}+\eta\ln\Biggl{[}\frac{1}{\lvert\tilde{\mathcal{D}}\rvert}\sum_{a,s\in\tilde{\mathcal{D}}}\exp\biggl{(}\frac{\hat{A}_{\phi}(s,a)}{\eta}\biggr{)}\Biggr{]}$
(21)

and $\mathcal{L}_{\nu}$ is the trust-region loss

$\displaystyle\begin{split}\mathcal{L}_{\nu}(\theta,\nu)&=\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s\in\mathcal{D}}\biggl{(}\nu\biggl{(}\varepsilon_{\nu}-\mathrm{sg}\Bigl{[}\Bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
s)\>\|\>\pi_{\theta}(\cdot\mid
s))\Bigr{]}\Bigr{]}\biggr{)}+\mathrm{sg}\bigl{[}\bigl{[}\nu\bigr{]}\bigr{]}D_{KL}\bigl{(}\pi_{\text{old}}(\cdot\mid
s)\>\|\>\pi_{\theta}(\cdot\mid s)\bigr{)}\biggr{)}.\end{split}$ (22)

Here, $\mathrm{sg}[[\cdot]]$ is a stop-gradient operator, meaning its
arguments are treated as constants when computing gradients, $\eta$ is a
learnable temperature parameter, $\nu$ is a learnable KL-penalty parameter,
$\varepsilon_{\nu}$ and $\varepsilon_{\eta}$ are hyperparameters,
$\mathcal{D}$ is a batch of transitions and
$\tilde{\mathcal{D}}\subset\mathcal{D}$ is the half of these transitions with
the largest advantages. We will provide a sketch of how to derive this
objective function in the following. We refer the interested reader to
Appendix Appendix C for a more detailed derivation.

Let $p_{\theta}(s,a)=\pi_{\theta}(a\mid s)d^{\pi_{\theta}}(s)$ denote the
joint state-action distribution under policy $\pi_{\theta}$ conditional on the
parameters $\theta$. Let $\mathcal{I}$ be a binary random variable whether the
updated policy $\pi_{\theta}$ is an improvement over the old policy
$\pi_{\text{old}}$, i.e. $\mathcal{I}=1$ if it is an improvement. We assume
the conditional probability of $\pi_{\theta}$ being an improvement given a
state $s$ and an action $a$ is proportional to the following expression

$p_{\theta}(\mathcal{I}=1\mid
s,a)\propto\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}.$ (23)

Given the desired outcome $\mathcal{I}=1$, we seek the posterior distribution
conditioned on this event. Specifically, we seek the maximum a posteriori
estimate

$\displaystyle\begin{split}\theta^{*}&=\operatorname*{arg\,max}_{\theta}\bigl{[}p_{\theta}(\mathcal{I}=1)\rho(\theta)\bigr{]}\\\
&=\operatorname*{arg\,max}_{\theta}\bigl{[}\ln
p_{\theta}(\mathcal{I}=1)+\ln\rho(\theta)\bigr{]},\end{split}$ (24)

where $\rho$ is some prior distribution. $\ln p_{\theta}(\mathcal{I}=1)$ can
be rewritten as

$\ln
p_{\theta}(\mathcal{I}=1)=\mathbb{E}_{S,A\sim\psi}\biggl{[}\ln\frac{p_{\theta}(\mathcal{I}=1,S,A)}{\psi(S,A)}\biggr{]}+D_{KL}\bigl{(}\psi\>\|\>p_{\theta}(\cdot,\cdot\mid\mathcal{I}=1)\bigr{)}$
(25)

for some distribution $\psi$ over $\mathcal{S}\times\mathcal{A}$. Observe
that, since the KL divergence is non-negative, the first term is a lower bound
for $\ln p_{\theta}(\mathcal{I}=1)$. Akin to EM algorithms, V-MPO now iterates
by choosing the variational distribution $\psi$ in the expectation (E) step to
minimize the KL divergence in Equation (25) to make the lower bound as tight
as possible. In the maximization (M) step, we maximize this lower bound and
the prior $\ln\rho(\theta)$ to obtain a new estimate of $\theta^{*}$ via
Equation (24).

First, we consider the E-step. Under the proportionality assumption (23), we
turn the problem of finding a variational distribution $\psi$ to minimize
$D_{KL}(\psi\>\|\>p_{\theta_{\text{old}}}(\cdot,\cdot\mid\mathcal{I}=1))$ into
an optimization problem over the temperature $\eta$. This is formulated as a
constrained problem subject to a bound on the KL divergence between $\psi$ and
the previous state-action distribution $p_{\theta_{\text{old}}}$ while
ensuring that $\psi$ is a state-action distribution. To enable optimizing
$\eta$ via gradient descent, we transform this constrained problem into an
unconstrained problem via Lagrangian relaxation, which emits both the form of
the variational distribution

$\psi(s,a)=\frac{p_{\theta_{\text{old}}}(s,a)\>p_{\theta_{\text{old}}}(\mathcal{I}=1\mid
s,a)}{\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\>p_{\theta_{\text{old}}}(\mathcal{I}=1\mid
s,a)\>da\>ds}$

and the temperature loss (21)

$\mathcal{L}_{\eta}(\eta)=\eta\varepsilon_{\eta}+\eta\ln\biggl{(}\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}\>da\>ds\biggr{)}.$

[73] find that using only the highest 50 % of advantages per batch when
sampling these expressions, i.e. replacing $\mathcal{D}$ with
$\tilde{\mathcal{D}}$, substantially improves the algorithm. The advantage
function $A_{\pi}$ is estimated by $\hat{A}_{\phi}$, which is learned as in
A3C.

Then, in the M-Step we solve the maximum a posterior estimation problem (24)
over the policy parameters $\theta$ for the constructed variational
distribution $\psi(s,a)$ and the thereby implied lower bound. This lower
bound, i.e. the first term in Equation (25), becomes the weighted maximum
likelihood policy loss (20)

$\mathcal{L}_{\pi}(\theta)=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\pi_{\theta}(a\mid
s)\>da\>ds$

after dropping terms independent of $\theta$. This loss is computed over the
same reduced batch $\tilde{\mathcal{D}}$ as the temperature loss, effectively
assigning out-of-sample transitions a weight of zero. Simultaneously, we want
to maximize the prior $\rho(\theta)$ according to the maximization problem
(24). V-MPO follows TRPO and PPO to choose a prior such that the new policy is
kept close to the previous one, i.e.

$\rho(\theta)=-\nu\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}\bigl{(}\pi_{\text{old}}(\cdot\mid
S)\|\pi_{\theta}(\cdot\mid S)\bigr{)}\bigr{]},~$

with learnable parameter $\nu$. However, optimizing the resulting sample-based
maximum likelihood objective directly tends to result in overfitting. Hence, a
sequence of transformations is applied. First, the prior is transformed into a
hard constraint on the KL divergence when optimizing the policy loss. To
employ gradient-based optimization, we use Lagrangian relaxation to transform
this constrained optimization problem back into an unconstrained problem and
use a coordinate-descent strategy to simultaneously optimize for $\theta$ and
$\nu$. This can equivalently be written via the stop-gradient operator
yielding the trust-region loss (22).

Algorithm 8 V-MPO

$\eta\in\mathbb{R}$, $\nu\in\mathbb{R}$, $\varepsilon_{\eta}\in\mathbb{R}$,
$\varepsilon_{\nu}\in\mathbb{R}$, $U\in\mathbb{N}$, $T\in\mathbb{N}$

Initialize $\theta$ and $\phi$ at random

$t\leftarrow 0$

while $t\leq T$ do

for $i=1,\ldots,U$ do

$a\sim\pi_{\theta}$ $\triangleright$ sample action

$\beta(a\mid s)\leftarrow\pi_{\theta}(a\mid s)$

$s,r\sim P(s,a)$ $\triangleright$ sample next state and reward

$t\leftarrow t+1$

Store $(a,s,r,\beta(a\mid s))$ in $\mathcal{D}$

end for

for all epochs do

Compute returns $R$ and advantages $A$

Compute $\tilde{\mathcal{D}}$

$L_{\nu}\leftarrow\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\nu(\varepsilon_{\nu}-\mathrm{sg}(D_{KL}(\pi_{\text{old}}\|\pi_{\theta})))+\mathrm{sg}(\nu)D_{KL}(\pi_{\text{old}}\|\pi_{\theta})$
$\triangleright$ KL loss

$L_{\pi}\leftarrow-\frac{1}{\lvert\tilde{\mathcal{D}}\rvert}\sum_{\tilde{\mathcal{D}}}\ln\pi_{\theta}(a\mid
s)\psi(s,a)$ $\triangleright$ Policy loss

$L_{\eta}\leftarrow\eta\varepsilon_{\eta}+\eta\ln(\frac{1}{\lvert\tilde{\mathcal{D}}\rvert}\sum_{\tilde{\mathcal{D}}}\exp\frac{A}{\eta})$
$\triangleright$ Temperature loss

$d\theta\leftarrow\nabla_{\theta}(L_{\pi}+L_{\nu})$,
$d\eta\leftarrow\frac{\partial}{\partial\eta}L_{\eta}$,
$d\nu\leftarrow\frac{\partial}{\partial\nu}L_{\nu}$ $\triangleright$ Compute
gradients

$d\phi\leftarrow\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\nabla_{\phi}(R-V_{\phi}(s))^{2}$

update $\theta$, $\eta$, $\nu$ and $\phi$ using $d\theta$, $d\eta$, $d\nu$ and
$d\phi$ via gradient ascent / descent

end for

end while

The learnable parameters $\eta$ and $\nu$ are Lagrangian multipliers and hence
must be positive. We enforce this by projecting the computed values to small
positive values $\eta_{\text{min}}$ and $\nu_{\text{min}}$ respectively if
necessary. The pseudocode for V-MPO is depicted in Algorithm 8. As
implementational details, V-MPO typically uses decoupled KL constraints for
the mean and covariance of the policy in continuous action spaces following
[2]. This enables better exploration without moving the policy mean as well as
fast learning by rapidly changing the mean without resulting in a collapse of
the policy due to vanishing standard deviations. In addition, V-MPO can be
used with an off-policy correction via an importance sampling ratio similarly
to TRPO and PPO and uses multiple actors following A3C.

###  4.6 Comparing Design Choices in Policy Gradient Algorithms

Having outlined the main on-policy policy gradient algorithms, we want to
shortly compare them to characterize the main design choices in constructing
such algorithms.

The predominant differences across policy gradient algorithms lie in the
estimators $\hat{\nabla}_{\theta}J(\theta)$ of the policy gradients. We
summarize these estimates in Table 1888For V-MPO, we focus on the policy loss,
thus ignoring the gradient of the KL loss $\mathcal{L}_{\nu}$ w.r.t. the
policy parameters $\theta$ here.. The algorithms can be distinguished along
several dimensions with respects to the gradients. First, they use different
variance reduction techniques, which are especially reflected in how $Q_{\pi}$
in the policy gradient formula (13) is estimated. Second, various policy
regularization strategies are used. Third, the algorithms employ further
lower-level details to stabilize learning. We will discuss each of these
dimensions in the following.

| Algorithm
---
| Gradient estimator
---
REINFORCE | $G\nabla_{\theta}\ln\pi_{\theta}(a\mid s)$
A3C | $\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\hat{A}\nabla_{\theta}\ln\pi_{\theta}(a\mid s)$
TRPO | $\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\hat{A}\nabla_{\theta}\frac{\pi_{\theta}(a\mid s)}{\pi_{\text{old}}(a\mid s)}$
PPO | $\frac{1}{\lvert\mathcal{D}\rvert}\sum_{\mathcal{D}}\hat{A}\nabla_{\theta}\min\biggl{(}\frac{\pi_{\theta}(a\mid s)}{\pi_{\text{old}}(a\mid s)},\text{clip}\Bigl{(}\frac{\pi_{\theta}(a\mid s)}{\pi_{\text{old}}(a\mid s)},1-\varepsilon,1+\varepsilon\Bigr{)}\biggr{)}$
V-MPO | $\frac{1}{\sum_{\tilde{\mathcal{D}}}\exp\bigl{(}\frac{\hat{A}}{\eta}\bigr{)}}\sum_{\tilde{\mathcal{D}}}\exp\bigl{(}\frac{\hat{A}}{\eta}\bigr{)}\nabla_{\theta}\ln\pi_{\theta}(a\mid s)$
Table 1: Policy gradient estimates used by various policy gradient algorithms.

Reducing variance is important to stabilize learning and speed up convergence
[77]. However, while high variance means algorithms require more samples to
converge, bias in the estimates is not resolvable even with infinite samples
[70]. All contemporary policy gradient algorithms, i.e. all presented
algorithms except REINFORCE, make use of baselines to reduce variance as
discussed in Section 3.2 when approximating the unknown $Q_{\pi}$. While
REINFORCE samples returns as an unbiased but high-variance estimate [75], the
other algorithms learn a value function $\hat{V}$ to estimate the advantage
function $\hat{A}$. Notably, this reduces variance at the cost of introducing
bias [43, 76, 70]. Further differences arise from how advantages are
estimated, albeit these strategies can be easily transferred between
algorithms. PPO uses GAE to estimate advantages, which generalizes the n-step
temporal difference estimates used in A3C, TRPO and V-MPO. In addition, V-MPO
scales the advantages via the learned temperature $\eta$ and only uses the top
50 % of advantages per batch.

To stabilize learning beyond variance reduction, several regularization
techniques are proposed by TRPO, PPO and V-MPO to limit the change in policies
across iterations. TRPO imposes a constraint on the KL divergence between the
newly learned and the previous policy. Thus, the policy gradients are not
directly applied to update the policy parameters $\theta$ but instead they are
postprocessed to yield an approximate solution to this constrained
optimization problem. This comes at the cost of algorithmic complexity
however. Whereas the other algorithms directly compute the estimated policy
gradients via automatic differentiation [86, 53], TRPO requires the estimation
of a hessian and the application of the conjugate gradient algorithm followed
by a line search. PPO avoids such complexity by introducing a heuristic, which
bounds the probability ratio $\frac{\pi_{\theta}(a\mid
s)}{\pi_{\text{old}}(a\mid s)}$, into its objective function. By
conservatively clipping this ratio, large policy changes induced by
overfitting the advantage function are prevented. This also enables PPO to
conduct multiple updates on the same data to accelerate learning [71]. V-MPO
too limits the KL divergence across policies. The prior distribution is
selected such that V-MPO arrives at a similar optimization problem with a
penalty on the KL divergence as TRPO. Following TRPO, V-MPO transforms this
into a constrained optimization problem, albeit now with the goal of
automatically tuning the penalty parameter by applying coordinate-descent to
the Lagrangian relaxation of this constrained optimization problem.

Lastly, we point out that different lower-level details are employed by the
discussed algorithm. Except for REINFORCE, all algorithms use several actors,
which are potentially updated asynchronously, and average gradients over
batches of transitions to further reduce their variance. Here, V-MPO slightly
diverges from the other algorithms as it computes a weighted average based on
the advantages of the transitions, i.e. with weights

$\frac{\exp\Bigl{(}\frac{A_{\pi_{\theta_{\text{old}}}}(s,a)}{\eta}\Bigr{)}}{\sum_{a,s\in\tilde{\mathcal{D}}}\exp\Bigl{(}\frac{A_{\pi_{\theta_{\text{old}}}}(s,a)}{\eta}\Bigr{)}}.$

A3C and PPO commonly use an entropy bonus to prevent premature convergence to
a suboptimal policy by incentivizing a higher standard deviation of the
Gaussian output by the policy. We observe that V-MPO does not use an entropy
bonus but achieves a comparable effect in continuous action spaces by
constraining the policy mean and standard deviation separately. Lastly, TRPO
and PPO include an importance sampling correction to compensate for the slight
off-policy nature of the algorithms induced by using multiple asynchronous
workers. This is also mentioned as an option for V-MPO [73].

##  5 Convergence Results

In this section, we discuss convergence results for policy gradient algorithms
from literature. First, we present an overview of different convergence proofs
in Section 5.1. Then, we thoroughly present one selected result in Section
5.2.

###  5.1 Literature Overview

Several convergence results have been proposed for policy gradient algorithms.
They differ along various dimensions: the specific algorithms covered, the
shown strength of convergence, the problem settings and the employed proving
techniques. The following overview of convergence results is not intended to
be complete but rather shall showcase these differences.

As previously discussed, REINFORCE uses an unbiased estimator of the policy
gradients, which in expectation therefore point in the direction of the true
gradients. Hence, under common stochastic approximation assumptions towards
the step sizes, REINFORCE can be shown to converge to a locally optimal policy
[75]. In the general form of policy gradient algorithms, agnostic to the
specific estimator of $Q_{\pi}$, showing convergence is more complex as the
estimated gradients are typically biased when using a learned value function
[43, 76]. [4] and [11] consider the simplest case where state and action
spaces $\mathcal{S}$ and $\mathcal{A}$ are finite and no function
approximation is used, i.e. the policy uses a tabular parameterization with
one parameter for each state-action combination. Using that the exact policy
gradients can be calculated in this case, both studies show the global
convergence to an optimal policy with a linear convergence rate.

[76] and [90] generalize these results to settings with function
approximation, albeit under impractical conditions on the approximators, which
are required to be linear in their inputs. The extension to function
approximation comes at the cost of only being able to proof local convergence
using stochastic approximation and the Supermartingale Convergence Theorem
[64].

Finally, some convergence results exist for the specific algorithms such as
TRPO and PPO. TRPO is based on Theorem 4.1, which comes with monotonic
improvement guarantees. However, TRPO is only an approximation to the
algorithm stemming from Theorem 4.1, so that no such guarantee holds for TRPO
in practice. We further remark that PPO is similarly intended as an heuristic
of this theoretical algorithm [71]. Nonetheless, efforts have been made to
proof the convergence of these practical algorithms. [51] show that a slightly
modified version of PPO converges to a globally optimal policy at a sublinear
rate under specific assumptions. In particular, they require an
overparameterized neural network as the function approximator such that they
can use infinite-dimensional mirror-descent [8] to proof the convergence. [34]
provide a proof using two time-scale stochastic approximation [39] that PPO
converges to a locally optimal policy under more realistic assumptions akin to
typical learning scenarios.

###  5.2 Mirror Learning

In this subsection, we focus on the convergence proof provided by [46]. While
primarily of theoretical interest, we choose to discuss this particular result
as it is agnostic to the selected algorithm and parameterization and can hence
by applied to a range of policy gradient algorithms. [46] introduce a
framework called _mirror learning_ , which comes with global convergence
guarantees for all policy gradient algorithms that adhere to a specific form.
In the following, we follow [46] in deriving their results. We start by giving
some definitions, based on which we then present the general form of mirror
learning updates. We show that the discussed algorithms largely adhere to this
form. Finally, we proof that this implies the convergence to an optimal
policy.

####  5.2.1 Fundamentals of Mirror Learning

From here onwards, we do not explicitly write down the policy parameters, i.e.
we omit the subscript $\theta$ when describing a policy $\pi$. [46] define the
drift $\mathfrak{D}$ and the neighborhood operator $\mathcal{N}$ as follows.

######  Definition 5.1.

(Drift) A drift functional

$\mathfrak{D}\colon\Pi\times\mathcal{S}\rightarrow\\{\mathfrak{D}_{\pi}(\cdot\mid
s)\colon\Delta(\mathcal{A})\rightarrow\mathbb{R}\\}$

is a map which satisfies the following conditions for all $s\in\mathcal{S}$
and $\pi,\bar{\pi}\in\Pi$:

  1. 1.

$\mathfrak{D}_{\pi}(\bar{\pi}\mid s)\geq\mathfrak{D}_{\pi}(\pi\mid s)=0$,
(non-negativity)

  2. 2.

$\mathfrak{D}_{\pi}(\bar{\pi}\mid s)$ has zero gradient with respects to
$\bar{\pi}(\cdot\mid s)$ at $\bar{\pi}(\cdot\mid s)=\pi(\cdot\mid s)$, more
precisely all its Gâteaux derivatives999See Definition D.16. are zero, (zero
gradient)

where we used $\mathfrak{D}_{\pi}\bigl{(}\bar{\pi}(\cdot\mid s)\mid
s\bigr{)}\coloneqq\mathfrak{D}_{\pi}(\bar{\pi}\mid s)$.

For any state distribution $\nu^{\bar{\pi}}_{\pi}\in\Delta(\mathcal{S})$, that
can depend on both $\bar{\pi}$ and $\pi$, the drift from $\bar{\pi}$ to $\pi$
is given by

$\mathfrak{D}^{\nu}_{\pi}(\bar{\pi})\coloneqq\mathbb{E}_{s\sim\nu^{\bar{\pi}}_{\pi}}\bigl{[}\mathfrak{D}_{\pi}(\bar{\pi}\mid
s)\bigr{]}.$

We require $\nu^{\bar{\pi}}_{\pi}$ to be such that this expectation is
continuous in $\bar{\pi}$ and $\pi$. We call a drift trivial if
$\mathfrak{D}^{\nu}_{\pi}(\bar{\pi})=0$ for all $\pi,\bar{\pi}\in\Pi$.

######  Definition 5.2.

(Neighborhood Operator) A mapping

$\mathcal{N}\colon\Pi\rightarrow\mathcal{P}(\Pi)$

is a neighborhood operator if it satisfies the following conditions:

  1. 1.

$\mathcal{N}$ is continuous, (continuity)

  2. 2.

$\mathcal{N}(\pi)$ is compact for all $\pi\in\Pi$, (compactness)

  3. 3.

There exists a metric $\chi\colon\Pi\times\Pi\rightarrow\mathbb{R}$ such that
$\chi(\pi,\bar{\pi})\leq\zeta$ implies $\bar{\pi}\in\mathcal{N}(\pi)$ for all
$\pi,\bar{\pi}\in\Pi$ given some $\zeta\in\mathbb{R}_{+}$. (closed ball)

We call $\mathcal{N}(\cdot)=\Pi$ the trivial neighborhood operator.

With these definitions, we can define the mirror learning update rule.

######  Definition 5.3.

(Mirror Learning Update) Let $\pi_{\text{old}}$ be the previous policy and
$d^{\pi_{\text{old}}}$ the state distribution under $\pi_{\text{old}}$.
Further, let

$\Bigl{[}\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\pi}\Bigr{]}(s)\coloneqq\mathbb{E}_{A\sim\bar{\pi}}\bigl{[}Q_{\pi}(s,A)\bigr{]}-\frac{\nu^{\bar{\pi}}_{\pi}}{d^{\pi}}\mathfrak{D}_{\pi}(\bar{\pi}\mid
s)$

be the mirror learning operator. Then, the mirror learning update chooses the
new policy $\pi_{\text{new}}$ as

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\bar{\pi}\in\mathcal{N}(\pi_{\text{old}})}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\biggl{[}\Bigl{[}\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\pi_{\text{old}}}\Bigr{]}(S)\biggr{]}.$
(26)

Under the light of this mirror learning update, the drift $\mathfrak{D}$ from
one policy to the next induces some penalty on the objective while the
neighborhood operator puts a hard constraint on the divergence of subsequent
policies.

####  5.2.2 Policy Gradient Algorithms as Instances of Mirror Learning

Before proving the convergence of mirror learning to an optimal policy, we
first show that the discussed policy gradient algorithms can partly be seen as
instances of mirror learning, i.e. use updates of the form

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\mathcal{N}(\pi_{\text{old}})}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\biggl{[}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\pi_{\text{old}}}(S,A)\bigr{]}-\frac{\nu^{\pi}_{\pi_{\text{old}}}}{d^{\pi_{\text{old}}}}\mathfrak{D}_{\pi_{\text{old}}}(\pi\mid
S)\biggr{]}.$

A3C

A3C is a direct application of the Policy Gradient Theorem, albeit with a
learned advantage function. Thus, at each iteration it approximately solves
the optimization problem

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi}\Bigl{[}A_{\pi_{\text{old}}}(S,A)\Bigr{]}=\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\Bigl{[}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\pi_{\text{old}}}(S,A)\bigr{]}\Bigr{]}.$

This is the most trivial instantiation of mirror learning by using the trivial
drift $\mathfrak{D}(\cdot\mid\cdot)=0$ and the trivial neighborhood operator
$\mathcal{N}(\cdot)=\Pi$. The same argumentation also applies to REINFORCE.
Note that in practice however, we maximize the expectation over
$\pi_{\text{old}}$ rather than $\pi$. For this reason, these are not exact
instances of mirror learning.

TRPO

TRPO’s constrained optimization problems

$\displaystyle\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}},A\sim\pi_{\text{old}}}\biggl{[}\frac{\pi(A\mid
S)}{\pi_{\text{old}}(A\mid S)}A_{\pi_{\text{old}}}(S,A)\biggr{]}$
$\displaystyle\text{subject to}\quad\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
S)\|\pi(\cdot\mid S))\bigr{]}\leq\delta$

can be rewritten as

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\mathcal{N}_{\text{TRPO}}(\pi_{\text{old}})}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\Bigl{[}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\pi_{\text{old}}}(S,A)\bigr{]}\Bigr{]}$

with the average-KL ball as the neighborhood operator, i.e.

$\mathcal{N}_{\text{TRPO}}(\pi_{\text{old}})=\bigl{\\{}\pi\mid\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
S)\|\pi(\cdot\mid S))\bigr{]}\leq\delta\bigr{\\}}.$

Here, we used that

$\displaystyle\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}\frac{\pi(A\mid
s)}{\pi_{\text{old}}(A\mid s)}A_{\pi_{\text{old}}}(s,A)\biggr{]}$
$\displaystyle=\int_{a\in\mathcal{A}}\pi_{\text{old}}(a\mid s)\frac{\pi(a\mid
s)}{\pi_{\text{old}}(a\mid s)}A_{\pi_{\text{old}}}(s,a)da$
$\displaystyle=\mathbb{E}_{A\sim\pi}\Bigl{[}A_{\pi_{\text{old}}}(s,A)\Bigr{]}$

and that maximizing over the action-value function is identical to maximizing
over the advantage function following the discussion in Section 3.2. Thus,
TRPO is a mirror learning instance with the trivial drift
$\mathfrak{D}(\cdot\mid\cdot)=0$.

PPO

Each iteration, PPO searches for

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{\pi_{\text{old}}}\biggl{[}\min\biggl{\\{}r_{\pi}(A\mid
S),\text{clip}\bigl{(}r_{\pi}(A\mid
S),1-\varepsilon,1+\varepsilon\bigr{)}\biggr{\\}}A_{\pi_{\text{old}}}(S,A)\biggr{]},$

where we write $r_{\pi}(a\mid s)$ for $\frac{\pi(a\mid
s)}{\pi_{\text{old}}(a\mid s)}$. We can rewrite the expectation over actions
by adding zero as

$\displaystyle\mathbb{E}_{A\sim\pi_{\text{old}}}$
$\displaystyle\biggl{[}\min\biggl{\\{}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A),\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}$
$\displaystyle=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)\biggr{]}-\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)$ $\displaystyle\quad-\min\biggl{\\{}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A),\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}.$

Using the same technique as before, we can write the first expectation
equivalently as
$\mathbb{E}_{A\sim\pi}\bigl{[}A_{\pi_{\text{old}}}(s,A)\bigr{]}$. We now focus
on the second expectation. We replace the $\min$ operator with a $\max$ and
push the first term inside the $\max$ to obtain

$\displaystyle\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)-\min\biggl{\\{}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A),\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}$
$\displaystyle\qquad=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)+\max\biggl{\\{}-r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A),-\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}$
$\displaystyle\qquad=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}\max\biggl{\\{}r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)-r_{\pi}(A\mid s)A_{\pi_{\text{old}}}(s,A),$
$\displaystyle\qquad\qquad r_{\pi}(A\mid
s)A_{\pi_{\text{old}}}(s,A)-\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}$
$\displaystyle\qquad=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}\max\biggl{\\{}0,\Bigl{(}r_{\pi}(A\mid
s)-\text{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}\Bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}.$

This final expression is non-negative. Moreover, it is zero for $\pi$
sufficiently close to $\pi_{\text{old}}$, i.e. such that for all actions
$a\in\mathcal{A}$ we have $r_{\pi}(a\mid s)=\frac{\pi(a\mid
s)}{\pi_{\text{old}}(a\mid s)}\in[1-\varepsilon,1+\varepsilon]$, because then
the $\mathrm{clip}$-function reduces to the identity function w.r.t. its first
argument. Thus, the derivatives of this expression must also be zero at
$\pi(\cdot\mid s)=\pi_{\text{old}}(\cdot\mid s)$. These properties are the
exact conditions for a mapping to be considered a drift in the sense of
Definition 5.1. With this preparation, we can now write the PPO update as

$\pi_{\text{new}}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\biggl{[}\mathbb{E}_{A\sim\pi}\Bigl{[}A_{\pi_{\text{old}}}(S,A)\Bigr{]}-\mathfrak{D}_{\pi_{\text{old}}}(\pi\mid
S)\biggr{]},$

where $\mathfrak{D}_{\pi_{\text{old}}}$ is a drift given by

$\mathfrak{D}_{\pi_{\text{old}}}(\pi\mid
s)=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}\max\biggl{\\{}0,\Bigl{(}r_{\pi}(A\mid
s)-\mathrm{clip}\bigl{(}r_{\pi}(A\mid
s),1-\varepsilon,1+\varepsilon\bigr{)}\Bigr{)}A_{\pi_{\text{old}}}(s,A)\biggr{\\}}\biggr{]}.$

This is an instance of the mirror learning update with the trivial
neighborhood operator $\mathcal{N}(\cdot)=\Pi$ and
$\nu^{\pi}_{\pi_{\text{old}}}=d^{\pi_{\text{old}}}$.

####  5.2.3 Convergence Proof

Now, we present the main theoretical result of [46].

######  Theorem 5.4.

Let $\mathfrak{D}^{\nu}$ be a drift, $\mathcal{N}$ a neighborhood operator and
$d^{\pi}$ the sampling distribution, all continuous in $\pi$. Let the
objective, i.e. the expected returns under a policy $\pi$, be written as
$J(\pi)=\mathbb{E}_{S_{0}\sim p_{0},\pi}\bigl{[}G_{0}\bigr{]}$. Let
$\pi_{0}\in\Pi$ be the initial policy and the sequence of policies
$\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$ be obtained through the mirror
learning update rule (26) under $\mathfrak{D}^{\nu}$, $\mathcal{N}$ and
$d^{\pi}$. Then,

  1. 1.

(Strict monotonic improvement)

$J(\pi_{n+1})\geq J(\pi_{n})+\mathbb{E}_{S\sim
p_{0}}\biggl{[}\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(S)}{d^{\pi_{n}}(S)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
S)\biggr{]}\quad\forall n\in\mathbb{N}_{0}.$

  2. 2.

(Value function optimality)

$\lim_{n\to\infty}V_{\pi_{n}}=V^{*}.$

  3. 3.

(Maximum attainable return)

$\lim_{n\to\infty}J(\pi_{n})=\max_{\pi\in\Pi}J(\pi).$

  4. 4.

(Policy optimality)

$\lim_{n\to\infty}\pi_{n}=\pi^{*}.$

###### Proof.

We structure the proof by [46] in five steps. In step 1, we start by showing
that mirror learning updates lead to improvements under the mirror learning
operator $\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n-1}}$, which implies
improvements in the value function $V_{\pi_{n}}$. In step 2, we prove that the
sequence of value functions $\bigl{(}V_{\pi_{n}}\bigr{)}^{\infty}_{n=0}$
converges to some limit. In step 3, we show the existence of limit points of
the sequence of policies $\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$, which are
fixed points of the mirror learning update (26). In step 4, we prove that
these limit points are also fixed points of Generalized Policy Iteration (GPI)
[75], from which we conclude that these limit points are optimal policies in
step 5. For simplicity, we proof Theorem 5.4 for discrete state and actions
spaces. However, the results are straightforward to extended to the continuous
cases (see the appendix in [46] for details).

Step 1

We start by showing by contradiction that for all $n\in\mathbb{N}_{0}$ and for
all $s\in\mathcal{S}$:

$\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s)\geq\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s).$
(27)

Suppose there exists $s_{0}\in\mathcal{S}$, which violates (27). We define a
policy $\hat{\pi}$ with

$\hat{\pi}(\cdot\mid s)=\begin{cases}\pi_{n+1}(\cdot\mid s)&\text{if }s\neq
s_{0},\\\ \pi_{n}(\cdot\mid s)&\text{if }s=s_{0}.\end{cases}$

This way, we guarantee $\hat{\pi}\in\mathcal{N}(\pi_{n})$ because
$\pi_{n+1}\in\mathcal{N}(\pi_{n})$ is forced by the mirror learning update
(26) and the distance between $\hat{\pi}$ and $\pi_{n}$ is similar to the
distance between $\pi_{n+1}$ and $\pi_{n}$ at every $s\neq s_{0}$ but smaller
at $s=s_{0}$.

By assumption, we have at $s_{0}$ that

$\displaystyle\bigl{[}\mathcal{M}^{\hat{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s_{0})$
$\displaystyle=\mathbb{E}_{A\sim\hat{\pi}}\Bigl{[}Q_{\pi_{n}}(s_{0},A)\Bigr{]}-\frac{\nu^{\hat{\pi}}_{\pi_{n}}}{d^{\pi_{n}}}\mathfrak{D}_{\pi_{n}}(\hat{\pi}\mid
s_{0})$
$\displaystyle=\mathbb{E}_{A\sim\pi_{n}}\Bigl{[}Q_{\pi_{n}}(s_{0},A)\Bigr{]}-\frac{\nu^{\pi_{n}}_{\pi_{n}}}{d^{\pi_{n}}}\mathfrak{D}_{\pi_{n}}(\pi_{n}\mid
s_{0})$
$\displaystyle=\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s_{0})$
$\displaystyle>\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s_{0}).$

It follows that

$\displaystyle\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\hat{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggr{]}-\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggr{]}=d^{\pi_{n}}(s_{0})\biggl{(}\Bigl{[}\mathcal{M}^{\hat{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(s_{0})-\Bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(s_{0})\biggr{)}>0,$

where we used that
$\Bigl{[}\mathcal{M}^{\hat{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(s)=\Bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(s)$
for $s\neq s_{0}$. Thus,

$\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\hat{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggr{]}>\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggr{]},$

which contradicts the mirror learning update rule, i.e. that

$\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggr{]}=\max_{\bar{\pi}\in\mathcal{N}(\pi_{n})}\mathbb{E}_{S\sim
d^{\pi_{n}}}\biggl{[}\Bigl{[}\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\pi_{n}}\Bigr{]}(S)\biggl{]}.$

Hence, we have shown that the sequence of policies
$\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$ created by the mirror learning
updates monotonically increases the mirror learning operator at every state.
Next, we show that this property, i.e.
$\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s)\geq\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}(s)$,
implies the monotonic improvement in the value function

$V_{\pi_{n+1}}(s)\geq V_{\pi_{n}}(s)$ (28)

for all $s~\in\mathcal{S}$ and $n\in\mathbb{N}_{0}$.

By using the definitions of the value function $V_{\pi}$, the action-value
function $Q_{\pi}$, the mirror learning operator
$\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\pi}$ and the identity
$\mathfrak{D}_{\pi}(\pi\mid s)=0$, adding zeros and rearranging, we obtain

$\displaystyle V_{\pi_{n+1}}(s)-V_{\pi_{n}}(s)$
$\displaystyle=\mathbb{E}_{\pi_{n+1}}\Bigl{[}R+\gamma
V_{\pi_{n+1}}(S^{\prime})\Bigr{]}-\mathbb{E}_{\pi_{n}}\Bigl{[}R+\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}$
$\displaystyle=\mathbb{E}_{\pi_{n+1}}\Bigl{[}R+\gamma
V_{\pi_{n+1}}(S^{\prime})\Bigr{]}-\mathbb{E}_{\pi_{n}}\Bigl{[}R+\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}$
$\displaystyle\qquad+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)-\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$ $\displaystyle=\mathbb{E}_{\pi_{n+1}}\Bigl{[}R+\gamma
V_{\pi_{n+1}}(S^{\prime})+\gamma V_{\pi_{n}}(S^{\prime})-\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}-\mathbb{E}_{\pi_{n}}\Bigl{[}R+\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}$
$\displaystyle\qquad+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)-\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$ $\displaystyle=\biggl{(}\mathbb{E}_{\pi_{n+1}}\Bigl{[}R+\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}-\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{)}$
$\displaystyle\qquad-\biggl{(}\mathbb{E}_{\pi_{n}}\Bigl{[}R+\gamma
V_{\pi_{n}}(S^{\prime})\Bigr{]}-\frac{\nu^{\pi_{n}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n}\mid
s)\biggr{)}$
$\displaystyle\qquad+\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$
$\displaystyle=\biggl{(}\mathbb{E}_{\pi_{n+1}}\Bigl{[}Q_{\pi_{n}}(s,A)\Bigr{]}-\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{)}$
$\displaystyle\qquad-\biggl{(}\mathbb{E}_{\pi_{n}}\Bigl{[}Q_{\pi_{n}}(s,A)\Bigr{]}-\frac{\nu^{\pi_{n}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n}\mid
s)\biggr{)}$
$\displaystyle\qquad+\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$
$\displaystyle\begin{split}&=\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}-\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}\\\
&\qquad+\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\end{split}$ (29)
$\displaystyle\geq\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s),$

where we used Inequality (27) in the final step. We take the infimum over
states and replace the expectation with another infimum over states as a lower
bound:

$\displaystyle\inf_{s\in\mathcal{S}}\Bigl{[}V_{\pi_{n+1}}(s)-V_{\pi_{n}}(s)\Bigr{]}$
$\displaystyle\geq\inf_{s\in\mathcal{S}}\biggl{[}\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{]}$
$\displaystyle\geq\inf_{s\in\mathcal{S}}\biggl{[}\gamma\inf_{s^{\prime}\in\mathcal{S}}\Bigl{[}V_{\pi_{n+1}}(s^{\prime})-V_{\pi_{n}}(s^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{]}$
$\displaystyle=\gamma\inf_{s^{\prime}\in\mathcal{S}}\Bigl{[}V_{\pi_{n+1}}(s^{\prime})-V_{\pi_{n}}(s^{\prime})\Bigr{]}+\inf_{s\in\mathcal{S}}\biggl{[}\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{]}.$

From this expression, we obtain

$\inf_{s\in\mathcal{S}}\Bigl{[}V_{\pi_{n+1}}(s)-V_{\pi_{n}}(s)\Bigr{]}\geq\frac{1}{1-\gamma}\inf_{s\in\mathcal{S}}\biggl{[}\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)\biggr{]}\geq 0,$

since $\nu^{\pi_{n+1}}_{\pi_{n}}(s)$ and $d^{\pi_{n}}(s)$ are probabilities
and the drift $\mathfrak{D}$ is non-negative. Thus, we have proven the
monotonic improvement of value functions $V_{\pi_{n+1}}(s)\geq
V_{\pi_{n}}(s)$. We observe that this already implies the strict monotonic
improvement property

$J(\pi_{n+1})\geq J(\pi_{n})+\mathbb{E}_{S\sim
p_{0}}\biggl{[}~\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(S)}{d^{\pi_{n}}(S)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
S)\biggr{]}$

for all $n~\in\mathbb{N}_{0}$ since applying (28) and (27) sequentially to
(29) yields for all $s\in\mathcal{S}$

$\displaystyle V_{\pi_{n+1}}(s)-V_{\pi_{n}}(s)$
$\displaystyle=\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}-\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}$
$\displaystyle\quad+\gamma\mathbb{E}_{\pi_{n+1}}\Bigl{[}V_{\pi_{n+1}}(S^{\prime})-V_{\pi_{n}}(S^{\prime})\Bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$
$\displaystyle\geq\bigl{[}\mathcal{M}^{\pi_{n+1}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}-\bigl{[}\mathcal{M}^{\pi_{n}}_{\mathfrak{D}}V_{\pi_{n}}\bigr{]}+\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s)$
$\displaystyle\geq\frac{\nu^{\pi_{n+1}}_{\pi_{n}}(s)}{d^{\pi_{n}}(s)}\mathfrak{D}_{\pi_{n}}(\pi_{n+1}\mid
s).$

We obtain the desired inequality by taking the expectation over $S\sim p_{0}$.

Step 2

From step 1, we know that the value functions increase uniformly over the
state space, i.e. $V_{\pi_{n+1}}(s)-V_{\pi_{n}}(s)\geq 0$, for all s