$\in\mathcal{S}$, $n\in\mathbb{N}_{0}$. As the rewards $r$ are bounded by
assumption and we consider the episodic case where episode lengths are also
bounded by $T$ (albeit the same argument applies for infinite time horizons
via discounting), the value functions
$V_{\pi}(s)=\mathbb{E}_{\pi}\bigl{[}\sum_{k=0}^{T}\gamma^{k}R_{t+k+1}\mid
S_{t}=s\bigr{]}$ are also uniformly bounded. Via the Monotone Convergence
Theorem (Theorem D.13), the sequence of value functions
$\bigl{(}V_{\pi_{n}}\bigr{)}^{\infty}_{n=0}$ must therefore converge to some
limit $V$.

Step 3

Now, we show the existence of limit points of the sequence of policies
$\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$ and prove by contradiction that these
are fixed points of the mirror learning update (26).

The sequence $\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$ is bounded, thus the
Bolzano-Weierstrass Theorem (Theorem D.14) yields the existence of limits
$\bar{\pi}$ to which some respective subsequence
$\bigl{(}\pi_{n_{i}}\bigr{)}^{\infty}_{i=0}$ converges. We denote this set of
limit points as $L\Pi$. For each element of such a convergent subsequence
$\bigl{(}\pi_{n_{i}}\bigr{)}^{\infty}_{i=0}$, mirror learning solves the
optimization problem

$\max_{\pi\in\mathcal{N}(\pi_{n_{i}})}\mathbb{E}_{S\sim
d^{\pi_{n_{i}}}}\Bigl{[}\bigl{[}\mathcal{M}^{\pi}_{\mathfrak{D}}V_{\pi_{n_{i}}}\bigr{]}(S)\Bigr{]}$
(30)

This expression is continuous in $\pi_{n_{i}}$ due to the continuity of the
value function [45], the drift and neighborhood operator (by definition) and
the sampling distribution (by assumption). Let
$\bar{\pi}=\lim_{i\to\infty}\pi_{n_{i}}$. Berge’s Maximum Theorem (Theorem
D.15) [6] now guarantees the convergence of the above expression, yielding

$\lim_{i\to\infty}\max_{\pi\in\mathcal{N}(\pi_{n_{i}})}\mathbb{E}_{S\sim
d^{\pi_{n_{i}}}}\Bigl{[}\bigl{[}\mathcal{M}^{\pi}_{\mathfrak{D}}V_{\pi_{n_{i}}}\bigr{]}(S)\Bigr{]}=\max_{\pi\in\mathcal{N}(\bar{\pi})}\mathbb{E}_{S\sim
d^{\bar{\pi}}}\Bigl{[}\bigl{[}\mathcal{M}^{\pi}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(S)\Bigr{]}.$
(31)

For all $i\in\mathbb{N}_{0}$, we obtain the next policy $\pi_{n_{i}+1}$ as the
argmax of Expression (30). Since this expression converges to the limit in
(31), there must exist some subsequence
$\bigl{(}\pi_{n_{i_{k}}+1}\bigr{)}^{\infty}_{k=0}$ of
$\bigl{(}\pi_{n_{i}+1}\bigr{)}^{\infty}_{i=0}$ which converges to some policy
$\pi^{\prime}$, which is the solution to the optimization problem (31). We now
show by contradiction that $\pi^{\prime}=\bar{\pi}$, which implies that
$\bar{\pi}$ is a fixed point of the mirror learning update rule.

Suppose $\pi^{\prime}\neq\bar{\pi}$. As $\pi^{\prime}$ is induced by the
mirror learning update rule, the monotonic improvement results from step 1
yield

$Q_{\pi^{\prime}}(s,a)=\mathbb{E}_{R,S^{\prime}\sim P}\Bigl{[}R+\gamma
V_{\pi^{\prime}}(S^{\prime})\Bigr{]}\geq\mathbb{E}_{R,S^{\prime}\sim
P}\Bigl{[}R+\gamma V_{\bar{\pi}}(S^{\prime})\Bigr{]}=Q_{\bar{\pi}}(s,a)$ (32)

and

$\bigl{[}\mathcal{M}^{\pi^{\prime}}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(s)\geq\bigl{[}\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(s).$

Suppose

$\mathbb{E}_{S\sim
d^{\bar{\pi}}}\Bigl{[}\bigl{[}\mathcal{M}^{\pi^{\prime}}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(S)\Bigr{]}>\mathbb{E}_{S\sim
d^{\bar{\pi}}}\Bigl{[}\bigl{[}\mathcal{M}^{\bar{\pi}}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(S)\Bigr{]},$

then we have for some state $s$

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

In the last equality, we used that the sequence of value functions converges
to some unique limit $V$, which implies $V_{\bar{\pi}}=V$. We obtain the
following via this result, Inequality (32), which must be strict for $s$, and
the non-negativity of the drift $\mathfrak{D}$:

$\displaystyle V_{\pi^{\prime}}(s)$
$\displaystyle=\mathbb{E}_{\pi^{\prime}}\bigl{[}Q_{\pi^{\prime}}(s,A)\bigr{]}$
$\displaystyle>\mathbb{E}_{\pi^{\prime}}\bigl{[}Q_{\bar{\pi}}(s,A)\bigr{]}$
$\displaystyle>\mathbb{E}_{\pi^{\prime}}\bigl{[}Q_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\pi^{\prime}}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\pi^{\prime}\mid
s)$ $\displaystyle>V(s).$

However due to $V_{\pi^{\prime}}(s)=\lim_{k\to\infty}V_{\pi_{n_{i_{k}}+1}}$,
this contradicts the uniqueness of the value limit, which gives
$V_{\pi^{\prime}}=V$. Therefore, we have shown by contradiction that

$\bar{\pi}\in\operatorname*{arg\,max}_{\pi\in\mathcal{N}(\bar{\pi})}\mathbb{E}_{S\sim
d^{\bar{\pi}}}\Bigl{[}\bigl{[}\mathcal{M}^{\pi}_{\mathfrak{D}}V_{\bar{\pi}}\bigr{]}(S)\Bigr{]}.$

Step 4

Following step 3, let $\bar{\pi}$ be a limit point of
$\bigl{(}\pi_{n}\bigr{)}^{\infty}_{n=0}$. We will show by contradiction that
$\bar{\pi}$ is also a fixed point of GPI (see Theorem 2.1), i.e. that for all
$s\in\mathcal{S}$

$\bar{\pi}\in\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{A\sim\pi}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}=\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\bar{\pi}}(s,A)\bigr{]}.$
(33)

From step 3, we know that

$\displaystyle\bar{\pi}$
$\displaystyle\in\operatorname*{arg\,max}_{\pi\in\Pi}\biggl{[}\mathbb{E}_{S\sim
d^{\bar{\pi}},A\sim\pi}\Bigl{[}Q_{\bar{\pi}}(S,A)-\frac{\nu^{\pi}_{\bar{\pi}}(S)}{d^{\bar{\pi}}(S)}\mathfrak{D}_{\bar{\pi}}(\pi\mid
S)\Bigr{]}\biggr{]}$
$\displaystyle=\operatorname*{arg\,max}_{\pi\in\Pi}\biggl{[}\mathbb{E}_{S\sim
d^{\bar{\pi}},A\sim\pi}\Bigl{[}A_{\bar{\pi}}(S,A)-\frac{\nu^{\pi}_{\bar{\pi}}(S)}{d^{\bar{\pi}}(S)}\mathfrak{D}_{\bar{\pi}}(\pi\mid
S)\Bigr{]}\biggr{]}$ (34)

as subtracting an action-independent baseline does not affect the argmax. Now,
we assume the existence of a policy $\pi^{\prime}$ and state $s$ with

$\mathbb{E}_{A\sim\pi^{\prime}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}>\mathbb{E}_{A\sim\bar{\pi}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}=0.$
(35)

Let $m=\lvert\mathcal{A}\rvert$ denote the size of the action space. Then, we
can write for any policy $\pi$, $\pi(\cdot\mid
s)=\bigl{(}x_{1},\ldots,x_{m-1},1-\sum^{m-1}_{i=1}x_{i}\bigr{)}$. With this
notation, we have

$\displaystyle\mathbb{E}_{A\sim\pi}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}$
$\displaystyle=\sum^{m}_{i=1}\pi(a_{i}\mid s)A_{\bar{\pi}}(s,a_{i})$
$\displaystyle=\sum^{m-1}_{i=1}x_{i}A_{\bar{\pi}}(s,a_{i})+\Bigl{(}1-\sum^{m-1}_{i=1}x_{i}\Bigr{)}A_{\bar{\pi}}(s,a_{m})$
$\displaystyle=\sum^{m-1}_{i=1}x_{i}\Bigl{(}A_{\bar{\pi}}(s,a_{i})-A_{\bar{\pi}}(s,a_{m})\Bigr{)}+A_{\bar{\pi}}(s,a_{m}).$

