mlsanityData to 14 Oct 2026

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

arXiv 2610.06931 ↗First posted 3 Oct 2026cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

28 of 57 references.

Closest ancestors · 6

Same direction, newest first

  1. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents20 May
  2. 2026Tight Sample Complexity Bounds for Entropic Best Policy Identification13 May
  3. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents23 Oct
  4. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model30 May
  5. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model11 Mar
  6. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents10 Mar

Other references · 22

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  4. 2014Algorithms for CVaR Optimization in MDPscited by 99
  5. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  6. 2015Policy Gradient for Coherent Risk Measurescited by 76
  7. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 58
  8. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  9. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 43
  10. 2022One Risk to Rule Them All: A Risk-Sensitive Perspective on Model-Based Offline Reinforcement Learningcited by 23
  11. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 22
  12. 2020Risk-Aware High-level Decisions for Automated Driving at Occluded Intersections with Reinforcement Learningcited by 20
10 more
  1. 2020Markov Decision Processes with Recursive Risk Measurescited by 18
  2. 2023On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processescited by 18
  3. 2023Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalentscited by 15
  4. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 14
  5. 2022A Policy Gradient Algorithm for the Risk-Sensitive Exponential Cost MDPcited by 13
  6. 2024RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learningcited by 9
  7. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 8
  8. 2024Truncated Variance Reduced Value Iterationcited by 8
  9. 2025Efficient Risk-sensitive Planning via Entropic Risk Measurescited by 7
  10. 2024Mitigating optimistic bias in entropic risk estimation and optimizationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Provably Efficient Sample Complexity for Robust CMDP
  2. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
  3. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
  4. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
  5. 2025Improving Reinforcement Learning Sample-Efficiency using Local Approximation
  6. 2026Reinforcement Learning for Exponential Utility: Algorithms and Convergence in Discounted MDPs
  7. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs
  8. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies