Poster

Cascaded Gaps: Towards Logarithmic Regret for Risk-Sensitive Reinforcement Learning

Yingjie Fei · Ruitu Xu

Hall E #825

Keywords: [ RL: Planning ] [ RL: Risk Sensitive ] [ Reinforcement Learning ]

[ Abstract ]
[ Paper PDF
Wed 20 Jul 3:30 p.m. PDT — 5:30 p.m. PDT
 
Spotlight presentation: Reinforcement Learning
Wed 20 Jul 10:15 a.m. PDT — 11:45 a.m. PDT

Abstract:

In this paper, we study gap-dependent regret guarantees for risk-sensitive reinforcement learning based on the entropic risk measure. We propose a novel definition of sub-optimality gaps, which we call cascaded gaps, and we discuss their key components that adapt to underlying structures of the problem. Based on the cascaded gaps, we derive non-asymptotic and logarithmic regret bounds for two model-free algorithms under episodic Markov decision processes. We show that, in appropriate settings, these bounds feature exponential improvement over existing ones that are independent of gaps. We also prove gap-dependent lower bounds, which certify the near optimality of the upper bounds.

Chat is not available.