mlsanityData to 14 Oct 2026

Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling

arXiv 2405.19017 ↗First posted 29 May 2024cs.LGcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We present a new algorithm based on posterior sampling for learning in Constrained Markov Decision Processes (CMDP) in the infinite-horizon undiscounted setting. The algorithm achieves near-optimal regret bounds while being advantageous empirically compared to the existing algorithms. Our main theoretical result is a Bayesian regret bound for each cost component of tildeO (DS√AT) for any communicating CMDP with S states, A actions, and diameter D. This regret bound matches the lower bound in order of time horizon T and is the best-known regret bound for communicating CMDPs achieved by a computationally tractable algorithm. Empirical results show that our posterior sampling algorithm outperforms the existing algorithms for constrained reinforcement learning.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 19 of its 29 references that are in the map. First posted on arXiv 29 May 2024.

Builds on

19 of 29 references.

References · 19

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2018Reward Constrained Policy Optimizationcited by 417
  3. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
  4. 2019Batch Policy Learning under Constraintscited by 244
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  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
7 more
  1. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  2. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
  3. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  4. 2020Learning in Markov Decision Processes under Constraintscited by 20
  5. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  6. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  7. 2022An Empirical Evaluation of Posterior Sampling for Constrained Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  2. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  2. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
  3. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  4. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
  5. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  6. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  8. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality