# Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents

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

## Key facts

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

## Builds on (most cited first, 16 of 16)

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Learning Bounds for Risk-sensitive Learning](https://mlsanity.com/paper/2006.08138/) (2020)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [A Wasserstein distance approach for concentration of empirical risk estimates](https://mlsanity.com/paper/1902.10709/) (2019)
- [Markov Decision Processes with Recursive Risk Measures](https://mlsanity.com/paper/2010.07220/) (2020)
- [Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds](https://mlsanity.com/paper/2210.14051/) (2022)
- [Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Design](https://mlsanity.com/paper/2211.10815/) (2022)

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

- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [Conformal Risk Training: End-to-End Optimization of Conformal Risk Control](https://mlsanity.com/paper/2510.08748/) (2025)
- [Continuous-time Risk-sensitive Reinforcement Learning via Quadratic Variation Penalty](https://mlsanity.com/paper/2404.12598/) (2024)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)
- [Risk-sensitive Markov Decision Process and Learning under General Utility Functions](https://mlsanity.com/paper/2311.13589/) (2023)
- [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)
- [Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2402.18159/) (2024)
- [Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes](https://mlsanity.com/paper/2404.00099/) (2024)
- [Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2510.20199/) (2025)
- [Tail Distribution of Regret in Optimistic Reinforcement Learning](https://mlsanity.com/paper/2511.18247/) (2025)
- [On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2605.21763/) (2026)
- [Risk-Aware Decision Making in Restless Bandits: Theory and Algorithms for Planning and Learning](https://mlsanity.com/paper/2410.23029/) (2024)
- [Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2610.06931/) (2026)

## 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.