Metraipolis › archive › dc_5418dffcb483
Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning — arXiv:2610.04752
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.04752
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:32:12.428Z
- SHA-256 of the archived text
e8962f1902e8d1a57699c6ed221ca609600f6e3bee724abf728916371428be13- Stable URL of this page
https://metraipolis.com/documento/dc_5418dffcb483
How to cite
Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning — arXiv:2610.04752 — arXiv, https://arxiv.org/abs/2610.04752 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5418dffcb483 (Metraipolis archive dc_5418dffcb483, sha256 e8962f1902e8d1a57699c6ed221ca609600f6e3bee724abf728916371428be13)
BibTeX
@misc{dc5418dffcb483,
title = {Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning — arXiv:2610.04752},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.04752},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5418dffcb483; sha256 e8962f1902e8d1a57699c6ed221ca609600f6e3bee724abf728916371428be13},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.04752. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno). Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2610.04752 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T05:27:05.981Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).