# Safe Policy Improvement for POMDPs via Finite-State Controllers

Thiago D. Simão, Marnix Suilen,11footnotemark: 1 Nils Jansen Equal
contribution.

###### Abstract

We study _safe policy improvement_ (SPI) for partially observable Markov
decision processes (POMDPs). SPI is an offline reinforcement learning (RL)
problem that assumes access to (1) historical data about an environment, and
(2) the so-called _behavior policy_ that previously generated this data by
interacting with the environment. SPI methods neither require access to a
model nor the environment itself, and aim to reliably improve the behavior
policy in an offline manner. Existing methods make the strong assumption that
the environment is fully observable. In our novel approach to the SPI problem
for POMDPs, we assume that a finite-state controller (FSC) represents the
behavior policy and that finite memory is sufficient to derive optimal
policies. This assumption allows us to map the POMDP to a finite-state fully
observable MDP, the _history MDP_. We estimate this MDP by combining the
historical data and the memory of the FSC, and compute an improved policy
using an off-the-shelf SPI algorithm. The underlying SPI method constrains the
policy-space according to the available data, such that the newly computed
policy only differs from the behavior policy when sufficient data was
available. We show that this new policy, converted into a new FSC for the
(unknown) POMDP, outperforms the behavior policy with high probability.
Experimental results on several well-established benchmarks show the
applicability of the approach, even in cases where finite memory is not
sufficient.

##  1 Introduction

Reinforcement learning (RL) is a standard approach to solve sequential
decision-making problems when the environment dynamics are unknown (Sutton and
Barto 1998). Typically, an RL agent interacts with the environment and
optimizes its behavior according to environment’s feedback. However, in
offline RL (Levine et al. 2020), the RL agent receives a fixed dataset of past
interactions between a behavior policy and the environment and derives a new
policy with no direct interaction with the environment. One of the challenges
in offline RL is to ensure that the new policy outperforms the behavior policy
(Cheng et al. 2022). This problem is called _safe policy improvement_ (SPI;
Thomas, Theocharous, and Ghavamzadeh 2015b). Most of the approaches to SPI
assume fully observable environments, see for instance (Petrik, Ghavamzadeh,
and Chow 2016; Laroche, Trichelair, and des Combes 2019).

$z,r$
---
learning
---
deployment
---
$\pi_{\beta}$
---
$a$
---
data collection
---
$[(z_{i},a_{i},r_{i},z_{i}^{\prime})]$
---
buffer
---
$z,r$
---
$a$
---
$\pi_{I}$
---
$\pi_{I}$
---
$\pi_{I}$
---
$\mathcal{D}$
---

Figure 1: Illustration of the offline reinforcement learning problem in
partially observable environments (adapted from Levine et al. 2020). The
dashed arrow indicates the setting where the behavior policy is available
during learning.

The restriction to full observability poses a serious limitation on the
applicability of SPI, as most real-world problems are _partially observable_ ,
due to, for instance, noisy sensors (Kochenderfer 2015). _Partially observable
Markov decision processes_ (POMDPs) are the standard model for decision-making
problems under partial observability (Kaelbling, Littman, and Cassandra 1998).
So far, SPI for POMDPs was only studied for memoryless policies (Thomas,
Theocharous, and Ghavamzadeh 2015a; Yeager et al. 2022). However, POMDP
policies often require a notion of memory. In general, optimal policies for
POMDPs with infinite horizons require infinite memory, rendering this problem
undecidable (Madani, Hanks, and Condon 2003). Nevertheless, finite memory can
make good approximations of the optimal policy (Bonet 2002) and are often used
in practice for being more explainable (Dujardin, Dietterich, and Chades
2017). Policies with finite memory may take the form of finite-state
controllers (FSCs; Meuleau et al. 1999a).

#### Our approach.

We contribute a novel SPI approach for POMDPs. First, to account for the
inherent memory requirement in partially observable domains, we present the
behavior policy as an FSC. To create a tractable method, we assume that there
exists a finite-memory policy for the POMDP that is optimal, also known as the
finite-history-window approach (Kaelbling, Littman, and Moore 1996, Section
7.3). This assumption allows us to cast the POMDP as an equivalent, fully
observable, _history MDP_ that is finite, instead of the standard infinite-
history MDP (Silver and Veness 2010). We are then able to reliably estimate
the transition and reward models of this finite-history MDP from the available
data. We employ a specific SPI method for MDPs, called safe policy improvement
with baseline bootstrapping (SPIBB; Laroche, Trichelair, and des Combes 2019).
In particular, we compute an improved policy that outperforms the behavior
policy up to an _admissible performance loss_ with high probability. In
comparison to the approach for mere MDPs (Laroche, Trichelair, and des Combes
2019), we derive an improved bound on this admissible performance loss by
exploiting the specific structure of the history MDP. The general flow of our
approach is illustrated in Figure 1.

#### Real-world applications.

This setting captures multiple real-world applications, such as predictive
maintenance, conservation of endangered species, and management of invasive
species. We may, for instance, have data from the degradation process of a
certain asset, which includes logs of inspections and maintenance that were
performed according to a fixed schedule (represented, for instance, as a
finite-state controller). Once we acquire a new asset, we can formalize the
optimization problem with offline RL to compute a new schedule, using the
original schedule as a behavior policy.

We demonstrate the applicability of our method on three standard POMDP
problems. The evaluation confirms the theoretical findings of our SPIBB
approach, in comparison to standard offline RL. We highlight results for
varying sizes of memory, and show that we can achieve reliable performance
improvement even for problems where finite memory is not sufficient in
general.

##  2 Background

For a countable set $X$ we write $|X|$ for the number of elements in $X$, and
$\Delta(X)$ for the set of probability distributions over $X$ with finite
support. Given two probability distributions $P,Q\in\Delta(X)$, the
_L1-distance_ between $P$ and $Q$ is

$\|P-Q\|_{1}=\sum_{x\in X}|P(x)-Q(x)|.$

The _L1-error_ of an estimated probability distribution $\tilde{P}$ is given
by the L1-distance between $\tilde{P}$ and the true distribution $P$:
$\|\tilde{P}-P\|_{1}$. Finally, we write $\mathbb{I}(x=y)$ for the indicator
function returning $1$ when $x=y$ and $0$ otherwise, and $[l:m]$ for the set
of natural numbers $\\{l,\dots,m\\}\subset\mathbb{N}$.

###  2.1 MDPs, POMDPs, and FSCs

######  Definition 1 (POMDP).

A _partially observable Markov decision process_ (POMDP) is a tuple
$\mathcal{M}=\langle S,A,T,R,\gamma,Z,O\rangle$, where $S$, $A$ and $Z$ are
finite sets of states, actions, and observations, $T\colon S\times
A\to\Delta(S)$ is the transition function, $R\colon S\times
A\to[R_{\min},R_{\max}]\subset\mathbb{R}$ is the reward function with known
bounds, $\gamma\in[0,1)\subset\mathbb{R}$ is the discount factor, and $O\colon
S\times A\to\Delta(Z)$ is the observation function.

As a special case we have the (fully observable) Markov decision process (MDP;
Puterman 1994), where $Z=S$ and $O(z|s,a)=\mathbb{I}(z=s)$, so it can be
defined as a POMDP without observations: $M=\langle S,A,T,R,\gamma\rangle$.

A _history_ is a sequence of observations and actions: $h\in(Z\times
A)^{*}\times Z$. We denote the set of all histories by $\mathcal{H}$, and
$\mathcal{H}_{k}$ denotes all histories of maximal length $k$, where the
length $|h|$ is the number of observations in the history $h$.

