Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 22 of its 49 references that are in the map. First posted on arXiv 7 Mar 2022.
Builds on
22 of 49 references.
References · 22
- 2018Is Q-learning Provably Efficient?cited by 485
- 2013Risk-sensitive Reinforcement Learningcited by 129
- 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
- 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
- 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
- 2020Q-learning with Logarithmic Regretcited by 59
- 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
- 2020Multiple Descent: Design Your Own Generalization Curvecited by 44
- 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
- 2020The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalizationcited by 39
- 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
- 2020More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Modelscited by 27
10 more
- 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
- 2019Entropic Risk Measure in Policy Searchcited by 19
- 2019Epistemic Risk-Sensitive Reinforcement Learningcited by 17
- 2021Convergence and Alignment of Gradient Descent with Random Backpropagation Weightscited by 14
- 2018On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimizationcited by 11
- 2019Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustlycited by 11
- 2020Meta Learning in the Continuous Time Limitcited by 10
- 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
- 2016Human Decision-Making under Limited Timecited by 4
- 2017Exponential error rates of SDP for block models: Beyond Grothendieck's inequalitycited by 4
Built on by
Citing papers per year: 2023: 1; 2024: 1.
2 papers.