Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time

Authors: jeremy  mcmahan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:55:53

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.

Main paper: 
 introduction: 
 Constrained Reinforcement Learning (CRL) traditionally produces stochastic, expectationconstrained policies that can behave undesirably -imagine a self-driving car that randomly changes lanes or runs out of fuel. However, artificial decision-making systems must be predictable, trustworthy, and robust. One approach to ensuring these qualities is to focus on deterministic policies, which are inherently predictable, easily implemented [19] , reliable for autonomous vehicles [30, 23] , and effective 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 a constrained Markov Decision Process (cMDP) denoted by M . Let C represent an arbitrary cost criterion and B be the available budget. We focus on the set of deterministic policies denoted by Π D . Our objective is to compute:max π∈Π D V π M s.t. C π M ≤ B,where V π M is the value and C π M is the cost of π in M . This objective generalizes the example of a self-driving car calculating the fastest fixed route without running out of fuel. Our main question is the following:Can near-optimal deterministic policies for constrained reinforcement learning problems be computed in polynomial time?Although optimal stochastic policies for expectation-constrained problems are efficiently computable [3] , the situation drastically changes when we require deterministic policies and general constraints. Computing optimal deterministic policies is NP-hard for most popular constraints, including expectation [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 with a 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 a single backward pass.Past work. Past approaches fail to simultaneously achieve computational efficiency, feasibility, and optimality. Optimal and feasible algorithms, albeit inefficient, utilize Mixed-Integer Linear Programs [17] and Dual-guided heuristic forward searches [29] for expectation-constraints, and cost-augmented MDPs for almost sure [11] 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-time approximation scheme (FPTAS) [49] is known for expectation constraints, but it 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 timespace 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 as chance constraints [51] , are provably inapproximable, TSR seems pivotal for efficient computation. Overall, our general framework answers three open complexity questions spanning two longstanding lines of work: we prove polynomial-time approximability for 1) anytime-constrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained 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 space-recursive nature of the criterion, we can efficiently approximate the Bellman operator with dynamic programming. Finally, rounding value demands result in approximation errors over both time and space, but carefully controlling these errors ensures provable guarantees.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 a 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 a similar general dynamic programming framework for the more complex MDP setting.Constrained RL. It is known that stochastic expectation-constrained policies are polynomial-time 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 stochastic expectation-constrained policies [14, 9, 2, 12, 5] and solving chance constraints [47, 53] , which capture the probability of entering unsafe states. Performing learning while avoiding dangerous states [53] is a special case of expectation constraints that has also been studied [42, 44] under 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] . 
