Q-Learning with Fine-Grained Gap-Dependent Regret

A new study by Haochen Zhang and colleagues establishes the first fine-grained, gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes, addressing a long-standing limitation in the field [1]. The work, posted on arXiv and accepted as a poster at ICLR 2026, tackles a core problem in reinforcement learning theory: while existing model-free algorithms achieve minimax worst-case regret, their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps [1][3]. The authors develop a novel analytical framework that explicitly separates the analysis of optimal and suboptimal state-action pairs, yielding the first fine-grained regret upper bound for the UCB-Hoeffding algorithm introduced by Jin et al. in 2018 [1][4]. To demonstrate the framework's generality, the researchers introduce ULCB-Hoeffding, a new UCB-based algorithm inspired by AMB (Xu et al., 2021) but with a simplified structure, which enjoys fine-grained regret guarantees and empirically outperforms AMB [1][4]. In the non-UCB setting, the study revisits AMB, the only previously known algorithm in this category, and identifies two key issues in its design and analysis: improper truncation in the Q-updates and violation of the martingale difference condition in its concentration argument [1][3]. The team proposes a refined version of AMB that addresses these issues, establishing the first rigorous fine-grained gap-dependent regret for a non-UCB-based method, with experiments demonstrating improved performance over the original [1][4]. The paper was first submitted on 8 October 2025 and revised on 15 June 2026 [1].