Research map / Bandits and online learning / Online convex optimization and games
Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting
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 a log-barrier OMD algorithm and a detect-switch BOBW algorithm for multi-armed bandits with heavy-tailed, possibly negative losses, achieving high-probability near-optimal adversarial and logarithmic stochastic regret without the truncated non-negative losses assumption.
Problem
Multi-armed bandits with heavy-tailed losses (unbounded, possibly negative, bounded (1+v)-th raw moments) in the adversarial regime and best-of-both-worlds setting, where prior optimal results needed a strong truncated non-negative losses assumption and only gave expected regret.
Approach
Replace the Tsallis entropy regularizer with a log-barrier regularizer, which tolerates negative losses and lets the trimming threshold scale with K rather than with action probabilities, removing the assumption; add increasing learning rates and simplex truncation for high-probability bounds, and embed this in the Bubeck-Slivkins detect-switch framework with a trimmed mean estimator for BOBW.
Key results
- OMD-LB-HT achieves high-probability adversarial regret O(u K^{v/(1+v)} T^{1/(1+v)} (log T)^2 log(T/ζ)) without Assumption 2.
- SAO-HT achieves adversarial regret O~(u K^{v/(1+v)} T^{1/(1+v)}) and stochastic regret O(K log K (u^{1+1/v}/Δ)^{1/v} log T) with high probability.
- Implies the first high-probability BOBW guarantee under pure local differential privacy for bounded losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Tsallis entropy with a log-barrier regularizer and remove the truncated non-negative losses assumption | OMD-LB-HT for adversarial heavy-tailed MAB · Adversarial heavy-tailed MAB | regret guarantee | Helped |
| Add the detect-switch framework to OMD-LB-HT | SAO-HT · Adversarial and stochastic heavy-tailed MAB | regret guarantee | Helped |
Limitations
- Gap-dependent term is K(1/Δ)^{1/v} rather than the optimal sum over arms, due to the detect-switch framework.
- Algorithms and bounds only cover moment order 1+v in (1,2]; higher moments do not improve bounds.
- Requires known heavy-tail parameters u and v and horizon T; adaptive case not covered.
Experimental setup
Metrics: pseudo-regret high-probability regret bound expected regret bound
Baselines: HTINF AdaTINF RobustUCB AdaR-UCB uniINF
Builds on: Bubeck & Slivkins 2012 detect-switch (SAO) Lee et al. 2020 log-barrier with increasing learning rates Huang et al. 2022 HTINF Bubeck et al. 2013 robust UCB
Closest papers by meaning
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.93)
- uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs (ICLR 2025 · similarity 0.91)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.90)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.90)
- Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.89)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
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.