#  Deterministic Policies for Constrained Reinforcement Learning in
Polynomial-Time

Jeremy McMahan

###### Abstract

We present a novel algorithm that efficiently computes near-optimal
deterministic policies for constrained reinforcement learning (CRL) problems.
Our approach combines three key ideas: (1) value-demand augmentation, (2)
action-space approximate dynamic programming, and (3) time-space rounding.
Under mild reward assumptions, our algorithm constitutes a fully polynomial-
time approximation scheme (FPTAS) for a diverse class of cost criteria. This
class requires that the cost of a policy can be computed recursively over both
time and (state) space, which includes classical expectation, almost sure, and
anytime constraints. Our work not only provides provably efficient algorithms
to address real-world challenges in decision-making but also offers a unifying
theory for the efficient computation of constrained deterministic policies.

##  1 Introduction

Constrained Reinforcement Learning (CRL) traditionally produces stochastic,
expectation-constrained policies that can behave undesirably - imagine a self-
driving car that randomly changes lanes or runs out of fuel. However,
artificial decision-making systems must be predictable, trustworthy, and
robust. One approach to ensuring these qualities is to focus on deterministic
policies, which are inherently predictable and trustworthy. Moreover, they are
easy to implement [10], reliable for autonomous vehicles [16, 12], and
effective for multi-agent coordination [23]. Similarly, almost sure and
anytime constraints [21] provide inherent trustworthiness and robustness,
essential for applications in medicine [6, 22, 18], disaster relief [9, 29,
27], and resource management [20, 19, 24, 4]. Despite the advantages of
deterministic policies and stricter constraints, their computation remains an
open challenge in CRL. Our research aims to address this challenge by studying
the computational complexity of computing deterministic policies for a wide
range of constraint types.

Consider a constrained Markov Decision Process (cMDP) denoted by $M$. Let $C$
represent an arbitrary cost criterion and $B$ be the available budget. We
focus on the set of deterministic policies denoted by $\Pi^{D}$. Our objective
is to compute: $\max_{\pi\in\Pi^{D}}V^{\pi}_{M}\text{ s.t. }C_{M}^{\pi}\leq
B$, where $V^{\pi}_{M}$ is the value and $C^{\pi}_{M}$ is the cost of $\pi$ in
$M$. This objective generalizes the example of a self-driving car calculating
the fastest fixed route without running out of fuel. Our main question is the
following:

> _Can near-optimal deterministic policies for constrained reinforcement
> learning problems be computed in polynomial time?_

Although optimal stochastic policies for expectation-constrained problems are
efficiently computable, the situation drastically changes when we require
deterministic policies and general constraints. Computing optimal
deterministic policies is NP-hard for most popular constraints, including
expectation [10], chance [30], almost sure, and anytime constraints [21]. This
complexity remains even if we relax our goal to finding just one feasible
policy, provided that we are dealing with a single chance constraint [30], or
any two of the other mentioned constraints [21]. Beyond these computational
challenges, traditional solution methods, such as backward induction [25, 2],
fail to apply due to the cyclic dependencies among subproblems: the value of
any decision may depend on the costs of both preceding and concurrent
decisions, preventing a solution from being computed in a single backward
pass. Therefore, our problem is far from trivial and calls for novel,
sophisticated techniques.

#### Past Work.

Previous work has proposed numerous algorithms, yet none simultaneously
achieve computational efficiency, feasibility, and optimality. Optimal and
feasible algorithms, albeit inefficient, utilize Mixed-Integer Linear Programs
[8] and Dual-guided heuristic forward searches [15] for expectation
constraints, and cost-augmented MDPs for almost sure [5] and anytime
constraints [21]. Conversely, optimal and efficient algorithms, though
infeasible, are known for expectation [26], almost sure, and anytime
constraints [21]. A fully polynomial-time approximation scheme (FPTAS) [28] is
known for expectation constraints, but it requires strong assumptions such as
a constant horizon [17]. Thus, striking a balance between computational
efficiency, feasibility, and optimality remains a significant challenge in the
pursuit of deterministic policies.

#### Our Contributions.

We present an affirmative answer to our question for a class of criteria that
we call time-space recursive (TSR), which captures expectation, almost sure,
and anytime constraints. We propose a novel algorithm that computes a near-
optimal and constraint-compliant deterministic policy for any cMDP and TSR
criterion. When the rewards are either polynomially bounded or non-negative,
our algorithm becomes an FPTAS, which achieves the best approximation
guarantees under worst-case analysis. Our algorithmic approach fully exploits
the TSR condition, which enables the cost of a policy to be computed
recursively in both time and (state) space. Conversely, several non-TSR
criteria, such as chance constraints, are provably inapproximable further
highlighting the pivotal role of TSR for efficient computation. Thus, our work
not only develops the first provably efficient, near-optimal algorithm for the
problem but also sheds light on a fundamental property that enables efficient
computation of constrained deterministic policies.

Our algorithmic approach breaks down into three main ideas: (1) value-demand
augmentation, (2) action-space approximate dynamic programming, and (3) time-
space rounding. We first reduce our problem to an equivalent minimization
problem. Then, we augment the states with value demands and the actions with
future value demands to break cyclic subproblem dependencies, enabling dynamic
programming methods. Importantly, we use values because they can be rounded
without compromising feasibility [21] and can capture constraints that are not
predictable from realized cumulative costs. However, this results in an
exponential action space, making the solution of the Bellman operator as hard
as the knapsack problem. By exploiting the space-recursive nature of the
criterion, we can efficiently approximate the Bellman operator with dynamic
programming. Finally, rounding value demands result in approximation errors
over both time and space, but carefully controlling these errors ensures
provable guarantees.

###  1.1 Related Work

#### Approximate Packing.

Stochastic packing problems, which generalize the knapsack problem, are often
special cases of our problem. Dean et al. [7], Frieze and Clarke [11] derived
algorithms with optimal approximation ratio for stochastic and integer packing
with multiple constraints, respectively. Yang et al. [31], Bhalgat et al. [3]
designed efficient approximation algorithms for variations of the stochastic
knapsack problem. Lastly, Halman et al. [14] derived an FPTAS for a general
class of stochastic dynamic programs, which was then further improved in [13,
1]. These methods require a single-dimensional state space that captures the
constraint. In contrast, our problems have an innate state space in addition
to the constraint, making our problem multi-dimensional. Our work can be
viewed as a similar general dynamic programming framework but designed for the
more complex MDP setting.

##  2 Cost Criteria

In this section, we formalize our problem setting. We also define our
conditions for cost criteria.

#### Constrained Markov Decision Processes.

A (tabular, finite-horizon) _Constrained Markov Decision Process_ (cMDP) is a
tuple $M=(\mathcal{S},\mathcal{A},P,r,c,H)$, where (i) $\mathcal{S}$ is the
finite set of _states_ , (ii) $\mathcal{A}$ is the finite set of _actions_ ,
(iii) $P_{h}(s,a)\in\Delta(S)$ is the _transition_ distribution, (iv)
$r_{h}(s,a)\in\mathbb{R}$ is the _reward_ , (v) $c_{h}(s,a)\in\mathbb{R}$ is
the _cost_ , and (vi) $H\in\mathbb{N}$ is the finite _time horizon_. We let
$S:=|\mathcal{S}|$, $A:=|\mathcal{A}|$, $[H]:=\left\\{1,\ldots,H\right\\}$,
and $\mathcal{M}$ denote the set of all cMDPs. We also let
$r_{max}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{h,s,a}|r_{h}(s,a)|$
denote the maximum magnitude reward,
$r_{min}\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{h,s,a}r_{h}(s,a)$ denote
the true minimum reward, and
$p_{min}\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{h,s,a,s^{\prime}}P_{h}(s^{\prime}\mid
s,a)$ denote the minimum transition probability. Since $\mathcal{S}$ is a
finite set, we often assume $\mathcal{S}=[S]$ WLOG. Lastly, for any predicate
$p$, we use the Iverson bracket notation $[p]$ to denote $1$ if $p$ is true
and $0$ otherwise, and we let $\chi_{p}$ denote the characteristic function
which evaluates to $0$ if $p$ is true and $\infty$ otherwise.

#### Interaction Protocol.

The agent interacts with $M$ using a policy $\pi=(\pi_{h})_{h=1}^{H}$. In the
fullest generality, $\pi_{h}:\mathcal{H}_{h}\to\Delta(\mathcal{A})$ is a
mapping from the observed history at time $h$ to a distribution of actions. In
contrast, a deterministic policy takes the form
$\pi_{h}:\mathcal{H}_{h}\to\mathcal{A}$. We let $\Pi$ denote the set of all
possible policies and $\Pi^{D}$ denote the set of all deterministic policies.
The agent starts at the initial state $s_{0}\in\mathcal{S}$ with observed
history $\tau_{1}=(s_{0})$. For any $h\in[H]$, the agent chooses an action
$a_{h}\sim\pi_{h}(\tau_{h})$. Then, the agent receives immediate reward
$r_{h}(s_{h},a_{h})$ and cost $c_{h}(s_{h},a_{h})$. Lastly, $M$ transitions to
state $s_{h+1}\sim P_{h}(s_{h},a_{h})$ and the agent updates the history to
$\tau_{h+1}=(\tau_{h},a_{h},s_{h+1})$. This process is repeated for $H$ steps;
the interaction ends once $s_{H+1}$ is reached.

#### Objective.

For any cost criterion $C:\mathcal{M}\times\Pi\to\mathbb{R}$ and budget
$B\in\mathbb{R}$, the agent’s goal is to compute a solution to the following
optimization problem:

$\max_{\pi\in\Pi}\mathbb{E}^{\pi}_{M}\left[\sum_{h=1}^{H}r_{h}(s_{h},a_{h})\right]\quad\text{s.t.}\quad\begin{cases}C^{\pi}_{M}\leq
B\\\ \pi\text{ deterministic}\end{cases}.$ (CON)

Here, $\mathbb{P}^{\pi}_{M}$ denotes the probability law over histories
induced from the interaction of $\pi$ with $M$, and $\mathbb{E}^{\pi}_{M}$
denotes the expectation defined by this law. We let
$V^{\pi}_{M}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}^{\pi}_{M}\left[\sum_{t=1}^{H}r_{t}(s_{t},a_{t})\right]$
denote the value of a policy $\pi$, and $V^{*}_{M}$ denote the optimal
solution value to (CON).

#### Cost Criteria.

We consider a broad family of cost criteria that satisfy a strengthening of
the standard policy evaluation equations [25]. This strengthening requires not
only the cost of a policy to be computable recursively in the time horizon,
but at each time the cost should also break down recursively in (state) space.

######  Definition 1 (TSR).

We call a cost criterion $C$ _time-recursive_ (TR) if for any cMDP $M$ and
policy $\pi\in\Pi^{D}$, $\pi$’s cost decomposes recursively into
$C_{M}^{\pi}=C_{1}^{\pi}(s_{0})$. Here, $C_{H+1}^{\pi}(\cdot)=\mathbf{0}$ and
for any $h\in[H]$ and $\tau_{h}\in\mathcal{H}_{h}$,

$C_{h}^{\pi}(\tau_{h})=c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),C_{h+1}^{\pi}\left(\tau_{h},a,s^{\prime}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right),$ (TR)

where $s=s_{h}(\tau_{h})$, $a=\pi_{h}(\tau_{h})$, and $f$ is a non-decreasing
function111When we say a multivariate function is non-decreasing, we mean it
is non-decreasing with respect to the partial ordering induced by component-
wise ordering. computable in $O(S)$ time. For technical reasons, we also
require that $f(x)=\infty$ whenever $\infty\in x$.

We further say $C$ is _time-space-recursive_ (TSR) if the $f$ term above is
equal to $g_{h}^{\tau_{h},a}(1)$. Here, $g_{h}^{\tau_{h},a}(S+1)=0$ and for
any $t\leq S$,

$g_{h}^{\tau_{h},a}(t)=\alpha\left(\beta\left(P_{h}(t\mid
s,a),C_{h+1}^{\pi}\left(\tau_{h},a,t\right)\right),g_{h}^{\tau_{h},a}(t+1)\right),$
(SR)

where $\alpha$ is a non-decreasing function, and both $\alpha,\beta$ are
computable in $O(1)$ time. We also assume that $\alpha(\cdot,\infty)=\infty$,
and $\beta$ satisfies $\alpha(\beta(0,\cdot),x)=x$ to match $f$’s condition.

Since the TR condition is a slight generalization of traditional policy
evaluation, it is easy to see that we can solve for minimum-cost policies
using backward induction.

######  Proposition 1 (TR Intuition).

If $C$ is TR, then $C$ satisfies the usual optimality equations. Furthermore,
$\operatorname*{arg\,min}_{\pi\in\Pi^{D}}C_{M}^{\pi}$ can be computed using
backward induction in $O(HS^{2}A)$ time.

Although the TR condition is straightforward, the TSR condition is more
strict. We will see the utility of the TSR condition in Section 4 when
computing Bellman updates. For now, we point out that the TSR condition is not
too restrictive: it is satisfied by many popular criteria studied in the
literature.

######  Proposition 2 (TSR examples).

The following classical constraints can be modeled by a TSR cost constraint.

  1. 1.

_(Expectation Constraints)_ are captured by
$C_{M}^{\pi}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}^{\pi}_{M}\left[\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\right]\leq
B$. We see $C$ is TSR by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}x+y$ and
$\beta(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}xy$.

  2. 2.

_(Almost Sure Constraints)_ are captured by
$C^{\pi}_{M}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1},\\\
\mathbb{P}^{\pi}_{M}[\tau]>0\end{subarray}}\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\leq
B$. We see $C$ is TSR by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}\max(x,y)$ and
$\beta(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}[x>0]y$.

  3. 3.

_(Anytime Constraints)_ are captured by
$C^{\pi}_{M}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{t\in[H]}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1},\\\
\mathbb{P}^{\pi}_{M}[\tau]>0\end{subarray}}\sum_{h=1}^{t}c_{h}(s_{h},a_{h})\leq
B$. We see $C$ is TSR by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}\max(0,\max(x,y))$ and
$\beta(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}[x>0]y$.

######  Remark 1 (Extensions).

Our methods can also handle stochastic costs and infinite discounting. We
defer the details to Appendix E. Moreover, we can handle multiple constraints
using vector-valued criteria so long as the comparison operator is a total
ordering of the vector space.

######  Remark 2 (Limitations).

Our methods cannot handle chance constraints or more than one of our example
constraints. However, this is not a limitation of our framework as the problem
becomes provably inapproximable under said constraints [30, 21].

##  3 Covering Algorithm

In this section, we propose an algorithm to solve (CON). Our approach relies
on converting the original problem into an equivalent covering problem that
can be solved using an unconstrained MDP. This covering MDP is derived using
the key idea of value augmentation.

#### Packing and Covering.

We can view (CON) as a _packing program_ , which wishes to maximize
$V^{\pi}_{M}$ subject to $C^{\pi}_{M}\leq B$. However, we could also tackle
the problem by reversing the objective: attempt to minimize $C^{\pi}_{M}$
subject to $V^{\pi}_{M}\geq V^{*}_{M}$. If (CON) is feasible, then any optimal
solution $\pi$ to this _covering program_ satisfies $V^{\pi}_{M}\geq
V^{*}_{M}$ and $C^{\pi}_{M}\leq B$. Thus, we can solve the original packing
program by solving the covering program.

######  Proposition 3 (Packing-Covering Reduction).

Suppose that
$C^{*}_{M}\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{\pi\in\Pi^{D}}C^{\pi}_{M}\text{
s.t. }V^{\pi}_{M}\geq V^{*}_{M}$. Then, $C^{*}_{M}\leq B\iff
V^{*}_{M}>-\infty$. Furthermore, if $V^{*}_{M}>-\infty$, then,

$\begin{matrix}\operatorname*{arg\,min}_{\pi\in\Pi^{D}}C^{\pi}_{M}\\\
V^{\pi}_{M}\geq
V^{*}_{M}\end{matrix}\;\subseteq\;\begin{matrix}\operatorname*{arg\,max}_{\pi\in\Pi^{D}}V^{\pi}_{M}\\\
C^{\pi}_{M}\leq B\end{matrix}.$ (PC)

