More for Less: Safe Policy Improvement with Stronger Performance Guarantees

1 Introduction

Markov decision processes (MDPs) are the standard model for sequential decision-making under uncertainty [Puterman, 1994]. Reinforcement learning (RL) solves such decisionmaking problems, in particular when the environment dynamics are unknown [Sutton and Barto, 1998].

In an online RL setting, an agent aims to learn a decisionmaking policy that maximizes the expected accumulated reward by interacting with the environment and observing feedback, typically in the form of information about the environment state and reward. While online RL has shown great performance in solving hard problems [Mnih et al., 2015; Silver et al., 2018], the assumption that the agent can always directly interact with the environment is not always realistic. In real-world applications such as robotics or healthcare, direct interaction can be impractical or dangerous [Levine et al., 2020]. Furthermore, alternatives such as simulators or digital twins may not be available or insufficiently capture the nuances of the real-world application for reliable learning [Ramakrishnan et al., 2020; Zhao et al., 2020].

Offline RL (or batch RL) [Lange et al., 2012] mitigates this concern by restricting the agent to have only access to a fixed data set of past interactions. As a common assumption, the data set has been generated by a so-called behavior policy. An offline RL algorithm aims to produce a new policy without further interactions with the environment [Levine et al., 2020]. Methods that can reliably improve the performance of a policy are key in (offline) RL.

Safe policy improvement (SPI) algorithms address this challenge by providing (probabilistic) correctness guarantees on the reliable improvement of policies [Thomas et al., 2015; Petrik et al., 2016]. These guarantees depend on the size of the data set and usually adhere to a conservative bound on the minimal amount of samples required. Since this bound often turns out to be too large for practical applications of SPI, it is instead turned into a hyperparameter (see, e.g., [Laroche et al., 2019]). The offline nature of SPI prevents further data collection, which steers the key requirements of SPI in practical settings: (1) exploit the data set as efficiently as possible and (2) compute better policies from smaller data sets.

1.1 Contributions

Our contribution provides the theoretical foundations to improve the understanding of SPI algorithms in general. Specifically, in a general SPI setting, we can guarantee a higher performance for significantly less data. Equivalently, we can allow the same amount of data and consequently provide significantly less performance guarantees. Our main technical contribution is an transformation of the underlying MDP model into a two-successor MDP (2sMDP) along with adjustments to the data set, that allows us to prove these tighter bounds. A 2sMDP is an MDP where each state-action pair has at most two successors, hence limiting the branching factor of an MDP to only two. These transformations preserve (the optimal) performance of policies and are reversible. In the context of SPI these transformations are implicit, i.e., do not have to be computed explicitly. Hence, we are able to apply standard SPI algorithms such as SPI with baseline bootstrapping

(SPIBB) [Laroche et al., 2019], and use our novel improvement guarantees without any algorithmic changes necessary, as also illustrated in Figure 1.

Following the theoretical foundations for the MDP and data set transformations (Section 4), we present two different methods to compute the new performance guarantees (Section 5). The first uses Weissman's bound [Weissman et al., 2003], as also used in, e.g., standard SPIBB, while the second uses the inverse incomplete beta function [Temme, 1992]. Our experimental results show a significant reduction in the amount of data required for equal performance guarantees (Section 6). Concretely, where the number of samples required at each state-action pair of standard SPIBB grows linearly in the number of states, our approach only grows logarithmic in the number of states for both methods. We also demonstrate the impact on three well-known benchmarks in practice by comparing them with standard SPIBB across multiple hyperparameters.

2 Preliminaries

Let X be a finite set. We denote the number of elements in X by |X|. A discrete probability distribution over X is a function µ: X → [0, 1] where ∑x∈X µ(x) = 1. The set of all such distributions is denoted by ∆(X). The L1-distance between two probability distributions µ and σ is defined as ‖µ - σ‖1 = ∑x∈X |µ(x) - σ(x)|. We write [m : n] for the set of natural numbers {m, . . . , n} ⊂ N, and I[x=x′ ] for the indicator function, returning 1 if x = x′ and 0 otherwise.

