Pith. sign in

REVIEW 4 major objections 5 minor 49 references

Polynomial-Time Approximability of Constrained Reinforcement Learning

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A single 'shortly recursive' class makes every standard constrained-RL constraint polynomially approximable.

desk verdict A significant and likely-correct unification of constrained MDP approximation, but the main proof as written has a gap: the algorithm uses exact next-layer values it never computes. read the letter →

arxiv 2502.07764 v1 pith:XHQZHYRL submitted 2025-02-11 cs.DS cs.AIcs.LG

Jeremy McMahan This is my paper · ORCID
classification cs.DScs.AIcs.LG MSC 68W2590C4068Q25
keywords constrainedMarkovdecisionprocessesbicriteriaapproximationdynamicroundingshortlyrecursivecriteriachanceconstraintsalmost-sureanytimepolynomial-time
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the standard constraint types used in constrained reinforcement learning—expectation, chance, almost-sure, and their anytime variants—all fit a single 'shortly recursive' (SR) class, and that every CMDP whose cost criterion is SR admits a polynomial-time $(0,\epsilon)$-additive bicriteria approximation: a policy with optimal value that overshoots each budget by at most $\epsilon$. If the main theorem is correct, planners can approximate constrained policies for any constant number of constraints without losing value, which would settle decade-old open questions on chance-constrained policies, deterministic policies under multiple expectation constraints, non-homogeneous constraint mixtures, and continuous-state processes. The significance is that one budget-rounding mechanism, rather than a zoo of constraint-specific algorithms, covers the field's most popular constraint families.

What carries the argument

