Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents
This work addresses risk-sensitive decision-making in reinforcement learning, which is important for applications like finance and robotics, but it appears incremental as it extends existing OCE frameworks to recursive settings with theoretical guarantees.
The authors tackled the problem of risk-sensitive reinforcement learning in episodic Markov decision processes by proposing a new formulation based on recursive optimized certainty equivalents (OCEs) and designing an efficient algorithm using value iteration and upper confidence bounds. They derived an upper regret bound and a minimax lower bound, showing that their algorithm achieves optimal dependence on the number of episodes and actions.
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.