Research map / Bandits and online learning / Multi-armed bandits
Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards
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 MED-PE, an experimental-design-guided phased elimination algorithm with a robust (truncated-mean) regression estimator for linear bandits with heavy-tailed rewards, improving upper and lower regret bounds on dimension dependence.
Problem
Minimax regret of stochastic linear bandits when rewards have only a finite (1+ε)-absolute central moment (heavy-tailed noise, ε in (0,1]); prior upper and lower bounds did not match and the known lower bound relied on a dimension-scaled moment.
Approach
A moment-based experimental design that minimizes the (1+ε)-moment of a regularized, robustly estimated least-squares estimator over active arms, used inside phased elimination; also a new lower bound with constant moment that shows d^{2ε/(1+ε)} dependence and a geometry-dependent upper bound.
Key results
- Upper bound Õ(d^{(1+3ε)/(2(1+ε))} T^{1/(1+ε)}) for general action sets, improving prior d T^{1/(1+ε)}, and Õ(√d (log n)^{ε/(1+ε)} T^{1/(1+ε)}) for finite action sets of size n.
- Lower bound Ω(d^{2ε/(1+ε)} T^{1/(1+ε)}) under constant (1+ε)-central moment, strictly above the MAB rate d^{ε/(1+ε)} T^{1/(1+ε)}.
- Recovers the known optimal sqrt(d)-type rate at ε=1 and gives sublinear regret for Matern kernel bandits for all ε in (0,1].
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MED-PE instead of the prior general-action-set approach | Heavy-tailed linear bandits · General linear bandits | regret upper bound: dT^{\frac{1}{1 + \epsilon}} -> d^{\frac{1 + 3\epsilon}{2(1 +\epsilon)}} T^{\frac{1}{1 + \epsilon}} | Helped |
| use MED-PE instead of the prior finite-action-set approach | Heavy-tailed linear bandits · Finite action set, |A| = n | regret upper bound: \sqrt{d \log n}T^{\frac{1}{1 + \epsilon}} -> \sqrt{d} (\log n)^{\frac{\epsilon}{1 + \epsilon}}T^{\frac{1}{1 + \epsilon}} | Helped |
| use the kernelized MED-PE bound instead of the prior Matérn-kernel bound | Heavy-tailed kernel bandits · Matérn kernel | regret upper bound: T^{\frac{2+\epsilon}{2(1 + \epsilon)}+\frac{d}{2\nu + d}} -> T^{1 - \frac{\epsilon}{1 + \epsilon} \frac{2 \nu}{2 \nu + d | Helped |
| use the new dimension-dependent lower-bound construction instead of the multi-armed-bandit-rate construction | Heavy-tailed linear bandits · General linear bandits | regret lower bound: d^{\frac{\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsilon}} -> \Omega(d^{\frac{2\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsil | Helped |
| use the action-set geometry in the MED-PE design for the simplex | MED-PE · Simplex action set | regret upper bound: d^{\frac{1 + 3\epsilon}{2(1 +\epsilon)}}T^{\frac{1}{1 + \epsilon}} -> \otil(d^{\frac{\epsilon}{1 + \epsilon}} T^{\frac{1 | Helped |
| use the action-set geometry in the MED-PE design for an l_p-norm ball with p ≤ 1 + ε | MED-PE · l_p-norm ball, p ≤ 1 + ε | regret upper bound: \otil(d^{\frac{1 + 3\epsilon}{2(1 +\epsilon)}} T^{\frac{1}{1 + \epsilon}}) -> \otil(d^{\frac{2\epsilon}{1 + \epsilon}} T | Helped |
Surprising findings
- The prior dT^{1/(1+ε)} lower bound was obtained with moment O(d), so it was misinterpreted as matching known upper bounds under constant moment; under constant moments the best previously provable lower bound was only d^{ε/(1+ε)}T^{1/(1+ε)}.
Limitations
- Gap between the upper bound d^{(1+3ε)/(2(1+ε))} and lower bound d^{2ε/(1+ε)} remains for ε in (0,1).
- Minimax optimality not established for general action sets; the geometry-dependent bound's complexity term is not fully characterized.
- Kernel result does not match the known lower bound except at ε=1 or as ε→0.
Experimental setup
Metrics: cumulative regret (theoretical upper and lower bounds)
Baselines: Medina and Yang (2016) robust linear bandits Shao et al. (2018) heavy-tailed linear bandits Xue et al. (2020) finite-arm heavy-tailed linear bandits Lee et al. (2024) Matern heavy-tailed kernel bandits heavy-tailed MAB (Bubeck et al. 2013)
Builds on: phased elimination robust mean estimation (truncated mean) G-optimal design Catoni M-estimator
Closest papers by meaning
- Nash Regret Guarantees for Linear Bandits (NeurIPS 2023 · similarity 0.93)
- Stochastic Linear Bandits with Parameter Noise (ICML 2026 · similarity 0.92)
- Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards (NeurIPS 2023 · similarity 0.92)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.92)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.90)
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.90)
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.