mlsanityData to 14 Oct 2026

Reinforcement Learning with Almost Sure Constraints

arXiv 2112.05198 ↗First posted 9 Dec 2021cs.LG cs.SY eess.SYcited by 11

Not on the map. Why?

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.

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

8 of 19 references.

References · 8

  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  2. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  3. 2019Reinforcement Learning with Convex Constraintscited by 60
  4. 2015Safety-Constrained Reinforcement Learning for MDPscited by 33
  5. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  6. 2021Learning to Act Safely with Limited Exposure and Almost Sure Certaintycited by 2
  7. 2021Computing Complexity-aware Plans Using Kolmogorov Complexitycited by 2
  8. 2020Assured RL: Reinforcement Learning with Almost Sure Constraintscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 2; 2024: 3; 2025: 1; 2026: 1.

11 papers.

  1. 2022Effects of Safety State Augmentation on Safe Explorationcited by 6
  2. 2023Anytime-Constrained Reinforcement Learningcited by 6
  3. 2022Policy Gradients for Probabilistic Constrained Reinforcement Learningcited by 5
  4. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  5. 2022Learning Globally Smooth Functions on Manifoldscited by 4
  6. 2022Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamicscited by 3
  7. 2024Learning safety critics via a non-contractive binary bellman operatorcited by 3
  8. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  9. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  10. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  11. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0