11institutetext: Ludwig-Maximilians University, Munich, Germany 11email:
<EMAIL_ADDRESS>Technical University of Munich, Munich,
Germany 22email<EMAIL_ADDRESS>
33institutetext: Siemens Technology, Munich, Germany
33email<EMAIL_ADDRESS>
# Safe Policy Improvement Approaches and their Limitations

Philipp Scholl 11 Felix Dietrich 22 Clemens Otte 33 Steffen Udluft 33

###### Abstract

Safe Policy Improvement (SPI) is an important technique for offline
reinforcement learning in safety critical applications as it improves the
behavior policy with a high probability. We classify various SPI approaches
from the literature into two groups, based on how they utilize the uncertainty
of state-action pairs. Focusing on the Soft-SPIBB (Safe Policy Improvement
with Soft Baseline Bootstrapping) algorithms, we show that their claim of
being provably safe does not hold. Based on this finding, we develop
adaptations, the Adv-Soft-SPIBB algorithms, and show that they are provably
safe. A heuristic adaptation, Lower-Approx-Soft-SPIBB, yields the best
performance among all SPIBB algorithms in extensive experiments on two
benchmarks. We also check the safety guarantees of the provably safe
algorithms and show that huge amounts of data are necessary such that the
safety bounds become useful in practice.

###### Keywords:

Risk-Sensitive Reinforcement Learning Safe Policy Improvement Markov Decision
Processes.

##  1 Introduction

Reinforcement learning (RL) in industrial control applications such as gas
turbine control [17] often requires learning solely from pre-recorded
observational data (called offline or batch RL [9, 4, 12]) to avoid a
potentially unsafe online exploration. This is especially necessary when
simulations of the system are not available. Since it is difficult to assess
the actual quality of the learned policy in this situation [6, 24], Safe
Policy Improvement (SPI) [23, 14] is an attractive option. SPI aims to ensure
that the learned policy is, with high probability, at least approximately as
good as the behavioral policy given, for example, by a conventional
controller.

In this paper, we review and benchmark current SPI algorithms and divide them
into two classes. Among them, we focus on the class of Soft-SPIBB algorithms
[14] and show that they are, contrary to the authors’ claim, not provably
safe. Therefore, we introduce the adaptation Adv-Approx-Soft-SPIBB. We also
develop the heuristic Lower-Approx-Soft-SPIBB, following an idea presented in
Laroche et al. [10]. Additionally, we conduct experiments to test these
refined algorithms against their predecessors and other promising SPI
algorithms. Here, our taxonomy of the SPI algorithms is helpful, as the two
classes of algorithms show different behavior. In summary, we extend
observations from Scholl et al. [20] in several ways:

  * •

We include a detailed presentation of the competitor SPI algorithms to equip
the reader with an in-depth understanding of various SPI mechanisms and our
taxonomy.

  * •

We present the complete proof of the safety of Adv-Soft-SPIBB with further
adaptations from the one from Nadjahi et al. [14] and discuss the usage of a
tighter error bound (Maurer and Pontil [13]) to strengthen the safety theorem.

  * •

We test empirically the error bounds of all provably safe algorithms to check
their applicability and identify some limitations, as some algorithms need
huge amounts of data to produce good policies while maintaining a meaningful
error bound at the same time.

The code for the algorithms and experiments can be found in the accompanying
repository.111https://github.com/Philipp238/Safe-Policy-Improvement-
Approaches-on-Discrete-Markov-Decision-Processes The next section introduces
the mathematical framework necessary for the later sections. Section 3
introduces other SPI algorithms, divides them into two classes and explains
the most promising ones in more detail. In Section 4, we present the work done
by Nadjahi et al. [14] and show that their algorithms are not provably safe.
In Section 5, we refine the algorithms of Nadjahi et al. [14] and prove the
safety of one of them. Tests against various competitors on two benchmarks are
described in Section 6. The test for the usefulness of the safety guarantees
is discussed in Section 7.

##  2 Mathematical Framework

The control problem we want to tackle with reinforcement learning consists of
an agent and an environment, modeled as a finite Markov Decision Process
(MDP). A finite MDP $M^{*}$ is represented by the tuple
$M^{*}=(\mathcal{S},\mathcal{A},P^{*},R^{*},\gamma)$, where $\mathcal{S}$ is
the finite state space, $\mathcal{A}$ the finite action space, $P^{*}$ the
unknown transition probabilities, $R^{*}$ the unknown stochastic reward
function, the absolute value of which is assumed to be bounded by $R_{max}$,
and $0\leq\gamma<1$ is the discount factor.

The agent chooses action $a\in\mathcal{A}$ with probability $\pi(a|s)$ in
state $s\in\mathcal{S}$, where $\pi$ is the policy controlling the agent. The
return at time $t$ is defined as the discounted sum of rewards
$G_{t}=\sum_{i=t}^{T}\gamma^{i-t}R^{*}(s_{i},a_{i})$, with $T$ the time of
termination of the MDP. As the reward function is bounded the return is
bounded as well, since $|G_{t}|\leq\frac{R_{max}}{1-\gamma}$. So, let
$G_{max}$ be a bound on the absolute value of the return. The goal is to find
a policy $\pi$ which optimizes the expected return, i.e., the state-value
function $V_{M^{*}}^{\pi}(s)=E_{\pi}[G_{t}|S_{t}=s]$ for the initial state
$s\in\mathcal{S}$. Similarly, the action-value function is defined as
$Q_{M^{*}}^{\pi}(s,a)=E_{\pi}[G_{t}|S_{t}=s,A_{t}=a]$.

Given data $\mathcal{D}=(s_{j},a_{j},r_{j},s_{j}^{\prime})_{j=1,\dots,n}$
collected by the baseline policy $\pi_{b}$, let $N_{\mathcal{D}}(s,a)$ denote
the number of visits of the state-action pair $(s,a)$ in $\mathcal{D}$ and
$\hat{M}=(\mathcal{S},\mathcal{A},\hat{P},\hat{R},\gamma)$ the Maximum
Likelihood Estimator (MLE) of $M^{*}$ where

$\hat{P}(s^{\prime}|s,a)=\frac{\sum_{(s_{j}=s,a_{j}=a,r_{j},s_{j}^{\prime}=s^{\prime})\in\mathcal{D}}1}{N_{\mathcal{D}}(s,a)}\text{
and
}\hat{R}(s,a)=\frac{\sum_{(s_{j}=s,a_{j}=a,r_{j},s_{j}^{\prime})\in\mathcal{D}}r_{j}}{N_{\mathcal{D}}(s,a)}.$
(1)

##  3 Related Work

Safety is an overloaded term in Reinforcement Learning, because it can refer
to the inherent uncertainty, safe exploration techniques, or parameter
uncertainty [5]. In this paper we focus on the latter. In the following
subsection we will introduce a taxonomy of SPI algorithms defined by us, and
then go into detail for the most promising methods in the other subsections.

###  3.1 Taxonomy

Many existing Safe Policy Improvement (SPI) algorithms utilize the uncertainty
of state-action pairs in one of the two following ways (see also Figure 1):

  * 1.

The uncertainty is applied to the action-value function to decrease the value
of uncertain actions. Therefore, these algorithms usually adapt the Policy
Evaluation (PE) step.

  * 2.

The uncertainty is used to restrict the set of policies that can be learned.
Therefore, these algorithms usually adapt the Policy Iteration (PI) step.

Figure 1: Taxonomy of SPI algorithms [20].

In the remainder of this section we introduce all algorithms shown in Figure
1, except for High Confidence Policy Improvement (HCPI) [23] and Robust MDP
[15], as they have been shown in Laroche et al. [10] and Nadjahi et al. [14]
to be not competitive in practice against many of the other SPI algorithms. We
also do not introduce the Soft-SPIBB algorithms, as they are investigated in
more detail in Section 4.

###  3.2 RaMDP

Petrik et al. [16] showed that maximizing the difference between the new
policy and a baseline policy on a rectangular uncertainty set of the
transition probabilities is NP-hard and, thus, derived the approximation
Reward-adjusted MDP (RaMDP). RaMDP applies the uncertainty to penalize the
reward and, therefore, the action-value function. Laroche et al. [10] extended
this algorithm by a hyper-parameter which controls the influence of the
uncertainty and modifies the reward matrix to incorporate the uncertainty in
the following way:

$\tilde{R}(s,a)=\hat{R}(s,a)-\frac{\kappa}{\sqrt{N_{\mathcal{D}}(s,a)}},$ (2)

where $\kappa>0$ is some hyper-parameter.

###  3.3 DUIPI

While RaMDP computes the uncertainty simply as a function of the number of
visits to a state-action pair, Schneegass et al. [18] try a more sophisticated
approach to estimate the uncertainty for Diagonal Approximation of Uncertainty
Incorporating Policy Iteration (DUIPI) by approximating the variance of the
action-value function.

Contrary to most other papers which reduce the reward function to
$R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, they consider

$\hat{R}_{3}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R},\quad\hat{R}_{3}(s,a,s^{\prime})=\frac{\sum_{(s_{j}=s,a_{j}=a,r_{j},s_{j}^{\prime}=s^{\prime})\in\mathcal{D}}r_{j}}{N_{\mathcal{D}}(s,a,s^{\prime})}.$
(3)

The calculation of the action-value function for some policy $\pi$ in the MDP
with the estimates $\hat{P}$ and $\hat{R}_{3}$ is classically done by
Iterative Policy Evaluation, i.e., by inserting the estimate of the action-
value function iteratively into the action Bellman equation [22]:

$Q_{k+1}(s,a)=\sum_{s^{\prime}}\hat{P}(s^{\prime}|s,a)(\hat{R}_{3}(s,a,s^{\prime})+\gamma\sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q_{k}(s^{\prime},a^{\prime})).$
(4)

The variance of $Q$ is then also calculated iteratively by using uncertainty
propagation, i.e., the fact that

$\operatorname{Var}(f(X))\approx D\operatorname{Var}(X)D^{T}$ (5)

holds for a function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ with Jacobian
$D_{i,j}=\frac{\partial f_{i}}{\partial x_{j}}$. Schneegass et al. [18]
present two different approaches in their paper, the first makes use of the
complete covariance matrix, while the second neglects the correlations between
state-action pairs. The authors show that the second approach is significantly
faster and that the correlation is less important for MDPs with bigger state
and action spaces. In the benchmark where it made a difference, there were 6
states with 2 actions and in the one where it did not matter anymore there
were 18 states and 4 actions. As all benchmarks considered in this paper use
MDPs which are greater than those two, we concentrate on the second approach
called DUIPI (Diagonal Approximation of Uncertainty Incorporating Policy
Iteration). By neglecting the covariances, Equation 5 becomes

$\operatorname{Var}(f(X))\approx\sum_{i}\left(\frac{\partial f}{\partial
X_{i}}\right)^{2}\operatorname{Var}(X_{i}),$ (6)

which should be read component-wise. Applying Equation 6 to the action-value
update in Equation 4 yields

$\begin{gathered}\operatorname{Var}(Q^{m}(s,a))\approx\sum_{s^{\prime}}(D_{Q,Q}^{m})^{2}\left(\sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})^{2}\operatorname{Var}(Q^{m-1}(s^{\prime},a^{\prime}))\right)\\\
+\sum_{s^{\prime}}D_{Q,\hat{P}}^{m}\operatorname{Var}(\hat{P}(s^{\prime}|s,a))+\sum_{s^{\prime}}D_{Q,\hat{R}_{3}}^{m}\operatorname{Var}(\hat{R}_{3}(s,a,s^{\prime})))\end{gathered}$
(7)

with the derivatives

$\begin{gathered}D_{Q,Q}^{m}=\gamma\hat{P}(s^{\prime}|s,a),\>D_{Q,\hat{P}}^{m}=\hat{R}_{3}(s,a,s^{\prime})+\gamma\sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})^{2}Q^{m-1}(s^{\prime},a^{\prime})\\\
\text{and }D_{Q,\hat{R}_{3}}^{m}=\hat{P}(s^{\prime}|s,a).\end{gathered}$ (8)

Equation 7 shows that the variance of the action-value function at the current
step depends on the variance of the action-value function at the previous step
and on the variance of the estimators $\hat{P}$ and $\hat{R}_{3}$.

To make use of the variance of the action-value function, which is
simultaneously computed in the PE step, the authors propose to define

$Q_{u}(s,a)=Q^{\pi}_{\hat{M}}(s,a)-\xi\sqrt{\operatorname{Var}(Q^{\pi}_{\hat{M}}(s,a))}$
(9)

and use the uncertainty incorporating action-value function $Q_{u}$ instead of
$Q^{\pi}_{\hat{M}}$ in the PI step. The policy is then chosen in a non greedy
way, for details see Schneegass et al. [18]. By choosing $\xi>0$, the
uncertainty of one state-action pair has a negative influence on $Q_{u}$ and
the new policy prefers state-action pairs with a low variance.

Assuming that the variance is well approximated, even though uncertainty
propagation is used and covariances between the state-action pairs are
neglected, and a normal distribution as the prior for the action-value
function is close to reality, yields a confidence interval on the real action-
value function $Q$, as

$\mathbb{P}(Q(s,a)>Q_{u}(s,a))=1-F(\xi)$ (10)

holds, with $Q_{u}$ as defined in Equation 9 and $F$ as the CDF of a standard
normal distribution [18].

One question that remains is how to determine the covariances of the
estimators $\hat{P}$ and $\hat{R}_{3}$. The authors present a Bayesian
approach applying the Dirichlet distribution as a prior for this, which will
be used in this paper.

In the experiments in Section 6 we observed that DUIPI’s estimation of the
transition probabilities results in the possibility that unobserved state-
action pairs are chosen, which is highly dangerous for safe reinforcement
learning. For this reason we implemented a mechanism which checks if a state-
action pair has been visited at least once in the training data and if it has
not been visited, the probability of the new policy to choose this state-
action pair will be set to 0 if possible. In our experiments this adjustment
turned out to yield a strong performance improvement and, thus, we use only
this new implementation of DUIPI for the experiments in the Sections 6 and 7.

###  3.4 R-MIN

Brafman and Tannenholtz [1] introduce the R-MAX algorithm as a simple online
algorithm for exploration. Its basic idea is to set the value of a state-
action pair to the highest possible value, if it has not been visited more
than $N_{\wedge}$ times yet, to encourage the algorithm to try these state-
action pairs for an efficient exploration.

The problem considered in this paper is quite opposite to that. First of all,
we are confronted with a batch offline learning problem. Furthermore, we are
not interested in exploration but in safety. Consequently, we invert their
technique and instead of setting the value of uncertain state-action pairs to
the best possible value, we set it to the worst possible value, which is why
we renamed the algorithm to R-MIN. The action-value function, thus, computes
as

$Q_{k+1}(s,a)=\begin{dcases}\sum_{s^{\prime},r}p(s^{\prime},r|s,a)(r+\gamma\sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q_{k}(s^{\prime},a^{\prime})),&\text{if
}N_{\mathcal{D}}(s,a)>N_{\wedge}\\\ \frac{R_{min}}{1-\gamma},&\text{if
}N_{\mathcal{D}}(s,a)\leq N_{\wedge},\end{dcases}$ (11)

as $\frac{R_{min}}{1-\gamma}$ is the sharpest lower bound on the value
function which works for any MDP, without any additional knowledge about its
structure. Note that it is important to apply Equation 11 in every iteration
of the PE step and not only at the end, as the uncertainty of one state-action
pair should also influence the value of state-action pairs leading to the
uncertain one with a high probability.

###  3.5 SPIBB

Regarding algorithms restricting the policy set, Laroche et al. [10] only
allow deviations from the baseline policy at a state-action pair if the
uncertainty is low enough, otherwise it remains the same. To decide whether
the uncertainty of a state-action pair is high, they only regard the times a
state-action pair has been visited and use the bootstrapped set $\mathcal{B}$
as the set of uncertain state-action pairs, which has been visited less than
some hyperparameter $N_{\wedge}$:

$\mathcal{B}=\\{(s,a)\in\mathcal{S}\times\mathcal{A}:N_{\mathcal{D}}(s,a)\leq
N_{\wedge}\\}.$ (12)

Laroche et al. [10] propose two algorithms: $\Pi_{b}$-SPIBB, which is provably
safe, and $\Pi_{\leq b}$-SPIBB, which is a heuristic relaxation.
$\Pi_{b}$-SPIBB approximately solves the following optimization problem in its
Policy Improvement step:

$\pi^{\prime}=\operatorname*{\arg\max}_{\pi}\sum_{a\in\mathcal{A}}Q^{\pi}_{\hat{M}}(s,a)\pi(a|s)\text{,
subject to:}$ (13a) $\pi^{\prime}(\cdot|s)\text{ being a probability density
over }\mathcal{A}\text{ and }$ (13b)
$\pi^{\prime}(a|s)=\pi_{b}(a|s),\;\forall(s,a)\in\mathcal{B}.$ (13c)

The fact that a policy computed by $\Pi_{b}$-SPIBB equals the behavior policy
$\pi_{b}$ for any state-action pair in the bootstrapped set, enables the
authors to prove that $\Pi_{b}$-SPIBB produces policies $\pi$ for which

$V^{\pi}_{M^{*}}(s)-V^{\pi_{b}}_{M^{*}}(s)\geq-\frac{4V_{max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{S}||\mathcal{A}|2^{|\mathcal{S}|}}{\delta}}$
(14)

holds with probability $1-\delta$ for any state $s\in\mathcal{S}$.

Its heuristic variation $\Pi_{\leq b}$-SPIBB does not exhibit any theoretical
safety. However, it performed even better than $\Pi_{b}$-SPIBB in their
benchmarks. Its most concise description is probably via its optimization
problem,

$\pi^{\prime}=\operatorname*{\arg\max}_{\pi}\sum_{a\in\mathcal{A}}Q^{\pi}_{\hat{M}}(s,a)\pi(a|s)\text{,
subject to:}$ (15a) $\pi^{\prime}(\cdot|s)\text{ being a probability density
over }\mathcal{A}\text{ and }$ (15b)
$\pi^{\prime}(a|s)\leq\pi_{b}(a|s),\;\forall(s,a)\in\mathcal{B}.$ (15c)

This problem only differs in its second constraint to the optimization problem
corresponding to $\Pi_{b}$-SPIBB. While $\Pi_{b}$-SPIBB prohibits the change
of the behavior policy for uncertain state-action pairs, $\Pi_{\leq b}$-SPIBB
just does not allow to add more weight to them but allows to reduce it.

##  4 Safe Policy Improvement with Soft Baseline Bootstrapping

