Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
This paper studies the safe reinforcement learning problem formulated as an episodic finite-horizon tabular constrained Markov decision process with an unknown transition kernel and stochastic reward and cost functions. We propose a model-based algorithm based on novel cost and reward function estimators that provide tighter cost pessimism and reward optimism. While guaranteeing no constraint violation in every episode, our algorithm achieves a regret upper bound of widetildeO((bar C - bar Cb)-1H2.5 S√AK) where bar C is the cost budget for an episode, bar Cb is the expected cost under a safe baseline policy over an episode, H is the horizon, and S, A and K are the number of states, actions, and episodes, respectively. This improves upon the best-known regret upper bound, and when bar C- bar Cb=Omega(H), it nearly matches the regret lower bound of Omega(H1.5√SAK). We deduce our cost and reward function estimators via a Bellman-type law of total variance to obtain tight bounds on the expected sum of the variances of value function estimates. This leads to a tighter dependence on the horizon in the function estimators. We also present numerical results to demonstrate the computational effectiveness of our proposed framework.
Key facts. Cited by 7 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. First posted on arXiv 14 Oct 2024.
Builds on
0 of 0 references.
No references here yet.
Built on by
Citing papers per year: 2025: 1; 2026: 6.
7 papers.
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
- 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
- 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
- 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
- 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
- 2026Provably Safe Sim-to-Real Transfercited by 0
- 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0
- 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraints1 Oct 2026
- 2026Provably Safe Sim-to-Real Transfer1 Sep 2026
- 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret12 May 2026
- 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses12 May 2026
- 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards29 Mar 2026
- 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safety29 Jan 2026
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation14 Feb 2025
Similar, not cited
Close in wording, no citation either way
- 2025Tail Distribution of Regret in Optimistic Reinforcement Learning
- 2024Optimistic Q-learning for average reward and episodic reinforcement learning
- 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
- 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
- 2025Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
- 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
- 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
- 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning