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 𝒪̃(δ*1/3 T2/3) regret for adversarial regimes as well as 𝒪̃(δ* log T / Δmin2) 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 Θ(T2/3) can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.
Related
- Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
BibTeX
@misc{lee2026nearly,
title = {{Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits}},
author = {Jongyeong Lee and Hyundam Yoo},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04307},
eprint = {2611.04307},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04307},
}
RIS
TY - UNPB
TI - Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
AU - Jongyeong Lee
AU - Hyundam Yoo
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04307
UR - https://arxiv.org/abs/2611.04307
AB - 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 𝒪̃(δ_*^1/3 T^2/3) regret for adversarial regimes as well as 𝒪̃(δ_* 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.
ER -