Definition 1 (MDP). AMarkov decision process (MDP) is a tuple M = (S, A, ι, P, R, γ), where S and A are finite sets of states and actions, respectively, ι ∈ S an initial state, P : S× A ⇀∆(S) is the (partial) transition function, R: S ×A ⇀ [-Rmax, Rmax] is the reward function bounded by some known value Rmax ∈ R, and γ ∈ (0, 1) ⊂ R is the discount factor.

We say that an action a is enabled in state s if P(s, a) is defined. We write P(s′ | s, a) for the transition probability P(s, a)(s′ ), and PostM(s, a) for the set of successor states reachable with positive probability from the state-action pair (s, a) in M. A path in M is a finite sequence 〈s1, a1, . . . , an-1, sn〉 ∈ (S × A)∗ × S where si ∈ PostM(si-1, ai-1) for all i ∈ [2:n]. The probability of following a path 〈s1, a1, . . . , an-1, sn〉 in the MDP M given a deterministic sequence of actions is written as PM(〈s1, a1, . . . , an-1, sn〉) and can be computed by repeatedly applying the transition probability function, i.e., PM(〈s1, a1, . . . , an-1, sn〉) = ∏n-1 i=1 P(si+1 | si, ai).

A memoryless stochastic policy for M is a function π: S → ∆(A). The set of such policies is Π. The goal is to find a policy maximizing the expected discounted reward

where rt is the reward the agent collects at time t when following policy π in the MDP.

We write V πM (s) for the state-based value function of an MDP M under a policy π. Whenever clear from context, we omit M and π. The value of a state s in an MDP M is the least solution of the Bellman equation and can be computed by, e.g., value iteration [Puterman, 1994]. The performance ρ(π,M) of a policy π in an MDP M is defined as the value in the initial state ι ∈ S, i.e., ρ(π,M) = V πM (ι).

3 Safe Policy Improvement

In safe policy improvement (SPI), we are given an MDP M with an unknown transition function, a policy πb, also known as the behavior policy, and a data set D of paths in M under πb. The goal is to derive a policy πI from πb and D that with high probability 1-δ guarantees to improve πb on M up to an admissible performance loss ζ. That is, the performance of πI is at least that of πb tolerating an error of ζ:

3.1 MaximumLikelihood Estimation

We use maximum likelihood estimation (MLE) to derive an MLE-MDP ˜M from the data set D. For a path ρ ∈ D, let #ρ(s, a) and #ρ(s, a, s′ ) be the number of (sequential) occurrences of a state-action pair (s, a) and a transition (s, a, s′ ) in ρ, respectively. We lift this notation the level of the data set D by defining #D(s, a) = ∑ρ∈D #ρ(s, a) and #D(s, a, s′ ) = ∑ρ∈D #ρ(s, a, s′ ).

Definition 2 (MLE-MDP). The maximum likelihood MDP (MLE-MDP) of an MDP M = (S, A, ι, P, R, γ) and data set D is a tuple ˜M = (S,A, ι, ˜ P,R, γ) where S, ι,A,R, and γ are as in M and the transition function is estimated from D:

Let e: S×A → R be an error function. We define Ξ ˜Me as the set of MDPs M ′ that are close to ˜M, i.e., where for all state-action pairs (s, a) the L1-distance between the transition function P ′ (· | s, a) and ˜ P(· | s, a) is at most e(s, a):

SPI methods aim at defining the error function e in such a way that Ξ ˜Me contains the true MDPM with high probability 1 - δ. Computing a policy that is an improvement over the behavior policy for all MDPs in this set then also guarantees an improved policy for the MDP M with high probability 1 - δ [Petrik et al., 2016]. The amount of data required to achieve a ζ SPI -approximately safe policy improvement with probability 1-δ (recall Equation (1)) for all state-action pairs has been established by Laroche et al. ([2019]) as