A _belief_ $b\in\Delta(S)$ is a distribution over the states of a POMDP.
Beliefs are _sufficient statistics_ for histories in POMDPs (Åström 1965;
Smallwood and Sondik 1973). That is, they provide just as much information as
the histories themselves. A belief $b$ can be updated into a new belief
$b^{\prime}$ upon taking an action $a$ and receiving an observation $z$ by
performing a Bayesian _belief update_ (Kaelbling, Littman, and Cassandra
1998). The belief $b^{\prime}$ of being in state $s$ given some history
$h^{\prime}$, denoted $b(s\mid h^{\prime})$, can be recursively computed by
repeated applications of the belief update on actions $a$ and observations $z$
in the history $h^{\prime}=haz$:

$b^{\prime}(s^{\prime}\mid haz)=b^{\prime}(s^{\prime}\mid b(\cdot\mid
h),a,z).$

until the history $h$ is empty, denoted $\emptyset$, and where
$b(\cdot\mid\emptyset)$ is the initial belief.

A POMDP is equivalent to an infinite-state fully observable MDP called the
_history MDP_ (Silver and Veness 2010).

######  Definition 2 (History MDP).

The fully observable _history MDP_ of a POMDP is
$\langle\mathcal{H},A,T_{\mathcal{H}},R_{\mathcal{H}},\gamma\rangle$, where
$\mathcal{H}$ is the set of all histories, $A$ and $\gamma$ are the actions
and discount factor from the POMDP, and
$T_{\mathcal{H}}\colon\mathcal{H}\times A\to\Delta(\mathcal{H})$ and
$R_{\mathcal{H}}\colon\mathcal{H}\times A\to\mathbb{R}$ are the transition and
reward functions:

$\displaystyle T_{\mathcal{H}}(haz\mid h,a)=\sum_{s\in S}b(s\mid
h)\sum_{s^{\prime}\in S}T(s^{\prime}\mid s,a)O(z\mid s^{\prime},a),$
$\displaystyle R_{\mathcal{H}}(h,a)=\sum_{s\in S}b(s\mid h)R(s,a).$

Since belief states are sufficient statistics for histories, the so-called
_belief MDP_ of a POMDP serves as a common alternative for the history MDP, we
refer to to Kaelbling, Littman, and Cassandra (1998) for more details.

A _policy_ for a POMDP is a function $\pi\colon\mathcal{H}\to\Delta(A)$,
mapping histories to distributions over actions. The set of all policies is
$\Pi$. The goal is to compute a policy that maximizes the expected discounted
reward in the infinite horizon:

$\max_{\pi\in\Pi}\mathbb{E}\left[\sum_{t=1}^{\infty}\gamma^{t}r_{t}\right],$

where $r_{t}$ is the reward the agent receives at time step $t$ when following
policy $\pi$. In general, a policy that maximizes the expected discounted
reward requires infinite memory, that is, it needs to account for all possible
histories. As such, computing optimal policies in POMDPs is undecidable in
general (Madani, Hanks, and Condon 2003).

We may instead use policies that only use a finite amount of memory. In
general, such policies are not optimal, that is, they do not maximize the
expected discounted reward, yet they are computationally more tractable. A
_finite-memory_ policy maps finite histories to actions,
$\pi\colon\mathcal{H}_{k}\to\Delta(A)$, and can be represented by a finite-
state controller of size $\kappa=(|Z|+1)^{k}$ (Meuleau et al. 1999a; Junges et
al. 2018), as we need to account for all possible combinations of observations
of size $k$, with a possible empty observation.

######  Definition 3 (Finite-state controller).

A _finite-state controller_ (FSC) is a tuple
$\langle\mathcal{N},n^{0},\psi,\eta\rangle$ where $\mathcal{N}$ is a finite
set of _memory nodes_ , $n^{0}\in\mathcal{N}$ is an _initial node_ ,
$\psi\colon\mathcal{N}\times Z\to\Delta(A)$ is an _action mapping_ , and
$\eta\colon\mathcal{N}\times Z\times A\to\mathcal{N}$ is a _memory update
function_. A $\kappa$-FSC is an FSC with $|\mathcal{N}|=\kappa$.

In any time step $t$, given the current memory node $n_{t}$ and observation
$z_{t}$, the action $a_{t}$ is randomly drawn from the distribution
$\psi(\cdot\mid n_{t},z_{t})$, and the memory node is updated to
$n_{t+1}=\eta(n_{t},z_{t},a_{t})$. A policy represented by an FSC can get
arbitrarily close to the optimal policy as $\kappa$ grows (Bonet 2002).
Computing finite-state controllers that aim to maximize the expected
(discounted) reward can be done in several ways, among those gradient descent
(Meuleau et al. 1999b) and convex optimization (Amato, Bernstein, and
Zilberstein 2010; Junges et al. 2018; Cubuktepe et al. 2021).

We denote the set of finite-memory policies of size $k$ by $\Pi_{k}$, and the
set of finite-memory policies of size $k$ represented by FSCs with some fixed
memory update $\eta$ by $\Pi_{k}^{\eta}$. Furthermore, FSCs of size $k$ can be
represented by FSCs with more memory. These sets are related by the following
inclusions, where $k^{\prime}>k$:
$\Pi_{k}^{\eta}\subset\Pi_{k}\subset\Pi_{k^{\prime}}\subset\Pi.$

Finally, we define the state-based and state-action-based value functions on
an (PO)MDP $M$ with policy $\pi$ as $V_{\pi}^{M}(s)$ and $Q_{\pi}^{M}(s,a)$
respectively. Whenever $M$ or $\pi$ are clear from the context we will omit
them. The _performance_ of a policy $\pi$ in $M$ is denoted by $\rho(\pi,M)$
and is defined as the expected value in some initial state $s_{0}$, that is,
$\rho(\pi,M)=V_{\pi}^{M}(s_{0})$. Furthermore, we write $V_{\max}$ for a known
upper bound on the absolute value of the performance:
$V_{\max}\leq\nicefrac{{R_{\max}}}{{1-\gamma}}$.

###  2.2 Safe Policy Improvement on MDPs

Here, we review safe policy improvement (SPI) for MDPs. A _dataset_ is a
sequence $\mathcal{D}$ of trajectories collected under a _behavior policy_
$\pi_{\beta}$ in an MDP $M^{*}$. For MDPs, the datasets we consider for SPI
are of the form $\mathcal{D}=\langle s_{t},a_{t},r_{t}\rangle_{t\in[1:m]}$,
and we write $\\#_{\mathcal{D}}(x)$ for the number of times $x$ occurs in
$\mathcal{D}$. The goal of SPI is to compute a new policy $\pi_{I}$ based on
$\mathcal{D}$ that outperforms $\pi_{\beta}$ with an allowed performance loss
$\zeta\in\mathbb{R}$ with high probability $1-\delta$.

SPI operates on a set of _admissible MDPs_ $\Xi$, that is, MDPs
$M=(S,A,T,R,\gamma)$ which are ‘close’ to an MDP
$\tilde{M}=(S,A,\tilde{T},\tilde{R},\gamma)$ estimated from a dataset
$\mathcal{D}$ by maximum likelihood estimation (MLE).

######  Definition 4 (MLE-MDP).

The MLE-MDP of an unknown true MDP $M^{*}=(S,A,T,R,\gamma)$ and a dataset
$\mathcal{D}$ is a tuple $\tilde{M}=(S,A,\tilde{T},\tilde{R},\gamma)$ with
transition and reward functions $\tilde{T}$ and $\tilde{R}$ derived from
$\mathcal{D}$ via maximum likelihood estimation:

$\tilde{T}(s^{\prime}\mid
s,a)=\frac{\\#_{\mathcal{D}}(s,a,s^{\prime})}{\\#_{\mathcal{D}}(s,a)},\text{
and }\tilde{R}(s,a)=\frac{R_{\text{total}}(s,a)}{\\#_{\mathcal{D}}(s,a)},$

where $R_{\text{total}}(s,a)$ is the sum of all rewards in $(s,a)$:
$R_{\text{total}}(s,a)=\sum_{(s_{t},a_{t},r_{t})\in\mathcal{D}}\mathbb{I}(s_{t}=s\wedge
a_{t}=a)\cdot r_{t}$.

For an MLE-MDP $\tilde{M}$ and error function $e\colon S\times
A\to\mathbb{R}$, we define the set of admissible MDPs $\Xi_{e}^{\tilde{M}}$
with a transition function $T$ that has $L_{1}$ distance to the estimated
transition function $\tilde{T}$ bounded by the error function $e$:

$\displaystyle\Xi_{e}^{\tilde{M}}=\\{M\mid\forall(s,a).\|T(\cdot\mid
s,a)-\tilde{T}(\cdot\mid s,a)\|_{1}\leq e(s,a)\\}.$

The general idea behind SPI methods is to define this error function $e$ such
that $\Xi_{e}^{\tilde{M}}$ includes the true MDP $M^{*}$ with high probability
$1-\delta$ (Petrik, Ghavamzadeh, and Chow 2016, Proposition $9$). Then one can
compute a new policy which is an improvement for all MDPs within
$\Xi_{e}^{\tilde{M}}$. An alternative is to simply solve the MLE-MDP, but this
could lead to arbitrarily poor policies when the amount of data is
insufficient. If, however, the amount of data is sufficient for all state-
action pairs, then we can guarantee with high probability that the improved
policy computed on the MLE-MDP has a higher performance. Specifically, as
pointed by Laroche, Trichelair, and des Combes (2019), the amount of data is
sufficient when for all state-action pairs

$\\#_{\mathcal{D}}(s,a)\geq\frac{8V_{\max}^{2}}{\zeta^{2}(1-\gamma)^{2}}\log\frac{2|S||A|2^{|S|}}{\delta}.$
(1)

Then with probability $1-\delta$ an optimal policy $\pi_{I}$ for $\tilde{M}$
is $\zeta$-approximately safe with respect to the true MDP $M^{*}$ for some
_admissible performance loss_ $\zeta\in\mathbb{R}$. That is,

$\rho(\pi_{I},M^{*})\geq\rho(\pi^{*},M^{*})-\zeta\geq\rho(\pi_{\beta},M^{*})-\zeta,$

where $\pi^{*}$ is an optimal policy in the true MDP $M^{*}$. Intuitively this
ensures that the estimated transition function is close enough to the true MDP
to guarantee that the policy computed in the MLE-MDP approximately outperforms
the behavior policy in the underlying MDP.

###  2.3 SPI with Baseline Bootstrapping on MDPs

The bound in Equation (1) needs to hold for every state-action pair, which
limits the practical use of optimizing the MLE-MDP. The _SPI with baseline
bootstrapping_ (SPIBB; Laroche, Trichelair, and des Combes 2019) algorithm
overcomes this limitation, allowing the constraint in (1) to be violated on
some state-action pairs. These state-action pairs are collected in
$\mathcal{U}$, the set of _unknown_ state-action pairs with counts smaller
than a given hyperparameter $N_{\wedge}$:

$\mathcal{U}=\\{(s,a)\in S\times A\mid\\#_{\mathcal{D}}(s,a)\leq
N_{\wedge}\\}.$

SPIBB computes an improved policy $\pi_{I}$ on $\tilde{M}$ as above, except
that $\pi_{I}$ is constrained to follow $\pi_{\beta}$ for unknown state-action
pairs: $\forall(s,a)\in\mathcal{U}.\,\pi_{I}(a\mid s)=\pi_{\beta}(a\mid s)$.
Then, $\pi_{I}$ is a $\zeta$-approximately safe improvement of $\pi_{\beta}$
with high probability $1-\delta$, where $\zeta$ is computed via (Theorem 2;
Laroche, Trichelair, and des Combes 2019):

$\begin{split}\zeta=\frac{4V_{\max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|S||A|2^{|S|}}{\delta}}-\rho(\pi_{I},\tilde{M})+\rho(\pi_{\beta},\tilde{M}).\end{split}$
(2)

##  3 SPIBB for POMDPs

Now we detail our approach to apply SPIBB to POMDPs.

#### Formal problem statement.

Given a POMDP $\mathcal{M}=\langle S,A,T,R,\gamma,Z,O\rangle$ of which the
transition and observation functions are unknown, some initial belief
$b\in\Delta(S)$, and a finite-memory behavior policy represented as a
$\kappa$-FSC $\pi_{\beta}=(\mathcal{N},n^{0},\psi,\eta)$, the goal is to apply
SPIBB to construct a new $\kappa$-FSC
$\pi_{I}=(\mathcal{N},n^{0},\psi^{\prime},\eta)$ with the same nodes and
memory structure $\eta$, _i.e._ $\pi_{\beta},\pi_{I}\in\Pi_{k}^{\eta}$, such
that with high probability $1-\delta$, $\pi_{I}$ is a $\zeta$-approximately
safe improvement over $\pi_{\beta}$ with respect to $\mathcal{M}$. That is,
with a probability of at least $1-\delta$ we have

$\rho(\pi_{I},\mathcal{M})\geq\rho(\pi_{\beta},\mathcal{M})-\zeta.$

###  3.1 From POMDP to Finite-History MDP

While a POMDP can be mapped to a fully observable history MDP (Definition 2),
this MDP has infinitely many states, making a direct application of SPI(BB)
methods infeasible. To mitigate this issue, we make an assumption on the
structure of the history MDP (and inherently on the POMDP) that implies that
the history MDP is equivalent to a smaller, finite, MDP. We formalize this
assumption via stochastic bisimulation (Givan, Dean, and Greig 2003).
Intuitively, this bisimulation is an equivalence relation that relates
(history) states that _behave_ similarly according to reward signals.

######  Definition 5 (Bisimilarity of history states).

A stochastic bisimulation relation $E\subseteq\mathcal{H}\times\mathcal{H}$ on
history states $h_{1},h_{2}\in\mathcal{H}$ is an equivalence relation
satisfying

$\displaystyle E(h_{1},h_{2})\iff\forall a\in A.\quad
R_{\mathcal{H}}(h_{1},a)=R_{\mathcal{H}}(h_{2},a)\text{ and }$
$\displaystyle\quad\forall h_{1}^{\prime},h_{2}^{\prime}\in\mathcal{H}\text{
with }E(h_{1}^{\prime},h_{2}^{\prime})\text{ we have }$
$\displaystyle\quad\qquad T_{\mathcal{H}}(h_{1}^{\prime}\mid
h_{1},a)=T_{\mathcal{H}}(h_{2}^{\prime}\mid h_{2},a).$

The largest stochastic bisimulation relation is called (stochastic)
bisimulation, denoted by $\sim$. We write $[h]_{\sim}$ for the equivalence
class of history $h$ under $\sim$, and $\mathcal{H}/_{\sim}$ for the set of
equivalence classes.

######  Assumption 1 (Sufficiency of finite histories).

Every history state $h$ of size $|h|>k$ in the history MDP is bisimilar to a
history state $h^{\prime}$ of size $|h^{\prime}|\leq k$. That is, $h\sim
h^{\prime}$.

As a consequence, the history MDP satisfying Assumption 1 has a finite
bisimulation quotient MDP (Givan, Dean, and Greig 2003), and we call it a
_finite-history MDP_ instead. This finite-history MDP consists of states that
are the equivalence classes of histories under $\sim$.

######  Definition 6 (Finite-history MDP).

A POMDP satisfying Assumption 1 is a fully observable finite-state MDP
$M=(\mathcal{H}/_{\sim},A,T_{H},R_{H},\gamma)$ where the states are given by
the set of equivalence classes, the actions and discount factor from the
POMDP, and transition and reward functions defined as

$\displaystyle T_{H}([haz]_{\sim}\mid[h]_{\sim},a)=$
$\displaystyle\quad\sum_{s\in S}b(s\mid[h]_{\sim})\sum_{s^{\prime}\in
S}T(s^{\prime}\mid s,a)O(z\mid s^{\prime},a),$ $\displaystyle
R_{H}([h]_{\sim},a)=\sum_{s\in S}b(s\mid[h]_{\sim})R(s,a).$

Under bisimulation equivalence, the finite-history MDP and the POMDP are
related in the following fundamental way.

######  Theorem 1 (Optimal finite-memory policies under bisimilarity).

An optimal policy $\pi^{*}$ in the finite-history MDP is an optimal finite-
memory policy for the POMDP.

Theorem 1 is a direct result of bisimilarity (Givan, Dean, and Greig 2003). We
may number the equivalence classes in the finite-history MDP in such a way
that they correspond to memory nodes of an FSC. As a result, the finite-
history MDP can be defined on a state-space consisting of memory nodes and
observations, rather than histories.

######  Definition 7 (Finite-history MDP via FSC).

A POMDP satisfying Assumption 1 is a fully observable finite-state MDP
$M=(\mathcal{N}\times Z,A,T_{H},R_{H},\gamma)$ where the states are given by
pairs of memory nodes from an FSC and observations, the actions from the
POMDP, and transition and reward functions defined as

$\displaystyle T_{H}(\langle n^{\prime},z^{\prime}\rangle\mid\langle
n,z\rangle,a)=$ $\displaystyle\,\,\sum_{s\in S}b(s\mid\langle
n,z\rangle)\sum_{s^{\prime}\in S}T(s^{\prime}\mid s,a)O(z^{\prime}\mid
s^{\prime},a)\eta(n^{\prime}\mid n,z^{\prime},a),$ $\displaystyle
R_{H}(\langle n,z\rangle,a)=\sum_{s\in S}b(s\mid\langle n,z\rangle)R(s,a).$

Where $b(s\mid\langle n,z\rangle)$ is the belief of being in state $s$ of the
POMDP given memory node $n$ and observation $z$.

This finite-history MDP will serve as the (unknown) true MDP $M^{*}$ in our
application of SPIBB, and $\eta$ is the memory update function of the FSC.

###  3.2 Estimating the Finite-History MDP

Next, we describe how to estimate the true finite-history MDP $M^{*}$ by an
MLE-MDP $\tilde{M}$. The approach is similar to that of SPI for MDPs described
in Section 2, except that the dataset $\mathcal{D}$ is different. Here,
$\mathcal{D}$ is collected from simulating the POMDP $\mathcal{M}$ under (FSC)
policy $\pi_{\beta}$. This yields a dataset of the form

$\mathcal{D}=\langle\langle n_{t},z_{t}\rangle,a_{t},r_{t}\rangle_{t\in[1:m]}$
(3)

where the observations $z_{t}$ come from the observation function, and the
memory nodes $n_{t}$ are observed from the FSC.

######  Definition 8 (Finite-history MLE-MDP).

The MDP from Definition 7 can be estimated from a dataset $\mathcal{D}$ of the
form (3), following the same approach for estimating a standard MLE-MDP as in
Definition 4:

$\displaystyle\tilde{T}_{H}(\langle n^{\prime},z^{\prime}\rangle\mid\langle
n,z\rangle,a)=\frac{\\#_{\mathcal{D}}(\langle n,z\rangle,a,\langle
n^{\prime},z^{\prime}\rangle)}{\\#_{\mathcal{D}}(\langle n,z\rangle,a)},\text{
and }$ $\displaystyle\tilde{R}_{H}(\langle
n,z\rangle,a)=\frac{R_{\text{total}}(\langle
n,z\rangle,a)}{\\#_{\mathcal{D}}(\langle n,z\rangle,a)},\text{ where }$
$\displaystyle R_{\text{total}}(\langle n,z\rangle,a)=\sum\limits_{(\langle
n_{t},z_{t}\rangle,a_{t},r_{t})\in\mathcal{D}}\mathbb{I}(\langle
n_{t},z_{t}\rangle=\langle n,z\rangle\wedge a_{t}=a)\cdot r_{t}.$

###  3.3 Applying SPIBB to the Finite-History MDP

In this section we apply the theory of SPIBB, as introduced in Section 2, to
our setting. In particular, we have just defined a true MDP $M^{*}$ (the
finite-history MDP, Definition 6) and an MLE-MDP $\tilde{M}$ estimating
$M^{*}$ (Definition 8). Let

$\mathcal{U}=\\{(\langle n,z\rangle,a)\in\mathcal{N}\times Z\times
A\mid\\#_{\mathcal{D}}(\langle n,z\rangle,a)\leq N_{\wedge}\\}$

be the set of tuples $(\langle n,z\rangle,a)$ which occur less than
$N_{\wedge}$ times in the dataset $\mathcal{D}$ for some hyperparameter
$N_{\wedge}$. Just as in SPIBB for MDPs, we compute a new policy
$\pi_{I}\in\Pi_{k}^{\eta}$ for the MLE-MDP $\tilde{M}$ that estimates the
finite-history MDP, constrained to follow the behavior policy $\pi_{\beta}$
used to collect $\mathcal{D}$ for all $(\langle n,z\rangle,a)\in\mathcal{U}$.

######  Theorem 2 ($\zeta$-bound on history MDP).

Let $\Pi_{\beta}$ be the set of policies under the constraint of following
$\pi_{\beta}$ when $(\langle n,z\rangle,a)\in\mathcal{U}$. Then, the policy
$\pi_{I}$ computed by the SPIBB algorithm on the history MDP (Definition 2) is
a $\zeta$-approximate safe policy improvement over the behavior policy
$\pi_{\beta}$ with high probability $1-\delta$, where:

$\zeta=\frac{4V_{\max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{H}||A|2^{|Z|}}{\delta}}-\rho(\pi_{I},\tilde{M})+\rho(\pi_{\beta},\tilde{M}).$

The proof replaces the regular MDP from the SPIBB algorithm by the (infinite)
history MDP. We can reduce the exponent from $|\mathcal{H}|$, which would be
the result of naively applying the SPIBB algorithm, to $|Z|$ because of the
structure of the transition function of the history MDP. In particular, the
transition function of the history MDP is defined for histories $h$ which are
appended by an action $a$ and an observation $z$ to $haz$, see Definition 2.
As such, the successor states of $h$ in the history MDP are fully determined
by the observation $z$ instead of the full state-space, and thus we may
replace $2^{|S|}$ from Equation (1) by $2^{|Z|}$. The full proof can be found
in Appendix A.

While Theorem 2 and its proof reason over the full history MDP, these results
extend to the finite-history MDP when Assumption 1 is satisfied. We have the
following corollary.

######  Corollary 1 ($\zeta$-bound on finite-history MDP).

Let $\Pi_{\beta}$ be the set of policies under the constraint of following
$\pi_{\beta}$ when $(\langle n,z\rangle,a)\in\mathcal{U}$. Then, the policy
$\pi_{I}$ computed by the SPIBB algorithm in the finite-history MDP $M^{*}$ of
a POMDP satisfying Assumption 1 is a $\zeta$-approximate safe policy
improvement over the behavior policy $\pi_{\beta}$ with high probability
$1-\delta$, where the admissible performance loss $\zeta$ is given by

$\displaystyle\zeta=\frac{4V_{\max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{N}\\!\\!\times\\!\\!Z||A|2^{|Z|}}{\delta}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-\rho(\pi_{I},\tilde{M})+\rho(\pi_{\beta},\tilde{M}).$

Since bisimilarity is an equivalence relation, the finite-history MDP is
equivalent to the full history MDP, and thus also the POMDP, see Theorem 1. As
a consequence, the proof of Corollary 1 follows immediately from Theorem 2 and
the fact that bisimulation is an equivalence relation.

Figure 2: The Maze environment. The locations are colored according to the
agent’s perception.

##  4 Empirical Analysis

This section contains the empirical evaluation of our approach to SPI on
POMDPs. We first describe the setup of the experiments, and then present and
analyze the results. We provide further details in Appendix B and code at
https://github.com/LAVA-LAB/spi_pomdp.

Figure 3: Policy improvement on the environments Maze, Tiger and Voicemail
(first, second and third row, respectively) for datasets collected by a
behavior policy with history size $k=2$, varying the hyperparameters pairs
column-wise: $(N_{\wedge}=5,k^{\prime}=2)$, $(N_{\wedge}=20,k^{\prime}=2)$,
$(N_{\wedge}=5,k^{\prime}=3)$, and $(N_{\wedge}=20,k^{\prime}=3)$. The plots
show the mean (solid line), $10\%$-CVaR (dashed line) and $1\%$-CVaR (dotted
line). The performance of the behavior policy is shown in green (dash-dotted
line).

###  4.1 Setup

#### Environments.

We consider three POMDP problems:

  1. i)

CheeseMaze (McCallum 1993): An agent navigates a maze, moving in the four
cardinal directions, but in each state it only perceives whether or not there
is a barrier in each direction (see Figure 2). The agent is placed at a random
location at the beginning of an episode, and receives a positive reward ($+1$)
if it reaches the goal (cheese), and a small negative reward ($-0.01$)
otherwise. The episode ends when the agent reaches the goal.

  2. ii)

Tiger (Kaelbling, Littman, and Cassandra 1998): An agent is in front of two
doors, and a tiger is randomly positioned behind one of them at the beginning
of each episode. The agent has three actions: Listening, or opening one of the
doors. Listening gives a noisy observation of the position of the tiger, and a
small negative reward ($-1$). Opening the door with the tiger gives a large
negative reward ($-100$), while opening the other door gives a positive reward
($+10$).

  3. iii)

Voicemail (Williams and Young 2007): An agent controls a voicemail machine, at
the beginning of the episode the user listens to a message and decides if they
want to keep it. This information is hidden from the agent, which has three
actions: _ask_ , _save_ , and _delete_. Asking the user if they want to keep
the message gives the agent a small negative reward ($-1$) and a noisy
observation of the user’s intention. Correctly saving the message gives a
positive reward ($+5$), and a negative reward ($-10$) otherwise. Correctly
deleting the message gives a positive reward ($+5$), and a negative reward
($-20$) otherwise.

#### Satisfaction of Assumption 1.

Note that the Maze environment is close to satisfying Assumption 1 for memory
that looks back two steps, _i.e._ , $k=2$, with the exceptions of histories
with equal observations. Tiger and Voicemail do not satisfy the assumption for
any $k$.

#### Behavior policies.

The behavior policies are generated via Q-learning using the memory of an FSC
that keeps track of the last $k\in\\{1,2\\}$ observations as the state. After
convergence, we extract a softmax policy, to ensure the behavior policy
explores different actions during data collection.

#### Data collection.

We consider datasets of different sizes, namely: $1$, $2$, $5$, $10$, $20$,
$50$, $\cdots$, $5\,000$, and $10\,000$ trajectories. For each environment,
number of trajectories, and behavior policy, we generate $500$ datasets.

#### Learning.

We consider two algorithms to compute a new policy: SPIBB, and Basic RL. Both
algorithms operate on the finite-history MLE-MDP (Definition 8) related to the
finite-history MDP of the POMDP. We implement Basic RL as an unconstrained
SPIBB where $N_{\wedge}=0$, that is, it solves the MLE-MDP using value
iteration. For each dataset, we compute new policies $\pi_{I}$ using each
offline RL algorithm, considering different hyperparameters:
$N_{\wedge}\in\\{5,7,10,15,20,30,50,70,100\\}$ and $k^{\prime}\in\\{k,k+1\\}$,
where $k^{\prime}$ is the history size encoded in the FSC of $\pi_{I}$.

#### Evaluation metrics.

Each policy is evaluated over $10\,000$ episodes to obtain an estimate of the
performance of the improved policy, $\rho(\pi_{I},M^{*})$. For an evaluation
across environments and behavior policies, we also consider the normalized
policy improvement:

$\bar{\rho}(\pi_{I})=\frac{\rho(\pi_{I},M^{*})-\rho(\pi_{\beta},M^{*})}{\rho(\pi_{\max},M^{*})-\rho(\pi_{\beta},M^{*})},$

where $\pi_{\max}$ is the policy with the highest expected return in each
environment. To aggregate the results across the $500$ repetitions, we compute
the mean and Conditional Value at Risk (CVaR; Rockafellar and Uryasev 2000).
We use $x\%$-CVaR to indicate the mean of the $x\%$ lowest performances. As an
approximation of the optimal value, we show the performance of PO-UCT (Silver
and Veness 2010), which uses the environment as a simulator to compute a
policy.

Figure 4: Policy improvement on the Voicemail environment for datasets
collected with a memoryless policy ($k=1$), varying the hyperparameters pairs
column-wise: $(N_{\wedge}=5,k^{\prime}=1)$, $(N_{\wedge}=50,k^{\prime}=1)$,
$(N_{\wedge}=5,k^{\prime}=2)$, and $(N_{\wedge}=50,k^{\prime}=2)$. The plots
show the mean (solid line), $10\%$-CVaR (dashed line) and $1\%$-CVaR (dotted
line). The performance of the behavior policy is shown in green (dash-dotted
line).

###  4.2 Results

Figure 3 shows results on the three environments (ordered by row). The data
was collected using a behavior policy with $k=2$. The first column shows the
results where SPIBB uses a low threshold to consider a history-action pair
known and the same memory size as the behavior policy ($N_{\wedge}=5$ and
$k^{\prime}=2$). The second column shows the results with a higher threshold
($N_{\wedge}=20$ and $k^{\prime}=2$). The third column shows the results for
increased memory ($N_{\wedge}=5$ and $k^{\prime}=3$). Finally, the fourth
column shows the results with a higher threshold and increased memory
($N_{\wedge}=20$ and $k^{\prime}=3$). Basic RL is included everywhere to give
a perspective on the influence of different hyperparameters.

Figures 4 and 5 extend the empirical analysis on the Voicemail and Tiger
environments for memoryless behavior policy ($k=1$), since they demonstrated
to be more challenging for the safe policy improvement problem. Figure 4
considers the Voicemail environment, while Figure 5 shows the normalized
results for a range of thresholds in the Tiger environment. We provide further
results in the Appendix C.

###  4.3 Analysis

#### Basic RL is unreliable.

Across all environments, the Basic RL algorithm shows a considerable
performance drop compared to the behavior policy, even in terms of the mean
performance for smaller datasets. Notice that for Tiger and Voicemail, the
CVaR metrics are often outside the graph.

#### SPIBB outperforms Basic RL.

In the environments Tiger and Voicemail (Figure 3, second and third row), the
SPIBB algorithm shows better performance than the Basic RL across all dataset
sizes. This is likely due to the SPIBB algorithm retaining the randomization
of the behavior policy when insufficient data is available.

#### SPIBB is reliable when Assumption 1 is satisfied.

Analyzing the results for the Maze environment (Figure 3, first row), we
observe that SPIBB shows reliably outperforms the behavior policy even for a
small $N_{\wedge}$ (first column), for which only the $1\%$-CVaR shows a
performance drop.

Figure 5: Normalized performance $\bar{\rho}(\pi_{I})$ on the Tiger
environment ($k=1$). The left, middle and right columns show the mean,
$10\%$-CVaR and $1\%$-CVaR, respectively. The first row shows the results
where the improved policy uses the same memory as the behavior policy
($k^{\prime}=k$), while the second row shows the results for an improved
policy with more memory ($k^{\prime}=k+1$).

#### More memory improves the reliability.

SPIBB shows slightly unreliable behavior for small values of $N_{\wedge}$ in
the Tiger and Voicemail environments (Figure 3), as evidenced by both the CVaR
curves, which can be alleviated by increasing the $N_{\wedge}$ or the memory
of the new policy (second, third and fourth column). When Assumption 1 is
violated, the performance drop may be significant, as seen in the first two
columns of Figure 4. In this case, merely increasing the $N_{\wedge}$
threshold is not enough to guarantee a policy improvement. Increasing the
memory size, however, allows the SPIBB algorithm to reliably improve the
behavior policy, as Figure 4 (last column) and Figure 5 (second row) show.

#### Deterministic policies may require more memory.

Figure 4 shows an interesting phenomenon. In partially observable settings,
the stochastic behavior policy might perform better than the new deterministic
policy, since randomization can trade-off some amount of memory. We observe
that when $k=1$, SPIBB and Basic RL converge to deterministic policies with an
expected return lower than the behavior policy. When SPIBB has sufficient
data, it is not constrained to follow the behavior policy, and thus does not
inherit any randomization from that policy. As stated in the previous
paragraph, more memory can then yield a new deterministic policy with a higher
return than the behavior policy.

##  5 Related Work

Offline RL, also known as batch RL, learns or evaluates a policy from a fixed
batch of historical data (Levine et al. 2020). Overall, these algorithms rely
on pessimism to mitigate the lack of feedback from the environment and can be
divided in two categories (Jin, Yang, and Wang 2021): those that constrain the
final policy to stay close to the behavior policy (Laroche, Trichelair, and
des Combes 2019), and those that penalize rare experiences (Petrik,
Ghavamzadeh, and Chow 2016). Our method belongs to the first category.

Various extensions of SPIBB could be adapted for POMDPs, such as soft-SPIBB
(Nadjahi, Laroche, and des Combes 2019; Scholl et al. 2022), deep-SPIBB
(Brandfonbrener, des Combes, and Laroche 2022), and factored-SPIBB (Simão and
Spaan 2019a, b). SPI has also been studied without the behavior policy (Simão,
Laroche, and des Combes 2020) and for multi-objective (Satija et al. 2021) and
non-stationary settings (Chandak et al. 2020).

When the behavior policy is influenced by unobserved variables, we may come
across confounding variables. The problem of evaluating a policy offline was
studied in this setting, for instance, assuming that observed and unobserved
variables are decoupled (Tennenholtz, Shalit, and Mannor 2020), or that the
influence of the confounding variable on the behavior policy is limited
(Namkoong et al. 2020). Since we assume that the behavior policy only depends
on the observed history, we have no confounding variables.

##  6 Conclusions

We presented a new approach to safe policy improvement in POMDPs. Our
experiments show the applicability of the approach, even in cases where
finite-history is not sufficient to obtain optimal results. In the future, it
would be interesting to relax Assumption 1 to distance metrics (Ferns,
Panangaden, and Precup 2004, 2005) instead of exact bisimilarity.

## Acknowledgments

We would like to thank Alberto Castellini, Alessandro Farinelli, Matthijs
Spaan, and Edoardo Zorzi for discussions on related topics. We also thank
Maris Galesloot for help with the implementation of the PO-UCT algorithm. This
research has been partially funded by NWO grants OCENW.KLEIN.187 (Provably
Correct Policies for Uncertain Partially Observable Markov Decision Processes)
and NWA.1160.18.238 (PrimaVera).

