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

• Zinkevich 2003 - Online Convex Programming and Generalized Infinitesimal Gradient Ascent

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

• Online Learning