# Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning

arXiv: https://arxiv.org/abs/2203.03110 · HTML: https://mlsanity.com/paper/2203.03110/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 7 Mar 2022.

## Builds on (most cited first, 22 of 22)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Multiple Descent: Design Your Own Generalization Curve](https://mlsanity.com/paper/2008.01036/) (2020)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization](https://mlsanity.com/paper/2002.11080/) (2020)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models](https://mlsanity.com/paper/2002.04725/) (2020)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Entropic Risk Measure in Policy Search](https://mlsanity.com/paper/1906.09090/) (2019)
- [Epistemic Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/1906.06273/) (2019)
- [Convergence and Alignment of Gradient Descent with Random Backpropagation Weights](https://mlsanity.com/paper/2106.06044/) (2021)
- [On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization](https://mlsanity.com/paper/1809.11083/) (2018)
- [Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly](https://mlsanity.com/paper/1904.09635/) (2019)
- [Meta Learning in the Continuous Time Limit](https://mlsanity.com/paper/2006.10921/) (2020)
- [Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm](https://mlsanity.com/paper/2103.09847/) (2021)
- [Human Decision-Making under Limited Time](https://mlsanity.com/paper/1610.01698/) (2016)
- [Exponential error rates of SDP for block models: Beyond Grothendieck's inequality](https://mlsanity.com/paper/1705.08391/) (2017)

## Built on by (most cited first, 2 of 2)

- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Taming Equilibrium Bias in Risk-Sensitive Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2405.02724/) (2024)

## Abstract (arXiv)

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.