Intuitively, if the data set D satisfies the constraint in Equation 2, the MLE-MDP estimated from D will be close enough to the unknown MDP M used to obtain D. To this end, it would be likely that a policy in the MLE-MDP with better performance will also have a better performance in M.

3.2 SPI with Baseline Bootstrapping

The constraint in Equation (2) has to hold for all state-action pairs in order to guarantee a ζ-approximate improvement and thus requires a large data set with good coverage of the entire model. SPI with baseline bootstrapping (SPIBB) [Laroche et al., 2019] relaxes this requirement by only changing the behavior policy in those pairs for which the data set contains enough samples and follows the behavior policy otherwise. Specifically, state-action pairs with less than N SPIBB ∧ samples are collected in a set of unknown state-action pairs U:

SPIBB then determines an improved policy πI similar to (standard) SPI, except that if (s, a) ∈ U, πI is required to follow the behavior policy πb:

Then, πI is an improved policy as in Equation (1), where N SPIBB ∧ is treated as a hyperparameter and ζ is given by

We can rearrange this equation to compute the number of necessary samples for a ζ SPIBB -approximate improvement. As ρ(πI , ˜M) is only known at runtime, we have to employ an under-approximation ρ(πb, ˜M) to a priori compute

Thus, the sample size constraint N SPIBB ∧ grows approximately linearly in terms of the size of the MDP. The exponent of the term 2|S| is an over-approximation of the maximum branching factor of the MDP, since worst-case, the MDP can be fully connected. In the following Section, we present our approach to limit the branching factor of an MDP. After that, we present two methods that exploit this limited branching factor to derive improved sampling size constraints for SPI that satisfy the same guarantees.

4 Tighter Improvement Bounds for SPI

In the following, we present the technical construction of twosuccessor MDPs and the data set transformation that allows us to derive the tighter performance guarantees in SPI.

4.1 FromMDP to Two-Successor MDP

A two-successor MDP (2sMDP) is an MDP M 2s where each state-action pair (s, a) has at most two possible successors states, i.e., |PostM2s(s, a)| ≤ 2. To transform an MDP M = (S,A, ι, P,R, γ) into a 2sMDP, we introduce a set of auxiliary states Saux along with the main states S of the MDP M. Further, we include an additional action τ and adapt the probability and reward functions towards a 2sMDP M 2s = (S ∪ Saux, A ∪ {τ }, ι, P 2s , R2s , γ 2s ).

For readability, we now detail the transformation for a fixed state-action pair (s, a) with three or more successors. The transformation of the whole MDP follows from repeatedly applying this transformation to all such state-action pairs.

We enumerate the successor states of (s, a), i.e., PostM(s, a) = {s1, . . . , sk} and define pi = P(si | s, a) for all i = 1, . . . , k. Further, we introduce k - 2 auxiliary states Ss,a aux = {x2, . . . , xk-1}, each with one available action with a binary outcome. Concretely, the two possible outcomes in state xi are "move to state si" or "move to one of the states si+1, . . . , sk" where the latter is represented by moving to an auxiliary state xi+1, unless i = k - 1 in which case we immediately move to sk. Formally, the new transition function P 2s (· | s, a) is:

For the transition function P 2s in the auxiliary states we define a new action τ that will be the only enabled action in these states. For i > 1, the transition function P 2s is then

An example of this transformation is shown in Figure 2, where Figure 2a shows the original MDP and Figure 2b shows the resulting 2sMDP. As we introduce |Post(s, a)| auxiliary states for a state-action pair (s, a), and k ≤ |S| in the worst-case of a fully connected MDP, we can bound the number of states in the 2sMDP by |S ∪ Saux| ≤ |S| + |S||A|(|S| - 2) ≤ |S|2 |A|. Note that we did not specify a particular order for the enumeration of the successor states. Further, other transformations utilizing auxiliary states with a different structure (e.g., a balanced binary tree) are possible.

However, neither the structure of the auxiliary states, nor the order of successor states changes the total number of states in the 2sMDP, which is the deciding factor for the application of this transformation in the context of SPI algorithms.

The extension of the reward function is straightforward, i.e., the agent receives the same reward as in the original MDP when in main states and no reward when in auxiliary states:

Any policy π for the MDP M can be extended into a policy π2s for the 2sMDP M 2s by copying π for states in S and choosing τ otherwise:

Finally, in order to preserve discounting correctly, we introduce a state-dependent discount factor γ 2s , such that discounting only occurs in the main states, i.e.,

This yields the following value function for the 2sMDP M 2s :

The performance of policy π2s on M 2s uses the value function defined above and is denoted by ρ2s (π2s , M 2s ) = V π2s M2s(ι), for the initial state ι ∈ S. Our transformation described above, together with the adjusted value function, indeed preserves the performance of the original MDP and policy:

Theorem 1 (Preservation of transition probabilities). For every transition (s, a, s′ ) in the original MDP M, there exists a unique path 〈s, a, x2, τ, . . . , xi, τ, s′ 〉 in the 2sMDPM 2s with the same probability. That is,

Wienh¨oft et al. [2023] prove all theoretical results.

Corollary 1 (Preservation of performance). Let M be an MDP, π a policy for M, and M 2s the two-successor MDP with policy π2s constructed from M and π as described above. Then ρ(π,M) = ρ2s (π2s ,M 2s ).

4.2 Data-set Transformation

In the previous section, we discussed how to transform an MDP into a 2sMDP. However, for SPI we do not have access to the underlying MDP, but only to a data set D and the behavior policy πb used to collect this data. In this section, we present a transformation similar to the one fromMDP to 2sMDP, but now for the data set D. This data set transformation allows us to estimate a 2sMDP from the transformed data via maximum likelihood estimation (MLE).

We again assume a data set D of observed states and actions of the form D = 〈st, at〉t∈[1:m] from an MDP M. We transform the data set D into a data set D2s that we use to define a two-successor MLE-MDP ˜M 2s . Each sample (st, at, st+1) in D is transformed into a set of samples, each corresponding to a path from st to st+1 via states in Saux in M 2s . Importantly, the data set transformation only relies on D and not on any additional knowledge about M.

Similar to the notation in Section 3, let #D(x) denote the number of times x occurs in D. For each state-action pair (s, a) ∈ S × A we denote its successor states in ˜M as Post ˜M (s, a) = {si |#D(s, a, si) > 0}, which are again enumerated by {s1, . . . , sk}. Similarly as for the MDP transformation, we define Post ˜M2s(s, a) = Post ˜M (s, a) if k ≤ 2 and Post ˜M2s (s, a) = {s1, x2} otherwise. For auxiliary states xi ∈ Ss,a aux , we define Post ˜M2s(xi, τ) = {si, xi+1} for i < k-1 and Post ˜M2s (xk-1, τ) = {sk-1, sk}. We then define the transformed data set D2s from D for each s ∈ S and s′ ∈ Post ˜M2s(s, a) as follows:

Further, for each xi ∈ Ss,a aux and s′ ∈ Post ˜M2s(s, a)

The following preservation results for data generated MLEMDPs are in the line of Theorem 1 and Corollary 1. See Figure 1 for an overview of the relationships between theorems.

Theorem 2 (Preservation of estimated transition probabilities). Let D be a data set and D2s be the data set obtained by the transformation above. Further, let ˜M and ˜M 2s be the MLE-MDPs constructed from D and D2s , respectively. Then for every transition (s, a, s′ ) in ˜M there is a unique path 〈s, a, x2, τ, . . . , xi, τ, s′ 〉 in ˜M 2s with the same probability:

Corollary 2 (Preservation of estimated performance). Let ˜M and ˜M 2s be the MLE-MDPs as above, constructed from D and D2s , respectively. Further, let ˜π be an arbitrary policy on ˜M and ˜π2s the policy that extends π for ˜M 2s by choosing τ in all auxiliary states. Then ρ(˜π, ˜M) = ρ2s (˜π2s , ˜M 2s ).

