Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive
  Reinforcement Learning
  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 the 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.
