PAC Sample Complexity of CVaR-Constrained Reinforcement Learning

High-stakes and safety-critical applications, such as financial investment and robotics, require sequential decision making that controls tail risk while optimizing average performance. Motivated by this fact, this paper studies Conditional Value-at-Risk (CVaR)-constrained reinforcement learning (RL) in the PAC setting. The goal is to minimize the expected cumulative performance cost subject to a CVaR constraint on the cumulative risk cost. We first prove the existence of an optimal policy that is stochastic and Markovian on the augmented state space. Based on this property, we propose an efficient and three-phase algorithm CVaR-PDS. This algorithm first solves linearly-constrained RL subproblems indexed by a grid of Value-at-Risk (VaR) candidates, and estimates a global model for subproblem solution evaluation, and then carefully performs post-hoc feasibility filtering and policy selection. We establish an $\tilde{\mathcal{O}}(\frac{S^{2}A{H}^4\tau }{{\alpha }^2{\epsilon }^3}+\frac{SA{H}^5\tau }{{\alpha }^2{\epsilon }^4}+\frac{H^7\tau }{{\zeta }_{\xi }^2{\alpha }^2{\epsilon }^3})$ sample complexity guarantee for algorithm CVaR-PDS, where $\tau$ is the constraint threshold, $\alpha$ is the risk level, and ${\zeta }_{\xi }$ is the Slater margin, together with an $\Omega (\frac{SA{H}^2}{\alpha {\epsilon }^2})$ sample complexity lower bound. To the best of our knowledge, our work provides the first non-asymptotic (finite-sample) results for CVaR-constrained RL.