The load-bearing object is the shortly recursive (SR) cost criterion: a cost function evaluated by $C_h = c_h(s,a) + f_{s'} g(P_h(s'|s,a)) C_{h+1}(s')$, where $f$ is an associative, non-decreasing, identity-preserving operator that is 1-Lipschitz in each argument and whose composition with the transition weight $g$ is 1-Lipschitz in the successor-cost vector. This property drives three constructions: the budget-augmented MDP that reduces global constraints to per-step constraints; the sequential dynamic program (Definition 4) that solves the exponential-action Bellman update by choosing successor budgets one state at a time; and dynamic rounding that replaces each partial cost with its upper multiple of $\ell$, re-rounding at every step because $f$ need not be linear. The error analysis separates space error (rounding the partial cost for each future state) from time error (rounding the budget at each horizon step), and shows both grow by at most $\ell$ per state or step, so the total budget violation is bounded by $\ell(1+(S+1)H)$.

What would settle it

Enumerate all small SR-criterion CMDPs (e.g., $S=3$ states, $H=4$ steps, one constraint, costs in $\{0,1,2\}$, transition probabilities on a coarse grid), compute the true optimum $V^*$ by brute force, and run Algorithm 4 with $\ell=\epsilon/(1+(S+1)H)$; if any instance returns a policy with cost above $B+\epsilon$, a value below $V^*$, or a spurious 'infeasible' report, Theorem 4 is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4: for any SR-criterion CMDP with polynomially bounded costs and a constant number of constraints, Algorithm 4 with $\ell = \epsilon/(1+(S+1)H)$ computes a $(0,\epsilon)$-additive bicriteria approximation in polynomial time. An SR criterion is one whose cost decomposes recursively as $C_h = c_h(s,a) + f_{s'} g(P_h(s'|s,a)) C_{h+1}(s')$, where the aggregate $f$ is associative, non-decreasing, identity-preserving, and 1-Lipschitz in each input, and $f$ combined with $g$ is 1-Lipschitz in the vector of successor costs. The proof works by augmenting states with artificial budgets, converting history-wide constraints into per-step action constraints; then solving the resulting knapsack-hard Bellman update via dynamic programming over rounded partial costs, with an upper threshold $\kappa(b)=b+\ell(S+1)$ that keeps feasible choices feasible. The SR property makes the rounding error accumulate at most linearly in horizon and state count, giving the $\epsilon$ budget violation. The framework also yields an $(\epsilon,\epsilon)$-bicriteria for Lipschitz-continuous state spaces via discretization, and, because expectation, chance, almost-sure, and anytime constraints are all SR, it provides the first polynomial-time approximability for chance constraints, deterministic policies under multiple expectation constraints, and non-homogeneous constraint mixtures.

Load-bearing premise

The cost criterion must be a short map: the function that merges successor costs must be non-decreasing, associative, and 1-Lipschitz, and so must its composition with the transition weighting; without that Lipschitz property the rounding-error bound that produces the $\epsilon$ budget violation no longer holds.

Editorial extensions

If this is right

  • Chance-constrained policies (total cost exceeding the budget with probability at most $\delta$) become polynomially approximable with a $(0,\epsilon)$ guarantee for the first time.
  • Deterministic policies under multiple expectation constraints, and non-homogeneous mixtures of expectation, chance, and almost-sure constraints, are polynomially approximable whenever the number of constraints is constant.
  • For Lipschitz-continuous state spaces, the same machinery gives an $(\epsilon,\epsilon)$-bicriteria approximation, extending polynomial-time approximability to continuous-state constrained MDPs.
  • With non-negative costs and polynomially bounded budgets, the additive guarantee becomes a relative $(1+\epsilon)$-bicriteria (Corollary 1).
  • Matching lower bounds (Proposition 2 and prior hardness results) imply that the additive $\epsilon$ relaxation and the constant-number-of-constraints condition cannot be removed unless $P = NP$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the paper leaves implicit is to test where the SR boundary sits: risk measures such as conditional value-at-risk are recursively evaluable but not 1-Lipschitz, so applying the rounding scheme to them on small instances should show exactly where the polynomial-time guarantee breaks.
  • The function-approximation sketch (parameterized budget functions $b_\theta$ in Section 6) suggests that the augmentation can be plugged into deep-RL pipelines for large state spaces; a testable next step is to measure whether the closed-loop budget update keeps violations near $\epsilon$ on a continuous control task.
  • Because the $(0,\epsilon)$ guarantee preserves optimal value while allowing a small budget overshoot, the framework is a natural fit for safety-critical settings where slightly relaxing a resource or risk budget is cheaper than losing performance; quantifying the empirical overshoot distribution across random CMDP instances would substantiate that trade-off.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a general framework for approximately solving constrained Markov decision processes (CMDPs) whose cost criteria are 'shortly recursive' (SR). The main idea is to convert a history-dependent constraint into a per-step constraint by augmenting the state with an artificial budget and the action space with choices of future budgets, obtaining a reduced MDP. The paper then develops dynamic-programming updates with rounding (Definition 6, Lemma 4, Algorithm 3), defines an approximate MDP on a rounded budget set (Definition 7), and proves a polynomial-time (0, epsilon)-additive bicriteria approximation theorem (Theorem 4). It also provides an extension to continuous-state CMDPs under Lipschitz assumptions (Theorem 5) and claims first polynomial-time approximability results for chance constraints, deterministic policies with multiple expectation constraints, and non-homogeneous constraints.

Significance. If the main theorems were fully established, the paper would be a substantial contribution: it unifies a broad class of constraints under a single algorithmic framework, gives a parameter-free choice of rounding scale, and would resolve several long-standing open questions on the polynomial-time approximability of constrained MDPs. The rounding error analysis in Lemmas 9 and 10 is detailed, and the stated runtime in Theorem 4 is explicit. However, the current manuscript contains several gaps that directly affect the proof of Theorem 4, most notably that Algorithm 3 as written cannot execute the recurrence used in its own analysis. The core approach is promising and the claims are defensible in spirit, but the technical presentation needs substantial revision before the main theorems are supported.

major comments (4)
  1. [Definition 6, Algorithm 3, Lemma 4, Theorem 4] The approximate Bellman update (ADP) in Definition 6 uses the exact next-layer value function \bar V^*_{h+1}(t,b_t) of the reduced MDP. Algorithm 3, however, processes layers from H down to 1 and at layer h has only the previously computed approximate function \hat V^*_{h+1}; it never has access to \bar V^*_{h+1}. The proof of Lemma 4 establishes the rounding guarantee only for the recurrence with the exact \bar V^*, and no error analysis is provided for the substitution of \hat V^* in place of \bar V^*. Consequently, the value lower bound in Lemma 5 and the final claim \hat V^\pi_1(s_0,\lceil B\rceil_\ell) \ge V^* in Theorem 4 are not established for the policy actually returned by Algorithm 3/4. This is a load-bearing gap because the (0,\epsilon) bicriteria guarantee allows no value loss.
  2. [Algorithm 3 line 1 vs Definition 7] Algorithm 3 initializes \hat V^*_{H+1}(s,b) \leftarrow \chi_{\{b\ge 0\}}, while Definition 7 and the base case used in Lemma 1 define \hat V^*_{H+1}(s,\hat b) = -\chi_{\{\hat b\ge 0\}}. With the algorithm's sign, infeasible terminal budgets contribute 0 instead of -\infty, which can make the infeasibility test in Algorithm 4 report feasibility incorrectly and can invalidate the value lower bound. This sign error must be corrected and its consequences traced through Lemmas 5 and 6.
  3. [Lemma 2 and Lemma 6] Lemma 2 refers to \bar C^\pi_h(s,b), and Lemma 6 refers to \hat C^\pi_h(s,\hat b), but no cost criterion is defined for the reduced MDP \bar M or for the approximate MDP \hat M. Definition 3 lists only states, actions, transitions, rewards, and the initial state, with no cost function. The proofs of these lemmas use an SR recursion for these undefined quantities and require that the policy's action lies in \bar A_h(s,b) or \hat A_h(s,\hat b). Without explicit definitions, the cost-violation bounds in Lemma 6 and hence the bicriteria guarantee in Theorem 4 are not supported.
  4. [Definition 6, Definition 7, Lemma 5] Definition 7 defines the approximate MDP \hat M over the rounded budget set \hat B, and its action space uses vectors in \hat B^S. However, the recurrence (ADP) in Definition 6 still ranges over b_t \in B, the original unrounded budget set, and uses \bar V^*_{h+1} on that set. When Algorithm 3 is invoked on \hat M in Algorithm 4, it is therefore not solving the approximate MDP whose state and action sets were defined. The paper neither states a modified recurrence over \hat B nor analyzes the mixed use of B and \hat B; this also affects the claimed runtime bound involving |\hat B|.
minor comments (5)
  1. [Throughout] There are numerous typos and grammatical slips, including 'quanitites' in Assumption 1, 'descretized' in Section 5.1, 'yeilds' before Theorem 5, and 'bicritiera' in the introduction; these should be corrected.
  2. [Theorem 3] The first sentence of Theorem 3, 'When \lceil\rceil_\ell and \kappa are replaced with the identity function, Algorithm 3 correctly solves any \bar M produced from Definition 3', is confusing because Algorithm 3's stated code always uses (AU); the exactness claim should be stated as a separate consistency lemma rather than as a conditional in the main theorem.
  3. [Proposition 1] The chance-constraint modeling says that 'the expected cost for the new M exactly corresponds to the probability cost', but the transition from the recurrence C^\pi_h(\tau_h,\bar c) to the SR form with indicator immediate costs is only sketched; a formal derivation would improve readability and verifiability.
  4. [Remark 6 and Proposition 2] The claim that the approximation guarantees are 'best possible' and that the dependence on m is unavoidable rests on Proposition 2, whose proof is a two-sentence sketch with no formal reduction details; either provide the full reduction or clearly mark this as a proof sketch.
  5. [Appendix, Definition 9] The budget space B is defined twice: once in Definition 3 as the union over policies and histories, and once in Appendix Definition 9 via a backward recursion; the equivalence is asserted in Lemma 8 but could be stated more prominently to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the (0,epsilon)-bicriteria guarantee is derived from the SR assumptions by direct lemmas; the author self-citations are contextual and non-load-bearing.

full rationale

Theorem 4 is the central claim, and its proof is self-contained in the paper: Lemmas 4, 5, 6, 9, and 10 establish the rounding error, optimal-value, and cost-violation bounds by direct induction using the short-map and monotonicity properties required in Definition 1. No parameter is fitted to a subset of the target data and then renamed as a prediction; the only tuning parameter is ell, and Theorem 4 explicitly sets ell = epsilon/(1+(S+1)H) and proves the resulting value and cost guarantees from the earlier lemmas. The class of SR criteria is defined by the recursive policy-evaluation structure (SR), so the theorem is conditional on that definition; Proposition 1 then separately verifies that expectation, chance, and almost-sure constraints can be modeled in this form using elementary identities. That is a modeling reduction, not a circular one. The paper cites prior work by the same author ([26], [27], [28]), but these citations are used for hardness context, for an augmented-state size remark, and for lower-bound commentary; the positive approximation theorem does not import a matching result as a black box. A reviewer-raised concern that Algorithm 3 computes (AU) using the approximate hat V*_{h+1} while Definition 6's (ADP) explicitly references the exact bar V*_{h+1} is a possible correctness/consistency gap in the algorithm's presentation, but it is not circularity: the intended reduction is not one where the conclusion is equivalent to an input by construction. Overall, the derivation chain is independent of its own conclusions, and I find no circular step that would warrant a score above zero.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central claim rests on the SR definitional restriction, polynomial cost boundedness, and Lipschitz continuity assumptions for the continuous-state case. The paper introduces no physical entities, only algorithmic constructs such as the artificial budget. No free parameters are fitted to data.

assumptions (4)
  • domain assumption SR criterion constrains f to be a short map when either input is fixed and when combined with g (Definition 1).
    This is a postulated restriction that defines the class of constraints covered. The paper proves it holds for expectation, chance, and almost-sure constraints, but the general theory is limited to it.
  • domain assumption Costs are polynomially bounded, meaning ||cmax - cmin|| is polynomial in the input size.
    The runtime in Theorem 4 depends on ||cmax - cmin||^3m, and lower bounds cited from [28] show this assumption is necessary for polynomial-time approximations.
  • domain assumption Continuous-state CMDPs satisfy Assumption 1: Lipschitz rewards, costs, and transitions, plus a state range |smax - smin| = O(|M|).
    Needed for the discretization error bounds in Lemma 7 and for the discretized state count \tilde S to remain polynomial.
  • standard math Standard finite-horizon MDP dynamic programming and rounding arguments.
    Used throughout without proof; they are standard in the algorithms literature.
invented entities (1)
  • Artificial budget b in the reduced MDP
    purpose: Encodes the remaining allowed cost allocation at each state, converting history-dependent constraints into per-time-step constraints.
    A mathematical construct for the algorithm, not a physical entity; it has no external falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polynomial-Time Approximability of Constrained Reinforcement Learning." pith.science (2026). https://pith.science/paper/XHQZHYRL

@misc{pith2026250207764,
  author       = {Pith},
  title        = {Pith review of: Polynomial-Time Approximability of Constrained Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XHQZHYRL}},
  note         = {Machine review of arXiv:2502.07764}
}
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.

