Research map / Bandits and online learning / Online convex optimization and games
Geometric Resampling in Nearly Linear Time for Follow-the-Perturbed-Leader with Best-of-Both-Worlds Guarantee in Bandit Problems
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.
Proposes Conditional Geometric Resampling (CGR), which conditions the perturbation resampling in FTPL bandit policies so the average per-round cost drops from O(K^2) to O(K log K) while keeping best-of-both-worlds regret.
Problem
Follow-the-Perturbed-Leader (FTPL) for K-armed bandits needs geometric resampling to estimate inverse arm probabilities, costing O(K^2) per round on average, which is worse than FTRL and limits its practical use despite achieving best-of-both-worlds guarantees.
Approach
Resample the perturbation only from the conditional event that is a necessary condition for the chosen arm to be pulled (the chosen arm's perturbation is the largest among arms no worse than it), giving an unbiased estimator via Mt/P(At) with O(K) cost per resampling and only O(log K) expected resamplings; a biased variant caps resamplings at (K∨4) log t for Fréchet shape-2 perturbations.
Key results
- CGR II-unbiased and II-biased have median resampling count of one, while original GR's number of resamplings is sometimes prohibitively large (Figure 1, K=32).
- Theory: CGR variants achieve E[Mt] of O(log K) and per-round average complexity O(K log K), versus O(K^2) for original GR.
- Runtime experiments (K from 2 to 128, 10000 rounds) show FTPL CGR runtime stays small as K grows while FTPL GR grows sharply; FTPL CGR II regret is close to T-INF IW and sometimes better.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace geometric resampling with conditional geometric resampling | FTPL · K-armed bandits | average complexity per round: O(K2) -> O(K log K) | Helped |
| replace GR with CGR | FTPL · stochastically constrained adversarial setting | pseudo-regret | Helped |
| cap conditional geometric resampling at (K ∨ 4) log t | FTPL with CGR II · K-armed bandits, Fréchet distribution with shape 2 | regret: O(√KT); O(∑i≠i∗ log T/∆i) | No clear effect |
| use TS-Prod's one-step approximate update instead of the FTPL CGR update | bandit policies · stochastically constrained adversarial setting | pseudo-regret | Hurt |
Surprising findings
- CGR I has faster runtime than CGR II despite a larger number of resamplings, because its conditioning step only requires a swap.
Limitations
- CGR II requires explicit CDF F and inverse F^{-1}, limiting generality.
- Biased CGR II worst-case guarantee of BOBW proven only for Fréchet shape-2 perturbations; general case needs heavy case-by-case analysis.
- CGR II-based FTPL regret remains worse than Tsallis-INF with reduced-variance estimator.
Experimental setup
Benchmarks: simulated stochastically constrained adversarial bandit environments simulated stochastic bandit environments
Metrics: pseudo-regret number of resampling runtime (sec)
Baselines: FTPL with geometric resampling (GR) Tsallis-INF IW Tsallis-INF RV TS-Prod
Builds on: Follow-the-Perturbed-Leader geometric resampling (Neu & Bartók 2016) Tsallis-INF Fréchet-type perturbation FTPL (Honda et al. 2023; Lee et al. 2024)
Closest papers by meaning
- Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems (NeurIPS 2025 · similarity 0.91)
- Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems (NeurIPS 2025 · similarity 0.90)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.87)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.87)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.87)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.