Theory: Online Learning and Regret Bounds

• Shalev-Shwartz 2007 - Online Learning: Theory, Algorithms, and Applications See section 2.4 (page 27 in pdf) for historical references
• Battou - Online Learning and Stochastic Approximations

• Zinkevich 2003 - Online Convex Programming and Generalized Infinitesimal Gradient Ascent See also the CMU tech report

Regret bounds are widely used for proving generalization bounds for online learning algorithms, and for proving convergence rates of optimization algorithms (for example, in the Adagrad paper).

Quick technical explaination from Bottou et al 2016, page 39:

• Gordon 1999 - Regret Bounds for Prediction Problems

• Multi-Armed Bandit
• Online Learning
• Reinforcement Learning - Theory