Tracking Most Severe Arm Changes in Bandits. (arXiv:2112.13838v2 [cs.LG] UPDATED)

In bandits with distribution shifts, one aims to automatically detect an
unknown number $L$ of changes in reward distribution, and restart exploration
when necessary. While this problem remained open for many years, a recent
breakthrough of Auer et al. (2018, 2019) provide the first adaptive procedure
to guarantee an optimal (dynamic) regret $\sqrt{LT}$, for $T$ rounds, with no
knowledge of $L$. However, not all distributional shifts are equally severe,
e.g., suppose no best arm switches occur, then we cannot rule …

arm arxiv tracking