Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs
Han Zhong, Jiayi Huang, Lin Yang, Liwei Wang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Wrap with mean-of-medians reward filtering | SupBMM / SupBTC · Linear bandit, Student's t df = 1.02 | cumulative regret | Improved |
| Wrap with mean-of-medians reward filtering | SupBMM / SupBTC · Linear bandit, Student's t df = 3 | cumulative regret | No clear effect |
| Wrap with mean-of-medians reward filtering | SupBMM / SupBTC · Super heavy-tailed bandit, df = 1 | cumulative regret | Improved |
| Wrap with mean-of-medians reward filtering | SupBMM / SupBTC · Super heavy-tailed bandit, df = 0.5 | cumulative regret | Improved |
| Use SupBTC as base algorithm instead of SupBMM within the framework (ablation) | Mean-of-medians framework · Super heavy-tailed bandit | cumulative regret | Improved |
| Apply mean-of-medians wrapper to TOFU instead of MENU (ablation) | Mean-of-medians framework · Student's t df = 3 and 1.02 | cumulative regret | Hurt |
| Add mean-of-medians wrapper to MoM, CRT, MENU, TOFU (ablation) | Baseline bandit algorithms · Student's t df = 1.02 | estimation error of theta | Improved |
| Add mean-of-medians wrapper to baselines (ablation) | Baseline bandit algorithms · Student's t df = 3 | estimation error of theta | No clear effect |
| Vary epsilon of the estimator in [0.3, 0.8] (ablation) | SupBTC_mom · Student's t df = 1 | mean regret over 100 paths | No clear effect |
| Vary bound parameter v over three values (ablation) | SupBMM_mom and SupBTC_mom · Student's t df = 0.5 | mean and median regret over 500 paths | No clear effect |
Closest papers by meaning
- Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update (ICML 2025 · similarity 0.93)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.88)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.88)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.88)
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.