Nadjahi et al. [14] continue the line of work on the SPIBB algorithms and
relax the hard bootstrapping to a softer version, where the baseline policy
can be changed at any state-action pair, but the amount of possible change is
limited by the uncertainty at this state-action pair. They claim that these
new algorithms, called Safe Policy Improvement with Soft Baseline
Bootstrapping (Soft-SPIBB), are also provably safe, a claim that is repeated
in Simao et al. [21] and Leurent [11]. Furthermore, they extend the
experiments from Laroche et al. [10] to include the Soft-SPIBB algorithms,
where the empirical advantage of these algorithms becomes clear. However,
after introducing the algorithms and the theory backing up their safety, we
will show in Section 4.4 that they are in fact not provably safe, which
motivates our adaptations in Section 5.

###  4.1 Preliminaries

To bound the performance of the new policy, it is necessary to bound the
estimate of the transition probabilities $\hat{P}$. By applying Hoelder’s
inequality, Nadjahi et al. [14] show that

$||P(\cdot|s,a)-\hat{P}(\cdot|s,a)||_{1}\leq e_{P}(s,a),$ (16)

holds with probability $1-\delta$, where

$e_{P}(s,a)=\sqrt{\frac{2}{N_{\mathcal{D}}(s,a)}\log\frac{2|\mathcal{S}||\mathcal{A}|2^{|\mathcal{A}|}}{\delta}}.$
(17)

The error function is used to quantify the uncertainty of each state-action
pair.

###### Definition 1

A policy $\pi$ is $(\pi_{b},\epsilon,e)$-_constrained_ w.r.t. a baseline
policy $\pi_{b}$, an error function $e$ and a hyper-parameter $\epsilon>0$, if

$\sum_{a\in\mathcal{A}}e(s,a)|\pi(a|s)-\pi_{b}(a|s)|\leq\epsilon$ (18)

holds for all states $s\in\mathcal{S}$.

Therefore, if a policy $\pi$ is $(\pi_{b},\epsilon,e)$-constrained, it means
that the $l^{1}$-distance between $\pi$ and $\pi^{\prime}$, weighted by some
error function $e$, is at most $\epsilon$.

###  4.2 Algorithms

The new class of algorithms Nadjahi et al. [14] introduce aims at solving the
following constrained optimization problem during the Policy Improvement step:

$\pi^{\prime}=\operatorname*{\arg\max}_{\pi}\sum_{a\in\mathcal{A}}Q^{\pi}_{\hat{M}}(s,a)\pi(a|s)\text{,
subject to:}$ (19a) $\pi^{\prime}(\cdot|s)\text{ being a probability density
over }\mathcal{A}\text{ and }$ (19b) $\pi^{(i+1)}\text{ being
}(\pi_{b},\epsilon,e)\text{-constrained}.$ (19c)

This computation leads to the optimal—w.r.t. the action-value function of the
previous policy—$(\pi_{b},\epsilon,e)$-constrained policy. The two algorithms
introduced in Nadjahi et al. [14], which numerically solve this optimization
problem, are Exact-Soft-SPIBB and Approx-Soft-SPIBB. The former solves the
linear formulation of the constrained problem by a linear program [3] and the
latter uses a budget calculation for the second constraint to compute an
approximate solution. In experiments, it is shown that both algorithms achieve
similar performance, but Exact-Soft-SPIBB takes considerably more time [14].

###  4.3 The Safety Guarantee

Nadjahi et al. [14] derive the theoretical safety of their algorithms from two
theorems. The first theorem, however, needs an additional property their
algorithms do not fulfill. For that reason we will move its discussion to
Section 5, where we will also introduce refined algorithms which fulfill said
property. To make up for this property, Nadjahi et al. [14] use Assumption 1
to prove Theorem 4.1.

###### Assumption 1

There exists a constant $\kappa<\frac{1}{\gamma}$ such that, for all state-
action pairs $(s,a)\in\mathcal{S}\times\mathcal{A}$, the following holds:

$\sum_{s^{\prime},a^{\prime}}e_{P}(s^{\prime},a^{\prime})\pi_{b}(a^{\prime}|s^{\prime})P^{*}(s^{\prime}|s,a)\leq\kappa
e_{P}(s,a)$ (20)

Interpreting $\pi_{b}(a^{\prime}|s^{\prime})P^{*}(s^{\prime}|s,a)$ as the
probability of observing the state-action pair $(s^{\prime},a^{\prime})$ after
observing $(s,a)$ we can rewrite Equation 20 to

$E_{P,\pi_{b}}[e_{P}(S_{t+1},A_{t+1})|S_{t}=s,A_{t}=a]\leq\kappa e_{P}(s,a),$
(21)

which shows that Assumption 1 assumes an upper bound on the uncertainty of the
next state-action pair dependent on the uncertainty of the current one.
Intuitively this makes sense, but we show in the next section that the bound
does not hold in general. However, using this assumption Nadjahi et al. [14]
prove Theorem 4.1 which omits the advantageous assumption of the new policy.

###### Theorem 4.1

Under Assumption 1, any $(\pi_{b},\epsilon,e_{P})$-constrained policy $\pi$
satisfies the following inequality in every state $s$ with probability at
least $1-\delta$:

$\displaystyle V^{\pi}_{M^{*}}(s)-V^{\pi_{b}}_{M^{*}}(s)\geq
V^{\pi}_{\hat{M}}(s)-V^{\pi_{b}}_{\hat{M}}(s)+$ $\displaystyle
2||d^{\pi}_{M}(\cdot|s)-d^{\pi_{b}}_{M}(\cdot|s)||_{1}V_{max}-\frac{1+\gamma}{(1-\gamma)^{2}(1-\kappa\gamma)}\epsilon
V_{max}$ (22)

Here,
$d^{\pi}_{M}(s^{\prime}|s)=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(S_{t}=s^{\prime}|S_{t}\sim
P\pi S_{t-1},S_{0}=s)$ denotes the expected discounted sum of visits to
$s^{\prime}$ when starting in $s$.

###  4.4 Shortcomings of the Theory

As explained above, the theoretical guarantees, Nadjahi et al. [14] claim for
the Soft-SPIBB algorithms, stem from Theorem 4.1. However, we now show that
Assumption 1 does not hold for any $0<\gamma<1$.

###### Theorem 4.2

Let the discount factor $0<\gamma<1$ be arbitrary. Then there exists an MDP
$M$ with transition probabilities $P$ such that for any behavior policy
$\pi_{b}$ and any data set $\mathcal{D}$, which contains every state-action
pair at least once, it holds that, for all $0<\delta<1$,

$\sum_{s^{\prime},a^{\prime}}e_{P}(s^{\prime},a^{\prime})\pi_{b}(a^{\prime}|s^{\prime})P(s^{\prime}|s,a)>\frac{1}{\gamma}e_{P}(s,a).$
(23)

This means that Assumption 1 can, independent of the discount factor, not be
true for all MDPs.

Figure 2: MDP with $n+1$ states, $n$ of them are final states and in the non-
final state, there is only $1$ action, leading to one of the others with equal
probability.[20]

###### Proof

Let $0<\gamma<1$ be arbitrary and $n\in\mathbb{N}$ be such that
$\sqrt{n}>\frac{1}{\gamma}$. Let $M$ be the MDP displayed in Figure 2. It has
$n+1$ states, from which $n$ states are terminal states, labeled $1$, $2$, …,
$n$. In the only non-terminal state $0$, there is only one action available
and choosing it results in any of the terminal states with probability
$\frac{1}{n}$. As there is only one action, one can omit the action in the
notation of $e_{P}$ and there is only one possible behavior policy. So,
Equation 23 can be reduced to

$\sum_{i=1}^{n}\frac{e_{P}(i)}{n}>\frac{e_{P}(0)}{\gamma}.$ (24)

Now, we show that

$\sum_{i=1}^{n}\frac{e_{P}(i)}{n}\geq\sqrt{n}e_{P}(0),$ (25)

which implies Equation 24 as $\sqrt{n}>\frac{1}{\gamma}$. Let $\mathcal{D}$
denote the data collected on this MDP such that every state has been visited
at least once. Thus, $N_{\mathcal{D}}(i)>0$—the number of visits to state
$i$—holds for every $i$. Equation 25 is equivalent to

$\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\sqrt{N_{\mathcal{D}}(i)}}\geq\frac{\sqrt{n}}{\sqrt{N}}$
(26)

where $N=N_{\mathcal{D}}(0)=\sum_{i=1}^{n}N_{\mathcal{D}}(i)$. Equation 26
follows by applying Jensen’s inequality once for the convex function
$x\mapsto\frac{1}{x}$, restricted to $x>0$, and once for the concave function
$x\mapsto\sqrt{x}$, also restricted to $x>0$:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\sqrt{N_{\mathcal{D}}(i)}}\geq\frac{1}{\frac{1}{n}\sum_{i=1}^{n}\sqrt{N_{\mathcal{D}}(i)}}\geq\frac{1}{\sqrt{\frac{1}{n}\sum_{i=1}^{n}N_{\mathcal{D}}(i)}}=\frac{1}{\sqrt{\frac{N}{n}}}=\frac{\sqrt{n}}{\sqrt{N}}.$

This concludes the proof.

The class of MDPs used in the proof and depicted in Figure 2 gives a good
impression what kind of constellations are critical for Assumption 1. An MDP
does not have to exhibit exactly the same structure to have similar effects,
it might already be enough if there is a state-action pair from which a lot of
different state-action pairs are exclusively accessible.

Although Assumption 1 is invalid in its generality shown at some specific
class of MDPs, it might still hold on simple MDPs which are not built in order
to disprove Assumption 1. One consideration here is that $n$ does not need to
be especially big as the proof only required $\sqrt{n}>\frac{1}{\gamma}$. So,
for any $\gamma>\frac{1}{\sqrt{2}}\approx 0.707$ it suffices to choose $n=2$.

Furthermore, we tested Assumption 1 empirically on the Random MDPs benchmark
considered in [14] where we found for no discount factor greater than 0.6 a
baseline policy and data set such that the assumption holds for all state-
action pairs.222https://github.com/Philipp238/Safe-Policy-Improvement-
Approaches-on-Discrete-Markov-Decision-
Processes/blob/master/auxiliary_tests/assumption_test.py Consequently, we
conclude that Assumption 1 is not reasonable and, thus, Theorem 4.1 cannot be
relied upon.

##  5 Advantageous Soft-SPIBB

In the last section we have shown that there is no safety guarantee for the
Soft-SPIBB algorithms. However, Nadjahi et al. [14] proved another theorem
which we present in its corrected form together with adapted algorithms to
which it is applicable.

###  5.1 Preliminaries

We follow Nadjahi et al. [14] and define the error function $e_{Q}$ as

$e_{Q}(s,a)=\sqrt{\frac{2}{N_{\mathcal{D}}(s,a)}\log\frac{2|\mathcal{S}||\mathcal{A}|}{\delta}},$
(27)

since that way we can bound the difference between the true action-value
function and its estimate. Contrary to them, we use a different estimate as
the bound again relies on Hoeffding’s inequality [8] which can only be applied
to a sum of random variables and, to the best of our knowledge, we do not know
how it can be applied to $Q^{\pi_{b}}_{\hat{M}}(s,a)$.

For our proof it is necessary to use the Monte-Carlo estimate for
$Q^{\pi_{b}}_{M}(s,a)$ from data $\mathcal{D}$

$\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)=\frac{1}{n}\sum_{i=1}^{n}G_{t_{i}}$ (28)

where $t_{1},...,t_{n}$ are times such that $(S_{t_{i}},A_{t_{i}})=(s,a)$, for
all $i=1,...,n$. As $E[G_{t_{i}}]=Q^{\pi_{b}}_{M}(s,a)$ it is possible to
apply the Hoeffding’s inequality for $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$,
similar to how it is done in Nadjahi et al. [14].

###### Lemma 1

For $e_{Q}$ as defined in Equation 27, it holds for an arbitrary MDP $M$ with
$G_{max}$ as an upper bound on the absolute value of the return in any state-
action pair of any policy and behavior policy $\pi_{b}$, that

$\mathbb{P}_{\mathcal{D}}\left(\forall(s,a)\in\mathcal{S}\times\mathcal{A}:|Q^{\pi_{b}}_{M}(s,a)-\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)|\leq
e_{Q}(s,a)G_{max}\right)\geq 1-\delta,$ (29)

if the $G_{t_{i}}$ used to estimate $\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)$ are
independent. Here, the subscript $\mathcal{D}$ of $\mathbb{P}$ emphasizes that
the dataset generated by $\pi_{b}$ is the random quantity.

###### Proof

First, note that Hoeffding’s inequality implies that

$\mathbb{P}(|\sum_{i=1}^{n}X_{i}-E[\sum_{i=1}^{n}X_{i}]|\geq t)\leq
2\exp(-2nt^{2}),$ (30)

for $X_{i}\in[0,1]$ independent. Fix the state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Then,

$\begin{gathered}\mathbb{P}_{\mathcal{D}}\left(\left|Q^{\pi_{b}}_{M}(s,a)-\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)\right|>e_{Q}(s,a)G_{max}\right)\\\
=\mathbb{P}_{\mathcal{D}}\left(\left|\frac{(Q^{\pi_{b}}_{M}(s,a)+G_{max})-(\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)+G_{max})}{2G_{max}}\right|>\sqrt{\frac{1}{2N_{\mathcal{D}}(s,a)}\log\frac{2|\mathcal{S}||\mathcal{A}|}{\delta}}\right)\\\
\leq
2\exp\left(-2N_{\mathcal{D}}(s,a)\frac{1}{2N_{\mathcal{D}}(s,a)}\log\frac{2|\mathcal{S}||\mathcal{A}|}{\delta}\right)=\frac{\delta}{|\mathcal{S}||\mathcal{A}|},\end{gathered}$
(31)

where it is possible to apply Hoeffding’s inequality in the second step since

$\frac{\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)+G_{max}}{2G_{max}}=\frac{1}{n}\sum_{i=1}^{n}\frac{G_{t_{i}}+G_{max}}{2G_{max}}$
(32)

is the empirical mean of independent variables which are bounded in $[0,1]$ as
$G_{t_{i}}$ are independent and bounded in $[-G_{max},G_{max}]$ and

$E[\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)]=E[G_{t_{i}}]=Q^{\pi_{b}}_{M}(s,a).$
(33)

Another change in this inequality compared to Nadjahi et al. [14] is, that we
get $G_{max}$ instead of $V_{max}$, since $G_{t}$ does in general not lie in
the interval $[-V_{max},V_{max}]$.

The first theorem from Nadjahi et al. [14] relies on the algorithms to produce
_advantageous_ policies. This property has to be slightly generalized to make
it applicable to the Monte Carlo estimate of the action value function.

###### Definition 2

A policy $\pi$ is $\pi_{b}$-_advantageous w.r.t. the function_
$Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, if

$\sum_{a}Q(s,a)\pi(a|s)\geq\sum_{a}Q(s,a)\pi_{b}(a|s)$ (34)

holds for all states $s\in\mathcal{S}$.

Interpreting $Q$ as an action-value function, Definition 2 yields that the
policy $\pi$ chooses higher-valued actions than policy $\pi^{\prime}$ for
every state.

###  5.2 Algorithms

In this subsection we introduce the adaptation Adv-Approx-Soft-SPIBB which
produces ($\pi_{b},e_{Q},\epsilon)$-constrained and $\pi_{b}$-advantageous
w.r.t. $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$ policies and is, thus, provably safe
by Theorem 5.1 in Section 4.3. Additionally, we present the heuristic
adaptation Lower-Approx-Soft-SPIBB. As both algorithms function similarly to
their predecessors by constraining the policy set, they also belong to the
category “Uncertainty as a restriction on the set of policies” in the taxonomy
in Figure 1.

####  5.2.1 Adv-Approx-Soft-SPIBB

The advantageous version of the Soft-SPIBB algorithms solves the following
problem in the Policy Improvement (PI) step:

$\pi^{\prime}=\operatorname*{\arg\max}_{\pi}\sum_{a\in\mathcal{A}}Q^{\pi}_{\hat{M}}(s,a)\pi(a|s)\text{,
subject to:}$ (35a) $\pi^{\prime}(\cdot|s)\text{ being a probability density
over }\mathcal{A},$ (35b) $\pi^{(i+1)}\text{ being
}(\pi_{b},\epsilon,e)\text{-constrained}\text{ and }$ (35c) $\pi^{(i+1)}\text{
being }\pi_{b}\text{-advantageous w.r.t. }\hat{Q}^{\pi_{b}}_{\mathcal{D}}.$
(35d)

The original Soft-SPIBB algorithms solve this optimization problem without the
constraint in Equation 35d as shown in Section 4.2. Adv-Approx-Soft-SPIBB
works exactly as its predecessor Approx-Soft-SPIBB except that it keeps an
additional budgeting variable ensuring that the new policy is
$\pi_{b}$-advantageous w.r.t. $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$. The
derivation of a successor algorithm of Exact-Soft-SPIBB is straightforward
since the constraint in Equation 35d is linear, however, we observed for
Exact-Soft-SPIBB and its successor numerical issues, so, we omit them in the
experiments in Section 6.

####  5.2.2 Lower-Approx-Soft-SPIBB

To introduce the heuristic adaptation of Approx-Soft-SPIBB we need a relaxed
version of the constrainedness property.

###### Definition 3

A policy $\pi$ is $(\pi_{b},\epsilon,e)$-_lower-constrained_ w.r.t. a baseline
policy $\pi_{b}$, an error function $e$, and a hyper-parameter $\epsilon$, if

$\sum_{a\in\mathcal{A}}e(s,a)\max\\{0,\pi(a|s)-\pi_{b}(a|s)\\}\leq\epsilon$
(36)

holds for all states $s\in\mathcal{S}$.

This definition does not punish a change in uncertain state-action pairs if
the probability of choosing it is decreased, which follows the same logic as
the empirically very successful adaptation $\Pi_{\leq b}$-SPIBB [10]. The
optimization problem solved by Lower-Approx-Soft-SPIBB is the following:

$\pi^{\prime}=\operatorname*{\arg\max}_{\pi}\sum_{a\in\mathcal{A}}Q^{\pi}_{\hat{M}}(s,a)\pi(a|s)\text{,
subject to:}$ (37a) $\pi^{\prime}(\cdot|s)\text{ being a probability density
over }\mathcal{A}\text{ and }$ (37b) $\pi^{(i+1)}\text{ being
}(\pi_{b},\epsilon,e)\text{-lower-constrained}.$ (37c)

Even though Lower-Approx-Soft-SPIBB is—just as its predecessor Approx-Soft-
SPIBB—not provably safe, the experiments in Section 6 show that it performs
empirically the best out of the whole SPIBB family.

###  5.3 Safety Guarantee