Figures

Figures reproduced from arXiv: 2502.07764 by the authors.

Figure 1
Figure 1. The Constraint Landscape 2. Chance Constraints – (f , g) defined as above and B′ def = δ. Here, we assume M’s states are augmented with cumulative costs and that ch((s, c¯), a) def = [ch(s, a) + c > B ¯ ] for the anytime variant and ch((s, c¯), a) def = [ch(s, a) + ¯c > B][h = H] otherwise. 3. Almost-sure Constraints – f (x, y) def = max(x, y), g(x) def = [x > 0], and B′ def = B. Anytime variant – f (x, y) def = max… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 37 canonical work pages

  1. [1]

    Alshiekh, R

    M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, and U. Topcu. Safe reinforcement learning via shielding.Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10.1609/aaai.v32i1.11797. URLhttps://ojs. aaai.org/index.php/AAAI/article/view/11797

    doi:10.1609/aaai.v32i1.11797 2018

  2. [2]

    E. Altman. Constrained Markov Decision Processes. Chapman and Hall/CRC, 1999. doi: 10.1201/9781315140223

    doi:10.1201/9781315140223 1999

  3. [3]

    Q. Bai, A. Singh Bedi, and V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal- dual algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6): 6737–6744, 6 2023. doi: 10.1609/aaai.v37i6.25826. URL https://ojs.aaai.org/ index.php/AAAI/article/view/25826. 13

    work page doi:10.1609/aaai.v37i6.25826 2023

  4. [4]

    Berkenkamp, M

    F. Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause. Safe model-based reinforcement learning with stability guarantees. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors,Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.,

    work page

  5. [5]

    Bhatia, P

    A. Bhatia, P. Varakantham, and A. Kumar. Resource constrained deep reinforcement learning. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1):610–620, 5 2021. doi: 10.1609/icaps.v29i1.3528. URL https: //ojs.aaai.org/index.php/ICAPS/article/view/3528

    work page doi:10.1609/icaps.v29i1.3528 2021

  6. [6]

    V. Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & Control Letters, 54(3):207–213, 2005. ISSN 0167-6911. doi: https: //doi.org/10.1016/j.sysconle.2004.08.007. URL https://www.sciencedirect.com/ science/article/pii/S0167691104001276

    work page doi:10.1016/j.sysconle.2004.08.007 2005

  7. [7]

    D. M. Bossens and N. Bishop. Explicit explore, exploit, or escape (e4): Near-optimal safety-constrained reinforcement learning in polynomial time.Mach. Learn., 112 (3):817–858, 6 2022. ISSN 0885-6125. doi: 10.1007/s10994-022-06201-z. URL https://doi.org/10.1007/s10994-022-06201-z

    work page doi:10.1007/s10994-022-06201-z 2022

  8. [8]

    Brantley, M

    K. Brantley, M. Dudík, T. Lykouris, S. Miryoosefi, M. Simchowitz, A. Slivkins, and W. Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. In NeurIPS, 2020. URLhttps://proceedings.neurips.cc/paper/2020/ hash/bc6d753857fe3dd4275dff707dedf329-Abstract.html

    work page 2020

