Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
This work addresses the challenge of safe exploration in reinforcement learning for applications requiring strict safety constraints, representing an incremental improvement in regret bounds.
The paper tackles the safe reinforcement learning problem in constrained Markov decision processes by proposing a model-based algorithm with novel cost and reward estimators that ensure no constraint violations. It achieves an improved regret upper bound of ̃O((C̄ - C̄_b)^{-1}H^{2.5}S√(AK)), nearly matching the lower bound when C̄ - C̄_b = Ω(H).
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 $\widetilde{\mathcal{O}}((\bar C - \bar C_b)^{-1}H^{2.5} S\sqrt{AK})$ where $\bar C$ is the cost budget for an episode, $\bar C_b$ 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 C_b=Ω(H)$, it nearly matches the regret lower bound of $Ω(H^{1.5}\sqrt{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.