cost criteria: 
 In this section, we formalize our problem setting. We also define our conditions for cost criteria.Constrained Markov decision processes. A (tabular, finite-horizon) Constrained Markov Decision Process (cMDP) is a tuple M = (S, A, P, r, c, H), where (i) S is the finite set of states, (ii) A is the finite set of actions, (iii) P h (s, a) ∈ ∆(S) is the transition distribution, (iv) Interaction protocol. The agent interacts with M using a policy π = (π h ) H h=1 . In the fullest generality, π h : H h → ∆(A) is a mapping from the observed history at time h to a distribution of actions. In contrast, a deterministic policy takes the form π h : H h → A. We let Π denote the set of all possible policies and Π D denote the set of all deterministic policies. The agent starts at the initial state s 0 ∈ S with observed history τ 1 = (s 0 ). For any h ∈ [H], the agent chooses an action a h ∼ π h (τ h ). Then, the agent receives immediate reward r h (s h , a h ) and cost c h (s h , a h ). Lastly, M transitions to state s h+1 ∼ P h (s h , a h ) and the agent updates the history to τ h+1 = (τ h , a h , s h+1 ). This process is repeated for H steps; the interaction ends once s H+1 is reached.r h (s, a) ∈ R is the reward, (v) c h (s, a) ∈ RObjective. For any cost criterion C : M × Π → R and budget B ∈ R, the agent's goal is to compute a solution to the following optimization problem:max π∈Π E π M H h=1 r h (s h , a h ) s.t. C π M ≤ B π deterministic . (CON)Here, P π M denotes the probability law over histories induced from the interaction of π with M , and E π M denotes the expectation defined by this law. We let V π M def = E π M H t=1 r t (s t , a t ) denote the value of a policy π, and V * M denote the optimal solution value to (CON).Cost criteria. We consider a broad family of cost criteria that satisfy a strengthening of the standard policy evaluation equations [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 a cost criterion C time-recursive (TR) if for any cMDP M and policyEQUATIONwhere s = s h (τ h ), a = π h (τ h ), and f is a non-decreasing function1 computable in O(S) time. For technical reasons, we also require that f (x) = ∞ whenever ∞ ∈ x.We further say C is time-space-recursive (TSR) if the f term above is equal to g τ h ,a h (1). Here, g τ h ,a h (S + 1) = 0 and for any t ≤ S,g τ h ,a h (t) = α β P h (t | s, a), C π h+1 (τ h , a, t) , g τ h ,a h (t + 1) , (SR)where α is a non-decreasing function, and both α, β are computable in O(1) time. We also assume that α(•, ∞) = ∞, and β satisfies α(β(0, •), x) = x to match f 's condition.Since the TR condition is a slight generalization of traditional policy evaluation, it is easy to see that we can solve for minimum-cost policies using backward induction. Proposition 1 (TR Intuition). If C is TR, then C satisfies the usual optimality equations. Furthermore, arg min π∈Π D C π M can be computed using backward induction in O(HS 2 A) time.Although the TR condition is straightforward, the TSR condition is more strict. We will see the utility of the TSR condition in Section 4 when computing Bellman updates. For now, we point out that the TSR condition is not too restrictive: it is satisfied by many popular criteria studied in the literature. Proposition 2 (TSR examples). The following classical constraints can be modeled by a TSR cost constraint.1. (Expectation Constraints) are captured byC π M def = E π M H h=1 c h (s h , a h ) ≤ B. We see C is TSR by defining α(x, y) def = x + y and β(x, y) def = xy. 2. (Almost Sure Constraints) are captured by C π M def = max τ ∈H H+1 , P π M [τ ]>0 H h=1 c h (s h , a h ) ≤ B. We see C is TSR by defining α(x, y) def = max(x, y) and β(x, y) def = [x > 0]y. 3. (Anytime Constraints) are captured by C π M def = max t∈[H] max τ ∈H H+1 , P π M [τ ]>0 t h=1 c h (s h , a h ) ≤ B. We see C is TSR by defining α(x, y) def = max(0, max(x, y)) and β(x, y) def = [x > 0]y.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 (Inapproximability). Our methods cannot handle chance constraints or more than one of our example constraints. However, this is not a limitation of our framework as the problem becomes provably inapproximable under said constraints [51, 36] .P π M [τ ]>0 H h=1 c h (s h , a h ) ≤ B.Let c(τ ) = H h=1 c h (s h , a h ) denote the cost of a full history τ ∈ H H+1 and let c h:t (τ ) = t k=h c k (s k , a k ) denote the partial cost of τ from time h to time t. Our choice of α and β imply that,C π h (τ h ) = c h (s, a) + max s ′ ∈P h (s,a) C π h+1 (τ h , a, s ′ ). (ASC)To show that C π M satisfies (TR), we prove for all h ∈ [H + 1] and allEQUATIONThen, we see that C π 1 (s 0 ) = max τ ∈H H+1 :EQUATIONand so C π M satisfies (SR). The infinity conditions and non-decreasing requirements are also easy to verify. We proceed by induction on h.• (Base Case) For the base case, we consider h = H + 1. Observe that for any history τ , we have c H+1:H (τ ) = 0 since it is an empty sum. Then, by definition of C π M , we see that C π H+1 (τ H+1 ) = 0 = max τ 0 = max τ c H+1:H (τ ).• (Inductive Step) For the inductive step, we consider h ≤ H. Let s = s h (τ h ) and a = π h (τ h ). For any τ ∈ H H+1 for which P π M [τ | τ h ] > 0, we can decompose its cost by c h:H (τ ) = c h (s, a) + c h+1:H (τ ). Since a is fixed, we can remove c h (s, a) from the optimization to get, max τ ∈H H+1 :P π M [τ |τ h ]>0 c h:H (τ ) = c h (s, a) + max τ ∈H H+1 : P π M [τ |τ h ]>0 c h+1:H (τ ).Next, we observe by the Markov property thatP π M [τ | τ h ] = s ′ P π M [τ | τ h , a, s ′ ]P h (s ′ | s, a). Thus, P π M [τ | τ h ] > 0 if and only if there exists some s ′ ∈ P h (s, a) satisfying P π M [τ | τ h , a, s ′ ] > 0. This implies that, max τ ∈H H+1 : P π M [τ |τ h ]>0 c h+1:H (τ ) = max s ′ ∈P h (s,a) max τ ∈H H+1 : P π M [τ |τ h ,a,s ′ ]>0 c h+1:H (τ ).By applying the induction hypothesis, we see that,max τ ∈H H+1 : P π M [τ |τ h ]>0 c h:H (τ ) = c h (s, a) + max s ′ ∈P h (s,a) max τ ∈H H+1 : P π M [τ |τ h ,a,s ′ ]>0 c h+1:H (τ ) = c h (s, a) + max s ′ ∈P h (s,a) C π h+1 (τ h , a, s ′ ) = C h (τ h ).The second line used the induction hypothesis and the third line used the definition of C π M . 3. (Anytime Constraints) We claim that C π M captures anytime constraints. This is because that for tabular MDPs,P π M [∀t ∈ [H], t h=1 c h (s h , a h ) ≤ B] = 1 if and only if for all t ∈ [H] and τ ∈ H H+1 with P π M [τ ] > 0 it holds that t h=1 c h (s h , a h ) ≤ B if and only if C π M = max t∈[H] max τ ∈H H+1 :P π M [τ ]>0 t h=1 c h (s h , a h ) ≤ B.Our choice of α and β imply that,C π h (τ h ) = c h (s, a) + max 0, max s ′ ∈P h (s,a) C π h+1 (τ h , a, s ′ ) . (AC)To show that C π M satisfies (TR), we show that for all h ∈ [H + 1] and allEQUATIONThen, we see that C π 1 (s 0 ) = max t∈[H] max τ ∈H H+1 :EQUATIONand so C π M satisfies (SR). The infinity conditions and non-decreasing requirements are also easy to verify. We proceed by induction on h.• (Base Case) For the base case, we consider h = H + 1. Observe that for any history τ and t, we have c H+1:t (τ ) = 0 since it is an empty sum. Then, by definition of C π M , we see that C π H+1 (τ H+1 ) = 0 = max t max τ 0 = max t max τ c H+1:t (τ ) 3 .• (Inductive Step) For the inductive step, we consider h ≤ H. Let s = s h (τ h ) and a = π h (τ h ). By separately considering the case where t = h and t ≥ h + 1 in the max t≥h , we see that max t≥h max τ ∈H H+1 :P π M [τ |τ h ]>0 c h:t (τ ) = max    max τ ∈H H+1 : P π M [τ |τ h ]>0 c h:h (τ ), max t≥h+1 max τ ∈H H+1 : P π M [τ |τ h ]>0 c h:t (τ )    = max   ch(s, a), c h (s, a) + max t≥h+1 max τ ∈H H+1 : P π M [τ |τ h ]>0 c h+1:t (τ )    = c h (s, a) + max   0, max t≥h+1 max τ ∈H H+1 : P π M [τ |τ h ]>0 c h+1:t (τ )    = c h (s, a) + max   0, max t≥h+1 max s ′ ∈P h (s,a) max τ ∈H H+1 : P π M [τ |τ h ,a,s ′ ]>0 c h+1:t (τ )    = c h (s, a) + max   0, max s ′ ∈P h (s,a) max t≥h+1 max τ ∈H H+1 : P π M [τ |τ h ,a,s ′ ]>0 c h+1:t (τ )    = c h (s, a) + max 0, max s ′ ∈P h (s,a) C π h+1 (τ h , a, s ′ ) = C h (τ h ).The second line used the fact that c h:h (τ ) = c h (s, a) and the recursive definition of c h:t (τ ). 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 π M . 
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 maximizeV π M subject to C π M ≤ B.However, we could also tackle the problem by reversing the objective:attempt to minimize C π M subject to V π M ≥ V * M . If (CON) is feasible, then any optimal solution π to this covering program satisfies V π M ≥ V * M and C π M ≤ B.Thus, we can solve the original packing program by solving the covering program.Proposition 3 (Packing-Covering Reduction). Suppose that C * M def = min π∈Π D C π M s.t. V π M ≥ V * M . Then, C * M ≤ B ⇐⇒ V * M > -∞. Furthermore, if V * M > -∞, then, arg min π∈Π D C π M V π M ≥ V * M ⊆ arg max π∈Π D V π M C π M ≤ B . (PC)Thus, any solution to the covering program is a solution to the packing program.We focus on the covering program for several reasons. To optimize the value recursively, we would need to predict the final cost resulting from intermediate decisions to ensure feasibility. Generally, such predictions would require strict assumptions on the cost criteria. By treating the value as the constraint instead, we only need to assume the cost can be optimized efficiently. Moreover, values are well understood in RL and are more amenable to approximation [36] . Thus, the covering program allows us to capture many criteria, ensure feasibility, and compute accurate value approximations.Algorithm 1 Reduction to RL Input: (M, C, B)1: M , C ← Definition 2(M, C) 2: π, C * ← SOLVE( M , C) 3: if C * 1 (s 0 , v) > B for all v ∈ 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 is to augment the state space with value demands, (s, v). Then, the agent can recursively reason how to minimize its cost while meeting the current value demand. If the agent starts at (s 0 , V * M ), then an optimal policy for M should be a solution to the covering program. The key invariant we desire is that any feasible policy π for M should satisfy V π h (s, v) ≥ v. To ensure this invariance, we recall the policy evaluation equations [41] . If π h (s) = a, then,V π h (s, v) = r h (s, a) + s ′ P h (s ′ | s, a) V π h+1 (s ′ , v s ′ ). (PE)For the value invariant to be satisfied, it suffices for the agent to choose an action a and commit to future value demands v s ′ satisfying,r h (s, a) + s ′ P h (s ′ | s, a)v s ′ ≥ v. (DEM)We can view choosing future value demands as part of the agent's augmented actions. Then, at any augmented state (s, v), the agent's augmented action space includes all (a, v) ∈ A × R S satisfying (DEM). When M transitions to s ′ ∼ P h (s, a), the agent's new augmented state should consist of the environment's new state in addition to its chosen demand for that state, (s ′ , v s ′ ). Putting these pieces together yields the definition of the cover MDP, Definition 2.Definition 2 (Cover MDP). The cover MDP M def = ( S, Ā, P , c, H) where,1. S def = S × V where V def = v | ∃π ∈ Π D , h ∈ [H + 1], τ h ∈ H h , V π h (τ h ) = v 2. Āh (s, v) def = (a, v) ∈ A × V S | r h (s, a) + s ′ P h (s ′ | s, a)v s ′ ≥ v . 3. Ph ((s ′ , v ′ ) | (s, v), (a, v)) def = P h (s ′ | s, a)[v ′ = v s ′ ]. 4. ch ((s, v), (a, v)) def = c h (s, a).The objective for M is to minimize the cost functionC def = C M with modified base case Cπ H+1 (s, v) def = χ {v≤0} .Covering algorithm. Importantly, the action space definition ensures the value constraint is satisfied. Meanwhile, the minimum cost objective ensures optimal cost. So long as our cost is TR, 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 1 correctly solves (CON) in finite time for any TR cost criterion.Remark 3 (Execution). Given a value-augmented policy π output from Algorithm 1, the agent can execute π using Algorithm 2. To compute V * M as the starting value, it suffices for the agent to compute,EQUATIONThis computation can be easily done given C * 1 (s 0 , •) in O(|V|) time.Input: π1: s1 = (s 0 , V * M ) 2: for h ← 1 to H do 3: (a, v) ← π h (s h ) 4:r h = r h (s, a) and s h+1 ∼ P h (s h , a)5: sh+1 = (s h+1 , v s h+1 )Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not 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. 
fast bellman updates: 
 In this section, we present an algorithm to solve M from Definition 2 efficiently. Although the Bellman updates can be as hard to solve as the knapsack problem, we use ideas from knapsack approximation algorithms to create an efficient method. Our approach exploits (SR) through approximate dynamic programming on the action space.Even if V were small, solving M would still be challenging due to the exponentially large action space. Even a single Bellman update requires the solution of a constrained optimization problem:C * h (s, v) = min a,v c h (s, a) + f P h (s ′ | s, a), C * h+1 (s ′ , v s ′ ) s ′ ∈P h (s,a) s.t. r h (s, a) + s ′ P h (s ′ | s, a)v s ′ ≥ v. (BU)Above, we used the fact that (s′ , v ′ ) ∈ Ph ((s, v), (a, v)) iff s ′ ∈ P h (s, a) and v ′ = v s ′ to simplify f 's input.Observe that even when each v s ′ only takes on two possible values, {0, w s ′ }, the optimization above can capture the minimization version of the knapsack problem, implying that it is NP-hard to compute.Recursive approach. Fortunately, we can use the connection to the Knapsack problem positively to efficiently approximate the Bellman update. For any fixed (s, v) ∈ S and a ∈ A, we focus on the inner constrained minimization over v:EQUATIONWe use (SR) to transform this minimization over v into a sequential decision-making problem that decides each v s ′ . As above, we can use the definition of P to simplify gEQUATIONSince v only constrains the valid (a, v) pairs, we can discard v and use the simplified notation g s,a h,v (t) instead of g (s,v),(a,v) h (t). It is then clear that we can recursively optimize the value of v t by focusing on g s,a h,v (t). To recursively encode the value constraint, we can record the partial value u = r h (s, a) + t-1 s ′ =1 P h (s ′ | s, a)v s ′ that we have accumulated so far. Then, we can check if our choices for v satisfied the constraint with the inequality u ≥ v. The formal recursion is defined in Definition 3. Definition 3. For any h ∈ [H], s ∈ S, v ∈ V, and u ∈ R, we define, g s,a h,v (S + 1, u) = χ {u≥v} and for t ≤ S,g s,a h,v (t, u) = min vt∈V α β P h (t | s, a), C * h+1 (t, v t ) , g s,a h,v (t + 1, u + P h (t | s, a)v t ) . (DP)Recursive rounding. This approach can still be slow due to the exponential number of partial values u induced. Similarly to the knapsack problem, the key is to round each input u to ensure fewer subproblems. Unlike the knapsack problem, however, we do not have an easily computable lower bound on the optimal value. Thus, we turn to a more aggressive recursive rounding. Since rounding may cause originally feasible values to violate the demand constraint, we also relax the demand constraint to u ≥ κ(v) for some lower bound function κ.Algorithm 3 Approx Bellman Update Input: (h, s, v, C * h+1 ) 1: for a ∈ A do 2: ĝs,a h,v (S + 1, u) ← χ {u≥v} ∀u ∈ Ûs,a h (S + 1) 3:for t ← S down to 1 do 4:for u ∈ Ûs,a h (t) do 5: v t,a , ĝs,a h,v (t, u) ← (ADP) 6: a * , Ĉ * h (s, v) ← min a∈A c h (s, a) + ĝs,a h,v (1, r h (s, a)) 7: return (a * , v 1,a * , . . . , v S,a * ) and Ĉ * h (s, v) Algorithm 4 Approx Solve Input: ( M , C) 1: Ĉ * H+1 (s, v) ← χ {v≤0} for all (s, v) ∈ S 2: for h ← H down to 1 do 3: for (s, v) ∈ S do 4: â, Ĉ * h (s, v) ← Algorithm 3(h, s, v, Ĉ * h+1 ) 5: π h (s, v) ← â 6: return π and Ĉ * Definition 4. Fix a rounding function ⌊•⌋ G and a lower bound function κ. For any h ∈ [H], s ∈ S, v ∈ V, and u ∈ R, we define, ĝs,a h,v (S + 1, u) = χ {u≥v} and for t ≤ S, ĝs,a h,v (t, u) def = min vt∈V α β P h (t | s, a), C * h+1 (t, v t ) , ĝs,a h,v (t + 1, ⌊u + P h (t | s, a)v t )⌋ G . (ADP)Fortunately, the approximate version behaves similarly to the original. The main difference is the constraint now ensures the rounded sums are at least the value lower bound. This is formalized in Lemma 1.Lemma 1. For any t ∈ [S + 1] and u ∈ R, we have that,EQUATIONwhere σs,a h,v (t, u)def = ⌊u + P h (t | s, a)v t ⌋ G + . . . + P h (S | s, a)v S G .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 a forward recursion. The details for the approximate Bellman update are given in Definition 5.s ∈ S, and a ∈ A, we define Ûs,a h (1)EQUATIONThen, an approximation to the Bellman update can be computed using Algorithm 3.2 Proposition 4. Algorithm 4 runs in O(HS 2 A|V| 2 Û ) time, whereÛ def = max h,s,a | Û s,a h |.When ⌊•⌋ G 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. 