This shows that $\mathbb{E}_{A\sim\pi}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}$ is
an affine function of $\pi(\cdot\mid s)$, which implies that all its Gâteaux
derivatives are constant in $\Delta(\mathcal{A})$ for fixed directions. Due to
Inequality (35), this further implies that the Gâteaux derivatives in
direction from $\bar{\pi}$ to $\pi^{\prime}$ are strictly positive.
Additionally, we have that the Gâteaux derivatives of
$\frac{\nu^{\pi}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\pi\mid
s)$ are zero at $\pi=\bar{\pi}$. We see this by establishing lower and upper
bounds, which both have derivatives of zero due to the independence of $\pi$
and the zero-gradient property of the drift:

$\frac{1}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\bar{\pi}\mid
s)=\frac{\nu^{\bar{\pi}}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\bar{\pi}\mid
s)=0\leq\frac{\nu^{\pi}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\pi\mid
s)\leq\frac{1}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\pi\mid s)$

recalling that $\mathfrak{D}_{\bar{\pi}}(\bar{\pi}\mid s)=0$ for any
$s\in\mathcal{S}$ and using $\nu^{\pi}_{\bar{\pi}}(s)\leq 1$. In combination,
we obtain that the Gâteaux derivative of
$\mathbb{E}_{A\sim\pi}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\pi}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\pi\mid
s)$ is strictly positive as well. Therefore, we can find some policy
$\hat{\pi}(\cdot\mid s)$ by taking a sufficiently small step from
$\bar{\pi}(\cdot\mid s)$ in the direction of $\pi^{\prime}(\cdot\mid s)$ such
that $\hat{\pi}\in\mathcal{N}(\bar{\pi})$ and

$\mathbb{E}_{A\sim\hat{\pi}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\hat{\pi}}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\hat{\pi}\mid
s)>\mathbb{E}_{A\sim\bar{\pi}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\bar{\pi}}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\bar{\pi}\mid
s)=0.$

With this, we can construct a policy which contradicts Equation (34). Let
$\tilde{\pi}$ be defined such that

$\tilde{\pi}(\cdot\mid x)=\begin{cases}\bar{\pi}(\cdot\mid x)&\text{if }x\neq
s,\\\ \hat{\pi}(\cdot\mid x)&\text{if }x=s.\end{cases}$

This guarantees $\tilde{\pi}\in\mathcal{N}(\bar{\pi})$ and

$\displaystyle\mathbb{E}_{S\sim d^{\bar{\pi}}}$
$\displaystyle\biggl{[}\mathbb{E}_{A\sim\tilde{\pi}}\bigl{[}A_{\bar{\pi}}(S,A)\bigr{]}-\frac{\nu^{\tilde{\pi}}_{\bar{\pi}}(S)}{d^{\bar{\pi}}(S)}\mathfrak{D}_{\bar{\pi}}(\tilde{\pi}\mid
S)\biggr{]}$
$\displaystyle=d^{\bar{\pi}}(s)\biggl{(}\mathbb{E}_{A\sim\tilde{\pi}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\tilde{\pi}}_{\bar{\pi}}(S)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\tilde{\pi}\mid
s)\biggr{)}$
$\displaystyle=d^{\bar{\pi}}(s)\biggl{(}\mathbb{E}_{A\sim\hat{\pi}}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}-\frac{\nu^{\hat{\pi}}_{\bar{\pi}}(s)}{d^{\bar{\pi}}(s)}\mathfrak{D}_{\bar{\pi}}(\hat{\pi}\mid
s)\biggr{)}$ $\displaystyle>0,$

which contradicts Equation (34), so the assumption (35) must be wrong, proving

$\bar{\pi}=\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{A\sim\pi}\bigl{[}A_{\bar{\pi}}(s,A)\bigr{]}=\operatorname*{arg\,max}_{\pi\in\Pi}\mathbb{E}_{A\sim\pi}\bigl{[}Q_{\bar{\pi}}(s,A)\bigr{]}.$

Step 5

The main result (33) from step 4 shows that any limit point $\bar{\pi}$ of
$\bigl{(}\pi_{n}\bigr{)}_{n\in\mathbb{N}}$ is also a fixed point of GPI. Thus,
as corollaries all properties induced by GPI (see Theorem 2.1) apply to
$\bar{\pi}\in L\Pi$. Particularly, we have the optimality of $\bar{\pi}$, the
value function optimality $V=V_{\bar{\pi}}=V^{*}$ and thereby also the
maximality of returns as

$\lim_{n\to\infty}J(\pi_{n})=\lim_{n\to\infty}\mathbb{E}_{S\sim
p_{0}}\bigl{[}V_{\pi_{n}}(S)\bigr{]}=\mathbb{E}_{S\sim
p_{0}}\bigl{[}V^{*}(S)\bigr{]}=\max_{\pi\in\Pi}J(\pi).$

Thus, we have shown all properties as claimed by Theorem 5.4. ∎

We close this section with some remarks. In practice, exact updates according
to the mirror learning update rule (26) are generally infeasible. Instead, we
can sample the expectation to obtain batch estimators over a batch
$\mathcal{D}$ of transitions

$\frac{1}{\lvert\mathcal{D}\rvert}\sum_{s,a\in\mathcal{D}}\Bigl{(}Q_{\pi_{\text{old}}}(s,a)-\frac{\nu^{{\pi_{\text{new}}}}_{\pi_{\text{old}}}}{d^{\pi_{\text{old}}}}\mathfrak{D}_{\pi_{\text{old}}}(\pi_{\text{new}}\mid
s)\Bigr{)},$

where $Q_{\pi_{\text{old}}}$ has to be estimated as well. These batch
estimators can also only be approximately optimized each iteration via
gradient ascent to update the policy. Given these approximations and the at-
best local convergence of gradient ascent, the outlaid convergence properties
remain theoretical.

##  6 Numerical Experiments

Now, we empirically compare the discussed policy gradient algorithms.
Consistent with the original works [54, 69, 71, 73], we compare them on the
established MuJoCo task suite [80], accessed through the Gymnasium library
[81]. MuJoCo features robotics simulations, where the tasks are to control and
move robots of different shapes by applying torques to each joint.

Our implementations build on the PPO implementation from the BRAX library [23]
and are written in JAX [13]. For enhanced comparability, all algorithms that
estimate advantages use GAE similarly to PPO. Instead of A3C, we use its
synchronous variant A2C due to its simpler implementation. Note that A2C
exhibits comparable performance as A3C [85] and only differs in that it waits
for all actors to collect transitions to update them synchronously. We modify
REINFORCE to average gradients over batches of transitions similarly as in the
other algorithms since computing one update per environment step is
computationally very costly. Note that this is however likely to improve the
performance compared to a naive implementation of REINFORCE. We do not tune
hyperparameters and keep choices consistent across algorithms where possible.
See Appendix Appendix A for the hyperparameters we use. The experiments were
run on a standard consumer CPU. All our implemented algorithms and the code
for running the experiments can be found at
https://github.com/Matt00n/PolicyGradientsJax.

Figure 4: Comparison of rewards per episode during training on several MuJoCo
tasks. For each algorithm, we report means and standard deviations of three
runs with different random seeds.

In our main experiment, we compare the performance of the algorithms in terms
of the achieved episodic rewards over the course of training. The performances
in different MuJoCo tasks are presented in Figure 4. We observe that PPO
outperforms the other algorithms in three of four tasks by achieving higher
episodic rewards while learning good policies quickly. The performance
difference is most prevalent on the _Humanoid_ -task, the most challenging of
the four, where PPO learns much stronger policies than the other algorithms.
In addition, we find our implementation of PPO to be competitive with common
RL libraries as shown in Appendix B.1. V-MPO and TRPO are comparable in
performance, with each of the two slightly outperforming the other on two out
of four environments. We note that V-MPO is intended for training for billions
of environment steps, such that its lower performance compared to PPO in our
experiments is expected101010Also see the discussions at
https://openreview.net/forum?id=SylOlp4FvH on this. [73]. A2C requires more
interactions with the environment to reach similar performance levels as V-MPO
and TRPO but fails to learn any useful policy in the _Ant_ -task. This slower
learning111111Slow in terms of the required environment steps. Note however
that A2C runs significantly faster than PPO, TRPO and V-MPO in absolute time
due to using less epochs per batch. is at least partially caused by A2C only
using a single update epoch per batch. REINFORCE performance worst on all
environments, which is unsurprising giving the high variance of gradients in
REINFORCE [75]. This also highlights the benefits of the bias-variance trade-
off by the other algorithms as discussed in Section 4.6. We find our
performance-based ranking of the algorithms to be consistent with literature
(e.g., [71, 73, 5]).

Moreover, we remark that A2C is the only algorithm for which we used an
entropy bonus because the learned policies collapsed without it. We showcase
this in our expended experiments in Appendix B.2. This underlines the
usefulness of the (heuristic) constraints of V-MPO, PPO and TRPO on the KL
divergence, which avoid such collapses even without any entropy bonuses. To
further investigate this, we show the average KL divergences between
consecutive policies throughout training in Figure 5. Here, we approximated
the KL divergence using the unbiased estimator [68]

$\hat{D}_{KL}\bigl{(}\pi_{\text{old}}(\cdot\mid
s)\>\|\>\pi_{\text{new}}(\cdot\mid
s)\bigr{)}=\mathbb{E}_{A\sim\pi_{\text{old}}}\biggl{[}\frac{\pi_{\text{new}}(A\mid
s)}{\pi_{\text{old}}(A\mid s)}-1-\ln\frac{\pi_{\text{new}}(A\mid
s)}{\pi_{\text{old}}(A\mid s)}\biggr{]}$

for all algorithms except TRPO, which analytically calculates the exact KL
divergence since it is used within the algorithm. We see that the KL
divergences remain relatively constant for all algorithms after some initial
movement. TRPO displays the most constant KL divergence, which is explained by
its hard constraint. With the chosen hyperparameters, V-MPO uses the same
bound on the KL divergence as TRPO, however without strictly enforcing it as
outlined in the derivation of V-MPO. Thus, V-MPO’s KL divergence exhibits
slightly more variance then TRPO and also frequently exceeds this bound. PPO’s
clipping heuristic achieves a similar effect resulting in a comparable
picture. Due to the lack of constraints on the KL divergence, A2C and
REINFORCE show slightly more variance. Interestingly, their KL divergences are
orders of magnitudes lower than for the other algorithms, especially for
REINFORCE (note the logarithmic scale in Figure 5). We reason this with A2C
and REINFORCE using only a singly update epoch per batch, whereas the PPO and
V-MPO use multiple epochs and TRPO uses a different update scheme via line
search. In Appendix B.3, we provide experimental evidence for this hypothesis.
Additionally, we note again that the entropy bonus also stabilizes and limits
the KL divergence for A2C as shown in Appendix B.2.

Figure 5: Comparison of the average KL divergence across policies during
training.

These findings highlight the benefits of regularization through constraining
the KL divergence and incentivizing entropy. Regularization stabilizes
learning and prevents a collapse of the policy. At the same time, it allows
more frequent updates through multiple epochs per batch, which drastically
increases the sample efficiency of the algorithms and speeds up learning.

##  7 Conclusion

In this work, we presented a holistic overview of on-policy policy gradient
methods in reinforcement learning. We derived the theoretical foundations of
policy gradient algorithms, primarily in the form of the Policy Gradient
Theorem. We have shown how the most prominent policy gradient algorithms can
be derived based on this theorem. We discussed common techniques used by these
algorithms to stabilize training including learning an advantage function to
limit the variance of estimated policy gradients, constraining the divergence
between policies and regularizing the policy through entropy bonuses.
Subsequently, we presented evidence from literature on the convergence
behavior of policy gradient algorithms, which suggest that they may find at
least locally optimal policies. Finally, we conducted numerical experiments on
well-established benchmarks to further compare the behavior of the discussed
algorithms. Here, we found that PPO outperforms the other algorithms in the
majority of the considered tasks and we provided evidence for the necessity of
regularization, by constraining KL divergence or by incentivizing entropy, to
stabilize training.

We acknowledge several limitations of our work. First, we deliberately limited
our scope to on-policy algorithms, which excludes closely related off-policy
policy gradient algorithms and the novelties introduced by them. Second, we
presented an incomplete overview of on-policy policy gradient algorithms as
other, albeit less established, algorithms exist (e.g., [61, 16]) and the
development of further algorithms remains an active research field. Here, we
focused on the, in our view, most prominent algorithms as determined by their
impact, usage and introduced novelties. Third, the convergence results we
referenced rest on assumptions that are quickly violated in practice. In
particular, we want to underline that the results based mirror learning rely
on the infeasible assumption of finding a global maximizer each iteration.
Fourth, while we compared the discussed algorithms empirically and found
results to be consistent with existing literature, our analysis is limited to
the specific setting we used. Different results may arise on other benchmarks,
with different hyperparameters or generally different implementations.

Finally, we note that still many questions remain to be answered in the field
of on-policy policy gradient algorithm. So far, our understanding of which
algorithm performs best under which circumstances is still limited. Moreover,
it is unclear whether the best possible policy gradient algorithm has yet been
discovered, which is why algorithm development remains of interest. Similarly,
comprehensive empirical comparisons with other classes of RL algorithms may
yield further insights on the practical advantages and disadvantages of policy
gradient algorithms and how their performance depends on the problem settings.
Finally, we observe that still only a limited number of convergence results
exist and not even all discussed algorithms are covered by these, e.g., no
convergence results exist for V-MPO to the best of our knowledge. Here,
further research is needed to enhance our understanding of the convergence
behavior of policy gradient algorithms.

