Learning Contextual Bandits in a Non-stationary Environment

Qingyun Wu, Naveen Iyer, Hongning Wang

TL;DR

This paper introduces dLinUCB, a novel contextual bandit algorithm designed for environments where user preferences (and thus reward distributions) change abruptly and unpredictably. By employing a hierarchical approach with "slave" bandit models that track different environmental states and a "master" bandit that monitors their performance, dLinUCB effectively detects and adapts to these changes, achieving significantly lower regret than existing methods in non-stationary settings.

What Problem Does This Paper Address?

Many real-world applications, like recommender systems and online advertising, rely on multi-armed bandit (MAB) algorithms to balance exploration and exploitation. However, traditional MAB algorithms assume a static environment where user preferences remain constant. This assumption is often violated in practice, as user interests can shift dynamically due to various factors. When preferences change, static MAB algorithms become suboptimal, leading to increased regret. This paper tackles the challenge of learning effectively in piecewise stationary environments, where the reward distribution remains stable for periods but can change abruptly at unknown times. The core problem is how to detect these changes and adapt the learning strategy without prior knowledge of when they will occur.

Methods

The proposed solution, dLinUCB, employs a hierarchical structure:

  • Slave Bandits: A set of contextual bandit models (specifically, LinUCB models are used for demonstration) are maintained. Each slave bandit is trained on data from a specific, assumed-to-be-stationary period.
  • Master Bandit: This higher-level component monitors the "badness" of each slave bandit. "Badness" is quantified by how often a slave bandit's reward predictions exceed its confidence bounds.
  • Change Detection: If a slave bandit's badness consistently exceeds a threshold derived from its confidence bounds, it signals a potential environmental change.
  • Model Management: When a change is detected with high confidence, outdated slave bandits are discarded, and new ones are created to learn the new environment.
  • Arm Selection: The master bandit selects the "most promising" slave bandit (the one with the lowest estimated badness) to interact with the environment. The feedback from this interaction is then used to update all active slave bandits, allowing them to learn from new data and refine their models.

This approach allows the algorithm to maintain multiple models representing different environmental states and dynamically switch between them as needed.

Datasets

The paper evaluates dLinUCB on:

  • Synthetic Datasets: Generated to control noise levels, environmental change magnitudes, and stationary period lengths, allowing for rigorous theoretical validation.
  • Real-World Datasets:
    • Yahoo! Today Module: A large-scale clickstream dataset for news recommendation.
  • LastFM & Delicious: Datasets from a music streaming service and a social bookmarking service, respectively, used for recommendation tasks.

The paper does not introduce new benchmarks but uses existing datasets to demonstrate the practical utility of dLinUCB in realistic non-stationary scenarios.

Key Insights and Ideas

  • The "Badness" Metric: Quantifying the deviation of a bandit model's predictions from its confidence bounds is a powerful indicator of environmental change. This metric allows the algorithm to infer when a model is no longer representative of the current environment.
  • Hierarchical Learning: Separating the problem into managing multiple "slave" models for different environmental states and a "master" model for change detection is an effective way to handle non-stationarity.
  • Adaptive Model Creation/Abandonment: Dynamically creating new models and discarding old ones is crucial for maintaining learning efficiency in environments that change over time. This avoids the performance degradation seen in static models.
  • Regret Bound Significance: The derived regret bound, $O(\Gamma_T \sqrt{S_{max}} \log S_{max})$, is theoretically shown to be among the lowest possible for non-stationary environments without further assumptions, highlighting the algorithm's efficiency.

Key Results

  • Theoretical Guarantees: dLinUCB is proven to have an upper regret bound of $O(\Gamma_T \sqrt{S_{max}} \log S_{max})$, where $\Gamma_T$ is the number of true environmental changes and $S_{max}$ is the longest stationary period. This bound is competitive with theoretical lower bounds.
  • Empirical Performance:
    • On synthetic data, dLinUCB consistently outperformed state-of-the-art stationary (LinUCB) and non-stationary (adTS, WMDUCB1) bandit algorithms across various noise levels, change magnitudes, and stationary period lengths.
  • In the Yahoo! Today Module experiment, dLinUCB achieved significant improvements (e.g., ~50% over uniform-LinUCB) in both user-personalized and non-personalized settings.
  • On LastFM and Delicious datasets, dLinUCB demonstrated strong performance, adapting well to the inherent non-stationarity and sparsity of these recommendation tasks.
  • Change Detection Accuracy: Visualizations show that dLinUCB accurately detects change points in real-world data, often in near real-time.

Limitations and Future Work

  • Continuously Changing Environments: The current dLinUCB is designed for piecewise stationary environments. Extending it to continuously changing environments (e.g., Brownian motion) where models become outdated immediately after creation is a key future direction.
  • Collaborative Learning: The current approach treats users as either identical or completely independent. Future work could explore how to integrate collaborative bandit learning techniques to leverage user similarities in non-stationary settings.
  • Contextual Badness Estimation: The master bandit's "badness" estimation currently does not utilize contextual information. Incorporating context into this estimation could further improve change detection accuracy and reduce regret.
  • Hyperparameter Sensitivity: While the paper demonstrates robustness, the performance of dLinUCB can be influenced by hyperparameters like $\delta_1$ and $\delta_2$, which control the sensitivity of change detection. Further research could explore adaptive or automatic tuning of these parameters.

Summary updated

Abstract

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.
BibTeX
@inproceedings{wu2018learning,
  author = {Qingyun Wu and Naveen Iyer and Hongning Wang},
  title = {{Learning Contextual Bandits in a Non-stationary Environment}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2018},
  doi = {10.1145/3209978.3210051},
}

Loading related content...

Figure