Discrepancy-Based Algorithms for Non-Stationary Rested Bandits
This provides a general framework for non-stationary rested bandits, addressing a key challenge in sequential decision-making for applications like recommendation systems, though it builds incrementally on existing UCB ideas.
The paper tackles the multi-armed bandit problem with non-stationary rewards in rested bandits, where reward distributions change only when arms are pulled, and achieves logarithmic regret bounds under natural conditions. It introduces a discrepancy-based algorithm that unifies analysis for various non-stationary bandit instances and shows practical improvements over benchmarks.
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. We show that the notion of discrepancy can be used to design very general algorithms and a unified framework for the analysis of multi-armed rested bandit problems with non-stationary rewards. In particular, we show that we can recover the regret guarantees of many specific instances of bandit problems with non-stationary rewards that have been studied in the literature. We also provide experiments demonstrating that our algorithms can enjoy a significant improvement in practice compared to standard benchmarks.