## References

  * [1] Abbas Abdolmaleki, Jost Tobias Springenberg, Jonas Degrave, Steven Bohez, Yuval Tassa, Dan Belov, Nicolas Heess, and Martin Riedmiller.  Relative entropy regularized policy iteration.  arXiv preprint arXiv:1812.02256, 2018.
  * [2] Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller.  Maximum a posteriori policy optimisation.  arXiv preprint arXiv:1806.06920, 2018.
  * [3] Joshua Achiam.  Spinning Up in Deep Reinforcement Learning.  2018\.
  * [4] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  Optimality and approximation with policy gradient methods in markov decision processes.  In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 64–66. PMLR, 09–12 Jul 2020.
  * [5] Marcin Andrychowicz, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphael Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, et al.  What matters in on-policy reinforcement learning? a large-scale empirical study.  arXiv preprint arXiv:2006.05990, 2020.
  * [6] Lawrence M Ausubel and Raymond J Deneckere.  A generalized theorem of the maximum.  Economic Theory, 3(1):99–107, 1993.
  * [7] Andrew G Barto, Richard S Sutton, and Charles W Anderson.  Neuronlike adaptive elements that can solve difficult learning control problems.  IEEE transactions on systems, man, and cybernetics, (5):834–846, 1983.
  * [8] Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  Operations Research Letters, 31(3):167–175, 2003.
  * [9] Richard Bellman.  Dynamic programming.  Science, 153(3731):34–37, 1966.
  * [10] Julius Berner, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen.  The modern mathematics of deep learning.  arXiv preprint arXiv:2105.04026, pages 86–114, 2021.
  * [11] Jalaj Bhandari and Daniel Russo.  On the linear convergence of policy gradient methods for finite mdps.  In International Conference on Artificial Intelligence and Statistics, pages 2386–2394. PMLR, 2021.
  * [12] Stephen P Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [13] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang.  JAX: composable transformations of Python+NumPy programs, 2018\.
  * [14] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [15] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun.  The loss surfaces of multilayer networks.  In Artificial intelligence and statistics, pages 192–204. PMLR, 2015.
  * [16] Karl W Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman.  Phasic policy gradient.  In International Conference on Machine Learning, pages 2020–2027. PMLR, 2021.
  * [17] George Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989\.
  * [18] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio.  Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.  Advances in neural information processing systems, 27, 2014.
  * [19] Thomas Degris, Martha White, and Richard S Sutton.  Off-policy actor-critic.  arXiv preprint arXiv:1205.4839, 2012.
  * [20] Arthur P Dempster, Nan M Laird, and Donald B Rubin.  Maximum likelihood from incomplete data via the em algorithm.  Journal of the royal statistical society: series B (methodological), 39(1):1–22, 1977.
  * [21] Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov.  Openai baselines.  https://github.com/openai/baselines, 2017.
  * [22] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [23] C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem.  Brax - a differentiable physics engine for large scale rigid body simulation, 2021.
  * [24] Scott Fujimoto, Herke Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  In International conference on machine learning, pages 1587–1596. PMLR, 2018.
  * [25] Xavier Glorot, Antoine Bordes, and Yoshua Bengio.  Deep sparse rectifier neural networks.  In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 315–323. JMLR Workshop and Conference Proceedings, 2011.
  * [26] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * [27] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter.  Variance reduction techniques for gradient estimates in reinforcement learning.  Journal of Machine Learning Research, 5(9), 2004.
  * [28] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In International conference on machine learning, pages 1861–1870. PMLR, 2018.
  * [29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [30] Magnus R Hestenes, Eduard Stiefel, et al.  Methods of conjugate gradients for solving linear systems.  Journal of research of the National Bureau of Standards, 49(6):409–436, 1952.
  * [31] Timothy Classen Hesterberg.  Advances in importance sampling.  Stanford University, 1988.
  * [32] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [33] Matthew W. Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron, Nikola Momchev, Danila Sinopalnikov, Piotr Stańczyk, Sabela Ramos, Anton Raichuk, Damien Vincent, Léonard Hussenot, Robert Dadashi, Gabriel Dulac-Arnold, Manu Orsini, Alexis Jacq, Johan Ferret, Nino Vieillard, Seyed Kamyar Seyed Ghasemipour, Sertan Girgin, Olivier Pietquin, Feryal Behbahani, Tamara Norman, Abbas Abdolmaleki, Albin Cassirer, Fan Yang, Kate Baumli, Sarah Henderson, Abe Friesen, Ruba Haroun, Alex Novikov, Sergio Gómez Colmenarejo, Serkan Cabi, Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Andrew Cowie, Ziyu Wang, Bilal Piot, and Nando de Freitas.  Acme: A research framework for distributed reinforcement learning.  arXiv preprint arXiv:2006.00979, 2020.
  * [34] Markus Holzleitner, Lukas Gruber, José Arjona-Medina, Johannes Brandstetter, and Sepp Hochreiter.  Convergence proof for actor-critic methods applied to ppo and rudder.  In Transactions on Large-Scale Data-and Knowledge-Centered Systems XLVIII: Special Issue In Memory of Univ. Prof. Dr. Roland Wagner, pages 105–130. Springer, 2021.
  * [35] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  Neural networks, 2(5):359–366, 1989.
  * [36] Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Kinal Mehta, and João G.M. Araújo.  Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms.  Journal of Machine Learning Research, 23(274):1–18, 2022.
  * [37] David R Hunter and Kenneth Lange.  A tutorial on mm algorithms.  The American Statistician, 58(1):30–37, 2004.
  * [38] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267–274, 2002.
  * [39] Prasenjit Karmakar and Shalabh Bhatnagar.  Two time-scale stochastic approximation with controlled markov noise and off-policy temporal-difference learning.  Mathematics of Operations Research, 43(1):130–151, 2018.
  * [40] Henry J Kelley.  Gradient theory of optimal flight paths.  Ars Journal, 30(10):947–954, 1960.
  * [41] Jack Kiefer and Jacob Wolfowitz.  Stochastic estimation of the maximum of a regression function.  The Annals of Mathematical Statistics, pages 462–466, 1952.
  * [42] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [43] Vijay R Konda and John N Tsitsiklis.  Onactor-critic algorithms.  SIAM journal on Control and Optimization, 42(4):1143–1166, 2003\.
  * [44] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25, 2012.
  * [45] Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang.  Trust region policy optimisation in multi-agent reinforcement learning.  arXiv preprint arXiv:2109.11251, 2021.
  * [46] Jakub Grudzien Kuba, Christian Schroeder de Witt, and Jakob Foerster.  Mirror learning: A unifying framework of policy optimisation.  arXiv preprint arXiv:2201.02373, 2022.
  * [47] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [48] Johannes Lederer.  Activation functions in artificial neural networks: A systematic overview.  arXiv preprint arXiv:2101.09957, 2021.
  * [49] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph E. Gonzalez, Michael I. Jordan, and Ion Stoica.  RLlib: Abstractions for distributed reinforcement learning.  In International Conference on Machine Learning (ICML), 2018.
  * [50] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  arXiv preprint arXiv:1509.02971, 2015.
  * [51] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang.  Neural proximal/trust region policy optimization attains globally optimal policy.  arXiv preprint arXiv:1906.10306, 2019.
  * [52] Peter Marbach and John N Tsitsiklis.  Simulation-based optimization of markov reward processes.  IEEE Transactions on Automatic Control, 46(2):191–209, 2001.
  * [53] Charles C Margossian.  A review of automatic differentiation and its efficient implementation.  Wiley interdisciplinary reviews: data mining and knowledge discovery, 9(4):e1305, 2019.
  * [54] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In International conference on machine learning, pages 1928–1937. PMLR, 2016.
  * [55] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, 2015.
  * [56] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of Machine Learning.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2 edition, 2018.
  * [57] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In Proceedings of the 27th international conference on machine learning (ICML-10), pages 807–814, 2010.
  * [58] David Pollard.  Asymptopia: an exposition of statistical asymptotic theory.  In Asymptopia: an exposition of statistical asymp-totic theory, 2000\.
  * [59] Boris T Polyak.  Some methods of speeding up the convergence of iteration methods.  Ussr computational mathematics and mathematical physics, 4(5):1–17, 1964.
  * [60] Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann.  Stable-baselines3: Reliable reinforcement learning implementations.  Journal of Machine Learning Research, 22(268):1–8, 2021.
  * [61] Md Masudur Rahman and Yexiang Xue.  Robust policy optimization in deep reinforcement learning.  arXiv preprint arXiv:2212.07536, 2022.
  * [62] Prajit Ramachandran, Barret Zoph, and Quoc V Le.  Searching for activation functions.  arXiv preprint arXiv:1710.05941, 2017.
  * [63] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  The annals of mathematical statistics, pages 400–407, 1951.
  * [64] Herbert Robbins and David Siegmund.  A convergence theorem for non negative almost supermartingales and some applications.  In Optimizing methods in statistics, pages 233–257. Elsevier, 1971\.
  * [65] Reuven Y. Rubinstein.  Simulation and the Monte Carlo Method.  Wiley, New York, first edition, 1981.
  * [66] David E Rumelhart, Geoffrey E Hinton, Ronald J Williams, et al.  Learning internal representations by error propagation, 1985.
  * [67] Gavin A Rummery and Mahesan Niranjan.  On-line Q-learning using connectionist systems, volume 37.  University of Cambridge, Department of Engineering Cambridge, UK, 1994\.
  * [68] John Schulman.  Approximating kl divergence.  John Schulman’s Homepage, 2020.
  * [69] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897. PMLR, 2015.
  * [70] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel.  High-dimensional continuous control using generalized advantage estimation.  arXiv preprint arXiv:1506.02438, 2015.
  * [71] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [72] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of go with deep neural networks and tree search.  Nature, 529(7587):484–489, 2016.
  * [73] H Francis Song, Abbas Abdolmaleki, Jost Tobias Springenberg, Aidan Clark, Hubert Soyer, Jack W Rae, Seb Noury, Arun Ahuja, Siqi Liu, Dhruva Tirumala, et al.  V-mpo: On-policy maximum a posteriori policy optimization for discrete and continuous control.  arXiv preprint arXiv:1909.12238, 2019.
  * [74] Richard S Sutton and Andrew G Barto.  Toward a modern theory of adaptive networks: expectation and prediction.  Psychological review, 88(2):135, 1981.
  * [75] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  The MIT Press, second edition, 2018.
  * [76] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  Advances in neural information processing systems, 12, 1999.
  * [77] Richard S Sutton, Satinder Singh, and David McAllester.  Comparing policy-gradient algorithms.  IEEE Transactions on Systems, Man, and Cybernetics, 2000.
  * [78] Richard Stuart Sutton.  Temporal credit assignment in reinforcement learning.  University of Massachusetts Amherst, 1984.
  * [79] Gerald Tesauro et al.  Temporal difference learning and td-gammon.  Communications of the ACM, 38(3):58–68, 1995.
  * [80] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033. IEEE, 2012.
  * [81] Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Perez-Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis.  Gymnasium, March 2023.
  * [82] Hado van Hasselt.  Reinforcement learning lecture 5: Model-free prediction, October 2021\.
  * [83] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [84] Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  1989\.
  * [85] Lilian Weng.  Policy gradient algorithms.  lilianweng.github.io, 2018.
  * [86] Robert Edwin Wengert.  A simple automatic derivative evaluation program.  Communications of the ACM, 7(8):463–464, 1964.
  * [87] Ronald J Williams.  Reinforcement-learning connectionist systems.  College of Computer Science, Northeastern University, 1987.
  * [88] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Reinforcement learning, pages 5–32, 1992.
  * [89] Ronald J Williams and Jing Peng.  Function optimization using connectionist reinforcement learning algorithms.  Connection Science, 3(3):241–268, 1991.
  * [90] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar.  Global convergence of policy gradient methods to (almost) locally optimal policies.  SIAM Journal on Control and Optimization, 58(6):3586–3612, 2020\.

##  Appendix A Hyperparameters

| Value
---|---
Hyperparameter | REINFORCE | A2C | TRPO | PPO | V-MPO
Learning rate | $3\cdot 10^{-4}$ | $3\cdot 10^{-4}$ | $3\cdot 10^{-4}$ | $3\cdot 10^{-4}$ | $3\cdot 10^{-4}$
Num. minibatches | $1$ | $8$ | $8$ | $8$ | $8$
Num. epochs | $1$ | $1$ |  $1$121212TRPO uses one epoch for its policy updates but 10 epochs per batch for updating the value network. | $10$ | $10$
Discount ($\gamma$) | — | $0.99$ | $0.99$ | $0.99$ | $0.99$
GAE parameter ($\lambda$) | — | $0.95$ | $0.95$ | $0.95$ | $0.95$
Normalize advantages | — | True | True | True | False
Entropy bonus coef. | $0$ | $0.1$ | $0$ | $0$ | $0$
Max. grad. norm | $0.5$ | $0.5$ | $0.5$ | $0.5$ | $0.5$
Unroll length | — | $2048$ | $2048$ | $2048$ | $2048$
KL target ($\delta$) | — | — | $0.01$ | — | —
CG damping | — | — | $0.1$ | — | —
CG max. iterations | — | — | $10$ | — | —
Line search max. iterations | — | — | $10$ | — | —
Line search shrinkage factor | — | — | $0.8$ | — | —
PPO clipping ($\varepsilon$) | — | — | — | $0.2$ | —
Min. temp. ($\eta_{\text{min}}$) | — | — | — | — | $10^{-8}$
Min. KL pen. ($\nu_{\text{min}}$) | — | — | — | — | $10^{-8}$
Init. temp. ($\eta_{\text{init}}$) | — | — | — | — | $1$
Init. KL pen. (mean) ($\nu_{\mu_{\text{init}}}$) | — | — | — | — | $1$
Init. KL pen. (std) ($\nu_{\sigma_{\text{init}}}$) | — | — | — | — | $1$
KL target (mean) ($\varepsilon_{\nu_{\mu}}$) | — | — | — | — | $0.01$
KL target (std) ($\varepsilon_{\nu_{\sigma}}$) | — | — | — | — | $5\cdot 10^{-5}$
KL target (temp.) ($\varepsilon_{\eta}$) | — | — | — | — | $0.01$
Table 2: Algorithm hyperparameters.

We report the hyperparameters we use in our main experiments in Table 2. All
algorithms use separate policy and value networks. Policy networks use 4
hidden layers with 32 neurons respectively. Value networks use 5 layers with
256 neurons each. We use swish-activation functions [62] throughout both
networks. Policy outputs are transformed to fit the bounds of the actions
spaces via a squashing function. We use the Adam optimizer [42] with gradient
clipping and a slight linear decay of the learning rates. Further, we
preprocess observations and rewards by normalizing them using running means
and standard deviations and clipping them to the interval $[-10,10]$. All
algorithms except REINFORCE use 8 parallel environments to collect experience.
We use independent environments to evaluate the agents throughout training. In
the evaluations, agents select actions deterministically as the mode of the
constructed distribution.

##  Appendix B Extended Experiments

Here, we present results from further experiments. Unless indicated otherwise,
we use the hyperparameters as reported in Appendix Appendix A.

###  B.1 Comparison to RL frameworks

In Table 3, we compare the performance of our implementation of PPO with
popular RL frameworks. Note that we did not tune any hyperparameters for our
implementations such that the reported scores should be understood as lower
bounds. We compare PPO since it is the most popular and commonly implemented
of the discussed algorithms across frameworks. In contrast, especially TRPO
and V-MPO are rarely found.

| Framework
---|---
| CleanRL | Baselines | SB3 | RLlib | ACME131313Numbers read approximately from plots in the paper. | Ours | Ours
| [36] | [21] | [60] | [49] | [33] |  |
MuJoCo version | v4 | v1 | v3 | v2 | v2 | v4 | v4
Steps in million | $1$ | $1$ | $1$ | $44$ | $10$ | $1$ | $8$
HalfCheetah | $2906$ | $1669$ | $5819$ | $9664$ | $6800$ | $4332$ | $6414$
Hopper | $2052$ | $2316$ | $2410$ | — | $2550$ | $895$ | $2616$
Humanoid | $742$ | — | — | — | $6600$ | $700$ | $7633$
Ant | — | — | $1327$ | — | $5200$ | $1258$ | $5671$
Table 3: Comparison of the mean performance of our PPO implementation with
popular RL frameworks. Scores for the frameworks are shown as reported in the
respective paper or documentation.

###  B.2 Entropy Bonus in A2C

In Figure 6, we show that using an entropy bonus improves the performance of
A2C by stabilizing learning. In particular, insufficiently low values of the
entropy coefficient result in a collapse of the policy after some time. This
is visible in a drastic increase in the KL divergences (note the logarithmic
scale).

Figure 6: We compare the episode reward (left) and KL divergence (right) for
different values of the entropy coefficient for A2C on HalfCheetah.

###  B.3 A2C and REINFORCE with Multiple Update Epochs

In Figure 7, we showcase that the KL divergence is low for A2C and REINFORCE
due to using only a single update epoch per batch. On the contrary, when using
multiple epochs, the policies collapse for both algorithms as visible by the
diverging KL divergence and abrupt performance loss. Note, that here we show
this behavior for five epochs, however in our tests A2C and REINFORCE display
similar behaviors already when only using two epochs, albeit the policies then
only collapse after an extended period of time. Further, note that over the
displayed range of environment steps, the algorithms do not yet learn any
useful policies when using a single epoch. However, performance improves for
both A2C and REINFORCE when given more time as depicted in Figure 4.

Figure 7: We compare the episode reward (left) and KL divergence (right) for
different numbers of update epochs for A2C and REINFORCE on HalfCheetah.

##  Appendix C V-MPO: Derivation Details

In the following, we provide a more detailed derivation of the objective
function of V-MPO

$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),$ (36)

$\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{]}$
(37)

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}$ (38)

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 probability of $\pi_{\theta}$ being an improvement 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{)}$ (39)

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}$ (40)

where $\rho$ is some prior distribution to be specified. Using Theorem D.7, we
obtain

$\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{)},$
(41)

where $\psi$ is a distribution 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
between an expectation (E) and a maximization (M) step. In the E-step we
choose the variational distribution $\psi$ to minimize the KL divergence in
Equation (41) to make the lower bound as tight as possible. In the M-step, we
maximize this lower bound and the prior $\ln\rho(\theta)$ to obtain a new
estimate of $\theta^{*}$ via Equation (40).

First, we consider the E-step. Minimizing
$D_{KL}(\psi\>\|\>p_{\theta_{\text{old}}}(\cdot,\cdot\mid\mathcal{I}=1))$
w.r.t. $\psi$ leads to

$\displaystyle\psi(s,a)$
$\displaystyle=p_{\theta_{\text{old}}}(s,a\mid\mathcal{I}=1)$
$\displaystyle=\frac{p_{\theta_{\text{old}}}(s,a)\>p_{\theta_{\text{old}}}(\mathcal{I}=1\mid
s,a)}{p_{\theta_{\text{old}}}(\mathcal{I}=1)}$
$\displaystyle=\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}$

