Efficient Exploration In Average-reward Constrained Reinforcement Learning: Achieving Near-optimal Regret With Posterior Sampling

Abstract

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 \(\tilde\{O\} (DS\sqrt\{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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyprovodin2024efficient

Related papers

• Provably Efficient Exploration In Constrained Reinforcement Learning:posterior Sampling Is All You Need (2023)0.00
• Posterior Sampling For Reinforcement Learning: Worst-case Regret Bounds (2017)0.00
• Model-based Reinforcement Learning For Continuous Control With Posterior Sampling (2020)0.00
• Prior-dependent Analysis Of Posterior Sampling Reinforcement Learning With Function Approximation (2024)0.00
• Optimistic Posterior Sampling For Reinforcement Learning With Few Samples And Tight Guarantees (2022)0.00
• Variance-aware Regret Bounds For Undiscounted Reinforcement Learning In Mdps (2018)0.00
• Minimax Regret Bounds For Reinforcement Learning (2017)0.00
• Logarithmic Regret Of Exploration In Average Reward Markov Decision Processes (2025)0.00