Thus, any solution to the covering program is a solution to the packing
program.

We focus on the covering program for several reasons. To optimize the value
recursively, we would need to predict the final cost resulting from
intermediate decisions to ensure feasibility. Generally, such predictions
would require strict assumptions on the cost criteria. By treating the value
as the constraint instead, we only need to assume the cost can be optimized
efficiently. Moreover, values are well understood in RL and are more amenable
to approximation [21]. Thus, the covering program allows us to capture many
criteria, ensure feasibility, and compute accurate value approximations.

#### Value Augmentation.

We can solve the covering program by solving a cost-minimizing MDP $\bar{M}$.
The key idea is to augment the state space with value demands, $(s,v)$. Then,
the agent can recursively reason how to minimize its cost while meeting the
current value demand. If the agent starts at $(s_{0},V^{*}_{M})$, then an
optimal policy for $\bar{M}$ should be a solution to the covering program.

The key invariant we desire is that any feasible policy $\pi$ for $\bar{M}$
should satisfy $\bar{V}^{\pi}_{h}(s,v)\geq v$. To ensure this invariant, we
recall the policy evaluation equations [25]. If $\pi_{h}(s)=a$, then,

$\bar{V}^{\pi}_{h}(s,v)=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\bar{V}^{\pi}_{h+1}(s^{\prime},v_{s^{\prime}}).$ (PE)

For the value invariant to be satisfied, it suffices for the agent to choose
an action $a$ and commit to future value demands $v_{s^{\prime}}$ satisfying,

$r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq v.$
(DEM)

We can view choosing future value demands as part of the agent’s augmented
actions. Then, at any augmented state $(s,v)$, the agent’s augmented action
space includes all $(a,\mathbf{v})\in\mathcal{A}\times\mathbb{R}^{S}$
satisfying (DEM). When $M$ transitions to $s^{\prime}\sim P_{h}(s,a)$, the
agent’s new augmented state should consist of the environment’s new state in
addition to its chosen demand for that state, $(s^{\prime},v_{s^{\prime}})$.
Putting these pieces together yields the definition of the cover MDP,
Definition 2.

######  Definition 2 (Cover MDP).

The _cover MDP_
$\bar{M}\stackrel{{\scriptstyle\text{def}}}{{=}}(\bar{\mathcal{S}},\bar{\mathcal{A}},\bar{P},\bar{c},H)$
where,

  1. 1.

$\bar{\mathcal{S}}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathcal{S}\times\mathcal{V}$
where
$\mathcal{V}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{v\mid\exists\pi\in\Pi^{D},h\in[H+1],\tau_{h}\in\mathcal{H}_{h},\;V^{\pi}_{h}(\tau_{h})=v\right\\}$

  2. 2.

$\bar{\mathcal{A}}_{h}(s,v)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{(a,\mathbf{v})\in\mathcal{A}\times\mathcal{V}^{S}\mid
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq
v\right\\}$.

  3. 3.

$\bar{P}_{h}((s^{\prime},v^{\prime})\mid(s,v),(a,\mathbf{v}))\stackrel{{\scriptstyle\text{def}}}{{=}}P_{h}(s^{\prime}\mid
s,a)[v^{\prime}=v_{s^{\prime}}]$.

  4. 4.

$\bar{c}_{h}((s,v),(a,\mathbf{v}))\stackrel{{\scriptstyle\text{def}}}{{=}}c_{h}(s,a)$.

The objective for $\bar{M}$ is to minimize the cost function
$\bar{C}\stackrel{{\scriptstyle\text{def}}}{{=}}C_{\bar{M}}$ with modified
base case
$\bar{C}_{H+1}^{\pi}(s,v)\stackrel{{\scriptstyle\text{def}}}{{=}}\chi_{\left\\{v\leq
0\right\\}}$.

#### Covering Algorithm.

Importantly, the action space definition ensures the value constraint is
satisfied. Meanwhile, the minimum cost objective ensures optimal cost. So long
as our cost is TR, $\bar{M}$ can be solved using fast RL methods instead of
the brute force computation required for general covering programs. These
properties ensure our method, Algorithm 1, is correct.

Algorithm 1 Reduction to RL

1:$(M,C,B)$

2:$\bar{M},\bar{C}\leftarrow\text{\lx@cref{creftype~refnum}{def: cover-
mdp}}(M,C)$

3:$\pi,\bar{C}^{*}\leftarrow\textsc{Solve}(\bar{M},\bar{C})$

4:if $\bar{C}^{*}_{1}(s_{0},v)>B$ for all $v\in\mathcal{V}$ then

5: return “Infeasible”

6:else

7: return $\pi$

######  Theorem 1 (Reduction).

If _Solve_ is any finite-time MDP solver, then Algorithm 1 correctly solves
(CON) in finite time for any TR cost criterion.

Algorithm 2 Augmented Interaction

1:$\pi$

2:$\bar{s}_{1}=(s_{0},V^{*}_{M})$

3:for $h\leftarrow 1$ to $H$ do

4: $(a,\mathbf{v})\leftarrow\pi_{h}(\bar{s}_{h})$

5: $r_{h}=r_{h}(s,a)$ and $s_{h+1}\sim P_{h}(s_{h},a)$

6: $\bar{s}_{h+1}=(s_{h+1},v_{s_{h+1}})$

######  Remark 3 (Execution).

Given a value-augmented policy $\pi$ output from Algorithm 1, the agent can
execute $\pi$ using Algorithm 2. To compute $V^{*}_{M}$ as the starting value,
it suffices for the agent to compute,

$V^{*}_{M}=\max\left\\{v\in\mathcal{V}\mid\bar{C}^{*}_{1}(s_{0},v)\leq
B\right\\}.$ (1)

This computation can be easily done given $\bar{C}^{*}_{1}(s_{0},\cdot)$ in
$O(|\mathcal{V}|)$ time.

##  4 Fast Bellman Updates

In this section, we present an algorithm to solve $\bar{M}$ from Definition 2
efficiently. Although the Bellman updates can be as hard to solve as the
knapsack problem, we use ideas from knapsack approximation algorithms to
create an efficient method. Our approach exploits (SR) through approximate
dynamic programming on the action space.

Even if $\mathcal{V}$ were small, solving $\bar{M}$ would still be challenging
due to the exponentially large action space. Even a single Bellman update
requires the solution of a constrained optimization problem:

$\begin{split}\bar{C}^{*}_{h}(s,v)=\min_{a,\mathbf{v}}\;&c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{*}\left(s^{\prime},v_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)\\\
\text{s.t.}\;&r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\geq v.\end{split}$ (BU)

Above, we used the fact that
$(s^{\prime},v^{\prime})\in\bar{P}_{h}((s,v),(a,\mathbf{v}))$ iff
$s^{\prime}\in P_{h}(s,a)$ and $v^{\prime}=v_{s^{\prime}}$ to simplify $f$’s
input. Observe that even when each $v_{s^{\prime}}$ only takes on two possible
values, $\\{0,w_{s^{\prime}}\\}$, the optimization above can capture the
minimization version of the knapsack problem, implying that it is NP-hard to
compute.

#### Recursive Approach.

Fortunately, we can use the connection to the Knapsack problem positively to
efficiently approximate the Bellman update. For any fixed
$(s,v)\in\bar{\mathcal{S}}$ and $a\in\mathcal{A}$, we focus on the inner
constrained minimization over $\mathbf{v}$:

$\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S},\\\
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq
v\end{subarray}}f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{*}\left(s^{\prime},v_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)$ (2)

We use (SR) to transform this minimization over $\mathbf{v}$ into a sequential
decision-making problem that decides each $v_{s^{\prime}}$. As above, we can
use the definition of $\bar{P}$ to simplify
$g^{(s,v),(a,\mathbf{v})}_{h}(t,v^{\prime})$ into a function of $t$ alone:

$g^{(s,v),(a,\mathbf{v})}_{h}(t)=\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h}^{(s,v),(a,\mathbf{v})}(t+1)\right).$
(3)

Since $v$ only constrains the valid $(a,\mathbf{v})$ pairs, we can discard $v$
and use the simplified notation $g^{s,a}_{h,\mathbf{v}}(t)$ instead of
$g^{(s,v),(a,\mathbf{v})}_{h}(t)$. It is then clear that we can recursively
optimize the value of $v_{t}$ by focusing on $g^{s,a}_{h,\mathbf{v}}(t)$.

To recursively encode the value constraint, we can record the partial value
$u=r_{h}(s,a)+\sum_{s^{\prime}=1}^{t-1}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}$ that we have accumulated so far. Then, we can check if our
choices for $\mathbf{v}$ satisfied the constraint with the inequality $u\geq
v$. The formal recursion is defined in Definition 3.

######  Definition 3.

For any $h\in[H]$, $s\in\mathcal{S}$, $v\in\mathcal{V}$, and $u\in\mathbb{R}$,
we define, $g^{s,a}_{h,v}(S+1,u)=\chi_{\\{u\geq v\\}}$ and for $t\leq S$,

$g_{h,v}^{s,a}(t,u)=\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,v}^{s,a}(t+1,u+P_{h}(t\mid
s,a)v_{t})\right).$ (DP)

#### Recursive Rounding.

This approach can still be slow due to the exponential number of partial
values $u$ induced. Similarly to the knapsack problem, the key is to round
each input $u$ to ensure fewer subproblems. Unlike the knapsack problem,
however, we do not have an easily computable lower bound on the optimal value.
Thus, we turn to a more aggressive recursive rounding. Since rounding may
cause originally feasible values to violate the demand constraint, we also
relax the demand constraint to $u\geq\kappa(v)$ for some lower bound function
$\kappa$.

######  Definition 4.

Fix a rounding function $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$ and a
lower bound function $\kappa$. For any $h\in[H]$, $s\in\mathcal{S}$,
$v\in\mathcal{V}$, and $u\in\mathbb{R}$, we define,
$\hat{g}^{s,a}_{h,v}(S+1,u)=\chi_{\\{u\geq v\\}}$ and for $t\leq S$,

$\hat{g}_{h,v}^{s,a}(t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),\hat{g}_{h,v}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)v_{t})\right\rfloor_{\mathcal{G}}\right).$ (ADP)

Fortunately, the approximate version behaves similarly to the original. The
main difference is the constraint now ensures the rounded sums are at least
the value lower bound. This is formalized in Lemma 1.

######  Lemma 1.

For any $t\in[S+1]$ and $u\in\mathbb{R}$, we have that,

$\begin{split}\hat{g}^{s,a}_{h,v}(t,u)=\min_{\mathbf{v}\in\mathcal{V}^{S-t+1}}&\;g^{s,a}_{h,\hat{\mathbf{v}}}(t)\\\
\text{s.t.}\quad&\;\hat{\sigma}_{h,\mathbf{v}}^{s,a}(t,u)\geq\kappa(v),\end{split}$
(4)

where
$\hat{\sigma}^{s,a}_{h,\mathbf{v}}(t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\lfloor\left\lfloor
u+P_{h}(t\mid s,a)v_{t}\right\rfloor_{\mathcal{G}}+\ldots+P_{h}(S\mid
s,a)v_{S}\right\rfloor_{\mathcal{G}}$.

To turn this recursion into a usable dynamic programming algorithm, we must
also precompute the inputs to any subcomputation. Unlike in standard RL, this
computation must be done with a forward recursion. The details for the
approximate Bellman update are given in Definition 5.

######  Definition 5 (Approx Bellman).

For any $h\in[H]$, $s\in\mathcal{S}$, and $a\in\mathcal{A}$, we define
$\hat{\mathcal{U}}_{h}^{s,a}(1)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{r_{h}(s,a)\right\\}$
and for any $t\in[S]$,

$\hat{\mathcal{U}}_{h}^{s,a}(t+1)\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{v_{t}\in\mathcal{V}}\bigcup_{u\in\hat{\mathcal{U}}_{h}^{s,a}(t)}\left\\{\left\lfloor
u+P_{h}(t\mid s,a)v_{t}\right\rfloor_{\mathcal{G}}\right\\}.$ (5)

Then, an approximation to the Bellman update can be computed using Algorithm
3.222We use the notation $x,o\leftarrow\min_{x}z(x)$ to say that $x$ is the
minimizer and $o$ the value of the optimization.

Algorithm 3 Approx Bellman Update

1:$(h,s,v,\bar{C}^{*}_{h+1})$

2:for $a\in\mathcal{A}$ do

3: $\hat{g}^{s,a}_{h,v}(S+1,u)\leftarrow\chi_{\\{u\geq v\\}}$ $\forall
u\in\hat{\mathcal{U}}^{s,a}_{h}(S+1)$

4: for $t\leftarrow S$ down to $1$ do

5: for $u\in\hat{\mathcal{U}}^{s,a}_{h}(t)$ do

6: $v_{t,a},\hat{g}^{s,a}_{h,v}(t,u)\leftarrow$ (ADP)

7:$a^{*},\hat{C}^{*}_{h}(s,v)\leftarrow\min_{a\in\mathcal{A}}c_{h}(s,a)+\hat{g}^{s,a}_{h,v}(1,r_{h}(s,a))$

8:return $(a^{*},v_{1,a^{*}},\ldots,v_{S,a^{*}})$ and $\hat{C}^{*}_{h}(s,v)$

######  Proposition 4.

Algorithm 4 runs in $O(HS^{2}A|\mathcal{V}|^{2}\hat{U})$ time, where
$\hat{U}\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{h,s,a}|\hat{U}^{s,a}_{h}|$.
When $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$ and $\kappa$ are the
identity function, Algorithm 4 outputs an optimal solution to $\bar{M}$.

Algorithm 4 Approx Solve

1:$(\bar{M},\bar{C}$)

2:$\hat{C}_{H+1}^{*}(s,v)\leftarrow\chi_{\left\\{v\leq 0\right\\}}$ for all
$(s,v)\in\bar{\mathcal{S}}$

3:for $h\leftarrow H$ down to $1$ do

4: for $(s,v)\in\bar{\mathcal{S}}$ do

5: $\hat{a},\hat{C}_{h}^{*}(s,v)\leftarrow\text{\lx@cref{creftype~refnum}{alg:
approx-bellman}}(h,s,v,\hat{C}^{*}_{h+1})$

6: $\pi_{h}(s,v)\leftarrow\hat{a}$

7:return $\pi$ and $\hat{C}^{*}$

######  Remark 4 (Speedups).

The runtime of our methods can be quadratically improved by rounding the
differences instead of the sums. We defer the details to Appendix E.

##  5 Approximation Algorithms

In this section, we present our approximation algorithms for solving (CON). We
carefully round the value demands over both time and space to induce an
approximate MDP. Solving this approximate MDP with Algorithm 4 yields our
FPTAS.

Although we can avoid exponential-time Bellman updates, the running time of
the approximate Bellman update will still be slow if $|\mathcal{V}|$ is large.
To reduce the complexity, we instead use a smaller set of approximate values
by rounding elements of $|\mathcal{V}|$. By rounding down, we effectively
relax the value-demand constraint. More aggressive rounding not only leads to
smaller augmented state spaces but also to smaller cost policies. The trade-
off is aggressive rounding leads to weaker guarantees on the computed policy’s
value. Thus, it is critical to carefully design the rounding and lower bound
functions to balance this trade-off.

#### Value Approximation.

Given a rounding down function $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$,
we would ideally use the rounded set $\left\\{\left\lfloor
v\right\rfloor_{\mathcal{G}}\mid v\in\mathcal{V}\right\\}$ to form our
approximate state space. To avoid having to compute $\mathcal{V}$ explicitly,
we instead use the rounded superset $\left\\{\left\lfloor
v\right\rfloor_{\mathcal{G}}\mid v\in[v_{min},v_{max}]\right\\}$, where
$v_{min}$ and $v_{max}$ are bounds on the extremal values that we specify
later. To ensure we can use Algorithm 4 to find solutions efficiently, we must
also relax the augmented action space to only include vectors that lead to
feasible subproblems for (ADP). From Lemma 1, we know this is exactly the set
of $(a,\hat{\mathbf{v}})$ for which
$\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))\geq\kappa(v)$.
Combining these ideas yields the new approximate MDP, which is defined in
Definition 6.

######  Definition 6 (Approximate MDP).

Given a rounding function $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$ and
lower bound function $\kappa$, the _approximate MDP_
$\hat{M}\stackrel{{\scriptstyle\text{def}}}{{=}}(\hat{\mathcal{S}},\hat{\mathcal{A}},\hat{P},\hat{c},H)$
where,

  1. 1.

$\hat{\mathcal{S}}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathcal{S}\times\hat{\mathcal{V}}$
where
$\hat{\mathcal{V}}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{\left\lfloor
v\right\rfloor_{\mathcal{G}}\mid v\in[v_{min},v_{max}]\right\\}$.

  2. 2.

$\hat{\mathcal{A}}_{h}(s,\hat{v})\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{(a,\hat{\mathbf{v}})\in\mathcal{A}\times\hat{\mathcal{V}}^{S}\mid\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))\geq\kappa(\hat{v})\right\\}$.

  3. 3.

$\hat{P}_{h}((s^{\prime},\hat{v}^{\prime})\mid(s,\hat{v}),(a,\hat{\mathbf{v}}))\stackrel{{\scriptstyle\text{def}}}{{=}}P_{h}(s^{\prime}\mid
s,a)[\hat{v}^{\prime}=\hat{v}_{s^{\prime}}]$.

  4. 4.

$\hat{c}_{h}((s,\hat{v}),(a,\hat{\mathbf{v}}))\stackrel{{\scriptstyle\text{def}}}{{=}}c_{h}(s,a)$.

The objective for $\hat{M}$ is to minimize the cost function
$\hat{C}\stackrel{{\scriptstyle\text{def}}}{{=}}C_{\hat{M}}$ with modified
base case
$\hat{C}_{H+1}^{\pi}(s,\hat{v})\stackrel{{\scriptstyle\text{def}}}{{=}}\chi_{\left\\{\hat{v}\leq
0\right\\}}$.

We can show that rounding down in Definition 6 achieves our goal of producing
smaller cost policies. This ensures feasibility is even easier to achieve. We
formalize this observation in Lemma 2.

######  Lemma 2 (Optimistic Costs).

For our later choices of $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$ and
$\kappa$, the following holds: for any $h\in[H+1]$ and
$(s,v)\in\bar{\mathcal{S}}$, we have $\hat{C}_{h}^{*}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}_{h}^{*}(s,v)$.

Thus, Algorithm 5 always outputs a policy with better than optimal cost when
the instance is feasible, $V^{*}_{M}>-\infty$. If the instance is infeasible,
all policies have cost larger than $B$ by definition and so Algorithm 5
correctly indicates the instance is infeasible. The remaining question is
whether Algorithm 5 outputs policies having near-optimal value.

#### Time-Space Errors.

To assess the optimality gap of Algorithm 5 policies, we must first explore
the error accumulated by our rounding approach. Rounding each value naturally
accumulates approximation error over time. Rounding the partial values while
running Algorithm 3 accumulates additional error over (state) space. Thus,
solving $\hat{M}$ using Algorithm 4 accumulates error over both time and
space, unlike other approximate methods in RL. As a result, our rounding and
threshold functions will generally depend on both $H$ and $S$.

Algorithm 5 Approximation Scheme

1:$(M,C,B)$

2:Hyperparameters: $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$ and $\kappa$

3:$\hat{M},\hat{C}\leftarrow\text{\lx@cref{creftype~refnum}{def:
approx}}(M,C,\left\lfloor\cdot\right\rfloor_{\mathcal{G}},\kappa)$

4:$\pi,\hat{C}^{*}\leftarrow\text{\lx@cref{creftype~refnum}{alg: approx-
solve}}(\hat{M},\hat{C})$

5:if $\hat{C}^{*}_{1}(s_{0},\hat{v})>B$ for all $\hat{v}\in\hat{\mathcal{V}}$
then

6: return “Infeasible"

7:else

8: return $\pi$

#### Arithmetic Rounding.

Our first approach is to round each value down to its closest element in a
$\delta$-cover. This guarantees that $v-\delta\leq\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq v$. Thus, $\left\lfloor
v\right\rfloor_{\mathcal{G}}$ is an underestimate that is not too far from the
true value. By setting $\delta$ to be inversely proportional to $SH$, we
control the errors over time and space. The lower bound must also be a
function of $S$ since it controls the error over space.

######  Definition 7 (Additive Rounding).

Fix $\epsilon>0$. We define,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\lfloor\frac{v}{\delta}\right\rfloor\delta\text{
and }\kappa(v)\stackrel{{\scriptstyle\text{def}}}{{=}}v-\delta(S+1),$ (6)

where
$\delta\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{\epsilon}{H(S+1)+1}$,
$v_{min}\stackrel{{\scriptstyle\text{def}}}{{=}}-Hr_{max}$, and
$v_{max}\stackrel{{\scriptstyle\text{def}}}{{=}}Hr_{max}$.

######  Theorem 2 (Additive FPTAS).

For any $\epsilon>0$, Algorithm 5 using Definition 7 given any cMDP $M$ and
TSR criteria $C$ either correctly outputs the instance is infeasible, or
produces a policy $\pi$ satisfying $\hat{V}^{\pi}\geq V^{*}_{M}-\epsilon$ in
$O(H^{7}S^{5}Ar_{max}^{3}/\epsilon^{3})$ time. Thus, it is an additive-FPTAS
for the class of cMDPs with polynomial-bounded $r_{max}$ and TSR criteria.

#### Geometric Rounding.

Since the arithmetic approach can be slow when $r_{max}$ is large, we can
instead round values down to their closest power of $1/(1-\delta)$. This
guarantees the number of approximate values needed is upper bounded by a
function of $\log(r_{max})$, which is polynomial in the input size. We choose
a geometric scheme satisfying $v(1-\delta)\leq\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq v$ so that the rounded value is an
underestimate and a relative approximation to the true value. To ensure this
property, we must now require that all rewards are non-negative.

######  Definition 8 (Relative Rounding).

Fix $\epsilon>0$. We define,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}\stackrel{{\scriptstyle\text{def}}}{{=}}v^{min}\left(\frac{1}{1-\delta}\right)^{\left\lfloor\log_{\frac{1}{1-\delta}}{\frac{v}{v^{min}}}\right\rfloor}\text{
and }\kappa(v)\stackrel{{\scriptstyle\text{def}}}{{=}}v(1-\delta)^{S+1},$ (7)

where
$\delta\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{\epsilon}{H(S+1)+1}$,
$v_{min}=p_{min}^{H}r_{min}$, and $v_{max}=Hr_{max}$.

######  Theorem 3 (Relative FPTAS).

For $\epsilon>0$, Algorithm 5 using Definition 8 given any cMDP $M$ and TSR
criteria $C$ either correctly outputs the instance is infeasible, or produces
a policy $\pi$ satisfying $\hat{V}^{\pi}\geq V^{*}_{M}(1-\epsilon)$ in
$O(H^{7}S^{5}A\log\left(r_{max}/r_{min}p_{min}\right)^{3}/\epsilon^{3})$ time.
Thus, it is a relative-FPTAS for the class of cMDPs with non-negative rewards
and TSR criteria.

######  Remark 5 (Assumption Necessity).

We also note the mild reward assumptions we made to guarantee efficiency are
unavoidable. Without reward bounds, (CON) captures the knapsack problem which
does not admit additive approximations. Similarly, without non-negativity,
relative approximations for maximization problems are generally not
computable.

##  6 Conclusions

In this paper, we studied the computational complexity of computing
deterministic policies for CRL problems. Our main contribution was the design
of an FPTAS, Algorithm 5, that solves (CON) for any cMPD and TSR criteria
under mild reward assumptions. In particular, our method is an additive-FPTAS
if the cMDP’s rewards are bounded by a polynomial in the input size, and is a
relative-FPTAS if the cMDP’s rewards are non-negative. We note these
assumptions are necessary for efficient approximation, so our algorithm
achieves the best approximation guarantees possible under worst-case analysis.
Moreover, our algorithmic approach, which uses approximate dynamic programming
over time and the state space, highlights the importance of the TSR condition
in making (CON) tractable. The TSR condition captures the fundamental
structure that renders any cost criteria efficiently approximable, thereby
serves as a unifying theory for constrained deterministic policies. Thus, our
work not only develops the first provably efficient algorithm for (CON) but
also uncovers novel algorithmic techniques and structural insights that serve
as a foundation for truly practical algorithms.

#### Future Work.

Several interesting questions remain unanswered. First, it remains unresolved
whether an FPTAS asymptotically faster than ours can be constructed. Second,
it is unclear whether our TSR condition is necessary for efficient computation
or whether a more general condition could be derived. Lastly, it would be
desirable to design algorithms that can feasibly handle multiple constraints
from Proposition 2. Although computing feasible policies for multiple of these
constraints is NP-hard, there could be interesting special cases that are
approximable efficiently.

## References

  * Alon and Halman [2021] T. Alon and N. Halman.  Automatic generation of fptases for stochastic monotone dynamic programs made easier.  _SIAM Journal on Discrete Mathematics_ , 35(4):2679–2722, 2021.  doi: 10.1137/19M1308633.  URL https://doi.org/10.1137/19M1308633.
  * Altman [1999] E. Altman.  _Constrained Markov Decision Processes_.  Chapman and Hall/CRC, 1999.  doi: 10.1201/9781315140223.
  * Bhalgat et al. [2011] A. Bhalgat, A. Goel, and S. Khanna.  Improved approximation results for stochastic knapsack problems.  In _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’11, page 1647–1665, USA, 2011. Society for Industrial and Applied Mathematics.
  * Bhatia et al. [2021] A. Bhatia, P. Varakantham, and A. Kumar.  Resource constrained deep reinforcement learning.  _Proceedings of the International Conference on Automated Planning and Scheduling_ , 29(1):610–620, 5 2021.  doi: 10.1609/icaps.v29i1.3528.  URL https://ojs.aaai.org/index.php/ICAPS/article/view/3528.
  * Castellano et al. [2022] A. Castellano, H. Min, E. Mallada, and J. A. Bazerque.  Reinforcement learning with almost sure constraints.  In R. Firoozi, N. Mehr, E. Yel, R. Antonova, J. Bohg, M. Schwager, and M. Kochenderfer, editors, _Proceedings of The 4th Annual Learning for Dynamics and Control Conference_ , volume 168 of _Proceedings of Machine Learning Research_ , pages 559–570. PMLR, 6 2022.  URL https://proceedings.mlr.press/v168/castellano22a.html.
  * Coronato et al. [2020] A. Coronato, M. Naeem, G. De Pietro, and G. Paragliola.  Reinforcement learning for intelligent healthcare applications: A survey.  _Artificial Intelligence in Medicine_ , 109:101964, 2020\.  ISSN 0933-3657.  doi: https://doi.org/10.1016/j.artmed.2020.101964.  URL https://www.sciencedirect.com/science/article/pii/S093336572031229X.
  * Dean et al. [2005] B. C. Dean, M. X. Goemans, and J. Vondrák.  Adaptivity and approximation for stochastic packing problems.  In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’05, page 395–404, USA, 2005. Society for Industrial and Applied Mathematics.  ISBN 0898715857.
  * Dolgov and Durfee [2005] D. A. Dolgov and E. H. Durfee.  Stationary deterministic policies for constrained mdps with multiple rewards, costs, and discount factors.  In _IJCAI_ , volume 19, pages 1326–1331, 2005.
  * Fan et al. [2021] C. Fan, C. Zhang, A. Yahja, and A. Mostafavi.  Disaster city digital twin: A vision for integrating artificial and human intelligence for disaster management.  _International Journal of Information Management_ , 56:102049, 2021.  ISSN 0268-4012.  doi: https://doi.org/10.1016/j.ijinfomgt.2019.102049.  URL https://www.sciencedirect.com/science/article/pii/S0268401219302956.
  * Feinberg [2000] E. A. Feinberg.  Constrained discounted markov decision processes and hamiltonian cycles.  _Mathematics of Operations Research_ , 25(1):130–140, 2000.  doi: 10.1287/moor.25.1.130.15210.  URL https://doi.org/10.1287/moor.25.1.130.15210.
  * Frieze and Clarke [1984] A. Frieze and M. Clarke.  Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses.  _European Journal of Operational Research_ , 15(1):100–109, 1984.  ISSN 0377-2217.  doi: https://doi.org/10.1016/0377-2217(84)90053-5.  URL https://www.sciencedirect.com/science/article/pii/0377221784900535.
  * Geißer et al. [2020] F. Geißer, G. Povéda, F. Trevizan, M. Bondouy, F. Teichteil-Königsbuch, and S. Thiébaux.  Optimal and heuristic approaches for constrained flight planning under weather uncertainty.  _Proceedings of the International Conference on Automated Planning and Scheduling_ , 30(1):384–393, Jun. 2020.  doi: 10.1609/icaps.v30i1.6684.  URL https://ojs.aaai.org/index.php/ICAPS/article/view/6684.
  * Halman and Nannicini [2019] N. Halman and G. Nannicini.  Toward breaking the curse of dimensionality: An fptas for stochastic dynamic programs with multidimensional actions and scalar states.  _SIAM Journal on Optimization_ , 29(2):1131–1163, 2019.  doi: 10.1137/18M1208423.  URL https://doi.org/10.1137/18M1208423.
  * Halman et al. [2014] N. Halman, D. Klabjan, C.-L. Li, J. Orlin, and D. Simchi-Levi.  Fully polynomial time approximation schemes for stochastic dynamic programs.  _SIAM Journal on Discrete Mathematics_ , 28(4):1725–1796, 2014.  doi: 10.1137/130925153.  URL https://doi.org/10.1137/130925153.
  * Hong and Williams [2023] S. Hong and B. C. Williams.  An anytime algorithm for constrained stochastic shortest path problems with deterministic policies.  _Artificial Intelligence_ , 316:103846, 2023.  ISSN 0004-3702.  doi: https://doi.org/10.1016/j.artint.2022.103846.  URL https://www.sciencedirect.com/science/article/pii/S0004370222001862.
  * Hong et al. [2021] S. Hong, S. U. Lee, X. Huang, M. Khonji, R. Alyassi, and B. C. Williams.  An anytime algorithm for chance constrained stochastic shortest path problems and its application to aircraft routing.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 475–481, 2021.  doi: 10.1109/ICRA48506.2021.9561229.
  * Khonji et al. [2019] M. Khonji, A. Jasour, and B. Williams.  Approximability of constant-horizon constrained pomdp.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , pages 5583–5590. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.  doi: 10.24963/ijcai.2019/775.  URL https://doi.org/10.24963/ijcai.2019/775.
  * Kolesar [1970] P. Kolesar.  A markovian model for hospital admission scheduling.  _Management Science_ , 16(6):B384–B396, 1970\.  ISSN 00251909, 15265501.  URL http://www.jstor.org/stable/2628725.
  * Li et al. [2018] R. Li, Z. Zhao, Q. Sun, C.-L. I, C. Yang, X. Chen, M. Zhao, and H. Zhang.  Deep reinforcement learning for resource management in network slicing.  _IEEE Access_ , 6:74429–74441, 2018.  doi: 10.1109/ACCESS.2018.2881964.
  * Mao et al. [2016] H. Mao, M. Alizadeh, I. Menache, and S. Kandula.  Resource management with deep reinforcement learning.  In _Proceedings of the 15th ACM Workshop on Hot Topics in Networks_ , HotNets ’16, page 50–56, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450346610.  doi: 10.1145/3005745.3005750.  URL https://doi.org/10.1145/3005745.3005750.
  * McMahan and Zhu [2024] J. McMahan and X. Zhu.  Anytime-constrained reinforcement learning.  In S. Dasgupta, S. Mandt, and Y. Li, editors, _Proceedings of The 27th International Conference on Artificial Intelligence and Statistics_ , volume 238 of _Proceedings of Machine Learning Research_ , pages 4321–4329. PMLR, 02–04 May 2024.  URL https://proceedings.mlr.press/v238/mcmahan24a.html.
  * Paragliola et al. [2018] G. Paragliola, A. Coronato, M. Naeem, and G. De Pietro.  A reinforcement learning-based approach for the risk management of e-health environments: A case study.  In _2018 14th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS)_, pages 711–716, 2018.  doi: 10.1109/SITIS.2018.00114.
  * Paruchuri et al. [2004] P. Paruchuri, M. Tambe, F. Ordonez, and S. Kraus.  Towards a formalization of teamwork with resource constraints.  In _Third International Joint Conference on Autonomous Agents and Multiagent Systems_ , United States, 2004. IEEE Computer Society.  Place of conference:USA.
  * Peng and Shen [2021] H. Peng and X. Shen.  Multi-agent reinforcement learning based resource management in mec- and uav-assisted vehicular networks.  _IEEE Journal on Selected Areas in Communications_ , 39(1):131–141, 2021.  doi: 10.1109/JSAC.2020.3036962.
  * Puterman [1994] M. L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., USA, 1st edition, 1994.  ISBN 0471619779.
  * Taleghan and Dietterich [2018] M. A. Taleghan and T. G. Dietterich.  Efficient exploration for constrained mdps.  In _2018 AAAI Spring Symposium Series_ , 2018.
  * Tsai et al. [2019] Y. L. Tsai, A. Phatak, P. K. Kitanidis, and C. B. Field.  Deep Reinforcement Learning for Disaster Response: Navigating the Dynamic Emergency Vehicle and Rescue Team Dispatch during a Flood.  In _AGU Fall Meeting Abstracts_ , volume 2019, pages NH33B–14, Dec. 2019.
  * Williamson and Shmoys [2011] D. P. Williamson and D. B. Shmoys.  _The Design of Approximation Algorithms_.  Cambridge University Press, USA, 1st edition, 2011.  ISBN 0521195276.
  * Wu et al. [2019] C. Wu, B. Ju, Y. Wu, X. Lin, N. Xiong, G. Xu, H. Li, and X. Liang.  Uav autonomous target search based on deep reinforcement learning in complex disaster scene.  _IEEE Access_ , 7:117227–117245, 2019.  doi: 10.1109/ACCESS.2019.2933002.
  * Xu and Mannor [2011] H. Xu and S. Mannor.  Probabilistic goal markov decision processes.  In _Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Three_ , IJCAI’11, page 2046–2052. AAAI Press, 2011.  ISBN 9781577355151.
  * Yang et al. [2022] S. Yang, S. Khuller, S. Choudhary, S. Mitra, and K. Mahadik.  Correlated Stochastic Knapsack with a Submodular Objective.  In S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, editors, _30th Annual European Symposium on Algorithms (ESA 2022)_ , volume 244 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 91:1–91:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-247-1.  doi: 10.4230/LIPIcs.ESA.2022.91.  URL https://drops.dagstuhl.de/opus/volltexte/2022/17029.

##  Appendix A Proofs for Section 2

###  A.1 Proof of Proposition 1

The proof follows from the standard proof of backward induction [25]. The main
ideas for the proof can also be seen in the proof of Lemma 4 and Lemma 5.

###  A.2 Proof of Proposition 2

###### Proof.

  1. 1.

(Expectation Constraints) We claim that $C_{M}^{\pi}$ captures expectation
constraints. This is immediate as an expectation constraint takes the form
$\mathbb{E}^{\pi}_{M}\left[\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\right]\leq B$ and
by definition
$C_{M}^{\pi}=\mathbb{E}^{\pi}_{M}\left[\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\right]$.
Moreover, the standard policy evaluation equations for deterministic policies
immediately imply,

$C^{\pi}_{h}(\tau_{h})=c_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)C^{\pi}_{h+1}(\tau_{h},a,s^{\prime}).$ (EC)

Thus, (TR) holds. It is also easy to see that
$\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})$ can be computed recursively state-
wise by,

$P_{h}(1\mid
s,a)C_{h+1}^{\pi}(\tau_{h},a,1)+\sum_{s^{\prime}=2}^{S}P_{h}(s^{\prime}\mid
s,a)C_{h+1}^{\pi}(\tau_{h},a,s^{\prime}),$ (8)

and so (SR) holds. The infinity conditions and non-decreasing requirements are
also easy to verify.

  2. 2.

(Almost Sure Constraints) We claim that $C_{M}^{\pi}$ captures almost sure
constraints. This is because that for tabular MDPs,
$\mathbb{P}^{\pi}_{M}[\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\leq B]=1$ if and only
if for all $\tau\in\mathcal{H}_{H+1}$ with $\mathbb{P}^{\pi}_{M}[\tau]>0$ it
holds that $\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\leq B$ if and only if
$C_{M}^{\pi}=\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau]>0\end{subarray}}\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\leq
B$.

Let $c(\tau)=\sum_{h=1}^{H}c_{h}(s_{h},a_{h})$ denote the cost of a full
history $\tau\in\mathcal{H}_{H+1}$ and let
$c_{h:t}(\tau)=\sum_{k=h}^{t}c_{k}(s_{k},a_{k})$ denote the partial cost of
$\tau$ from time $h$ to time $t$. Our choice of $\alpha$ and $\beta$ imply
that,

$C^{\pi}_{h}(\tau_{h})=c_{h}(s,a)+\max_{s^{\prime}\in
P_{h}(s,a)}C^{\pi}_{h+1}(\tau_{h},a,s^{\prime}).$ (ASC)

To show that $C^{\pi}_{M}$ satisfies (TR), we prove for all $h\in[H+1]$ and
all $\tau_{h}\in\mathcal{H}_{h}$ that

$C_{h}(\tau_{h})=\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:H}(\tau).$ (9)

Then, we see that
$C_{1}^{\pi}(s_{0})=\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid
s_{0}]>0\end{subarray}}c_{1:H}(\tau)=\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau]>0\end{subarray}}\sum_{h=1}^{H}c_{h}(s_{h},a_{h})=C^{\pi}_{M}$.
Thus, $C^{\pi}_{M}$ satisfies (TR). Furthermore, it is clear that
$\max_{s^{\prime}\in P_{h}(s,a)}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})$ can be
computed state-recursively by,

$\max(C_{h+1}^{\pi}(\tau_{h},a,1)[P_{h}(1\mid
s,a)>0],\max_{s^{\prime}=2}^{S}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})[P_{h}(s^{\prime}\mid
s,a)>0]),$ (10)

and so $C^{\pi}_{M}$ satisfies (SR). The infinity conditions and non-
decreasing requirements are also easy to verify.

We proceed by induction on $h$.

     * •

(Base Case) For the base case, we consider $h=H+1$. Observe that for any
history $\tau$, we have $c_{H+1:H}(\tau)=0$ since it is an empty sum. Then, by
definition of $C_{M}^{\pi}$, we see that
$C_{H+1}^{\pi}(\tau_{H+1})=0=\max_{\tau}0=\max_{\tau}c_{H+1:H}(\tau)$.

     * •

(Inductive Step) For the inductive step, we consider $h\leq H$. Let
$s=s_{h}(\tau_{h})$ and $a=\pi_{h}(\tau_{h})$. For any
$\tau\in\mathcal{H}_{H+1}$ for which
$\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0$, we can decompose its cost by
$c_{h:H}(\tau)=c_{h}(s,a)+c_{h+1:H}(\tau)$. Since $a$ is fixed, we can remove
$c_{h}(s,a)$ from the optimization to get,

$\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:H}(\tau)=c_{h}(s,a)+\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h+1:H}(\tau).$

Next, we observe by the Markov property that
$\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]=\sum_{s^{\prime}}\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]P_{h}(s^{\prime}\mid
s,a)$. Thus, $\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0$ if and only if there
exists some $s^{\prime}\in P_{h}(s,a)$ satisfying
$\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]>0$. This implies that,

$\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h+1:H}(\tau)=\max_{s^{\prime}\in
P_{h}(s,a)}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]>0\end{subarray}}c_{h+1:H}(\tau).$

By applying the induction hypothesis, we see that,

$\displaystyle\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:H}(\tau)$
$\displaystyle=c_{h}(s,a)+\max_{s^{\prime}\in
P_{h}(s,a)}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]>0\end{subarray}}c_{h+1:H}(\tau)$
$\displaystyle=c_{h}(s,a)+\max_{\begin{subarray}{c}s^{\prime}\in
P_{h}(s,a)\end{subarray}}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})$
$\displaystyle=C_{h}(\tau_{h}).$

The second line used the induction hypothesis and the third line used the
definition of $C^{\pi}_{M}$.

  3. 3.

(Anytime Constraints) We claim that $C_{M}^{\pi}$ captures anytime
constraints. This is because that for tabular MDPs,
$\mathbb{P}^{\pi}_{M}[\forall t\in[H],\;\sum_{h=1}^{t}c_{h}(s_{h},a_{h})\leq
B]=1$ if and only if for all $t\in[H]$ and $\tau\in\mathcal{H}_{H+1}$ with
$\mathbb{P}^{\pi}_{M}[\tau]>0$ it holds that
$\sum_{h=1}^{t}c_{h}(s_{h},a_{h})\leq B$ if and only if
$C^{\pi}_{M}=\max_{t\in[H]}\max_{\tau\in\mathcal{H}_{H+1}:\mathbb{P}^{\pi}_{M}[\tau]>0}\sum_{h=1}^{t}c_{h}(s_{h},a_{h})\leq
B$.

Our choice of $\alpha$ and $\beta$ imply that,

$C^{\pi}_{h}(\tau_{h})=c_{h}(s,a)+\max\left(0,\max_{s^{\prime}\in
P_{h}(s,a)}C^{\pi}_{h+1}(\tau_{h},a,s^{\prime})\right).$ (AC)

To show that $C^{\pi}_{M}$ satisfies (TR), we show that for all $h\in[H+1]$
and all $\tau_{h}\in\mathcal{H}_{h}$ that

$C_{h}(\tau_{h})=\max_{t\geq
h}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:t}(\tau).$ (11)

Then, we see that
$C_{1}^{\pi}(s_{0})=\max_{t\in[H]}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid
s_{0}]>0\end{subarray}}c_{1:t}(\tau)=\max_{t\in[H]}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau]>0\end{subarray}}\allowbreak\sum_{h=1}^{t}c_{h}(s_{h},a_{h})=C^{\pi}_{M}$.
Thus, $C^{\pi}_{M}$ satisfies (TR). Furthermore, it is clear that
$\max(0,\max_{s^{\prime}\in P_{h}(s,a)}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime}))$
can be computed state-recursively by,

$\begin{split}\max\Big{(}\max(0,C_{h+1}^{\pi}(\tau_{h},a,1)[P_{h}(1\mid
s,a)>0])&,\\\
\max(0,\max_{s^{\prime}=2}^{S}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})&[P_{h}(s^{\prime}\mid
s,a)>0])\Big{)},\end{split}$ (12)

and so $C^{\pi}_{M}$ satisfies (SR). The infinity conditions and non-
decreasing requirements are also easy to verify.

We proceed by induction on $h$.

     * •

(Base Case) For the base case, we consider $h=H+1$. Observe that for any
history $\tau$ and $t$, we have $c_{H+1:t}(\tau)=0$ since it is an empty sum.
Then, by definition of $C_{M}^{\pi}$, we see that
$C_{H+1}^{\pi}(\tau_{H+1})=0=\max_{t}\max_{\tau}0=\max_{t}\max_{\tau}c_{H+1:t}(\tau)$333Technically,
there is no $t\in[H]$ satisfying $t\geq H+1$. We instead interpret the $t\geq
h$ condition in the max as over all integers and define the immediate costs to
be $0$ for all future times to simplify the base case..

     * •

(Inductive Step) For the inductive step, we consider $h\leq H$. Let
$s=s_{h}(\tau_{h})$ and $a=\pi_{h}(\tau_{h})$. By separately considering the
case where $t=h$ and $t\geq h+1$ in the $\max_{t\geq h}$, we see that,

$\displaystyle\max_{t\geq
h}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:t}(\tau)$
$\displaystyle=\max\left(\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:h}(\tau),\max_{t\geq
h+1}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h:t}(\tau)\right)$
$\displaystyle=\max\left(c_{h}(s,a),c_{h}(s,a)+\max_{t\geq
h+1}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h+1:t}(\tau)\right)$
$\displaystyle=c_{h}(s,a)+\max\left(0,\max_{t\geq
h+1}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h}]>0\end{subarray}}c_{h+1:t}(\tau)\right)$
$\displaystyle=c_{h}(s,a)+\max\left(0,\max_{t\geq h+1}\max_{s^{\prime}\in
P_{h}(s,a)}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]>0\end{subarray}}c_{h+1:t}(\tau)\right)$
$\displaystyle=c_{h}(s,a)+\max\left(0,\max_{s^{\prime}\in
P_{h}(s,a)}\max_{t\geq
h+1}\max_{\begin{subarray}{c}\tau\in\mathcal{H}_{H+1}:\\\
\mathbb{P}^{\pi}_{M}[\tau\mid\tau_{h},a,s^{\prime}]>0\end{subarray}}c_{h+1:t}(\tau)\right)$
$\displaystyle=c_{h}(s,a)+\max\left(0,\max_{s^{\prime}\in
P_{h}(s,a)}C_{h+1}^{\pi}(\tau_{h},a,s^{\prime})\right)$
$\displaystyle=C_{h}(\tau_{h}).$

The second line used the fact that $c_{h:h}(\tau)=c_{h}(s,a)$ and the
recursive definition of $c_{h:t}(\tau)$. The fourth line used the result
proven for the almost sure case above. The sixth line used the induction
hypothesis. The last line used the definition of $C^{\pi}_{M}$.

∎

##  Appendix B Proofs for Section 3

###  B.1 Helpful Technical Lemmas

Here, we use a different, inductive definition for $\mathcal{V}$ then in the
main text. However, the following lemma shows they are equivalent.

######  Definition 9 (Value Space).

For any $s\in\mathcal{S}$, we define
$\mathcal{V}_{H+1}(s)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{0\right\\}$,
and for any $h\in[H]$,

$\displaystyle\mathcal{V}_{h}(s)\stackrel{{\scriptstyle\text{def}}}{{=}}\displaystyle\bigcup_{a}\bigcup_{\mathbf{v}\in\bigtimes_{s^{\prime}}\mathcal{V}_{h+1}(s^{\prime})}\left\\{r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\right\\}.$ (13)

We define
$\mathcal{V}\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{h,s}\mathcal{V}_{h}(s)$.

######  Lemma 3 (Value Intution).

For all $s\in\mathcal{S}$ and $h\in[H+1]$,

$\mathcal{V}_{h}(s)=\left\\{v\in\mathbb{R}\mid\exists\pi\in\Pi^{D},\tau_{h}\in\mathcal{H}_{h},\;\left(s=s_{h}(\tau_{h})\wedge
V_{h}^{\pi}(\tau_{h})=v\right)\right\\},$ (14)

and $|\mathcal{V}_{h}(s)|\leq A^{\sum_{t=h}^{H}S^{H-t}}$. Thus, $\mathcal{V}$
can be computed in finite time using backward induction.

######  Lemma 4 (Cost).

For any $h\in[H+1]$, $\tau_{h}\in\mathcal{H}_{h}$, and $v\in\mathcal{V}$, if
$s=s_{h}(\tau_{h})$, then,

$\begin{split}\bar{C}_{h}^{*}(s,v)\leq\min_{\pi\in\Pi^{D}}&\;C_{h}^{\pi}(\tau_{h})\\\
\text{s.t.}&\;V_{h}^{\pi}(\tau_{h})\geq v.\end{split}$ (15)

######  Lemma 5 (Value).

Suppose that $\pi\in\Pi^{D}$. For all $h\in[H+1]$ and
$(s,v)\in\bar{\mathcal{S}}$, if $\bar{C}^{\pi}_{h}(s,v)<\infty$, then
$\bar{V}^{\pi}_{h}(s,v)\geq v$.

######  Remark 6 (Technical Subtlety).

