# Anytime-Constrained Reinforcement Learning

arXiv: https://arxiv.org/abs/2311.05511 · HTML: https://mlsanity.com/paper/2311.05511/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Virtual to Real Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1704.03952/) (2017)
- [Safe Reinforcement Learning by Imagining the Near Future](https://mlsanity.com/paper/2202.07789/) (2022)
- [Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?](https://mlsanity.com/paper/2004.00915/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Deep Reinforcement Learning for Resource Management in Network Slicing](https://mlsanity.com/paper/1805.06591/) (2018)
- [Resource Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/1812.00600/) (2018)
- [Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL](https://mlsanity.com/paper/2008.13319/) (2020)
- [Safe Chance Constrained Reinforcement Learning for Batch Process Control](https://mlsanity.com/paper/2104.11706/) (2021)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Provably Safe PAC-MDP Exploration Using Analogies](https://mlsanity.com/paper/2007.03574/) (2020)
- [Quantile Constrained Reinforcement Learning: A Reinforcement Learning Framework Constraining Outage Probability](https://mlsanity.com/paper/2211.15034/) (2022)

## Built on by (most cited first, 6 of 6)

- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)
- [Off-Policy Reinforcement Learning with Anytime Safety Guarantees via Robust Safe Gradient Flow](https://mlsanity.com/paper/2510.01492/) (2025)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)
- [On the Clock: Towards Punctual and Productive Time-Budgeted AI Agents](https://mlsanity.com/paper/2610.10833/) (2026)

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