Research map / Bandits and online learning / Online convex optimization and games
uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs
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 uniINF, a parameter-free best-of-both-worlds FTRL algorithm with log-barrier regularizer for heavy-tailed multi-armed bandits, achieving near-optimal regret in both stochastic and adversarial settings without knowing alpha or sigma.
Problem
Heavy-tailed multi-armed bandits where loss moments (sigma, alpha) are unknown and the environment may be stochastic or adversarial; prior methods either need known parameters or fail in adversarial settings.
Approach
Uses FTRL with a log-barrier regularizer whose learning rate auto-balances a Bregman divergence term against a shift term, combined with adaptive skipping-clipping of heavy-tailed losses and a refined log-barrier analysis that gives (1-x_i)^2 factors excluding the optimal arm, plus a stopping-time argument for logarithmic stochastic regret.
Key results
- Adversarial regret of Õ(σ K^{1-1/α} T^{1/α}), matching the instance-independent lower bound up to log factors.
- Stochastic regret O(K (σ^α/Δ_min)^{1/(α-1)} log T · log(σ^α/Δ_min)), matching the instance-dependent lower bound up to logarithmic factors when gaps are similar.
- First parameter-free algorithm achieving best-of-both-worlds guarantees for heavy-tailed MABs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use uniINF without prior knowledge of the heavy-tail parameters | uniINF · Stochastic HTMAB | regret | Helped |
| Use uniINF without prior knowledge of the heavy-tail parameters | uniINF · Adversarial HTMAB | regret | Helped |
Limitations
- Extra logarithmic factors in the bounds.
- Dependence on the sub-optimal gaps is improvable when some gaps are much smaller than others.
- Relies on the truncated non-negative loss assumption for the optimal arm and unique best arm assumption in stochastic settings.
Experimental setup
Metrics: pseudo-regret
Baselines: HTINF OptHTINF AdaTINF AdaR-UCB RobustUCB Robust MOSS APE^2 SAO-HT
Builds on: HTINF INF Tsallis-INF RobustUCB
Closest papers by meaning
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.87)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays (NeurIPS 2026 · similarity 0.86)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.86)
- A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond (NeurIPS 2025 · 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.