## References

  * Amato, Bernstein, and Zilberstein (2010) Amato, C.; Bernstein, D. S.; and Zilberstein, S. 2010.  Optimizing fixed-size stochastic controllers for POMDPs and decentralized POMDPs.  _Auton. Agents Multi Agent Syst._ , 21(3): 293–320.
  * Åström (1965) Åström, K. J. 1965.  Optimal control of Markov processes with incomplete state information.  _Journal of mathematical analysis and applications_ , 10(1): 174–205.
  * Bonet (2002) Bonet, B. 2002.  An epsilon-Optimal Grid-Based Algorithm for Partially Observable Markov Decision Processes.  In _ICML_ , 51–58. Morgan Kaufmann.
  * Brandfonbrener, des Combes, and Laroche (2022) Brandfonbrener, D.; des Combes, R. T.; and Laroche, R. 2022.  Incorporating Explicit Uncertainty Estimates into Deep Offline Reinforcement Learning.  _arXiv preprint arXiv:2206.01085_.
  * Chandak et al. (2020) Chandak, Y.; Jordan, S. M.; Theocharous, G.; White, M.; and Thomas, P. S. 2020.  Towards Safe Policy Improvement for Non-Stationary MDPs.  In _NeurIPS_ , 9156–9168.
  * Cheng et al. (2022) Cheng, C.; Xie, T.; Jiang, N.; and Agarwal, A. 2022.  Adversarially Trained Actor Critic for Offline Reinforcement Learning.  In _ICML_ , volume 162, 3852–3878. PMLR.
  * Cubuktepe et al. (2021) Cubuktepe, M.; Jansen, N.; Junges, S.; Marandi, A.; Suilen, M.; and Topcu, U. 2021\.  Robust Finite-State Controllers for Uncertain POMDPs.  In _AAAI_ , 11792–11800. AAAI Press.
  * Dujardin, Dietterich, and Chades (2017) Dujardin, Y.; Dietterich, T.; and Chades, I. 2017.  Three New Algorithms to Solve N-POMDPs.  In _AAAI_ , 4495–4501. AAAI Press.
  * Ferns, Panangaden, and Precup (2004) Ferns, N.; Panangaden, P.; and Precup, D. 2004.  Metrics for Finite Markov Decision Processes.  In _UAI_ , 162–169. AUAI Press.
  * Ferns, Panangaden, and Precup (2005) Ferns, N.; Panangaden, P.; and Precup, D. 2005.  Metrics for Markov Decision Processes with Infinite State Spaces.  In _UAI_ , 201–208. AUAI Press.
  * Givan, Dean, and Greig (2003) Givan, R.; Dean, T. L.; and Greig, M. 2003.  Equivalence notions and model minimization in Markov decision processes.  _Artif. Intell._ , 147(1-2): 163–223.
  * Jin, Yang, and Wang (2021) Jin, Y.; Yang, Z.; and Wang, Z. 2021.  Is Pessimism Provably Efficient for Offline RL?  In _ICML_ , volume 139, 5084–5096. PMLR.
  * Junges et al. (2018) Junges, S.; Jansen, N.; Wimmer, R.; Quatmann, T.; Winterer, L.; Katoen, J.; and Becker, B. 2018.  Finite-State Controllers of POMDPs using Parameter Synthesis.  In _UAI_ , 519–529. AUAI Press.
  * Kaelbling, Littman, and Cassandra (1998) Kaelbling, L. P.; Littman, M. L.; and Cassandra, A. R. 1998.  Planning and Acting in Partially Observable Stochastic Domains.  _Artif. Intell._ , 101(1-2): 99–134.
  * Kaelbling, Littman, and Moore (1996) Kaelbling, L. P.; Littman, M. L.; and Moore, A. W. 1996.  Reinforcement Learning: A Survey.  _J. Artif. Intell. Res._ , 4: 237–285.
  * Kochenderfer (2015) Kochenderfer, M. J. 2015.  _Decision making under uncertainty: theory and application_.  MIT press.
  * Laroche, Trichelair, and des Combes (2019) Laroche, R.; Trichelair, P.; and des Combes, R. T. 2019.  Safe Policy Improvement with Baseline Bootstrapping.  In _ICML_ , volume 97, 3652–3661. PMLR.
  * Levine et al. (2020) Levine, S.; Kumar, A.; Tucker, G.; and Fu, J. 2020.  Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.  _arXiv preprint arXiv:2005.01643_.
  * Madani, Hanks, and Condon (2003) Madani, O.; Hanks, S.; and Condon, A. 2003.  On the undecidability of probabilistic planning and related stochastic optimization problems.  _Artif. Intell._ , 147(1-2): 5–34.
  * McCallum (1993) McCallum, A. 1993.  Overcoming Incomplete Perception with Utile Distinction Memory.  In Utgoff, P. E., ed., _ICML_ , 190–196.
  * Meuleau et al. (1999a) Meuleau, N.; Kim, K.; Kaelbling, L. P.; and Cassandra, A. R. 1999a.  Solving POMDPs by Searching the Space of Finite Policies.  In _UAI_ , 417–426. Morgan Kaufmann.
  * Meuleau et al. (1999b) Meuleau, N.; Peshkin, L.; Kim, K.; and Kaelbling, L. P. 1999b.  Learning Finite-State Controllers for Partially Observable Environments.  In _UAI_ , 427–436. Morgan Kaufmann.
  * Nadjahi, Laroche, and des Combes (2019) Nadjahi, K.; Laroche, R.; and des Combes, R. T. 2019.  Safe Policy Improvement with Soft Baseline Bootstrapping.  In _ECML/PKDD (3)_ , volume 11908, 53–68. Springer.
  * Namkoong et al. (2020) Namkoong, H.; Keramati, R.; Yadlowsky, S.; and Brunskill, E. 2020.  Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding.  In _NeurIPS_ , 18819–18831.
  * Petrik, Ghavamzadeh, and Chow (2016) Petrik, M.; Ghavamzadeh, M.; and Chow, Y. 2016.  Safe Policy Improvement by Minimizing Robust Baseline Regret.  In _NIPS_ , 2298–2306.
  * Puterman (1994) Puterman, M. L. 1994.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  New York, NY, USA: John Wiley & Sons, Inc., 1st edition.
  * Rockafellar and Uryasev (2000) Rockafellar, R. T.; and Uryasev, S. 2000.  Optimization of conditional value-at-risk.  _Journal of risk_ , 2(3): 21–41.
  * Satija et al. (2021) Satija, H.; Thomas, P. S.; Pineau, J.; and Laroche, R. 2021.  Multi-Objective SPIBB: Seldonian Offline Policy Improvement with Safety Constraints in Finite MDPs.  In _NeurIPS_ , 2004–2017.
  * Scholl et al. (2022) Scholl, P.; Dietrich, F.; Otte, C.; and Udluft, S. 2022.  Safe Policy Improvement Approaches on Discrete Markov Decision Processes.  In _ICAART (2)_ , 142–151. SCITEPRESS.
  * Silver and Veness (2010) Silver, D.; and Veness, J. 2010.  Monte-Carlo Planning in Large POMDPs.  In _NIPS_ , 2164–2172. Curran Associates, Inc.
  * Simão, Laroche, and des Combes (2020) Simão, T. D.; Laroche, R.; and des Combes, R. T. 2020.  Safe Policy Improvement with an Estimated Baseline Policy.  In _AAMAS_ , 1269–1277. IFAAMAS.
  * Simão and Spaan (2019a) Simão, T. D.; and Spaan, M. T. J. 2019a.  Safe Policy Improvement with Baseline Bootstrapping in Factored Environments.  In _AAAI_ , 4967–4974. AAAI Press.
  * Simão and Spaan (2019b) Simão, T. D.; and Spaan, M. T. J. 2019b.  Structure Learning for Safe Policy Improvement.  In _IJCAI_ , 3453–3459. ijcai.org.
  * Smallwood and Sondik (1973) Smallwood, R. D.; and Sondik, E. J. 1973.  The Optimal Control of Partially Observable Markov Processes over a Finite Horizon.  _Oper. Res._ , 21(5): 1071–1088.
  * Sutton and Barto (1998) Sutton, R. S.; and Barto, A. G. 1998.  _Reinforcement learning - an introduction_.  Adaptive computation and machine learning. MIT Press.
  * Tennenholtz, Shalit, and Mannor (2020) Tennenholtz, G.; Shalit, U.; and Mannor, S. 2020.  Off-Policy Evaluation in Partially Observable Environments.  In _Proc. AAAI_ , 10276–10283. AAAI Press.
  * Thomas, Theocharous, and Ghavamzadeh (2015a) Thomas, P. S.; Theocharous, G.; and Ghavamzadeh, M. 2015a.  High-Confidence Off-Policy Evaluation.  In _AAAI_ , 3000–3006. AAAI Press.
  * Thomas, Theocharous, and Ghavamzadeh (2015b) Thomas, P. S.; Theocharous, G.; and Ghavamzadeh, M. 2015b.  High Confidence Policy Improvement.  In _ICML_ , volume 37, 2380–2388. JMLR.org.
  * Weissman et al. (2003) Weissman, T.; Ordentlich, E.; Seroussi, G.; Verdu, S.; and Weinberger, M. J. 2003\.  Inequalities for the $L_{1}$ Deviation of the Empirical Distribution.  Technical report, Hewlett-Packard Labs, Palo Alto, United States.
  * Williams and Young (2007) Williams, J. D.; and Young, S. J. 2007.  Partially observable Markov decision processes for spoken dialog systems.  _Comput. Speech Lang._ , 21(2): 393–422.
  * Yeager et al. (2022) Yeager, J.; Moss, J. E. B.; Norrish, M.; and Thomas, P. S. 2022.  Mechanizing Soundness of Off-Policy Evaluation.  In _ITP_ , volume 237, 32:1–32:20.

##  Appendix A Proof of Theorem 2

#### Theorem 2

($\zeta$-bound on history MDP). _Let $\Pi_{\beta}$ be the set of policies
under the constraint of following $\pi_{\beta}$ when $(\langle
n,z\rangle,a)\in\mathcal{U}$. Then, the policy $\pi_{I}$ computed by the SPIBB
algorithm on the history MDP (Definition 2) is a $\zeta$-approximate safe
policy improvement over the behavior policy $\pi_{\beta}$ with high
probability $1-\delta$, where:_

