mlsanityData to 7 Oct 2026

Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need

arXiv 2309.15737 ↗First posted 27 Sep 2023cs.LGcited by 0

Not on the map. Why?

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 (HS √AT) for any communicating CMDP with S states, A actions, and bound on the hitting time H. This regret bound matches the lower bound in order of time horizon T and is the best-known regret bound for communicating CMDPs in the infinite-horizon undiscounted setting. Empirical results show that, despite its simplicity, our posterior sampling algorithm outperforms the existing algorithms for constrained reinforcement learning.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 39 references that are in the map. First posted on arXiv 27 Sep 2023.

Builds on

20 of 39 references.

References · 20

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2018Reward Constrained Policy Optimizationcited by 397
  3. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
  4. 2019Batch Policy Learning under Constraintscited by 242
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2021Reinforcement learning based recommender systems: A surveycited by 187
  7. 2020Exploration-Exploitation in Constrained MDPscited by 146
  8. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  9. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  10. 2017AI Safety Gridworldscited by 108
  11. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  12. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
8 more
  1. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  2. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  3. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  4. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  5. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  6. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  7. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  8. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6

Built on by

Not cited yet.