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.
Experimental Setup
The researchers evaluated the algorithm using both synthetic and real-world datasets:
- Synthetic Data: A controlled environment with 10,000 observations and 8 abrupt change points to verify state recovery.
- 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).
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