Q-Learning with Fine-Grained Gap-Dependent Regret

• URL: http://arxiv.org/abs/2510.06647v1
• Date: Wed, 08 Oct 2025 05:02:16 GMT
• Title: Q-Learning with Fine-Grained Gap-Dependent Regret
• Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue,
• Abstract summary: Existing model-free algorithms achieve minimax worst-case regret, but their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps.<n>We establish fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms.
• Score: 13.370933509246568
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study fine-grained gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. Existing model-free algorithms achieve minimax worst-case regret, but their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps. We address this limitation by establishing fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms. In the UCB-based setting, we 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 UCB-Hoeffding (Jin et al., 2018). To highlight the generality of this framework, we 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. In the non-UCB-based setting, we revisit the only known algorithm AMB, and identify two key issues in its algorithm design and analysis: improper truncation in the $Q$-updates and violation of the martingale difference condition in its concentration argument. We propose 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 AMB.

Related papers

• Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem [15.493230983626281]
  Several optimism-based bandit algorithms -- including UCB, UCB-V, linear UCB, and finite-arm GP-UCB -- achieve logarithmic regret using proofs that, despite superficial differences, follow essentially the same structure.<n>This note isolates the minimal ingredients behind these analyses: a single high-probability concentration condition on the estimators, after which logarithmic regret follows from two short deterministic lemmas describing radius collapse and optimism-forced deviations.<n>The framework yields unified, near-minimal proofs for these classical algorithms and extends naturally to many contemporary bandit variants.
  arXiv  Detail & Related papers  (2025-12-20T16:11:55Z)
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
  Upper Confidence Bound (UCB) algorithms are a widely-used class of sequential algorithms for the $K$-armed bandit problem.<n>We show that the Lai-Robbins regret formula is exact if and only if the sub-optimality gaps exceed the order $sigmasqrtKlog T/T$.<n>We also show that its maximal regret deviates from the minimax regret by a logarithmic factor, and therefore settling its strict minimax optimality in the negative.
  arXiv  Detail & Related papers  (2024-12-09T01:14:02Z)
• Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition [4.895986534376972]
  We study the gap-dependent bounds of two important algorithms for on-policy Q-learning for finite-horizon episodic Markov Decision Processes (MDPs)<n>We develop a novel error decomposition framework to prove gap-dependent regret bounds of UCB-Advantage and Q-EarlySettled-Advantage that are logarithmic in $T$.<n>We also establish the gap-dependent bound for the policy switching cost of UCB-Advantage and improve that under the worst-case MDPs.
  arXiv  Detail & Related papers  (2024-10-10T03:19:46Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  Best arm identification problem elegantly amalgamates regret minimization and BAI. Agent's goal is to identify the best arm with a prescribed confidence level. Double KL-UCB algorithm achieves optimality as the confidence level tends to zero.
  arXiv  Detail & Related papers  (2024-09-27T16:46:02Z)
• Scale-free Adversarial Reinforcement Learning [17.276918882127728]
  This paper initiates the study of scale-free learning in Markov Decision Processes (MDPs) We design a generic algorithmic framework, underlineScale underlineClipping underlineBound (textttSCB) We achieve the first minimax optimal expected regret bound and the first high-probability regret bound in scale-free adversarial MABs.
  arXiv  Detail & Related papers  (2024-03-01T19:21:10Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  We introduce a new variant of the Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
  arXiv  Detail & Related papers  (2023-01-19T18:24:08Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  We design and analyze the BoBW-lil'UCB$(gamma)$ algorithm. We show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives. We also show that BoBW-lil'UCB$(gamma)$ outperforms a competitor in terms of the time complexity and the regret.
  arXiv  Detail & Related papers  (2021-10-16T17:52:32Z)
• Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
  gradient-based Bi-Level Optimization (BLO) methods have been widely applied to handle modern learning tasks. There are almost no gradient-based methods able to solve BLO in challenging scenarios, such as BLO with functional constraints and pessimistic BLO. We provide Bi-level Value-Function-based Sequential Minimization (BVFSM) to address the above issues.
  arXiv  Detail & Related papers  (2021-10-11T03:13:39Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms [8.099977107670918]
  Upper Confidence Bound (UCB) is an optimistic-based MAB algorithm. This paper provides new results on the arm-sampling behavior of UCB. It also provides the first process-level characterization of the MAB problem under UCB.
  arXiv  Detail & Related papers  (2021-06-03T20:52:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.