$\zeta=\frac{4V_{\max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{H}||A|2^{|Z|}}{\delta}}-\rho(\pi_{I},\tilde{M})+\rho(\pi_{\beta},\tilde{M}).$
(4)

###### Proof of theorem 2.

First, we restate Theorem 2.1 by Weissman et al. (2003) that bounds the
L1-error of an empirical probability distribution $\tilde{P}$ given a finite
number of samples.

######  Proposition (Theorem 2.1 by Weissman et al. (2003)).

Given $m$ i.i.d. random variables distributed according to $P$ and given an
estimated probability distribution $\tilde{P}$ computed from those $m$
variables, we have

$\Pr(\|P-\tilde{P}\|_{1}\geq\epsilon)\leq(2^{n}-2)e^{-\nicefrac{{m\epsilon^{2}}}{{2}}}.$

To bound the L1-error of the estimated transition function of given a $(h,a)$
pair of the history MDP, given $\\#_{\mathcal{D}}(h,a)$ samples for
$(h,a)\in\mathcal{D}$ we can apply the Theorem 2.1 (Weissman et al. 2003) to
obtain

$\displaystyle\Pr\left(\|T(\cdot\mid h,a)-\tilde{T}(\cdot\mid
h,a)\|_{1}\geq\epsilon\right)$
$\displaystyle\quad\leq(2^{|Z|}-2)e^{-\nicefrac{{\\#_{\mathcal{D}}(h,a)\epsilon^{2}}}{{2}}}.$

Choosing an appropriate $N_{\wedge}$, we can do a union bound over all
history-action pairs, we get that the probability of having an arbitrary
history-action pair $(h,a)$ of which the L1-error is larger than $\epsilon$ is
bounded by $\delta$:

$\displaystyle\Pr$ $\displaystyle\left(\exists(h,a)\in\mathcal{H}\times
A:\|T(\cdot\mid h,a)-\tilde{T}(\cdot\mid h,a)\|_{1}\geq\epsilon\right)$
$\displaystyle\quad\leq\sum_{h,a\in\mathcal{H}\times A}Pr\left(\|T(\cdot\mid
h,a)-\tilde{T}(\cdot\mid h,a)\|_{1}\geq\epsilon\right)$
$\displaystyle\quad\leq|\mathcal{H}|\,|A|(2^{|Z|}-2)e^{-\nicefrac{{N_{\wedge}\epsilon^{2}}}{{2}}}$
$\displaystyle\quad=\delta.$

Reordering the equation above, we get

$\epsilon=\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{H}||A|2^{|Z|}}{\delta}},$
(5)

and then

$\displaystyle\Pr\left(\exists h,a\in\mathcal{H}\times A.\|T(\cdot\mid
h,a)-\tilde{T}(\cdot\mid h,a)\|_{1}\geq\epsilon\right)\leq\delta.$

The last step of the proof is to replace the $\epsilon$ from Equation 36 of
(Laroche, Trichelair, and des Combes 2019) by the value from Equation (5),
resulting in

$\displaystyle\zeta=\frac{4V_{\max}}{1-\gamma}\sqrt{\frac{2}{N_{\wedge}}\log\frac{2|\mathcal{H}||A|2^{|Z|}}{\delta}}-\rho(\pi_{I},\tilde{M})+\rho(\pi_{\beta},\tilde{M}),$

as stated in the Theorem. ∎

##  Appendix B Experiments Details

#### Further details on the problems.

All experiments use a discount factor $\gamma=0.95$, with at most $300$ steps
in an episode.

#### Training the behavior policies.

We train a Q-learning agent over $5\,000$ episodes with learning
rate($\alpha$) and exploration rate ($\epsilon$) decaying exponentially after
each episode.

$\alpha_{i}\leftarrow\alpha_{0}\exp(-\lambda*i),$
$\epsilon_{i}\leftarrow\epsilon_{0}\exp(-\lambda*i),$

where $i$ is the episode index, $\lambda$ is the decay rate, $\alpha_{0}$ and
$\epsilon_{0}$ are the initial learning rate and initial exploration rate,
respectively.

After training, we extract the behavior policy $\pi_{\beta}$ using a softmax
function

$\pi_{\beta}(a\mid s)=\frac{e^{-\tau Q(s,a)}}{\sum_{a^{\prime}\in A}e^{-\tau
Q(s,a^{\prime})}},$

where $Q(s,a)$ is the final value of the state-action pair $s,a$ and $\tau$ a
hyperparameter to control the randomness of the behavior policy. As mentioned
in the main paper, the state in this case is the history of the last $k$
observations.

|  | CheeseMaze | Tiger | Voicemail
---|---|---|---|---
Initial exploration rate | $\epsilon_{0}$ | $0.500$ | $0.500$ | $0.500$
Initial learning rate | $\alpha_{0}$ | $1.000$ | $1.000$ | $1.000$
Decay rate | $\lambda$ | $0.002$ | $0.002$ | $0.002$
Softmax temperature | $\tau$ | $15.000$ | $0.050$ | $0.300$
Table 1: Hyperparameters to generate the behavior policies.

#### Computing specifications.

All experiments were performed on a machine with a 4GHz Intel Core i9 CPU and
64Gb of memory, using a single core for each experiment.

##  Appendix C Supplementary Experimental Results

Figure 6: Policy improvement on the Tiger environment for datasets collected
with a memoryless policy ($k=1$), varying the hyperparameters pairs column-
wise: $(N_{\wedge}=5,k^{\prime}=1)$, $(N_{\wedge}=50,k^{\prime}=1)$,
$(N_{\wedge}=5,k^{\prime}=2)$, and $(N_{\wedge}=50,k^{\prime}=2)$. The plots
show the mean (solid line), $10\%$-CVaR (dashed line) and $1\%$-CVaR (dotted
line). The performance of the behavior policy is shown in green (dash-dotted
line).

Figure 7:  Normalized results ($\bar{\rho}(\pi_{I})$) on the Maze environment
($k=2$). The left, middle and right columns show the mean, $10\%$-CVaR and
$1\%$-CVaR, respectively. The first row shows the results where the improved
policy uses the same memory as the behavior policy ($k^{\prime}=k$), while the
second row shows the results for an improved policy with more memory
($k^{\prime}=k+1$).

Figure 8:  Normalized result on the Voicemail environment ($k=2$). The left,
middle and right columns show the mean, $10\%$-CVaR and $1\%$-CVaR,
respectively. The first row shows the results where the improved policy uses
the same memory as the behavior policy ($k^{\prime}=k$), while the second row
shows the results for an improved policy with more memory ($k^{\prime}=k+1$).

Figure 9: Normalized results ($\bar{\rho}(\pi_{I})$) on the Tiger environment
($k=2$). The left, middle and right columns show the mean, $10\%$-CVaR and
$1\%$-CVaR, respectively. The first row shows the results where the improved
policy uses the same memory as the behavior policy ($k^{\prime}=k$), while the
second row shows the results for an improved policy with more memory
($k^{\prime}=k+1$).

Figure 10: Normalized results ($\bar{\rho}(\pi_{I})$) on the Voicemail
environment ($k=1$). The left, middle and right columns show the mean,
$10\%$-CVaR and $1\%$-CVaR, respectively. The first row shows the results
where the improved policy uses the same memory as the behavior policy
($k^{\prime}=k$), while the second row shows the results for an improved
policy with more memory ($k^{\prime}=k+1$).