Research map / Bandits and online learning / Online convex optimization and games
Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations 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.
Revisits FTRL-FTPL duality to give BOBW guarantees for FTPL with asymmetric unbounded Fréchet-type (incl. Laplace-Pareto hybrid) perturbations, and studies whether symmetric Fréchet perturbations can match 1/2-Tsallis entropy, finding positive results only for K=2.
Problem
FTPL policies for multi-armed bandits lag FTRL in analysis: prior BOBW results for FTPL required nonnegative perturbations with monotone f/F, excluding unbounded/asymmetric and hybrid perturbations, and it was unclear whether symmetric Fréchet perturbations (matching 1/2-Tsallis entropy for K=2) can
Approach
Relaxes the monotone f/F condition by showing that when the left tail of the perturbation is lighter than the right tail (tail index beta >= alpha+2), the stability analysis still goes through; applies this to unimodal asymmetric Fréchet/Laplace-Pareto perturbations, and numerically links 1/2-Tsallis entropy to a symmetric Fréchet perturbation, showing BOBW for K=2 but a counterexample for K>=3.
Key results
- FTPL with Laplace-Pareto hybrid perturbation (alpha=2, Gumbel-type left tail) achieves Reg(T) <= 49.25 sqrt(KT) + O(sqrt(K)+K log T) with m=0.23 (adversarial).
- Symmetric Pareto perturbation (shape 2) yields uniformly bounded -phi'/phi^{3/2} and O(sqrt(KT)) adversarial and O(log T) stochastic regret for K=2.
- For K=3 with symmetric Fréchet perturbations, -phi'/phi^{3/2} is not Omega(1) at lambda=(0,c,...,c) with c>=2sqrt(K) (lower bound ~ (c+2)/(K sqrt K)), violating the standard BOBW condition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use asymmetric unbounded Fréchet-type perturbations with α>1 and β≥α+2 | FTPL · Adversarial and stochastic MAB with a unique optimal arm | regret: \gO(\sqrt{KT}) adversarial regret; when α=2, \sum_i \gO(\log T / \Delta_i) stochastic regret | Helped |
| Use Laplace-Pareto hybrid perturbations | FTPL · Adversarial MAB | regret: \mathrm{Reg}(T) \leq 49.25\sqrt{KT} + \gO(\sqrt{K} + K\log T) | Helped |
| Use Laplace-Pareto hybrid perturbations | FTPL · Stochastic MAB with a unique optimal arm | regret: \mathrm{Reg}(T) \leq \sum_{i\ne i^*} \frac{(60m+m^{-1})^2 \log T}{0.035 \Delta_i} + (\frac{2K}{27}+e^2)\log(T+1) + \Thet | Helped |
| Use symmetric Pareto perturbations with shape 2 | FTPL · Adversarial and stochastic MAB, K=2 | regret: \gO(\sqrt{KT}) adversarial regret; \gO(\log T/\Delta_{i: i\ne i^*}) stochastic regret | Helped |
| Extend symmetric Fréchet-type perturbations with tail indices 2 from K=2 to K≥3 | FTPL standard BOBW analysis · Multi-armed bandits, K≥3 | standard BOBW analysis condition: \frac{-\phi_i'(\lambda)}{\phi_i^{3/2}(\lambda)} \geq \tilde{\Omega}(\frac{c+2}{K\sqrt{K}}) \qq{and} \frac{-\phi_i'(\lamb | Hurt |
Surprising findings
- Symmetric Fréchet perturbations violate the key BOBW stability condition for K>=3 even when the suboptimal arms have identical losses, unlike asymmetric or nonnegative ones.
- Density-to-CDF ratio f/F need not be monotone for the BOBW analysis to hold when the left tail is lighter than the right tail, so the nonnegativity assumption is not necessary for K=2.
Limitations
- Dominant regret constant (49.25) is larger than FTRL counterparts; stochastic bound has larger constants.
- The conjectured symmetric perturbation for 1/2-Tsallis is only supported numerically and existence of an i.i.d. realization is not proven.
- Symmetric perturbations fail the key condition for K>=3, so the general BOBW question remains open.
Experimental setup
Metrics: regret bound (adversarial) regret bound (stochastic) ratio -phi'/phi^{3/2} boundedness
Baselines: Exp3 FTPL with Gumbel perturbations FTRL with 1/2-Tsallis entropy FTPL with nonnegative Fréchet perturbations
Builds on: FTPL with Fréchet-type perturbations (Honda et al.) FTRL-FTPL equivalence (discrete choice theory) Tsallis-INF Exp3
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.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.90)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.86)
- On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization (NeurIPS 2026 · similarity 0.86)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.86)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 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.