approximation algorithms: 
 In this section, we present our approximation algorithms for solving (CON). We carefully round the value demands over both time and space to induce an approximate MDP. Solving this approximate MDP with Algorithm 4 yields our FPTAS.Although we can avoid exponential-time Bellman updates, the running time of the approximate Bellman update will still be slow if |V| is large. To reduce the complexity, we instead use a 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 to carefully design the rounding and lower bound functions to balance this trade-off.Value approximation. Given a rounding down function ⌊•⌋ G , we would ideally use the rounded set ⌊v⌋ G | v ∈ V to form our approximate state space. To avoid having to compute V explicitly, we instead use the rounded superset⌊v⌋ G | v ∈ [v min , v max ], where v min and v max are bounds on the extremal values that we specify later. To ensure we can use Algorithm 4 to find solutions efficiently, we must also relax the augmented action space to only include vectors that lead to feasible subproblems for (ADP). From Lemma 1, we know this is exactly the set of (a, v) for which σs,a h,v (1, r h (s, a)) ≥ κ(v). Combining these ideas yields the new approximate MDP, defined in Definition 6. Definition 6 (Approximate MDP). Given a rounding function ⌊•⌋ G and lower bound function κ, theapproximate MDP M def = ( Ŝ, Â, P , ĉ, H) where, 1. Ŝ def = S × V where V def = ⌊v⌋ G | v ∈ [v min , v max ] . 2. Âh (s, v) def = (a, v) ∈ A × VS | σs,a h,v (1, r h (s, a)) ≥ κ(v) . 3. Ph ((s ′ , v′ ) | (s, v), (a, v)) def = P h (s ′ | s, a)[v ′ = vs ′ ]. 4. ĉh ((s, v), (a, v)) def = c h (s, a).The objective for M is to minimize the cost functionĈ def = C M with modified base case Ĉπ H+1 (s, v) def = χ {v≤0} .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 ⌊•⌋ G and κ, the following holds: for anyh ∈ [H + 1] and (s, v) ∈ S, we have Ĉ * h (s, ⌊v⌋ G ) ≤ C * h (s, v).Thus, Algorithm 5 always outputs a policy with better than optimal cost when the instance is feasible,V * M > -∞.If the instance is infeasible, all policies have cost larger than B by definition and so Algorithm 5 correctly indicates the instance is infeasible. The remaining question is whether Algorithm 5 outputs policies having near-optimal value. Time-Space errors. To assess the optimality gap of Algorithm 5 policies, we must first explore the error accumulated by our rounding approach. Rounding each value naturally accumulates approximation error over time. Rounding the partial values while running Algorithm 3 accumulates additional error over (state) space. Thus, solving M using Algorithm 4 accumulates error over both time and space, unlike other approximate methods in RL. As a result, our rounding and threshold functions will generally depend on both H and S.Arithmetic rounding. Our first approach is to round each value down to its closest element in a δ-cover. This guarantees that v -δ ≤ ⌊v⌋ 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 a function of S since it controls the error over space.Input: (M, C, B) 1: Hyperparameters: ⌊•⌋ G and κ 2: M , Ĉ ← Definition 6(M, C, ⌊•⌋ G , κ) 3: π, Ĉ * ← Algorithm 4( M , Ĉ) 4: if Ĉ * 1 (s 0 , v) > B for all v ∈ V then 5:return "Infeasible" 6: else 7:EQUATIONwhere Theorem 2 (Additive FPTAS). For any ϵ > 0, Algorithm 5 using Definition 7 given any cMDP M and TSR criteria C either correctly outputs the instance is infeasible, or produces a policy π satisfyingEQUATIONV π ≥ V * M -ϵ in O(H 7 S 5 Ar 3 max /ϵ 3 ) time.Thus, it is an additive-FPTAS for the class of cMDPs with polynomial-bounded r max and TSR criteria.Geometric rounding. Since the arithmetic approach can be slow when r max is large, we can instead round values down to their closest power of 1/(1 -δ). This guarantees the number of approximate values needed is upper bounded by a function of log(r max ), which is polynomial in the input size. We choose a geometric scheme satisfying v(1 -δ) ≤ ⌊v⌋ G ≤ v so that the rounded value is an underestimate and a relative approximation to the true value. To ensure this property, we must now require that all rewards are non-negative. Definition 8 (Relative Approx). Fix ϵ > 0. We define,EQUATIONwhereδ def = ϵ H(S+1)+1, v min = p H min r min , and v max = Hr max . Theorem 3 (Relative FPTAS). For ϵ > 0, Algorithm 5 using Definition 8 given any cMDP M and TSR criteria C either correctly outputs the instance is infeasible, or produces a policy π satisfyingV π ≥ V * M (1 -ϵ) in O(H 7 S 5A log (r max /r min p min ) 3 /ϵ 3 ) time. Thus, it is a relative-FPTAS for the class of cMDPs with non-negative rewards and TSR criteria. Remark 5 (Assumption Necessity). We also note the mild reward assumptions we made to guarantee efficiency are unavoidable. Without reward bounds, (CON) captures the knapsack problem which does not admit additive approximations. Similarly, without non-negativity, relative approximations for maximization problems are generally not computable. 
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 of the TSR condition in making (CON) tractable. Our work finally resolves the long-standing open questions of polynomial-time approximability for 1) anytimeconstrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained 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-case analysis could circumvent this worst-case hardness. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper is purely theoretical and does not include any releasable materials.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: Our paper is purely theoretical and does not include any experiments.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 5.Proof.1. (Expectation Constraints) We claim that C π M captures expectation constraints. This is immediate as an expectation constraint takes the formE π M H h=1 c h (s h , a h ) ≤ B and by definition C π M = E π M H h=1 c h (s h , a h ) .Moreover, the standard policy evaluation equations for deterministic policies immediately imply,C π h (τ h ) = c h (s, a) + s ′ P h (s ′ | s, a)C π h+1 (τ h , a, s ′ ). (EC)Thus, (TR) holds. It is also easy to see that s ′ P h (s ′ | s, a)C π h+1 (τ h , a, s ′ ) can be computed recursively state-wise by,EQUATIONand so (SR) holds. The infinity conditions and non-decreasing requirements are also easy to verify. 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 ∈ S, we define V H+1 (s) def = {0}, and for any hEQUATION)We defineV def = h,s V h (s).Lemma 3 (Value Intution). For all s ∈ S and h ∈ [H + 1],EQUATIONand |V h (s)| ≤ A H t=h S H-t . Thus, V can be computed in finite time using backward induction. Lemma 4 (Cost). For any h ∈EQUATION) Lemma 5 (Value). Suppose that π ∈ Π D . For all h ∈ [H + 1] and (s, v) ∈ S, if Cπ h (s, v) < ∞, then V π h (s, v) ≥ v. Remark 6 (Technical Subtlety). Technically, V π h (τ h ) is only well defined if P π M [τ h ]> 0 and all of our arguments technically should assume this is the case. However, it is standard in MDP theory to define the policy evaluation equations on non-reachable trajectories using the standard recursion to simplify proofs, as we have done here. Formally, this is equivalent to assuming the process starts initially at τ h instead of just conditioning on reaching τ h , or defining the values to correspond to policy evaluation equations directly. This is consistent with the usual definition when P π M [τ h ] > 0 but gives it a defined value also when P π M [τ h ] = 0. In either case, this detail only means our recursive definition of V is a superset rather than exactly the set of all values as we defined in the main text. This does not effect the final results since unreachable trajectories do not effect π's overall value in the MDP anyway, and only effects the interpretations of some intermediate variables.Proof. By definition of V * M and C * M ,V * M > -∞ ⇐⇒ ∃π ∈ Π D , C π M ≤ B ∧ V π M ≥ V * M ⇐⇒ C * M ≤ B.For the second claim, we observe that if V * M > -∞ then by the above argument any optimal deterministic policy π for COVER satisfiesC π M = C * M ≤ B and V π M ≥ V * M . Thus, COV ER ⊆ P ACK.Proof. We proceed by induction on h. Let s ∈ S be arbitrary.Base Case. For the base case, we consider h = H + 1. In this case, we know that for any π ∈ Π D and any τ ∈ H H+1 , V π H+1 (τ H+1 ) = 0 ∈ {0} = V H+1 (s) by definition. Furthermore,|V H+1 (s)| = 1 = A 0 = A H t=H+1 S t .Step. For the inductive step, we consider h ≤ H. In this case, we know that for any π ∈ Π D and any τ h ∈ H h , if s = s h (τ h ) and a = π h (τ h ), then the policy evaluation equations imply,V π h (τ h ) = r h (s, a) + s ′ P h (s ′ | s, a)V π h+1 (τ h , a, s ′ ).We know by the induction hypothesis that V π h+1 (τ h , a, s ′ ) ∈ V h+1 (s ′ ). Thus, by (13) , V π h (τ h ) ∈ V h (s). Lastly, we see by (13) and the induction hypothesis that,|V h (s)| ≤ A s ′ |V h+1 (s ′ )| ≤ A s ′ A H t=h+1 S H-t = A 1+S H t=h+1 S H-t = A H t=h S H-t .This completes the proof.Proof. We proceed by induction on h. Let τ h ∈ H h and v ∈ V be arbitrary and suppose that s = s h (τ h ). We let C * h (τ h , v) denote the minimum for the RHS of (15).Base Case. For the base case, we consider h = H + 1. Observe that for any π ∈ Π D , V π H+1 (τ H+1 ) = 0 by definition. Thus, there exists a π ∈ Π D satisfying V π H+1 (τ H+1 ) ≥ v if and only if v ≤ 0. We also know by definition that any such policy π satisfies C π H+1 (τ H+1 ) = 0 and if no such policy exists C * H+1 (τ H+1 , v) = ∞ by convention. Therefore, we see that C * H+1 (τ H+1 , v) = χ {v≤0} . Then, by definition of the base case for C, it follows that,C * H+1 (s, v) = χ {v≤0} = C * H+1 (τ H+1 , v).Step. For the inductive step, we consider h ≤ H.If C * h (τ h , v) = ∞, then trivially C * h (s, v) ≤ C * h (τ h , v). Instead, suppose that C * h (τ h , v) < ∞. Then, there must exist a feasible π ∈ Π D satisfying V π h (τ h ) ≥ v. Let a * = π h (τ h ).By the policy evaluation equations, we know that,V π h (τ h ) = r h (s, a * ) + s ′ P h (s ′ | s, a * )V π h+1 (τ h , a * , s ′ ).For each s ′ ∈ S, define v * s ′ def = V π h+1 (τ h , a * , s ′ ) and observe that v * s ′ ∈ V h+1 (s ′ ) ⊆ V by Lemma 3. Thus, we see that (a * , v * ) ∈ A × V S and r h (s, a)+ s ′ P h (s ′ | s, a)v s ′ ≥ v, which implies (a * , v * ) ∈ Āh (s, v). Since π satisfies V π h+1 (τ h , a * , s ′ ) ≥ v * s ′ , it is clear that C * h+1 (s ′ , v * s ′ ) ≤ C π h+1 (τ h , a * , s ′ ). Thus, the induction hypothesis implies that C * h+1 (s ′ , v * s ′ ) ≤ C * h+1 (s ′ , v * s ′ ) ≤ C π h+1 (τ h , a * , s ′ ).The optimality equations for M then imply that,C * h (s, v) = min (a,v)∈ Āh (s,v) c h (s, a) + f P h (s ′ | s, a), C * h+1 (s ′ , v s ′ ) s ′ ∈P h (s,a) ≤ c h (s, a * ) + f P h (s ′ | s, a * ), C * h+1 (s ′ , v * s ′ ) s ′ ∈P h (s,a * ) ≤ c h (s, a * ) + f P h (s ′ | s, a), C π h+1 (τ h , a * , s ′ ) s ′ ∈P h (s,a * ) = C π h (τ h ).The first inequality used the fact that (a * , v * ) ∈ Āh (s, v). 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 definingC * h (τ h , v), we see that C * h (s, v) ≤ C * h (τ h , v). This completes the proof.Proof. We proceed by induction on h. Let (s, v) ∈ S be arbitrary.Base Case. For the base case, we consider h = H +1. By definition and assumption, Cπ H+1 (s, v) = χ {v≤0} < ∞. Thus, it must be the case that v ≤ 0 and so by definition V π H+1 (s, v) = 0 ≥ v.Step. For the inductive step, we consider h ≤ H. We decompose π h (s, v) = (a, v) where we know (a, v) ∈ Āh (s, v) since π has finite cost 4 . Moreover, it must be the case that for any s ′ ∈ S with P h (s ′ | s, a) > 0 that Cπ h+1 (s ′ , v s ′ ) < ∞ otherwise the property that f outputs ∞ when inputted an ∞ would imply a contradiction:Cπ h (s, v) = c h (s, a) + f P h (s ′ | s, a), Cπ h+1 (s ′ , v s ′ ) s ′ ∈P h (s,a) = c h (s, a) + f (. . . , ∞, . . .) = ∞.Thus, the induction hypothesis implies that V π h+1 (s ′ , v s ′ ) ≥ v s ′ for any such s ′ ∈ S. By the policy evaluation equations, we see that,V π h (s, v) = r h (s, a) + s ′ P h (s ′ | s, a) V π h+1 (s ′ , v s ′ ) ≥ r h (s, a) + s ′ P h (s ′ | s, a)v s ′ ≥ v.The third line uses the definition of Āh (s, v). This completes the proof.Proof.If C * 1 (s 0 , v) > B for all v ∈ V, then C * M > B since otherwise we would have C * 1 (s 0 , v) ≤ C * 1 (s 0 , v) = C * M ≤B by Lemma 4. Thus, if Algorithm 1 outputs "infeasible" it is correct. On the other hand, suppose that there exists some v ∈ V for which C * 1 (s 0 , v) ≤ B. By standard MDP theory, we know that since π ∈ Π D is a solution to M , it must satisfy the optimality equations. In particular, Cπ 5 , we see that there exists a π ∈ Π D for which C π M ≤ B and so1 (s 0 , v) = C * 1 (s 0 , v) ≤ B. Since C π M = Cπ 1 (s 0 , v)V * M > -∞. Since V *M is the value of some deterministic policy, Lemma 3 implies that V * M ∈ V. Thus, Lemma 5 implies thatV π 1 (s 0 , V * M ) ≥ V * M and C π 1 (s 0 , V * M ) ≤ C * 1 (s 0 , V * M ) ≤ B.Consequently, running π with initial state s0 = (s 0 , V * M ) is an optimal solution to (CON). In either case, Algorithm 1 is correct.Definition 10. We define the exact partial sum,EQUATION)Observation 1. We observe that both σ and σ can be computed recursively. Specifically,σ s,a h,v (S + 1, u) = u and σ s,a h,v (t, u) = σ s,a h,v (t, u + P h (t | s, a)v t ). Similarly, σs,a h,v (S + 1, u) = u and σs,a h,v (t, u) = σ s,a h,v (t, ⌊u + P h (t | s, a)v t ⌋ G ).For completeness, and to assist with other arguments, we also prove the exact recursion we presented in Definition 3 is correct using Lemma 6.Lemma 6. For any t ∈ [S + 1] and u ∈ R, we have that,g s,a h,v (t, u) = min v∈V S-t+1g s,a h,v (t)EQUATIONMoreover, C * h (s, v) = min a∈A c h (s, a) + g s,a h,v (1, r h (s, a)).Proof. We proceed by induction on t.Base Case. For the base case, we consider t = S + 1.Since S s ′ =S+1 P h (s ′ | s, a)v s ′ = 0 is the empty sum, the condition u + S s ′ =S+1 P h (s ′ | s, a)v s ′ ≥ v is true iff u ≥ v. Also, for any v, g s,ah,v (S + 1) = 0 by definition. Thus, the minimum defining g s,a h,v (S + 1, u) is 0 when u ≥ v and is ∞ due to infeasibility otherwise. In symbols, g s,a h,v (S + 1, u) = χ {u≥v} as was to be shown.Step. For the inductive step, we consider t ≤ S. We see that g s,a h,v (t, u)= min v∈V S-t+1 u+ S s ′ =t P h (s ′ |s,a)v s ′ ≥v g s,a h,v (t) = min v∈V S-t+1 u+ S s ′ =t P h (s ′ |s,a)v s ′ ≥v α β P h (t | s, a), C * h+1 (t, v t ) , g s,a h,v (t + 1) = min vt∈V min v∈V S-t (u+P h (t|s,a)vt)+ S s ′ =t+1 P h (s ′ |s,a)v s ′ ≥v α β P h (t | s, a), C * h+1 (t, v t ) , g s,a h,v (t + 1) = min vt∈V α   β P h (t | s, a), C * h+1 (t, v t ) , min v∈V S-t (u+P h (t|s,a)vt)+ S s ′ =t+1 P h (s ′ |s,a)v s ′ ≥v g s,a h,v (t + 1)    = min vt∈V α β P h (t | s, a), C * h+1 (t, v t ) , g s,a h,v (t + 1, u + P h (t | s, a)v t )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 a∈A c h (s, a) + g s,a h,v (1, r h (s, a)) = C * h (s, v) then= minEQUATION= C * h (s, v).Proof. We proceed by induction on t.Base Case. For the base case, we consider t = S + 1. By definition, σs,a h,v (S + 1, u) = u so the constraint is satisfied iff u ≥ v. Since for any v, ĝs,a h,v (S + 1) = 0 by definition, the minimum defining ĝs,a h,v (S + 1, u) is 0 when u ≥ v and is ∞ due to infeasibility otherwise. In symbols, ĝs,a h,v (S + 1, u) = χ {u≥v} as was to be shown.    = min vt∈V α β P h (t | s, a), C * h+1 (t, v t ) , ĝs,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G )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 α 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.Proof. The runtime guarantee is 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.The following claims all assume Definition 7.EQUATION)Lemma 7. For any h ∈ [H], s ∈ S, a ∈ A, v ∈ R S , u ∈ R, and t ∈ [S + 1], we have,EQUATION) Lemma 8 (Cost). For any h ∈ [H + 1] and (s, v) ∈ S, Ĉ * h (s, ⌊v⌋ G ) ≤ C * h (s, v). Lemma 9 (Approximation). Suppose that π ∈ Π D . For all h ∈ [H + 1] and (s, v) ∈ Ŝ, if Ĉπ h (s, v) < ∞, then V π h (s, v) ≥ v -δ(S + 1)(H -h + 1).The following claims all assume Definition 8.EQUATIONEQUATION)Lemma 11 (Cost). Suppose all rewards are non-negative. For any h ∈ [H + 1] and (s, v) ∈ S, Ĉ * h (s, ⌊v⌋ G ) ≤ C * h (s, v). Lemma 12 (Approximation). Suppose all rewards are non-negative and π ∈ Π D . For all h ∈ [H +1] and(s, v) ∈ Ŝ, if Ĉπ h (s, v) < ∞, then V π h (s, v) ≥ v(1 -δ) (S+1)(H-h+1) .Proof. Using properties of the floor function, we can infer that,⌊v⌋ G = v δ δ ≤ v δ δ = v,and,⌊v⌋ G = v δ δ ≥ ( v δ -1)δ = v δ δ -δ ≥ v -δ.Proof. We proceed by induction on t.Base Case. For the base case, we consider t = S + 1. By definition, we have σs,a h,v (S + 1, u) = u = σ s,a h,v (S + 1, u).Step. For the inductive step, we consider t ≤ S. We first see that,σs,a h,v (t, u) = σs,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) ≤ σ s,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) = ⌊u + P h (t | s, a)v t ⌋ G + S s ′ =t+1 P h (s ′ | s, a)v t ≤ u + S s ′ =t P h (s ′ | s, a)v t = σ s,a h,v (t, u).The first inequality used the induction hypothesis and the second inequality used the fact that ⌊x⌋ G ≤ x.We also see that,σs,a h,v (t, u) = σs,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) ≥ σ s,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) -δ(S -t) = ⌊u + P h (t | s, a)v t ⌋ G + S s ′ =t+1 P h (s ′ | s, a)v t -δ(S -t) ≥ u + S s ′ =t P h (s ′ | s, a)v t -δ(S -t + 1) = σ s,a h,v (t, u) -δ(S -t + 1).The first inequality used the induction hypothesis and the second inequality used the fact that ⌊x⌋ G ≥ x -δ.Proof. We proceed by induction on h. Let (s, v) ∈ S be arbitrary.Base Case. For the base case, we consider h = H + 1. Since ⌊v⌋ G ≤ v, we immediately see,Ĉ * H+1 (s, ⌊v⌋ G ) = χ {⌊v⌋ G ≤0} ≤ χ {v≤0} = C * H+1 (s, v).Step. For the inductive step, we consider h ≤ H.If C * h (s, v) = ∞, then trivially Ĉ * h (s, ⌊v⌋ G ) ≤ C * h (s, v). Instead, suppose that C * h (s, v) < ∞.Let π be a solution to the optimality equations for M so that Cπh (s, v) = C * h (s, v) < ∞. Since C * h (s, v) < ∞, we know that (a * , v * ) = π h (s, v) ∈ Āh (s, v). By the definition of Āh (s, v), we know that,σ s,a * h,v * (1, r h (s, a * )) = r h (s, a * ) + s ′ P h (s ′ | s, a * )v * s ′ ≥ v ≥ ⌊v⌋ G .For each s ′ ∈ S, define v *s ′ def = ⌊v * s ′ ⌋ G and recall that v * s ′ ∈ V. We first observe that, σ s,a * h,v * (1, r h (s, a * )) = r h (s, a * ) + s ′ P h (s ′ | s, a) ⌊v s ′ ⌋ G ≥ r h (s, a * ) + s ′ P h (s ′ | s, a)(v s ′ -δ) = r h (s, a * ) + s ′ P h (s ′ | s, a)v s ′ -δ = σ s,a * h,v * (1, r h (s, a * )) -δ.Then by Lemma 7,σs,a * h,v * (1, r h (s, a * )) ≥ σ s,a * h,v * (1, r h (s, a * )) -δS ≥ σ s,a * h,v * (1, r h (s, a * )) -δ(S + 1) ≥ ⌊v⌋ G -δ(S + 1) = κ(⌊v⌋ G ). Thus, (a * , v * ) ∈ Âh (s, ⌊v⌋ G ). Since v * s ′ ∈ V, the induction hypothesis implies that Ĉ * h+1 (s ′ , v * s ′ ) ≤ C * h+1 (s ′ , v * s ′ ) = Cπ h+1 (s ′ , v * s ′ ).The optimality equations for M then imply that,Ĉ * h (s, ⌊v⌋ G ) = min (a,v)∈ Âh (s,v) c h (s, a) + f P h (s ′ | s, a), Ĉ * h+1 (s ′ , vs ′ ) s ′ ∈P h (s,a) ≤ c h (s, a * ) + f P h (s ′ | s, a * ), Ĉ * h+1 (s ′ , v * s ′ ) s ′ ∈P h (s,a * ) ≤ c h (s, a * ) + f P h (s ′ | s, a), Cπ h+1 (s ′ , v * s ′ ) s ′ ∈P h (s,a * ) = Cπ h (s, v) = C * h (s, v).The first inequality used the fact that (a * , v * ) ∈ Âh (s, v). The second inequality relied on f being non-decreasing and the induction hypothesis. The penultimate equality used (TR). This completes the proof.Proof. We proceed by induction on h. Let (s, v) ∈ Ŝ be arbitrary.Base Case. For the base case, we consider h = H +1. By definition and assumption, Ĉπ H+1 (s, v) = χ {v≤0} < ∞. Thus, it must be the case that v ≤ 0 and so by definition V π H+1 (s, v) = 0 ≥ v.Step. For the inductive step, we consider h ≤ H. As in the proof of Lemma 5, we know that π h (s, v) = (a, v) ∈ Âh (s, v) and for any s ′ ∈ S with P h (s ′ | s, a) > 0 that Ĉπ h+1 (s ′ , v s ′ ) < ∞. Thus, the induction hypothesis implies that V π h+1 (s ′ , vs ′ ) ≥ vs ′ -δ(S + 1)(H -h) for any such s ′ ∈ S. By the policy evaluation equations, we see that,V π (s, v) = r h (s, a) + s ′ P h (s ′ | s, a) V π h+1 (s ′ , vs ′ ) ≥ r h (s, a) + s ′ P h (s ′ | s, a)v s ′ -δ(S + 1)(H -h) = σ s,a h,v (1, r h (s, a)) -δ(S + 1)(H -h) ≥ σs,a h,v (1, r h (s, a)) -δ(S + 1)(H -h) ≥ v -δ(S + 1) -δ(S + 1)(H -h) = v -δ(S + 1)(H -h + 1).The first inequality used the induction hypothesis. The second inequality used Lemma 7. The third inequality used the fact that by definition of Âh (s, v) and κ, σs,ah,v (1, r h (s, a)) ≥ κ(v) = v -δ(S +1). This completes the proof.Proof.Correctness. If Ĉ * 1 (s 0 , v) > B for all v ∈ V, then C * M > B since otherwise we would have Ĉ * 1 (s 0 , ⌊v⌋ G ) ≤ C * 1 (s 0 , v) ≤ C * M ≤ B by Lemma 8. Thus, if Algorithm 5 outputs "infeasible" it is correct.On the other hand, suppose that there exists some v ∈ V for which Ĉ * 1 (s 0 , v) ≤ B. By standard MDP theory, we know that since π ∈ Π D is a solution to M , it must satisfy the optimality equations. In particular, Ĉπ1 (s 0 , v) = Ĉ * 1 (s 0 , v) ≤ B. As in the proof of Theorem 1, since C π M = Ĉπ 1 (s 0 , v), we see that there exists a π ∈ Π D for which C π M ≤ B and so V * M > -∞. Since V *M is the value of some deterministic policy, Lemma 3 implies thatV * M ∈ V. Thus, Lemma 9 implies that V π 1 (s 0 , ⌊V * M ⌋ G ) ≥ ⌊V * M ⌋ G -δ(S + 1)H ≥ V * M -δ(1 + (S + 1)H) = V * M -ϵ and Ĉπ 1 (s 0 , V * M ) ≤ C * 1 (s 0 , V * M ) ≤ B.Consequently, running π with initial state s0 = (s 0 , ⌊V * M ⌋ G ) is an optimal solution to (CON). In either case, Algorithm 5 is correct. In particular, we see that the range of the rounded sums defining Û is at widest [-2Hr max -δS, 2Hr max ] since for any t + 1 the rounded input is,⌊r h (s, a) + P h (1 | s, a)v 1 ⌋ G + . . . + P h (t | s, a)v t G ≤ r h (s, a) + t s ′ =1 P h (s ′ | s, a)v s ′ ,which is at most 2Hr max , and,⌊r h (s, a) + P h (1 | s, a)v 1 ⌋ G + . . . + P h (t | s, a)v t G ≥ r h (s, a) + t s ′ =1 P h (s ′ | s, a)v s ′ -δt, which is at least -2Hr max -δS. Overall, we see that O(| V| 2 | Û|) = O(| V| 3 ) = O(H 6 S 3 r 3max /ϵ 3 ) implying that the total run time is O(H 7 S 5 Ar 3 max /ϵ 3 ) as claimed.Proof. Using properties of the floor function, we can infer that,⌊v⌋ G = v min 1 1 -δ log 1 1-δ v v min ≤ v min 1 1 -δ log 1 1-δ v v min = v v min v min = v,and,⌊v⌋ G = v min 1 1 -δ log 1 1-δ v v min ≥ v min 1 1 -δ log 1 1-δ v v min -1 = v(1 -δ).Proof. We proceed by induction on t.Base Case. For the base case, we consider t = S + 1. By definition, we have σs,a h,v (S + 1, u) = u = σ s,a h,v (S + 1, u).Step. For the inductive step, we consider t ≤ S. We first see that,σs,a h,v (t, u) = σs,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) ≤ σ s,a h,v (t + 1, ⌊u + P h (t | s, a)v t ⌋ G ) = ⌊u + P h (t | s, a)v t ⌋ G + S s ′ =t+1 P h (s ′ | s, a)v t ≤ u + S s ′ =t P h (s ′ | s, a)v t = σ s,a h,v (t, u).The first inequality used the induction hypothesis and the second inequality used the fact that ⌊x⌋ G ≤ x.We also see that,σs,a h,v (t, u) = σs,a h,v t + 1, ⌊u + P h (t | s, a)v t ⌋ G ≥ σ s,a h,v t + 1, ⌊u + P h (t | s, a)v t ⌋ G (1 -δ) S-t = ⌊u + P h (t | s, a)v t ⌋ G + S s ′ =t+1 P h (s ′ | s, a)v t (1 -δ) S-t ≥ (1 -δ)u + (1 -δ) S s ′ =t P h (s ′ | s, a)v t (1 -δ) S-t = σ s,a h,v (t, u)(1 -δ) S-t+1 .The first inequality used the induction hypothesis and the second inequality used the fact that ⌊x⌋ G ≥ x -δ and the fact that all rewards and values are non-negative allowing us to add a (1 -δ)-factor to the other value demands.Proof. We proceed by induction on h. Let (s, v) ∈ S be arbitrary.Base Case. For the base case, we consider h = H + 1. Since ⌊v⌋ G ≤ v, we immediately see,Ĉ * H+1 (s, ⌊v⌋ G ) = χ {⌊v⌋ G ≤0} ≤ χ {v≤0} = C * H+1 (s, v).Step. For the inductive step, we consider h ≤ H.If C * h (s, v) = ∞, then trivially Ĉ * h (s, ⌊v⌋ G ) ≤ C * h (s, v). Instead, suppose that C * h (s, v) < ∞.Let π be a solution to the optimality equations for M so that Cπh (s, v) = C * h (s, v) < ∞. Since C * h (s, v) < ∞, we know that (a * , v * ) = π h (s, v) ∈ Āh (s, v). By the definition of Āh (s, v), we know that,σ s,a * h,v * (1, r h (s, a * )) = r h (s, a * ) + s ′ P h (s ′ | s, a * )v * s ′ ≥ v ≥ ⌊v⌋ G .For each s ′ ∈ S, define v *s ′ def = ⌊v * s ′ ⌋ G and recall that v * s ′ ∈ V. We first observe that, σ s,a * h,v * (1, r h (s, a * )) = r h (s, a * ) + s ′ P h (s ′ | s, a) ⌊v s ′ ⌋ G ≥ r h (s, a * ) + s ′ P h (s ′ | s, a)v s ′ (1 -δ) ≥ r h (s, a * ) + s ′ P h (s ′ | s, a)v s ′ (1 -δ) = σ s,a * h,v * (1, r h (s, a * ))(1 -δ).The second inequality used the fact that all rewards are non-negative. Then by Lemma 10,σs,a * h,v * (1, r h (s, a * )) ≥ σ s,a * h,v * (1, r h (s, a * ))(1 -δ) S ≥ σ s,a * h,v * (1, r h (s, a * ))(1 -δ) S+1 ≥ ⌊v⌋ G (1 -δ) S+1 = κ(⌊v⌋ G ). Thus, (a * , v * ) ∈ Âh (s, ⌊v⌋ G ). Since v * s ′ ∈ V, the induction hypothesis implies that Ĉ * h+1 (s ′ , v * s ′ ) ≤ C * h+1 (s ′ , v * s ′ ) = Cπ h+1 (s ′ , v * s ′). The optimality equations for M then imply that,Ĉ * h (s, ⌊v⌋ G ) = min (a,v)∈ Âh (s,v) c h (s, a) + f P h (s ′ | s, a), Ĉ * h+1 (s ′ , vs ′ ) s ′ ∈P h (s,a) ≤ c h (s, a * ) + f P h (s ′ | s, a * ), Ĉ * h+1 (s ′ , v * s ′ ) s ′ ∈P h (s,a * ) ≤ c h (s, a * ) + f P h (s ′ | s, a), Cπ h+1 (s ′ , v * s ′ ) s ′ ∈P h (s,a * ) = Cπ h (s, v) = C * h (s, v).The first inequality used the fact that (a * , v * ) ∈ Âh (s, v). The second inequality relied on f being non-decreasing and the induction hypothesis. The penultimate equality used (TR).This completes the proof.Proof. We proceed by induction on h. Let (s, v) ∈ Ŝ be arbitrary.Base Case. For the base case, we consider h = H +1. By definition and assumption, Ĉπ H+1 (s, v) = χ {v≤0} < ∞. Thus, it must be the case that v ≤ 0 and so by definition V π H+1 (s, v) = 0 ≥ v.Step. For the inductive step, we consider h ≤ H. As in the proof of Lemma 5, we know that π h (s, v) = (a, v) ∈ Âh (s, v) and for any s ′ ∈ S with P h (s ′ | s, a) > 0 that Ĉπ h+1 (s ′ , v s ′ ) < ∞. Thus, the induction hypothesis implies that V π h+1 (s ′ , vs ′ ) ≥ vs ′ (1 -δ) (S+1)(H-h) for any such s ′ ∈ S. By the policy evaluation equations, we see that,V π h (s, v) = r h (s, a) + s ′ P h (s ′ | s, a) V π h+1 (s ′ , vs ′ ) ≥ r h (s, a) + s ′ P h (s ′ | s, a)v s ′ (1 -δ) (S+1)(H-h) ≥ σ s,a h,v (1, r h (s, a))(1 -δ) (S+1)(H-h) ≥ σs,a h,v (1, r h (s, a))(1 -δ) (S+1)(H-h) ≥ v(1 -δ) S+1 (1 -δ) (S+1)(H-h)which is at most 2Hr max . Then, the same analysis from before shows that the number of scaled powers of 1/(1 -δ) needed to cover this interval is O(| V|). Thus, we see thatO(| V| 2 | Û|) = O(| V| 3 ) = O(H 6 S 3 log( rmax pminrmin ) 3 /ϵ 3) implying that the total run time is O(H 7 S 5 A log( rmax pminrmin ) 3 /ϵ 3 ) as claimed.Suppose each cost c h (s, a) is replaced with a cost distribution C h (s, a). Here, we consider finitely supported cost distributions whose supports are at most m ∈ N. Then, instead of the agent occurring cost c h (s, a) upon taking action a in state s at time h, the agent occurs a random cost c h ∼ C h (s, a). Generally, this necessitates histories be cost dependent, and so the policy evaluation equations become,V π h (τ h ) = r h (s, a) + c ′ ,s ′ C h (c ′ | s, a)P h (s ′ | s, a)V π h+1 (τ h , a, c ′ , s ′ ). (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, V remains a 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:Āh (s, v) def =    (a, v) ∈ A × V m×S | r h (s, a) + c ′ ,s ′ C h (c ′ | s, a)P h (s ′ | s, a)v c ′ ,s ′ ≥ v    .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 is that g's recursion is now two dimensional. Definition 11 (TSRC). We call a criterion C time-space-cost-recursive (TSRC) if C π M = C π 1 (s 0 ) where C π H+1 (•) = 0 and for any h ∈ [H] and τ h ∈ H h letting s = s h (τ h ) and a = π h (τ h ),EQUATIONIn the above, c ′ ∈ C h (s, a) and s ′ ∈ P h (s, a). We now require that f be computable in O(mS) time. We also require that the f term above is equal to g τ h ,a h (1, 1), where, g τ h ,a h (m + 1, 1) = 0, g τ h ,a h (k, S + 1) = g τ h ,a h (k + 1, 1), and,EQUATIONIn the above, we assume c k is the kth supported cost of C h (s, a). Again, both α, β can be computed in O(1) time, but now α(β(y, •), x) = x whenever 0 ∈ y.Our examples from before also carry over to the stochastic cost setting. We can then modify our approximate recursion from before. Approximation. Lastly, our rounding now occur error over time, space, and cost. Thus, we simply need to slightly modify our rounding functions. The main change is we useδ def = ϵ H(mS+1)+1. We also further relax our lower bounds to κ(v) def = v -δ(mS + 1) and κ def = v(1 -δ) mS+1 respectively. Our running times correspondingly will have m 3 terms now.Approximations. Since we focus on approximation algorithms, the infinite discounted case can be immediately handled by using the idea of effective horizon. We can treat the problem as a finite horizon problem where the finite horizon H defined so that ∞ h=H γ h-1 r max ≤ ϵ ′ . By choosing ϵ ′ 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 0-cost actions are always available so that the policy can guarantee feasibility after the effective horizon has passed.Hardness. We also note that all of the standard hardness results concerning deterministic policy computation carries over to the infinite discounting case even if all quantities are stationary.We can significantly improve the running time of our FPTAS. The main guarantee is given in Corollary 1. They key step is to modify Algorithm 3 to use the differences instead of the sums. It is easy to see that this is equivalent since, r h (s, a) +s ′ P h (s ′ | s, a)v s ′ ≥ v ⇐⇒ v - s ′ P h (s ′ | s, a)v s ′ ≤ r h (s, a).Since rounding down the differences make them larger, it becomes harder to be below r h (s, a). Consequently, we now interpret κ as an upper bound for r h (s, a) instead of a lower bound on v The approximate dynamic programming method based on differences can be seen in Definition 13. Definition 13. Fix a rounding down function ⌊•⌋ G and upper bound function κ. For any h ∈ [H], s ∈ S, v ∈ V, and u ∈ R, we define, ĝs,a h,v (S + 1, u) = χ {u≤κ(r h (s,a))} and for t ≤ S, ĝs,a h (t, u)def = min vt∈V α β P h (t | s, a), C * h+1 (t, v t ) , ĝs,a h (t + 1, ⌊u -P h (t | s, a)v t )⌋ G . (DIF)The recursion is nearly identical to the originally, and unsurprisingly, it retains the same theoretical guarantees but in the reverse order. The guarantees can be seen in Lemma 13, which is straightforward to prove following the approach in the proof of Lemma 1. Lemma 13. For any t ∈ [S + 1] and u ∈ R, we have that,EQUATIONwhere σs,a h,v (t, u)def = ⌊u -P h (t | s, a)v t ⌋ G -. . . -P h (S | s, a)v S G .The difference version so far does not help us get faster algorithms. The key is in how we use it.Since the base case of the recursion is r h (s, a) and not v, we can compute the approximate bellman update for all v's simultaneously. This ends up saving us a factor of |V| that we had in the original Algorithm 4. The new algorithm is defined in Algorithm 6. The inputs to the recursion are define in Definition 14. However, for the relative approximation, no choice of upper bound can ensure enough feasibility. Thus, we simply use κ(r h (s, a)) def = r h (s, a) and apply a different analysis. We also note that technically, differences can become negative. To deal with this the relative rounding function should simply send any negative number to 0: ⌊-x⌋ G def = 0. The analysis is mostly the same, but the feasibility statement must be slightly modified. Lemma 14. Suppose all rewards are non-negative. For any h ∈[H + 1] and (s, v) ∈ S, Ĉ * h (s, v(1 -δ) H-h+1 G ) ≤ C * h (s, v).The idea is that since no fixed upper bound can capture arbitrary input values, we simply input relative values. Then, the feasibility part of Lemma 11 goes through as before. The proofs mostly remain the same, but the rounding must again change. We must now start at the smaller v min that is the original v min scaled by a factor of (1 -δ) H to ensure that V * M (1 -δ) H is in V . This makes V larger, but not by too much as we argued in previous analyses. 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 in 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Justification: We beleive our paper follows the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024).When we say a multivariate function is non-decreasing, we mean it is non-decreasing with respect to the partial ordering induced by component-wise ordering.We use the notation x, o ← minx z(x) to say that x is the minimizer and o the value of the optimization.Technically, there is no t ∈ [H] satisfying t ≥ H + 1. We instead interpret the t ≥ h condition in the max as over all integers and define the immediate costs to be 0 for all future times to simplify the base case.By convention, we assume min ∅ = ∞We can view C ( V ) as the extension of C (V ) needed to formally evaluate memory-augmented policies. Since we consider deterministic policies, it is trivial to convert any memory-augmented policy into a historydependent policy that is defined in the original environment M . 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Minor comments:
-  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.
 
