  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.
