Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
Authors: Jeremy McMahan
Venue: NeurIPS 2024 poster (2024)
Keywords: Constrained Reinforcement Learning
Approximation Algorithms
Computational Complexity
Primary area: learning_theory

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. Our algorithm constitutes a fully polynomial-time approximation scheme (FPTAS) for any time-space recursive (TSR) cost criteria. A TSR criteria requires the cost of a policy to be computable recursively over both time and (state) space, which includes classical expectation, almost sure, and anytime constraints. Our work answers three open questions spanning two long-standing lines of research: polynomial-time approximability is possible for 1) anytime-constrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained policies.

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
Jeremy McMahan
University of Wisconsin-Madinn
jmcmahan@visc.cm
Abstract
We present 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 ap- proximate dynamic programming, and (3) time-space rounding. Our algorithm constitutes fully polynomial-time approximation scheme (FPTAS) for any time- space recursive (TSR) cost criteria. A TSR criteria requires the cost of a policy to be computable recursively over both time and (state) space, which includes classical expectation, almost sure, and anytime constraints. Our work answers three open questions spanning two standing lines of research: polynomial-tine approx- imability is possible for 1) wwriim-coosstrnnee policies, 2) almost-sure-construe policies, and deterministic expectation-constrannee policies.
Introduction
Constrained Reinforcement Learning (CRL) traditionally produces stochastic, expectation- constrained policies that can behave undesirably imaaine a self-driving car that randomly changes lanes out of fuel. However, artificial decision-making systems must be predictable, trustwor- thy, and robust. One approach to ensuring these qualities is to focus on deterministic policies, which are inherently predictable, easily implemented [19], reliable for autonomous vehicles [30, 23], and ef-
fective for multi-agent coordination [38]. Similarly, almost sure and anytime constraints [36] provide
inherent trustworthiness and robustness, essential for applications in medicine [15, 37, 32], disaster relief [18, 50, 45], and resource management [35, 34, 40, 7]. Despite the advantages of deterministic policies and stricter constraints, even the computation of approximate solutions has remained an open challenge since NP-hardness was proven nearly 25 years ago [19]. Our work addresses this challenge by studying the computational complexity of computing deterministic policies for general constraint criteria.
Consider constrained Markov Decision Process (cMDP) denoted by M. Let C represent arbitrary cost criterion and B be the available budget. We focus on the set of deterministic policies denoted by _1 Our objective is compute: max VT, s.t. O B, where V is the value and O is the cost of π in M. This objective generalizes the example of self-driving car calculating the fastest fixed route without running out of fuel. Our main question the following:
Can near-optimal deterministic policies for constrained reinforcement learning problems be computed in polynomial time?
Although optimal stochastic policies for expectation-constee putable [3], the situation drastically changes when require deterministic policies and general constraints. Computing optimal deterministic policies NP-hard for most popular constraints, including expectation [19], chance [51], almost sure, and anytime constraints [36]. This complexity remains even if we relax our goal to finding just one feasible policy, provided that we are dealing
problems are efficiently com-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

with single chance constraint [51], or at least two of the other mentioned constraints [36]. Beyond these computational challenges, traditional solution methods, such as backward induction [41, 3]. 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 single backward pass.
Past work. Past approaches fail to simultaneously achieve computational efficiency, feasibility, and optimality. Optimal and feasible algorithms, albeit inefficient, utilize Mixed-Intege Linear Programs [17] and Dual-guided heuristic forward searches [29] for expectation-constrane
and cost-augmented MDPs for almost sure [1I] and anytime constraints [36]. Conversely, optimal and efficient, though infeasible, algorithms are known for expectation [43], almost sure, and anytime constraints [36]. A fully polynomial-tine approximation scheme (FPTAS) [49] is known for ex- pectation constraints, but requires strong assumptions such as a constant horizon [31]. Balancing computational efficiency, feasibility, and optimality remains the bottleneck to efficient approximation.
Our contributions. We present an FPTAS for computing deterministic policies under any time- space recursive (TSR) constraint criteria. A TSR criteria requires the cost of a policy to be computable recursively in both time and (state) space, which captures expectation, almost sure, and anytime constraints. Since non-TSR criteria, such chance constraints [51], provably inapproximable, TSR seems pivotal for efficient computation. Overall, our general framework answers three open complexity questions spanning two longstanding lines of work: prove polynomial-time approxima- bility for 1) aanytime-come constrained policies, 2) almost- allmos--sure-constraane constraind policies, and 3) deterministic expectation-conssrainde policies, which have been open for nearly 25 years [19].
Our approach breaks down into three main ideas: (1) value-demand augmentation, (2) action-space approximate dynamic programming, and (3) time-space rounding. 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 [36] and can capture constraints that are not predictable from cumulative costs. However, this results in an exponential action space that makes solving the Bellman operator as hard as the knapsack problem. By exploiting the rpecerreeursive 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. Many stochastic packing problems, which generalize the knapsack problem, are captured by our problem. Dean et al. [16], Frieze and Clarke [21] derived optimal approximation ratio algorithms for stochastic packing and integer packing with multiple constraints, respectively. Yang et al. [52], Bhalgat et al. [6] designed efficient approximation algorithms for variations of the stochastic knapsack problem. Then, Halman et al. [27] derived an FPTAS for a general class of stochastic dynamic programs, which was then further improved in [26, 1]. These methods require single-dimensional state space that captures the constraint. In contrast, our problems have an innate state space in addition to the constraint. Our work forms similar general dynamic programming framework for the more complex MDP setting.
Constrained RL. is known that stochastic expectation-constrainee policies are polynomial- computable via linear programming [3], and many planning and learning algorithms exist for them [39, 46, 8, 28). Some learning algorithms can even avoid violation during the learning process under certain assumptions [48, 4]. Furthermore, Brantley et al. [10] developed no-regret algorithms for cMDPs and extended their algorithms to the setting with a constraint on the cost accumulated over all episodes, which is called a knapsack constraint [10, 13].
Safe RL. The safe RL community [22, 25] has mainly focused on no-violation learning for stochas- tic inpectation-consrraiie capture the probability of entering unsafe states. Performing learning while avoiding dangerous states [53] is special case of expectation constraints that has also been studied [42, 44] under
policies [14, 9, 2, 12, 5] and solving chance constraints [47, 53], which

---

non-trivial assumptions. In addition, instantaneous constraints, which require the expected cost to be within budget at all times, have also been studied [33, 20, 24].
2
Cost criteria
In this section, we formalize our problem setting. We also define our conditions for cost criteria.
(tabular, knite-horizon, Constrained Markov Decision Process (cMDP) is a tuple M = (S, A. P.r, c, H), where (i) S is the finite set of states, (ii) A is the finite set of actions, (iii) (a(s, a) E A(S) is the transition distribution, (iv) Th (s. a) E IR is the reward, (v) ca (s, a) E R is the cost, and (vi) H E N is the finite time horizon. We let S :- (), A := |A],
Constrained Markov decision processes.
def [M] = , H, and M denote the set of all cMDPs. We also let Tmaa max [1 a)l
denote the maximum magnitude reward, I I'mnn minn,,,a I' (s a) denote the true minimum reward, def and Pmin min (s s, s,a) denote the minimum transition probability. Since a finite set, often assume S [S] WLOG. Lastly, for any predicate p, the Iverson bracket notation [p] to denote if p is true and 0 otherwise, and we let Xp denote the characteristic function which evaluates to 0 if p is true and oo otherwise.
def
Interaction protocol. The agent interacts with M using a policy л = (TT)) In the fullest generality, Fx : Hr. -> A(A) is mapping from the observed history at time h to distribution of actions. In contrast, a deterministic policy takes the form TA Hr - A. We let II denote the set of all possible policies and IT denote the set of all deterministic policies. The agent starts at the initial state 80 E S with observed history Ti = (sp). ). For any / E [M]. the agent chooses an action an ~ Th (Tr). Then, the agent receives immediate reward ra (8h, aA) and cost ea (5h, on). Lastly, M transitions to state 81++1 ~ Pn(sn, on) and the agent updates the history to Th+11 (Th, (hS 1h+1). This process is repeated for H steps; the interaction ends once SH+1 is reached.
Objective. For any cost criterion C : M x I1 + IR and budget B E I, the agent's goal is to compute a solution to the following optimization problem:
Σ ru(sn, an)
JC S
max EM TEll
s.t.
(CON)
deterministic
Here, Pās denotes the probability law over histories induced from the interaction of a with M, and Eğ denotes the expectation defined by this law. We let V E ΣE re(s),,))) oz) denote the value of a policy n, and Vi denote the optimal solution value to (CON).
Cost criteria. We consider broad family of cost criteria that satisfy strengthening of the standard policy evaluation equations [41]. 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 cost criterion C time-recursive (TR) if for any cMDP M and policy E I2" ITs cost decomposes recursively into C = (so)). Here, (+)+(()) = 0 and for any h E [H] and T E Hi.
(k(T)) = = (x
+ (S ((Pa(s s,a), Ch+1 (Th, a, 6,) sEP(())))
(TR)
where s = 9n (T,), a = (T)), and f is a non-decreasing function' computable in O(S) time. For technical reasons, we also require that f(x) = oo whenever oc E x.
We further say C is tine-space-recussie (TSR) if the f term above is equal to gh Th. ((1.. Here,
T (S 1) and for any 1 < SS Ih
gh Th. (t) = a (B (Ph(t) s, s, Ch+ (Th, .9 Th. *t++)(+)))))
(SR)
'hen we multivariate function is non- non- decreasing, we mean it is non -on-decresiing with respect to the partial ordering induced by component simponent-wiseeee ordering.
3

---

where a is non-decreasing function, and both a, S are computable in (11) time. We also assume that at., oo) o0, and B satisfies a(3(0, x) = æ to match f's condition.
Since the TR condition is slight generalization of traditional policy evaluation, it is easy to see that we can solve for minimum- policies using backward induction.
Proposition (TR Intuition). If TR, then C satisfies the usual optimality equations. Furthermore, arg enn Cā can be computed using backward induction in O(H 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. (Expectation Constraints) are captured by CM def ENs [Σ cn() S B. We see C
is TSR by defining a(x, y) def x + and ((x, y) def xy.
2. (Almost Sure Constraints) are captured by Cha def max+gHn+1.
2==1 Cn(sn, ux) S B. We
see C' is TSR by defining a(x, u) def max(x, y) and ((x, v) 1x > 0ly.
del
3. (Anytime Constraints) are captured by CM def max(E[H] max En= en Ch(s:; an) S P1/1120
B. We see C' is TSR by defining a(x,1) max(O, max(2, v)) and ((x, 3) def 1x Oly.
Remark 1 (Extensions). Our methods can also handle stochastic costs and infinite discounting. We defer the details to Appendix F. 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 (Inapprxiimability) Our methods cannot handle chance constraints or more than of our example constraints. However, this is not a limitation of our framework as the problem becomes provably inapproximable under said constraints [51, 36].
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 could also tackle the problem by reversing the objective:
V subject to C, < B. However, attempt to minimize Căr subject to V 2 Vύ. If (CON) is feasible, then any optimal solution æ to this covering program satisfies V VM and C < B. Thus, we can solve the original packing program by solving the covering program.
def Proposition 3 (Packing-Covering Reduction). Suppose that Oi = min C s.t. VT 2 Vir Then, Ci S B > VM > -00. Furthermore, if VV > 00, then,
arg min CM V 2 V
arg orgmaxTeut VM, C. S B
C
(PC)
Thus, any solution to the covering program is 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 RL. and are more amenable to approximation [36]. Thus, the covering program allows us to capture many criteria, ensure feasibility, and compute accurate value approximations.

---

Algorithm Reduction to RL
Input: (M, C)
1: M,C. f Definition 2 C))
2: m, C* f- (M,VE(M, C))
3: if (so. v) > B for all E V then
4: return "Infeasible"
5: else
6: return
Value augmentation. We can solve the covering program by solving a cost-minimizing MDP M. The key idea 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 (so, VM), then an optimal policy for M should be a solution to the covering program.
The key invariant we desire is that any feasible policy т for M should satisfy (s, v) v. To ensure this invariance, we recall the policy evaluation equations [41]. Tx(() = a, then,
VA os = (n a) +
Σ Ph(d' (+,0)
(PE)
For the value invariant to be satisfied, it suffices for the agent to choose an action a and commit to future value demands uy satisfying,
rn(s,a) Pald 18,0) 2
(DEM)
We view choosing future value demands as part of the agent's augmented actions. Then, at any augmented state (s, v). the agent's 's augmented action space includes all (a, v) E A x H satisfying (DEM). When M transitions environment's 's new state in addition to its chosen demand for that state, (8', v.). Putting these pieces together yields the definition of the cover MDP, Definition
~ Ps (s, a), the agent's new augmented state should consist of the
Definition (Cover MDP). The cover MDP M del (S,A,
where,
1. S def S x V where V def {u FF ITP, h [H 1), E Hr, Ví = o)
()) + E. Pa s,a)es 2 2). 2. us, def ((a,v)
3. Pr((s ,0) us, (a, v)) Pa(s' s,a)[t'= = =z.
4. (x, v), (a, v)) del
as)
The objective for M is minimize the cost function C def C3r with modified base case C H (), def (es0)-
Covering algorithm. Importantly, the action space definition ensures the value constraint is satisfied. Meanwhile, the minimum cost objective ensures optimal cost. So long our cost is TR, 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.
Theorem 1 (Reduction). If SOLVE is any finite-time MDP solver, then Algorithm I correctly solves (CON) in finite time for any TR cost criterion.
Remark 3 (Execution). Given value-augmented policy output from Algorithm 1, the agent can execute я using Algorithm 2. To compute V as the starting value, suffices for the agent to compute,
V max {u V Ci (50, v) < B)
(1)
This computation can be easily done given (so,) .) in O(V)) time.
5

