Polynomial-Time Approximability of Constrained Reinforcement Learning
Authors: Jeremy McMahan
Venue: ICML 2025 poster (2025)
Keywords: Constrained Reinforcement Learning
Computational Complexity
Approximation Algorithms
Primary area: theory->reinforcement_learning_and_planning

Abstract: We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time $(0,\epsilon)$-additive bicriteria approximation algorithm for finding optimal constrained policies across a broad class of recursively computable constraints, including almost-sure, chance, expectation, and their anytime variants. Matching lower bounds imply our approximation guarantees are optimal so long as $P \neq NP$. The generality of our approach results in answers to several long-standing open complexity questions in the constrained reinforcement learning literature. Specifically, we are the first to prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and policies under constraints for continuous-state processes.

Polynomial-Time Approxinability of Constrained Reinforcement Learning
Jeremy McMahan
Abstract
expectation-constrained policies, leaving many popular ser- tings with longstanding open problems. Even chance con- straints, arguably close second in popularity, still lack any polynomial -imem even approximate, algorithms despite be- ing introduced over a decade ago (Xu and Mannor, 201 1). Other settings for which polynomial-tin -tme algorithms are open include deterministic policies under multiple expec- tation constraints, policies under non- non-homogeneous con- straints (i.e., constraints of different types), and policies under constraints for continuous-state processes. Conse- quently, we study the computational complexity of general constrained problems to resolve many of these fundamental open questions.
We study the computational complexity of ap- proximating general constrained Markov deci- sion processes. Our primary contribution is the design of a polynomial time (0, )oad)didee bi- criteria approximation algorithm for finding op- timal constrained policies across broad class of recursively computable constraints, including almost-sure, chance, expectation, and their any- time variants. Matching lower bounds imply our approximation guarantees are optimal so long as P * NP. The generality of our approach re- sults answers to several long-standing open complexity questions in the constrained reinforce- ment learning literature. Specifically, we are the first prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multi- ple expectation constraints, policies under non- homogeneous constraints (i.e., constraints of dif- ferent types), and policies under constraints for continuous-state processes.
Formally, we study the solution of Constrained Markov Decision Processes (CMDPs). Here, we define CMDP through three fundamental parts: (1) an MDP M that accu- mulates both rewards and costs, (2) general cost criterion C, and (3) budget vector B. Additionally, we allow the agent to specify whether they require their policy to be de- terministic or stochastic, formalized through goal policy class IT. The agent's goal to solve max V subject to C B, where V denotes the agent's value and Oßr denotes the agent's cost under л. This model capture very general problems, including minimum time routes for self-driving vehicles that must satisfy 1) an anytime con- straint on fuel consumption, 2) an expectation constraint on CO2 consumption, and 3) a chance constraint on vehicle wear and tear. Our main question the following:
1. Introduction
Constrained Reinforcement Learning (CRL) is growing in- creasingly crucial for managing complex, real-world appli- cations such as medicine (Coronato al., 2020; Paragli- ola al., 2018; Kolesar, 1970), disaster relief (Fan al., 2021; Wu al., 2019; Tsai et al., 2019), and resource management (Mao al., 2016; Li et al., 2018; Peng and Shen, 2021; Bhatia et al., 2021). Various constraints, in- cluding expectation (Altman, 1999), chance (Xu and Man- nor, 2011), 1), almost-sure (Castellano et al., 2022), and any- time constraints (McMahan and Zhu, 2024b), were each proposed to address new challenges. Despite the rich- ness of the literature, most works focus stochastic,
Can general CMDPs be approximated in polyno- mial time?
Solving general CMDPs is notoriously chal- lenging. When restricted to deterministic policies, solving a CMDP with just one constraint NP-hard (Feinberg, 2000; Xu and Mannor, 2011; McMahan and Zhu, 2024b; McMahan, 2024). This difficulty increases with the num- ber of constraints: with at least two constraints, finding feasible deterministic policy, let alone near-optimal one, becomes NP-hard (McMahan and Zhu, 2024b). Even if we relax the deterministic requirement, this hardness remains for all constraint types other than expectation. Computa- tional hardness aside, standard RL techniques fail to apply due the combinatorial nature induced by many constraint
Hardness.
'Department of Computer Science, University of Wisconsin- Madison, Wisconsin, USA. Correspondence to: Jeremy McMahan jmmemahan& @ wisc.edu>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Polynomial-Tine Approximability of Constrained Reinforcement Learning
types, Adding in additional constraints with fundamentally different structures further complicates the problem.
1.1. Related Work
Constrained RL. is known that stochastic expectation- constrained policies are polynomial-timg computable via lin- car programming (Altman, 1999), and many planning and learning algorithms exist for them (Paternain et al., 2019; Vaswani et al., 2022; Borkar, 2005; HasanzadeZonuzy et al., 2021). Some learning algorithms can even avoid violation during the learning process under certain assumptions (Wei et al., 2022; Bai et al., 2023). Furthermore, Brantley et al. (2020) developed no-regret algorithms for cMDPs and ex- tended their algorithms to the setting with constraint on the cost accumulated over all episodes, which is called a knapsack constraint (Brantley et al., 2020; Cheung, 2019).
Past Work. A few works have managed to derive provable approximation algorithms for some cases of CRL.. McMa- han (2024) presented a fully polynomial-time approxima- tion scheme (FPTAS) for the computation of deterministic policies of a general class of constraints, which includes expectation, almost-sure, and anytime constraints. Although powerful, their framework only works for one constraint and fails to capture anytime-expectation constraints along with chance constraints. Similarly, Khonji et al. (2019) achieves an FPTAS for expectation and chance constraints, but only in the constant horizon setting. In contrast, McMa- han and Zhu (2024b) develops a polynomial-time (0,e)- additive bicritiera approximation algorithm for anytime and almost-sure constraints. However, their framework is spe- cialized to those constraint types and thus fails for our purpose. In contrast, Xu and Mannor (2011) developed pseudo-polynomial time algorithm for finding feasible chance-constraineed policies, but their methods do not lead to polynomial-time solutions.
Safe RL. The safe RL community (García et al., 2015; Gu et al., 2024) has mainly focused on no-violation learning for stochastic enpectation-constramme policies (Chow et al., 2018; Bossens and Bishop, 2022; Alshiekh et al., 2018; Cheng et al., 2019; Berkenkamp et al., 2017) and solving chance constraints (Wang et al., 2023; Zhao et al., 2023), which capture the probability of entering unsafe states. Per- forming learning while avoiding dangerous states (Zhao et al., 2023) is special case of expectation constraints that has also been studied (Roderick et al., 2021; Thomas et al., 2021) under non-trivial assumptions. In addition, instanta- neous constraints, which require the immediate cost to be within budget at all times, have also been studied (Li et al., 2021; Fisac et al., 2019; Gros et al., 2020).
Our Contributions. We design a polynomial-time (0,e)- additive bicriteria approximation algorithm for tabular, SR- criterion CMDPs. An SR criterion is required to satisfy a generalization of the policy evaluation equations and in- cludes expectation, chance, and almost-sure constraints along with their anytime equivalents. Our framework im- approximability re- sults for (1) policies under chance constraints, (2) determin- istic policies under multiple expectation constraints, and (3) policies under non-homo non-homogencous constraints - each of which has been unresolved for over decade. We then ex- tend our algorithm into a polynomial bicriteria approximation algorithm for continuous-state CM- PDs under general class of constraints, which includes expectation, almost-sure, and anytime constraints.
plies the first positive polynomial
2. Constraints
Cost-Accumulating MDPs. In this work, we consider environments that accumulate both rewards and costs. Formally, we consider a (finitehhorizon, tabular) cost- accumulating Markov Decision Process (caMDP) tuple M = SH, A, P, R. C, so), where (i) H Zzo is the fi- nite time horizon, (ii) S, is the finite set of states, (ii) (s( is the finite set of available actions, (iv) Pa (s a) E A(S) is the transition distribution for a given state 3 E S and action a E A (note, AS5) represents the probability simplex over S) (v) (s,s a) E A(R) is the reward distribution, (vi) (n E ART") the cost distribution, and (vii) so S is the initial state.
(c, <aaddiivve
Our Techniques. Our algorithm requires several key tech- niques. First, we transform a constraint concerning all re- alizable histories into a simpler per-time constraint. We accomplish this by augmenting the state space with an ar- tificial budget and augmenting the action space to choose future budgets to satisfy the constraint. However, Bellman updates then become as hard as the knapsack problem due to the large augmented action space. For tabular cMDPs, we show that the Bellman updates can be approximately computed using dynamic programming and rounding. By strategically rounding the artificial budget space, we achieve a (0, e)- bicriteria approximation for tabular CMDPs. By appropriately discretizing the continuous state space, our method becomes a (c, e)- -ibbicriteria approximation algorithm for continuous state CMDPs.
To simplify notation, we let (x(8, a) def BiRg, a)] de- note the expected reward, en (a(8,,) (8) represent the cost func- tion when costs are deterministic (which will be the case throughout the main text), S def [S] denote the number of states, A def |A| denote the number of joint actions, [H] del (1...., H). MM be the set of all caMDPs, and |M] be the total description size of the caMDP. We also use the def Iverson Bracket notation [P] 1 L(P=Truc) and the char- acteristic function XP which is co when P False and 0
2

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
otherwise.
function rooted at O. Moreover, require that f is short map when either of its inputs are fixed, satisfies f(0, = f(x, 0) = for all a, and when combined with 9. i..., f 9 (Pr (s' s.)) Zer. is a short map in z.
Agent Interactions. The agent interacts with M using policy = (TA) In the fullest generality, Ta Hr. + ((A) is a mapping from the observed history at time h (including costs) to a distribution of actions. Often, re- searchers study Markovian policies, which take the form Th S + (AA), and deterministic policies, which take the form A Hp. + A. We let II denote the set of all policies and II denote the set of all deterministic policies.
Remark 2.2 (Stochastic Variants). Our results generalize to both stochastic policies and stochastic costs as well. The algorithmic approach is identical, but the definitions and analysis are more complex. Consequently, we focus on the deterministic cases in the main text.
The agent starts in the initial state 8o with observed history TI (so). For any & E [.]. the agent chooses joint action an ~ Th. (T.). Then, the agent receives immediate reward Th ~ (s, a) and cost vector Ch ~ Cz a)). Lastly, M transitions to state $/+1 ~ (s as), prompting the agent to update its observed history 7 = (Th: ah, Ch,y 8h+1). This process is repeated for H steps; the interaction ends once 81+1 is reached.
Constraint Formulations. The fundamental constraints considered in the CRL literature are Expectation, Chance, and Almost-sure constraints. Each of these induces a natural anytime variant that stipulates the required constraint must hold for the truncated cost Σ Ch2 at all times h E [H]. We give the formal definitions in Figure 1. Importantly, each constraint is equivalent to Căr s B' for some appropriately chosen SR criteria.
Proposition 2.3 (SR Modeling). The classical constraints can be modeled by SR constraints of the form CM S B' as follows:
Constrained Processes. Suppose the agent has a cost criterion C: : . x II - Rm and a corresponding budger vector B E Rm. We refer to the tuple (M, B) as a Constrained Markov Decision Process (CMDP). Given a CMDP and desired policy class πI E (TP,, IT], the agent's goal is to solve the constrained optimization problem:
def y. g(x) def x,
1. Expectation Constraints - f(x,)) and B' def B.
2. Chance Constraints (f.g) defined as above and B' def 6. Here, we assume M's states are aug- mented with cumulative costs and that en ((s,e).a) def (en(s,a) + C > B] for the anytime variant and (nl(s, a) def (cn(s,a) + >> B] H otherwise.
max TE
VM
(CON)
C B
In the above, Vă del ET Em (N(,,, an) denotes the value of a policy n, ET, denotes the expectation defined by M and 1 denotes the probability law over histories induced from the interaction of with M. Lastly, we let V* denote the optimal solution value to (CON). In the main paper, we focus on the case where II = P.
3. Almost-sure Constraints -f v) def max(x, y), g g(x) def [x 0], and B' def B. Anytime variant max(0, max(x, v)) while g and B' remain the same.
f v) def
SR Criteria. We study cost criteria that generalize the standard policy evaluation equations to enable dynamic pro- gramming techniques. In particular, we require the cost of policy to be recursively computable with respect to the time horizon. For our later approximations in Section 5, we will also need key functions defining the recursion to be short maps, i.e., 1-Lipschitz, with respect to the infinity norm.
General anytime variants, including anytime expectation constraints, can be modeled by {CM., S B} (E'H where CM, is the original SR criterion but defined for the truncated-horizon process with horizon I.
Computational Limitations. It is known that comput- ing feasible policies for CMDPs is NP-hard (McMahan, 2024; McMahan and Zhu, 2024b). As such, we must relax feasibility for any hope of polynomial -imme algorithms. Con- sequently, we focus on bicriteria approximation algorithms.
Definition 2.1 (SR). We call a cost criterion shortly recur- sive (SR) if for any caMDP M and any policy
π E II,, x's cost decomposes recursively into C CT (80). where C#++1 0 and for all h E [H] and To E Hr, letting (TT.) and a = (T)T)),
Definition 2.4 (Bicriteria). A policy I is an (a: B) aadiitive bicriteria approximation to CMDP (M, C, B) if V Z V - a and C% S B + 3. We refer to an algorithm as an (a. 3) -iibritter if for any CMDP it outputs an (a, B)- additive bicriteria approximation or correctly reports the instance is infeasible.
(Th)== (s) + (Pa 8, a)) Ch+1 (Th, a's). (SR) Here, for is the finite extension of an associative, non- decreasing, binary function f, and g is a [0, 1] valuud
3

---

Polynomial-Timg Approximability of Constrained Reinforcement Learning
Con/Time
Expectation
Chance
Almost-Sure
H
H
H
Classical
EM
Ch
B
PM
M
>
B
S 6
M
Σ
S B
=1
A=1
A=1
Anytime (VI E [H]
EM
Ch
S
B
PM
M
Ch
> B
2
P'
Σ A=1
S =1
B
Lt=1
L=11
Pigure 1. The Constraint Landscape
The existence of a polynomial-time bicriterion for our gen- eral constrained problem implies brand-new approximabil- ity results for many classic problems in the CRL literature. For clarity, we will explicitly state the cemplexity-theoretee implications for each classical setting.
Expectation Constraints. Instead, we can exploit the recursive nature of the expected cost to find solution. Suppose at stage (s, h) we impose an artificial budget b on the expected cost of a policy x from time h onward: E
or b. By the policy evaluation equations, we know this equates to satisfying:
HH
Theorem 2.5 (Implications). A polynomial-tin ee, bicriteria implies that in polynomial time it is possible to compute policy E Il satisfying VM 2 V e and any constant combination of the following constraints:
Cg(s cx + P
P 1s,a)
6. (2)
For this invariant to be satisfied, it suffices for the agent to choose future artificial budgets b, for s' E S satisfying,
1. E
Eh=1 Ch S B +
2. PM
E Ch S B + =1
cn(s, a) +
Σ Ph('s s,a)by Sb. b.
3. PM
Σ E Ch B+ 58+6.
and ensure the future artificial budgets are obeyed induc- tively: Ch+1 (s', s b..
In other words, polynomial-time approximability is possible for each of the settings described in Section 1 when the number of constraints constant.
General Approach. We can apply the same reasoning for general recursively computable cost criteria. If is SR, then we know that Cj2, (s) obeys (SR). Thus, to guarantee that C (s) S b it suffices to choose be's satisfying,
Remark 2.6 (Extensions). All of our results hold for Markov games and infinite discounted settings.
ea (s, a) + + (Pr(s' 1 18,a)) bw S.b.
(4)
3. Reduction
and inductively guarantee that Ch+ (8') S by.
In this section, we present a general solution approach to SR- criterion CMDPs. Our approach revolves around converting the general cost constraint into a per-step action constraint. This leads to the design of an augmented MDP that can be solved with standard RL methods.
We can view choosing future artificial budgets as part of the agent's augmented actions. Then, at any augmented state (s, b). the agent's augmented action space includes all (a, b) E A R satisfying (3). When M transitions s' augmented state should consist
Pr, (s, a), the agent's of the environment's 's state in addition to its chosen demand for that state, (s', be).. Putting these pieces together yields the definition of the reduced, action-constrained MDP, Definition 3.1.
Augmentation. State augmentation is the known approach for solving anytime-constraig MDPs (McMahan and Zhu, 2024b). The augmentation permits the problem to be solved by the following dynamic program:
Definition 3.1 (Reduced MDP). Given any SR-criterion CMDP (M, C, B). we define the reduced MDP M def (H, A. R. Su) where,
(s, = max (n(s,a) eEA. (s,ag)
(1)
+ Σ | (1..
1. S,
S x B where B def U Une[m41| UnER. (T))
def
When moving to other constraints, the cumulative cost may no longer suffice to determine constraint satisfaction. For example, the expected cost depends on the cumulative cost of all realizable branches, not just the current branch.
((a.b) E An(s) x R (n(s,a) + (s de
J. 9 (Ph (8,0),bb)

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
Algorithm 1 Reduction
4. Bellman Updates
Require: M,
In this section, we discuss efficient methods for solving M. Our approach relies on using (SR) to break down the Bellman update so that it is solvable using dynamic pro- gramming. We then use dynamic rounding to achieve an efficient approximation algorithm.
1: M +- Definition 3.1(M, C, B)
2: R; V <- (OLVE(M)
3: if V* -c then
4: return "Infeasible"
5: else
6: return πT
Bellman Hardness. Even small set of artificial bud- gets, B, needed to be considered, solving M would still be challenging due to its exponentially large, constrained action space. Just one Bellman update equates to solving the constrained optimization problem:
7: end if
Algorithm 2 Augmented Interaction
Require: π
1: 31 = (so: B)
2: for + to H do
VI (s. max (s a) + a.
Σ Pa(s' 8, (s',byr 8²
Thp (Bh) 4: 8 Pn(sh,a a)
3: (a,
s.L. cn(s + ( (Pa b, S
5: 8/+1 (sh+1, Dea+s)
6: end for
(BU)
Above, we used the fact that (8' Supp(PM((s,bb) 6), (a, b))) iff s' E Supp(Px(ss a)) and B' = by. In fact, even when each by only takes on two possible values, {0, w this optimization problem generalizes the knapsack problem, implying that it is NP-hard to solve.
3. Ph[(s', 66) (s, 6), (a, b)) def Ph(s' s,a) = bw]
4. [n,(s, b). (a, b)) del ())
def
5. 50 (sp. B)
Dynamic Programming. To get around this computa- tional bottleneck, we must fully exploit Definition 2.1. For any fixed (h, (s, u)) the key idea is to treat choosing b's as its own sequential decision-making problem. Sup- pose we have already chosen cost F def / (Pa I s, s,a)) Since f is associa- tive, we can update our partial cost after choosing b, to f(F, (P,, s, a,))),,). Once we have made choice for each future state, we verify if (a, b) E (s, by checking the condition: (s,s, a) + F < b. By incorporat- ing the value objective, we design a dynamic program for computing (BU).
We also re-define the base case value to ( def -X16203. Note, the reduced MDP has non-stationary state and action set, unlike the base MDP.
leading to partial
Reduction. Importantly, M's augmented action space sures constraint satisfaction. Thus, we have effectively re- duced a problem involving total history constraints to one with only standard per-time-step constraints. So long as our cost SR, M can be solved using fast RL methods instead of the brute force computation required for general CMDPs. These properties ensure our method, Algorithm 1, is correct. Lemma 3.2 (Value). For any h E [H + 1]. Th E Hr. and b E B, if sn (Tr), then,
Definition 4.1 (DP). For any E [H). (s, E S, and E R. we define V 1, -X(es(ea))+55)) and for any t [S].
(s) 2 sup (Th) TEIID
(5)
V. (1, F) def
max (1 8, s, (1,b+ bEE
s.t. C (Th) b.
(6)
b.b (1+ (F, s,a)),.)).
Lemma 3.3 (Cost). Suppose that πI E II For all h E [H+ 1] and (s,b) b) E S. V (s,b) > -0, then C% (s, b) & b. Theorem 3.4 (Reduction). If SOLVE is any any finite-time MDP solver, then Algorithum 1 correctly solves (CON) in finite time for any SR-criterion CMDP.
Lemma 4.2 (DP Correctness). For any h E [H] and (s. E S, we have that V (s,b) m) + V
Dynamic Rounding. Although a step in the right direc- tion, solving Definition 4.1 can still be slow due to the expo- nential number considered partial costs. We resolve this issue by rounding each partial cost to an element of some
Remark 3.5 (Deployment). Given budget-augmented pol- icy N output from Algorithm 1, the agent can execute π using Algorithm
5

---

Polynomial-Tinee Approximability of Constrained Reinforcement Learning
small set F. Since f need not be linear, using rounding in preprocessing step does not suffice: we must re-round at each step to ensure inputs are valid element of our input set.
Algorithm 3 Approximate Backward Induction
Require: M
1: Vū (s, b) < X(b20) for all (s,b) E S
2: for h <- H down to do
3: for (s, b) E S do
For any > 0, we view as a new unit length. Our rounding function maps any real number to its closest upper bound in the set of integer multiples of L. We use upper bounds to guarantee that the rounded partial costs are always larger than the true partial costs. Smaller ensures less approxi- mation error, while larger l ensures fewer considered partial costs. Thus, & directly controls the accuracy-efficiency trade- off.
4: à. (s. b) + (AU)
(s, b) + â
end for
7: end for
8: return π. 1/
Remark 4.6 (DP details). Technically, to turn this recursion into a true dynamic program, we must also precompute the inputs to any subproblem. Unlike in standard RL, this computation must be done with forward recursion. If we let F (t) denote the set of possible input rounded partial costs for state I, then the set satisfies the inductive relation- ship (1) del {0} and for any L [S]. J. f.. (1++1 1) del Us UPEAt [[f + g(P. s, s,a))6,le): This re- lationship translates directly into an iterative algorithm for computing all needed inputs. Using this gives a complete DP algorithm for solving (ADP)).
Definition 4.3 (Rounding Functions). For any > 0 and def [
x E IR., we define [
l to be the smallest integer def multiple of that larger than æ. We also define (x)x))
x+ ++ 1). Note, when considering vectors, all operations are performed component-we
Since we round up the partial costs, the approximate partial cost of a feasible b could exceed b. To ensure all feasible choices of b are considered, we must also relax the budget comparison. Instead, we compare partial costs to carefully chosen upper threshold r(b). Putting these pieces together yields our approximate Bellman update method.
Theorem 4.7 (Approx Solve). When 7e and k are replaced with the identity function, Algorithm 3 correctly solves any M produced from Defini- tion 3.1. Moreover, Algorithm 3 runs in time O (omm++gm++2A11 ||Cmaz Cmin //mmm/))))))))))))
Definition 4.4 (Approximate Update). Fix any {> 0 and
function : R - Th. For any h E [A]], (s, b) E S,
A and f I,, we define V (S + 1, F) der
(oa(sa)) and for any i E [S].
Vrs F) del max (t 8, (t,bbbt BEB
5. Bicriteria
Vig (1+1, [1 (F.
s,a))b:)l)
(ADP)
Algorithm 3 allows us to approximately solve M finite cases much faster than traditional methods. However, when [B] is large, the algorithm still runs in exponential time. Sim- ilarly to the partial cost rounding in Definition 4.4, we can reduce the size of [B] by considering a smaller approximate set based on rounding. Since we still desire optimistic bud- gets, we use the same rounding function from Definition 4.3 but with a different choice of f.
We then define the approximate update by,
V (s, b) def maxri a) + (1,
(AU)
aEA
Overall, solving the ADP yields an approximate solution. Lemma 4.5 (Approximation). For any h [l]), (s,b) e S, E A, F R.", and E iS + 1], we have that.
Budget Rounding. Rounding naturally impacts the state space, but has other consequences as well. To avoid complex computation, we consider the approximate set I def {[b]e b E [bmin, bmaz]} where [bmsn bmaz] 2 B is a superset of all required artificial budgets that we formalize later. As before, rounding the budgets may cause originally feasible choices to now violate the constraint. To ensure all feasible choices are considered and that we can use Algo- rithm 3 to get speed-ups, we define the approximate action space to include all vectors that lead to feasible subproblems
Ve f)
Σ Pa(s' (,a)Vitz(666
max bEBS-141
s'=
s.1. (s + In.b(1 1, M) S m(b),
where [1, F) is the dynamic rounding of I (f.f (PP(t b.)). Moreover, if Te and is are replaced with the identity function, (AU) is equivalent to (BU).
We use the notation 2., +- ming 2(x) to say that is the minimizer and o the value of the optimization.
6

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
Algorithm 4 Bicriteria
Arithmetic Rounding. Our approach is round each value down to its closest element in an f-cover. Using the same rounding in Definition 4.3, we guarantee that b S [b] I b + L. Thus, [6] is an overestimate 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 controls the error over space.
Require: (M,C,B) B)
I: Hyperparameter: C
2: M {- Definition 5.I (f, 9). ()
3: и, V* t- Algorithm (MM, ())
4: if Vi [B],) -00 then
5: return "Infeasible"
6: else
7: return
Lemma 5.3 (Approximate Cost), Suppose that π E 11 For all h E [H+ +-1 and (s, (s. E S, if b) 00, then (H b) < b AS + 1)(H - -h 11).
8: end if
Theorem 5.4 (Bicriteria). For any SR-criterion CMDP with polynomially- bounded costs and > 0. the choice of l def is (0, (0,c)-bicriteria running in polynomial time O (yim++1sm++ A ||Cmas -omin liss /
of (ADP). From Lemma 4.5, we know this set exactly the set of (a, b) satisfying (s, a) f () s k(b). Putting these ideas together yields a new, approximate MDP.
I+[$+1) ensures Algorithm 4
Definition 5.1 (Approximate MDP). Given any SR- criterion CMDP (M, B), define the approximate MDP M def
(H, A.S.A.P,,A So) where,
Corollary 5.5 (Relative). For any 0, the choice of e def B(T($+1)+1) ensures Algorithum 4 is polynomial time (0, + e)-relative bicriteria for the class of polynomial- budget-bounded-cont CMDPs with SR-cost criteria. This includes all SR-criterion CMDPs with non-negalive costs.
1. S, def S₁ x B where B def {[b]g] b E [Dmine dmaz]]
2. (n b) def ((a,b) E An(s) x gs (r((, +
Pr,6 0) S k()}}
Remark 5.6 (Chance Constraints). Technically, for chance constraints, we first create a cost-augmented MDP that is initially passed into the input. This allows us to write chance constraints in the SR form. Consequently, the S term in Theorem 5.4 is really a larger augmented S. To achieve e cost violation, (McMahan and Zhu, 2024b) showed that an augmented space of size O(SH² [[Cmaz - Cminnl Io /c) is needed, which still results in polynomial-time complexity.
3. Pn((s', (s, 6), (a. b)) def Pa(s' s,a) 1
4. [ss b), a) de a))
5. so def (50: [B,,)
Remark 5.7 (Approximation Optimality). (McMahan and Zhu, 2024b) showed that our assumptions on cost bounds are necessary to achieve polynomial- approximations. Thus, our approximation guarantees are the best possible. Moreover, we can show that our dependency on the number of constraints is also unavoidable. This is formalized in Proposition 5.8.
We again re-ieeine the base case value to ( B)
-X(200
Since we always round budgets up. the agent can make even better choices than originally. It is then easy to see that policies for MM always achieve optimal constrained value. We formalize this observation in Lemma 5.2.
Proposition 5.8 (Multi-Constraint Hardness). m Q(n for some constant d, then computing e-feasible policy for CMDP is NP-hard for any e > 0.
Lemma 5.2 (Optimal Value). For any h e [H 1] and b) E S, (s, [b]p) 2 (s,
5.1. Continuous MDPs
Time-Space Errors. To assess the violation gap of Algo- rithm 4 policies, we must first explore the error accumulated by our rounding approach. Rounding each artificial bud- get naturally accumulates approximation error over time. Rounding the partial costs while running Algorithm 3 accu- mulates additional error over (state) space. Thus, solving M using Algorithm 4 accumulates eтror over both time and space, unlike standard approximate methods in RL. As a result, our rounding and threshold functions will generally depend on both H and S.
We also show that approximations are possible in infinite state settings under certain continuity assumptions.
Assumption 5.9 (Continuity). We assume the caMDP M is Lipschitz continuous. Formally, require that (1)
S [8min, Smar]. J. (2) the reward function is X Lipschitz, (3) the cost function is Xe Lipschitz, (4) the transitions are X Lipschitz each with respect to the state input, and (5) each of these quantities is polynomial-size sized in the input rep- resentation. For SR-criterion CMDPs, we also assume that
7

---

Polynomial-Ting Approximability of Constrained Reinforcement Learning
I has a natural finite equivalent denoted J, g is sublinear short map, and f (Smar Smin) for any constant 2.
sic formulations studied in the CRL literature. We con- clude that for the vast majority of constraints, including all the standard constraints, polynomial-tine approxima- bility is possible. We demonstrated this phenomenon by developing polynomial-time bicriteria approximations with the strongest possible guarantees for a general class of con- straints that can be written in a form that satisfies general policy evaluation equations. Overall, our work resolves the polynomial-tine approximability of many settings, some of which have lacked any polynomial-imme algorithm for over decade. In particular, we are the first to develop a polynomial- algorithm with any kind of guarantee for chance constraints and non-homogeneous constraints.
All we need to do is discretize the state space, and run our previous algorithm on the following discretized CMDP.
Definition 5.10 (Discretized CMDP). Given any SR- criterion CMDP B) we define the discretized CMDP (M, C,B) B) where M = S.A C, 3o) is the discretized caMDP defined by,
1. S del' {[5] SEEO S}
del Ph ( 3,a)ds' 2. (5 a)
3. 3u def ([sole.1) B3
Impact Statement
and Ö' is the cost criterion defined by replacing o with its natural finite equivalent f-
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We that discretization results in small impact to both the value and cost that depend on the continuity parameters. Lemma 5.11 (Discretization). For all h E [H+1], Th E Hr. and π E _1P, we let in denote Th. with each state 8t rounded E(Ar + h + 1) and C (fx) I
References
to [s Then, we have that VIr (Fr) 2 (Tt)
M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, and U. Topcu. Safe reinforcement learn- ing via shielding. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10.1609/ aaai caai.v32i1.11797 URL.htts:://ojs http://p//...aaaattreee//eeeeeee
Hp)Hr Hr maaxxmmx - ( (Tr) + E(de + H)) (8men - 8min) (H- - h + 1). For sureatteure constraints, the cost incurs an ad- ditional factor of 1/ 1/Pmin: where Pmin denotes the smallest non-zero transition probability for M.
org/
Overall, using our previous bicriteria on M yields our ap- proximation results.
E. Altman. Constrained Markov Decision Processes. Chap- man and Hall/CRC, 1999. doi: 10.1201/9781315114222.
5.12 (Continuous Bicriteria). For any SR-criterion CMDP satisfying Assumption 5.9 and any def > 0, the choice of discretization e/2
Theorem
Q. Bai, A. Singh Bedi, and V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learn- ing via conservative natural policy gradient primal-dual algorithm. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 376))6737-6744,, 6 2023. doi: 10.1609/ aaai. mmai.v37i..2588 URL
ts approximation la def e/2 rithm 4(M) is a (eic)-bicr running in time O (Hom+) (10++154422 A |lmaar - Cmin 113m fc3m) where $ O((A, + +e+ H max(Cmax V'ma) (mma)) (Smaz Smin) //ec.. This time polynomial so long as |smax Smin ((M)). Moreover, finostt-ure/anntinn constraints enjoy the same guarantee with an additional factor of pmin in S.
and
(A,+Ac+Ap)) max(Cmuz Fmaz Mmmax
1+(++1)H ensures Algo-
index php/ http/////aaattte//eeeeee/e//////
F. Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause. Safe model-based reinforcement learning with stability guarantees. In I. Guyon, U. V. Luxburg, S. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.,
Corollary 5.13 (Simplified). For continuous-state SR- criterion CMDPs satisfying Assumption 5.9, there exist polynomial-time (c, -)bbiritteria solutions for expectation constraints, almost-sure constraints, anyiime-almos--sre constraints, and any combinations of these constraints.
2017. URL https::/ neurips. oc Cc/ cccpappr_fileeeeeeeeeeeeeeppppee 7 7666bed59621333317700 6ba 3bd3d3ac3323adadaaadeeea pdf.
6. Conclusion
A. Bhatia, P. Varakantham, and A. Kumar. Resource constrained deep reinforcement learning. Proceedings of the International Conference on Automated Plan ning and Scheduling, 29(1):610-620 5 2021. doi:
In this work, we studied the question of whether polynomial- time approximation algorithms exist for many of the clas-
8

---

Polynomial-Timg Alll of Constrained Reinforcement Learning
10. 0..16099icaps..29113388. httpasssttttttttossssst/
Processing Systems, volume 31. Curran Associates, Inc.,
2018. URL https::/procceddii ngs neurips.
cc/ /f/ 4 4tee1499036227666666e08887799999 pdf.
V. Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & Con- trol Letters, 54(3):207-213, 2005. ISSN 0167-
6911. doi: http:://oo.oggll..00..eeeeeeeeem
A. Coronato, M. Nacem, G. De Pietro, and G. Paragliola. Reinforcement learning for intelligent healthcare applications: survey. Artificial Intelligence in Medicine, 109:101964, 2020. ISSN 0933-3657. doi:
007. URL https: UKL.sbbee//ww..ccennndeeeee..... scien
D. M. Bossens and N. Bishop. Explicit explore, exploit, or escape (e4): Near-optimal safety-cone cenett-conttrained reinforce- ment learning in polynomial time. Mach. Learn., 112 (3):817-858, 2022. ISSN 0885-6125, doi: 10.1007/ s10994-022-00220--z URL https: /tapps///dd/ /ttp//do..oo// /ttp://olo..o..../////o///// 1007/s10994-022-0002
URL http:///bo..n////looooo//atattad science/arte
C. Fan, C. Zhang, A. Yahja, and A. Mostafavi. Dis- aster city digital twin: vision for integrating artificial and human intelligence for disaster man- agement. International Journal of Information
K. Brantley, M. Dudik, T. Lykouris, S. Miry- oosefi, M. Simchowitz, A. Slivkins, and W. Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. In NeurlPS, 2020. URL
Management, 56:102049, 2021. ISSN 0268-4012.
doi: http://d..ogg//looooooiinnnnnnoo URL.
neurips.com hrrripsscc//epee//222//aaaaa boc275388feead42235ff7777edd html.
Abstracte
A. Feinberg. Constrained discounted markov deci- sion processes and hamiltonian cycles. Mathematics of Operations Research, 25(1):130-14)) 2000. doi: 00.1287mm00:25.1130152222
A. Castellano, H. Min, E. Mallada, and J. A. Bazerque. Re- inforcement learning with almost sure constraints. In R. Firoozi, N. Mehr, E. Yel, R. Antonova, J. Bohg, M. Schwager, and M. Kochenderfer, editors, Proceed- ings of The 4th Annual Learning for Dynamics and Control Conference, volume 168 of Proceedingy of Ma- chine Learning Research, pages 559-570. PMLR, 6 2022. URL UtL.tts:: htt.ctpp:://rrceeddggg w.lr.press/ v168 //s/aastellano2222 html.
URL ht ttsp:: /doi. org /2g/10.10 10. 1287 moor 25 25.1.130.152.. 15210.
J. F. Fisac, N. F. Lugovoy, V. Rubies-Royo. S. Ghosh, and C. J. Tomlin. Bridging hamilton-jacobi safety analysis and reinforcement learning. In 2019 Interna- tional Conference on Robotics and Automation (ICRA), page ICRA.2019 URL https: //t::///oiiio orr/0100..00. 1109/ICRA.. 2019. 00199.87999 8794107.
IEEE Press, 2019. doi: 10.1109/
R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick. End- to-end safe reinforcement learning through barrier fune- tions for safety-critical continuous control tasks. Proceed- ings of the AAAI Conference on Artificial Intelligence, 33 (01):338773396) Jul. 2019. doi: 1.11609/aai.v33000 33013387, URL httpst /ttpttttp:///saaa.te. //t.://a..aaaa........aa//a/aaa. hhppAAAI/aara http//AAAaaatiill//veeee///// aaai. org/ index.
J. Gareía, Fern, and o Feránndez. A comprehen- sive survey on safe reinforcement learning. Jour- nal of Machine Learning Research, 16(42):1437-1480, 2015. URL http://jmlr. org worggppaprs/vvl... harcial5a.html.
W. C. Cheung. Regret minimization for reinforcement learn- ing with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems, vol- ume 32, 2019. URL hitps /
S. Gros, M. Zanon, and A. Bemporad. Safe rein- forcement learning via projection on safe set: How to achieve optimality? IFAC- PAAC-appesO,nLine, 53(2):8076-8081, 2020. ISSN 2405-8963. doi:
neurips oc https/ccccccpppe1///1/1.... httpa/::///pcceppeeeeeeeee
URL https::/www.scceeeeddiieee
pdf.
sctenceearrticele///////222383/9 21 IFAC World Congress.
Y. Chow, O. Nachum, E. 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 Information
S. Gu, L. Yang, Y. Du, G. Chen, F. Walter, J. Wang, and A. Knoll. review safe reinforcement learn- ing: Methods, theory and applications, 2024. URL https: ptttps://rxiv...o http::///arrv..orr//bb/2........

---

Polynomial-Tine Approximability of Constrained Reinforcement Learning
A. HasanzadeZZomuzy, A. Bura, D. Kalathil, and S. Shakkot- tai. Learning with safety constraints: Sample com- plexity of reinforcement learning for constrained mdps. Proceedings of the AAAI Conference on Artificial In- telligence, 35(9):766777674 5 2021. doi: 16.1609/ URL /ttps://ojs..aaa. index. AAA httpp////A//aattreeeeeeeee//////
Learning Research, pages 4321-4329. PMLR, 02-04 May 2024b. URL ptcttpss//proceeeee ngs .ms.mlr. press/ v223 mmmmaaan24...haa.
mmlr.
G. Paragliola, A. Coronato, M. Nacem, and G. De Pictro. reinforcement learning- based approach for the risk man- agement of e-health environments: A case study. In 2018 14th International Conference on Signal-maag Techmol- ogy & InternetBaased Systems (SITIS), pages 711-716, 2018. doi: 10.1109/SITIS 2018.. 14.
M. Khonji, A. Jasour, and B. Williams. Approximabil- ity of constant-horizon constrained pomdp. In Proceed- ings of the Eventy-Fighit International Joint Confer- ence on Artificial Intelligence, IJCAI-19, pages 5583- 5590. International Joint Conferences on Artificial Intel- ligence Organization, 7 2019. doi: 10.24996//jccai./019// 775. URL https: /ttp::///doi. wtt.c//...ror....29///eoooo 2019/775.
S. Patemain, L. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances in Neural In- formation Processing Systems, volume 32, 2019. URL https://proceeding..eeee cc /cc/ppper_.illee/ppper///////11 1La26111aac113331111116690022 Paper.. pdf.
Kolesar. A markovian model for hospital admission scheduling. Managemtent Science, 16(6):B344-B39) B39, 1970. ISSN 00251909, 15265501. URL http: /tttt://www... jstor. /tt.rorrrg//taale/2228222
H. Peng and X. Shen. Multi-agent reinforcement learning based resource management in mec- and uav-assisted vehicular networks. IEEE Journal on Selected Areas in Communications, 39(1):31-1441 2021. doi: 10.1109/ JSAC.2020.303698
Li, D. Fridovich-Keil S. Sojoudi, and C. J. Tomlin. Augmented lagrangian method for instantaneously con- strained reinforcement learning problems. In 2021
60th IEEE Conference Decision and Control (CDC), page 2989. IEEE Press, 2021. doi: 10.1109/ CDC45484 2021 96630088 htRpst/ httttts:://o..orrrt //doi.oorrr 2021. 96830888
M. Roderick, V. Nagarajan, and Z. Kolter. Provably safe pac-mdp exploration using analogies. In A. Baner- jec and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Ma- chine Learning Research, pages 1216-1224. PMIR, 4 2021. URL httpsttss////ooceeeeee v130/roderick2la.o html.
R. Li. Z. Zhao, Q. Sun, C.-L. I, C. Yang, X. Chen, M. Zhao, and H. Zhang. Deep reinforcement learning for resource management in network slicing. IEEE Access, 6:74429- 74441, 2018. doi: 10.1 109//09/SS 201 28018.2881990 1644.
mlr. wtt.:mess..p///.p.mmm.mm.m..m. press/
H. Mao, M. Alizadeh, I. Menache, and S. Kandula. Re- source management with deep reinforcement learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks, HotNets '16, page 50-56, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450346610. 3005745..000550. URL httt:::/ddoi.orrt 1145/3005745.30055
G. Thomas, Y. Luo, and T. Ma. Safe reinforcement learning by imagining the near future. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1 13859 13869. Curran Associates, Inc., 2021. URL /tt.teed/// neurips. cc 22227cc1226681112212222222222220
doi: 10.1145/
Paper.
pdf.
McMahan. Deterministic policies for constrained re- inforcement learning in polynomial time, 2024. URL betps://arxile wwt./bgg///ooooooooooo..ooo.. abs 220...2405..0 141883
Y. Tsai, A. Phatak, P. K. Kitanidis, and B. Field. Deep Reinforcement Learning for Disaster Response: Navigat- ing the Dynamic Emergency Vehicle and Rescue Team Dispatch during a Flood. In AGU Fall Meeting Abstracts, volume 2019, pages NH33B-14, Dec. 2019.
J. McMahan and X. Zhu. Anytime-constrained multi-agent reinforcement learning, 2024a. TRRh:tts:///aae
org/abs/2410.22 23637.
S. Vaswani, L. Yang, and C. Szepesvari. Near-optimal sample complexity bounds for constrained mdps. In S. Koyejo, S. Mohamed, A. Agarwal, D. Bel- grave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, vol- ume 35, pages 3110-3122. Curran Associates, Inc.,
J. McMahan and X. Zhu. Anytime-constrained re- inforcement learning, In S. Dasgupta. S. Mandt, and Y. Li, editors, Proceedings of The 27th In- ternational Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine
10

---

Polynomial-Timg Apploxiabiiyyyyy of Constrained
Reinforcement Learning
2022. URL http:://prooeeddngg..rrrri cc /ttpppeerefllleeppppe///////////
pdf.
Y. Wang, S. S. Zhan, R. Jiao, Z. Wang, W. Jin, Z. Yang. Z. Wang, C. Huang, and Q. Zhu. Enforcing hard straints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In A. Krause, E. Brun- skill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 Proceedings of Ma- chine Learning Research, pages 36593-36604 PMLR, 2023. URL.httss: / pro.ceddeeeeeeeeeee.oo ngs m1 press/ v202 /w/p//aangaaaaaaa//am/.. html.
H. Wei, X. Liu, and L. Ying. Triple-q: A model-free algo- rithm for constrained reinforcement learning with sub- linear 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 In- telligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3274-3307. PMLR, 3 2022. URL https: h/ppoceeediggssseeeeeeeeeces..se mlr, mlr.press/ v151/wei2e www....weeee... html.
C. Wu, B. Ju, Y. Wu, X. Lin, N. Xiong, G. Xu, H. Li, and X. Liang. Uav autonomous target search based on deep reinforcement learning in complex disaster scene. IEEE Access, 1111227--112444 2019. doi: 10.1109/ACCES. 2019.2933002.
H. Xu and S. Mannor. Probabilistic goal markov decision processes. In Proceedings of the Twenty-Secan Second Interna- tional Joint Conference on Artificial Intelligence Volume Volume Three, IJCAI page 2046-2052. AAAI Press, 2011. ISBN 9781577355151.
W. Zhao, T. He, R. Chen, Wei, and C. Liu. State-wise safe reinforcement learning: survey. Proceedings of the Thirty-Second International Joint Conference on Arti- ficial Intelligence, IJCAI '23, 2023. ISBN 978-1-956792- 03-4. doi: 10.24963/iecai20233766 //doi.org/ 24963/ ijcai. htt.:/................3
URL https:

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
A. Proofs for Section 2
A.1. Proof of Proposition 2.3 Proof.
Expectation Constraints, We define CM def
EM
-h=1 CHj
Under this definition, the standard policy evaluation
equations imply that,
+ Σ Pa s, +.
(8)
It is then clear that this can be written in (f.g)-form for being summation and g being the identity. It is easy that these functions have the desired properties.
Chance Constraints. Let M denote the initial caMDP. We define CT def
PM
E cb > B). We see that the
probability be recursively decomposed follows for the anytime variant:
C% (Th, c) = [cn +a> B] E Ph
+0>
For the general invariant, we only include the indicator term step H. To write this into the desired form, define cost-augmented MDP M that keeps track of the cumulative cost at each step as in (McMahan and Zhu, 2024a). In particular, the anytime variant has the immediate cost defined to be cn((s, é), a) expected cost for the new M exactly corresponds to the probability cost. Thus, the claim holds.
def
[ea (s, a) + > BJ. Then, it is clear that
Almost-sure Constraints. We define Oß max
TH+1 1
Ei=l CFI
to be the worst case cost. Under this definition,
is known that the worst-case cost decomposes into,
(Tr) c, a) + max ( s, 1
(T4+1).
(10)
is then clear that this can be written (ffg))-orm for f being maximum and g being the indicator. Properties of maximum imply that max,' (C(s") c) max, C(s') + Thus, the total combination short map, and the rest of the needed properties can be seen to hold. The anytime variant follows similarly.
A.2. Proof of Theorem 2.5
Proof. The theorem follows immediately by translating the results the SR-criterion into their original forms in the proof above.
B. Proof for Section 3
B.1. Helpful Technical Lemmas
Definition B.1 (Budget Space), For any s S, we define (s) def (0), and for any h E [H),
(s) def
U
(n(s,a)+f (s. a)) be))
(11)
a bEX,, Bati(e")
We define B def Un. (s).
Lemma B.2 (Budget Space Intution). For all and h E [H 1).
(s) (be Rdd E
E Hi. (s sT(Th) (TTTT) 6))
(12)
and [B((s)] S A S Thus, B can be computed in finite time using backward induction.
Proof. We proceed by induction on h. Let E be arbitrary.
12

---

Polynomial-Ting Approximability of Constrained Reinforcement Learning
Base Case. For the base case, consider / H In this case, we know that for any ITP and any HH+1 C (TH+1) = 0 E {0} = (s) by definition. Furthermore, ( = == A A S*
Inductive Step. For the inductive step, we consider h v H. In this case, we know that for any x E IIP and any th E Hh. s = (Th) and a = ny (T.), then the policy evaluation equations imply,
( = ca, a) + +f g s, (T,, s')).
We know by the induction hypothesis that 1 a, 8') E Bn+1(s). Thus, by (11), (T.) E (s). Lastly, we see by (11) and the induction hypothesis that,
B& (+)] S A II [B)+((')1 s III 1 su=r A 8h AE sh-t
This completes the proof.
B.2. Proof of Lemma 3.2
Proof. First, let Viz (Th,b) b) denote the supremum in (5). We proceed by induction on h.
Base Case. For the base case, we consider h = H + 1. Definition 2.1 implies that C#+1 (TH+1) 0 for any E II Thus, there exists a E IT satisfying C (1+2(TH+1 Σ b if and only if 2 O. We also know by definition that any policy π satisfies
= 0 and no feasible policy exists (T b) = -oo by convention. Therefore, we see that V (T X(b20)- Then, by definition of Vi+ it follows that,
1 X(b200 =
Inductive Step. For the inductive step, we consider any S H. If VV (Th, b) = then trivially Vy 2 (T, b). Instead, suppose that Vi (Tr, -c. Then, there must exist ITP satisfying C7 S b. Let a" (T.).. By (SR), we know that,
(T.) cn(ss + f.g (Pr(5') 8, a)) (Tn,
For each s' E S, define by, del (hu a', and observe that by. E B. Thus, we see that (a", bb) E A B and (8) + ( (,,)))b S b, so (a", b²) E An by definition.
Since क satisfies Ch+ (Th,at "²)'")))"""""")"" S by, we see that Vi+ (b,)) 2 (TA, a', 8'). Thus, the induction hypothesis implies (i b)) 2 Vi (s(,b,)) 2 Vi (T,, a s'). The optimality equations for M then give us,
(s, max (n((s,b), a) + aEAn(s.))
(n(s,a) Σ Ph ($1.)))
max (n(b))
2 rn((s,a") + E Ph(s' (s
2 2n(ssa")) Pa(s'' (o(s'|ssa"")a
(T))
The second line used the definition of each quantity in M. The first inequality used the fact that (a',b") (s, b). The second inequality used the induction hypothesis. The final equality used the deterministic policy evaluation equations.
Since was an arbitrary feasible policy for the optimization detining VA (Th, b), we see that Vi 6) 2 (T, This completes the proof.
13

---

VyT(8o) Polynomial-Time Approximability of Constrained Reinforcement Learning
B.3. Proof of Lemma 3.3
Proof. We proceed by induction h.
Base Case. For the base case, we consider H + By definition and assumption, ( -X(b203 > -00. Thus, it must be the case that 2 0 and so by Definition 2.1 C#+1 (s, = <
Inductive Step. For the inductive step, we consider any I H. We decompose (s, (a. b) where we know (a, b) E (n, 6) since V (s, b) -o Moreover, must be the case that for any s' with (s 8, 0 that V ( (8', by)) otherwise the average reward would be ooo which would imply contradiction:
(s, a)( + Σ Pa(s' V, (b(bb)
a),(s,a) .... Pr(s' 8, s,a)(-oo) +...
=00.
Thus, the induction hypothesis implies that (
(5', (b,)),)))) S by for any such s' S. By (SR), that,
(T, cs(s a) (P'( 1 (.))))
() 1 ( (s' |s,))}b
b.
The second line used the fact that f is non-decreasing and g is a non-negative scalar. The third line used the fact that (a, b) E bs, This completes the proof.
B.4. Proof of Theorem 3.4
Proof. If V B) = -oo, then we know by Lemma 3.2 that,
x0 VJ B) 2 sup (i)(s)
rEll
(13)
s.t. (s0) < B.
In other words, feasible exists, so Algorithm reporting "Infeasible" is correct. On the other hand, suppose that (80, B) >> -oo and let x" be any solution to the optimality equations for M. By Lemma 3.3, we know that Cf (So, B) < B implying that x² is a feasible solution. Moreover, Lemma 3.2 again tells us that,
ViT (so, B) = Vi- (80, B) 2 sup
=EnI
(14)
s.t. Ci (8o) & B.
Thus, x² is an optimal solution to (CON) and Algorithm correctly returns Therefore, in cases, Algorithm correct.
C. Proofs for Section
Formally, Phb can be defined recursively by (t, (t, F) del fro (t+1, [ (( (.a))oo)
with base case (S
F) F.
By convention, we assume max -0
14

---

Polynomial- Time Approximability of Constrained Reinforcement Learning
C.I. Proof of Lemma 4.2 Proof. First, we show that,
n.b (t,
max bEBS-(+1
Σ Pu(s' s.a) (s'.bb)))))
(15)
g'=
s.t.
Cr a) JT. (1, F) S b,
For notational simplicity, we define ( def Es Pa((') 8, a. (8', by). We proceed by induction on t.
We just need to show that the maximum in (15) also matches this expression. First, observe objective is the empty summation, which is O. Also, fa.a (S + 1, F) = F, so the constraint is satisfied iff cs a) + F I b. Thus, the maximum is 0 when en (x, a) + F < b and is -oo due to infeasibility otherwise. In other words, equals ((ex(e.))+F50f as was to be shown.
Base Case. For the base case, we consider = S + 1. By definition, we know that (t,
Inductive Step. For the inductive step, we consider any 1 S S. From (6), we that,
VE (1, F)
max Pv V/ (1, n.6 (1 + 1,5 ( b.EB
max Pa(l a, V (1,b,.+ + b.EB
V + 1)
max
bEB
P,(t|s,a)Vi V. + 1)
max
max bER (1 (P
6,
max
(t 8, (t, + (i
hEB 111
(1 (F ((le..))))))
Pa s, a) Vi + V. + +1)
max bEBS-141
max bEB (1
(t)
The second line used the induction hypothesis. The third line used the fact that the first term is independent of future b values. The fourth line used the properties of maximum. The fourth line used the recursive definition of fr.g (t. F). The last line used the recursive definition of b.b (t).
For the second claim, we observe that,
V (s. b) =
max a.b, +f 9(Pa Sb (s)
an(s,)) + EPnss' Ps ii
ra(s,a) Σ Pa(s 8, s,a) ex(ss))+/
a.b.
rn(s,a)+ + Ph(d'' | (s')
max max
= =max7h(8,a) +
max
Epa( (,a)Vi+1('',bb (8.
= mma maxx7a(8,0)
h.6 (1,0). (1,
15

---

Polynomial-Ting Approximability of Constrained Reinforcement Learning
C.2. Proof of Lemma 4.5
Proof. Recall, as in the proof of Lemma 4.2, we define (t) def E Ph(''s 8, V.a) by:) to simplity expressions. We proceed by induction on t.
Base Case. For the base case, we consider t = S + 1. By definition, we know that Vi,,(t F) (x.)+ ( Fsw())3 We just need to show that the maximum in (7) also matches this expression. First, observe objective is the empty summation, which is O. Also, (S + 1, F) = F, so the constraint is satisfied iff cx a) + f I k(b). Thus, the maximum is 0 when on (8, a) + P < x(b) and - oo due to infeasibility otherwise. In other words, it equals - -(Sm())))++$M(()) as was to be shown.
Inductive Step. For the inductive step, we consider any t S S. From (ADP), we that,
h.b (1, F) max (t 8, a) V (t) + Vn.5 (1+ 1, [1 (F. (PP(((( (1+((++)))
b
= max (t 8, (1,, + bcE
max
bEBS-t
max b
max bEBS-
PR 8, 8, + (75(
(((s)))f2 [F o (.t.))))
Pa 8, s,a) (t,bb,) + 17 + 1)
max
BEB -
cn(s,)) ((
max bEBS-
PM s.a) bb) + (t+++1)
(r(s,)) (t Sm(())
(t)(
max - ( Sm(()
The second line used the induction hypothesis. The third line used the fact that the first term is independent of future b values. The fourth line used the properties of maximum. The fourth line used the recursive definition of fi, (t, F). The last line used the recursive definition of V/ (t).
For the second claim, we simply observe without rounding that (ADP) is the same as (6). Thus, Lemma 4.2 yields the result.
C.3. Proof of Theorem 4.7
Proof. The fact that Algorithm 3 correctly solves any M follows from the fact that (AU) is equivalent to (BU) via Lemma 4.5,
For the time complexity claim, observe that the number of subproblems considered is 2(HS>A|BB){)) A|
and the time needed per subproblem is O(Bl) to explicitly optimize each artificial budget. Thus, the running time is O(HS² 1|1 We can further analyze |F] in terms of the original input variables. First, we claim that J C [Dmin bmax + ESJ. To see this, observe
that the rounded input at state t ++ 1 1is,
f(F, (bll ((Fbb)) f (Pa a,)))) 2 g(P |s, a))mmm 2 bmin-
d==1
d=11
Here, we used the fact that f is non-decreasing and the weighted combination is short map rooted at O. Similarly, we see,
f(P, (be.) S fF, (bl1)) + 1(t
< i g(Pn s. ab) +) + l(t 1)
*=1
} g(Ph s a.a) + lt
$ 4-1
s Umaz + lt.
16

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
Under this assumption, it is clear that the number of integer multiples of residing in this superset is O((mmax + E binin) /f) per constraint. When considering all constraints once, this becomes OeIama + LS bmin 1| /// (mm) O Umin Il /0m + 5T). Incorporating this bound into the runtime then gives 0 A
[ Iibaa min Il )
Similar to the reasoning above, we can see the cost of any policy, and thus the artificial budget set, is contained within [Mmmn Hemaz] Using this fact, we get the final running time O(1 gm=+2 A |[maa Cmin 11 / m(m)
D. Proofs for Section
D.I. Time-Space Error Lemmas
Lemma D.1 (Time Error), For any h E [H], a E A. if $ bb+ z, then,
JR.b (,, (1. 0) S Fr.b (1,0) f. (1. 0)
(16)
Here, we translate scalar x > 0 into the vector (z.....z))
Proof. By definition of J/,
S. E, (1,0) - (1,0) /00.//00//..... k,)))K))
= f | s,a));,
2 f ssa)){b
= f
s(Ph(s' s,a))6>)
-1,
The second and fourth lines used the fact that f is identity preserving. The inequality uses the fact that f is non-decreasing and g is a non-negative scalar, so the total weighted combination also non-decreasing.
Similarly, we see that,
f (1,0) = f(0,f 9(Pr(s' (,))))())
6'
S 1 (sb +z)
$f ( |s,a))by +
= f(0, f g( | (s +
JK (1,0) +
The second and fifth lines used the fact that / identity preserving. The first inequality again uses the fact that the weighted combination is non-decreasing, The second inequality follows since the weighted combination short map with respect the infinity norm.
S || =1lag holds for any infinity-norm short map a, we see that (a(y+z)-a(()) < || xo Moreover, if is non-decreasing and z is a positive scaler treated as a vector, we further have a(y + z) - a(y) Ja(y + =) - a<y)) < || = z. This final inequality immediately implies that a(y + =) S a(y) + z. When a is vector-valued, this incquality holds component-wise.
In particular, since
Since f is associative, we can define (, F) = recursively.
s,a))br) either forward recursively or backward
17

---

Polynomial-Ting Approximability of Constrained Reinforcement Learning
Lemma D.2 (Space Error). For any h [H], a a A. b Rm and t E [S + 1}.
(t, - (t, f,, + (5 - ++ 1)e.
(17)
Proof. We proceed by induction on I.
Base Case, For the base case, we consider t S 1. By definition, we have that fr,b(5 + 1, 1.u) = u [S + +1.u). Thus, the claim holds.
Inductive Step.
For the inductive step, we consider any / S The recursive definition of ia. implies,
(t, u) 1 ()))b)))
2 pei 1 s,
(,,))(t
g(Pa(5s)) s,a)b,))
s
2 f(f(u.g(Phtt (..P((((s.)))b))))
f g(Pr(s'' s,,a)rr))
#'=+1
= =( a)),,,
g(Pr(s' (s,a)b/)))
s'=+1
(t,
The first inequality used the induction hypothesis to replace f with f, and the second inequality used that f is non-decreasing in either input and [be 2 b. The other lines use f's associativity.
Similarly, we see that,
(t,((1, = 1, s,a))b)1e)
( -5-1)6
s,
= =[[[f(. ( b.,))
f s(Pn(5') (,a))b))) + (S t)e
s'=+11
SJ ( ())))))))))))) +l,
I g(Pa(s' s,,)),)) + (S t)e
S
*1111
s
fff(u, ( a)))))
f g(Pr(s' (9,(''(s,a)bb)))) (s,a)b))) + + t 1)4
s'
= f(u,f(o(Pr(t s,
((Pa (s,)),)))) + + t 1)4
=41
(t (S-
The first inequality used the induction hypothesis to replace f with f. The second inequality used that f is non-decreasing in either input and [x I x + f. The third inequality used that f is a short map in the first input. The other lines use f's associativity.
This completes the proof.
D.2. Proof of Lemma 5.2
Proof. We proceed by induction on h.
Base Case. For the base case, we consider h H Since [b], 2 b, we immediately see,
V (s, [b1,) -X(12,200 2 -X6200 = (s.
(18)
18

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
Inductive Step. For the inductive step, consider any h S H. If (s, -o, then trivially (s, (b],) 2 (s, b). Now, suppose that (s, -c. Let be solution the optimality equations for M. Consequently, we know that V b) = (s, b) > -0,, which implies (a", b²) (s, b) E As b). By definition of An (s,
(s. + f (1,0) cx ((a((s' s, S - [b]
(19)
For each s' E S, define 8 del [6 We show (a",b;) E As. (b,,) as follows:
ca(s,a0) + fa.0 (1,0) (n(ssa))++ / (,.. (1,0) +
1,6
S (n (1, + +
- [b], +1(-+1)
= =((blp)
The first inequality follows from Lemma D.2. The second inequality follows from Lemma D.1 with 6 < b* + The third inequality follows from (19). The equality follows by definition of K. Thus, (a", b²) E An [b]e).
Since by E B by definition, the induction hypothesis implies that Vitz (s', 82) 2 Vitt1 (b',b)) = V (5',b))) optimality equations for M then imply that,
b2). The
V (s, [b]e)=
rh + Ph a,,a (5',
max (e,
2 (s, + Σ 1 (3 (d.02)
2n((sa")) + Σ Pa (s, (51b))
= (8,
().
The first inequality used the fact that (a b*)= E (n, b). The second inequality follows from the induction hypothesis. The last two equalities follow from the standard policy evaluation equations and the definition of æ, respectively. This completes the proof.
D.3. Proof of Lemma 5.3
Proof. We proceed by induction on h.
Base Case. For the base case, we consider H + 1. By definition and assumption, (g, = -X(6203 > -00.
Thus, it must be the case that > 0 and so by definition C7 (s,b) = 0 -0 b.
Inductive Step. For the inductive step, consider any h H. As in the proof of Lemma 3.3, we know that (a, b) (s, E Ás 6) and for any s' S with Ps(s') s, a, that V (s',bz) > -c. Thus, the induction hypothesis implies that C%+1 (s', bw)) < by + CSS () ht) for any such s'. For any other s', we have g (Pa(8') (.a)) (() = 0 by assumption.
Thus, the weighted combination of E+ ( (8', (x))
equal to the weighted combination of b' where io def C (8', (be)) if
19

---

Polynomial-Tine Approximability of Constrained Reinforcement Learning
(s(8') 8, > and V. def
otherwiss. Moreover, we have D' <b+ A( + 1)(H - h) since & >>> 0. Thus, by (SR),
(s, ca(s. + (f (sa))) (
ca(s, ( (1,0
S cc(ss,)) + +, {S + 1)(H h)
<x(b) + + 1) h)
= b+ + +) - - +).
The first inequality used Lemma D.1. The second inequality used the fact that (a, (a, E (s, The last line used the definition of This completes the proof.
D.4. Proof of Theorem 5.4
Proof. If (CON) is feasible, then inductively we see that (s0, [B],) -c0. The contrapositive then implies if V (su. [B] = -o, then (CON) is infeasible. Thus, when Algorithm 4 outputs "Infeasible", it correct.
On the other hand, suppose (so. [B] > -cc and that is optimal solution to M. By Lemma and and Lemma 3.2, we know that VIT (so: [B],)= 2 (so,
(so, B) > V*. Also, by Lemma 5.3, know that ČT (so, B + 2(1 + (S + 1). Our choice of 1+1++1)4 then implies that ÓTH = CT [B1) 12) I BB4 Thus, т is an (0, <) addiiive bicriteria approximation for (CON).
[B]e) I [B], L(S 1) s
Both cases together imply that Algorithm is a valid (0, e -bicrittte
Time Complexity. We immediately from Theorem 4.7 that the running time of Algorithm 4 is at most O [12m1 (12m+15m+2 52m+2 A| ||Cmaz Cmin 11' /em To complete the analysis, we need to bound [B]. First, we note [B] is at most the number of integer multiples of in the range [bmin bmaz] S [miis Cmax]" For any individual constraint, this number is at most ((H(caar - Hmmi))/ )/()
({)= I S(H2S(( S(Cma - cmin)/e) using the definition of I+(++)H Thus, O(11225 |maz Cmin (E) Squaring this quantity and plugging it back into our original formula yields: O 6mm-1 54m+2 A |[maa Cmin fmmm f
the total number of rounded artificial budgets
D.5. Proof of Proposition 5.8
Proof. We consider a reduction from the Hamiltonian Path problem. The transitions reflect the graph structure, and the actions determine the edge to follow next. To determine a Hamiltonian path exists, we can simply make an indicator constraint for each node that signals that node has been reached. is then clear that relaxing the budget constraint does not help since we can always shrink the budget for any given e-slackness. Thus, the claim holds.
D.6. Proof Lemma 5.11
Proof. We proceed by induction on h.
Base Case. For the base case, we consider h Hf + 1. By definition, we have (F+1(TH+1) 0 V4+1(TH+1) and (T (T+1))
20

---

Polynomial-Tinge Approximability of Constrained Reinforcement Learning
Inductive Step. For the inductive step, we consider any S H. For simplicity, let x def {(>, + Xp) Hr Taaaz (8mar 8min).
The standard policy evaluation equations imply that,
( + ;
= =ra([s]e, Σ f 8't6
J''=8 (s [ a)dss Vi Viss (ft+1)
=ra([s],,a)) + [ Pals') a ( (F
r a) + / Pa(s')
x(H - hi)dd'
= =ra([s]e, { Ph(s'
x(H h)
rn( - lx 1 (Ph( (,,)) (xp) (T x(H h)
= (T)) EA, - ldpp (. Vitti (T+i(Tnt1dds - x H - -h)
2 (T.) EA - -Ed HxpHrmad' (Smax Smin) - x - h)
(Th) -((A, * Hraa (Smar Smin) x(H H h) (T.) x(H -h 1).
If we let del e(Ae + Ap) Cmaa (Smoz 8min), we also see that,
(%.)) = en (Tole ( (e)
cn((sle, + 1 d't
J Pa ajd's
= cc((sse,aa) + P | a)
I cn([s]g + Ps(s' [s o) + y(H - h))
< (n([s a) + Ps I [ + v(( - h)
I (s, + lA. + (Ph('s s,a) 07, + y(H - h))
= (s. + Pa(s' s. CT) + Dd + Exp f T (h + y(H h)
< (Th))) + tde + Exp f HCmav + y(H - h)
< (Th) + +td + Explsmax - 8min) H + y(H h)
S (TT) + -((e + App - 8min) Hemas y(H h) (T()) + y(1l h +1.
We note the above also holds P is replaced with g(P) for a sublinear short map
For almost-sure constraints, the proof slightly different since we need to keep the inner integral by definition of the
21

---

Polynomial-Timg Approximability of Constrained Reinforcement Learning
worst-case cost for continuous state spaces. Letting
def [(Ae + X²) H Cmao (8maz - 8min D/D////m the bound then becomes,
(f.) = (r([sle, a) + max Ps m
[)) > (fh+))
s'4
= ca([8le>> + max
Pa(8'
[sle, a)ds's > (
s'=8'
Phls'
[sle= a)ds'
= =cu[[s] a) + max
s'=
Ch+1 (fn+1)
ps
5'+
= cn([s]e + max
(fn+i)ds' /ps Ps [ (f
8'=3"
s'+e
< <an((81e))) + max
Pals' [s] (C) y( h))ds's /pw
8'+
S <cn([see a) + max
Pa(s' 2
C)+ (Th+4))))))))) /ps + +(H h)
s==3"
L Pald')
S (s) + le + max
Jam
+ +0 max
Ch Ch+1(T++1dd+ /d /p8 -
Ps s.
S (s + max
Ch Ch+1(Tn + tde ll Ayy Pmin
S'S Ss
ps
+ vv(l h1)
(T(T)) + lde l &xxpH Cman / Pmin + y(H h))
I CT(Tn) + +l()e >pp Smin) 3min) Cman Priinnn/////i/i/ Pmin + y(H h)
(TT) + +u(H - h +)
D.7. Proof of Theorem 5.12
Proof. The theorem follows immediately from Theorem 5.4 and Lemma 5.11.
E. Extensions
Markoy Games. It is easy to see that our augmented approach works to compute constrained equilibria. For efficient algorithms, using - oo to indicate infeasibility becomes problematic. However, we can still use per-stage LP solutions and add a constraint that the equilibrium value must be larger than some very small constant to rule out invalid -oo solutions. Alternatively, the AND/OR tree approach used in (McMahan and Zhu, 2024a) can be applied here to directly compute all the feas-bee states.
Infinite Discounting. Since we focus approximation algorithms, the infinite discounted handled by using the idea of effective horizon. We can treat the problem a finite horizon problem where the finite horizon H is defined so that Σi= " Cmaz < c' By choosing c' and small enough, we can get equivalent feasibility approximations. The discounting also ensures the effective horizon is polynomially sized, implying efficient computation.
be immediately
Stochastic Policies. For stochastic policies, our approximate results follow from simply replacing each max, and max;, with general linear program over finite distribution, which can be solved in polynomial time.
22

---

Polynomial-Time Approximability of Constrained Reinforcement Learning
Stochastic Costs. For finitely-supported cost distributions, all results remain the except for almost-surr/anytiine constraints, which must be written in the form:
C (Th)
max
o¹ max[Ph(s s, > (TT
(20)
oESupp(Cuts.a)
Also, note that histories must be cost-dependent.
Now, we have that future budgets depend on both the next state and the realized cost, so our (ADP) must now be dependent on both states and immediate costs for subproblems. The construction is similar to the approach in (McMahan, 2024).
23


Reviews:
[{"review_id": "I4t1rVbLFr", "reviewer": "Reviewer_htBq", "summary": "In this paper, they study polynomial algorithm for a generalized constrained MDP (CMDP).\nIn particular, they formulate a class of CMDPs whose constraints have generalized Bellman-recursive structures, and\nconstruct polynomial algorithms for it via state/action augmentation and budget/state discretization.\nMoreover, they extend their method by replacing the augmented component with function approximation.\nFinally, they show an application of the proposed method as a fast, approximate solver for knapsack problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! We intend to revise the paper with your notational suggestions in mind. Please see our general rebuttal below, which addresses your concerns about our title, the significance of our results, and the role of our knapsack example:\n\n--- *General Rebuttal* ---\n\n\"We address the common concerns of the reviewers, particularly those who may not be experts in the Constrained Reinforcement Learning (CRL) domain. These concerns include using the term \"Reinforcement Learning\" (RL) in our title and the significance of our contributions to the CRL literature. We also clarify the intention behind the final section's knapsack example, given the theoretical nature of our work.\n\n1. **[Title]** First, it is a common convention in the RL literature to use \"RL\" to reference both planning (full MDP knowledge) and learning settings, as seen in many of the past CRL works cited in our paper, such as [1,2,3]. Moreover, planning algorithms can directly translate into learning algorithms through model-based learning approaches. However, we understand this might be misleading to some reviewers, given our paper's focus on computational complexity. We are open to changing the title if the reviewers believe this would be beneficial.\n\n2. **[Contributions]** Second, we would like to try to convey the significance of our contributions even to non-experts in CRL through their foundational nature. Specifically, we note that the entire objective of CRL is to compute a value-maximizing policy that satisfies constraints. From a computational perspective, the fundamental question is whether such an (approximately) optimal policy is computable in polynomial time. We not only make progress on this question for nearly all constraints studied by the CRL literature, but also derive algorithms that achieve the provably best approximation guarantees possible under $P \\neq NP$. Thus, our work is the first to establish polynomial-time approximability for each setting mentioned in the abstract and introduction, including the natural heterogeneous and chance constraint [3] settings. Before our work, all of these settings lacked sub-exponential time algorithms, or any algorithm, since their first introductions over 25 years ago. In fact, a significant paper appearing in Neurips 2024 [2] achieved similar results to ours, but only for the special case of problems with exactly one constraint and excluding chance constraints.\n\n3. **[Knapsack Example]** Lastly, we emphasize that our paper is theoretical work with the singular focus of addressing: \"Can general CMDPs be approximated in polynomial time?\" Since this is a question about the worst-case computational complexity of an optimization problem, this question can only be answered using a mathematical proof. In particular, numerical experiments cannot establish computational complexity bounds and thus do not serve our primary objective. Consequently, our final section on function approximation was only intended to highlight the flexibility of our approach rather than stand as an experimental section. We see now this may have been confusing, and are happy to remove that section if it distracts from the paper's main message on the computational complexity of CRL.\n\n**References**:\n\n[1] \"Anytime-Constrained Reinforcement Learning\", Jeremy McMahan and Xiaojin Zhou. AISTATS 2024.\n\n[2] \"Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time\", Jeremy McMahan. NeurIPS 2024.\n\n[3] \"Risk-Constrained Reinforcement Learning with Percentile Risk Criteria\", Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. JMLR 2017\n\n--- *End of general rebuttal* ---\n\nIn addition to those points, we would like to address the reviewer's statement about the straightforwardness of the results. We note that many works have attempted to develop polynomial-time algorithms for our settings since they were first studied over 25 years ago, yet we are the first to achieve this feat. We believe this fact alone implies our approach is not insignificant. Moreover, if our approach were straightforward, we would argue this is an additional benefit. Specifically, this would mean that our method is not only provably exponentially faster than past approaches but also achieves optimal approximation guarantees without relying on complicated machinery such as large MILPs and exhaustive searches. \n\nThank you once again for your valuable feedback! We hope our responses address your concerns and clarify the contributions of our work.", "claims_and_evidence": "Reinforcement learning is a subfield of machine learning, which I believe involves some form of inference from finite sample. However, the presented results assume the complete knowledge of CMDP. Therefore I think the title is more accurate with something like \"Polynomial-Time Solvability of Constrained Markov Decision Process\".", "methods_and_evaluation_criteria": "The presentation of Knapsack Example could be more detailed in a quantitative aspect.", "theoretical_claims": "The idea behind the proof is easy to follow.", "experimental_designs_or_analyses": "The presentation of Knapsack Example could be more detailed in a quantitative aspect.", "relation_to_broader_scientific_literature": "I am not an expert in constrained MDP literature, so not sure how significant its contributions are.\nOn one side, the proposed framework is of great generality, which is nice, yet on the other side, the theoretical analysis seems rather straightforward and the authors indicate no particular use of the widened applicability beyond the good old knapsack problem.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "* L074 left: \"SR\" appears here for the first time without explanation.  \n* L097 left (and more): decide which one to use: cMDP or CMDP?  \n* L099 right: Give the total description size of caMDP explicitly.  \n* L133 left: $t$ starting from 1, but the initial time step is 0.  \n* L155 left: \"finite extension of $f$\" is ambiguous. I personally prefer explanations with mathematical expression, like $f_{t=1}^T x_t:=f(f(\\cdots f(f(x_1, x_2), x_3), \\cdots, x_{T-1}), x_T)$.\n* L145 right: what is the truncated-horizon process?\n* L196 left: Our *method(?)* revolves ...\n* L262 left: Define $\\bar{C}_h^\\pi(s,b)$\n* L316 left: $\\kappa_\\ell$\n* L321 left: $g(P_h(s'|s,a),b_{s'}))$", "questions_for_authors": "None.", "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": "n5CSH8xevm", "reviewer": "Reviewer_p12Q", "summary": "The submission provides a novel generic bicriteria approximation algorithm that covers a broad range of Constrained Markov Decision Processes (CMDPs).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! Please see our general rebuttal above in Reviewer htBq's rebuttal section. \n\n**[Formalization]** In addition, we address the claim that our problem is not properly formalized. As our work is within the domain of CRL, we assume some basic familiarity with CRL notations and conventions. Specifically, our definition of a caMDP is almost identical to the usual definition of a \"constrained MDP\" used in other CRL works, including the AISTATS paper [1] that the reviewer referenced. That being said, we are happy to break the norms of the literature to enhance the clarity of the paper. To this end, we will add the following clarifications: \n1) H is a positive integer, \n2) s represents a state, \n3) a represents an action, \n4)  $\\Delta(X)$ represents the probability simplex over elements of a set X (so $\\Delta(S)$ is the set of all possible distributions over states), and \n5) Lowercase c denotes the cost function when costs are deterministic, similar to lowercase r. \n\n**[Non-Stationarity]** To clarify to the reviewer, we used $S_h$ and $A_h$ in the definition of caMDPs because Definition 3.1 requires a non-stationary state and action space that may change over time, similar to Definition 2 in [1]. To clarify this, we will revert to a classic stationary state space in the caMDP definition, and instead define the non-stationary state and action space concept more explicitly in Definition 3.1, where that concept is first needed. Consequently, the caMDP definition would then take the more standard form $(S, A, H, P, R, C, s_0)$. \n\n**[CMDP Definition]** We also would like to point out that we have formally defined a CMDP in the paragraph \"Constrained Processes\" to be the tuple $(M, C, B)$ consisting of a caMDP along with a cost criterion $\\mathcal{C}$ and a budget B. We introduce this definition because known works on constrained MDPs only consider a single constraint type, so the cost criterion is usually assumed from context. However, since we consider many different types of constraints here, we felt it would be useful to explicitly specify the cost criterion in the environment's definition. If it would be clearer, we are also happy to skip the definition of a caMDP and define a CMPD as the 9-tuple: $(S, A, H, P, R, C, s_0, \\mathcal{C}, B)$. Note, the lowercase cMDP is just a typo that should be CMDP. As mentioned above, CMDP and caMDP are different.\n\n**[Comparison to [1]]** Concerning a comparison to [1], we bring the reviewer's attention to the section 3 statement: \"When moving to other constraints, the cumulative cost may no longer suffice to determine constraint satisfaction. For example, the expected cost depends on the cumulative cost\nof all realizable branches, not just the current branch.\" Thus, unlike the simple augmentation of cumulative cost as done in [1], here we must use a more abstract notion of artificial future budgets with our state augmentation. This results in an exponentially sized augmented action space that cannot be solved efficiently using standard algorithms, unlike the simpler MDP constructed in [1] without action augmentation. This forces us to design an entirely new approximate dynamic programming (DP) approach, which makes up the entirety of section 4. Lastly, in the paragraph  \"time-space errors\", we mentioned that we use a customized rounding scheme due to errors accumulating over space and time in our approximate DP approach, unlike that of [1]'s projection scheme. These are all key fundamental differences needed to tackle combinations of constraints beyond anytime constraints. \n\n**[Running Example]** We will also add a self-driving car example commonly used in CRL. Specifically, we wish to construct a route that minimizes time for the car to reach its destination while obeying 1) an anytime constraint on its gas consumption so that it does not run out of fuel, 2) an expectation constraint on its CO2 consumption to minimize damage to the Earth, and 3) a chance constraint ensuring the car has a low probability of sustaining damage on the route.\n\nPlease let us know if there are any other items we can clarify, and thank you again for your feedback!", "claims_and_evidence": "Yes, with the exception of the malformed definitions and anecdotal experimental setup (see \"Other Strengths and Weaknesses\").", "methods_and_evaluation_criteria": "The submission is of foundational nature and the methods (proofs) are appropriate.", "theoretical_claims": "Only some, due to issues with malformed definitions.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The results build on and extend previous works on solving CMDPs; the most closely related paper is the AISTATS 2024 paper which provides a bicriteria approximation algorithm for a subset of the instances considered here.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "On the positive side, the overall contribution of the submission is solid: while it lacks experimental evaluations (contrasting many of the preceding papers), it does provide a non-trivial theoretical contribution which pushes the boundaries of approximability for a range of CMDPs. I am not an expert on CMDPs, but the description of the related work to me convincingly justified the relevance of these problems.\n\nThe inclusion of the to-the-point \"Our Techniques\" paragraph is a nice touch that is often missing from theoretical ICML submissions. Nevertheless, given how close the result is to the recently developed polynomial-time (0, ϵ)-additive bicriteria approximation algorithms of McMahan and Zhu (AISTATS 2024), I would have expected a closer treatment of how the techniques differ from those used previously. There is a brief note on this at the start of Section 3, but does that paragraph imply that there is no intersection between the techniques used here and those employed in the preceding AISTATS 2024 paper?\n\nRegarding experimental evaluations, the second-to-last paragraph of the submission mentions a seemingly anecdotal experimental setup without providing any proper details. I believe that in the current form, these claims should not appear in the main body of the submission as they are entirely non-reproducible; they can either be expanded to a proper experimental setup (with details), or moved entirely to the appendix. As the submission's contribution is foundational, I do not consider the lack of experiments to be a significant issue.\n\n-On the negative side, the problem is not properly formalized, or more precisely, the provided definition in Section 2 is malformed. It defines a caMDP as a tuple of the form (H,S,...), which is fine - however, when describing the elements of the tuple, it never speaks about S but rather about S_h where h is never defined or explained (and similarly for A_h etc.). Moreover, is the \"time horizon\" H an integer? What is the triangle(S) and triangle(R) notation? And are s,a elements of S and A, respectively? These things have to be made crystal clear, as without the formal definitions the vast majority of the ICML audience would not be able to understand the specific formal model used (and hence the contributions become meaningless). Due to these issues, I could not verify the formal correctness of the proofs.\n\nFormal issues aside, given the complexity of the problem formulation it would be natural to include a simple example of a concrete problem instance (possibly highlighting various types of constraints). This could be, e.g., a running example that guides readers through Section 2, or just some summarizing examples at the end of that section.\n\n## Update after rebuttal\nThank you for the responses; I maintain my assessment and score.", "other_comments_or_suggestions": "-Typo on page 2: \"bicritiera\" should be \"bicriteria\", and there should not be an \"a\" on row \"64\".\n-The running title still has the placeholder \"Submission and Formatting Instructions for ICML 2025\".\n-Row 196: \"Our revolves around\" - I suggest rephrasing, as it is not clear what \"Our\" refers to.\n-Row 400: \"The user also have\" -> \"... has\"", "questions_for_authors": "The authors are welcome to respond to any of the points raised in the \"Other Strengths And Weaknesses\" section, and in particular clarify the problem definition while providing some concrete example of a problem instance. I am open to adjusting my score, but cannot currently recommend acceptance given the current state of the presentation.\n\nOn a related note, is there a reason for using CMDP in some places, cMDP in others and caMDP elsewhere?  Are these the same things merely using inconsistent abbreviations? As far as I could see, only caMDP is formally defined in the paper.", "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": "d4Ip03b3Ch", "reviewer": "Reviewer_c1yJ", "summary": "The paper develops approximation algorithms for constrained MDP problems. The problem formulation in the paper can incorporate a broad class of recursively computable constraints, including almost-sure, chance, expectation, and their anytime variants. For this general problem formulation, the paper develops a framework to compute a near-optimal policy that achieves the same objective value as the optimal policy, while ensuring that the constraints are satisfied with an additive error $\\epsilon$. \n\nThe general approach developed in the paper is based on an augmentation scheme. To be specific, the paper chooses a future artificial budget to replace the original constraints. The artificial budget imposes some restrictions on the actions that can be taken at each round, and then enables us to reduce the original constrained MDP problems into MDP problems. Then, with this reduced MDP problem, the paper can develop the associated Bellman updates and employs a dynamic programming to solve the problem. However, the dynamic programming can be hard to solve, the paper then develops a dynamic rounding approach to ease the computation. Finally, with an additional approximation method that approximates the possible set of artificial budget with a finite set, the paper develops an $\\epsilon$-approximate policy with a computation time polynomial in $1/\\epsilon$. The paper further extends their approaches to continuous settings, as well as function approximation settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! Please see our general rebuttal above in Reviewer htBq's rebuttal section, which addresses Weaknesses 2-4 and other points the reviewer brought up. In addition to those points, we address several points below.\n\n**[Weakness 1]** In our paragraph \"Past Work\" in the introduction, we explicitly mentioned all known works that achieve polynomial-time approximation algorithms for special cases of our problem. Are there any specific works the reviewer is thinking of that we have missed here? All other works we are aware of are exponential time or apply to completely different settings, and thus are immediately inferior or incomparable to our method within the context of establishing polynomial-time approximability of our problem. However, we are happy to include references to exponential time algorithms if the reviewer feels this will make connections to the literature clearer.\n\n**[Q1]** Note, in the appendix, we show how to modify our method to achieve stochastic policies. However, we emphasize that the computation of stochastic, expectation-constrained policies is already known and so not a goal of our paper. Our goal is to compute deterministic, expectation-constrained policies and policies under other constraints, which are problems that have yet to be solved in the literature.\n\n**[Q2]** Note, this approach only works for *stochastic, expectation-constrained policies*. The LP formulation no longer holds when policies are additionally constrained to be deterministic or are forced to obey more complex anytime or chance constraints. This is immediate since our problem is NP-hard as mentioned in the \"Hardness\" paragraph, so any such polynomial-sized LP formulation would immediately imply that P = NP.\n\n**[Q3]** As in our Weakness 1 discussion, we again emphasize that the only goal of our paper is to devise *polynomial-time* algorithms for problems that currently have none. As such, the only distinction we focus on is polynomial runtimes vs exponential runtimes. Since all the open problems we discuss either have only exponential time algorithms or have no algorithm whatsoever, our algorithms beat all such competitors by definition in the context of computational complexity. Again, we are happy to include references to exponential time algorithms if the reviewer feels this will make connections to the literature clearer.\n\n\n**[Q4 + Q5]** Please see our general rebuttal in addition to the discussion above for Q3.\n\nThank you again for your feedback, and let us know if there is anything else we can clarify!", "claims_and_evidence": "The claim is clear and looks convincing.", "methods_and_evaluation_criteria": "The method makes sense, however, there is no numerical validation of their algorithms, as I further explain in the strength and weakness part.", "theoretical_claims": "I have checked the proofs and the theoretical claims. They look correct to me.", "experimental_designs_or_analyses": "There is no numerical experiment in the paper.", "relation_to_broader_scientific_literature": "The main contribution of the paper is to develop a general method to approximate the CMDP problems, where the constraints can take many formulations, including almost-sure, chance, expectation, and anytime variants. The paper computes a policy that enjoys the same objective value as the optimal policy, and violates the constraint up to an additive $\\epsilon$ bound, with a computation time polynomial in $1/\\epsilon$.", "essential_references_not_discussed": "Most papers are discussed.", "other_strengths_and_weaknesses": "Strength:\n\nThe paper develops a general approach to handle the CMDP problems, where the constraints can incorporate many formulation, for example almost surely, chance, expectation, and the anytime variants. \n\nWeakness:\n\n1. The comparison with the previous literature can be made better. The CMDP problems are classical problems, and many algorithms have been developed to solve the CMDP problems. However, it is not clear from the paper whether the computation time bound improves over the previous results. \n\n2. The writing of the paper could be further improved, especially the descriptions of the methods in Section 6.\n\n3. There is no numerical experiment over the algorithms developed in the paper.\n\n4. The constrained MDP problems considered in the paper actually assume that all the problem parameters are given and the algorithms in the paper rely heavily on the prior knowledge of the cost, as well as transition probabilities. Therefore, I do not see any learning element in the paper, though the title of the paper is about reinforcement learning.", "other_comments_or_suggestions": "1. In Section 6, it is said that an OpenAI gym environment is developed to model the approach with function approximation on this CMDP. However, I cannot find further details in the paper.\n\n2. There is no impact statement in the paper.", "questions_for_authors": "1. It seems to me that your algorithm will always produce a deterministic policy. However, it is well known that the optimal policy for a CMDP problem can be a randomized policy, especially when the constraint takes an expectation formulation. Is it possible that your algorithm will output a randomized policy?\n\n2. Since the paper assumes that all the problem parameters are given, could we just formulate the CMDP problem as an optimization problem, and then use the existing optimization algorithm to solve it? For example, Altman (1999) just formulates the CMDP problems as linear programming to solve it. \n\n3. How does the computation time bound developed in the paper compare to previous bounds established in the literature?\n\n4. Since the title of the paper is regarding reinforcement learning, how to implement the algorithm when the problem parameters are not given, for example, the cost and the transition probabilities are unknown.\n\n5. Could you comment on the real performance of your algorithm?", "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": "ub6btGvJUG", "reviewer": "Reviewer_TjVX", "summary": "The authors study the computational complexity of constrained MDPs.\nThey show some novel results regarding finding approximately optimal policies.\n\nIn particular, they studied the question of whether polynomial time approximation algorithms exist for many of the classic formulations studied in the CRL literature.\nThey found that for the vast majority of constraints, including all the standard constraints, polynomial-time approximability is possible.\nTheir work resolves the polynomial-time approximability of many settings, some of which have been lacking in any polynomial-time algorithm.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! We will update the paper to clarify the points the reviewer made. To address your questions,\n\n**[Page 4]** This is meant to be s' as is. Note, this equation corresponds to the usual policy evaluation equations for a deterministic policy. Here, we are assuming a is the specific action chosen by the policy.\n\n**[Page 7]** Note, each quantity involved is part of the MDP, so smaller than its description size. Recall that m, the number of constraints, must be constant or else the problem cannot be solved efficiently. Given m is constant, quantities such as S^m are then polynomial-sized. For example, given only one constraint, the bound is $O(H^7 S^6 A poly(|M|)/\\epsilon^3)$, which can be seen to be polynomial in $|M|$ and $1/\\epsilon$.\n\nThanks again and let us know if there is anything else that needs clarifying!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I only checked the main body :)", "experimental_designs_or_analyses": "Yes, at a high level.", "relation_to_broader_scientific_literature": "Contributions are relevant and important for the broader RL community, as they prove long-sought guarantees for various types of RL tasks, such as polynomial-time approximability for policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and so on.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "This work is to the best of my knowledge, original.\n\nThe authors are the first to prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and policies under constraints for continuous-state processes.\nThis fills an important gap in the literature, and for that matter I am vouching for this paper to be accepted.", "other_comments_or_suggestions": "Please add an Impact Statement!", "questions_for_authors": "Page 1:\nPlease frame your main question in a more general way.\n\nPage 2:\nCould you please add some discussion on CAMDPs?\n\nPage 3:\nI do not understand Definition 2.4.\n\nPage 3:\nCan you please add some comments regarding Proposition 2.3 (proof sketch)?\nI understand that the proof is in the appendix, but some justification must be added in the main body as well.\n\nPage 4:\nIn Equation (2), did you perhaps mean to sum over $a$?\n\nPlease further explain Equation (4).\n\nPage 5:\nPlease elaborate on the functionalities of Algorithm 1 and Algorithm 2, in their respective captions.\n\nPage 6:\nI do not understand Lines 302 to 309 (second column).\n\nPage 7:\nTheorem 5.4:\nWhy is this running time polynomial?\n\nPage 8:\nPlease further elaborate on future work.", "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:

Meta-review: All the Reviewers agreed that the paper meets the bar for acceptance at ICML. The initial concerns of the Reviewers were solved by the Authors during the rebuttals. Thus, I will propose acceptance.
Decision: Accept (poster)