---
title: "Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.04307v1"
permalink: "https://feed.astralor.com/items/itm_b94a9fa3df11bd0b9a1ec653"
published: "2026-11-03T04:38:17.000Z"
score: 55
channel: "ai"
tags: ["Nearly Linear-Time Follow-the-Perturbed-Leader","Weakly Observable Graph","Bandits","Follow-the-Perturbed-Leader","FTPL"]
---

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

## At a glance

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. T…

## Key points

- 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, den…

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_b94a9fa3df11bd0b9a1ec653