mlsanityData to 14 Oct 2026

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

arXiv 2503.08934 ↗First posted 11 Mar 2025cs.LGcited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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, a criterion we refer to as Iterated CVaR. We first build a connection between Iterated CVaR RL and (s, a)-rectangular distributional robust RL with a specific uncertainty set for CVaR. We establish nearly matching upper and lower bounds on the sample complexity of this problem. Specifically, we first prove that a value iteration-based algorithm, ICVaR-VI, achieves an ε-optimal policy with at most tildeO left(fracSA(1-γ)4τ2ε2 right) samples, where γ is the discount factor, and S, A are the sizes of the state and action spaces. Furthermore, when τ ≥ γ, the sample complexity improves to tildeO left( fracSA(1-γ)3ε2 right). We further show a minimax lower bound of tildeO left(frac(1-γ τ)SA(1-γ)4τε2 right). For a fixed risk level τ ∈ (0,1], our upper and lower bounds match, demonstrating the tightness and optimality of our analysis. 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 tildeO left(fracSApmin right), where pmin denotes the minimum non-zero reaching probability of the transition kernel.

Key facts. Cited by 5 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. Builds on 19 of its 47 references that are in the map. First posted on arXiv 11 Mar 2025.

Builds on

19 of 47 references.

References · 19

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  5. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  6. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  7. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  8. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  9. 2015Policy Gradient for Coherent Risk Measurescited by 76
  10. 2020Reinforcement Learning in Economics and Financecited by 58
  11. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  12. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
7 more
  1. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
  2. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 22
  3. 2021On the Convergence and Optimality of Policy Gradient for Markov Coherent Riskcited by 20
  4. 2020Markov Decision Processes with Recursive Risk Measurescited by 18
  5. 2023Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalentscited by 15
  6. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 14
  7. 2023Provably Efficient CVaR RL in Low-rank MDPscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  2. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Modelcited by 5
  3. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalentscited by 1
  4. 2026Tail-Influence Sampling for CVaR Policy Evaluationcited by 0
  5. 2026Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Modelcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
  2. 2025Provably Efficient Sample Complexity for Robust CMDP
  3. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis
  4. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  5. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning
  6. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysis
  7. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents
  8. 2024Robust Risk-Sensitive Reinforcement Learning with Conditional Value-at-Risk