# Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism

arXiv: https://arxiv.org/abs/2410.10158 · HTML: https://mlsanity.com/paper/2410.10158/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Built on by (most cited first, 7 of 7)

- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Constrained Meta Reinforcement Learning with Provable Test-Time Safety](https://mlsanity.com/paper/2601.21845/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Provably Safe Sim-to-Real Transfer](https://mlsanity.com/paper/2609.01418/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## 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.