Technically, $V_{h}^{\pi}(\tau_{h})$ is only well defined if
$\mathbb{P}^{\pi}_{M}[\tau_{h}]>0$ and all of our arguments technically should
assume this is the case. However, it is standard in MDP theory to define the
policy evaluation equations on non-reachable trajectories using the standard
recursion to simplify proofs, as we have done here. Formally, this is
equivalent to assuming the process starts initially at $\tau_{h}$ instead of
just conditioning on reaching $\tau_{h}$, or defining the values to correspond
to policy evaluation equations directly. This is consistent with the usual
definition when $\mathbb{P}^{\pi}_{M}[\tau_{h}]>0$ but gives it a defined
value also when $\mathbb{P}^{\pi}_{M}[\tau_{h}]=0$. In either case, this
detail only means our recursive definition of $\mathcal{V}$ is a superset
rather than exactly the set of all values as we defined in the main text. This
does not effect the final results since unreachable trajectories do not effect
$\pi$’s overall value in the MDP anyway, and only effects the interpretations
of some intermediate variables.

###  B.2 Proof of Proposition 3

###### Proof.

By definition of $V^{*}_{M}$ and $C^{*}_{M}$,

$\displaystyle V^{*}_{M}>-\infty$
$\displaystyle\iff\exists\pi\in\Pi^{D},\;C^{\pi}_{M}\leq B\wedge
V^{\pi}_{M}\geq V^{*}_{M}$ $\displaystyle\iff C^{*}_{M}\leq B.$

For the second claim, we observe that if $V^{*}_{M}>-\infty$ then by the above
argument any optimal deterministic policy $\pi$ for COVER satisfies
$C_{M}^{\pi}=C^{*}_{M}\leq B$ and $V^{\pi}_{M}\geq V^{*}_{M}$. Thus,
$COVER\subseteq PACK$. ∎

###  B.3 Proof of Lemma 3

###### Proof.

We proceed by induction on $h$. Let $s\in\mathcal{S}$ be arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. In this case, we know that for any
$\pi\in\Pi^{D}$ and any $\tau\in\mathcal{H}_{H+1}$,
$V_{H+1}^{\pi}(\tau_{H+1})=0\in\\{0\\}=\mathcal{V}_{H+1}(s)$ by definition.
Furthermore, $|\mathcal{V}_{H+1}(s)|=1=A^{0}=A^{\sum_{t=H+1}^{H}S^{t}}$.

#### Inductive Step.

For the inductive step, we consider $h\leq H$. In this case, we know that for
any $\pi\in\Pi^{D}$ and any $\tau_{h}\in\mathcal{H}_{h}$, if
$s=s_{h}(\tau_{h})$ and $a=\pi_{h}(\tau_{h})$, then the policy evaluation
equations imply,

$V_{h}^{\pi}(\tau_{h})=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)V_{h+1}^{\pi}(\tau_{h},a,s^{\prime}).$

We know by the induction hypothesis that
$V_{h+1}^{\pi}(\tau_{h},a,s^{\prime})\in\mathcal{V}_{h+1}(s^{\prime})$. Thus,
by (13), $V_{h}^{\pi}(\tau_{h})\in\mathcal{V}_{h}(s)$. Lastly, we see by (13)
and the induction hypothesis that,

$|\mathcal{V}_{h}(s)|\leq
A\prod_{s^{\prime}}|\mathcal{V}_{h+1}(s^{\prime})|\leq
A\prod_{s^{\prime}}A^{\sum_{t=h+1}^{H}S^{H-t}}=A^{1+S\sum_{t=h+1}^{H}S^{H-t}}=A^{\sum_{t=h}^{H}S^{H-t}}.$

This completes the proof. ∎

###  B.4 Proof of Lemma 4

###### Proof.

We proceed by induction on $h$. Let $\tau_{h}\in\mathcal{H}_{h}$ and
$v\in\mathcal{V}$ be arbitrary and suppose that $s=s_{h}(\tau_{h})$. We let
$C^{*}_{h}(\tau_{h},v)$ denote the minimum for the RHS of (15).

#### Base Case.

For the base case, we consider $h=H+1$. Observe that for any $\pi\in\Pi^{D}$,
$V_{H+1}^{\pi}(\tau_{H+1})=0$ by definition. Thus, there exists a
$\pi\in\Pi^{D}$ satisfying $V_{H+1}^{\pi}(\tau_{H+1})\geq v$ if and only if
$v\leq 0$. We also know by definition that any such policy $\pi$ satisfies
$C^{\pi}_{H+1}(\tau_{H+1})=0$ and if no such policy exists
$C^{*}_{H+1}(\tau_{H+1},v)=\infty$ by convention. Therefore, we see that
$C^{*}_{H+1}(\tau_{H+1},v)=\chi_{\left\\{v\leq 0\right\\}}$. Then, by
definition of the base case for $\bar{C}$, it follows that,

$\bar{C}_{H+1}^{*}(s,v)=\chi_{\left\\{v\leq
0\right\\}}=C^{*}_{H+1}(\tau_{H+1},v).$

#### Inductive Step.

For the inductive step, we consider $h\leq H$. If
$C^{*}_{h}(\tau_{h},v)=\infty$, then trivially $\bar{C}^{*}_{h}(s,v)\leq
C^{*}_{h}(\tau_{h},v)$. Instead, suppose that $C^{*}_{h}(\tau_{h},v)<\infty$.
Then, there must exist a feasible $\pi\in\Pi^{D}$ satisfying
$V_{h}^{\pi}(\tau_{h})\geq v$. Let $a^{*}=\pi_{h}(\tau_{h})$. By the policy
evaluation equations, we know that,

$V_{h}^{\pi}(\tau_{h})=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a^{*})V_{h+1}^{\pi}(\tau_{h},a^{*},s^{\prime}).$

For each $s^{\prime}\in\mathcal{S}$, define
$v_{s^{\prime}}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}V_{h+1}^{\pi}(\tau_{h},a^{*},s^{\prime})$
and observe that
$v_{s^{\prime}}^{*}\in\mathcal{V}_{h+1}(s^{\prime})\subseteq\mathcal{V}$ by
Lemma 3. Thus, we see that
$(a^{*},\mathbf{v}^{*})\in\mathcal{A}\times\mathcal{V}^{S}$ and
$r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq v$,
which implies $(a^{*},\mathbf{v}^{*})\in\bar{\mathcal{A}}_{h}(s,v)$.

Since $\pi$ satisfies $V_{h+1}^{\pi}(\tau_{h},a^{*},s^{\prime})\geq
v_{s^{\prime}}^{*}$, it is clear that
$C^{*}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})\leq
C^{\pi}_{h+1}(\tau_{h},a^{*},s^{\prime})$. Thus, the induction hypothesis
implies that $\bar{C}^{*}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})\leq
C^{*}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})\leq
C^{\pi}_{h+1}(\tau_{h},a^{*},s^{\prime})$. The optimality equations for
$\bar{M}$ then imply that,

$\displaystyle\bar{C}^{*}_{h}(s,v)$
$\displaystyle=\min_{(a,\mathbf{v})\in\bar{\mathcal{A}}_{h}(s,v)}c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{*}\left(s^{\prime},v_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a^{*}),\bar{C}_{h+1}^{*}\left(s^{\prime},v_{s^{\prime}}^{*}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a),C_{h+1}^{\pi}\left(\tau_{h},a^{*},s^{\prime}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle=C_{h}^{\pi}(\tau_{h}).$

The first inequality used the fact that
$(a^{*},\mathbf{v}^{*})\in\bar{\mathcal{A}}_{h}(s,v)$. The second inequality
relied on $f$ being non-decreasing and the induction hypothesis. The final
equality used (TR).

Since $\pi$ was an arbitrary feasible policy for the optimization defining
$C^{*}_{h}(\tau_{h},v)$, we see that $\bar{C}_{h}^{*}(s,v)\leq
C^{*}_{h}(\tau_{h},v)$. This completes the proof. ∎

###  B.5 Proof of Lemma 5

###### Proof.

We proceed by induction on $h$. Let $(s,v)\in\bar{\mathcal{S}}$ be arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. By definition and assumption,
$\bar{C}^{\pi}_{H+1}(s,v)=\chi_{\left\\{v\leq 0\right\\}}<\infty$. Thus, it
must be the case that $v\leq 0$ and so by definition
$\bar{V}_{H+1}^{\pi}(s,v)=0\geq v$.

#### Inductive Step.

For the inductive step, we consider $h\leq H$. We decompose
$\pi_{h}(s,v)=(a,\mathbf{v})$ where we know
$(a,\mathbf{v})\in\bar{\mathcal{A}}_{h}(s,v)$ since $\pi$ has finite cost444By
convention, we assume $\min\varnothing=\infty$. Moreover, it must be the case
that for any $s^{\prime}\in\mathcal{S}$ with $P_{h}(s^{\prime}\mid s,a)>0$
that $\bar{C}_{h+1}^{\pi}(s^{\prime},v_{s^{\prime}})<\infty$ otherwise the
property that $f$ outputs $\infty$ when inputted an $\infty$ would imply a
contradiction:

$\displaystyle\bar{C}^{\pi}_{h}(s,v)$
$\displaystyle=c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{\pi}\left(s^{\prime},v_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)$ $\displaystyle=c_{h}(s,a)+f(\ldots,\infty,\ldots)$
$\displaystyle=\infty.$

Thus, the induction hypothesis implies that
$\bar{V}^{\pi}_{h+1}(s^{\prime},v_{s^{\prime}})\geq v_{s^{\prime}}$ for any
such $s^{\prime}\in\mathcal{S}$. By the policy evaluation equations, we see
that,

$\displaystyle\bar{V}^{\pi}_{h}(s,v)$
$\displaystyle=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\bar{V}^{\pi}_{h+1}(s^{\prime},v_{s^{\prime}})$ $\displaystyle\geq
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}$
$\displaystyle\geq v.$

The third line uses the definition of $\bar{\mathcal{A}}_{h}(s,v)$. This
completes the proof. ∎

###  B.6 Proof of Theorem 1

###### Proof.

If $\bar{C}^{*}_{1}(s_{0},v)>B$ for all $v\in\mathcal{V}$, then $C^{*}_{M}>B$
since otherwise we would have $\bar{C}^{*}_{1}(s_{0},v)\leq
C^{*}_{1}(s_{0},v)=C^{*}_{M}\leq B$ by Lemma 4. Thus, if Algorithm 1 outputs
“infeasible” it is correct.

On the other hand, suppose that there exists some $v\in\mathcal{V}$ for which
$\bar{C}^{*}_{1}(s_{0},v)\leq B$. By standard MDP theory, we know that since
$\pi\in\Pi^{D}$ is a solution to $\bar{M}$, it must satisfy the optimality
equations. In particular,
$\bar{C}^{\pi}_{1}(s_{0},v)=\bar{C}^{*}_{1}(s_{0},v)\leq B$. Since
$C^{\pi}_{M}=\bar{C}^{\pi}_{1}(s_{0},v)$555We can view $\bar{C}$ ($\bar{V}$)
as the extension of $C$ ($V$) needed to formally evaluate memory-augmented
policies. Since we consider deterministic policies, it is trivial to convert
any memory-augmented policy into a history-dependent policy that is defined in
the original environment $M$., we see that there exists a $\pi\in\Pi^{D}$ for
which $C^{\pi}_{M}\leq B$ and so $V^{*}_{M}>-\infty$.

Since $V^{*}_{M}$ is the value of some deterministic policy, Lemma 3 implies
that $V^{*}_{M}\in\mathcal{V}$. Thus, Lemma 5 implies that
$V_{1}^{\pi}(s_{0},V^{*}_{M})\geq V^{*}_{M}$ and
$C^{\pi}_{1}(s_{0},V^{*}_{M})\leq C^{*}_{1}(s_{0},V^{*}_{M})\leq B$.
Consequently, running $\pi$ with initial state $\bar{s}_{0}=(s_{0},V^{*}_{M})$
is an optimal solution to (CON). In either case, Algorithm 1 is correct. ∎

##  Appendix C Proofs for Section 4

######  Definition 10.

We define the exact partial sum,

$\sigma^{s,a}_{h,\mathbf{v}}(t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}.$ (16)

######  Observation 1.

We observe that both $\sigma$ and $\hat{\sigma}$ can be computed recursively.
Specifically, $\sigma^{s,a}_{h,\mathbf{v}}(S+1,u)=u$ and
$\sigma^{s,a}_{h,\mathbf{v}}(t,u)=\sigma^{s,a}_{h,\mathbf{v}}(t,u+P_{h}(t\mid
s,a)v_{t})$. Similarly, $\hat{\sigma}^{s,a}_{h,\mathbf{v}}(S+1,u)=u$ and
$\hat{\sigma}^{s,a}_{h,\mathbf{v}}(t,u)=\sigma^{s,a}_{h,\mathbf{v}}(t,\left\lfloor
u+P_{h}(t\mid s,a)v_{t}\right\rfloor_{\mathcal{G}})$.

For completeness, and to assist with other arguments, we also prove the exact
recursion we presented in Definition 3 is correct using Lemma 6.

######  Lemma 6.

For any $t\in[S+1]$ and $u\in\mathbb{R}$, we have that,

$\begin{split}g^{s,a}_{h,v}(t,u)=\min_{\mathbf{v}\in\mathcal{V}^{S-t+1}}&\;g^{s,a}_{h,\mathbf{v}}(t)\\\
\text{s.t.}\quad&\;u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\geq v.\end{split}$ (17)

Moreover,
$\bar{C}^{*}_{h}(s,v)=\min_{a\in\mathcal{A}}c_{h}(s,a)+g_{h,v}^{s,a}(1,r_{h}(s,a))$.

###  C.1 Proof of Lemma 6

###### Proof.

We proceed by induction on $t$.

#### Base Case.

For the base case, we consider $t=S+1$. Since
$\sum_{s^{\prime}=S+1}^{S}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}=0$ is the
empty sum, the condition $u+\sum_{s^{\prime}=S+1}^{S}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\geq v$ is true iff $u\geq v$. Also, for any $\mathbf{v}$,
$g_{h,\mathbf{v}}^{s,a}(S+1)=0$ by definition. Thus, the minimum defining
$g_{h,\mathbf{v}}^{s,a}(S+1,u)$ is $0$ when $u\geq v$ and is $\infty$ due to
infeasibility otherwise. In symbols, $g_{h,v}^{s,a}(S+1,u)=\chi_{\\{u\geq
v\\}}$ as was to be shown.

#### Inductive Step.

For the inductive step, we consider $t\leq S$. We see that,

$\displaystyle g_{h,v}^{s,a}(t,u)$
$\displaystyle=\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t+1}\\\
u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq
v\end{subarray}}g_{h,\mathbf{v}}^{s,a}(t)$
$\displaystyle=\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t+1}\\\
u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq
v\end{subarray}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t}\\\
(u+P_{h}(t\mid s,a)v_{t})+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\geq v\end{subarray}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t}\\\
(u+P_{h}(t\mid s,a)v_{t})+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\geq v\end{subarray}}g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,v}^{s,a}(t+1,u+P_{h}(t\mid
s,a)v_{t})\right)$

The second lined used (SR). The third line split the optimization into the
first decision and the remaining decisions and decomposed the sum in the
constraint. The fourth line used the fact that $\alpha$ is a non-decreasing
function of both its arguments and the fact that the second optimization only
concerns the second argument. The last line used the induction hypothesis.

The observation that
$\min_{a\in\mathcal{A}}c_{h}(s,a)+g_{h,v}^{s,a}(1,r_{h}(s,a))=\bar{C}^{*}_{h}(s,v)$
then follows from the definition of $\bar{\mathcal{A}}_{h}(s,v)$ and (BU):

$\displaystyle\min_{a\in\mathcal{A}}c_{h}(s,a)+g_{h,v}^{s,a}(1,r_{h}(s,a))$
$\displaystyle=\min_{a\in\mathcal{A}}c_{h}(s,a)+\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S}\\\
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s}\geq
v\end{subarray}}g_{h,\mathbf{v}}^{s,a}(1)$
$\displaystyle=\min_{a\in\mathcal{A}}\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S}\\\
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s}\geq
v\end{subarray}}c_{h}(s,a)+g_{h,\mathbf{v}}^{s,a}(1)$
$\displaystyle=\min_{(a,\mathbf{v})\in\bar{\mathcal{A}}_{h}(s,v)}c_{h}(s,a)+g_{h,\mathbf{v}}^{s,a}(1)$
$\displaystyle=\bar{C}^{*}_{h}(s,v).$

∎

###  C.2 Proof of Lemma 1

###### Proof.

We proceed by induction on $t$.

#### Base Case.

For the base case, we consider $t=S+1$. By definition,
$\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(S+1,u)=u$ so the constraint is
satisfied iff $u\geq v$. Since for any $\hat{\mathbf{v}}$,
$\hat{g}_{h,\hat{\mathbf{v}}}^{s,a}(S+1)=0$ by definition, the minimum
defining $\hat{g}_{h,\hat{\mathbf{v}}}^{s,a}(S+1,u)$ is $0$ when $u\geq v$ and
is $\infty$ due to infeasibility otherwise. In symbols,
$\hat{g}_{h,v}^{s,a}(S+1,u)=\chi_{\\{u\geq v\\}}$ as was to be shown.

#### Inductive Step.

For the inductive step, we consider $t\leq S$. We see that,

$\displaystyle\hat{g}_{h,v}^{s,a}(t,u)$
$\displaystyle=\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t+1}\\\
\hat{\sigma}_{h,\mathbf{v}}^{s,a}(t,u)\geq
v\end{subarray}}g_{h,\mathbf{v}}^{s,a}(t)$
$\displaystyle=\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t+1}\\\
\hat{\sigma}_{h,\mathbf{v}}^{s,a}(t,u)\geq
v\end{subarray}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t}\\\
\hat{\sigma}_{h,\mathbf{v}}^{s,a}(t+1,\left\lfloor u+P_{h}(t\mid
s,a)v_{t}\right\rfloor_{\mathcal{G}})\geq
v\end{subarray}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),\min_{\begin{subarray}{c}\mathbf{v}\in\mathcal{V}^{S-t}\\\
\hat{\sigma}_{h,\mathbf{v}}^{s,a}(t+1,\left\lfloor u+P_{h}(t\mid
s,a)v_{t}\right\rfloor_{\mathcal{G}})\geq
v\end{subarray}}g_{h,\mathbf{v}}^{s,a}(t+1)\right)$
$\displaystyle=\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),\hat{g}_{h,v}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)v_{t}\right\rfloor_{\mathcal{G}})\right)$

The second lined used (SR). The third line split the optimization into the
first decision and the remaining decisions and used the recursive definition
of $\hat{\sigma}$ in the constraint. The fourth line used the fact that
$\alpha$ is a non-decreasing function of both its arguments and the fact that
the second optimization only concerns the second argument. The last line used
the induction hypothesis. ∎

###  C.3 Proof of Proposition 4

###### Proof.

The runtime guarantee is easily seen since Algorithm 4 consists of nested
loops. The fact that it computes an optimal solution for $\bar{M}$ absent
rounding or lower bounding follows immediately from Lemma 6. ∎

##  Appendix D Proofs for Section 5

###  D.1 Helpful Technical Lemmas (Additive)

The following claims all assume Definition 7.

######  Observation 2.

For any $v\in\mathbb{R}$,

$v-\delta\leq\left\lfloor v\right\rfloor_{\mathcal{G}}\leq v.$ (18)

######  Lemma 7.

For any $h\in[H]$, $s\in\mathcal{S}$, $a\in\mathcal{A}$,
$\mathbf{v}\in\mathbb{R}^{S}$, $u\in\mathbb{R}$, and $t\in[S+1]$, we have,

$\sigma^{s,a}_{h,\mathbf{v}}(t,u)-(S-t+1)\delta\leq\hat{\sigma}^{s,a}_{h,\mathbf{v}}(t,u)\leq\sigma^{s,a}_{h,\mathbf{v}}(t,u).$
(19)

######  Lemma 8 (Cost).

For any $h\in[H+1]$ and $(s,v)\in\bar{\mathcal{S}}$,
$\hat{C}_{h}^{*}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}_{h}^{*}(s,v)$.

######  Lemma 9 (Approximation).

Suppose that $\pi\in\Pi^{D}$. For all $h\in[H+1]$ and
$(s,\hat{v})\in\hat{\mathcal{S}}$, if $\hat{C}^{\pi}_{h}(s,\hat{v})<\infty$,
then $\hat{V}^{\pi}_{h}(s,\hat{v})\geq\hat{v}-\delta(S+1)(H-h+1)$.

###  D.2 Helpful Technical Lemmas (Relative)

The following claims all assume Definition 8.

######  Observation 3.

For any $v\in\mathbb{R}$,

$v(1-\delta)\leq\left\lfloor v\right\rfloor_{\mathcal{G}}\leq v.$ (20)

######  Lemma 10.

For any $h\in[H]$, $s\in\mathcal{S}$, $a\in\mathcal{A}$,
$\mathbf{v}\in\mathbb{R}^{S}_{\geq 0}$, $u\in\mathbb{R}_{\geq 0}$, and
$t\in[S+1]$, we have,

$\sigma^{s,a}_{h,\mathbf{v}}(t,u)(1-\delta)^{S-t+1}\leq\hat{\sigma}^{s,a}_{h,\mathbf{v}}(t,u)\leq\sigma^{s,a}_{h,\mathbf{v}}(t,u).$
(21)

######  Lemma 11 (Cost).

Suppose all rewards are non-negative. For any $h\in[H+1]$ and
$(s,v)\in\bar{\mathcal{S}}$, $\hat{C}_{h}^{*}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}_{h}^{*}(s,v)$.

######  Lemma 12 (Approximation).

Suppose all rewards are non-negative and $\pi\in\Pi^{D}$. For all $h\in[H+1]$
and $(s,\hat{v})\in\hat{\mathcal{S}}$, if
$\hat{C}^{\pi}_{h}(s,\hat{v})<\infty$, then
$\hat{V}^{\pi}_{h}(s,\hat{v})\geq\hat{v}(1-\delta)^{(S+1)(H-h+1)}$.

###  D.3 Proof of 2

###### Proof.

Using properties of the floor function, we can infer that,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}=\left\lfloor\frac{v}{\delta}\right\rfloor\delta\leq\frac{v}{\delta}\delta=v,$

and,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}=\left\lfloor\frac{v}{\delta}\right\rfloor\delta\geq(\left\lceil\frac{v}{\delta}\right\rceil-1)\delta=\left\lceil\frac{v}{\delta}\right\rceil\delta-\delta\geq
v-\delta.$

∎

###  D.4 Proof of Lemma 7

###### Proof.

We proceed by induction on $t$.

#### Base Case.

For the base case, we consider $t=S+1$. By definition, we have
$\hat{\sigma}_{h,\mathbf{v}}^{s,a}(S+1,u)=u=\sigma_{h,\mathbf{v}}^{s,a}(S+1,u)$.

#### Inductive Step.

For the inductive step, we consider $t\leq S$. We first see that,

$\displaystyle\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t,u)$
$\displaystyle=\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})$
$\displaystyle\leq\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})$
$\displaystyle=\left\lfloor u+P_{h}(t\mid
s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{t}$ $\displaystyle\leq
u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid s,a)\hat{v}_{t}$
$\displaystyle=\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t,u).$

The first inequality used the induction hypothesis and the second inequality
used the fact that $\left\lfloor x\right\rfloor_{\mathcal{G}}\leq x$.

We also see that,

$\displaystyle\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t,u)$
$\displaystyle=\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})$
$\displaystyle\geq\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})-\delta(S-t)$
$\displaystyle=\left\lfloor u+P_{h}(t\mid
s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{t}-\delta(S-t)$ $\displaystyle\geq
u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid s,a)\hat{v}_{t}-\delta(S-t+1)$
$\displaystyle=\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t,u)-\delta(S-t+1).$

The first inequality used the induction hypothesis and the second inequality
used the fact that $\left\lfloor x\right\rfloor_{\mathcal{G}}\geq x-\delta$. ∎

###  D.5 Proof of Lemma 8

###### Proof.

We proceed by induction on $h$. Let $(s,v)\in\bar{\mathcal{S}}$ be arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. Since $\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq v$, we immediately see,

$\hat{C}_{H+1}^{*}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})=\chi_{\left\\{\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq 0\right\\}}\leq\chi_{\left\\{v\leq
0\right\\}}=\bar{C}^{*}_{H+1}(s,v).$

#### Inductive Step.

For the inductive step, we consider $h\leq H$. If
$\bar{C}^{*}_{h}(s,v)=\infty$, then trivially $\hat{C}^{*}_{h}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}^{*}_{h}(s,v)$. Instead, suppose that
$\bar{C}^{*}_{h}(s,v)<\infty$. Let $\pi$ be a solution to the optimality
equations for $\bar{M}$ so that
$\bar{C}_{h}^{\pi}(s,v)=\bar{C}^{*}_{h}(s,v)<\infty$. Since
$\bar{C}^{*}_{h}(s,v)<\infty$, we know that
$(a^{*},\mathbf{v}^{*})=\pi_{h}(s,v)\in\bar{\mathcal{A}}_{h}(s,v)$. By the
definition of $\bar{\mathcal{A}}_{h}(s,v)$, we know that,

$\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a^{*})v_{s^{\prime}}^{*}\geq v\geq\left\lfloor
v\right\rfloor_{\mathcal{G}}.$

For each $s^{\prime}\in\mathcal{S}$, define
$\hat{v}_{s^{\prime}}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\lfloor
v_{s^{\prime}}^{*}\right\rfloor_{\mathcal{G}}$ and recall that
$v_{s^{\prime}}^{*}\in\mathcal{V}$. We first observe that,

$\displaystyle\sigma^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))$
$\displaystyle=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\left\lfloor v_{s^{\prime}}\right\rfloor_{\mathcal{G}}$ $\displaystyle\geq
r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)(v_{s^{\prime}}-\delta)$
$\displaystyle=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}-\delta$
$\displaystyle=\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))-\delta.$

Then by Lemma 7,

$\displaystyle\hat{\sigma}^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))$
$\displaystyle\geq\sigma^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))-\delta
S$
$\displaystyle\geq\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))-\delta(S+1)$
$\displaystyle\geq\left\lfloor v\right\rfloor_{\mathcal{G}}-\delta(S+1)$
$\displaystyle=\kappa(\left\lfloor v\right\rfloor_{\mathcal{G}}).$

Thus, $(a^{*},\hat{\mathbf{v}}^{*})\in\hat{\mathcal{A}}_{h}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})$.

Since $v_{s^{\prime}}^{*}\in\mathcal{V}$, the induction hypothesis implies
that
$\hat{C}^{*}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}}^{*})\leq\bar{C}^{*}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})=\bar{C}^{\pi}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})$.
The optimality equations for $\hat{M}$ then imply that,

$\displaystyle\hat{C}^{*}_{h}(s,\left\lfloor v\right\rfloor_{\mathcal{G}})$
$\displaystyle=\min_{(a,\hat{\mathbf{v}})\in\hat{\mathcal{A}}_{h}(s,v)}c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\hat{C}_{h+1}^{*}\left(s^{\prime},\hat{v}_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a^{*}),\hat{C}_{h+1}^{*}\left(s^{\prime},\hat{v}_{s^{\prime}}^{*}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{\pi}\left(s^{\prime},v^{*}_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle=\bar{C}_{h}^{\pi}(s,v)$
$\displaystyle=\bar{C}_{h}^{*}(s,v).$

The first inequality used the fact that
$(a^{*},\mathbf{v}^{*})\in\hat{\mathcal{A}}_{h}(s,v)$. The second inequality
relied on $f$ being non-decreasing and the induction hypothesis. The
penultimate equality used (TR). This completes the proof. ∎

###  D.6 Proof of Lemma 9

###### Proof.

We proceed by induction on $h$. Let $(s,\hat{v})\in\hat{\mathcal{S}}$ be
arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. By definition and assumption,
$\hat{C}^{\pi}_{H+1}(s,\hat{v})=\chi_{\left\\{\hat{v}\leq 0\right\\}}<\infty$.
Thus, it must be the case that $\hat{v}\leq 0$ and so by definition
$\hat{V}_{H+1}^{\pi}(s,\hat{v})=0\geq\hat{v}$.

#### Inductive Step.

For the inductive step, we consider $h\leq H$. As in the proof of Lemma 5, we
know that
$\pi_{h}(s,v)=(a,\hat{\mathbf{v}})\in\hat{\mathcal{A}}_{h}(s,\hat{v})$ and for
any $s^{\prime}\in\mathcal{S}$ with $P_{h}(s^{\prime}\mid s,a)>0$ that
$\hat{C}_{h+1}^{\pi}(s^{\prime},v_{s^{\prime}})<\infty$. Thus, the induction
hypothesis implies that
$\hat{V}^{\pi}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}})\geq\hat{v}_{s^{\prime}}-\delta(S+1)(H-h)$
for any such $s^{\prime}\in\mathcal{S}$. By the policy evaluation equations,
we see that,

$\displaystyle\hat{V}^{\pi}_{h}(s,\hat{v})$
$\displaystyle=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\hat{V}^{\pi}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}})$ $\displaystyle\geq
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{s^{\prime}}-\delta(S+1)(H-h)$
$\displaystyle=\sigma_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))-\delta(S+1)(H-h)$
$\displaystyle\geq\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))-\delta(S+1)(H-h)$
$\displaystyle\geq\hat{v}-\delta(S+1)-\delta(S+1)(H-h)$
$\displaystyle=\hat{v}-\delta(S+1)(H-h+1).$

The first inequality used the induction hypothesis. The second inequality used
Lemma 7. The third inequality used the fact that by definition of
$\hat{\mathcal{A}}_{h}(s,\hat{v})$ and $\kappa$,
$\hat{\sigma}^{s,a}_{h,\hat{\mathbf{v}}}(1,r_{h}(s,a))\geq\kappa(\hat{v})=\hat{v}-\delta(S+1)$.
This completes the proof. ∎

###  D.7 Proof of Theorem 2

###### Proof.

#### Correctness.

If $\hat{C}^{*}_{1}(s_{0},v)>B$ for all $\hat{v}\in\hat{\mathcal{V}}$, then
$C^{*}_{M}>B$ since otherwise we would have
$\hat{C}^{*}_{1}(s_{0},\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}^{*}_{1}(s_{0},v)\leq C^{*}_{M}\leq B$
by Lemma 8. Thus, if Algorithm 5 outputs “infeasible” it is correct.

On the other hand, suppose that there exists some
$\hat{v}\in\hat{\mathcal{V}}$ for which $\hat{C}^{*}_{1}(s_{0},\hat{v})\leq
B$. By standard MDP theory, we know that since $\pi\in\Pi^{D}$ is a solution
to $\hat{M}$, it must satisfy the optimality equations. In particular,
$\hat{C}^{\pi}_{1}(s_{0},\hat{v})=\hat{C}^{*}_{1}(s_{0},v)\leq B$. As in the
proof of Theorem 1, since $C^{\pi}_{M}=\hat{C}^{\pi}_{1}(s_{0},\hat{v})$, we
see that there exists a $\pi\in\Pi^{D}$ for which $C^{\pi}_{M}\leq B$ and so
$V^{*}_{M}>-\infty$.

Since $V^{*}_{M}$ is the value of some deterministic policy, Lemma 3 implies
that $V^{*}_{M}\in\mathcal{V}$. Thus, Lemma 9 implies that
$\hat{V}_{1}^{\pi}(s_{0},\left\lfloor
V^{*}_{M}\right\rfloor_{\mathcal{G}})\geq\left\lfloor
V^{*}_{M}\right\rfloor_{\mathcal{G}}-\delta(S+1)H\geq
V^{*}_{M}-\delta(1+(S+1)H)=V^{*}_{M}-\epsilon$ and
$\hat{C}^{\pi}_{1}(s_{0},V^{*}_{M})\leq C^{*}_{1}(s_{0},V^{*}_{M})\leq B$.
Consequently, running $\pi$ with initial state
$\bar{s}_{0}=(s_{0},\left\lfloor V^{*}_{M}\right\rfloor_{\mathcal{G}})$ is an
optimal solution to (CON). In either case, Algorithm 5 is correct.

#### Complexity.