---

Algorithm 2 Augmented interaction
Input:
1: 81 = (Su. VM
2: for h f- 1 to H do
3:
(a, v) f- (3))
4: Th rn (n, a) and 8h+1 Pa(sn,
5: 8h+1 = (sb+1; Usp
4 Fast Bellman updates
In this section, we present an algorithm to solve M from Definition 2 efficiently, Although the Bellman updates can be hard to solve as the knapsack problem, 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 V were small, solving M would still be challenging due to the exponentially large action space. Even single Bellman update requires the solution of a constrained optimization problem:
(s, min on (s, a) + f ((Pa(6') s, Ch+a (6', v.)) 3 sEPP((..)
a.V
(BU)
s.t. rr a) + > Pa(d' (s,))u.2 2
Above, we used the fact that (s',v) E Pa((s, v), (a, v)) iff E Pa a) and o' ug to simplify f's input. Observe that even when each U&r only takes on two possible values, {0, w. J. the optimization above can capture the minimization version of the knapsack problem, implying that 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 (8, v) E S and a E A, we focus on the inner constrained minimization over
f ((Pa(s') s, Thta (
min VEVS
(2)
Ta (x.a)+E., (a 20
We use (SR) to transform this minimization over into sequential decision-making problem that (s.v).la.v) (t, v') into function
decides each Ugr. As above, we can use the definition of P to simplify Ir. of alone:
(a.)) (t) = (3 (Pa(t) s, s.a),Ci, Ch+i (t) (aw)),aa)) (t + +1))
(3)
Since e only constrains the valid (a, v) pairs, we can discard and use the simplified notation (t) instead of gh (a.)).(a.))) (t). It then clear that recursively optimize the value of e by focusing
on gh, (1).
To recursively encode the value constraint, we can record the partial value u = Th (8, a) E (s' s, a)u,/ that we have accumulated so far. Then, we can check if our choices for satisfied the constraint with the inequality 2 v. The formal recursion is defined in Definition 3.
Definition 3. For any h E [H] S v E V, and u E R, we define, Nh. + 1. 1,u) = X(u2o) and f S,
3. (,, = min a (8 s, Ch+z (t, v.)) g. 1,u Pa | s,a)).)) weD
(DP)
Recursive rounding. This approach can still be slow due the exponential number of partial values u induced. Similarly to the knapsack problem, the key is to round each input 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 more aggressive recursive rounding. Since rounding may cause originally feasible values to violate the demand constraint, we also relax the demand constraint to x(v) for some lower bound function K.

---

