Best Arm Identification for Bandits with Shifting Means
Finding the best option when the playing field keeps shifting
When an AI system tries to identify the best choice among many options, it usually assumes the quality differences stay constant. This paper tackles a harder version of that problem: the differences remain stable, but an outside force can shift all values up or down unpredictably each round. The researchers show that popular existing methods fail under these shifting conditions and propose a new algorithm that provably finds the best option while using the minimum possible number of tests.
Many real systems operate in changing environments—stock portfolios affected by market swings, medical treatments complicated by fluctuating patient conditions, or recommendation systems dealing with shifting user preferences. This work provides algorithms that can reliably identify the best strategy even when external forces keep moving the goalposts, without requiring extra samples to do so. That efficiency matters in high-stakes settings where every test is expensive or time-consuming.