mlsanityData to 7 Oct 2026

On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents

arXiv 2605.21763 ↗First posted 20 May 2026cs.LG cs.SY eess.SYcited by 0

Not on the map. Why?

Abstract (arXiv)

We study risk-sensitive reinforcement learning in finite discounted MDPs, where a generative model of the MDP is assumed to be available. We consider a family or risk measures called the optimized certainty equivalent (OCE), which includes important risk measures such as entropic risk, CVaR, and mean-variance. Our focus is on the sample complexities of learning the optimal state-action value function (value learning) and an optimal policy (policy learning) under recursive OCE. We provide an exact characterization of utility functions u for which the corresponding OCE defines an objective that is PAC-learnable. We analyze a simple model-based approach and derive PAC sample complexity bounds. We establish that whenever u does not have full domain dom(u)neq ℝ, the corresponding problem is not PAC-learnable. Finally, we establish corresponding lower bounds for both value and policy learning, demonstrating tightness in the size SA of state-action space, and for a more restricted class of utilities, we derive lower bounds that makes the dependence on the effective horizon frac11-γ explicit. Specifically, for CVaRτ we show that the correct dependence on τ is frac1τ2, thus improving by a factor of frac1τ over state-of-the-art although our bound has a suboptimal dependence on frac11-γ.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 66 references that are in the map. First posted on arXiv 20 May 2026.

Builds on

29 of 66 references.

References · 29

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2013Risk-sensitive Reinforcement Learningcited by 129
  3. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  4. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  5. 2014Algorithms for CVaR Optimization in MDPscited by 98
  6. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  7. 2015Policy Gradient for Coherent Risk Measurescited by 74
  8. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
  9. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  10. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
  11. 2020Bayesian Robust Optimization for Imitation Learningcited by 28
  12. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 21
17 more
  1. 2022One Risk to Rule Them All: A Risk-Sensitive Perspective on Model-Based Offline Reinforcement Learningcited by 21
  2. 2020Risk-Aware High-level Decisions for Automated Driving at Occluded Intersections with Reinforcement Learningcited by 19
  3. 2020Markov Decision Processes with Recursive Risk Measurescited by 17
  4. 2023On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processescited by 17
  5. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  6. 2023Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalentscited by 14
  7. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  8. 2022A Policy Gradient Algorithm for the Risk-Sensitive Exponential Cost MDPcited by 11
  9. 2023Beyond Average Return in Markov Decision Processescited by 11
  10. 2024RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learningcited by 8
  11. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 7
  12. 2024Truncated Variance Reduced Value Iterationcited by 6
  13. 2025Efficient Risk-sensitive Planning via Entropic Risk Measurescited by 4
  14. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 4
  15. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Modelcited by 3
  16. 2026Deep Reinforcement Learning for Optimal Portfolio Allocation: A Comparative Study with Mean-Variance Optimizationcited by 2
  17. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalentscited by 1

Built on by

Not cited yet.