A Definition of Non-Stationary Bandits

Understand

Despite the subject of non-stationary bandit learning having attracted much recent attention, we have yet to identify a formal definition of non-stationarity that can consistently distinguish non-stationary bandits from stationary ones.

• Prior work has characterized non-stationary bandits as bandits for which the reward distribution changes over time.
• We demonstrate that this definition can ambiguously classify the same bandit as both stationary and non-stationary; this ambiguity arises in the existing definition's dependence on the latent sequence of reward distributions.
• Moreover, the definition has given rise to two widely used notions of regret: the dynamic regret and the weak regret.