# Reinforcement Learning with Almost Sure Constraints

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 19 references that are in the map.
- First posted on arXiv 9 Dec 2021.

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

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Safety-Constrained Reinforcement Learning for MDPs](https://mlsanity.com/paper/1510.05880/) (2015)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Learning to Act Safely with Limited Exposure and Almost Sure Certainty](https://mlsanity.com/paper/2105.08748/) (2021)
- [Computing Complexity-aware Plans Using Kolmogorov Complexity](https://mlsanity.com/paper/2109.10303/) (2021)
- [Assured RL: Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2012.13036/) (2020)

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

- [Effects of Safety State Augmentation on Safe Exploration](https://mlsanity.com/paper/2206.02675/) (2022)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)
- [Policy Gradients for Probabilistic Constrained Reinforcement Learning](https://mlsanity.com/paper/2210.00596/) (2022)
- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [Learning Globally Smooth Functions on Manifolds](https://mlsanity.com/paper/2210.00301/) (2022)
- [Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamics](https://mlsanity.com/paper/2212.01505/) (2022)
- [Learning safety critics via a non-contractive binary bellman operator](https://mlsanity.com/paper/2401.12849/) (2024)
- [Anytime-Competitive Reinforcement Learning with Policy Prior](https://mlsanity.com/paper/2311.01568/) (2023)
- [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)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

In this work we address the problem of finding feasible policies for Constrained Markov Decision Processes under probability one constraints. We argue that stationary policies are not sufficient for solving this problem, and that a rich class of policies can be found by endowing the controller with a scalar quantity, so called budget, that tracks how close the agent is to violating the constraint. We show that the minimal budget required to act safely can be obtained as the smallest fixed point of a Bellman-like operator, for which we analyze its convergence properties. We also show how to learn this quantity when the true kernel of the Markov decision process is not known, while providing sample-complexity bounds. The utility of knowing this minimal budget relies in that it can aid in the search of optimal or near-optimal policies by shrinking down the region of the state space the agent must navigate. Simulations illustrate the different nature of probability one constraints against the typically used constraints in expectation.