arXiv:2611.04307v1 stat.ML

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

Jongyeong Lee, Hyundam Yoo

제출 2026-11-04

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.04307v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.