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

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

## Key facts

- Cited by 1 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 29 of its 66 references that are in the map.
- First posted on arXiv 20 May 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Policy Gradient for Coherent Risk Measures](https://mlsanity.com/paper/1502.03919/) (2015)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Bayesian Robust Optimization for Imitation Learning](https://mlsanity.com/paper/2007.12315/) (2020)
- [One Risk to Rule Them All: A Risk-Sensitive Perspective on Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2212.00124/) (2022)
- [Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path](https://mlsanity.com/paper/2206.02678/) (2022)
- [Risk-Aware High-level Decisions for Automated Driving at Occluded Intersections with Reinforcement Learning](https://mlsanity.com/paper/2004.04450/) (2020)
- [Markov Decision Processes with Recursive Risk Measures](https://mlsanity.com/paper/2010.07220/) (2020)
- [On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes](https://mlsanity.com/paper/2304.12477/) (2023)
- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents](https://mlsanity.com/paper/2301.12601/) (2023)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [A Policy Gradient Algorithm for the Risk-Sensitive Exponential Cost MDP](https://mlsanity.com/paper/2202.04157/) (2022)
- [Beyond Average Return in Markov Decision Processes](https://mlsanity.com/paper/2310.20266/) (2023)
- [RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2410.23569/) (2024)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [Efficient Risk-sensitive Planning via Entropic Risk Measures](https://mlsanity.com/paper/2502.20423/) (2025)
- [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)
- [Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2510.20199/) (2025)
- [Deep Reinforcement Learning for Optimal Portfolio Allocation: A Comparative Study with Mean-Variance Optimization](https://mlsanity.com/paper/2602.17098/) (2026)

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

- [Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2610.06931/) (2026)

## 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-γ.