mlsanityData to 14 Oct 2026

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

arXiv 2506.00286 ↗First posted 30 May 2025cs.LG cs.AI math.OCcited by 5

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

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.

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.

Builds on

27 of 69 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model11 Mar
  2. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents10 Mar

Other references · 25

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

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026Tight Sample Complexity Bounds for Entropic Best Policy Identificationcited by 1
  2. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalentscited by 1
  3. 2026Risk-Aware General-Utility Markov Decision Processescited by 0
  4. 2026Long-Term Sequential Decision Making under Riskcited by 0
  5. 2026Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Modelcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Risk-averse Total-reward MDPs with ERM and EVaR
  2. 2025Provably Efficient Sample Complexity for Robust CMDP
  3. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  4. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning
  5. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
  6. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysis
  7. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
  8. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation