Research map / Bandits and online learning / Online convex optimization and games

Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems

NeurIPS 2025 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that FTPL with Fréchet(shape 2) perturbations and geometric resampling achieves O(sqrt(nm)(sqrt(d log d)+m^{5/6})) adversarial regret and logarithmic stochastic regret for m-set semi-bandits, approaching best-of-both-worlds.

Problem

Computing arm-selection probabilities for FTRL in m-set semi-bandits is costly; FTPL avoids this but its regret analysis is hard, so it was unknown whether FTPL achieves near-optimal adversarial and best-of-both-worlds regret for m-set semi-bandits.

Approach

Analyze FTPL with Fréchet(α=2) perturbations via a FTRL-style decomposition extended to action sets lacking interior points, bounding the ratio of perturbation-density terms with new monotonicity and tail lemmas, and combine with geometric resampling for unbiased loss estimates.

Key results

• Adversarial pseudo-regret bound O(sqrt(nm)(sqrt(d log d)+m^{5/6})) for FTPL with Fréchet perturbations and eta_t=1/sqrt(t).
• Stochastic regret O(sum_i log(n)/Delta_i) plus an additive term under a unique-optimal-action assumption.
• Lower-bound constructions show the log(d) and m^{5/6}/d^{1/2} factors are unavoidable for the current term-wise analysis.

Surprising findings

• The paper's stated conclusions were revised: an earlier monotonicity claim was found incorrect, adding log(d) and m^{5/6}/d^{1/2} factors to the adversarial bound.

Limitations

• Regret bound has extra log(d) and m^{5/6} factors relative to the optimal O(sqrt(nmd)).
• Stochastic result requires a unique optimal action (at most m arms with zero gap) and an additive term larger than desired.
• Only the m <= d/2 regime is covered.

Experimental setup

Datasets: synthetic Bernoulli loss sequences (d=10, m=5, n=10^7)

Benchmarks: synthetic m-set semi-bandit (d=10, m=5, n=10^7)

Metrics: pseudo-regret

Baselines: COMBUCB Thompson Sampling EXP2 LOGBARRIER hybrid regularizer FTRL

Builds on: Follow-the-Regularized-Leader FTPL with Fréchet perturbations for MAB (Jin et al.) geometric resampling Tsallis-INF self-bounding constraint technique

Closest papers by meaning

• Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality (ICML 2026 · similarity 0.94)
• Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems (NeurIPS 2025 · similarity 0.92)
• Geometric Resampling in Nearly Linear Time for Follow-the-Perturbed-Leader with Best-of-Both-Worlds Guarantee in Bandit Problems (ICML 2025 · similarity 0.91)
• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.90)
• Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.89)
• Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.89)