- 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.
questions: 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: limitations: The paper does a good job outlining the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?

- 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.

- Theoretical statement doesn't contain assumptions. It would be good if you could incorporate assumptions in the theoretical statements, especially in propositions and theorems.

- 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).
questions: questions: - Why is Proposition 2 a proposition but not just an example?
- 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. 
- In line 148, what does "this covering program" mean? Does it correspond to the reversed objective?
- why value-demand augmentation and not value-function augmentation?
limitations: limitations: None
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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?
3. 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.
questions: 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?
2. Is there existing works  using the same problem definition?
limitations: limitations: 1. The complexity is still high.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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:
- Sootla, Aivar, et al. "Sauté RL: Almost surely safe reinforcement learning using state augmentation." ICML, 2022.
- Wachi, Akifumi, Xun Shen, and Yanan Sui. "A Survey of Constraint Formulations in Safe Reinforcement Learning." IJCAI (2024).

I 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.

**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.

**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.

In 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.
questions: 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)?


### Minor Comments
- Line 117-118: (SR) $\rightarrow$ (TSR)
limitations: limitations: The authors have slightly addressed the limitations. There is no discussion regarding potential negative societal impact of their work.

Comments: title: Rebuttal Acknowledgement
"mean of a policy"
Follow-up to Reviewer's Second Comment
Follow-up to Reviewer's Comment
comment: I thank the authors for their rebuttal. I have read all the comments and maintain my score.
Dear AC FgZ1,

