# Sparsity, variance and curvature in multi-armed bandits

arXiv: https://arxiv.org/abs/1711.01037 · HTML: https://mlsanity.com/paper/1711.01037/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 24 of 24)

- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2107.09572/) (2021)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [Improved Algorithms for Adversarial Bandits with Unbounded Losses](https://mlsanity.com/paper/2310.01756/) (2023)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Scale-free Adversarial Reinforcement Learning](https://mlsanity.com/paper/2403.00930/) (2024)
- [Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2510.17103/) (2025)
- [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025)
- [On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls](https://mlsanity.com/paper/2506.19752/) (2025)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Covariance-adapting algorithm for semi-bandits with application to sparse rewards](https://mlsanity.com/paper/2604.13738/) (2026)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts](https://mlsanity.com/paper/2506.01685/) (2025)
- [Online Budget Allocation with Censored Semi-Bandit Feedback](https://mlsanity.com/paper/2508.05844/) (2025)
- [Stochastic Linear Bandits with Parameter Noise](https://mlsanity.com/paper/2601.23164/) (2026)
- [Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2608.15996/) (2026)

## Abstract (arXiv)

In (online) learning theory the concepts of sparsity, variance and curvature are well-understood and are routinely used to obtain refined regret and generalization bounds. In this paper we further our understanding of these concepts in the more challenging limited feedback scenario. We consider the adversarial multi-armed bandit and linear bandit settings and solve several open problems pertaining to the existence of algorithms with favorable regret bounds under the following assumptions: (i) sparsity of the individual losses, (ii) small variation of the loss sequence, and (iii) curvature of the action set. Specifically we show that (i) for s-sparse losses one can obtain tildeO(√s T)-regret (solving an open problem by Kwon and Perchet), (ii) for loss sequences with variation bounded by Q one can obtain tildeO(√Q)-regret (solving an open problem by Kale and Hazan), and (iii) for linear bandit on an ℓpn ball one can obtain tildeO(√n T)-regret for p ∈ [1,2] and one has tildeOmega(n √T)-regret for p>2 (solving an open problem by Bubeck, Cesa-Bianchi and Kakade). A key new insight to obtain these results is to use regularizers satisfying more refined conditions than general self-concordance