Learning Contextual Bandits in a Non-stationary Environment
This addresses the dynamic user preference problem in recommender systems and similar real-world applications, representing an incremental improvement over stationary assumptions.
The paper tackles the problem of non-stationary reward distributions in contextual bandit algorithms, which cause suboptimal performance in applications like recommender systems, by proposing an algorithm that detects environmental changes and updates strategies, achieving rigorous regret bounds and empirical validation on synthetic and real-world datasets.
Multi-armed bandit algorithms have become a reference solution for handling the explore/exploit dilemma in recommender systems, and many other important real-world problems, such as display advertisement. However, such algorithms usually assume a stationary reward distribution, which hardly holds in practice as users' preferences are dynamic. This inevitably costs a recommender system consistent suboptimal performance. In this paper, we consider the situation where the underlying distribution of reward remains unchanged over (possibly short) epochs and shifts at unknown time instants. In accordance, we propose a contextual bandit algorithm that detects possible changes of environment based on its reward estimation confidence and updates its arm selection strategy respectively. Rigorous upper regret bound analysis of the proposed algorithm demonstrates its learning effectiveness in such a non-trivial environment. Extensive empirical evaluations on both synthetic and real-world datasets for recommendation confirm its practical utility in a changing environment.