Show all 49 references
  1. [9]

    Castellano, H

    A. Castellano, H. Min, E. Mallada, and J. A. Bazerque. Reinforcement learning with almost sure constraints. In R. Firoozi, N. Mehr, E. Yel, R. Antonova, J. Bohg, M. Schwager, and M. Kochenderfer, editors,Proceedings of The 4th Annual Learning for Dynamics and Control Conferenc...

    2022

  2. [10]

    Cheng, G

    R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick. End-to-end safe reinforce- ment learning through barrier functions for safety-critical continuous control tasks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):3387–3395, Jul

  3. [11]

    W. C. Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. InAdvances in Neural Information Processing Systems, volume 32, 2019. URLhttps://proceedings.neurips.cc/paper/2019/ file/a02ffd91ece5e7efeb46db8f10a74059-Paper.pdf

    2019

  4. [12]

    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 Processing Systems, volume 31. Curr...

  5. [13]

    Coronato, M

    A. Coronato, M. Naeem, G. De Pietro, and G. Paragliola. Reinforcement learn- ing for intelligent healthcare applications: A survey. Artificial Intelligence in Medicine, 109:101964, 2020. ISSN 0933-3657. doi: https://doi.org/10.1016/j. artmed.2020.101964. URL https://www.scienc...

    2020

  6. [14]

    C. Fan, C. Zhang, A. Yahja, and A. Mostafavi. Disaster city digital twin: A vision for integrating artificial and human intelligence for disaster management. International Journal of Information Management, 56:102049, 2021. ISSN 0268-

    2021

  7. [15]

    E. A. Feinberg. Constrained discounted markov decision processes and hamiltonian cycles. Mathematics of Operations Research, 25(1):130–140, 2000. doi: 10.1287/moor. 25.1.130.15210. URL https://doi.org/10.1287/moor.25.1.130.15210

    doi

  8. [16]

    J. F. Fisac, N. F. Lugovoy, V. Rubies-Royo, S. Ghosh, and C. J. Tomlin. Bridging hamilton-jacobi safety analysis and reinforcement learning. In2019 International Conference on Robotics and Automation (ICRA), page 8550–8556. IEEE Press,

  9. [17]

    García, Fern, and o Fernández

    J. García, Fern, and o Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437–1480, 2015. URL http://jmlr.org/papers/v16/garcia15a.html

    2015

  10. [18]

    S. Gros, M. Zanon, and A. Bemporad. Safe reinforcement learning via projection on a safe set: How to achieve optimality?IFAC-PapersOnLine, 53(2):8076–8081, 2020. ISSN 2405-8963. doi: https://doi.org/10.1016/j.ifacol.2020.12.2276. URLhttps:// www.sciencedirect.com/science/artic...

    2020 doi

  11. [19]

    S. Gu, L. Yang, Y. Du, G. Chen, F. Walter, J. Wang, and A. Knoll. A review of safe reinforcement learning: Methods, theory and applications, 2024. URLhttps: //arxiv.org/abs/2205.10330

    2024 arXiv

  12. [20]

    HasanzadeZonuzy, A

    A. HasanzadeZonuzy, A. Bura, D. Kalathil, and S. Shakkottai. Learning with safety constraints: Sample complexity of reinforcement learning for constrained mdps. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):7667–7674, 5

  13. [21]

    URL https://doi.org/10.1109/ICRA

    doi: 10.1109/ICRA.2019.8794107. URL https://doi.org/10.1109/ICRA. 2019.8794107

    2019

  14. [22]

    P. Kolesar. A markovian model for hospital admission scheduling.Management Science, 16(6):B384–B396, 1970. ISSN 00251909, 15265501. URLhttp://www.jstor. org/stable/2628725. 15

    1970

  15. [23]

    J. Li, D. Fridovich-Keil, S. Sojoudi, and C. J. Tomlin. Augmented lagrangian method for instantaneously constrained reinforcement learning problems. In2021 60th IEEE Conference on Decision and Control (CDC), page 2982–2989. IEEE Press, 2021. doi: 10.1109/CDC45484.2021.9683088....

    2021

  16. [24]

    R. Li, Z. Zhao, Q. Sun, C.-L. I, C. Yang, X. Chen, M. Zhao, and H. Zhang. Deep reinforcement learning for resource management in network slicing.IEEE Access, 6: 74429–74441, 2018. doi: 10.1109/ACCESS.2018.2881964

    2018

  17. [25]

    H. Mao, M. Alizadeh, I. Menache, and S. Kandula. Resource management with deep reinforcement learning. InProceedings 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. d...

    2016

  18. [26]

    J. McMahan. Deterministic policies for constrained reinforcement learning in polyno- mial time, 2024. URLhttps://arxiv.org/abs/2405.14183

    2024 arXiv

  19. [27]

    Khonji, A

    M. Khonji, A. Jasour, and B. Williams. Approximability of constant-horizon con- strained pomdp. InProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 5583–5590. International Joint Conferences on Artificial Intelligence O...

    2019 doi

  20. [28]

    McMahan and X

    J. McMahan and X. Zhu. Anytime-constrained reinforcement learning. In S. Dasgupta, S. Mandt, and Y. Li, editors,Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, pages 4321–4329. P...

    2024

  21. [29]

    Paragliola, A

    G. Paragliola, A. Coronato, M. Naeem, and G. De Pietro. A reinforcement learning- based approach for the risk management of e-health environments: A case study. In 2018 14th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS), pages 711–716, 20...

    2018

  22. [30]

    Paternain, L

    S. Paternain, L. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforce- ment learning has zero duality gap. InAdvances in Neural Information Processing Systems, volume 32, 2019. URLhttps://proceedings.neurips.cc/paper_files/ paper/2019/file/c1aeb6517a1c7f33514f7ff690...

    2019

  23. [31]

    Peng and X

    H. Peng and X. Shen. Multi-agent reinforcement learning based resource management in mec- and uav-assisted vehicular networks.IEEE Journal on Selected Areas in Communications, 39(1):131–141, 2021. doi: 10.1109/JSAC.2020.3036962

    2021

  24. [32]

    Roderick, V

    M. Roderick, V. Nagarajan, and Z. Kolter. Provably safe pac-mdp exploration using analogies. In A. Banerjee and K. Fukumizu, editors,Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Resear...

    2021

  25. [33]

    McMahan and X

    J. McMahan and X. Zhu. Anytime-constrained multi-agent reinforcement learning,

  26. [34]

    Y. L. Tsai, A. Phatak, P. K. Kitanidis, and C. B. Field. Deep Reinforcement Learning for Disaster Response: Navigating the Dynamic Emergency Vehicle and Rescue Team Dispatch during a Flood. InAGU Fall Meeting Abstracts, volume 2019, pages NH33B–14, Dec. 2019

    2019

  27. [35]

    Vaswani, L

    S. Vaswani, L. Yang, and C. Szepesvari. Near-optimal sample complex- ity bounds for constrained mdps. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Informa- tion Processing Systems, volume 35, pages 3110–3122. Curran Associ...

  28. [36]

    Y. Wang, S. S. Zhan, R. Jiao, Z. Wang, W. Jin, Z. Yang, Z. Wang, C. Huang, and Q. Zhu. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, ...

    2023

  29. [37]

    H. Wei, X. Liu, and L. Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In G. Camps-Valls, F. J. R. Ruiz, and I. Valera, editors,Proceedings of The 25th International Conference on Artificial Int...

    2022

  30. [38]

    C. Wu, B. Ju, Y. Wu, X. Lin, N. Xiong, G. Xu, H. Li, and X. Liang. Uav autonomous target search based on deep reinforcement learning in complex disaster scene.IEEE Access, 7:117227–117245, 2019. doi: 10.1109/ACCESS.2019.2933002

    2019

  31. [39]

    Xu and S

    H. Xu and S. Mannor. Probabilistic goal markov decision processes. InProceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Three, IJCAI’11, page 2046–2052. AAAI Press, 2011. ISBN 9781577355151

    2011

  32. [40]

    Thomas, Y

    G. Thomas, Y. Luo, and T. Ma. Safe reinforcement learning by imag- ining the near future. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information 16 Processing Systems, volume 34, pages 13859–13869. Curran Associates, Inc.,

  33. [41]

    URL https://proceedings.neurips.cc/paper_files/paper/2021/file/ 73b277c11266681122132d024f53a75b-Paper.pdf

    2021

  34. [49]

    Infeasible

    W. Zhao, T. He, R. Chen, T. Wei, and C. Liu. State-wise safe reinforcement learning: a survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI ’23, 2023. ISBN 978-1-956792-03-4. doi: 10.24963/ijcai. 2023/763. URL https://doi...

    2023 doi

  35. [2017]

    URL https://proceedings.neurips.cc/paper_files/paper/2017/file/ 766ebcd59621e305170616ba3d3dac32-Paper.pdf

    2017

  36. [2018]

    URL https://proceedings.neurips.cc/paper_files/paper/2018/file/ 4fe5149039b52765bde64beb9f674940-Paper.pdf. 14

    2018

  37. [2019]

    URLhttps://ojs.aaai.org/index.php/ AAAI/article/view/4213

    doi: 10.1609/aaai.v33i01.33013387. URLhttps://ojs.aaai.org/index.php/ AAAI/article/view/4213

    doi

  38. [2021]

    URL https://ojs.aaai.org/index.php/ AAAI/article/view/16937

    doi: 10.1609/aaai.v35i9.16937. URL https://ojs.aaai.org/index.php/ AAAI/article/view/16937

    doi

  39. [2022]

    URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ 14a5ebc9cd2e507cd811df78c15bf5d7-Paper-Conference.pdf

    2022

  40. [2024]

    URL https://arxiv.org/abs/2410.23637

    arXiv

  41. [4012]

    URL https://www

    doi: https://doi.org/10.1016/j.ijinfomgt.2019.102049. URL https://www. sciencedirect.com/science/article/pii/S0268401219302956

    2019

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.