We want to emphasize that while D2s may contain more samples than D, it does not yield any additional information. Rather, instead of viewing each transitions sample as an atomic data point, in D2s transition samples are considered like a multi-step process. E.g, The sample (s, a, s3) ∈ D would be transformed into the samples {(s, a, x2), (x2, τ, x3), (x3, τ, s3)} ∈ D2s which in the construction of the MLE-MDP are used to estimate the probabilities P(s′ ̸= s1 | s, a), P(s′ ̸= s2 | s, a, s′ ̸= s1) and P(s′ = s3 | s, a, s′ ̸= s1, s′ ̸= s2), respectively. The probabilities of these events are mutually independent, but when multiplied give exactly P (s3 | s, a).

5 SPI in Two-Successor MDPs

In this section, we discuss how SPI can benefit from twosuccessor MDPs as constructed following our new transformation presented in Section 4. The dominating term in the bound N obtained by [Laroche et al., 2019] is the branching factor of the MDP, which, without any prior information, has to necessarily be over-approximated by |S| (cf. Section 3.2). We use our transformation above to bound the branching factor to k = 2, which allows us to provide stronger guarantees with the same data set (or conversely, require less data to guarantee a set maximum performance loss). Note that bounding the branching factor by any other constant can be achieved by a similar transformation as in Section 4, but k = 2 leads to an optimal bound [Wienh¨oft et al., 2023].

Let ˜M and ˜M 2s be theMLE-MDPs inferred from data sets D and D2s , respectively. Further, let π⊙ and π2s ⊙ denote the optimal policies in these MLE-MDPs, constrained to the set of policies that follow πb for state-action pairs (s, a) ∈ U. Note that these optimal policies can easily be computed using, e.g., standard value iteration. First, we show how to improve the admissible performance loss ζ in SPI on twosuccessor MDPs.

Lemma 1. Let M 2s be a two-successor MDP with behavior policy πb. Then, π2s ⊙ is a ζ-approximately safe policy improvement over πb with high probability 1 - δ, where:

For a general MDP M, we can utilize this result by first applying the transformation from Section 4.1.

Theorem 3 (Weissman-based tighter improvement guarantee). Let M be an MDP with behavior policy πb. Then, π⊙ is a ζ 2s -approximate safe policy improvement over πb with high probability 1 - δ, where:

As for ζ SPIBB , we can rearrange the equation to compute the number of necessary samples for a ζ 2s -safe improvement:

Note that ζ 2s and N 2s ∧ only depend on parameters of M and policy performances on ˜M, which follows from Corollary 2 yielding ρ(π⊙, ˜M) = ρ2s (π⊙, ˜M 2s ). Hence, it is not necessary to explicitly compute the transformed MLE-MDP ˜M 2s .

5.1 Uncertainty in Two-Successor MDPs

So far, the methods we outlined relied on a bound of the L1distance between a probability vector and its estimate based on a number of samples [Weissman et al., 2003]. In this section, we outline a second method to tighten this bound for two-successor MDP and how to apply it to obtain a smaller approximation error ζ β for a fixed N β ∧ .

We now fix a state-action pair (s, a). Since we are dealing with a two-successor MDP, there are only two successor states, s1 and s2. To bound the error function, we view each sample of action a in state s as a Bernoulli trial. As shorthand notation, we define p = P(s, a, s1), and consequently we have 1 - p = P(s, a, s2). Using a uniform prior over p and given a data set D in which (s, a, s1) occurs k1 times and (s, a, s2) occurs k2 times, the posterior probability over p is given by a beta distribution with parameters k1+1 and k2+1, i.e., Pr(p | D) ∼ B(k1+1, k2+1) [Jaynes, 2003]. We can express the error function in terms of the probability of p being contained in a given interval [p, p] as e(s, a) = p - p.