If the AC considers that this paper is written so that the contributions are clearly explained for the NeurIPS community, I respect the decision.
Dear reviewer SLVm,

Your point is well taken, that the authors are encouraged to make more connections to adjacent areas that receive more attention in the NeurIPS/ICML communities. I do think the authors have agreed to this sentiment in general, and I am inclined to leaving the detailed execution to the authors. 

After all, this is a planning / computational complexity paper. I understand that such a topic may feel a bit distant to many in the community nowadays, but such areas (with overlap with planning venues like ICAPS and TCS venues like SODA/STOC) have always been within the scope of NeurIPS and part of theoretical foundation of RL. I welcome specific and concrete citation suggestions that are directly relevant to the paper from reviewers with close expertise on the topic. For a computational complexity paper, such citations would be prior papers that establish upper / lower bounds on problems closely related to the one studied in the current work. Otherwise I am inclined to treat additional citations as "soft suggestions" and the authors can use their judgement to include whatever they feel relevant.

AC
I don't feel there is any progress in the discussion. I think it is simply because the authors have not fully surveyed constrained RL that the authors think that "we believe we have cited the most relevant ones to our specific problem setting".

Because the remaining discussion period is short, I will ask a short and clear question.

**Question.** Could you provide a plan on how to revise related work sections? Please explain what kinds of discussion the authors to planning to add. Here, please list the papers on constrained RL to be cited and discuss the relations with this paper.