For the complexity claim, we observe that the running time of Algorithm 5 is
$O(HS^{2}A|\hat{\mathcal{V}}|^{2}|\hat{\mathcal{U}}|)$. To bound
$|\hat{\mathcal{V}}|$, we observe that the number of integer multiples of
$\delta$ required to capture the range $[-Hr_{max},Hr_{max}]$ is at most
$O(\frac{Hr_{max}}{\delta})=O(H^{2}Sr_{max}/\epsilon)$ by definition of
$\delta$. Moreover,
$|\hat{\mathcal{U}}|=O(|\hat{\mathcal{V}}|+S)=O(|\hat{\mathcal{V}}|)$ for
sufficiently large $\frac{r_{max}}{\epsilon}$.

In particular, we see that the range of the rounded sums defining
$\hat{\mathcal{U}}$ is at widest $[-2Hr_{max}-\delta S,2Hr_{max}]$ since for
any $t+1$ the rounded input is,

$\left\lfloor\left\lfloor r_{h}(s,a)+P_{h}(1\mid
s,a)\hat{\mathbf{v}}_{1}\right\rfloor_{\mathcal{G}}+\ldots+P_{h}(t\mid
s,a)\hat{\mathbf{v}}_{t}\right\rfloor_{\mathcal{G}}\leq
r_{h}(s,a)+\sum_{s^{\prime}=1}^{t}P_{h}(s^{\prime}\mid
s,a)\hat{\mathbf{v}}_{s^{\prime}},$

which is at most $2Hr_{max}$, and,

$\left\lfloor\left\lfloor r_{h}(s,a)+P_{h}(1\mid
s,a)\hat{\mathbf{v}}_{1}\right\rfloor_{\mathcal{G}}+\ldots+P_{h}(t\mid
s,a)\hat{\mathbf{v}}_{t}\right\rfloor_{\mathcal{G}}\geq
r_{h}(s,a)+\sum_{s^{\prime}=1}^{t}P_{h}(s^{\prime}\mid
s,a)\hat{\mathbf{v}}_{s^{\prime}}-\delta t,$

which is at least $-2Hr_{max}-\delta S$. Overall, we see that
$O(|\hat{\mathcal{V}}|^{2}|\hat{\mathcal{U}}|)=O(|\hat{\mathcal{V}}|^{3})=O(H^{6}S^{3}r_{max}^{3}/\epsilon^{3})$
implying that the total run time is
$O(H^{7}S^{5}Ar_{max}^{3}\allowbreak/\epsilon^{3})$ as claimed. ∎

###  D.8 Proof of 3

###### Proof.

Using properties of the floor function, we can infer that,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}=v^{min}\left(\frac{1}{1-\delta}\right)^{\left\lfloor\log_{\frac{1}{1-\delta}}{\frac{v}{v^{min}}}\right\rfloor}\leq
v^{min}\left(\frac{1}{1-\delta}\right)^{\log_{\frac{1}{1-\delta}}{\frac{v}{v^{min}}}}=\frac{v}{v^{min}}v^{min}=v,$

and,

$\left\lfloor
v\right\rfloor_{\mathcal{G}}=v^{min}\left(\frac{1}{1-\delta}\right)^{\left\lfloor\log_{\frac{1}{1-\delta}}{\frac{v}{v^{min}}}\right\rfloor}\geq
v^{min}\left(\frac{1}{1-\delta}\right)^{\log_{\frac{1}{1-\delta}}{\frac{v}{v^{min}}}-1}=v(1-\delta).$

∎

###  D.9 Proof of Lemma 10

###### Proof.

We proceed by induction on $t$.

#### Base Case.

For the base case, we consider $t=S+1$. By definition, we have
$\hat{\sigma}_{h,\mathbf{v}}^{s,a}(S+1,u)=u=\sigma_{h,\mathbf{v}}^{s,a}(S+1,u)$.

#### Inductive Step.

For the inductive step, we consider $t\leq S$. We first see that,

$\displaystyle\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t,u)$
$\displaystyle=\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})$
$\displaystyle\leq\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}})$
$\displaystyle=\left\lfloor u+P_{h}(t\mid
s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{t}$ $\displaystyle\leq
u+\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid s,a)\hat{v}_{t}$
$\displaystyle=\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t,u).$

The first inequality used the induction hypothesis and the second inequality
used the fact that $\left\lfloor x\right\rfloor_{\mathcal{G}}\leq x$.

We also see that,

$\displaystyle\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(t,u)$
$\displaystyle=\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}\left(t+1,\left\lfloor
u+P_{h}(t\mid s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}\right)$
$\displaystyle\geq\sigma_{h,\hat{\mathbf{v}}}^{s,a}\left(t+1,\left\lfloor
u+P_{h}(t\mid
s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}\right)(1-\delta)^{S-t}$
$\displaystyle=\left(\left\lfloor u+P_{h}(t\mid
s,a)\hat{v}_{t}\right\rfloor_{\mathcal{G}}+\sum_{s^{\prime}=t+1}^{S}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{t}\right)(1-\delta)^{S-t}$
$\displaystyle\geq\left((1-\delta)u+(1-\delta)\sum_{s^{\prime}=t}^{S}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{t}\right)(1-\delta)^{S-t}$
$\displaystyle=\sigma_{h,\hat{\mathbf{v}}}^{s,a}(t,u)(1-\delta)^{S-t+1}.$

The first inequality used the induction hypothesis and the second inequality
used the fact that $\left\lfloor x\right\rfloor_{\mathcal{G}}\geq x-\delta$
and the fact that all rewards and values are non-negative allowing us to add a
$(1-\delta)$-factor to the other value demands. ∎

###  D.10 Proof of Lemma 11

###### Proof.

We proceed by induction on $h$. Let $(s,v)\in\bar{\mathcal{S}}$ be arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. Since $\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq v$, we immediately see,

$\hat{C}_{H+1}^{*}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})=\chi_{\left\\{\left\lfloor
v\right\rfloor_{\mathcal{G}}\leq 0\right\\}}\leq\chi_{\left\\{v\leq
0\right\\}}=\bar{C}^{*}_{H+1}(s,v).$

#### Inductive Step.

For the inductive step, we consider $h\leq H$. If
$\bar{C}^{*}_{h}(s,v)=\infty$, then trivially $\hat{C}^{*}_{h}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}^{*}_{h}(s,v)$. Instead, suppose that
$\bar{C}^{*}_{h}(s,v)<\infty$. Let $\pi$ be a solution to the optimality
equations for $\bar{M}$ so that
$\bar{C}_{h}^{\pi}(s,v)=\bar{C}^{*}_{h}(s,v)<\infty$. Since
$\bar{C}^{*}_{h}(s,v)<\infty$, we know that
$(a^{*},\mathbf{v}^{*})=\pi_{h}(s,v)\in\bar{\mathcal{A}}_{h}(s,v)$. By the
definition of $\bar{\mathcal{A}}_{h}(s,v)$, we know that,

$\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a^{*})v_{s^{\prime}}^{*}\geq v\geq\left\lfloor
v\right\rfloor_{\mathcal{G}}.$

For each $s^{\prime}\in\mathcal{S}$, define
$\hat{v}_{s^{\prime}}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\lfloor
v_{s^{\prime}}^{*}\right\rfloor_{\mathcal{G}}$ and recall that
$v_{s^{\prime}}^{*}\in\mathcal{V}$. We first observe that,

$\displaystyle\sigma^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))$
$\displaystyle=r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\left\lfloor v_{s^{\prime}}\right\rfloor_{\mathcal{G}}$ $\displaystyle\geq
r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}(1-\delta)$
$\displaystyle\geq\left(r_{h}(s,a^{*})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)v_{s^{\prime}}\right)(1-\delta)$
$\displaystyle=\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))(1-\delta).$

The second inequality used the fact that all rewards are non-negative. Then by
Lemma 10,

$\displaystyle\hat{\sigma}^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))$
$\displaystyle\geq\sigma^{s,a^{*}}_{h,\hat{\mathbf{v}}^{*}}(1,r_{h}(s,a^{*}))(1-\delta)^{S}$
$\displaystyle\geq\sigma^{s,a^{*}}_{h,\mathbf{v}^{*}}(1,r_{h}(s,a^{*}))(1-\delta)^{S+1}$
$\displaystyle\geq\left\lfloor v\right\rfloor_{\mathcal{G}}(1-\delta)^{S+1}$
$\displaystyle=\kappa(\left\lfloor v\right\rfloor_{\mathcal{G}}).$

Thus, $(a^{*},\hat{\mathbf{v}}^{*})\in\hat{\mathcal{A}}_{h}(s,\left\lfloor
v\right\rfloor_{\mathcal{G}})$.

Since $v_{s^{\prime}}^{*}\in\mathcal{V}$, the induction hypothesis implies
that
$\hat{C}^{*}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}}^{*})\leq\bar{C}^{*}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})=\bar{C}^{\pi}_{h+1}(s^{\prime},v_{s^{\prime}}^{*})$.
The optimality equations for $\hat{M}$ then imply that,

$\displaystyle\hat{C}^{*}_{h}(s,\left\lfloor v\right\rfloor_{\mathcal{G}})$
$\displaystyle=\min_{(a,\hat{\mathbf{v}})\in\hat{\mathcal{A}}_{h}(s,v)}c_{h}(s,a)+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\hat{C}_{h+1}^{*}\left(s^{\prime},\hat{v}_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a)}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a^{*}),\hat{C}_{h+1}^{*}\left(s^{\prime},\hat{v}_{s^{\prime}}^{*}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle\leq
c_{h}(s,a^{*})+f\left(\left(P_{h}(s^{\prime}\mid
s,a),\bar{C}_{h+1}^{\pi}\left(s^{\prime},v^{*}_{s^{\prime}}\right)\right)_{s^{\prime}\in
P_{h}(s,a^{*})}\right)$ $\displaystyle=\bar{C}_{h}^{\pi}(s,v)$
$\displaystyle=\bar{C}_{h}^{*}(s,v).$

The first inequality used the fact that
$(a^{*},\mathbf{v}^{*})\in\hat{\mathcal{A}}_{h}(s,v)$. The second inequality
relied on $f$ being non-decreasing and the induction hypothesis. The
penultimate equality used (TR).

This completes the proof. ∎

###  D.11 Proof of Lemma 12

###### Proof.

We proceed by induction on $h$. Let $(s,\hat{v})\in\hat{\mathcal{S}}$ be
arbitrary.

#### Base Case.

For the base case, we consider $h=H+1$. By definition and assumption,
$\hat{C}^{\pi}_{H+1}(s,\hat{v})=\chi_{\left\\{\hat{v}\leq 0\right\\}}<\infty$.
Thus, it must be the case that $\hat{v}\leq 0$ and so by definition
$\hat{V}_{H+1}^{\pi}(s,\hat{v})=0\geq\hat{v}$.

#### Inductive Step.

For the inductive step, we consider $h\leq H$. As in the proof of Lemma 5, we
know that
$\pi_{h}(s,v)=(a,\hat{\mathbf{v}})\in\hat{\mathcal{A}}_{h}(s,\hat{v})$ and for
any $s^{\prime}\in\mathcal{S}$ with $P_{h}(s^{\prime}\mid s,a)>0$ that
$\hat{C}_{h+1}^{\pi}(s^{\prime},v_{s^{\prime}})<\infty$. Thus, the induction
hypothesis implies that
$\hat{V}^{\pi}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}})\geq\hat{v}_{s^{\prime}}(1-\delta)^{(S+1)(H-h)}$
for any such $s^{\prime}\in\mathcal{S}$. By the policy evaluation equations,
we see that,

$\displaystyle\hat{V}^{\pi}_{h}(s,\hat{v})$
$\displaystyle=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\hat{V}^{\pi}_{h+1}(s^{\prime},\hat{v}_{s^{\prime}})$ $\displaystyle\geq
r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a)\hat{v}_{s^{\prime}}(1-\delta)^{(S+1)(H-h)}$
$\displaystyle\geq\sigma_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))(1-\delta)^{(S+1)(H-h)}$
$\displaystyle\geq\hat{\sigma}_{h,\hat{\mathbf{v}}}^{s,a}(1,r_{h}(s,a))(1-\delta)^{(S+1)(H-h)}$
$\displaystyle\geq\hat{v}(1-\delta)^{S+1}(1-\delta)^{(S+1)(H-h)}$
$\displaystyle=\hat{v}(1-\delta)^{(S+1)(H-h+1)}.$

The first inequality used the induction hypothesis. The second inequality used
the fact that the rewards are non-negative. The third inequality used Lemma
10. The fourth inequality used the fact that by definition of
$\hat{\mathcal{A}}_{h}(s,\hat{v})$ and $\kappa$,
$\hat{\sigma}^{s,a}_{h,\hat{\mathbf{v}}}(1,r_{h}(s,a))\geq\kappa(\hat{v})=\hat{v}(1-\delta)^{S+1}$.

This completes the proof. ∎

###  D.12 Proof of Theorem 3

###### Proof.

#### Correctness.

If $\hat{C}^{*}_{1}(s_{0},v)>B$ for all $\hat{v}\in\hat{\mathcal{V}}$, then
$C^{*}_{M}>B$ since otherwise we would have
$\hat{C}^{*}_{1}(s_{0},\left\lfloor
v\right\rfloor_{\mathcal{G}})\leq\bar{C}^{*}_{1}(s_{0},v)\leq C^{*}_{M}\leq B$
by Lemma 11. Thus, if Algorithm 5 outputs “infeasible” it is correct.

On the other hand, suppose that there exists some
$\hat{v}\in\hat{\mathcal{V}}$ for which $\hat{C}^{*}_{1}(s_{0},\hat{v})\leq
B$. By standard MDP theory, we know that since $\pi\in\Pi^{D}$ is a solution
to $\hat{M}$, it must satisfy the optimality equations. In particular,
$\hat{C}^{\pi}_{1}(s_{0},\hat{v})=\hat{C}^{*}_{1}(s_{0},v)\leq B$. As in the
proof of Theorem 1, since $C^{\pi}_{M}=\hat{C}^{\pi}_{1}(s_{0},\hat{v})$, we
see that there exists a $\pi\in\Pi^{D}$ for which $C^{\pi}_{M}\leq B$ and so
$V^{*}_{M}>-\infty$.

Since $V^{*}_{M}$ is the value of some deterministic policy, Lemma 3 implies
that $V^{*}_{M}\in\mathcal{V}$. Thus, Lemma 12 implies that
$\hat{V}_{1}^{\pi}(s_{0},\left\lfloor
V^{*}_{M}\right\rfloor_{\mathcal{G}})\geq\left\lfloor
V^{*}_{M}\right\rfloor_{\mathcal{G}}(1-\delta)^{(S+1)H}\geq
V^{*}_{M}(1-\delta)^{(S+1)H+1}=V^{*}_{M}(1-\frac{\epsilon}{(S+1)H+1})^{(S+1)H+1}\geq
V^{*}_{M}(1-\epsilon)$ and $\hat{C}^{\pi}_{1}(s_{0},V^{*}_{M})\leq
C^{*}_{1}(s_{0},V^{*}_{M})\leq B$. Consequently, running $\pi$ with initial
state $\bar{s}_{0}=(s_{0},\left\lfloor V^{*}_{M}\right\rfloor_{\mathcal{G}})$
is an optimal solution to (CON). In either case, Algorithm 5 is correct.

#### Complexity.

For the complexity claim, we observe that the running time of Algorithm 5 is
$O(HS^{2}A|\hat{\mathcal{V}}|^{2}|\hat{\mathcal{U}}|)$. To bound
$|\hat{\mathcal{V}}|$, we observe that the number of $vmin$-scaled powers of
$1/(1-\delta)$ required to capture the range $[0,Hr_{max}]$ is at most one
plus the largest power needed, which is

$\displaystyle O(\log_{1/(1-\delta)}(\frac{Hr_{max}}{v_{min}}))$
$\displaystyle=O(\log(\frac{Hr_{max}}{v_{min}})/\log(1/(1-\delta)))$
$\displaystyle=O(\log(\frac{Hr_{max}}{v_{min}})/\delta)$
$\displaystyle=O(\log(HS\frac{Hr_{max}}{p_{min}^{H}r_{min}})/\epsilon)$
$\displaystyle=O(H^{2}S\log(\frac{r_{max}}{p_{min}r_{min}})/\epsilon),$

