mlsanityData to 7 Oct 2026

Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents

arXiv 2301.12601 ↗First posted 30 Jan 2023cs.LG cs.AI math.OCcited by 14

Not on the map. Why?

Abstract (arXiv)

The optimized certainty equivalent (OCE) is a family of risk measures that cover important examples such as entropic risk, conditional value-at-risk and mean-variance models. In this paper, we propose a new episodic risk-sensitive reinforcement learning formulation based on tabular Markov decision processes with recursive OCEs. We design an efficient learning algorithm for this problem based on value iteration and upper confidence bound. We derive an upper bound on the regret of the proposed algorithm, and also establish a minimax lower bound. Our bounds show that the regret rate achieved by our proposed algorithm has optimal dependence on the number of episodes and the number of actions.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 16 of its 45 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

16 of 45 references.

References · 16

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2013Risk-sensitive Reinforcement Learningcited by 129
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  9. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
  10. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
  11. 2020Learning Bounds for Risk-sensitive Learningcited by 33
  12. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
4 more
  1. 2019A Wasserstein distance approach for concentration of empirical risk estimatescited by 18
  2. 2020Markov Decision Processes with Recursive Risk Measurescited by 17
  3. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  4. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 5; 2026: 1.

14 papers.

Sort:

By area:

  1. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  2. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  3. 2025Conformal Risk Training: End-to-End Optimization of Conformal Risk Controlcited by 11
  4. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 7
  5. 2023Risk-sensitive Markov Decision Process and Learning under General Utility Functionscited by 7
  6. 2024Continuous-time Risk-sensitive Reinforcement Learning via Quadratic Variation Penaltycited by 5
  7. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 4
  8. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  9. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  10. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Modelcited by 3
  11. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalentscited by 1
  12. 2024Risk-Aware Decision Making in Restless Bandits: Theory and Algorithms for Planning and Learningcited by 0
2 more
  1. 2025Tail Distribution of Regret in Optimistic Reinforcement Learningcited by 0
  2. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalentscited by 0