using Bayes’ Theorem (Theorem D.2). Sampling from right-hand side of (39) thus
yields

$\hat{\psi}(s,a)=\frac{\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}}{\sum_{a,s\in\mathcal{D}}\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}},$

which is the variational distribution found in the policy loss (37). [73] find
that using only the highest 50 % of advantages per batch, 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 identically as in A3C.

We derive the temperature loss to automatically adjust the temperature $\eta$
by applying (39) to the KL term in (41), which we want to minimize:

$\displaystyle
D_{KL}\Bigl{(}\psi\>\|\>p(\cdot,\cdot\mid\mathcal{I}=1)\Bigr{)}$
$\displaystyle=D_{KL}\biggl{(}\psi\>\|\>\frac{p_{\theta_{\text{old}}}(S,A)p_{\theta_{\text{old}}}(\mathcal{I}=1\mid
S,A)}{p_{\theta_{\text{old}}}(\mathcal{I}=1)}\biggr{)}$
$\displaystyle=D_{KL}\Biggl{(}\psi\>\|\>\frac{p_{\theta_{\text{old}}}(S,A)\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(S,A)}{\eta}\Bigr{)}}{p_{\theta_{\text{old}}}(\mathcal{I}=1)}\Biggr{)}$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\Biggl{(}\frac{p_{\theta_{\text{old}}}(s,a)\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}}{\psi(s,a)p_{\theta_{\text{old}}}(\mathcal{I}=1)}\Biggr{)}\>da\>ds$

By applying the logarithm to the individual terms, rearranging and multiplying
through by $\eta$ we get

$\displaystyle
D_{KL}\Bigl{(}\psi\>\|\>p(\cdot,\cdot\mid\mathcal{I}=1)\Bigr{)}$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\biggl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}+\ln
p_{\theta_{\text{old}}}(s,a)$ $\displaystyle\qquad-\ln
p_{\theta_{\text{old}}}(\mathcal{I}=1)-\ln\psi(s,a)\biggr{)}\>da\>ds$
$\displaystyle\propto-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\biggl{(}A_{\pi_{\text{old}}}(s,a)+\eta\ln
p_{\theta_{\text{old}}}(s,a)-\eta\ln p_{\theta_{\text{old}}}(\mathcal{I}=1)$
$\displaystyle\qquad-\eta\ln\psi(s,a)\biggr{)}\>da\>ds$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)A_{\pi_{\text{old}}}(s,a)\>da\>ds+\eta\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{\psi(s,a)}{p_{\theta_{\text{old}}}(s,a)}\>da\>ds$
$\displaystyle\qquad+\lambda\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\>da\>ds$

with $\lambda=\eta\ln p_{\theta_{\text{old}}}(\mathcal{I}=1)$. To optimize
$\eta$ while minimizing the KL term, we transform this into a constrained
optimization problem with a bound on the KL divergence

$\displaystyle\operatorname*{arg\,max}_{\psi}$
$\displaystyle\quad\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)A_{\pi_{\text{old}}}(s,a)\>da\>ds$
subject to
$\displaystyle\quad\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{\psi(s,a)}{p_{\theta_{\text{old}}}(s,a)}\>da\>ds\leq\varepsilon_{\eta},$
$\displaystyle\quad\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\>da\>ds=1$

and then back into an unconstrained problem via Lagrangian relaxation,
yielding the objective function

$\displaystyle\mathcal{J}(\psi,\eta,\lambda)$
$\displaystyle=\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)A_{\pi_{\text{old}}}(s,a)\>da\>ds+\eta\biggl{(}\varepsilon_{\eta}$
$\displaystyle\quad-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{\psi(s,a)}{p_{\theta_{\text{old}}}(s,a)}\>da\>ds\biggr{)}+\lambda\biggl{(}1-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\>da\>ds\biggr{)}.$

Differentiating w.r.t. $\psi(s,a)$ and setting to zero yields

$\psi(s,a)=p_{\theta_{\text{old}}}(s,a)\exp\biggl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\biggr{)}\exp\biggl{(}-1-\frac{\lambda}{\eta}\biggr{)}$

Normalizing over $s$ and $a$ confirms the already attained solution

$\psi(s,a)=\frac{p_{\theta_{\text{old}}}(s,a)\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}}{\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}\>da\>ds},$
(42)

but now we can also find the optimal $\eta$ by substituting this solution into
$\mathcal{J}(\psi,\eta,\lambda)$. Doing so and dropping terms independent of
$\eta$ leads to

$\displaystyle\begin{split}\eta&\biggl{(}\varepsilon_{\eta}-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{\psi(s,a)}{p_{\theta_{\text{old}}}(s,a)}\>da\>ds\biggr{)}\\\
&=\eta\varepsilon_{\eta}+\eta\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln
p_{\theta_{\text{old}}}(s,a)\>da\>ds-\eta\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\psi(s,a)\>da\>ds.\end{split}$
(43)

Because of Equation (42), we have

$\displaystyle\eta\psi(s,a)\ln\psi(s,a)$
$\displaystyle=\eta\psi(s,a)\ln\frac{p_{\theta_{\text{old}}}(s,a)\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}}{\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\exp\Bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\Bigr{)}\>da\>ds}$
$\displaystyle=\psi(s,a)\Biggl{(}\eta\ln
p_{\theta_{\text{old}}}(s,a)+A_{\pi_{\text{old}}}(s,a)-\eta\ln\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\exp\biggl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\biggr{)}\>da\>ds\Biggr{)},$

where the first summand cancels out the second term in (43) and the second
summand no longer depends on $\eta$ and thus can be dropped. Hence, we obtain
the temperature loss function

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

through which we can optimize $\eta$ using gradient descent.

Given the non-parametric sample-based variational distribution $\psi(s,a)$,
the M-step now optimizes the policy parameters $\theta$. Based on (40), we
want to maximize the discussed lower bound, i.e. minimize

$-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{p_{\theta}(\mathcal{I}=1,s,a)}{\psi(s,a)}\>da\>ds-\ln
p(\theta)$

to find new policy parameters $\theta$. Using Equations (42) and (39), the
first term becomes

$\displaystyle-$
$\displaystyle\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{p_{\theta}(\mathcal{I}=1,s,a)}{\psi(s,a)}\>da\>ds$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{p_{\theta}(\mathcal{I}=1\mid
s,a)p_{\theta}(s,a)}{\psi(s,a)}\>da\>ds$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\biggl{(}\frac{\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}p_{\theta}(s,a)}{p_{\theta_{\text{old}}}(s,a)\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}}\frac{1}{\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}\>da\>ds}\biggr{)}\>da\>ds$
$\displaystyle=-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\biggl{(}\frac{p_{\theta}(s,a)}{p_{\theta_{\text{old}}}(s,a)}\frac{1}{\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}p_{\theta_{\text{old}}}(s,a)\exp\bigl{(}\frac{A_{\pi_{\text{old}}}(s,a)}{\eta}\bigr{)}\>da\>ds}\biggr{)}\>da\>ds.$

Using $p_{\theta}(s,a)=\pi_{\theta}(a\mid s)d^{\pi_{\theta}}(s)$, assuming the
state distribution $d^{\pi}$ to be independent of $\theta$ and dropping terms
that do not depend on $\theta$ yields

$\displaystyle\operatorname*{arg\,min}_{\theta}\biggl{(}-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{p_{\theta}(\mathcal{I}=1,s,a)}{\psi(s,a)}\>da\>ds\biggr{)}$
$\displaystyle=\operatorname*{arg\,min}_{\theta}\biggl{(}-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln
p_{\theta}(s,a)\>da\>ds\biggr{)}$
$\displaystyle=\operatorname*{arg\,min}_{\theta}\biggl{(}-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\pi_{\theta}(a\mid
s)\>da\>ds\biggr{)},$

which is the weighted maximum likelihood policy loss as in (36), that we
compute on sampled transitions, effectively assigning out-of-sample
transitions a weight of zero.

A useful prior $\rho(\theta)$ in Equation (40) is to keep the new policy close
to the previous one as in TRPO and PPO. This translates to

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

Since optimizing the resulting sample-based maximum likelihood objective
directly tends to result in overfitting, this prior is instead transformed
into a constraint on the KL-divergence with bound $\varepsilon_{\nu}$, i.e.

$\displaystyle\operatorname*{arg\,min}_{\theta}$
$\displaystyle\quad\biggl{(}-\int_{s\in\mathcal{S}}\int_{a\in\mathcal{A}}\psi(s,a)\ln\frac{p_{\theta}(\mathcal{I}=1,s,a)}{\psi(s,a)}\>da\>ds\biggr{)}$
subject to $\displaystyle\quad\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{]}\leq\varepsilon_{\nu}.$

To employ gradient-based optimization, we use Lagrangian relaxation to
transform this constraint optimization problem back into the unconstrained
problem

$\mathcal{J}(\theta,\nu)=\mathcal{L}_{\pi}(\theta)+\nu\bigl{(}\varepsilon_{\nu}-\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\bigl{[}D_{KL}(\pi_{\text{old}}(\cdot\mid
S)\|\pi_{\theta}(\cdot\mid S))\bigr{]}\bigr{)}.$ (45)

This problem is solved by alternating between optimizing for $\theta$ and
$\nu$ via gradient descent in a coordinate-descent strategy. Using the stop-
gradient operator $\mathrm{sg}[[\cdot]]$, the objective can equivalently to
this strategy be rewritten for as

$\displaystyle\mathcal{L}_{\nu}(\theta,\nu)=\nu\biggl{(}\varepsilon_{\nu}-\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\biggl{[}\mathrm{sg\Bigl{[}\Bigl{[}D_{KL}\bigl{(}\pi_{\theta_{\text{old}}}(\cdot\mid
S)\>\|\>\pi_{\theta}(\cdot\mid
S)\bigr{)}\Bigr{]}\Bigr{]}\biggr{]}}\biggr{)}+\mathrm{sg}\bigl{[}\bigl{[}\nu\bigr{]}\bigr{]}\mathbb{E}_{S\sim
d^{\pi_{\text{old}}}}\Bigl{[}D_{KL}\bigl{(}\pi_{\theta_{\text{old}}}(\cdot\mid
S)\>\|\>\pi_{\theta}(\cdot\mid S)\bigr{)}\Bigr{]}.$

Sampling this gives Equation (38). $\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.

##  Appendix D Auxiliary Theory

Here, we list a range of well-known definitions and results that we use in our
work.

######  Definition D.1.

(Compact Space) A topological space $X$ is called compact if for every set $S$
of open covers of $X$, there exists a finite subset $S^{\prime}\subset S$ that
also is an open cover of $X$.

######  Theorem D.2.

(Bayes’ Theorem) Let $(\Omega,\mathcal{A},\mathbb{P})$ be a probability space
and $\bigcup_{i\in I}B_{i}$ be a disjoint and finite partition of $\Omega$
with $B_{i}\in\mathcal{A}$ and $\mathbb{P}(B_{i})>0$ for $i~\in I$. Then, for
all $A\in\mathcal{A}$ and all $k\in I$

