mlsanityData to 14 Oct 2026

Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning

arXiv 2610.04752 ↗First posted 3 Oct 2026stat.ML cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study model-free online reinforcement learning (RL) for episodic tabular Markov decision processes, focusing on both gap-dependent regret and policy switching cost. While fine-grained gap-dependent analysis has been established for model-free RL algorithms using Hoeffding-type exploration bonuses, such results for model-free algorithms with variance-based exploration bonuses remain unknown, despite their superior worst-case and coarse-grained gap-dependent guarantees. In this paper, we resolve this open problem by establishing the first fine-grained gap-dependent regret upper bound for UCB-Bernstein+, a refined UCB-Bernstein algorithm, in variance-aware model-free online RL. Moreover, by integrating a stage-wise policy update design into our fine-grained framework and using refined variance-based bonuses, we achieve the best-known gap-dependent local switching cost to date. In addition, our analysis yields improved worst-case guarantees for both regret and local switching cost over the original UCB-Bernstein algorithm. Numerical experiments further demonstrate that UCB-Bernstein+ achieves favorable empirical performance in both regret and local switching cost.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 3 of its 42 references that are in the map. First posted on arXiv 3 Oct 2026.

Builds on

3 of 42 references.

Closest ancestors · 1

Same direction, newest first

  1. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation23 Feb

Other references · 2

  1. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  2. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Q-Learning with Fine-Grained Gap-Dependent Regret
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
  5. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  7. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction