Tracking Most Significant Arm Switches in Bandits. (arXiv:2112.13838v6 [cs.LG] UPDATED)

Web: http://arxiv.org/abs/2112.13838

In bandit with distribution shifts, one aims to automatically adapt to
unknown changes in reward distribution, and restart exploration when necessary.
While this problem has been studied for many years, a recent breakthrough of
Auer et al. (2018, 2019) provides the first adaptive procedure to guarantee an
optimal (dynamic) regret $\sqrt{LT}$, for $T$ rounds, and an unknown number $L$
of changes. However, while this rate is tight in the worst case, it remained
open whether faster rates are possible, without …

arm arxiv lg tracking