mlsanityData to 7 Oct 2026

Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation

arXiv 2301.11547 ↗First posted 27 Jan 2023cs.LG cs.AI cs.SYcited by 6

Not on the map. Why?

Abstract (arXiv)

Constrained Markov decision processes (CMDPs) model scenarios of sequential decision making with multiple objectives that are increasingly important in many applications. However, the model is often unknown and must be learned online while still ensuring the constraint is met, or at least the violation is bounded with time. Some recent papers have made progress on this very challenging problem but either need unsatisfactory assumptions such as knowledge of a safe policy, or have high cumulative regret. We propose the Safe PSRL (posterior sampling-based RL) algorithm that does not need such assumptions and yet performs very well, both in terms of theoretical regret bounds as well as empirically. The algorithm achieves an efficient tradeoff between exploration and exploitation by use of the posterior sampling principle, and provably suffers only bounded constraint violation by leveraging the idea of pessimism. Our approach is based on a primal-dual approach. We establish a sub-linear tilde Oleft(H2.5 √|S|2 |A| K right) upper bound on the Bayesian reward objective regret along with a bounded, i.e., tildeOleft(1right) constraint violation regret over K episodes for an |S|-state, |A|-action and horizon H CMDP.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 24 of its 37 references that are in the map. First posted on arXiv 27 Jan 2023.

Builds on

24 of 37 references.

References · 24

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  5. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  6. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  8. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  9. 2020Stochastic Bandits with Linear Constraintscited by 68
  10. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  11. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  12. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
12 more
  1. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  2. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  4. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  5. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  6. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  7. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  8. 2019Safe Linear Stochastic Banditscited by 27
  9. 2020Learning in Markov Decision Processes under Constraintscited by 20
  10. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  11. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  12. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 2.

6 papers.

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  2. 2023A safe exploration approach to constrained Markov decision processescited by 10
  3. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  4. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  5. 2023Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Needcited by 0
  6. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0