Discrepancy-Based Algorithms for Non-Stationary Rested Bandits

Understand

We study the multi-armed bandit problem where the rewards are realizations of general non-stationary stochastic processes, a setting that generalizes many existing lines of work and analyses.

• In particular, we present a theoretical analysis and derive regret guarantees for rested bandits in which the reward distribution of each arm changes only when we pull that arm.
• Remarkably, our regret bounds are logarithmic in the number of rounds under several natural conditions.
• We introduce a new algorithm based on classical UCB ideas combined with the notion of weighted discrepancy, a useful tool for measuring the non-stationarity of a stochastic process.