Formally, given a 2sMDP M 2s and an error tolerance δ, we construct an error function e: S × A → R that ensures with probability 1 - δ that ‖P(s, a) - ˆ P(s, a)‖1 ≤ e(s, a) for all (s, a). To achieve this, we distribute δ uniformly over all states to obtain δT = δ/|S|, independently ensuring that for each state-action pair (s, a) the condition ‖P(s, a) - ˆ P(s, a)‖1 ≤ e(s, a) is satisfied with probability at least 1- δT .

The task that remains is to find such an interval [p, p] for which we can guarantee with probability δT that p is contained within it. Formally, we can express this via the incomplete regularized beta function I, which in turn is defined as the cumulative density function of the beta distribution B:

We show that we can define the smallest such interval in terms of the inverse incomplete beta function [Temme, 1992], denoted as I -1 δ .

Lemma 2. Let k ∼ Bin(n, p) be a random variable according to a binomial distribution. Then the smallest interval [p, p] for which

holds, has size

Next, we show how to utilize this bound for the interval size in MDPs with arbitrary topology. The core idea is the same as in Theorem 3: We transform the MDP into a 2sMDP and apply the error bound e(s, a) = p - p from Lemma 2.

Theorem4 (Beta-based tighter improvement guarantee). Let M be an MDP with behavior policy πb. Then, π⊙ is a ζ β - approximate safe policy improvement over πb with high probability 1 - δ, where:

There is no closed formula to directly compute N β ∧ for a given ζ β . However, for a given admissible performance loss ζ, we can perform a binary search to obtain the smallest natural number N β ∧ such that ζ β ≤ ζ given in Theorem 4.

Comparison of Different N∧. In the context of SPI, finding an N∧ that is as small as possible while still guaranteeing ζapproximate improvement is the main objective. An overview of the different ζ and N∧ that are available is given in Table 1. Comparing the equations for different N∧, we immediately see that N 2s ∧ ≤ N SPIBB ∧ if and only if 2|S| ≥ 4|S||A|. This means the only MDPs where standard SPIBB outperforms our 2sMDP approach are environments with a small statespace but a large action-space. By Lemma 2, we have that the error term e(s, a) used to compute ζ β is minimal in the 2sMDP 1 , and in particular it is smaller than the error term used to compute ζ 2s . Thus we always have N β ∧ ≤ N 2s ∧ . In case 2|S| < 4|S||A| it is also possible to compute both N SPIBB ∧ , and N β ∧ and simply choose the smaller one.

6 Implementation and Evaluation

We provide an evaluation 2 of our approach from two different perspectives. First, a theoretical evaluation of how the different N∧ depend on the size of a hypothetical MDP, and second, a practical evaluation to investigate how smaller N∧ values translate to the performance of the improved policies.

1 Technically, Lemma 2 allows for arbitrary parameters while the SPIBB algorithm only allows integers for the number of samples, and thus integer parameters in the inverse beta function, so ζ β is only minimal for evenN β ∧ . However, we can easily adapt the equation for odd N β ∧ by replacing N β ∧ by N β ∧ - 1 and N β ∧ +1, respectively.

2 Code available at https://github.com/LAVA-LAB/improved spi.

6.1 Example Comparison of Different N∧

To render the theoretical differences between the possible N∧ discussed at the end of Section 5 more tangible, we now give a concrete example.

We assume a hypothetical MDP with |A| = 4, Vmax = 1, γ = 0.95, and SPIBB parameters δ = 0.1 and ζ = 0.1. For varying sizes of the state-space, we compute all three sample size constraints: N SPIBB ∧ , N 2s ∧ , and N β ∧. The results are shown in Figure 3, where Figure 3a shows the full plot and Figure 3b provides an excerpt to differentiate between the N 2s ∧ and N β ∧ plots by scaling down the y-axis. Note that the x-axis, the number of states in our hypothetical MDP, is on a log-scale. We see that N SPIBB ∧ grows linearly with the number of states, whereas N 2s ∧ and N β ∧ are logarithmic in the number of states. Further, we note that N β ∧ is significantly below N 2s ∧ , which follows from Lemma 1. Finally, the difference between N SPIBB ∧ and N 2s ∧ is for small MDPs of around a hundred states already a factor 10.

Discussion. While we show that a significant reduction of the required number of samples per state-action pair N∧ is possible via our two approaches, we note that even for small MDPs (e.g., |S| = 100) we still need over 10 million samples per state-action pair to guarantee that an improved policy is safe w.r.t. the behavior policy. That is, with probability 1 - δ = 0.9, an improved policy will have an admissible performance loss of at most ζ = 0.1, which is infeasible in practice. Nevertheless, a practical evaluation of our approaches is possible taking on a different perspective, which we address in the next section.

6.2 Evaluation in SPIBB

We integrate our novel results for computing ζ 2s , ζ β , N 2s ∧ , and N β ∧ into the implementation of SPIBB [Laroche et al., 2019].

Benchmarks. We consider two standard benchmarks used in SPI and one other well-known MDP: the 25-state Gridworld proposed by Laroche et al. [2019], the 25-state Wet Chicken benchmark [Hans and Udluft, 2009], which was used to evaluate SPI approaches by Scholl et al. [2022], and a 376state instance of Resource Gathering proposed by Barrett and Narayanan [2008].

(a) N SPIBB

∧ = 100,N 2s

∧ = 55,N β

∧ = 27.

(b) N SPIBB

∧ = 200,N 2s

∧ = 110,N β

∧ = 67.

(c) N SPIBB

∧ = 400,N 2s

Figure 4: Safe policy improvement on the Gridworld environment.

Behavior policy. For the Gridworld, we use the same behavior policy as [Laroche et al., 2019]. For the Wet Chicken environment, we use Q-Learning with a softmax function to derive a behavior policy. The behavior policy of Resource Gathering was derived from the optimal policy by selecting each non-optimal action with a probability of 1e-5.

Methodology. Recall that in the standard SPIBB approach, N∧ is used as a hyperparameter, since the actual N∧ for reasonable δ and ζ are infeasible. While our methods improve significantly on N∧, the values we obtain are still infeasible in practice, as discussed in Section 6.1. We still use N SPIBB ∧ as a hyperparameter, and then run the SPIBB algorithm and compute the resulting ζ SPIBB . This ζ SPIBB is consequently used to compute the values N 2s ∧ and N β ∧ that ensure the same performance loss. We then run SPIBB again with these two values for N∧. As seen in the previous experiment, and detailed at the end of Section 5, for most MDPs - including our examples - we have N β ∧ ≤ N 2s ∧ ≤ N SPIBB ∧ for a fixed ζ.

Evaluation metrics. For each data set size, we repeat each experiment 1000 times and report the mean performance of the learned policy, as well as the 10% and 1% conditional value at risk (CVaR) values [Rockafellar and Uryasev, 2000], indicating the mean performance of the worst 10% and 1% runs. To give a complete picture, we also include the performance of basic RL (dynamic programming on the MLEMDP [Sutton and Barto, 1998]), the behavior policy πb, and the optimal policy π∗ of the underlying MDP.

Results. We present the results for the Gridworld, Wet Chicken, and Resource Gathering environments for three different hyperparameters N SPIBB ∧ in Figures 4, 5, and 6, respectively. In all instances, we see similar and improved behaviors as we presumed by sharpening the sampling bounds with our new approaches. Smaller values for N∧ typically require smaller data sets for a policy to start improving, and this is precisely what our methods set out to do. In particular, we note that our methods (2S and Beta) are quicker to converge to an optimal policy than standard SPIBB. Beta is, as expected, the fastest, and starts to improve over the behavior policy for data sets about half the size compared to SPIBB in the Gridworld. Further, while theoretically, the factor between the different N∧ does not directly translate to the whole data set size, we see that in practice on all three benchmarks this is roughly the case. Finally, we note that Basic RL is unreliable compared to the SPI methods, as seen by the CVaR values being significantly below the baseline performance for several data set sizes in all three environments. This is as expected and in accordance with well-established results.

