Research map / Bandits and online learning / Online convex optimization and games
Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
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 HVT-UCB, a one-pass Huber-loss bandit algorithm built on online mirror descent that reduces per-round cost from O(t log T) to O(1) while keeping the optimal and variance-aware regret of adaptive Huber regression for heavy-tailed linear bandits.
Problem
Heavy-tailed noise with only (1+ε)-finite moments in stochastic linear bandits; existing adaptive Huber regression methods need storing all past data and a full pass each round, which is computationally infeasible at scale.
Approach
Replace the full-batch adaptive Huber regression with a one-step online mirror descent update using a local-norm regularizer, plus a recursive normalization factor sigma_t and robustification parameter tau_t that keep normal data in the quadratic region of the Huber loss, so that a single-pass estimator attains the same estimation error and regret as the offline method.
Key results
- Achieves regret Õ(d T^{1/(1+ε)}) with per-round cost O(1), matching the lower bound up to log factors, and instance-dependent regret Õ(d T^{(1-ε)/(2(1+ε))} sqrt(sum nu_t^2) + ...) matching HEAVY-OFUL.
- In synthetic experiments with Student t noise and Gaussian noise, HVT-UCB achieves regret comparable to HEAVY-OFUL with a reported speedup exceeding 800x.
- Under Gaussian noise, HVT-UCB stays competitive with OFUL while the truncation-based CRTM performs suboptimally.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use one-pass OMD Huber updates instead of full-batch adaptive Huber regression | Heavy-tailed linear bandits · Heavy-tailed linear bandits, instance-dependent bound | per-round computational cost: \O(t\log T) -> \O(1) | Helped |
| use one-pass OMD Huber updates instead of full-batch adaptive Huber regression | Heavy-tailed linear bandits · Heavy-tailed linear bandits, instance-dependent bound | regret | No clear effect |
| use hvtucb instead of OFUL | Heavy-tailed linear bandits under Student's t noise · Student's t noise | cumulative regret | Helped |
| use hvtucb instead of CRTM | Linear bandits under Gaussian noise · Gaussian noise | cumulative regret | Helped |
Limitations
- Instance-dependent regret and the O(1) cost require knowledge of the moment bound nu_t (or a general bound nu) for each round.
- Experiments are limited to small synthetic settings with d=2 and T=18000; the projection step adds O(d^3) cost per round.
- Extensions to linear MDPs and adaptive control are discussed but not established.
Experimental setup
Benchmarks: synthetic linear bandit with Student t noise (df=2.1) synthetic linear bandit with Gaussian noise
Metrics: cumulative regret computational time
Baselines: OFUL CRTM CRMM HEAVY-OFUL
Builds on: Heavy-OFUL (adaptive Huber regression) OFUL OL2M/logistic bandit ONS Online Mirror Descent
Closest papers by meaning
- No-Regret Algorithms for Heavy-Tailed Linear Bandits (ICML 2016 · similarity 0.93)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.89)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.88)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.87)
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.