mlsanityData to 7 Oct 2026

Anytime-Constrained Reinforcement Learning

arXiv 2311.05511 ↗First posted 9 Nov 2023cs.LG cs.AI cs.DScited by 5

Not on the map. Why?

Abstract (arXiv)

We introduce and study constrained Markov Decision Processes (cMDPs) with anytime constraints. An anytime constraint requires the agent to never violate its budget at any point in time, almost surely. Although Markovian policies are no longer sufficient, we show that there exist optimal deterministic policies augmented with cumulative costs. In fact, we present a fixed-parameter tractable reduction from anytime-constrained cMDPs to unconstrained MDPs. Our reduction yields planning and learning algorithms that are time and sample-efficient for tabular cMDPs so long as the precision of the costs is logarithmic in the size of the cMDP. However, we also show that computing non-trivial approximately optimal policies is NP-hard in general. To circumvent this bottleneck, we design provable approximation algorithms that efficiently compute or learn an arbitrarily accurate approximately feasible policy with optimal value so long as the maximum supported cost is bounded by a polynomial in the cMDP or the absolute budget. Given our hardness results, our approximation guarantees are the best possible under worst-case analysis.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 20 of its 59 references that are in the map. First posted on arXiv 9 Nov 2023.

Builds on

20 of 59 references.

References · 20

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
  3. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  4. 2013Bandits with Knapsackscited by 163
  5. 2020Exploration-Exploitation in Constrained MDPscited by 146
  6. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2017Virtual to Real Reinforcement Learning for Autonomous Drivingcited by 79
  10. 2022Safe Reinforcement Learning by Imagining the Near Futurecited by 67
  11. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  12. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
8 more
  1. 2020Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?cited by 29
  2. 2018Deep Reinforcement Learning for Resource Management in Network Slicingcited by 27
  3. 2018Resource Constrained Deep Reinforcement Learningcited by 23
  4. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  5. 2021Reinforcement Learning with Almost Sure Constraintscited by 11
  6. 2021Safe Chance Constrained Reinforcement Learning for Batch Process Controlcited by 10
  7. 2020Provably Safe PAC-MDP Exploration Using Analogiescited by 9
  8. 2022Quantile Constrained Reinforcement Learning: A Reinforcement Learning Framework Constraining Outage Probabilitycited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 2.

5 papers.

  1. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  2. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  3. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  4. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0
  5. 2026On the Clock: Towards Punctual and Productive Time-Budgeted AI Agentscited by 0