# Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 58 references that are in the map.
- First posted on arXiv 7 Feb 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [EPOpt: Learning Robust Neural Network Policies Using Model Ensembles](https://mlsanity.com/paper/1610.01283/) (2016)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [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)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Conservative Offline Distributional Reinforcement Learning](https://mlsanity.com/paper/2107.06106/) (2021)
- [Risk-Averse Offline Reinforcement Learning](https://mlsanity.com/paper/2102.05371/) (2021)
- [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)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2202.09667/) (2022)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [Reinforcement Learning for Education: Opportunities and Challenges](https://mlsanity.com/paper/2107.08828/) (2021)
- [Distributionally Robust Batch Contextual Bandits](https://mlsanity.com/paper/2006.05630/) (2020)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds](https://mlsanity.com/paper/2210.14051/) (2022)
- [Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning](https://mlsanity.com/paper/2106.01723/) (2021)
- [Conditional Value-at-Risk: Theory and Applications](https://mlsanity.com/paper/1511.00140/) (2015)

## Built on by (most cited first, 30 of 32)

- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [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)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)
- [The Central Role of the Loss Function in Reinforcement Learning](https://mlsanity.com/paper/2409.12799/) (2024)
- [Risk-sensitive Markov Decision Process and Learning under General Utility Functions](https://mlsanity.com/paper/2311.13589/) (2023)
- [Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2402.07598/) (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)
- [Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees](https://mlsanity.com/paper/2508.05441/) (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)
- [Robust Risk-Sensitive Reinforcement Learning with Conditional Value-at-Risk](https://mlsanity.com/paper/2405.01718/) (2024)
- [Risk-aware Direct Preference Optimization under Nested Risk Measure](https://mlsanity.com/paper/2505.20359/) (2025)
- [Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2510.20199/) (2025)
- [LAD: Learning Advantage Distribution for Reasoning](https://mlsanity.com/paper/2602.20132/) (2026)
- [JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning](https://mlsanity.com/paper/2307.11704/) (2023)
- [Risk-Sensitive Agent Compositions](https://mlsanity.com/paper/2506.04632/) (2025)
- [Minimax-optimal trust-aware multi-armed bandits](https://mlsanity.com/paper/2410.03651/) (2024)
- [Non-Linear Model-Based Sequential Decision-Making in Agriculture](https://mlsanity.com/paper/2509.01924/) (2025)
- [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)
- [Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity](https://mlsanity.com/paper/2602.03778/) (2026)
- [The Critical Horizon: Inspection Design Principles for Multi-Stage Operations and Deep Reasoning](https://mlsanity.com/paper/2602.09394/) (2026)
- [Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems](https://mlsanity.com/paper/2604.12519/) (2026)
- [Pessimistic Risk-Aware Policy Learning in Contextual Bandits](https://mlsanity.com/paper/2605.15620/) (2026)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)

## Abstract (arXiv)

In this paper, we study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance τ. Starting with multi-arm bandits (MABs), we show the minimax CVaR regret rate is Omega(√τ-1AK), where A is the number of actions and K is the number of episodes, and that it is achieved by an Upper Confidence Bound algorithm with a novel Bernstein bonus. For online RL in tabular Markov Decision Processes (MDPs), we show a minimax regret lower bound of Omega(√τ-1SAK) (with normalized cumulative rewards), where S is the number of states, and we propose a novel bonus-driven Value Iteration procedure. We show that our algorithm achieves the optimal regret of widetilde O(√τ-1SAK) under a continuity assumption and in general attains a near-optimal regret of widetilde O(τ-1√SAK), which is minimax-optimal for constant τ. This improves on the best available bounds. By discretizing rewards appropriately, our algorithms are computationally efficient.