In this subsection, we prove Theorem 5.1 which states that algorithms that
produce $(\pi_{b},\epsilon,e_{Q})$-constrained policies which are
$\pi_{b}$-advantageous w.r.t. $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$—as Adv-Approx-
Soft-SPIBB does—are safe. Before that, it is necessary to introduce some
notation from the predecessor paper [10]. To enable the use of matrix
operations all the quantities introduced so far are denoted as vectors and
matrices in the following. The value functions become

$Q^{\pi}=(Q^{\pi}(1,1),...,Q^{\pi}(1,|\mathcal{A}|),Q^{\pi}(2,1),...,Q^{\pi}(|\mathcal{S}|,|\mathcal{A}|))\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
(38)

and

$V^{\pi}=(V^{\pi}(1),...,V^{\pi}(|\mathcal{S}|))\in\mathbb{R}^{|\mathcal{S}|}.$
(39)

Similarly, the reward vector is

$R=(R(1,1),...,R(1,|\mathcal{A}|),R(2,1),...,R(|\mathcal{S}|,|\mathcal{A}|))\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}.$
(40)

The policy is denoted by

$\pi=(\pi_{\cdot
1}\ldots\pi_{\cdot|\mathcal{S}|})\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|},$
(41)

with columns $\pi_{kj}=\pi(k|j)$ for $(j-1)|\mathcal{A}|+1\leq k\leq
j|\mathcal{A}|$ and $\pi_{kj}=0$ otherwise. Lastly, the transition
probabilities are

$P=\left(\begin{array}[]{ccccc}P\left(1\bigr{\rvert}1,1\right)&\cdots&P\left(1\bigr{\rvert}1,|\mathcal{A}|\right)&\cdots&P\left(1\bigr{\rvert}|\mathcal{S}|,|\mathcal{A}|\right)\\\
\vdots&&\vdots&&\vdots\\\
P\left(|\mathcal{S}|\bigr{\rvert}1,1\right)&\cdots&P\left(|\mathcal{S}|\bigr{\rvert}1,|\mathcal{A}|\right)&\cdots&P\left(|\mathcal{S}|\bigr{\rvert}|\mathcal{S}|,|\mathcal{A}|\right)\par\end{array}\right)\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}||\mathcal{A}|}.$
(42)

Note that we omit the current MDP $M$ in all these notations, as we always do,
if it is clear or not relevant which MDP is currently used. Using this
notation, we can present Proposition 1 without its proof from Nadjahi et al.
[14].

###### Proposition 1

Let $\pi_{1}$ and $\pi_{2}$ be two policies on an MDP $M$. Then

$V^{\pi_{1}}_{M}-V^{\pi_{2}}_{M}=Q^{\pi_{2}}_{M}(\pi_{1}-\pi_{2})d^{\pi_{1}}_{M}$
(43)

holds.

Proposition 1 yields a decomposition of the difference of the state value
function for two different policies on the same MDP which is utilized to prove
the corrected version of Theorem 1 from Nadjahi et al. [14].

###### Theorem 5.1

For any $(\pi_{b},\epsilon,e_{Q})$-constrained policy that is
$\pi_{b}$-advantageous w.r.t. $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$, which is
estimated with independent returns for each state-action pair, the following
inequality holds:

$\mathbb{P}_{\mathcal{D}}\left(\forall
s\in\mathcal{S}:V_{M^{*}}^{\pi}(s)-V_{M^{*}}^{\pi_{b}}(s)\geq-\frac{\epsilon
G_{max}}{1-\gamma}\right)\geq 1-\delta,$

where $M^{*}$ is the true MDP on which the data $\mathcal{D}$ gets sampled by
the baseline policy $\pi_{b}$, $0\leq\gamma<1$ is the discount factor, and
$\delta>0$ is the safety parameter for $e_{Q}$.

###### Proof

We start by applying Proposition 1:

$\begin{gathered}V^{\pi}_{M}-V^{\pi_{b}}_{M}=Q^{\pi_{b}}_{M}(\pi-\pi_{b})d^{\pi}_{M}=(Q^{\pi_{b}}_{M}-\hat{Q}^{\pi_{b}}_{\mathcal{D}}+\hat{Q}^{\pi_{b}}_{\mathcal{D}})(\pi-\pi_{b})d^{\pi}_{M}\\\
=(Q^{\pi_{b}}_{M}-\hat{Q}^{\pi_{b}}_{\mathcal{D}})(\pi-\pi_{b})d^{\pi}_{M}+\hat{Q}^{\pi_{b}}_{\mathcal{D}}(\pi-\pi_{b})d^{\pi}_{M}.\end{gathered}$
(44)

The goal of this proof is to lower bound these two summands. For the first
summand, notice that it is a row vector and, so, a bound on the $\ell^{1}$
norm gives a simultaneous bound for all states. Thus, applying a vector-matrix
version of Hoelder’s inequality, which is proven in Lemma 2 later on, yields

$\begin{gathered}||(Q^{\pi_{b}}_{M}-\hat{Q}^{\pi_{b}}_{\mathcal{D}})(\pi-\pi_{b})d^{\pi}_{M}||_{1}\leq||((Q^{\pi_{b}}_{M}-\hat{Q}^{\pi_{b}}_{\mathcal{D}})(\pi-\pi_{b}))^{T}||_{\infty}||d^{\pi}_{M}||_{1},\end{gathered}$
(45)

where all the norms refer to matrix norms. Using Lemma 1 and that $\pi$ is
$(\pi_{b},e_{Q},\epsilon)$-constrained yields that

$\begin{gathered}||\left((Q^{\pi_{b}}_{M}-\hat{Q}^{\pi_{b}}_{\mathcal{D}})(\pi-\pi_{b})\right)^{T}||_{\infty}\leq\max_{s}\sum_{a}|Q^{\pi_{b}}_{M}(s,a)-\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)||\pi(a|s)-\pi_{b}(a|s)|\\\
\leq\max_{s}\sum_{a}e_{Q}(s,a)G_{max}|\pi(a|s)-\pi_{b}(a|s)|\leq\epsilon
G_{max}\end{gathered}$ (46)

holds with probability $1-\delta$. The next step is to compute

$\begin{gathered}||d^{\pi}_{M}||_{1}=\max_{s}\sum_{s^{\prime}}\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(S_{t}=s^{\prime}|X_{t}\sim
P\pi S_{t},S_{0}=s)\\\
=\max_{s}\sum_{t=0}^{\infty}\gamma^{t}\sum_{s^{\prime}}\mathbb{P}(S_{t}=s^{\prime}|X_{t}\sim
P\pi
S_{t},S_{0}=s)=\max_{s}\sum_{t=0}^{\infty}\gamma^{t}=\frac{1}{1-\gamma}.\end{gathered}$
(47)

Thus, the first summand can be lower bounded by $-\frac{\epsilon
G_{max}}{1-\gamma}$ with probability $1-\delta$. To lower bound the second
summand, note that all entries of $d^{\pi}_{M}$ are non-negative, so Theorem
5.1 follows if $\hat{Q}^{\pi_{b}}_{\mathcal{D}}(\pi-\pi_{b})(s)\geq 0$ for
every state $s\in\mathcal{S}$. So, let $s\in\mathcal{S}$ be arbitrary. Then,

$\begin{gathered}\hat{Q}^{\pi_{b}}_{\mathcal{D}}(\pi-\pi_{b})(s)=\sum_{a}\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)(\pi(a|s)-\pi_{b}(a|s))\geq
0\end{gathered}$ (48)

holds, since $\pi$ is $\pi_{b}$-advantageous w.r.t.
$\hat{Q}^{\pi_{b}}_{\mathcal{D}}$.

As mentioned in the proof, it remains to show that the inequality in Equation
45 holds.

###### Lemma 2

Let $n\in\mathbb{N}$, $v\in\mathbb{R}^{n}$ and $A\in\mathbb{R}^{n\times n}$ be
arbitrary. Then,

$||v^{T}A||_{1}\leq||v||_{\infty}||A||_{1}$ (49)

holds, where all norms refer to matrix norms.

###### Proof

Denote the columns of $A$ by $a^{1},...,a^{n}$. Then,

$\begin{gathered}||v^{T}A||_{1}=||(v^{T}a^{1},...,v^{T}a^{n})||_{1}=\max_{i=1,...,n}\\{|v^{T}a^{i}|\\}\\\
\leq\max_{i=1,...,n}\\{||v||_{\infty}||a^{i}||_{1}\\}=||v||_{\infty}\max_{i=1,...,n}\\{||a^{i}||_{1}\\}=||v||_{\infty}||A||_{1}\end{gathered}$
(50)

where we used the definition of the $\ell^{1}$ norm for matrices as the
maximum absolute column sum in the second and the last step and Hoeffding’s
inequality in the third step.

One possibility to improve Theorem 5.1 is to increase the sharpness of the
error function. For this, note that for Theorem 5.1 it is sufficient that the
error function fulfills the inequality from Lemma 1. One disadvantage of using
Hoeffding’s inequality to define the error function $e_{Q}$ as in Equation 27
is that it only incorporates the number of observations to estimate the
uncertainty, while it neglects additional knowledge of the data, e.g., its
variance. It should be clear that less observations of a quantity are
necessary to estimate it with high confidence, if the quantity has a low
variance. This is incorporated in the bound derived by Maurer and Pontil [13].

###### Lemma 3

(Maurer and Pontil) Let $X_{1},...,X_{n}$ be i.i.d. variables with values in
$[0,1]$ and denote with $X$ the random vector $X=(X_{1},...,X_{n})$. Then,

$\mathbb{P}\left(\bar{X}-E[\bar{X}]\leq\sqrt{\frac{2\widehat{\operatorname{Var}}(X)\log\frac{2}{\delta}}{n}}+\frac{7\log\frac{2}{\delta}}{3(n-1)}\right)\geq
1-\delta$ (51)

for any $\delta>0$. Here,
$\widehat{\operatorname{Var}}(X)=\frac{1}{n(n-1)}\sum_{1\leq i<j\leq
n}(Z_{i}-Z_{j})^{2}$ denotes the sample variance.

Following Lemma 3 we define

$e_{Q}^{B}(s,a)=2\left(\sqrt{\frac{2\widehat{\operatorname{Var}}(\frac{G}{2G_{max}})\log(\frac{4|\mathcal{S}||\mathcal{A}|}{\delta})}{N_{\mathcal{D}}(s,a)}}+\frac{7\log(\frac{4|\mathcal{S}||\mathcal{A}|}{\delta})}{3(N_{\mathcal{D}}(s,a)-1)}\right)$
(52)

with $G=(G_{t_{1}},...,G_{t_{n}})$. With exactly the same proof as for Lemma 1
for $e_{Q}$, it is possible to show the same inequality for $e_{Q}^{B}$, if
one applies the empirical version of Bennett’s inequality instead of
Hoeffding’s inequality:

###### Lemma 4

For $e_{Q}^{B}$ as defined in Equation 52, it holds for an arbitrary MDP $M$
with $G_{max}$ as an upper bound on the absolute value of the return in any
state-action pair of any policy and behavior policy $\pi_{b}$, that

$\mathbb{P}_{\mathcal{D}}\left(\forall(s,a)\in\mathcal{S}\times\mathcal{A}:|Q^{\pi_{b}}_{M}(s,a)-\hat{Q}^{\pi_{b}}_{\mathcal{D}}(s,a)|\leq
e_{Q}^{B}(s,a)G_{max}\right)\geq 1-\delta,$ (53)

if the $G_{t_{i}}$ used to estimate $\hat{Q}^{\pi_{b}}_{\mathcal{D}}$ are
independent.

The advantage of this new error function is the improved asymptotic bound,
especially for low variance returns. There are also two disadvantages. The
first is that if only a few observations are available, the bound is worse
than the bound achieved by the Hoeffding’s bound. The second is that the value
$G_{max}$ is used in the definition of $e_{Q}^{B}$. However, the maximal
return is not necessarily known. There are various possible approaches to
solve this issue. Either by estimating it from the observations $G_{t}$, lower
bounding it by $\frac{1}{2}(\max_{t}G_{t}-\min_{t}G_{t})$ or approximating it
using $\frac{R_{max}}{1-\gamma}$. The first approach might be very accurate in
practice when enough data is available, the second approach might be less
powerful, however, Lemma 3 is certain to hold for any lower bound on $G_{max}$
and $\frac{R_{max}}{1-\gamma}$ might be a good a priori known approximation
for some MDPs and it would also work to substitute $G_{max}$ in this whole
theory by $\frac{R_{max}}{1-\gamma}$, which makes also Theorem 5.1 more
interpretable but less powerful.

In Section 7 we empirically investigate how the error function relying on the
Maurer and Pontil bound compare to the one relying on Hoeffding’s bound.

##  6 Experiments

We test the adapted Soft-SPIBB algorithms against Basic RL (classical Dynamic
Programming [22] on the MLE MDP $\hat{M}$), Approx-Soft-SPIBB [14], its
predecessors $\Pi_{b}$\- and $\Pi_{\leq b}$-SPIBB [10], DUIPI [18], RaMDP [16]
and R-MIN, the pessimistic adaptation of R-MAX [1].

Since the adaptation of DUIPI to avoid unknown state-action pairs, as
described in Section 3.3, proved in these experiments to be an important and
consistent improvement, we display only the results of this adaptation of
DUIPI in Section 6.2. We also checked if the error function relying on the
bound by Maurer and Pontil [13] improved the performance of the Soft-SPIBB
algorithms. However, it did not provide a significant improvement and, thus,
we also only show the results for the algorithms applying the error function
based on Hoeffding’s inequality.

###  6.1 Experimental Settings

We use two different benchmarks for our comparison. The first one is the
Random MDPs benchmark already used in Laroche et al. [10] and Nadjahi et al.
[14]. As the second benchmark we use the Wet Chicken benchmark [7] which
depicts a more realistic scenario.

We perform a grid-search to choose the optimal hyper-parameter for each
algorithm for both benchmarks. Our choices can be found in the table below.
The hyper-parameter selection is the main difference to the experiments we
conduct in Section 7 as the hyper-parameters here are solely optimized for
performance without considerations of the safety guarantees, while we choose
the hyper-parameter in Section 7 such that the bounds are meaningful.

Table 1: Chosen hyper-parameters for both benchmarks [20]. Algorithms |  Random MDPs | Wet Chicken
---|---|---
Basic RL | - | -
RaMDP | $\kappa=0.05$ | $\kappa=2$
R-MIN | $N_{\wedge}=3$ | $N_{\wedge}=3$
DUIPI | $\xi=0.1$ | $\xi=0.5$
$\Pi_{b}$-SPIBB | $N_{\wedge}=10$ | $N_{\wedge}=7$
$\Pi_{\leq b}$-SPIBB | $N_{\wedge}=10$ | $N_{\wedge}=7$
Approx-Soft-SPIBB | $\delta=1,\,\epsilon=2$ | $\delta=1,\,\epsilon=1$
Adv-Approx-Soft-SPIBB (ours) | $\delta=1,\,\epsilon=2$ | $\delta=1,\,\epsilon=1$
Lower-Approx-Soft-SPIBB (ours) | $\delta=1,\,\epsilon=1$ | $\delta=1,\,\epsilon=0.5$

In both experiments we conduct $10,000$ iterations for each algorithm. As we
are interested in Safe Policy Improvement, we follow Chow et al. [2], Laroche
et al. [10], and Nadjahi et al. [14] and consider besides the mean performance
also the 1%-CVaR (Critical Value at Risk) performance, which is the mean
performance over the worst 1% of the runs.

####  6.1.1 Random MDP Benchmark

First we consider the grid-world like Random MDPs benchmark introduced in
Nadjahi et al. [14] which generates a new MDP in each iteration. The generated
MDPs consist of 50 states, including an initial state (denoted by 0) and a
final state. In every non-terminal state there are four actions available and
choosing one leads to four possible next states. All transitions yield zero
reward except upon entering the terminal state, which gives a reward of 1. As
the discount factor is chosen as $\gamma=0.95$, maximizing the return is
equivalent to finding the shortest route to the terminal state.

The baseline policy on each MDP is computed such that its performance is
approximately $\rho_{\pi_{b}}=V_{M^{*}}^{\pi_{b}}(0)=\eta
V_{M^{*}}^{\pi_{*}}(0)+(1-\eta)V_{M^{*}}^{\pi_{u}}(0)$, where $0\leq\eta\leq
1$ is the baseline performance target ratio interpolating between the
performance of the optimal policy $\pi_{*}$ and the uniform policy $\pi_{u}$.
The generation of the baseline policy starts with a softmax on the optimal
action-value function and continues with adding random noise to it, until the
desired performance is achieved [14]. To counter the effects from
incorporating knowledge about the optimal policy, the MDP is altered after the
generation of the baseline policy by transforming one regular state to a
terminal one which also yields a reward of 1.

The performances are normalized to make them more comparable between different
runs by calculating
$\bar{\rho}_{\pi}=\frac{\rho_{\pi}-\rho_{\pi_{b}}}{\rho_{\pi_{*}}-\rho_{\pi_{b}}}$.
Thus, $\bar{\rho}_{\pi}<0$ means a worse performance than the baseline policy,
$\bar{\rho}_{\pi}>0$ means an improvement w.r.t. the baseline policy and
$\bar{\rho}_{\pi}=1$ means the optimal performance was reached.

####  6.1.2 Wet Chicken Benchmark

The second experiment uses the more realistic Wet Chicken benchmark [7]
because of its heterogeneous stochasticity. Figure 3 visualizes the setting of
the Wet Chicken benchmark. The basic idea behind it is that a person floats in
a small boat on a river. The river has a waterfall at one end and the goal of
the person is to stay as close to the waterfall as possible without falling
down. Thus, the closer the person gets to the waterfall the higher the reward
gets, but upon falling down they start again at the starting place, which is
as far away from the waterfall as possible. It is modeled as a non-episodic
MDP.

Figure 3: The setting of the Wet Chicken benchmark used for reinforcement
learning. The boat starts at $(x,y)=(0,0)$ and starts there again upon falling
down the waterfall at $x=5$. The arrows show the direction and strength of the
stream towards the waterfall. Additionally, turbulence is stronger for small
$y$. The goal for the boat is to stay as close as possible to the waterfall
without falling down [20].

The whole river has a length and width of 5, so, there are 25 states. The
starting point is $(x,y)=(0,0)$ and the waterfall is at $x=5$. The position of
the person at time $t$ is denoted by the pair $(x_{t},y_{t})$. The river
itself has a turbulence ($b_{t}=3.5-v_{t}$) which is stronger for small $y$
and a stream ($v_{t}=y_{t}\frac{3}{5}$) towards the waterfall which is
stronger for larger $y$. The effect of the turbulence is stochastic; so, let
$\tau_{t}\sim U(-1,1)$ be the parameter describing the stochasticity of the
turbulence at time $t$.

The person can choose from five actions listed below with $a_{x}$ and $a_{y}$
describing the influence of an action on $x_{t}$ and $y_{t}$, respectively:

  * •

