Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits

Abstract

We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)$ regret for stochastic regimes, where $δ_*$ and $Δ$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $Θ(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 3 November 2026

  Nonparametric GARCH: An Iterated Neural Estimator

  Ruizhi Deng, Guohao Shen and Ngai Hang Chan
• arXiv preprint · 4 November 2026

  Discovering like a scientist: Literature-informed dimensionless learning for physical closure of data-driven equations

  Hao Xu, Tianhao Wu and Dongxiao Zhang
• arXiv preprint · 3 November 2026

  Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

  Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov and 1 other
• arXiv preprint · 4 November 2026

  Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

  Huanjian Zhou and Taiji Suzuki
• arXiv preprint · 3 November 2026

  Statistical Machine Learning for Medicinal Plant Leaves Classification

  Jayani P. Gamage and Thiyanga S. Talagala

All new papers in Machine Learning (Statistics)