Research map / Bandits and online learning / Multi-armed bandits
A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis
Tor Lattimore
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 |
|---|---|---|---|
| Use a median-of-means UCB with optimistic estimates of both mean and variance, assuming a known finite kurtosis bound | \widehat{MM} scale-free UCB · Finite-armed stochastic bandits with bounded kurtosis | asymptotic regret: \limsup_{n\to\infty} \frac{\mathcal R_n}{\log(n)} \leq C\sum_{i:\Delta_i > 0} \Delta_i \left(\kappa - 1 + \frac{\sigma^2 | Improved |
| Require consistency across subgaussian classes with arbitrary scale | Bandit strategies · Non-trivial subgaussian bandits | logarithmic regret | Hurt |
| Use finite kurtosis as the distributional assumption instead of a known payoff scale or variance parameter | Scale-free bandit learning · Non-parametric stochastic bandits | asymptotic regret: logarithmic regret | Improved |
| Replace median-of-means with Catoni's estimator | \widehat{MM} scale-free UCB · Finite-armed stochastic bandits with bounded kurtosis | regret constants | Improved |
Closest papers by meaning
- Refining the Confidence Level for Optimistic Bandit Strategies (JMLR 2018 · similarity 0.90)
- Maximum Average Randomly Sampled: A Scale Free and Non-parametric Algorithm for Stochastic Bandits (NeurIPS 2023 · similarity 0.89)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)
- Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs (NeurIPS 2018 · similarity 0.89)
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.87)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · 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.
