Motivated by computational considerations for convex optimization,
the notion of adaptive regret was first introduced by [1]},
which generalizes regret by considering the regret of every interval. They also provide an algorithm Follow-The-Leading-History which attains \(\tilde{O}(\sqrt{T})\)  adaptive regret.
[2]} consider the worst regret performance among all intervals with the same length and obtain interval-length dependent bounds.
[2]} obtain an efficient algorithm that achieves \(O(\sqrt{|I| \log ^2 T})\)  adaptive regret. This bound was later improved by [4]} to \(O(\sqrt{|I| \log T})\) .
