mlsanityData to 7 Oct 2026

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

arXiv 2302.03201 ↗First posted 7 Feb 2023cs.LG math.OC math.STcited by 32

Not on the map. Why?

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.

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

Builds on

28 of 58 references.

References · 28

  1. 2021Convex optimizationcited by 2,479
  2. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 162
  8. 2016EPOpt: Learning Robust Neural Network Policies Using Model Ensemblescited by 136
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  12. 2014Optimizing the CVaR via Samplingcited by 98
16 more
  1. 2014Algorithms for CVaR Optimization in MDPscited by 98
  2. 2022Robust Reinforcement Learning using Offline Datacited by 95
  3. 2021Conservative Offline Distributional Reinforcement Learningcited by 78
  4. 2021Risk-Averse Offline Reinforcement Learningcited by 65
  5. 2019Being Optimistic to Be Conservative: Quickly Learning a CVaR Policycited by 63
  6. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
  7. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  8. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
  9. 2022Doubly Robust Distributionally Robust Off-Policy Evaluation and Learningcited by 34
  10. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
  11. 2021Reinforcement Learning for Education: Opportunities and Challengescited by 25
  12. 2020Distributionally Robust Batch Contextual Banditscited by 20
  13. 2019Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewardscited by 19
  14. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  15. 2021Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learningcited by 10
  16. 2015Conditional Value-at-Risk: Theory and Applicationscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 10; 2025: 8; 2026: 8.

32 papers.

Sort:

By area:

  1. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  2. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  3. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  4. 2024Three Dogmas of Reinforcement Learningcited by 14
  5. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  6. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  7. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 7
  8. 2023Risk-sensitive Markov Decision Process and Learning under General Utility Functionscited by 7
  9. 2024Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Modelcited by 7
  10. 2023Provably Efficient CVaR RL in Low-rank MDPscited by 6
  11. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  12. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 4
20 more
  1. 2025Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guaranteescited by 4
  2. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  3. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  4. 2024Robust Risk-Sensitive Reinforcement Learning with Conditional Value-at-Riskcited by 2
  5. 2025Risk-aware Direct Preference Optimization under Nested Risk Measurecited by 2
  6. 2026LAD: Learning Advantage Distribution for Reasoningcited by 2
  7. 2023JoinGym: An Efficient Query Optimization Environment for Reinforcement Learningcited by 1
  8. 2025Risk-Sensitive Agent Compositionscited by 1
  9. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalentscited by 1
  10. 2024Minimax-optimal trust-aware multi-armed banditscited by 0
  11. 2025Non-Linear Model-Based Sequential Decision-Making in Agriculturecited by 0
  12. 2025Reducing the Probability of Undesirable Outputs in Language Models Using Probabilistic Inferencecited by 0
  13. 2025Constrained Language Model Policy Optimization via Risk-aware Stepwise Alignmentcited by 0
  14. 2026Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinitycited by 0
  15. 2026The Critical Horizon: Inspection Design Principles for Multi-Stage Operations and Deep Reasoningcited by 0
  16. 2026Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problemscited by 0
  17. 2026Pessimistic Risk-Aware Policy Learning in Contextual Banditscited by 0
  18. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0
  19. 2026Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVIcited by 0
  20. 2026Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedbackcited by 0