∧ = 219,N β

∧ = 146.

(a) N SPIBB

|D|

∧ = 600,N 2s

7 RelatedWork

A variant of our transformation from MDP to 2sMDP was introduced by Mayr and Munday [2023], utilizing binary trees built from auxiliary states as gadgets. Similar to our construction, Junges et al. [2018] transform a partially observable MDP (POMDP) [Kaelbling et al., 1998; Spaan, 2012] into a simple POMDP, where each state has either one action choice, and an arbitrary number of successor states, or where there are multiple actions available but each action has a single successor state. The same transformation was applied to uncertain POMDPs [Cubuktepe et al., 2021].

Besides the main approaches to SPI mentioned in Section 3, there are a number of other noteworthy works in this area. SPIBB has been extended to soft baseline bootstrapping in [Nadjahi et al., 2019], where instead of either following the behavior policy or the optimal policy in the MLE-MDP in a state-action pair, randomization between the two is applied. However, the theoretical guarantees of this approach rely on an assumption that rarely holds [Scholl et al., 2022].

Incorporating structural knowledge of the environment has been shown to improve the sample complexity of SPI algorithms [Sim˜ao and Spaan, 2019a; Sim˜ao and Spaan, 2019b]. It is also possible to deploy the SPIBB algorithm in problems with large state space using MCTS [Castellini et al., 2023]. For a more detailed overview of SPI approaches and an empirical comparison between them, see [Scholl et al., 2022]. For an overview of how these algorithms scale in the number of states, we refer to [Brandfonbrener et al., 2022].

Other related work investigated how to relax some of the

∧ = 43,N β

∧ = 12.

(b) N SPIBB

|D|

∧ = 800,N 2s

∧ = 57,N β

∧ = 25.

(c) N SPIBB

|D|

∧ = 1000,N 2s

Figure 6: Safe policy improvement on the Resource Gathering environment.

assumptions SPI methods make. In [Sim˜ao et al., 2020], a method for estimating the behavior policy is introduced, relaxing the need to know this policy. Finally, a number of recent works extend the scope and relax common assumptions by introducing SPI in problems with partial observability [Sim˜ao et al., 2023], non-stationary dynamics [Chandak et al., 2020], and multiple objectives [Satija et al., 2021].

Finally, we note that SPI is a specific offline RL problem [Levine et al., 2020], which has seen significant advances recently [Kidambi et al., 2020; Yu et al., 2020; Kumar et al., 2020; Smit et al., 2021; Yu et al., 2021; Rigter et al., 2022]. While these approaches may be applicable to high dimensional problems such as control tasks and problems with large observation space [Fu et al., 2020], they often ignore the reliability aspect of improving over a baseline policy, as SPI algorithms do. Nevertheless, it remains a challenge to bring SPI to high-dimensional problems.

8 Conclusion

We presented a new approach to safe policy improvement that reduces the required size of data sets significantly. We derived new performance guarantees and applied them to state-of-theart approaches such as SPIBB. Specifically, we introduced a novel transformation to the underlying MDP model that limits the branching factor, and provided two new ways of computing the admissible performance loss ζ and the sample size constraint N∧, both exploiting the limited branching factor in SPI(BB). This improves the overall performance of SPI algorithms, leading to more efficient use of a given data set.

∧ = 71,N β

∧ = 37.

Contribution Statement

Patrick Wienh¨oft and Marnix Suilen share first authorship, contributing equally to the development and implementation of the method. The other authors contributed with discussions, ideas, and the presentation of the method.

Acknowledgments

The authors were partially supported by the DFG through the Cluster of Excellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany's Excellence Strategy), the TRR 248 (see https://perspicuous-computing.science, project ID 389792660), the NWO grants OCENW.KLEIN.187 (Provably Correct Policies for Uncertain Partially Observable Markov Decision Processes) and NWA.1160.18.238 (PrimaVera), and the ERC Starting Grant 101077178 (DEUCE).