# Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path

arXiv: https://arxiv.org/abs/2206.02678 · HTML: https://mlsanity.com/paper/2206.02678/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2022.

## Builds on (most cited first, 18 of 18)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Optimizing the CVaR via Sampling](https://mlsanity.com/paper/1404.3862/) (2014)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy](https://mlsanity.com/paper/1911.01546/) (2019)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [Medical Dead-ends and Learning to Identify High-risk States and Treatments](https://mlsanity.com/paper/2110.04186/) (2021)
- [Markov Decision Processes with Recursive Risk Measures](https://mlsanity.com/paper/2010.07220/) (2020)

## Built on by (most cited first, 22 of 22)

- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)
- [Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2402.07598/) (2024)
- [A Simple Mixture Policy Parameterization for Improving Sample Efficiency of CVaR Optimization](https://mlsanity.com/paper/2403.11062/) (2024)
- [Provably Efficient CVaR RL in Low-rank MDPs](https://mlsanity.com/paper/2311.11965/) (2023)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2503.08934/) (2025)
- [Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model](https://mlsanity.com/paper/2506.00286/) (2025)
- [Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2402.18159/) (2024)
- [Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes](https://mlsanity.com/paper/2404.00099/) (2024)
- [Risk-sensitive Reinforcement Learning Based on Convex Scoring Functions](https://mlsanity.com/paper/2505.04553/) (2025)
- [Risk-aware Direct Preference Optimization under Nested Risk Measure](https://mlsanity.com/paper/2505.20359/) (2025)
- [Online Risk-Averse Planning in POMDPs Using Iterated CVaR Value Function](https://mlsanity.com/paper/2601.20554/) (2026)
- [On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2605.21763/) (2026)
- [Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation](https://mlsanity.com/paper/2402.18149/) (2024)
- [Reducing the Probability of Undesirable Outputs in Language Models Using Probabilistic Inference](https://mlsanity.com/paper/2510.21184/) (2025)
- [Constrained Language Model Policy Optimization via Risk-aware Stepwise Alignment](https://mlsanity.com/paper/2512.24263/) (2025)
- [Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems](https://mlsanity.com/paper/2604.12519/) (2026)
- [Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees](https://mlsanity.com/paper/2609.35874/) (2026)
- [Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedback](https://mlsanity.com/paper/2609.38938/) (2026)
- [Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2610.06931/) (2026)

## Abstract (arXiv)

In this paper, we study a novel episodic risk-sensitive Reinforcement Learning (RL) problem, named Iterated CVaR RL, which aims to maximize the tail of the reward-to-go at each step, and focuses on tightly controlling the risk of getting into catastrophic situations at each stage. This formulation is applicable to real-world tasks that demand strong risk avoidance throughout the decision process, such as autonomous driving, clinical treatment planning and robotics. We investigate two performance metrics under Iterated CVaR RL, i.e., Regret Minimization and Best Policy Identification. For both metrics, we design efficient algorithms ICVaR-RM and ICVaR-BPI, respectively, and provide nearly matching upper and lower bounds with respect to the number of episodes K. We also investigate an interesting limiting case of Iterated CVaR RL, called Worst Path RL, where the objective becomes to maximize the minimum possible cumulative reward. For Worst Path RL, we propose an efficient algorithm with constant upper and lower bounds. Finally, our techniques for bounding the change of CVaR due to the value function shift and decomposing the regret via a distorted visitation distribution are novel, and can find applications in other risk-sensitive RL problems.