# Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 57 references that are in the map.
- First posted on arXiv 3 Oct 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, 28 of 28)

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [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)
- [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)
- [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)
- [Mitigating optimistic bias in entropic risk estimation and optimization](https://mlsanity.com/paper/2409.19926/) (2024)
- [Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2510.20199/) (2025)
- [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)

## Abstract (arXiv)

In this paper, we study the sample complexities of value and policy learning in finite discounted Markov decision processes (MDPs) under recursive entropic risk preferences with risk parameter (βneq 0), assuming access to a generative model of the MDP. We provide a refined analysis of model-based risk-sensitive Q-value iteration (MB-RS-QVI), a plug-in model-based method introduced in prior work, and derive ((varepsilon,δ))-PAC guarantees for both learning the optimal (Q)-value function and an (varepsilon)-optimal policy. Our bounds improve the exponential dependence on the effective horizon (1/(1-γ)) compared with the best existing guarantees for this setting. In particular, they match the existing lower bounds in their exponential dependence on (|β|/(1-γ)), as well as in (S), (A), (varepsilon), and (|β|), up to logarithmic factors. Consequently, our analysis removes the exponential gap between the previously known upper and lower bounds, leaving only a polynomial gap in the effective horizon.