$\mathbb{P}(B_{k}\mid A)=\frac{\mathbb{P}(A\mid
B_{k})\mathbb{P}(B_{k})}{\sum_{i\in I}\mathbb{P}(A~\mid
B_{i})\mathbb{P}(B_{i})}.$

######  Theorem D.3.

Let $X$ be a random variable. Then,

$\mathrm{Var}[X]=\mathbb{E}\bigl{[}X^{2}\bigr{]}-\mathbb{E}\bigl{[}X\bigr{]}^{2}.$

######  Definition D.4.

(Entropy) Let $(\Omega,\mathcal{A},\mathbb{P})$ be a probability space and
$X\sim\mathbb{P}$ be a random variable. The entropy of $X$ is given by

$H(X)\coloneqq\mathbb{E}_{X\sim\mathbb{P}}\bigl{[}-\ln\mathbb{P}(X)\bigr{]}.$

######  Definition D.5.

(Kullback-Leibler Divergence) For any measurable space $\mathcal{A}$ and
probability densities $p$ and $q$ of the respective distributions $P$ and $Q$,
the Kullback-Leibler divergence or relative entropy from $Q$ to $P$ is given
by

$D_{KL}(p\|q)\coloneqq\int_{a\in\mathcal{A}}p(a)\ln\frac{p(a)}{q(a)}da.$

######  Definition D.6.

(Total Variation Divergence) For any measurable space $\mathcal{A}$ and
probability densities $p$ and $q$ of the respective distributions $P$ and $Q$,
the total variation variance from $Q$ to $P$ is given by

$D_{TV}(p\|q)\coloneqq\frac{1}{2}\int_{a\in\mathcal{A}}p(a)-q(a)da.$

######  Theorem D.7.

Let $(\Omega,\mathcal{A})$ be a measurable space and $p$ and $\psi$ be
probability measures on that space. Let and $X\in\mathcal{A}$ and
$Z\in\mathcal{A}$. Then,

$\ln
p(X)=\mathbb{E}_{Z\sim\psi}\biggl{[}\ln\frac{p(X,Z)}{\psi(Z)}\biggr{]}+D_{KL}(\psi\>\|\>p(\cdot\mid
X)).$

######  Theorem D.8.

Let $X$ be a random variable. Then,

$\min_{a}\mathbb{E}\bigl{[}(X-a)^{2}\bigr{]}=\mathbb{E}[X].$

######  Theorem D.9.

Let $(\mathcal{A},\Sigma)$ be a measurable space with $\sigma$-finite measures
$\mu$ and $\nu$ such that $\nu$ is absolutely continuous in $\mu$. Let $g$ be
a Radon-Nikodym derivative of $\nu$ w.r.t. $\mu$, i.e.
$\nu(A)=\int_{A}g\>d\mu$ for all $A\in\Sigma$. Let, $f$ be a $\nu$-integrable
function. Then,

$\int_{\mathcal{A}}f\>d\nu=\int_{\mathcal{A}}(f\cdot g)\>d\mu.$

######  Theorem D.10.

(Leibniz Integral Rule) Let $X$ be an open subset of $\mathbb{R}^{d}$,
$d\in\mathbb{N}$. Let $\mathcal{A}$ be a measurable set and $f\colon
X\times\mathcal{A}\rightarrow\mathbb{R}$ be a function which satisfies

  1. 1.

$f(x,a)$ is a Lebesgue-integrable function of $a$ for all $x\in X$.

  2. 2.

For almost all $a\in\mathcal{A}$, all partial derivatives exist for all $x\in
X$.

  3. 3.

There exists some integrable function
$g\colon\mathcal{A}\rightarrow\mathbb{R}$ with
$\lvert\nabla_{x}f(x,a)\rvert\leq g(a)$ for all $x\in X$ and almost all
$a\in\mathcal{A}$.

Then, for all $x\in X$ we have

$\nabla_{x}\int_{a\in\mathcal{A}}f(x,a)da=\int_{a\in\mathcal{A}}\nabla_{x}f(x,a)da$

######  Theorem D.11.

(Fubini’s Theorem) Let $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ be measurable
spaces with measures $\mu_{1}$ and $\mu_{2}$ and
$f\colon\mathcal{A}_{1}\times\mathcal{A}_{2}\rightarrow\mathbb{R}$ be
measurable and integrable w.r.t. the product measure $\mu_{1}\otimes\mu_{2}$,
i.e. $\int_{\mathcal{A}_{1}\times\mathcal{A}_{2}}\lvert
f\rvert\>d(\mu_{1}\otimes\mu_{2})<\infty$ or $f\geq 0$ almost everywhere.
Then, $f(x,y)$ is integrable for almost all $x$ and $y$ and

$\int_{\mathcal{A}_{1}}\int_{\mathcal{A}_{2}}f(x,y)\>d\mu_{1}(x)\>d\mu_{2}(y)=\int_{\mathcal{A}_{2}}\int_{\mathcal{A}_{1}}f(x,y)\>d\mu_{2}(y)\>d\mu_{1}(x)$

######  Theorem D.12.

(Taylor’s Theorem - one-dimensional) Let $k\in\mathbb{N}$ and let
$f\colon\mathbb{R}\rightarrow\mathbb{R}$ be $k$-times differentiable at
$a\in\mathbb{R}$. Then, there exists a function
$h_{k}\colon\mathbb{R}\rightarrow\mathbb{R}$ such that

$f(x)=\sum^{k}_{i=0}\frac{f^{(i)}(a)}{i!}(x-a)^{i}+h_{k}(x)(x-a)^{k}.$

######  Theorem D.13.

(Monotone Convergence Theorem) Let
$\bigl{(}x_{n}\bigr{)}^{\infty}_{n=0}\subset\mathbb{R}$ be a bounded and
monotonically increasing sequence. Then, the sequence converges, i.e.
$\lim_{n\to\infty}x_{n}$ exists and is finite.

######  Theorem D.14.

(Bolzano-Weierstrass Theorem) Let
$\bigl{(}x_{n}\bigr{)}^{\infty}_{n=0}\subset\mathbb{R}^{d}$, $d\in\mathbb{N}$
be a bounded sequence. Then, there exists some convergent subsequence
$\bigl{(}x_{n_{i}}\bigr{)}^{\infty}_{i=0}$.

######  Theorem D.15.

(Berge’s Maximum Theorem) Let $X$ and $\Theta$ be topological spaces, $f\colon
X\times\Theta\rightarrow\mathbb{R}$ be continuous on $X\times\Theta$ and
$C\colon\Theta\rightrightarrows X$ be a compact-valued correspondence with
$C(\theta)\neq\emptyset$ for all $\theta\in\Theta$. Let

$f^{*}(\theta)=\sup\bigl{\\{}f(x,\theta)\mid x~\in C(\theta)\bigr{\\}}$

and

$C^{*}(\theta)=\operatorname*{arg\,max}\bigl{\\{}f(x,\theta)\mid x\in
C(\theta)\bigr{\\}}=\bigl{\\{}x\in C(\theta)\mid
f(x,\theta)=f^{*}(\theta)\bigr{\\}}.$

If $C$ is continuous at $\theta$, then $f^{*}$ is continuous and $C^{*}$ is
upper hemicontinuous with nonempty and compact values.

######  Definition D.16.

(Gâteaux Derivative) Let $X$ and $Y$ be locally convex topological spaces, let
$U$ be an open subset of $X$ and $F\colon U\rightarrow Y$. The Gâteaux
derivative of $F$ at $x\in U$ in the direction $d\in X$ is defined as

$dF(x,d)=\lim_{h\to 0}\frac{F(x+rd)-F(x)}{r}.$