Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path
This addresses risk avoidance in real-world tasks like autonomous driving and clinical planning, offering theoretical guarantees, but it is incremental as it builds on existing risk-sensitive RL frameworks.
The paper tackles the problem of risk-sensitive reinforcement learning by introducing Iterated CVaR RL, which maximizes tail rewards at each step to avoid catastrophic outcomes, and provides algorithms with nearly matching upper and lower bounds on regret and policy identification, as well as constant bounds for a limiting case called Worst Path RL.
In this paper, we study a novel episodic risk-sensitive Reinforcement Learning (RL) problem, named Iterated CVaR RL, which aims to maximize the tail of the reward-to-go at each step, and focuses on tightly controlling the risk of getting into catastrophic situations at each stage. This formulation is applicable to real-world tasks that demand strong risk avoidance throughout the decision process, such as autonomous driving, clinical treatment planning and robotics. We investigate two performance metrics under Iterated CVaR RL, i.e., Regret Minimization and Best Policy Identification. For both metrics, we design efficient algorithms ICVaR-RM and ICVaR-BPI, respectively, and provide nearly matching upper and lower bounds with respect to the number of episodes $K$. We also investigate an interesting limiting case of Iterated CVaR RL, called Worst Path RL, where the objective becomes to maximize the minimum possible cumulative reward. For Worst Path RL, we propose an efficient algorithm with constant upper and lower bounds. Finally, our techniques for bounding the change of CVaR due to the value function shift and decomposing the regret via a distorted visitation distribution are novel, and can find applications in other risk-sensitive RL problems.