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

DevFeed: [Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits](<https://devfeed.tech/articles/nearly-linear-time-follow-the-perturbed-leader-for-weakly-observable-graph-bandits-116927.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.04307>)

Author: Jongyeong Lee, Hyundam Yoo

Published: 2026-11-04T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Mamba](<https://devfeed.tech/topics/mamba.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [adversarial](<https://devfeed.tech/tags/adversarial.md>), [bandits](<https://devfeed.tech/tags/bandits.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [estimator](<https://devfeed.tech/tags/estimator.md>), [graph](<https://devfeed.tech/tags/graph.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [novel](<https://devfeed.tech/tags/novel.md>), [online-learning](<https://devfeed.tech/tags/online-learning.md>), [policy](<https://devfeed.tech/tags/policy.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [time-complexity](<https://devfeed.tech/tags/time-complexity.md>)

## AI overview

For directed weakly observable feedback graphs, the proposed Follow-the-Perturbed-Leader policy is designed for nearly linear expected time while providing guarantees for both adversarial and stochastic regimes. Its graph-based loss estimator combines forced exploration, conditional geometric resampling, and adaptive learning rates with surrogate probabilities. The stated regret is Õ(δ_*^{1/3} T^{2/3}) in adversarial settings and Õ(δ_* log T / Δ_min²) in stochastic settings, where δ_* is the fractional weak domination number and Δ_min denotes the minimum suboptimality gap. The abstract reports these guarantees but provides no further implementation or empirical details.

## Source excerpt

arXiv:2611.04307v1 Announce Type: cross 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}}(\delta_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(\delta_* \log T / \Delta_{\min}^2)$ regret for stochastic regimes, where $\delta_*$ and $\Delta$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $\Theta(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.