A Linear Bandit for Seasonal Environments.

Giuseppe Di Benedetto, Vito Bellini, Giovanni ZappellaarXiv 2020 · OpenReview

Abstract

Contextual bandit algorithms are essential for modern recommendation systems but often struggle in non-stationary environments where reward functions change abruptly. While existing methods use forgetting mechanisms or change-point detection to adapt, they fail to leverage recurring patterns, such as seasonal trends or holiday shopping behaviors. We present the All-Season Bandit, a novel algorithm that maintains a library of "base bandits" to remember and reuse previous states. By employing a "shadow bandit" for change detection and dynamic weighting for model selection, the All-Season Bandit significantly reduces regret in environments with recurring non-stationarity by avoiding redundant exploration.

Introduction

Most contextual bandit algorithms assume a stationary environment where the relationship between a user’s context and their likely reward remains constant. In reality, user behavior is often fickle and seasonal. For instance, a music streaming app might see a surge in specific genres during holidays, only to have tastes revert to "normal" later.

Existing solutions generally fall into two categories: passive methods (e.g., sliding windows) that prioritize recent data by forgetting the past, and active methods that reset models upon detecting a change. Neither approach handles seasonality well; when an environment returns to a previously seen state, these algorithms treat it as brand new, wasting resources on re-learning. The All-Season Bandit addresses this gap by treating the environment as a collection of unique, recurring stationary states.

Methods

The All-Season Bandit architecture is built around three core components designed to balance long-term memory with short-term adaptability.

Key Components

  • Base Bandits (Long-term Memory): A collection of Linear Thompson Sampling (linTS) instances. Each instance specializes in a specific reward state the system has encountered previously.
  • Shadow Bandit (Short-term Memory): A specialized bandit that monitors only the most recent data. It acts as a "scout"; if its predictions significantly outperform all existing Base Bandits, it signals a shift to a new, unrecorded state.
  • Dynamic Weighting: At each step, the algorithm calculates a weight for every bandit (Base and Shadow) based on the posterior predictive probability. This effectively asks, "How likely is it that our recent observations were generated by this specific bandit's model?"
  • KL Pruning: To maintain computational efficiency and prevent an infinite growth of models, the system uses Symmetric Kullback-Leibler (KL) divergence. If two bandits become too similar, the one with higher uncertainty is discarded, ensuring the library remains diverse.
Figure 2: The top panel shows the ground truth non-stationarity pattern (different colors represent different reward states), while the bottom panel shows the algorithm's dynamic weighting, demonstrating how it correctly identifies and switches between base bandits as the environment shifts.

Experimental Setup

The researchers evaluated the algorithm using both synthetic and real-world datasets:

  1. Synthetic Data: A controlled environment with 10,000 observations and 8 abrupt change points to verify state recovery.
  2. MNIST & Fashion-MNIST: Image classification tasks were converted into bandit problems where the "reward" was a correct classification. To simulate real-world volatility, labels were shuffled according to three distinct patterns: Regular (long periods, few changes), Realistic (mixed durations), and Extreme (frequent changes).
Figure 6: Visualization of the three non-stationarity patterns (Regular, Realistic, and Extreme) used to evaluate the algorithm's robustness against varying frequencies of environmental shifts.

Key Results and Insights

The All-Season Bandit consistently outperformed state-of-the-art baselines like SW-LinTS (Sliding Window) and dLinUCB across various scenarios.

  • Superior Accuracy: In MNIST "arm-shift" experiments, the All-Season variant achieved an average reward of 0.77, surpassing standard LinTS (0.72) and the complex DenBand competitor (0.71).
  • Robustness to Rapid Change: The performance gains were most pronounced in "Extreme" patterns. While passive algorithms struggled to converge before the next shift, the All-Season Bandit could quickly "snap" back to a previously learned model, maintaining high performance even under high frequency changes.
  • Memory as an Asset: The core insight is that non-stationarity is often about reversion rather than just change. By treating past models as reusable assets, the algorithm avoids the regret associated with re-exploring known states.

Conclusion and Future Work

The All-Season Bandit offers a more efficient approach to machine learning in volatile environments by remembering the past to navigate the future. While highly effective, the authors note that the current linear reward assumption could be a limitation in highly non-linear real-world scenarios. Future work will explore using General Bayes for more robust weighting and Bayesian Core Sets to further refine the mathematical rigor of the pruning process.

Summary updated

Abstract

Contextual bandit algorithms are extremely popular and widely used in recommendation systems to provide online personalised recommendations. A recurrent assumption is the stationarity of the reward function, which is rather unrealistic in most of the real-world applications. In the music recommendation scenario for instance, people's music taste can abruptly change during certain events, such as Halloween or Christmas, and revert to the previous music taste soon after. We would therefore need an algorithm which can promptly react to these changes. Moreover, we would like to leverage already observed rewards collected during different stationary periods which can potentially reoccur, without the need of restarting the learning process from scratch. A growing literature has addressed the problem of reward's non-stationarity, providing algorithms that could quickly adapt to the changing environment. However, up to our knowledge, there is no algorithm which deals with seasonal changes of the reward function. Here we present a contextual bandit algorithm which detects and adapts to abrupt changes of the reward function and leverages previous estimations whenever the environment falls back to a previously observed state. We show that the proposed method can outperform state-of-the-art algorithms for non-stationary environments. We ran our experiment on both synthetic and real datasets.
BibTeX
@misc{benedetto2020linear,
  author = {Giuseppe Di Benedetto and Vito Bellini and Giovanni Zappella},
  title = {{A Linear Bandit for Seasonal Environments.}},
  year = {2020},
  eprint = {2004.13576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.13576},
}
Figure