by definition of $\delta$ and the fact that
$\log(\frac{1}{1-\delta})=-\log(1-\delta)\geq-\log(e^{-\delta})=\delta$.
Moreover, $|\hat{\mathcal{U}}|=O(|\hat{\mathcal{V}}|)$.

We see that the range of the rounded sums is at widest $[0,2Hr_{max}]$ since
for any $t+1$ rounding non-negative sums is at least $0$ and,

$\left\lfloor\left\lfloor r_{h}(s,a)+P_{h}(1\mid
s,a)\hat{\mathbf{v}}_{1}\right\rfloor_{\mathcal{G}}+\ldots+P_{h}(t\mid
s,a)\hat{\mathbf{v}}_{t}\right\rfloor_{\mathcal{G}}\leq
r_{h}(s,a)+\sum_{s^{\prime}=1}^{t}P_{h}(s^{\prime}\mid
s,a)\hat{\mathbf{v}}_{s^{\prime}},$

which is at most $2Hr_{max}$. Then, the same analysis from before shows that
the number of scaled powers of $1/(1-\delta)$ needed to cover this interval is
$O(|\hat{\mathcal{V}}|)$. Thus, we see that
$O(|\hat{\mathcal{V}}|^{2}|\hat{\mathcal{U}}|)=O(|\hat{\mathcal{V}}|^{3})=O(H^{6}S^{3}\log(\frac{r_{max}}{p_{min}r_{min}})^{3}/\epsilon^{3})$
implying that the total run time is
$O(H^{7}S^{5}A\log(\frac{r_{max}}{p_{min}r_{min}})^{3}/\epsilon^{3})$ as
claimed. ∎

##  Appendix E Extensions

###  E.1 Stochastic Costs

Suppose each cost $c_{h}(s,a)$ is replaced with a cost distribution
$C_{h}(s,a)$. Here, we consider finitely supported cost distributions whose
supports are at most $m\in\mathbb{N}$. Then, instead of the agent occurring
cost $c_{h}(s,a)$ upon taking action $a$ in state $s$ at time $h$, the agent
occurs a random cost $c_{h}\sim C_{h}(s,a)$. Generally, this necessitates
histories be cost dependent, and so the policy evaluation equations become,

$V_{h}^{\pi}(\tau_{h})=r_{h}(s,a)+\sum_{c^{\prime},s^{\prime}}C_{h}(c^{\prime}\mid
s,a)P_{h}(s^{\prime}\mid s,a)V_{h+1}^{\pi}(\tau_{h},a,c^{\prime},s^{\prime}).$
(CPE)

#### Cover MDP.

This implicitly changes the definition of $\mathcal{V}$ since the histories
considered in the definition must now include cost history. Since the cost
distributions are finitely supported, $\mathcal{V}$ remains a finite set. The
main difference for $\bar{M}$ is that the future value demands must depend on
both the immediate cost and the next state. This slightly changes the action
space:

$\bar{\mathcal{A}}_{h}(s,v)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{(a,\mathbf{v})\in\mathcal{A}\times\mathcal{V}^{m\times
S}\mid r_{h}(s,a)+\sum_{c^{\prime},s^{\prime}}C_{h}(c^{\prime}\mid
s,a)P_{h}(s^{\prime}\mid s,a)v_{c^{\prime},s^{\prime}}\geq v\right\\}.$

#### Bellman Updates.

In order to solve $\bar{M}$ using Algorithm 4, we must extend the definition
of TSR to also be recursive in the immediate costs. The key difference of the
_TSRC_ condition is that $g$’s recursion is now two dimensional.

######  Definition 11 (TSRC).

We call a criterion $C$ _time-space-cost-recursive_ (TSRC) if
$C_{M}^{\pi}=C_{1}^{\pi}(s_{0})$ where $C_{H+1}^{\pi}(\cdot)=\mathbf{0}$ and
for any $h\in[H]$ and $\tau_{h}\in\mathcal{H}_{h}$ letting $s=s_{h}(\tau_{h})$
and $a=\pi_{h}(\tau_{h})$,

$C_{h}^{\pi}(\tau_{h})=c_{h}(s,a)+f\left(\left(C_{h}(c^{\prime}\mid
s,a),P_{h}(s^{\prime}\mid
s,a),C_{h+1}^{\pi}\left(\tau_{h},a,c^{\prime},s^{\prime}\right)\right)_{c^{\prime},s^{\prime}}\right).$
(22)

In the above, $c^{\prime}\in C_{h}(s,a)$ and $s^{\prime}\in P_{h}(s,a)$. We
now require that $f$ be computable in $O(mS)$ time. We also require that the
$f$ term above is equal to $g_{h}^{\tau_{h},a}(1,1)$, where,
$g_{h}^{\tau_{h},a}(m+1,1)=0$,
$g_{h}^{\tau_{h},a}(k,S+1)=g_{h}^{\tau_{h},a}(k+1,1)$, and,

$g_{h}^{\tau_{h},a}(k,t)=\alpha\left(\beta\left(C_{h}(c_{k}\mid
s,a),P_{h}(t\mid
s,a),C_{h+1}^{\pi}\left(\tau_{h},a,t\right)\right),g_{h}^{\tau_{h},a}(k,t+1)\right).$
(23)

In the above, we assume $c_{k}$ is the $k$th supported cost of $C_{h}(s,a)$.
Again, both $\alpha,\beta$ can be computed in $O(1)$ time, but now
$\alpha(\beta(y,\cdot),x)=x$ whenever $0\in y$.

Our examples from before also carry over to the stochastic cost setting.

######  Proposition 5 (TSCR examples).

The following classical constraints can be modeled by a TSCR cost constraint.

  1. 1.

_(Expectation Constraints)_ We capture these constraints by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}x+y$ and
$\beta(x,y,z)\stackrel{{\scriptstyle\text{def}}}{{=}}xyz$.

  2. 2.

_(Almost Sure Constraints)_ We capture these constraints by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}\max(x,y)$ and
$\beta(x,y,z)\stackrel{{\scriptstyle\text{def}}}{{=}}[x>0\wedge y>0]z$.

  3. 3.

_(Anytime Constraints)_ We capture these constraints by defining
$\alpha(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}\max(0,\allowbreak\max(x,y))$
and $\beta(x,y,z)\stackrel{{\scriptstyle\text{def}}}{{=}}[x>0\wedge y>0]z$.

We can then modify our approximate recursion from before.

######  Definition 12.

We define,
$\hat{g}^{s,a}_{h,v}(m+1,1,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\chi_{\\{u\geq
v\\}}$,
$\hat{g}^{s,a}_{h,v}(k,S+1,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\hat{g}^{s,a}_{h,v}(k+1,1,u)$
and for $t\leq S$,

$\begin{split}\hat{g}_{h,\hat{v}}^{s,a}(k,t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{v_{k,t}\in\mathcal{V}}\alpha\Big{(}\beta\left(C_{h}(c_{k}\mid
s,a),P_{h}(t\mid s,a),\bar{C}_{h+1}^{*}\left(t,v_{k,t}\right)\right),\\\
\hat{g}_{h,v}^{s,a}\left(k,t+1,\left\lfloor u+C_{h}(c_{k}\mid s,a)P_{h}(t\mid
s,a)v_{k,t}\right\rfloor_{\mathcal{G}}\right)\Big{)}.\end{split}$ (24)

#### Approximation.

Lastly, our rounding now occur error over time, space, and cost. Thus, we
simply need to slightly modify our rounding functions. The main change is we
use
$\delta\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{\epsilon}{H(mS+1)+1}$. We
also further relax our lower bounds to
$\kappa(v)\stackrel{{\scriptstyle\text{def}}}{{=}}v-\delta(mS+1)$ and
$\kappa\stackrel{{\scriptstyle\text{def}}}{{=}}v(1-\delta)^{mS+1}$
respectively. Our running times correspondingly will have $m^{3}$ terms now.

###  E.2 Infinite Discounting

#### Approximations.

Since we focus on approximation algorithms, the infinite discounted case can
be immediately handled by using the idea of effective horizon. We can treat
the problem as a finite horizon problem where the finite horizon $H$ defined
so that $\sum_{h=H}^{\infty}\gamma^{h-1}r_{max}\leq\epsilon^{\prime}$. By
choosing $\epsilon^{\prime}$ and $\epsilon$ small enough, we can get
traditional value approximations. The discounting also ensures the effective
horizon $H$ is polynomially sized implying efficient computation. We just need
to assume that $0$-cost actions are always available so that the policy can
guarantee feasibility after the effective horizon has passed.

#### Hardness.

We also note that all of the standard hardness results concerning
deterministic policy computation carries over to the infinite discounting case
even if all quantities are stationary.

###  E.3 Faster Approximations

We can significantly improve the running time of our FPTAS. The main guarantee
is given in Corollary 1. They key step is to modify Algorithm 3 to use the
differences instead of the sums. It is easy to see that this is equivalent
since,

$r_{h}(s,a)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\geq v\iff
v-\sum_{s^{\prime}}P_{h}(s^{\prime}\mid s,a)v_{s^{\prime}}\leq r_{h}(s,a).$

Since rounding down the differences make them larger, it becomes harder to be
below $r_{h}(s,a)$. Consequently, we now interpret $\kappa$ as an upper bound
for $r_{h}(s,a)$ instead of a lower bound on $v$ The approximate dynamic
programming method based on differences can be seen in Definition 13.

######  Definition 13.

Fix a rounding down function $\left\lfloor\cdot\right\rfloor_{\mathcal{G}}$
and upper bound function $\kappa$. For any $h\in[H]$, $s\in\mathcal{S}$,
$v\in\mathcal{V}$, and $u\in\mathbb{R}$, we define,
$\hat{g}^{s,a}_{h,v}(S+1,u)=\chi_{\\{u\leq\kappa(r_{h}(s,a))\\}}$ and for
$t\leq S$,

$\hat{g}_{h}^{s,a}(t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{v_{t}\in\mathcal{V}}\alpha\left(\beta\left(P_{h}(t\mid
s,a),\bar{C}_{h+1}^{*}\left(t,v_{t}\right)\right),\hat{g}_{h}^{s,a}(t+1,\left\lfloor
u-P_{h}(t\mid s,a)v_{t})\right\rfloor_{\mathcal{G}}\right).$ (DIF)

The recursion is nearly identical to the originally, and unsurprisingly, it
retains the same theoretical guarantees but in the reverse order. The
guarantees can be seen in Lemma 13, which is straightforward to prove
following the approach in the proof of Lemma 1.

######  Lemma 13.

For any $t\in[S+1]$ and $u\in\mathbb{R}$, we have that,

$\begin{split}\hat{g}^{s,a}_{h}(t,u)=\min_{\mathbf{v}\in\mathcal{V}^{S-t+1}}&\;\hat{g}^{s,a}_{h,\hat{\mathbf{v}}}(t)\\\
\text{s.t.}\quad&\;\tilde{\sigma}_{h,\mathbf{v}}^{s,a}(t,u)\leq\kappa(r_{h}(s,a)),\end{split}$
(25)

where
$\tilde{\sigma}^{s,a}_{h,\mathbf{v}}(t,u)\stackrel{{\scriptstyle\text{def}}}{{=}}\left\lfloor\left\lfloor
u-P_{h}(t\mid s,a)v_{t}\right\rfloor_{\mathcal{G}}-\ldots-P_{h}(S\mid
s,a)v_{S}\right\rfloor_{\mathcal{G}}$.

The difference version so far does not help us get faster algorithms. The key
is in how we use it. Since the base case of the recursion is $r_{h}(s,a)$ and
not $v$, we can compute the approximate bellman update for all $v$’s
simultaneously. This ends up saving us a factor of $|\mathcal{V}|$ that we had
in the original Algorithm 4. The new algorithm is defined in Algorithm 6. The
inputs to the recursion are define in Definition 14.

Algorithm 6 Approx Solve

1:$(\bar{M},\bar{C}$)

2:$\hat{C}_{H+1}^{*}(s,v)\leftarrow\chi_{\left\\{v\leq 0\right\\}}$ for all
$(s,v)\in\bar{\mathcal{S}}$

3:for $h\leftarrow H$ down to $1$ do

4: for $s\in\mathcal{S}$ do

5: for $a\in\mathcal{A}$ do

6: $\hat{g}^{s,a}_{h}(S+1,u)\leftarrow\chi_{\\{u\leq\kappa(r_{h}(s,a))\\}}$
$\forall u\in\hat{\mathcal{U}}_{h}^{s,a}$

7: for $t\leftarrow S$ down to $1$ do

8: for $u\in\hat{\mathcal{U}}_{h}^{s,a}$ do

9: $\hat{v}_{t,a}\hat{g}_{h}^{s,a}(t,u)\leftarrow\eqref{equ: difference-
recursion}$

10: for $v\in\mathcal{V}$ do

11:
$a^{*},\hat{C}^{*}_{h}(s,v)\leftarrow\min_{a\in\mathcal{A}}c_{h}(s,a)+\hat{g}^{s,a}_{h}(1,v)$

12: $\pi_{h}(s,v)\leftarrow a^{*}$

13:return $\pi$ and $\hat{C}^{*}$

######  Definition 14.

For any $h\in[H]$, $s\in\mathcal{S}$, and $a\in\mathcal{A}$, we define
$\hat{\mathcal{U}}_{h}^{s,a}(1)\stackrel{{\scriptstyle\text{def}}}{{=}}\mathcal{V}$
and for any $t\in[S]$,

$\hat{\mathcal{U}}_{h}^{s,a}(t+1)\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{v_{t}\in\mathcal{V}}\bigcup_{\hat{\sigma}\in\hat{\mathcal{U}}_{h}^{s,a}(t)}\left\\{\left\lfloor\hat{\sigma}-P_{h}(t\mid
s,a)v_{t}\right\rfloor_{\mathcal{G}}\right\\}.$ (26)

######  Proposition 6.

The running time of Algorithm 6 is $O(HS^{2}A|\mathcal{V}|\hat{\sigma})$.

######  Corollary 1 (Running Time Improvements).

Using Algorithm 6, the running time of our additive-FPTAS becomes
$O(H^{5}S^{4}Ar_{max}^{2}/\epsilon^{2})$, and the running time of our
relative-FPTAS becomes
$O(H^{5}S^{4}A\allowbreak\log(\frac{r_{max}}{r_{min}p_{min}})^{2}/\epsilon^{2})$

#### Approximation Details.

Although the running times our clear from removing the factor of $|\hat{V}|$,
we need to slightly alter our approximation schemes for this to work. First,
we need to use
$\kappa(r_{h}(s,a))\stackrel{{\scriptstyle\text{def}}}{{=}}r_{h}(s,a)+\delta$
for the additive approximation. The proof from before goes through almost
identically.

However, for the relative approximation, no choice of upper bound can ensure
enough feasibility. Thus, we simply use
$\kappa(r_{h}(s,a))\stackrel{{\scriptstyle\text{def}}}{{=}}r_{h}(s,a)$ and
apply a different analysis. We also note that technically, differences can
become negative. To deal with this the relative rounding function should
simply send any negative number to $0$:
$\left\lfloor-x\right\rfloor_{\mathcal{G}}\stackrel{{\scriptstyle\text{def}}}{{=}}0$.
The analysis is mostly the same, but the feasibility statement must be
slightly modified.

######  Lemma 14.

Suppose all rewards are non-negative. For any $h\in[H+1]$ and
$(s,v)\in\bar{\mathcal{S}}$, $\hat{C}_{h}^{*}(s,\left\lfloor
v(1-\delta)^{H-h+1}\right\rfloor_{\mathcal{G}})\leq\bar{C}_{h}^{*}(s,v)$.

The idea is that since no fixed upper bound can capture arbitrary input
values, we simply input relative values. Then, the feasibility part of Lemma
11 goes through as before. The proofs mostly remain the same, but the rounding
must again change. We must now start at the smaller $v_{min}$ that is the
original $v_{min}$ scaled by a factor of $(1-\delta)^{H}$ to ensure that
$\left\lfloor V^{*}_{M}(1-\delta)^{H}\right\rfloor$ is in $\hat{V}$. This
makes $\hat{V}$ larger, but not by too much as we argued in previous analyses.