Multi-Armed Bandits with Non-Stationary Rewards

Corinna CortesarXiv 2017 · arXiv

TL;DR

This paper introduces a new framework and algorithms for the "rested" multi-armed bandit problem, where reward distributions change only when an arm is pulled. They achieve near-optimal logarithmic regret by leveraging a novel concept called "weighted discrepancy," which quantifies how much a reward process deviates from stationarity. This work unifies and extends existing results for various non-stationary bandit settings.

What Problem Does This Paper Address?

The classic multi-armed bandit (MAB) problem involves an agent repeatedly choosing one of several "arms" (e.g., ads, treatments) to maximize cumulative rewards. Traditionally, this assumes rewards are independent and identically distributed (i.i.d.). However, many real-world scenarios involve non-stationary rewards, where the underlying reward distributions change over time.

This paper focuses on a specific type of non-stationarity called the "rested" setting. In this setting, the reward distribution of an arm only evolves when that specific arm is pulled. This is in contrast to the "restless" setting, where all arms' distributions change continuously, regardless of selection. The challenge is to design algorithms that can adapt to these changes and achieve good performance (low regret) without making strong, often unverifiable, assumptions about the nature of the non-stationarity. Existing work often requires specific knowledge of the reward process (e.g., it follows a Brownian motion or a Markov process), which is not always available.

Methods

The core contribution is the introduction of weighted discrepancy as a tool to measure non-stationarity in the rested setting. This concept quantifies the difference between the expected future reward of an arm and a weighted average of its past expected rewards.

The authors then develop Discrepancy-based UCB (DISC-UCB) algorithms. These algorithms build upon the well-known Upper Confidence Bound (UCB) principle but incorporate the weighted discrepancy.

  1. Known Discrepancy: They first show that if the discrepancies are known, a DISC-UCB algorithm can achieve logarithmic path-dependent dynamic pseudo-regret. This is a strong theoretical result, demonstrating the power of the discrepancy measure.
  2. Bounded Discrepancy: More realistically, they propose WEIGHTED-UCB, which assumes only that the discrepancies are bounded. This algorithm also achieves logarithmic regret, matching or improving upon existing state-of-the-art results for various specific non-stationary scenarios.

The analysis relies on concentration bounds (similar to Hoeffding's inequality but adapted for non-stationarity) and a novel definition of regret called "path-dependent dynamic pseudo-regret," which is more appropriate for non-stationary settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and experimental validation using simulated stochastic processes.

Key Insights and Ideas

  • Weighted Discrepancy as a Unifying Measure: The paper introduces weighted discrepancy as a powerful and general tool to quantify non-stationarity in rested bandit problems. This concept allows for a unified theoretical framework that can encompass many previously studied specific cases.
  • Restless vs. Rested Distinction: The paper clearly delineates the "rested" setting (changes only when pulled) and highlights its distinct challenges and opportunities compared to the "restless" setting.
  • Logarithmic Regret is Achievable: The core finding is that even with arbitrary bounded non-stationarity in the rested setting, logarithmic regret (near-optimal) is achievable. This is a significant theoretical guarantee.
  • UCB Adaptation is Effective: The paper demonstrates that adapting the UCB principle by incorporating discrepancy measures can lead to robust and efficient algorithms for non-stationary bandits.
  • Empirical Validation: Experiments show that their proposed algorithms outperform a standard adversarial bandit algorithm (EXP3) across various simulated non-stationary scenarios.

Key Results

  • Theoretical Guarantees:
    • DISC-UCB (Known Discrepancy): Achieves logarithmic path-dependent dynamic pseudo-regret when discrepancies are known.
  • WEIGHTED-UCB (Bounded Discrepancy): Achieves logarithmic path-dependent dynamic pseudo-regret under the assumption of bounded discrepancies. This result is shown to be optimal in certain static gap scenarios.
  • Unified Framework: The discrepancy-based approach provides a unified framework to recover and extend regret guarantees for various specific non-stationary scenarios, including i.i.d., drifting means, rarely changing means, rotting arms, periodic means, and trend functions.
  • Empirical Performance: Experiments show that WEIGHTED-UCB consistently outperforms EXP3 across diverse simulated non-stationary environments, often by a significant margin, especially in the long run.

Limitations and Future Work

  • Computational Cost of Discrepancy Estimation: While the theoretical analysis assumes known or bounded discrepancies, estimating these values in practice can be computationally challenging. The paper mentions that for some scenarios, discrepancy can be bounded by carefully choosing weights, but this might not always be straightforward.
  • "Oblivious Adversary" Assumption: The paper assumes an "oblivious adversary" that sets up the stochastic processes beforehand. While common, a more adaptive adversary could pose further challenges.
  • Future Work: The paper suggests exploring more complex scenarios and adaptive adversaries. The unified framework also opens doors for analyzing new types of non-stationary processes. The empirical results suggest that further investigation into practical implementations and hyperparameter tuning for WEIGHTED-UCB could be beneficial.

Summary updated

BibTeX
@misc{cortes2017multi,
  author = {Corinna Cortes},
  title = {{Multi-Armed Bandits with Non-Stationary Rewards}},
  year = {2017},
  eprint = {1710.10657},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.10657},
}
Figure