Sparsity, variance and curvature in multi-armed bandits

Interior-point polynomial algorithms in convex programming

Y. Nesterov and A. Nemirovski · 1994

Earlier work this paper cites.

The non-stochastic multi-armed bandit problem

P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire · 2002

Earlier work this paper cites.

Competing in the dark: An efficient algorithm for bandit linear optimization

J. Abernethy, E. Hazan, and A. Rakhlin · 2008

Earlier work this paper cites.

Minimax policies for adversarial and stochastic bandits

J.-Y. Audibert and S. Bubeck · 2009

Earlier work this paper cites.

Better algorithms for benign bandits

E. Hazan and S. Kale · 2009

Earlier work this paper cites.

Sparse online learning via truncated gradient

J. Langford, L. Li, and T. Zhang · 2009

Earlier work this paper cites.

A simple multi-armed bandit algorithm with optimal variation-bounded regret

E. Hazan and S. Kale · 2011

Cited alongside, same era.

Regret analysis of stochastic and nonstochastic multi-armed bandit problems

S. Bubeck and N. Cesa-Bianchi · 2012

Cited alongside, same era.

Towards minimax policies for online linear optimization with bandit feedback

S. Bubeck, N. Cesa-Bianchi, and S.M. Kakade · 2012

Cited alongside, same era.

Regret in online combinatorial optimization

J.Y. Audibert, S. Bubeck, and G. Lugosi · 2014

Cited alongside, same era.

Bandit convex optimization: Towards tight bounds

E. Hazan and K. Levy · 2014

Cited alongside, same era.

Efficient learning by implicit exploration in bandit problems with side observations

T. Kocák, G. Neu, M. Valko, and R. Munos · 2014

Cited alongside, same era.

Convex optimization: Algorithms and complexity

S. Bubeck · 2015

Later among the works it cites.

Explore no more: Improved high-probability regret bounds for non-stochastic bandits

G. Neu · 2015

Later among the works it cites.

Learning in games: Robustness of fast convergence

D. Foster, Z. Li, T. Lykouris, K. Sridharan, and E. Tardos · 2016

Later among the works it cites.

Refined lower bounds for adversarial bandits

S. Gerchinovitz and T. Lattimore · 2016

Later among the works it cites.

Gains and losses are fundamentally different in regret minimization: The sparse case

J. Kwon and V. Perchet · 2016

Later among the works it cites.