Note that I am no longer talking about safe RL. I now focus on constrained RL literature that has been particularly published in NeurIP or ICML.
Dear reviewer iqFB,

> why can one not apply the mean of the policy to get a deterministic behaviour?

Note that you cannot do that in MDPs in general. In standard MDP formulations, actions are categorical variables, so you cannot simply "take the mean". Your comment would make sense in continuous control problems where actions are vectors in Euclidean spaces, but that requires additional structural assumptions on the dynamics (e.g., this might be true in linear systems).
We appreciate your feedback! We completely agree that some safe RL papers study convergence; we in no way intended to make a sweeping statement about all safe RL papers and we apologize for the imprecise phrasing of our statement. As for the comment on constrained RL, we mention that some constrained RL papers, such as those addressing constrained resource problems, do not concern safety. Similarly, some safe RL papers study safe behavior not defined by cumulative cost constraints. Thus, we believe it is fair to say our constrained RL paper is not directly a safe RL paper, but does have applications to safe RL, since constraints may or may not concern safety depending on their intended applications. 

We agree we could cite more works in the paper (and plan to), but we believe we have cited the most relevant ones to our specific problem setting. We note works concerning our problem have appeared in good theory and ML conferences including AISTATS, AAAI, and SODA. In terms of contributions, as we stated in our general rebuttal: "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]." These specific problems have many interesting applications, which are discussed in the first paragraph of our paper.
I think the authors misunderstand the terminology of safe RL. The following eminent survey paper on safe RL (citations > 1900) categorizes these optimization criteria into four groups: (i) the worst-case criterion, (ii) the risk-sensitive criterion, (iii) the constrained criterion, and (iv) other optimization criteria.
- Garcıa, Javier, and Fernando Fernández. "A comprehensive survey on safe reinforcement learning." Journal of Machine Learning Research 16.1 (2015): 1437-1480.

