# Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model

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

## Key facts

- Cited by 5 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 27 of its 69 references that are in the map.
- First posted on arXiv 30 May 2025.

## 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, 27 of 27)

- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [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)
- [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)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (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)
- [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)
- [A Framework for Time-Consistent, Risk-Averse Model Predictive Control: Theory and Algorithms](https://mlsanity.com/paper/1511.06981/) (2015)
- [Mitigating optimistic bias in entropic risk estimation and optimization](https://mlsanity.com/paper/2409.19926/) (2024)

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

- [Tight Sample Complexity Bounds for Entropic Best Policy Identification](https://mlsanity.com/paper/2605.13717/) (2026)
- [On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2605.21763/) (2026)
- [Risk-Aware General-Utility Markov Decision Processes](https://mlsanity.com/paper/2607.09298/) (2026)
- [Long-Term Sequential Decision Making under Risk](https://mlsanity.com/paper/2607.19914/) (2026)
- [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 with recursive entropic risk measures (ERM), where the risk parameter β neq 0 controls the agent's risk attitude: β>0 for risk-averse and β<0 for risk-seeking behavior. A generative model of the MDP is assumed to be available. 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 ERM. We introduce a model-based algorithm, called Model-Based ERM Q-Value Iteration (MB-RS-QVI), and derive PAC-type bounds on its sample complexity for both value and policy learning. Both PAC bounds scale exponentially with |β|/(1-γ), where γ is the discount factor. We also establish corresponding lower bounds for both value and policy learning, showing that exponential dependence on |β|/(1-γ) is unavoidable in the worst case. The bounds are tight in the number of states and actions (S and A), providing the first rigorous sample complexity guarantees for recursive ERM across both risk-averse and risk-seeking regimes.