Drift: The person does nothing, $(a_{x},a_{y})=(0,0)$.

  * •

Hold: The person paddles back with half their power $(a_{x},a_{y})=(-1,0)$.

  * •

Paddle back: The person wholeheartedly paddles back, $(a_{x},a_{y})=(-2,0)$.

  * •

Right: The person goes to the right parallel to the waterfall,
$(a_{x},a_{y})=(0,1)$.

  * •

Left: The person goes to the left parallel to the waterfall,
$(a_{x},a_{y})=(0,-1)$.

The new position of the person assuming no river constraints is then
calculated by

$(\hat{x},\hat{y})=({\rm round}(x_{t}+a_{x}+v_{t}+\tau_{t}b_{t}),{\rm
round}(x_{t}+a_{y})),$ (54)

where the $round$ function is the usual one, i.e., a number is getting rounded
down if the first decimal is 4 or less and rounded up otherwise. Incorporating
the boundaries of the river yields the new position as

$x_{t+1}=\begin{dcases}\hat{x},&\text{if }0\leq\hat{x}\leq 4\\\
0,&\text{otherwise}\end{dcases}\text{ and }y_{t+1}=\begin{dcases}0,&\text{if
}\hat{x}>4\\\ 4,&\text{if }\hat{y}>4\\\ 0,&\text{if }\hat{y}>0\\\
\hat{y},&\text{otherwise}\end{dcases}.$ (55)

As the aim of this experiment is to have a realistic setting for Batch RL, we
use a realistic behavior policy. Thus, we do not incorporate any knowledge
about the transition probabilities or the optimal policy as it has been done
for the Random MDPs benchmark. Instead we devise heuristically a policy,
considering the overall structure of the MDP.

Our behavior policy follows the idea that the most beneficial state might lie
in the middle of the river at $(x,y)=(2,2)$. This idea stems from two trade-
offs. The first trade-off is between low rewards for a small $x$ and a high
risk of falling down for a big $x$ and the second trade-off is between a high
turbulence and low velocity for a low $y$ and the opposite for big $y$. To be
able to ensure the boat stays at the same place turbulence and velocity should
both be limited.

This idea is enforced through the following procedure. If the boat is not in
the state $(2,2)$, the person tries to get there and if they are already
there, they use the action paddle back. Denote this policy with
$\pi_{b}^{\prime}$. We cannot use this exact policy, as it is deterministic,
i.e., in every state there is only one action which is chosen with probability
1. This means that for each state there is at most 1 action for which data is
available when observing this policy. This is countered by making
$\pi_{b}^{\prime}$ $\epsilon$-greedy, i.e., define the behavior policy
$\pi_{b}$ as the mixture

$\pi_{b}=(1-\epsilon)\pi_{b}^{\prime}+\epsilon\pi_{u}$ (56)

where $\pi_{u}$ is the uniform policy which chooses every action in every
state with the same probability. $\epsilon$ was chosen to be 0.1 in the
following experiments. By calculating the transition matrix of the Wet Chicken
benchmark, it is possible to determine the performances of our polices exactly
and compute the optimal policy. This helps to get a better grasp on the
policies’ performances: The baseline policy with $\epsilon=0.1$ has a
performance of 29.8, the uniform policy $\pi_{u}$ of 20.7 and the optimal
policy of 43.1.

###  6.2 Results

(a) Mean

(b) 1%-CVaR

Figure 4: Mean (a) and 1%-CVaR (b) normalized performance over 10,000 trials
on the Random MDPs benchmark for $\rho_{\pi_{b}}=0.9$. In the context of SPI
the focus lies on the 1%-CVaR. The mean performance is dominated by the
algorithms applying a penalty on the action-value function, while the
restricting algorithms are winning for few data points in the risk-sensitive
1%-CVaR measure and only lose to DUIPI in the long run. Among the SPIBB class,
Lower-Approx-Soft-SPIBB shows the best performance in both runs [20].

(a) Mean

(b) 1%-CVaR

Figure 5: Mean (a) and 1%-CVaR (b) performance over 10,000 trials on the Wet
Chicken benchmark for $\epsilon=0.1$ for the baseline policy. The mean
performance is dominated by RaMDP, while the restricting algorithms are
winning in the risk-sensitive 1%-CVaR measure. Among the SPIBB class, Lower-
Approx-Soft-SPIBB shows the best mean and 1%-CVaR performance [20].

The results with optimized hyper-parameters as shown in Table 1 can be seen in
Figure 4 and 5 for the Random MDPs and Wet Chicken benchmark, respectively.
The performances for both benchmarks are very similar, except for DUIPI which
apparently has strong problems to estimate the variance in the complex
environment of the Wet Chicken benchmark. In general, the algorithms
penalizing the action-value function dominate the mean performance, especially
when large amounts of data are available, but they lose against the class of
restricting algorithms when it comes to the 1%-CVaR performance, which is the
more interesting metric when talking about safety. The strongest performing
algorithm among the class of restricting algorithm with respect to both
metrics—thus, also the safest among both classes—and in both benchmarks is
Lower-Approx-Soft-SPIBB. It is followed by Approx-Soft-SPIBB which is slightly
better than its theoretical adaptation Adv-Approx-Soft-SPIBB. The worst
algorithms from this class are the original SPIBB algorithms: $\Pi_{b}$-SPIBB
(SPIBB) and $\Pi_{\leq b}$-SPIBB (Lower-SPIBB).

Interestingly, Basic RL is outperformed by various algorithms in the mean
performance, which might be surprising as the others are intended for safe RL
instead of an optimization of their mean performance. The reason for this
might be that considering the uncertainty of the action-value function is even
beneficial for the mean performance. Also, considering its 1%-CVaR
performance—not even visible in Figure 5(b) due to its inferior
performance—the safety advantage of the SPI algorithms becomes very clear.

These two experiments demonstrate that restricting the set of policies instead
of adjusting the action-value function can be very beneficial for the safety
aspect of RL, especially in complex environments and for a low number of
observations. On the contrary, from a pure mean performance point of view it
is favorable to rather adjust the action-value function.

##  7 Critical Discussion of the Safety Bounds

In this section we want to check the strength of the safety bounds in the
experiments. The only theoretically safe algorithms among those in the last
section are Adv-Approx-Soft-SPIBB, $\Pi_{b}$-SPIBB and DUIPI. However, DUIPI
only uses an approximation of the variance and additionally assumes that the
action-value function is normally distributed. This has to be kept in mind
when comparing the different bounds. To test these bounds we repeat the
experiments on the Wet Chicken benchmark and this time choose the hyper-
parameters such that the bound is a useful one.

##### Adv-Approx-Soft-SPIBB

For Adv-Approx-Soft-SPIBB the safety guarantee is Theorem 5.1 and, thus, we
set $\delta>0$ close to 0 and also $\epsilon>0$ small enough to make Equation
5.1 meaningful. All the parameters are known a priori so one can choose
$\epsilon$ and directly know the value of the bound. As we use $\gamma=0.95$,
all the returns are between 0 and 80 ($80=\frac{4}{1-\gamma}$) and, therefore,
$G_{max}=40$, as there is an MDP equivalent to the usual Wet Chicken benchmark
but with centered returns and $G_{max}$ only needs to be an upper bound on
these centered ones. We choose $\epsilon$ to be at most $0.01$, as this yields
a lower bound of $-8$ below the baseline policy’s performance.

As mentioned before, $G_{max}$ is known exactly in this setting, which enables
the use of the error function relying on the Maurer and Pontil bound for Adv-
Approx-Soft-SPIBB. In Section 5 we propose this new error function
specifically for its improved asymptotic tightness and consequently we will
test it out in this experiment as well.

#####  $\Pi_{b}$-SPIBB

In Section 3.5 we mentioned that $\Pi_{b}$-SPIBB produces policies which are
$\xi$-approximate ($1-\delta$)-safe policy improvements w.r.t. the behavior
policy $\pi_{b}$, where

$\xi=\frac{4V_{max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{S}||\mathcal{A}|2^{|\mathcal{S}|}}{\delta}}.$
(57)

So, one has to choose the hyper-parameter $N_{\wedge}$, which is the number of
visits a state-action pair needs for the behavior policy to be changed at this
state-action pair, such that this lower bound becomes meaningful. In the Wet
Chicken benchmark, $|\mathcal{S}|=25$, $|\mathcal{A}|=5$ and $V_{max}\approx
20$ (referring to an MDP with centered performances). We use $\gamma=0.95$ and
want $\delta\leq 0.05$. To choose $N_{\wedge}$, Equation 57 is transformed to

$N_{\wedge}=\frac{32V_{max}\log\left(\frac{2\mathcal{S}||\mathcal{A}|2^{|\mathcal{S}|}}{\delta}\right)}{\xi^{2}(1-\gamma)^{2}}.$
(58)

To gain again a lower bound of at least $-8$, one has to set $\xi=8$ and
inserting all the values into Equation 58 yields $N_{\wedge}=1,832,114$ for
$\delta=0.05$. For a smaller $\delta$ this is even bigger. It is obvious that
$\Pi_{b}$-SPIBB does not work for a $N_{\wedge}$ that high, as the output
policy would always be the behavior policy unless there are far more than
$10,000,000$ observations available, which seems unreasonable for such a small
MDP. For this reason, we exclude $\Pi_{b}$-SPIBB from this experiment.

##### DUIPI

Lastly, DUIPI’s safety stems from the calculation of the variance of the
action-value function by assuming a distribution on the action-value function
and then applying the bound through Equation 10. For example, for a lower
bound which applies to $99\%$ one has to choose $\xi>2.33$. Contrary to Adv-
Approx-Soft-SPIBB it is unknown in advance what the lower bound is, as this
depends on the variance which depends on the policy itself.

Table 2: Performance and bounds of the provably safe algorithms. Algorithms |  Adv-Approx- Soft-SPIBB (Hoeffding) |  Adv-Approx- Soft-SPIBB (Maurer and Pontil) | DUIPI
---|---|---|---
Length trajectory |  1%-CVaR performance |  Bound |  1%-CVaR performance |  Bound |  1%-CVaR performance |  Bound
5,000 | 29.6 | 21.5 | 29.6 | 21.5 | 29.7 | 25.2
10,000 | 29.7 | 21.5 | 29.7 | 21.5 | 29.7 | 26.5
50,000 | 30.1 | 21.5 | 30.3 | 21.5 | 29.7 | 28.2
100,000 | 30.4 | 21.5 | 30.9 | 21.5 | 30.1 | 29.5
500,000 | 31.4 | 21.5 | 33.7 | 21.5 | 37.7 | 37.2
1,000,000 | 32.1 | 21.5 | 35.4 | 21.5 | 38.0 | 37.6

Table 2 shows the algorithms with their respective 1%-CVaR performances over
10,000 runs and the safety bounds. The hyper parameters were chosen for each
of the algorithms such that the bound holds at least for 99% of the runs,
however, in these experiments they actually held all of the time, indicating
that the bounds might be too loose. The baseline policy is as described in the
previous section, however, it is 0.2-greedy this time and has a performance of
29.5.

These experiments show that for all algorithms a huge amount of data is
necessary to get a sharp bound and produce a good policy at the same time.
Adv-Approx-Soft-SPIBB applying the error function relying on Hoeffding’s
inequality performs arguably the worst. While still achieving the same
security, the performance of the computed policies is significantly higher by
using the error function relying on the Maurer and Pontil bound. DUIPI simply
reproduces the greedy version of the baseline policy until a trajectory length
of 50,000. As soon as 500,000 steps are in the data set, however, DUIPI
strongly outperforms its competitors and also yields meaningful lower bounds
on its performance. However, one has to keep in mind that DUIPI uses a first
order Taylor approximation for the uncertainty propagation, approximates the
full covariance matrix only by the diagonal and assumes a prior distribution
on the action-value function.

Adv-Approx-Soft-SPIBB is very sensitive to changes in $\epsilon$. E.g., for
$\epsilon=0.005$, which yields a safety bound of 25.5, Adv-Approx-Soft-SPIBB
using Hoeffding’s inequality achieves only a 1%-CVaR performance of 30.9 for a
trajectory length of 1,000,000 and of 33.2 if it uses the inequality of Maurer
and Pontil. Contrary to that, changes in $\delta$ have a weaker effect on its
performance, as setting $\delta=0.001$ results in a 1%-CVaR performance of
31.9 and 34.9 for Adv-Approx-Soft-SPIBB relying on the inequalities by
Hoeffding and by Maurer and Pontil, respectively. DUIPI only has one parameter
to control the likelihood of the bound being correct and choosing it such that
the bound holds with 99.9% (corresponding to a $\delta=0.001$), leaves the
1%-CVaR performance for a trajectory with 1,000,000 steps unchanged but
deteriorates the 1%-CVaR performance for smaller data sets, i.e., for less
than 500,000 observations the new policy will simply be the greedy baseline
policy and for 500,000 the 1%-CVaR performance becomes 35.4.

##  8 Conclusion

In this paper, we reviewed and classified multiple SPI algorithms. We showed
that the algorithms in Nadjahi et al. [14] are not provably safe and have
proposed a new version that is provably safe. Adapting their ideas, we also
derived a heuristic algorithm which shows, among the entire SPIBB class on two
different benchmarks, both the best mean performance and the best $1\%$-CVaR
performance, which is important for safety-critical applications. Furthermore,
it proves to be competitive in the mean performance against other state of the
art uncertainty incorporating algorithms and especially to outperform them in
the $1\%$-CVaR performance. Additionally, it has been shown that the
theoretically supported Adv-Approx-Soft-SPIBB performs almost as well as its
predecessor Approx-Soft-SPIBB, only falling slightly behind in the mean
performance.

The experiments also demonstrate different properties of the two classes of
SPI algorithms in Figure 1: algorithms penalizing the action-value functions
tend to perform better in the mean, but lack in the 1%-CVaR, especially if the
available data is scarce.

In our experiments in Section 7, we demonstrate that the safety guarantees
only become helpful when huge amounts of data are available, which restricts
their use cases for now. However, we also show that there are still possible
improvements, for example, relying on tighter error functions. To explore this
idea further or to look for improvements of the bound in Theorem 5.1, as
already started in Scholl [19], would be important next steps to make SPI more
applicable in practice.

Perhaps the most relevant direction of future work is to apply this framework
to continuous MDPs, which has so far been explored by Nadjahi et al. [14] and
Scholl [19] without theoretical safety guarantees. Apart from the theory, we
hope that our observations of the two classes of SPI algorithms can contribute
to the choice of algorithms for the continuous case.

#### Acknowledgements

FD was partly funded by Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation), project 468830823. PS, CO and SU were partly funded by German
Federal Ministry of Education and Research, project 01IS18049A (ALICE III).

## References

  * [1] Brafman, R.I., Tennenholtz, M.: R-MAX - a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research 3 (Mar 2003)
  * [2] Chow, Y., Tamar, A., Mannor, S., Pavone, M.: Risk-sensitive and robust decision-making: a CVaR optimization approach. In: Proceedings of the 28th International Conference on Neural Information Processing Systems (2015)
  * [3] Dantzig, G.B.: Linear Programming and Extensions. RAND Corporation, Santa Monica, CA (1963)
  * [4] Fujimoto, S., Meger, D., Precup, D.: Off-policy deep reinforcement learning without exploration. In: Proc. of the 36th International Conference on Machine Learning (2019)
  * [5] García, J., Fernandez, F.: A Comprehensive Survey on Safe Reinforcement Learning. Journal of Machine Learning Research. 16 (2015)
  * [6] Hans, A., Duell, S., Udluft, S.: Agent self-assessment: Determining policy quality without execution. In: IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (2011)
  * [7] Hans, A., Udluft, S.: Efficient Uncertainty Propagation for Reinforcement Learning with Limited Data. In: Artificial Neural Networks – ICANN, vol. 5768 (2009)
  * [8] Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301), 13–30 (1963)
  * [9] Lange, S., Gabel, T., Riedmiller, M.: Batch Reinforcement Learning. In: Reinforcement Learning: State-of-the-Art. Adaptation, Learning, and Optimization, Springer, Berlin, Heidelberg (2012)
  * [10] Laroche, R., Trichelair, P., Tachet des Combes, R.: Safe policy improvement with baseline bootstrapping. In: Proc. of the 36th International Conference on Machine Learning (2019)
  * [11] Leurent, E.: Safe and Efficient Reinforcement Learning for Behavioural Planning in Autonomous Driving. Theses, Université de Lille (Oct 2020)
  * [12] Levine, S., Kumar, A., Tucker, G., Fu, J.: Offline reinforcement learning: Tutorial, review, and perspectives on open problems. CoRR abs/2005.01643 (2020)
  * [13] Maurer, A., Pontil, M.: Empirical Bernstein bounds and sample-variance penalization. In: COLT (2009)
  * [14] Nadjahi, K., Laroche, R., Tachet des Combes, R.: Safe policy improvement with soft baseline bootstrapping. In: Proc. of the 2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (2019)
  * [15] Nilim, A., El Ghaoui, L.: Robustness in Markov decision problems with uncertain transition matrices. In: Proc. of the 16th International Conference on Neural Information Processing Systems (2003)
  * [16] Petrik, M., Ghavamzadeh, M., Chow, Y.: Safe policy improvement by minimizing robust baseline regret. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS’16, Curran Associates Inc., Red Hook, NY, USA (2016)
  * [17] Schaefer, A.M., Schneegass, D., Sterzing, V., Udluft, S.: A neural reinforcement learning approach to gas turbine control. In: International Joint Conference on Neural Networks (Aug 2007)
  * [18] Schneegass, D., Hans, A., Udluft, S.: Uncertainty in Reinforcement Learning \- Awareness, Quantisation, and Control. In: Robot Learning. Sciyo (Aug 2010)
  * [19] Scholl, P.: Evaluation of Safe Policy Improvement with Soft Baseline Bootstrapping. Master’s thesis, Technical University of Munich (Apr 2021)
  * [20] Scholl, P., Dietrich, F., Otte, C., Udluft, S.: Safe policy improvement approaches on discrete Markov decision processes. In: Proceedings of the 14th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART. pp. 142–151. INSTICC, SciTePress (2022). https://doi.org/10.5220/0010786600003116
  * [21] Simão, T.D., Laroche, R., Tachet des Combes, R.: Safe Policy Improvement with an Estimated Baseline Policy. In: Proc. of the 19th International Conference on Autonomous Agents and MultiAgent Systems (2020)
  * [22] Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction. MIT press (2018)
  * [23] Thomas, P.S.: Safe Reinforcement Learning. Doctoral dissertations., University of Massachusetts (2015)
  * [24] Wang, R., Foster, D., Kakade, S.M.: What are the statistical limits of offline RL with linear function approximation? In: International Conference on Learning Representations (2021)