This paper was published in JMLR in 2015, and the definitions of "safe RL" or "constrained RL" are widely used in the RL community in NeurIPS/ICML. Therefore, I respectfully disagree with the following authors' claim
> "Although Safe RL is a common application of Constrained RL, our work is not directly a Safe RL work."

Also, the following statement is not true. Many constrained (deep) RL algorithms (e.g., CPO or TRPO-Lagrangian) do not focus on the safe exploration problem. They aim to achieve constraint satisfaction after convergence.
> Safe RL primarily focuses on the issue of safe exploration, which does not even appear in the planning setting.
- Achiam, Joshua, et al. "Constrained policy optimization." International conference on machine learning. PMLR, 2017.

Even if we focus on the constrained RL or constrained MDP, it is unreasonable not to mention any paper on safe RL or constrained RL that has been published in NeurIPS (or relevant conferences). 

The critical issue is that this paper seems to be written without adequate surveying, which makes the contributions extremely unclear for the NeurIPS community.
Thank you for your response! We completely agree that we did not reference many Safe RL papers; however, we remind the reviewer that our paper concerns the topic of Constrained RL. Specifically, our paper focuses on the computational complexity of planning for Constrained RL, although our results can technically extend to learning settings. For concrete applications of our work, our method is a polynomial time algorithm for the autonomous vehicle routing problem posed by Hong, and the anytime constraints problem posed by McMahan. 

Although Safe RL is a common application of Constrained RL, our work is not directly a Safe RL work. Safe RL primarily focuses on the issue of safe exploration, which does not even appear in the planning setting. We remind the reviewer that the planning problem for most Safe RL formulations lies in P, unlike our NP-hard problem. Given this context, we ask the reviewer: would it be relevant to reference many more Safe RL works other than to show potential applications of our work?
Thank you for clarifications! I have read other reviews and authors' rebuttals.
While I have a deeper understanding of the contribution of this paper, I still feel that existing safe RL papers have been largely ignored. Though this paper is submitted to NeurIPS, this paper has literally no reference paper on safe RL published in NeurIPS/ICML/ICLR. I think this paper is hard to follow and its contribution is unclear for the NeurIPS community. Since many safe RL papers have been published in NeurIPS or relevant conferences, it is better to write this paper based on them for clearly present the contributions of this paper.

I will not be upset if this paper gets accepted, but I am not willing to recommend acceptance.