Algorithm 3 Approx Bellman Update
Input: (h, 8, Ch+1)
1: for a E A do
2: 9h, (S 1, u) t X(u20) Vu E B.Euhh1 (S + +1)
3: for - S down to 1 do
4: for u u do
5:
01,as I2,0 (t, u) + (ADP)
6: a", (r,C f mingEA Ca(s, a) + an (L,
7: return (a", s U and Oj (s)
Algorithm 4 Approx Solve
Input: (M,C)
1: C (s, v) 4- X(vzo) for all (s, S
2: for + H down do
3: for (s, E do
4: à, (,,, Algorithm 3(h, 0h+1)
5: (s, v) f-
6: return and C*
Definition 4. Fix a rounding function L:Ig and lower bound function k. For any / E [M], 8 E S, UE E V. and u E R, we define, 5.. (S + 1, u) = X(u2v) and for t S S,
Tho (t, u) def min (P s, s, Ch (t, v)) 2h + +1, lu Pa(t a)v))l)) (ADP) v.E
Fortunately, the approximate version behaves similarly the original. The main difference the constraint now ensures the rounded sums are at least the value lower bound. This is formalized in
Lemma
Lemma 1. For any [S+ 1] and R. we have that,
(t.
min (t)
VEVS-111
(4)
S.1.
h u) 2 k(v),
where 6/2 (t, def [u + Pa(t s, s,a)o +... (S s, s,a)ss
To turn this recursion into a usable dynamic programming algorithm, we must also pre-compute the inputs to any sub-computation. Unlike in standard RL, this computation must be done with forward recursion. The details for the approximate Bellman update are given in Definition
(,,(()) Definition 5 (Approx Bellman). For any E [H]. E S, and a E A, we define U, (1) def and for any E [S].
(t
def
U
U
{lu+ Pa(t 8,)))lg)
(5)
V.EV (E();"(1)
Then, an approximation to the Bellman update can be computed using Algorithm 3.2
Proposition 4. Algorithm runs in OHSS time, where O def max 10 When L:Ig and & are the identity function, Algorithm 4 outputs an optimal solution to M.
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 F.
We use the notation ming =(x) say that is the minimizer and the value of the optimization.

---

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-ting time Bellman updates, the running time of the approximate Bellman update will still be slow if [V] is large. To reduce the complexity, we instead use smaller set of approximate values by rounding elements of [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 carefully design the rounding and lower bound functions to balance this trade-off.
Value approximation. Given rounding down function 1:1g. we would ideally use the rounded set [Lvg e V} form our approximate state space. To avoid having to compute V explicitly, we instead use the rounded superset [[v]g u UE [Umin, Umaz]], where Umin and Umaa 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 I, we know this is exactly the set of (a, v) for which $.0 (1, (8, a)) 2 x(v). Combining these ideas yields the new approximate MDP, defined in A
Definition
Definition (Approximate MDP). Given rounding function L:1g and lower bound function k, the approximate MDP M def (S P,C, H) where,
1. S def Sx & where v def {Lugg V [Uman Umaz]}
2. 0s) del EA Ss 10 (1, k()))
3. (i((({,0) | (s, (a, v) def Ps s, =
4. (,, 0). (a, f) def as)
The objective for M is to minimize the cost function é def C3s with modified base case Ez H+ (s, 0) der X(e5o)-
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 L-Ig and K, the following holds: for any E [H + 1] and (s, v) E S, we have (s, (u]g) I (s,
Thus, Algorithm 5 always outputs a policy with better than optimal cost when the instance is feasible, V > -oc. 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 eтror 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 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 Hl and S.
Arithmetic rounding. Our first approach is to round each value down to its closest element in a 8-cover. This guarantees that u 5 < [w] g < v. Thus, [v]g is an underestimate that is not too far from the true value. By setting to be inversely proportional to SH, we control the errors over time and space. The lower bound must also be function of S since it controls the error over space.
8

---

Algorithm 5 Approximation Scheme
Input: (M, C,C,
I: Hyperparameters: 1.1g and K
2: M, <- Definition 6(M, C, (:lg,,))
3: Ó* < Algorithm 4(M, C)
4: if C1 (so: B) B for all E V then
5: return "Infeasible"
6: else
7: return 7
Definition (Additive Approx). Fix E > We define,
Lu]g [
def
5 and k<() def 8(S 1):
(6)
where 8 def
def H1 man. and Umaz Hrmas-
def
H($+1)+1 Uyain
Theorem 2 (Additive FPTAS). For any > O, Algorithm using Definition 7 given any cMDP M and TSR criteria C either correctly outputs the instance is infeasible, produces policy satisfying V 2 Vis in O(H² 5 Ar Armaz/e time. Thus, it is an addiiive-FPTAS for the class of cMDPs with polynomial-boundee
Ymaz and TSR criteria.
Geometric rounding. Since the arithmetic approach be slow when Tmaz is large, instead round values down to their closest power of 1/(1 - 5). This guarantees the number of approximate values needed is upper bounded by a function of log(Tmaz), which is polynomial in the input size. We choose a geometric scheme satisfying v(1 6) < [w]g S v so that the rounded value an underestimate and relative approximation to the true value. To ensure this property, must now require that all rewards are non-negative.
Definition (Relative Approx). Fix 0. We define,
log
[w]g def mén
and n(v) def v(1 8)5+1,
where 8 def
H($+1)+I+ Umiín Pminn Tmins and Umax HTmav-
Theorem 3 (Relative FPTAS). For e >> O, Algorithm 5 using Definition 8 given any cMDP M and TSR criteria either correctly outputs the instance infeasible, or produces a policy æ satisfying Ve 2 VM (1 -11-e) O(H log (Fmaz/ moin//mmmmmmn )3 /e3) time. Thus, it is relative-PPTAS 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 generally not computable.
1ormark5AAsunnn
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 polynomially bounded, 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 the TSR condition in making (CON) tractable. Our work finally resolves the long-standing open questions of polynomial-time approximability for 1) anytime- constrained policies, 2) simoos-sure-constrainee policies, and 3) deterministic expectation-constreee policies.

---

Future work. Several interesting questions remain unanswered. First, it remains unresolved whether an FPTAS exists asymptotically faster than ours. Second, whether our TSR condition is necessary for efficient computation or whether a more general condition could be derived is unclear. Lastly, it is open whether there exist algorithms that can feasibly handle multiple constraints from Proposition 2. Although computing feasible policies for multiple constraints is NP-hard, special cases may be approximable efficiently. Moreover, an average-case or smoothed-cass analysis could circumvent this worst-case hardness.
Acknowledgments and Disclosure of Funding
This work was supported in part by NSF grant 2023239.
References
[1] T. Alon and N. Halman. Automatic generation of fptases for stochastic monotone dynamic programs made easier. SIAM Journal Discrete Mathematics, 35(4):2679-2722, 2021. doi: 10/119799M13308663 URL https::pp//. h http://.....r/111.1//////1111111
1137 1
[2] M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, and U. Topcu. Safe reinforcement learning via shielding. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1), Apr. 2018. doi: v0.1609/aai.v222..1111.... 11297. URL httph::t////// /tt../aa..aaaa.............a.... oroooogg///oo //ng/nnd..... php/ MM//arttileevvie//111
[3] E. Altman. Constrained Markov Decision Processes. Chapman and Hall/CRC, 1999, doi: 10. (0.11199881115140220
[4] Q. Bai, A. Singh Bedi, and V. Aggarwal. Achieving zero constraint violation for constrained rein- forcement learning via conservative natural policy gradient primal-dual algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 3766)66777777744 6 2023. doi: 10. 10.1609/aaii. v3716.25826. URL //op:::://jj// aaai, org/ hetg//nnxx.... php/ hatpp///AA/taaiicce//eeeeeee 25826..
[5] Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause. Safe model- based reinforcement learning with stability guarantees. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 30. Curran Associates, Inc., 2017. URL http:hhhts::ppooceeeeeeeie paper ppppprrrp/pppppppprrrrrre http:///wapp.a....//a/c///////aa
neurips cc/ pdf.
/
[6] 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.
[7] A. Bhatia, Varakantham, and A. Kumar. Resource constrained deep reinforcement learning. Proceedings of the International Conference Automated Planning and Scheduling, 29(1): 610-620, 2021. doi: (0.1660//caps.v222 v2911.35299 URL. https:/ //ops:://jjs /ojs. aaai, .aag.org/aae org/index. index... php/ICAPS/arte httpa/atteeeeee///2222222
[8] V. Borkar. An actor-critic algorithm for constrained markov decision processes. Systems Control Letters, 54(3):207-213, 2005. ISSN 0167-6911. doi: http:://doi.org/00.01166 sysconle.2004.08.007 URI.
50167691100001276.
[9] D. M. Bossens and N. Bishop. Explicit explore, exploit, or escape (e4): Near-optimal safety- constrained reinforcement learning in polynomial time. Mach. Learn., 112(3))817-858, 6 2022. ISSN 0885-6125, doi: 10. 00.10077/119994-222-000010 URL hittps://dot org/10. s10994- 0200--222-000 022-06201-..
[10] K. Brantley, M. Dudík, Lykouris, S. Miryoosefi, M. Simchowitz, A. Slivkins, and W. Sun. Constrained episodic reinforcement learning in concave-convex and knapsack set- tings. NewrIPS, 2020. URL. https: httppp::/ppopcepiinnggg/oo/ wwwpddiiinnnnnnniinineeeee newrins wwtps/cccpppppeeeeeeeee /hash/ (cdd755877eeed427555777777177 -tt.://dddddeaaaaaaraaaat....t.. Abstract. html.
10

---

[11] A. Castellano, H. Min, E. Mallada, and J. A. Bazerque. Reinforcement learning with almost sure constraints. In R. Firoozi, N. Mehr, 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. PMIR, 6 2022. URL https: prt.c/edocceeeenss///o mlr ppwss/v168/ cwwtellanooaa.... html.
[12] R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick. End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks. Proceedings of the AAAI Conference on Artificial Intelligence, (3(01):3387-3399 Jul. 2019. doi: 10.1669/aaai.v3330) 33013387. URL attps://og aaai org/ index. wwwpiinwwe.iiiii.eeeeepppeeppppe httpp/pp/paaaaaaiaaaeaaaapppaaaa http:///AAarrtteeeeeeee//////22/
[13] W. C. Cheung. Regret minimization for reinforcement learning with vectorial feed- back and complex objectives. In Advances in Neural Information Processing Sys- tems, volume 32, 2019. URL https: http///doooceeeeeeee/eeee wewrips.cc/paperreeeeeeee..ee cc/paper/2019/fflee
000f:00000ca0111ee46666666000000 Pww.111aa009aa.a..a-ee .df.
[14] Y. Chow, O. Nachum, Duenez-Guzman, and M. Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Informationn Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: https:::/proceeeeinngg///// neurips cc/ cc/paper. htpppppppeeessss_//// files/ hppp://000/114444400657776666660 Paper pdf.
[15] A. Coronato, M. Nacem, G. De Pietro, and G. Paragliola. Reinforcement learning for intelligent
healthcare applications: A survey. Artificial Intelligence in Medicine, 109:101 164111 2020. ISSN 0933-3657. doi: http::/doi.oor http://ddooor//100.0 httpa//a/////////33///22222222 sciencedireen com http//ccinceeeeeeeeeeo/ http:////eeeaattttt/////////////
101964. URL https: //w/:://wwww
[16] B. C. Dean, M. Goemans, and J. Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium Dis- crete Algorithms, SODA '05, page 395-404, USA, 2005. Society for Industrial and Applied Mathematics. ISBN 0898715857.
[17] 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.
[18) C. Fan, C. Zhang. A. Yahja, and A. Mostafavi. Disaster city digital twin: A vision for inte- grating artificial and human intelligence for disaster management. International Journal of Information Management, 56: 102049, 2021. ISSN 0268-4012. doi: https://oi.org//00 1011///0 1016/ J.jinfoomgg2011.1022444 URL https: http://www.cciineeerrrrttte com ctmm//iience//rttiee./ psi/SQ266401219302956
[19] E. A. Feinberg. Constrained discounted markov decision processes and hamiltonian cycles. Mathematics of Operations Research, 1501):130-140, 2000. doi: 10. 2...9//mo.......33..155
URL https: //toi/ org/ 10. 10w7 25 1. 130. 15210.
[20] J. Fisac, N. Lugovoy, V. Robies-Royo, S. Ghosh, and C. Tomlin. Bridging hamilton- jacobi safety analysis and reinforcement learning. In 2019 International Conference on Roboties and Automation (ICRA), page 8550 8556. IEEE Press, 2019. doi: (0.1109/CRA.221113994400) URL https: //dii. org/ 10. 1109/ 1199/ICRA ICRA 2019. 879411777
[21] 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: URL httpss///ww...eiieeeeee..... httpa//www........c.ccc.ccooeaaa
[22] J. García, Fem, and Fernández. A comprchensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437-1448) 2015. http:/// org/
papers/vis veeers//v//e/ garciai5a.hhtm.
[23] F. Geißer, G. Povéda, F. Trevizan, M. Bondouy, F. Teichteil-Königeeee Königsbuch, and S. Thiébaux. Optimal and heuristic approaches for constrained flight planning under weather uncertainty. Proceedings of the International Conference Automated Planning and Scheduling, 30(1): 384-393, Jun. 2020. doi: 10. 10.16000 1000///ccs...33/ v30ccappp..00..... www.v.v016....0... URL https:/t////c..ccmmm /// /ojs. aeaii.or/iingaeeeee index. Php/ICAPS/ane www.ICAAS//ticlllccc
wttps//rtiileeeee cetticcl/eeee wwweeleeeeeeeeeeeeeeeeeeeeeeeeee 6684.

---

[24] S. Gros, M. Zanon, and A. Bemporad. Safe reinforcement learning via projection on a safe set:
How achieve optimality? PEAC-PaperssnnLine, 53(2):8076 1077668081,,10 2020. ISSN 2405-8963. doi: https///bbb.or///00000116fffff/o
URL https: / /www. sciencedirect. com/ 21 IFAC World Congress.
[25] S. Gu, L. Yang, Du, G. Chen, F. Walter, J. Wang, and A. Knoll. A review of safe reinforcement learning: Methods, theory and applications. 2024. URL https://arxiv..ottt http://axwi..rgaaa///aaaaaa////a 22200 10330.
[26] N. Halman and G. Nannicini. Toward breaking the curse of dimensionality: An fptas for stochastic dynamic programs with multidimensional actions and sealar states. SIAM Journal on Optimization, 131-111,, 2019. doi: 10. 00.1137/18M1008433 URL https://doi. org/
10. 10.1137/18M120842
[27] N. Halman, D. Klabjan, C.-L.. Li, J. Orlin, and D. Simchi-Levi. Fully polynomial time ap- proximation schemes for stochastic dynamic programs. SIAM Journal on Discrete Mathemat- ics, 28(4):1755-1796, 2014. doi: 10.1113/130925153 URL https://doi. oog.orgg/// 10//111.10 1137/ 130925153.
[28] A. HasanzadeZonuzy, A. Bura, D. Kalathil, and S. Shakkottai. Learning with safety constraints: Sample complexity of reinforcement learning for constrained mdps. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):7667-7674, 2021. doi: 10.1609/amai. v35.9...99999 https:/ /ojs. aaai. orgg/nnee php/ http///rarteeeeeeeeeeeeeeeeeeeee
[29] 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: http::/doi. wttp://iii.r/11..11110..00 arttt//..ttitt.2222..... 2022..00442222 URL http:: wwtp//wwww.ciccccrreet.... com/ com/science, article/piii http////////////0/000001212
[30] 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 202/ IEEE International Conference Robotics and Automation (ICRA), pages 475-481, 2021. doi: 10. 109//CCA44800.20000 000.1.11111111 95611229.
[31] M. Khonji, Jasour, and B. Williams. Approximability of monstant-horizon constrained pomdp. In Proceedings of the Twenty-Fight International Joint Conference on Artificial Intelligence, IJCAI- 19, pages 5583-5590. International Joint Conferences on Artificial Intelligence Orga- nization, 7 2019. doi: 10. (024463//jcaii2119977 URL https:://dot http://oooo.oo//.////// 24963/ / i caai. 2019/775.
[32] Kolesar. A markovian model for hospital admission scheduling. Management Science, 16 (3):B38-B3366 1970. ISSN 00251909, 15265501. URL //wtt. http://stooorrr/taall...... www.eooggglssaeeeeee stable/ 2628725.
[33] J. Li, D. Fridovich-Kein S. Sojoudi, and C. J. Tomlin. Augmented lagrangian method for instantaneously constrained reinforcement learning problems. In 2021 60th IEEE Conference on Decision and Control (CDC), page 2982-2982 IEEE Press, 2021. doi: (0.1109/4D444484, 2021.9683088. URL aattps://doi.
1109/CDC45484. 0021.9688088.
[34] R. Li, Z. Zhao, Q. Sun, C.-L. 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 201 8. 2881964.
[35] H. Mao, M. Alizadeh, I. Menache, and S. Kandula. Resource management with deep re- inforcement learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Ner- works, HotNets "16, page 50-56. New York, NY, USA. 2016. Association for Comput- ing Machinery. ISBN 9781450346610. //doi. 1145 /005//300745... 3000550
doi: 10.1145/3005745.300575 URL https:
[36] J. McMahan and X. Zhu. Anytime-constraime reinforcement learning. In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings of 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 4321 43399. PMLR, 02-04 May 2024. URL https: httpttps///pooceeednnne mlr. wwwpppress//e//e// /22mmmmmmmmma22...mmm html.
12

---

[37] 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 (STTIS), pages 711-716, 2018, doi: 10.1109/SITIS. 2OTTTTSS..01.00111 2010.00114.
[38] 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.
[39] S. Paternain, L.. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances in Neural Information Processing Systems, vol- ume 32, 2019. URL https://pproceeeding http://roceeddnnn.eeeieeisspeeep file/clasn http://cc66........3334446666660 Paper.
wwtpcpppppppp.pc.e loverrfille wetrrfffleepppppe fiteeee/pp/pppr///////
[40] H. Peng and X. Shen. Multi-agent reinforcement learning based resource management in mec- and uav-assisted vehicular networks. IEEE Journal on Selected Areas Communications, 39
(1):131-141, 2021. doi: 10.10990SAAC.20033336666
[41] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
[42] M. Roderick, V. Nagarajan, and Z. Kolter. Provably safe pac-mdp exploration using analogies. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1216-1224. PMLR, 2021. URL https::/t///otttee http:////occeeen..///ee mlr, mwr.ppree press/ 2090/roddrick211 html.
[43] M. A. Taleghan and T. G. Dietterich. Efficient exploration for constrained mdps. In 2018 AAAI Spring Symposium Series, 2018.
[44] G. Thomas, Y. Luo, and T. Ma. Safe reinforcement learning by imagining the near future. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 13859-13869, Curran Associates, Inc., 2021. URL https: h/proc/eeecccc..oeceeeoooeoo wewp:r/reeeeiinnneeee..ooooooope cttpppp..ccppp.....cpppppp files pptp://ppppp//////111// 733277C12266111222222224ffaa Paw.bb-appppppp.pp.
[45] 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 Flood. In AGU Fall Meeting Abstracts, volume 2019, pages NH33B-14, Dec. 2019.
[46] S. Vaswani, L. Yang, and C. Szepesvari. Near-optimal sample complexity bounds for constrained mdps. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 3110-3122. Curran Associates, Inc., 2022. URL https: http:: http://///cpceeeeeeeeeeeeee neurips................ http:///ee//aaaaccoooaao/7/aaaaa htt.://rwwe...aaeeeeeeeeeeeeonne pdf.
[47] Y. Wang, S. S. Zhan, R. Jiao, Z. Wang. W. Jin, Z. Yang. Z. Wang, C. Huang, and Q. Zhu. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 36593-36603 PMLR, 7 2023. URL attps://proceediie
mlr, press/v202/ /ttp///222////22aas/ html.
[48] H. Wei, X. Liu, and L. Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3274-3307. PMLR, 2022. URL https: h/tp:///ecoc/cesss/e/eee mlr. prress/v51/wwill 2tmll.l... html.
[49] D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, USA, 1st edition, 2011. ISBN 0521195276.
13

---

[50] 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 complex disaster scene. IEEE Access, 117227-117245, 2019. doi: RAA109/AACESSS22999995350
[51] 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.
[52] 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 Leibnniz-Zentrum für Informatik. ISBN 978-3-95977-247-1. doi: 10. 0230/LIPIcs.ESA.22222 URL https: /ttp//ddrppp..//e dagstuhl de /wwpopps/vllleeeteee////e 17029.
[53] W. Zhao, T. He, R. Chen, T. Wei, and C. Liu. State-wise safe reinforcement learning: survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI '23, 2023, ISBN 978-1 1-556792--3---4 doi: 20.24966ijccai2222776.. URL https://doi.. org/10. 24922/29222/21 /ijaaiii/aa../// /t2////a3...2///6...
A Appendix/ supplemental material
14

---

B Proofs for Section 2
B.1 Proof of Proposition
The proof follows from the standard proof of backward induction [41]. The main ideas for the proof can also be seen in the proof of Lemma 4 and Lemma
B.2
Proof of Proposition
Proof.
1. (Expectation Constraints) We claim that Cj captures expectation constraints. This is immediate an expectation constraint takes the form BT E Cs(sh, an) S B and
by definition MM M Σ (n an)] Moreover, the standard policy evaluation equations for deterministic policies immediately imply,
(T,) = c (s, Σ (s 1 (,,0)T
(EC)
Thus, (TR) holds. is also easy to see that Eg Pa(s' computed recursively state-wise by,
a,
can be
(a | (, 1) +) Σ Pa(s' (1,))
(8)
and so (SR) holds. The infinity conditions and non-decreasing requirements are also easy to verify.
2. (Almost Sure Constraints) We claim that Cā captures almost sure constraints. This is because that for tabular MDPs, P. (E 1==1 Ch (Sh; an) I B] 1 if and only if for all
T E HH+1 with PA [T] > it holds that Eie Cn an) < B and only C% = max E Cx(8,, an) < B. Pb/1/30
Let c(t) = Σ#=
h= Cn (8h, an) denote the cost of full history E H and let Che((T)
Eken (sk, an) denote the partial cost of from time h to time Our choice of a and imply that,
(T.) a))
max ('EPa
Ch a's).
(ASC)
To show that C satisfies (TR), we prove for all h E [H + 1] and all Tu E Hy that
Ca(TT)) max rEH FMLTT))
(T:
(9)
Then, we see that (so) = max reHa (T:H(T) max Σ/t Ch (8h, an)
[r
PM
Ch. Thus, O satisfies (TR). Furthermore, is clear that max can be computed state-recursively by.
CT Ch+z (Th,
max (Th, a, [)[Pa(1 s, > 0). max Ohai(To, 8, 8')( (179((818,000 a. > 0)), (10)
='=2
and Că satisfies (SR). The infinity conditions and non-decreasing requirements also easy to verify.
We proceed by induction on h.
(Base Case) For the base case, consider h = H 1. Observe that for any history we have CH+1:: (T) = since it is an empty sum. Then, by definition of Cj we see that (T41(TH41) 0 max, 0 = max, CH+1:H(T).
15

---

(Inductive Step) For the inductive step, we consider h S H. Let s = (A(T) and Ta (T,).. For any Hu++ for which MM[T mm 0, we can decompose its cost by (7: (s,8,) a) + c1+1:11 (T). Since a is fixed, we can remove ca(8, a) from
the optimization get,
max Cc. = css rEN P 1F/T//220
max CT+1:H(
Next, observe by the Markov property that P [M TAl E. P IT a, 8 P/ s. Thus, PT Thl > 0 if and only if there exists some s' E a) satisfying P5 PT ( The a, > O. This implies that,
max (++1:1(T)= rEH#+1: P [F
max (sP)
max rEH#+11 F
Ch+1: (T).
By applying the induction hypothesis, we see that,
(r:n(t)=cu(s,ll) + max rEH#I1: P [r/T]220
max
TEH 11: Fh FMl (1)
max
s'EPa(s,a)
= cc((s,)) + max d'EPa(s,a)
Ch+ (Th,
= CT(AT)
The second line used the induction hypothesis and the third line used the definition of M-
3. (Anytime Constraints) We claim that C captures anytime constraints. This is because that for tabular MDPs, PM (Vt E [H], Σ (s an) S B] 1 if and only if for all E [ and r E HH+1 with PR [r] > 0 holds that Eh Ch (sh, an) I and only PM(T) C max [R] m
Ei (sh, ax) S B.
Our choice a and / imply that,
CT = Cn (8, (s, + max (0,
CT (())) (PPa(s.))
max
(AC)
To show that Cßy satisfies (TR), we show that for all h [H + 1] and all Th Hn that
Ca(Tn) = max max +EH# 12h
(har(T).
(11)
Then, we see that (so) = m max re CL:(T) = max max P7
Ehen cn ax) = O Thus, O satisfies (TR). Furthermore, it is clear that max(O, max m Oh (Th, a, s')) can be computed state-recursively by,
max maxx(0, Ch (Th, () 8, 0)),
(12)
max(0, max Ch (Th, a, a.),a,ss)))) (P)(ss s, a'=2
0)).
and so Cß satisfies (SR). The infinity conditions and non-decreasing requirements are also easy verify.
We proceed by induction h.
(Base Case) For the base case, we consider h + 1. Observe that for any history and I, have (T+) = 0 since it is empty sum. Then, by definition of C% we see that C 1 (TH+1) = 0 = max, max, max, max, (
'Technically, there is no E [H] satisfying > H + 1. We instead interpret the t 2 h condition in the max over all integers and define the immediate costs be for all future times simplify the base case.
16

---

(Inductive Step) For the inductive step, we consider h v H. Let = (h(T)) and
Th (Ta). By separately considering the case where h and t 2 h + 1 in the
maxi2h, we see that max42h max rEM#41: (Ta((T
FM
max
max Choc ChcA(T), max max Cha(T)
rEHM+1: P3r(7/m])20
12h+1
rEHx+1: Pl
Ch (((s,a) + max max Cc+II(T)
max
12h+1 reH 1
cC(88,)) + max
0, max 12++1 rEM#41: MM
max (u+Ia((T
= (8, + max
0, m18x max
C++1a(T)
12 (s.a)
P 1770
(s, + max
0, max
max ('EP)( 12
max rENu-11 P3lrtom
cu+1a(F)
= cn(88 a) + max
0, max (s,a)
C C (T,,
= C..(TT.
The second line used the fact that Ch:A Ch (s, a) and the recursive definition of (N=(()) 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
C Proofs for Section
C.1 Helpful Technical Lemmas
Here, we use a different, inductive definition for V then in the main text. However, the following lemma shows they are equivalent.
Definition 9 (Value Space). For any S, we define VH+1(s) {0}, and for any h [H].
(s)
U
rn(s,a) + Σ Pa(s' (s.
(13)
vEX, (h
We define V Un.o (s((s).
Lemma (Value Intution). For all E S and [H + 1},
Vi((s) = ( 3T II", Th E Hr, (s = su(Th) A V =))
(14)
and (s)] < AEL sH 8"-1 Thus, V can be computed in finite time using backward induction.
Lemma 4 (Cost). For any h [H + 1}. E H4. and V, if su(Ta), then,
(5, min CR (Th) m
(15)
s.t. V (Th) 2 v.
17

---

Lemma 5 (Value). Suppose that E II For all h E [H + 1] and (s, E S, if (f < co, then Vi (8, v) 2 u.
Remark 6 (Technical Subtlety). Technically, Vg (Tx) is only well defined if Pf [T)]]]]]]])] > and all of 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, we have done here. Formally, this is equivalent assuming the process starts initially at тж instead of just conditioning on reaching Th, or defining the values to correspond to policy evaluation equations directly. This is consistent with the usual definition when PT [Th] but gives it a defined value also when P5 [Tx] = 0. In either case, this detail only means our recursive superset rather than exactly the set of all values as we defined in the main text.
definition of This does not effect the final results since unreachable trajectories do not effect x s overall value in the MDP anyway, and only effects the interpretations of some intermediate variables.
C.2 Proof of Proposition? 3
Proof. By definition of V and Civ-
VM+ >
En E II. C. S BAVE 2 VM
CM S B.
For the second claim, we observe that Vi > -o then by the above argument any optimal deterministic policy for COVER satisfies CM = Css I B and V V.- Thus, COVER S
PACK.
C.3
Proof of Lemma
Proof. We proceed by induction on h. Let E S be arbitrary.
Base Case. For the base case, we consider h = H + 1. In this case, we know that for any E _1 and any T HH+1, ( 0 {0} VH++(s) by definition. Furthermore, (s)+ = A A St
Inductive Step. For the inductive step, we consider h < H. In this case, we know that for any TTP and any Th Ha. if (Th) and TT. (T)),,), then the policy evaluation equations imply,
(T.) rx(ss)) + Σ I (
We know by the induction hypothesis that Vita(To a, 8') E (8'). Thus, by (13), Vg (T.) e Vn (s). Lastly, we see by (13) and the induction hypothesis that,
(s) s II (s+) S A III
A S" A1+5E 5"1 = =A -AE s"-
This completes the proof.
C.4 Proof of Lemma
Proof. We proceed by induction h. Let Tu E Hr, and V be arbitrary and suppose that $ = sn (TR). We let (T,, v) denote the minimum for the RHS of (15).
Base Case. For the base case, we consider h = H 1. Observe that for any a E ITP, V (TH+1)= = by definition. Thus, there exists IT satisfying V (T=1(T if < 0. We also know by definition that any such policy и satisfies C CT+1(TH+1) 0 and if no such policy exists C#++1 (TH-1; r) by convention. Therefore, we see that C (T)+1,0) X(e50)- Then, by definition of the base case for C. it follows that,
if and only
Ci+1(s, Xleso = (T=1
18

---

Inductive Step. For the inductive step. we consider h S H. If (T,,,, = xc, then trivially (8, S (T. v). Instead, suppose that Ca u) < co. Then, there must exist a feasible x E IIP satisfying V. (Tr) 2 v. Let a" = (Tn). By the policy evaluation equations, we know that,
= + Σ (o (Tt
V (Thy a', s') and observe that og E Vs+i(s') S V by Lemma 3. Thus, we see that (a", vt) Ax vs and ra(s,a) + Ev Ps 8,0)us 2 which implies (a",v")= (s,
For each s' E S, define us def V
Since satisfies (T 88) Ug, it clear that 08 S C (T,, a², 5'). Thus, the induction hypothesis implies that C (41( oz) S Ch (s', ug)) S C ( s'). The optimality
equations for M then imply that,
(), = min (ss (PPh(s' ss Cht1 (x), sEE)tta)))))))) (..))
$ sc((s,a)++ (1Ph(''1s, (s', (eP))ta))))))))))
<cn(s,a") (Pa (8,6, Ch+s (Tr, 8)) sEPa(a)) (Th)
The first inequality used the fact that va) E (s, The second inequality relied on f being non-decreasing and the induction hypothesis. The final equality used (TR).
Since π was an arbitrary feasible policy for the optimization defining Cj v), we see that C%, S (T,, This completes the proof.
C.5 Proof of Lemma
Proof. We proceed by induction on h. Let (s, v) E S be arbitrary.
Base Case. For the base case, we consider H +++1, 1. By definition and assumption, Ö #+ (s, ((e50) < 00. Thus, it must the case that S and so by definition (8, = v.
Inductive Step. For the inductive step. we consider h < H. We decompose T (s, v) = (a, v) where we know (a, v) E An v) since æ has finite cost'. Moreover, must be the case that for any E S with Ph (s' s, a) >> 0 that C us', < oc otherwise the property that f outputs oo when inputted an oo would imply contradiction:
(s, v) ca(s,a) + ((Pa(s)) a,)), Cht1 (6, SEP))e)))))))
= cs, a) + (0..,., =00
Thus, the induction hypothesis implies that Vit ver) ) 2 vy for any such s' E S. By the policy evaluation equations, we see that,
(s) = rn(s,a) Σ Ph(s's s,a))
2 rn( + Σ Pa(s') (s,)),
The third line uses the definition of (s, This completes the proof. By convention, assume min Ø
19

---

C.6 Proof of Theorem
Proof. If C7 (80, v) > for V E V. then Ci > B since otherwise we would have Čj (so, v) S (s00 1) = Cir B by Lemma 4. Thus, if Algorithm 1 outputs "infeasible" it is correct.
On the other hand, suppose that there exists some u E V for which (so. v) S B. By standard MDP theory, know that since
ITT is solution M, it must satisfy the optimality equations. In particular, C7 (8n, u) = Cj (80, v) I B. Since CF = CT (so, v)', we see that there exists a π E TT for which C. S B and VM -00.
Since VA is the value some deterministic policy, Lemma 3 implies that Vy V. Thus, Lemma implies that V (so, VM) VM and (To, V I Cj (so, VMr S. B. Consequently, running with initial state 50 = (50, VM) ) is an optimal solution to (CON). In either case, Algorithm is correct.
D Proofs for Section 4
Definition 10. We define the exact partial sum,
hh (t,
Pnis def u+ Σ Pa(s's s,,),, s/=t
(16)
Observation 1. We observe that both a and 5 can be computed recursively. Specifically, o (S + 1,u) and h. (1, u) 1.a (1, Pu(t 8,0)o.. Similarly, ( + 1,u) and 35.0 (t, - (t, Pa s.at
For completeness, and to assist with other arguments, we also prove the exact recursion we presented in Definition is correct using Lemma 6.
Lemma 6. For any [S 1] and R. we have that,
3.0 (t, = min 9h.0
vEVS-r-1 (t)
(17)
S.1.
u +
Pa 18 18, 2 v.
Moreover, (7 v) = min (a(s, a) + Dh
3.0 (1, Th (s)
D.1
Proof of Lemma
Proof. We proceed by induction on L.
Base Case. For the base case, we consider t = S 1. Since ΣS Es=s+1 Pa(s' (, = is is true iff 2 Also, for any v, gh (S 1) by definition. Thus, the minimum defining g (S + 1, u) is when u > v and is oo due to infcasibility otherwise. In symbols, 9h. (S + 1, u) X(aze) as was to be shown.
the empty sum, the condition ES Es=s+1 Pa(s' (),
'We can view (V) as the extension of C' (V) needed to formally evaluate cemory-augmennte policies. Since consider deterministic policies, it is trivial to convert any augmened policy into history- dependent policy that is defined in the original environment M.
20

---

Inductive Step.
For the inductive step, we consider S S. We see that 3.
Ih (t, u)
min vEVe 244 641
5:0 9h.v (1)
a+ -. Pa(s (.))
(3 (Pa(() (h.1(())) 1hh
min vEyS-++1
u+ -+E. (.(ss(s.a)).))
a (B((P(tt) s,a), Ch+ (t, .h. (t (t+ 1))
min MeEV
min vers-t 22
min a M
B (Pa((t) s, 0,4), (t,w)).
min (utPa(t(ssa))+ - P
( +1)
3.0
min a (P 2. Ch+ (t)) Ih 1, Ph(tt s, s)))),)
M.EV
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 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 (s, (1, Cj v) then follows from the definition of (s, v) and (BU):
min (s, + 9h, (l, = min (s aEA
min vErS
Jh.v (1)
aEA
ra(s,)) + +. P100
min aEA
min veys (x E, (a( Cx(s,a) + (1
Cn(s, a) + Jh,v ( (1)
min
(a.))
Cs)
D.2
Proof of Lemma
Proof. We proceed by induction on I.
Base Case. For the base case, we consider t = S + 1. By definition, 2 (S 1, the constraint satisfied iff 2 v. Since for any v, ( + 1) by definition, the minimum s.a (S + 1, is 0 when u 2 and is oc due to infeasibility otherwise. In symbols, defining 9h gh + L, X(u2o) was to be shown.
21

---

Inductive Step.
For the inductive step, we consider t S S. We see that,
9h.0 (t, u)
min vEV--1+1
(h)
min vErS-1+1 by (a))2
a ( s. Ch+ (t, (t
(S((Ptt)) s, (, (t, Ihy (t (t+
min NEV
min
vEYS
min
B (Pr(tt 8, 0,, ((,vz))
min
g (t +1)
NEV
vEY5-1
min a (B s,0), Ch+1 (t, v)) 9.. (f 1, Pt ( s,
vEV
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 ā in the constraint. The fourth line used the fact that a is a non-decreasing function of both arguments and the fact that the second optimization only concerns the second argument. The last line used the induction hypothesis.
D.3 Proof of Proposition 4
Proof. The runtime guarantee easily seen since Algorithm 4 consists of nested loops. The fact that it computes an optimal solution for M absent rounding or lower bounding follows immediately from Lemma 6.
E Proofs for Section 5
E.1 Helpful Technical Lemmas (Additive)
The following claims all assume Definition 7. Observation 2. For any IR,
V v 8 L-le S.
(18)
Lemma 7, For any h E [H]
R, and t E [S + 11, we have
(1, - -5 1)6 < (1, < (1,
(19)
Lemma 8 (Cost). For any h E [H + 1] and (8,v) v) E S, C7 (o]g) S (s,
Lemma 9 (Approximation). Suppose that π E ITP For all h E [H + 1] and (s, E S. if
Ö 6) < cc, then V (s. 6) 2 0 8(S + 1)(H h h+11 1).
E.2 Helpful Technical Lemmas (Relative)
The following claims all assume Definition 8. Observation 3. For any IR,
v(1 ((1-0) 6) s L Sv.
(20)
Lemma 10. For any h E H. SE a A. v ER u E Rgo. and t E [S + 1], we have,
hh (1) 8-
(t, S oi (t, u).
(21)
Lemma 11 (Cost), Suppose all rewards are non-negative For any [H + 1] and (s, S. (s, (v]g) S Cx(ss)) v).
Lemma 12 (Approximation), Suppose all rewards are non-negative and π E II", For aor h e [H+1] and (s, 0) E S, if (f (s, (s, 6) < co, then V (s, 6) 2 6(1 (1-)88+++(H--+))
22

---

E.3 Proof of Observation 2
Proof. Using properties of the floor function, we can infer that,
[mlg
_ = v,
and,
2
|0|
=
8
8 2
-1)8 =
6 - 6 2 0 6.
E,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 0, (S + 1, h (S + u).
Inductive Step.
For the inductive step, we consider S S. We first see that,
0 h (t, u) = , (t 1, Iu + (t s,
S o 1, u (t a,))oll)
= Pa(t 8, a.000 + Σ
Pa(s' 8,a)e,
s'=++1
S uut Σ (s s,
n. (t, u).
The first inequality used the induction hypothesis and the second inequality used the fact that | S x.
We also see that,
hny (t, u) o + [u Ph(t s))eos
2 onv + 1, [u + Ph(l s, s.)))=l))- -
- -(S-
lu+ Pa 8, a, + Σ Pa(s' s, 8(S - t)
s'mt41
8
2 + Σ Pa s,a)0, - ( - 1+1)
s'=t
8.0 b.v
(t, u) 8(S 1+
The first inequality used the induction hypothesis and the second inequality used the fact that
[x g 2 r
5.
E.5 Proof of Lemma 8
Proof. We proceed by induction on h. Let (s, v) S be arbitrary.
Base Case. For the base case, consider h H + Since Lu]g S immediately see,
CH = [1v S X(uso} (8,
23

---

Inductive Step. For the inductive step, we consider h S H. If o) co, then trivially C,,s, (v]g) (s) u). Instead, suppose that (x, < cc. Let be solution to the optimality equations for M so that C% (s. u) (s, v) < co. Since (h,ss v) < oo, we know that (a", v*) (s) E Anss, v). By the definition of An, U), we know that,
kv = as) Pn 8, 1,,"))u 2 Llla-
For each s' E S, define 82. Lا and recall that 2ig E V. We first observe that,
3.0 h.v- (1, rn(s,a") + Σ (s |s, Lu
2 (n(ssa") + Σ Pr [s, -6) 6)
=rx(s,a") + Priss ss, - 8
=..0"" (1rnss))))) -8.
Then by Lemma 7,
3.00 h (1,rn(s,a"))
aa (1, 8S
A.
aa" hr (1,rn(8,a")) - 8(S 1)
Lulg - 3(5+1) x((ulg)-
Thus, (a", v1) E LuIg).
Since uy, E V. the induction hypothesis implies that (5', S C O2+1(',05) = (x+1(6,0)))
The optimality equations for M then imply that,
(g min (((sa)+ ((PA(6' (s,a), Ch+1 (,), (5 (or) sEPP(eAa)) (aM))A((s)))
S af ((PA6') ( s,a"), Chez (5, )
s = (PPa(' ( Oht (d), (s,)))
us)
(s, v). The second inequality relied on f being The first inequality used the fact that va) E An non- -ecresesnn and the induction hypothesis. The penultimate equality used (TR). This completes the proof.
E.6 Proof of Lemma 9
Proof. We proceed by induction on h. Let (s, 6) E S be arbitrary.
Base Case. For the base case, consider h H 1. By definition and assumption, Eτ 1 0) ((eco) < co. Thus, it must be the case that < 0 and so by definition V 6) = 0 2 0.
Inductive Step. For the inductive step, we consider h < H. As the proof of Lemma 5, we know that TT. (s, v) = (a, v) A, 0) and for any s' S with (s ss)a) > that &h (h var) < co. Thus, the induction hypothesis implies that W 0x) e. 6(S + 1)(H - h) for any such
24

---

s' E S. By the policy evaluation equations, we see that,
(s, as) + Σ Pa(s' ss,a
2 (n( Ps s,, 5(S 1)(H h)
h 8(S + 1)( h)
2 9,0 (s,,((,r((ssaa) - 6(S + 1)(H - h)
2 0 - 6( 1) 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 (s, 6) and K, o, (1, (s) 2 x(0) 0 0-5(5 1). This completes the proof.
E.7 Proof of Theorem 2 Proof.
Correctness. If (so, v) B for all ê E V, then Cs B since otherwise would have (sa. (mlg) S (so. v) S Ci s B by Lemma Thus, if Algorithm outputs "infeasible" is correct.
On the other hand, suppose that there exists some ê v for which (sa, 6) S B. By standard MDP theory, we know that since x E 11 is a solution M, must satisfy the optimality equations. In particular, ČT (so. 8) we see that there exists ग E I1 for which C. S and so VM -00
(sp, 2) S As in the proof of Theorem 1, since Cм (s i).
Since Vžr is the value of some deterministic policy, Lemma 3 implies that VM E V. Thus, Lemma implies that 1/= (so,
(lrlg) 2 LV - 5(S + 1)H 2 VM - 5(1 (S + 1)H) = VM e and CT (50. Vit) S C1 (so, VM) S B. Consequently, running æ with initial state 5g = (so, (lgg) 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² A()12(1)) To bound [V], we observe that the number of integer multiples of required to capture the range H-Hrmax: H Hrmasl is most O (Hngae)) O(H² mmaa//c by definition of 6. Moreover, | O(I² + S) O(iV)) for sufficiently large Tmax_
In particular, we see that the range of the rounded sums defining ú is at widest [-2Hr maz 8S, 2Hrmaai since for any + the rounded input is,
(rn(s, + Ph(1 a, .... + Pa(t) S rn(ss + Σ Phls' s,a)ior
which is at most 2 2Hr and,
[Ir((s, + PA s. avvilg ( +... +...+ Pa(t s, a, 2 () +
Σ Ps s,a) - St.
s'-1
which is at least -2 man 8S. Overall, we see that 0(1)) 0(1)13) 03H553, 3 / implying that the total run time is O(H 5 Ar 2 as claimed.
E.8
Proof of Observation
Proof. Using properties of the floor function, infer that,
[v]g men
1
loy
S y min
log
T-
m2i
1-8
1- 8
U.
25

---

and,
log
lok
1
[lgg
mann
min
001 -8).
1-8
1-6
E.9
Proof of Lemma 10
Proof. We proceed by induction
Base Case. For the base case, consider t = S 1. By definition, have 0 (S + 1, = (S + u.).
Inductive Step. For the inductive step, we consider S S. We first see that,
n (t, u) = o + +, lu + (t 8, a)))6c
S
u Pt(( s,))delg)
= [u+ Pa(1 8, a000 + Σ
Pa(s's 8,a)6
s'=1+1
$ + Σ Pa s,a)
9.0 n (f, u).
The first inequality used the induction hypothesis and the second inequality used the fact that [x1g S
We also see that,
0 (t, = 0n (t - 1, Pa(t 8, a)
2 NN (t Iu Pt(t s, s.a00)lg) (1 (1- 8)5-
9.
Iu + Pa(l 8,0)0el + Σ
Pa(s's 8, (1 - 575-1 (1-0)5-1
8'=+11
(1 8)u (1- Σ Pa s,, (1 -15-
N. (t, u) 8-5-141.
The first inequality used the induction hypothesis and the second inequality used the fact that [glg 2 x 8 and the fact that all rewards and values are non-negative allowing us to add
(1 - 8)-ftct to the other value demands.
E.10 Proof of Lemma 11
Proof.
We proceed by induction on h. Let (s, v) E S be arbitrary.
Base Case. For the base case, we consider h H Since Lulg S immediately see,
(s, X(l0) $ X(rso) Cir41(s
Inductive Step. For the inductive step, we consider h < H. If CH v) co, then trivially Cz (u]g) (s, v). Instead, suppose that (s, v) < 00. Let be solution the optimality
26

---

equations for M so that (s, (s, < co. Since (s,s,) v) < oo, we know that (a", v*) vA( E (8, By the definition of (8, v). we know that,
hv (1,ra(s, a =m(ss) P. s, 2 Lllg.
For each s' S, define ig def L and recall that ug V. We first observe that,
2a h (1,ra(1,,,")) =r((s, Σ Pa(s' 8, Luwla
2 rr, + Σ 1,, -
|
2 ml(s,a)) + Σ Ph(s' s,a)us (1 (1-6)
= of (1, ())
The second inequality used the fact that all rewards are non-negative. Then by Lemma 10,
3.. 4.v (L,
2 e. (1, (a),,aa))][ ))( 5)5
2 h,v- (1, a a')) 5)551
z Lmlg (1 - 8)s+1
= x((vlg).
Thus, (a" E (s, Lulg).
Since us E V, the induction hypothesis implies that (s', S C (p.i(s',0g) = (5 The optimality equations for M then imply that,
min ca(s,a)+1 + ((RA60) (s,a), Chu1 (6', (5, (T.Pa(ssa)) (a.)))
07 (v]g)
$ (c)(),a))+ + ((Pa66' |s,a"), Chtz (5l (d. s
<a((,,a")+ + (PPa (8,()' (8' ) (T,
us)
The first inequality used the fact that va) E (s, v). The second inequality relied on f being non-decreasing and the induction hypothesis. The penultimate equality used (TR).
This completes the proof.
E.11
Proof of Lemma 12
Proof. We proceed by induction on h. Let (s, 6) E S be arbitrary.
Base Case. For the base case, we consider h H+1. By definition and assumption, Óg (1, 0) = X(e50) < co. Thus, it must be the case that 0 0 and so by definition V 6) = 0 ' ú.
Inductive Step. For the inductive step, we consider h < H. As the proof of Lemma 5, we know that TT. (s, v) = (a, v) As 0) and for any s' S with (s ss,a) > that (s' var) < oo. Thus, the induction hypothesis implies that Vir (s', (x) 2 01r(1 ()(5+1)(H-)) for any such
27

---

s' E S. By the policy evaluation equations, we see that,
(s(s, a) + - Puls' s,a) 0z))
5
2 a)) + Σ PM(s' s,0)0, (1-8))1++++ 6)(8+1)(H-))
o (1. o)) 8)(8+1)
2 o (1. a)) - - -)(8+))(
2 ö(1 - 5+ (1-))
= =0(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 An 6) and K, C, (1, (s,, a)) 2 x(0) = 6(1 - 8)5+1.
This completes the proof.
E.12 Proof of Theorem 3
Proof.
B for all é E V. then Chs > B since otherwise we would have (so, Lvlg) S Ci (50, v) S CM S B by Lemma 11. Thus, if Algorithm 5 outputs "infeasible" is correct.
Correctness. If Cf
On the other hand, suppose that there exists some i E v for which Ci 0) S B. By standard MDP theory, we know that since æ E 11 is a solution to M, it must satisfy the optimality equations. In particular, ČT (so. 8) = (su, v) < B. As in the proof of Theorem 1, since Cß2 = ČT (su, i), we see that there exists क E ITP for which Cj S and so VM -00.
Since VM is the value of some deterministic policy, Lemma 3 implies that VM E V. Thus, Lemma 12 implies that ViT (Su: [V 2 [V (1 ()(+1) 2 V1 8)($+1)H+1 (1 (S+1jø=T] ((++))++1 2 (1 - c) and CT (so. VM) I (so. VM) I B. Consequently, rumning with initial state 5p (so, [V)lgg) is optimal solution (CON). In either case, Algorithm is correct.
Complexity. For the complexity claim, we observe that the running time of Algorithm 5 is O(HS3 To bound [VI, observe that the number of vmin-scaled powers of 1/(1 8) required to capture the range [0, Hrma) is at most one plus the largest power needed, which
H Hrmaz)
H Hrmaz //loo(//((( - 6)))
((1og1/1-6))
= Olog(
Umin
Umin
Hrmaz )/8)
Olog(
Unin
HTmoz
Olog(HS
)/e)
Punn Tmin
=(H2 log(
Tmaz
}/e),
Pmint Tmin
by definition of and the fact that log( - = - llog(1 - -5) 2 -log(e 00) = 8. Moreover, |u]| = =(D)).
We see that the range of the rounded sums is at widest [0, 2 man) since for any + rounding non-negative sums is least 0 and,
[Irn(s, + PA(1 | 8,0)&1Jg +...+ Pa(1 s, S sn((s,))+ + Σ Pa(s' 8,a),.,
28

---

which is at most 2Hr r maz- Then, the same analysis from before shows that the number of scaled pow-
ers of 1/(1 5) needed to cover this interval is O(V)) Thus, we see that ((V))2))) Og113
O(H 5 log( Pmon )3/(²) implying that the total run time is O(H S SSAAloog Aloo
) Yiaa
//30 as
Pmnn Pmin
Pmann Pman
claimed.
F
Extensions
F.1 Stochastic Costs
Suppose each cost (s a) is replaced with cost distribution (s a). Here, we consider finitely most m N. Then, instead of the agent occurring
supported cost distributions whose supports cost en (s, a) upon taking action a in state s at time h, the agent occurs a random cost C₁ ~ Cn (s. a). Generally, this necessitates histories be cost dependent, and so the policy evaluation equations become.
(T.) = (s(ssa) + Σ Onld s.() C',
(CPE)
Cover MDP. This implicitly changes the definition of V since the histories considered in the definition must now include cost history. Since the cost distributions are finitely supported, remains finite set. The main difference for M is that the future value demands must depend on both the immediate cost and the next state. This slightly changes the action space:
Un(s, def (a,v) E Ax Vmx (r)ss,a) + EChld' Cile' s. s s, 2 20..
Bellman Updates. In order to solve 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 that g's recursion is now two dimensional.
Definition 11 (TSRC). We call a criterion time-space-coot--eccrsse (TSRC) if C3 = CT (s0) where C H++ (.) 0 and for any h [H] and Th Hr letting (N((T) and (Th).
C% = (s, + ((Crle' (oo(c'(ssaa,... Px(s, ss,a), Ch+ (Th, a, c, ss)) e,0,)
(22)
In the above, d' (s. a) and s' as, We now require that f be computable in 0(mS) Ta." time. We also require that the term above is equal to gh (1, where, 9h 27""(m + 1, = 0. Lh (k: S 5 1) 9% Th.0 (k- 1, 1),, and,
gh Th.a (k. 1) = a (g (Cn(ex 8, 8, Pa(1 s, a), Ch+i (Th, a, 1)) 9hh Th (k,
(23)
In the above, we assume C the kth supported cost of Ch, a). Again, both a, 3 can be computed in ((1) time, but now a(B(y, x), = x whenever ( E y.
Our examples from before also earry over to the stochastic cost setting.
Proposition 5 (TSCR examples). The following classical constraints can be modeled by a TSCR cost constraint.
1. (Expectation Constraints) We capture these constraints by defining a(x, v) def x + and (xx 2) def
zyz.
2. (Almost Sure Constraints) We capture these constraints by defining o<xx de and [(x, y, 2) [x OA 0]2.
max(x,)) v)
3. (Anytime Constraints) We capture these constraints by defining alz, y) de max(0, max(x, y)) and ((x,y,2) def
x DAA > Ojz.
We can then modify our approximate recursion from before.
29

---

Definition 12. We define, 2 (m + 1, 1,1,u) der X(uzo), 2h S 1, uu) def gh.e (k: 1, 1, u) and fort - S,
del
min a ( (Ch(ex 8, Pa(t 8, 0, Ch+1 1 (t, (k,))) VV
9h.6 (h,
(24)
Fh. (k, [1,4+1, 1, lu + Ca(cn 8, Pa a)wx.elg))
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 use å def Mmm++1)+T We
also further relax our lower bounds to k(v) 8(mS + 1) and v(1 - 8yms+1 respectively. Our running times correspondingly will have m terms now.
F.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 finite horizon problem where the finite horizon H defined so that - and 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 O-cost actions are always available that the policy can guarantee feasibility after the effective horizon has passed.
xe 7 Tma S é'. By choosing e'
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.
F.3 Faster Approximations
We can significantly improve the running time of our FPTAS. The main guarantee is given in Corollary I. They key step is to modify Algorithm 3 to use the differences instead of the sums. is easy to see that this is equivalent since,
rn(s,a) EPa(''
Pu (, 2 = PPi(s' Pa(s' (,,)) (s(ss)))
Since rounding down the differences make them larger, it becomes harder to be below TA a). Consequently, we now interpret к as upper bound for (s, a) instead of lower bound The approximate dynamic programming method based on differences can be seen in Definition 13.
Definition 13. Fix a rounding down function L:gg and upper bound function н. For any h E [H], E S,S, U. V, and R, we define, (S + 1, X(uSm(m((saa)) and for S.
In (1, u) def
min a (3 (P) 8, 8, Ch+1 vl)) (1 + ( a))):))) (DIF) NEV
The recursion is nearly identical to the originally, and unsurprisingly. it retains the same theoretical guarantees but the reverse order. The guarantees can be seen in Lemma 13, which is straightforward prove following the approach the proof of Lemma 1.
Lemma 13. For any t E [S + 1] and u E E, we have that,
(t, u) min 9h (t) vEVS
(25)
S.L.
0 h (t, & ())),
def [Lu Ph(t 8, a)urla .... PA(S (((S)s.0)) a.
where 5,20 (1,
The difference version so far does not help us get faster algorithms. The key is in how we use it. Since the base case the recursion is r4 (8, a) and not v, we can compute the approximate bellman update for all v's simultaneously. This ends up saving us a factor of [V] that we had in the original Algorithm The new algorithm is defined Algorithm 6. The inputs to the recursion are define in Definition 14.
30

---

Algorithm 6 Approx Solve
Input: (M,C)
1: CH (8, v) < X{v50) for all (8,0) E
2: for h 4- H down
do
3:
for s E S do
4:
for a E A do
5:
Ih ( fort S down 1 do
+ 1,
+ ((us Yu E Uh
6:
7:
for ip do
8:
6r,09h (t,u) + (DIF) for v E do
9:
a", (s,
miimaeAh(ss.)) (1,u)
11:
Ta (s 1) t a
return and C*
Definition 14. For any h E [H], E S, and E A, we define "
(1) def V and for any E [S],
ú, (1 " +1
U
{ Ph(t a.)uug))))
(26)
weV (A)
Proposition 6. The running time of Algorithm 6 is O A)
Corollary (Running Time Improvements). Using Algorithm 6, the running time of our additive- FPTAS becomes S4 Ar Armax/E"), and the running time of our relative-FPTAS becomes O(H A log( Tmiin Pmiin )3/62) (mms=_)//e"))
Ymaz
Although the running times our clear from removing the factor of [V], we need slightly alter our approximation schemes for this work. First, need to use k(rn(s, a)) def (s, a) + for the additive approximation. The proof from before goes through almost identically.
Approximation Details.
However, for the relative approximation, choice of upper bound can ensure enough feasibility.
Thus, we simply use s(ra (s, a)) def (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: 1-x1g 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 E / + 1] and (s,v) S. Cs,,s, [o(1 8) () (8,
The idea is that since no fixed upper bound can capture arbitrary input values, we simply input relative values. Then, the fcasibility part of Lemma 11 goes through before. The proofs mostly remain the same, but the rounding must again change. We must now start at the smaller Umin that is the original Umin scaled by a factor of (1 - 8)d to ensure that [Va (1 5) is in V. This makes ÿ larger, but not by much argued in previous analyses.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We believe the claims made are accurate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We point out our assumed reward bounds and note they are unavoidable under
worst-case analysis.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
Our paper provides all proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [NA]
Justification:
Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ Seaiiic/guides/Codeee
wwwsssssssolloooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.coo. wttpccccpppccceeeecceccecccccctt gwwpc//ggg//////eeeo /CodeSubeieeeeeeee /ttee//uuideeeoeeuuumuiiiiiiiii cetoommsssionni ssionnollllo oniioniyll for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
34

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer: [Yes]
Justification:
We beleive our paper follows the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss in the introduction and conclusions potential positive impacts of our work. We do not believe there are any direct negative impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any releasable materials.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper is purely theoretical and does not include any experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper is purely theoretical and does not any crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper purely theoretical and does not use any crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "RuKZBzzJk5", "reviewer": "Reviewer_pADD", "summary": "The paper provide a novel polynomial-time algorithm for finding near-optimal deterministic policies in constrained MDPs with a large family constraints beyond expectation. The algorithm first considers in the dual covering problem minimizing cost for constrained value. The new problem is then viewed as solving a new augmented MDP with \"value demands.\" This MDP is more prone to approximate algorithms via approximate dynamic programming and careful rounding. In the process, the class of constraints supported by the algorithm (TSR constraints) is a step towards the class of constraints that allow polynomial-time algorithms.", "questions": "Please see the weaknesses. Also I wonder whether the proof techniques to focus on covering problem in cMDPs, and approximate dynamic programming are common in the literature. If so, more citations could be useful.", "limitations": "The paper does a good job outlining the limitations.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper solves a significant problem in the area. Apart form the new tractability result, the TSR class for constraints includes most kinds of constraints of interest and only excludes the ones that are known to be impossible to solve. This is a step towards classification of constraints that admit FPTAS.\n- I am not an expert in the area, and I cannot comment on novelty of techniques used by the paper in confidence. However, I find them not only novel, but also potentially inspiring for RL theory.\n- The paper is well-written and easy to follow despite its technical complexity.", "weaknesses": "I think more discussions on the optimality/tightness of each step of algorithm design would benefit the paper. I suppose some of the operations/steps are specific to this problem and therefore investigation of the optimality the whole algorithm might require a lot effort possibly in another paper. However, I wonder if for some of the steps we can have insights on whether the operation is optimal or not. For example, if I am not wrong, switching to the covering problem was harmless, same for the reduction to the value augmented MDP. I am not sure how optimal handling the augmented MDP is. However, I guess due to the MDP formulation some existing results may apply. Perhaps the authors can provide some insights on each of the steps.\n\nMinor comments:\n-  Some small comments in the paper for quantities that will be discussed later would be welcome. Specifically, in the discussions on tractability of solving the cover MDP the lack of knowledge of the set $V$ is not brought up. Only later in the paper this issue is addressed.\n \n- The Objective of the cover MDP could be better clarified. The objective appears to be determined by the function $f$ as opposed to the conventional summation and expectations of value functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! The main techniques used in this paper are packing-covering equivalence (essentially, strong duality), dynamic programming, and rounding. These are general techniques found in standard approximation algorithms textbooks such as the book “The Design of Approximation Algorithms” cited in our paper. Moreover, dynamic programming is crucial to most of MDP theory. How we applied these techniques, such as creating a covering MDP and applying dynamic programming to the action space, is unique to this problem. We are unaware of any other paper that uses these general techniques in the same way. \n\nAs for the optimality of each step of our reduction, we note no step harms the optimality of the solution except for the rounding steps. In terms of fine-grained time complexity, it is hard to say whether reducing to the covering problem somehow limits how fast algorithms could be. Resolving that question would require a time complexity lower bound for both the original and the covering problem for comparison. Proving such lower bounds would be fairly complicated and is far beyond the scope of this paper, but would be very interesting for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X8yKkeSmPo", "reviewer": "Reviewer_iqFB", "summary": "The paper presents an algorithm that computes deterministic policy for constraint RL. The work is majorly theoretical. The proposed algorithm for the worst-case analysis achieves the best approximation guarantees. Their approach incorporates ideas from state augmentation with value function, approximate dynamic programming, and time-space rounding.", "questions": "- Why is Proposition 2 a proposition but not just an example?\n- remove line 144. It creates more confusion than helps to understand. E.g., use of not defined terminology of covering MDP now and value augmentation. \n- In line 148, what does \"this covering program\" mean? Does it correspond to the reversed objective?\n- why value-demand augmentation and not value-function augmentation?", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Computes a near-optimal policy\n- Consider a diverse range of constraint functions\n- Algorithm belongs to FPTAS", "weaknesses": "- Motivation sounds weak or rather superficial. In the case of stochastic policies, why can one not apply the mean of the policy to get a deterministic behaviour?\n\n- All the Algorithms are difficult to parse/not self-contained. What does it mean if a definition takes an input of M, C?  Maybe I missed it somewhere, what is V^s? Would be good if you can define the symbols in the algorithm at least input.\n\n- Theoretical statement doesn't contain assumptions. It would be good if you could incorporate assumptions in the theoretical statements, especially in propositions and theorems.\n\n- Finite state-action space, perhaps rather difficult to then have meaningful applications among the ones that the authors mention in the first paragraph, e.g., autonomous driving. On a high level I am wondering, since you are also solving for a finite horizon case, why would one not apply an open loop MPC type approach for a constraint finite horizon application (that also results in deterministic policies and is polynomial time for finite H).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! \n\nWe first address the weakness comments:\n1. We do not believe our motivation is weak as it comes from two longstanding lines of work: (1) deterministic policies, which are critical for multi-agent coordination and for autonomous vehicles [Hong, Geißer], and (2) Anytime/Almost-Sure constraints which are prevalent in any task with resource consumption and any safety critical system [McMahan, Castellano]. More applications, including medicine, can be found in our first paragraph. The fact that simple derandomization strategies fail is the topic of an entire line of work that started with Feinberg in 2000 and culminated with our paper. It is difficult to fully capture the intuition from this line of work, but one way to see that any simple derandomization approach fails is to note that stochastic policy computation is in P, but deterministic policy computation is NP-hard as mentioned on line 31. As such, it is immediate that no easy derandomization strategy can exist unless P = NP. We emphasize again that we do not only solve the deterministic policy problem but also solve the anytime and almost-sure-constrained problems, which is a major contribution of our paper. The fact that we can solve both of these problems with one framwork is a major strength of our work.\n2. The definition of the covering MDP depends on M and C. Consequently, we used Definition(M,C) to indicate that this particular M and C should be used to construct the covering MDP; we will clarify this in the writing. $v_s$ is defined informally on line 165, formally on line 168, and compactly in definition 2; note we use standard notation for indexing a vector. To our knowledge, all quantities are defined according to standard theory convention; if there are any undefined symbols, we are happy to fix them.\n3. Perhaps surprisingly, the only assumption we need in nearly all of the paper is that the cost function is TSR. The only other assumptions are the reward assumptions that are explicitly stated in the two approximation theorems, Theorem 2 and 3. Thus, all theoretical statements do contain their assumptions. We ask the reviewer: what assumptions do you feel have not been included?\n4. We completely agree it would be nice to extend beyond the tabular case in future work. Since not even the tabular setting has been resolved until now, our work serves as an important first step to devising more practical algorithms in the future. \n5. Since past approaches have been unable to solve this problem til now, we attempted a different approach inspired by the approximation algorithm community to achieve provable guarantees.\n\nTo your questions:\n1. They are not examples because they need non-trivial mathematical proof to verify they satisfy the TSR condition. Anytime constraints, especially, were non-trivial to massage into the TSR form. The proofs are given in the appendix.\n2. Yes, the covering program corresponds to flipping the objective and the constraint similarly to duality. Packing and covering programs are common in optimization, especially combinatorial optimization, so we used those terms to connect to that literature.\n3. The value demand is a total value goal the agent must hit; it is different from the actual value it has accumulated. We use the term demand just as in general optimization and network flow theory to indicate an amount requirement on a resource.\n\nReferences:\n\nFeinberg, Eugene A. “Constrained Discounted Markov Decision Processes and Hamiltonian Cycles.” Mathematics of Operations Research, vol. 25, no. 1, 2000\n\nGeißer, Florian, et al. \"Optimal and heuristic approaches for constrained flight planning under weather uncertainty.\" Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30. 2020\n\nHong, Sungkweon, et al. \"An anytime algorithm for chance constrained stochastic shortest path problems and its application to aircraft routing.\" 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021\n\nMcMahan, Jeremy, and Xiaojin Zhu. \"Anytime-Constrained Reinforcement Learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8y0nXldmbi", "reviewer": "Reviewer_DPnW", "summary": "The paper proposes a novel algorithm for constraint MDPs whose constraints have TR properties. The algorithm converts the original problem to an unconstraint MDP. To address the challenge of high complexity of the proposed approach, the method discovers that for constraints with TSR properties, it can accelerate the Bellman update. Furthermore, the paper proposes the approximate version of the problem by rounding the values effectively.", "questions": "1. Could you provide examples that needs constraint MDP with TSR (TR) constraints while cannot be modeled as a single MDP problem with cleverly designed rewards?\n2. Is there existing works  using the same problem definition?", "limitations": "1. The complexity is still high.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The analysis is comprehensive and the logic is strong.\n2. The fast bellman update for TSR constraints and the approximate rounding are interesting but very useful in practical computation.\n3. The overall writing is good, esp. for math notations and explanation.", "weaknesses": "1. The problem extends knapsack problems to constraint MDP. It is unclear if this problem is novel or is a common interest in the RL and control community.\n2. It is hard to think of practical problems that fit the setting on TSR, could you provide examples that needs constraint MDP with TSR (TR) constraints while cannot be modeled as a single MDP problem with cleverly designed rewards?\n3. The overall algorithm and the improvement are important but also seems like straight-forward extensions on the basic algorithms. The overall complexity is still very high at last.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! Although we introduce TSR constraints, they generalize the main constraints studied by the constrained reinforcement learning (CRL) literature, including expectation, almost sure, and anytime constraints. CRL is an entire subarea of RL that was born as early as 1981 [Kallenberg] and is often used by the safe RL community. Since CRL has hundreds of impressive works, we cannot easily convey the many motivations for constrained problems. Instead, we give an example of anytime constraints: self-driving cars must not run out of fuel. Here, it is easy to see that reward shaping could only work if we include current fuel levels in the state space, but this would take exponential time [McMahan], which necessitates the constraint formulation of the problem. McMahan and Castellano point out many more applications of anytime and almost-sure constraints. Finding deterministic policies under expectation constraints was first motivated by Feinberg and Schwartz and has been a focus of works on autonomous vehicles [Hong, Geißer]. Many other applications, including medicine, can be found in the first paragraph of our paper.\n\nWe note the TSR constraints, and even the constraints they generalize, have a very different mathematical structure from the knapsack problem. Adding stochasticity to the knapsack problem increases the complexity due to the non-trivial adaptivity gap, which forces optimal solutions to take the form of adaptive “policies” rather than a simple set of knapsack items [Dean]. Introducing MDPs only further increases the complexity [McMahan]. Consequently, our problem is non-trivial compared to the knapsack problem, and our methods are not straightforward extensions of knapsack algorithms. Moreover, our algorithm is the first ever provable approximation algorithm for almost sure and anytime constraints, let alone an FPTAS, which is known to be the best approximation guarantee possible. Furthermore, our algorithm is the first ever FPTAS for expectation constraints for general MDPs since the NP-hardness result from nearly 25 years ago [Feinberg]. Although the complexity is arguably high, our method is still the first provable approximation algorithm for these problems and gives insights into breaking through the exponential time barrier. We hope these insights will lead to even faster algorithms in future work.\n\nReferences:\n\nDean, Brian C., Michel X. Goemans, and Jan Vondrák. \"Approximating the stochastic knapsack problem: The benefit of adaptivity.\" Mathematics of Operations Research 33.4 (2008): 945-964\n\nFeinberg, Eugene A. “Constrained Discounted Markov Decision Processes and Hamiltonian Cycles.” Mathematics of Operations Research, vol. 25, no. 1, 2000\n\nGeißer, Florian, et al. \"Optimal and heuristic approaches for constrained flight planning under weather uncertainty.\" Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30. 2020.\n\nHong, Sungkweon, et al. \"An anytime algorithm for chance constrained stochastic shortest path problems and its application to aircraft routing.\" 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021\n\nKallenberg, L. C. M. \"Unconstrained and constrained dynamic programming over a finite horizon.\" 1981.\n\nMcMahan, Jeremy, and Xiaojin Zhu. \"Anytime-Constrained Reinforcement Learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xDHU1YagN2", "reviewer": "Reviewer_SLVm", "summary": "The authors propose an algorithm that efficiently computes near-optimal deterministic policies for constrained reinforcement learning (CRL) problems. The proposed algorithm comprises three ideas: 1) value-demand augmentation, 2) action-space approximate dynamic programming, and 3) time-space rounding. Under some assumptions, their algorithm constitutes a fully polynomial-time approximation scheme (FPTAS) for a few 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.", "questions": "[Q] Could you discuss the computational complexity of the proposed algorithm while referring to those in SOTA algorithms (for constrained RL problems based on expectation)?\n\n\n### Minor Comments\n- Line 117-118: (SR) $\\rightarrow$ (TSR)", "limitations": "The authors have slightly addressed the limitations. There is no discussion regarding potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "**Novelty.** I think this paper brings new insights into the field of safe RL (based on constraints) or CMDPs. I think the authors provide unique views for addressing or solving constrained RL problems. \n\n**Cover MDP.** It is an interesting approach to formulate a CMDP that covers diverse formulations for constrained RL. There have similar attempts as I will mention in Weakness, the proposed one is novel as far as I know.\n\n**Algorithm.** I think the proposed algorithm is technically sound. It is a good property to solve diverse problems using a single algorithm in a reasonable computational time.", "weaknesses": "**Unclear difference from previous work.** I do not think this paper clearly conveys the differences or contributions compared to previous work. I think this paper is not written after fully surveying existing work. Within the several major claims the authors make, there are several existing works where similar attempts were made. For example, in safe RL literature, there have been several papers on state augmentation or generalized formulations:\n- Sootla, Aivar, et al. \"Sauté RL: Almost surely safe reinforcement learning using state augmentation.\" ICML, 2022.\n- Wachi, Akifumi, Xun Shen, and Yanan Sui. \"A Survey of Constraint Formulations in Safe Reinforcement Learning.\" IJCAI (2024).\n\nI know existing works have not made the same contributions as this paper, but it is significant to properly make the differences clear rather than exaggerate the contributions.\n\n**Theoretical results.** Though I think the theoretical results are good, I think it is better to compare the theoretical results with existing ones. I understand no existing algorithm can solve diverse safe RL problems, unlike the proposed ones. However, there are a bunch of theoretical results on CMDPs based on expectations (and recent papers derive the upper bounds for other problem formulations). It is necessary to compare the upper bound or strength of the assumptions between the SOTA algorithm and the proposed ones.\n\n**Experiments.** I highly respect theoretical ML papers, but I think this paper needs empirical evaluation because the main claim is efficient computation. The algorithm is complicated and it is questionable whether the proposed algorithm actually works well even in toy problems.\n\nIn summary, this paper presents novel and interesting insights, but this paper is not written based on existing research. Thus, the contribution is not clear and I feel the contributions of this paper are exaggerated. Also, the theoretical and empirical advantages are not clear, which should be clearly written or supported by additional work. Therefore, I do not think this paper is ready for publication and resubmit to another venue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! We address the concerns about the contributions of our paper. Our paper is highly focused, addressing only the question proposed on line 29 of our intro: “Can near-optimal deterministic policies for constrained reinforcement learning problems be computed in polynomial time?” Since providing an FPTAS does answer this question, we believe our claims are not exaggerated. We use the term \"efficient\" as a synonym for polynomial time, which is a convention in computer science, especially in theory works; given this convention, it is accurate to say an FPTAS is efficient. Being a theory work, we did not claim that our algorithms would work well in practice; the only goal of this paper is to derive new theoretical insights as a first step to devising practical algorithms in the future, as stated throughout the paper [21, 29, 58, 316]. Furthermore, we emphasize our results answer three open complexity questions: we prove polynomial-time approximability for 1) anytime-constrained MDPs, 2) almost-sure-constrained MDPs, and 3) deterministic policies for expectation-constrained MDPs, which has been open for nearly 25 years. \n\nFor the concerns of past work, we compared many past methods in detail in the marked prior work paragraph [41], where we pointed out each method's time complexity, whether they produced infeasible policies, and whether the policies were suboptimal.\nWe emphasize our work studies the computational complexity of finding deterministic policies for a large class of constraints. Importantly, as stated on line 31 of our intro, it is well known that the computation of stochastic expectation-constrained policies is in P, whereas our problem is known to be NP-hard [Feinberg, McMahan]. Consequently, stochastic policy works address a problem in a completely different complexity class, so they cannot be fairly compared to our setting. Similarly, works on learning complexity, including both papers you pointed out, do not apply to our work on computational complexity, and generally must allow constraint violation for learning, unlike our setting where feasibility is critical. Instead, we discussed the papers by McMahan and Castellano, which cover the same constraints as those papers, but from the computational complexity perspective, which is related to our work. Given the space limitations, we tried to cite only the most relevant works concerning the computational complexity of our problem. We were unable to include other interesting papers on deterministic policies, notably Feinberg’s full line of work, that we plan to include in the final paper.\n\nReferences:\n\nCastellano, Agustin, et al. \"Reinforcement learning with almost sure constraints.\" Learning for Dynamics and Control Conference. PMLR, 2022\n\nFeinberg, Eugene A. “Constrained Discounted Markov Decision Processes and Hamiltonian Cycles.” Mathematics of Operations Research, vol. 25, no. 1, 2000\n\nMcMahan, Jeremy, and Xiaojin Zhu. \"Anytime-Constrained Reinforcement Learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Since the reviewers agree with the mathematical correctness of our results, we emphasize the significance of our contributions. 
To summarize, our general framework provides answers to not just one but three open complexity questions spanning two longstanding lines of work: we prove polynomial-time approximability for 1) anytime-constrained MDPs, 2) almost-sure-constrained MDPs, and 3) deterministic policies for expectation-constrained MDPs, which has been open for nearly 25 years [Feinberg]. Before our work, no provable approximation algorithms had been known for any of these problems, absent a special case of expectation constraints [Khonji], and we designed algorithms satisfying the conditions of an FPTAS, which is the best possible approximation guarantee.

Computing optimal deterministic policies under expectation constraints was shown to be NP-hard in 2000 [Feinberg]. Since then, only one work, to our knowledge, has successfully derived a non-trivial approximation algorithm, but only for the constant horizon setting [Khonji]. Our paper is the first to fully settle the computational complexity of deterministic policies since the original hardness result nearly 25 years ago. Moreover, we provide an FPTAS, known to be the best possible approximation guarantee. 

Since as early as 2011 [Xu], the literature has argued for alternative constraints to handle many real-world applications. Recently, there has been a strong push for anytime [McMahan] and almost-sure constraints [Castellano]. Our work is also the first to provide any provable approximation algorithm for these constraints, let alone an FPTAS. Solving these newer constraints alone is a notable contribution of our work, and our general framework can solve constraints beyond even these. 

References:

Castellano, Agustin, et al. "Reinforcement learning with almost sure constraints." Learning for Dynamics and Control Conference. PMLR, 2022.

Feinberg, Eugene A. “Constrained Discounted Markov Decision Processes and Hamiltonian Cycles.” Mathematics of Operations Research, vol. 25, no. 1, 2000

Khonji, Majid, Ashkan Jasour, and Brian C. Williams. "Approximability of Constant-horizon Constrained POMDP." IJCAI. 2019

McMahan, Jeremy, and Xiaojin Zhu. "Anytime-Constrained Reinforcement Learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2024

Xu, Huan, and Shie Mannor. "Probabilistic goal Markov decision processes." IJCAI Proceedings-International Joint Conference on Artificial Intelligence. Vol. 22. No. 3. 2011.

Meta-review: The paper presents novel theoretical results in finding near-optimal deterministic policies in constrained RL. The reviewers generally appreciate the theoretical achievement and the relevance of the problem. There are concerns that the work is leaning heavily towards computational complexity and planning communities, and the authors are encouraged to make more connections to closely related topics in the NeurIPS community.
Decision: Accept (poster)