Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model

In this work, we study the sample complexity problem of risk-sensitive Reinforcement Learning (RL) with a generative model, where we aim to maximize the Conditional Value at Risk (CVaR) with risk tolerance level τ at each step, named Iterated CVaR. We develop nearly matching upper and lower bounds on the sample complexity for this problem. Specifically, we first prove that a value iteration-based algorithm, ICVaR-VI, achieves an ϵ-optimal policy with at most Õ (SA/((1-γ )⁴τ²ϵ²) samples, where γ is the discount factor, and S,A are the sizes of the state and action spaces. Furthermore, if τ ≥ γ, then the sample complexity can be further improved to Õ (SA/(1- γ)³ϵ²). We further show a minimax lower bound of Õ ((1-γτ) SA/(1-γ)⁴τϵ²). For a constant risk level 0 < τ ≤ 1, our upper and lower bounds match with each other, demonstrating the tightness and optimality of our analyses. We also investigate a limiting case with a small risk level τ, called Worst-Path RL, where the objective is to maximize the minimum possible cumulative reward. We develop matching upper and lower bounds of Õ (SA/p_min), where p_min denotes the minimum non-zero reaching probability of the transition kernel.