Minimax Optimal Sample Complexity for Iterated CVaR Reinforcement Learning With a Generative Model

Standard Reinforcement Learning (RL) algorithms are typically designed to maximize the expected accumulative reward, which may be inadequate in scenarios where risk sensitivity is critical. In this work, the problem of risk-sensitive RL with Iterated Conditional Value at Risk is studied, where the objective is to optimize outcomes under a specified risk level τ at each step. This work provides the first minimax optimal sample complexity analysis for this problem with a generative model. Specifically, the sample complexity is firstly characterized as a function of the number of states S , actions A , and effective horizon 1-γ)-1 (resp. horizon H in the finite-horizon setting), and is further shown to be minimax optimal via a novel minimax lower bound analysis when the risk level <; τ ≤ 1 is treated as a constant or the risk level is above a threshold of γ (resp. 1-1/H in the finite horizon setting). For the case when the risk level is small, the limiting case of τ 0→ , termed worst-path RL, is then studied, and the minimax optimal sample complexity is also theoretically characterized.