Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits

Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong

TL;DR

This paper introduces a novel piecewise stationary linear bandit model where an environment's context changes at unknown times based on an unknown distribution. To solve the problem of identifying the best arm under these conditions, the authors propose PS$\varepsilon$BAI$^+$, an algorithm that actively detects changepoints and aligns recurring contexts to maximize data efficiency. The authors prove that this approach is almost minimax optimal, drastically reducing sample complexity compared to naïve baselines.

What Problem Does This Paper Address?

In traditional multi-armed bandit problems, the environment is assumed to be stationary—meaning the expected reward for pulling a certain arm remains constant over time. However, real-world scenarios like stock markets (bull vs. bear markets) or agriculture (changing weather patterns) are inherently non-stationary.

The authors tackle a specific flavor of this problem: Piecewise Stationary Linear Bandits (PSLB). Here, the environment remains stable for a period before suddenly shifting to a new "context" at an unknown changepoint. Crucially, the agent does not know when these shifts happen, what the latent context vectors look like, or the underlying distribution of these contexts. The goal is Best Arm Identification (BAI): finding the single best arm based on its long-term average return across all contexts, using as few samples as possible within a specified confidence ($\delta$) and tolerance ($\varepsilon$).

Methods

The core contribution is the PS$\varepsilon$BAI$^+$ (Piecewise-Stationary $\varepsilon$-Best Arm Identification$^+$) algorithm. It utilizes a clever parallel-execution strategy combining two subroutines:

  1. PS$\varepsilon$BAI (Active Learner): This subroutine actively manages non-stationarity using two custom procedures:
  2. Linear-Change Detection (LCD): Uses a sliding window mechanism to monitor rewards and trigger an alarm when a context change occurs.
  3. Linear-Context Alignment (LCA): Once a change is detected, instead of wiping its memory, the algorithm checks if the new context matches a previously seen one. This allows it to pool historical data across non-consecutive segments of the same context.
  4. N$\varepsilon$BAI (Naïve Baseline): A safe but slower baseline algorithm whose sample complexity unfortunately scales linearly with the maximum possible segment length ($L_{max}$).

By running both in parallel and allocating arm pulls according to a minimax-optimal G-optimal design, PS$\varepsilon$BAI$^+$ inherits the rapid change-detection speed of the active learner while maintaining the mathematical safety net of the naïve baseline.

Figure 1: (a) No change alarm is raised during a stationary segment. The active CD samples are the input to the LCD subroutine at current time step t. (b) A changepoint is detected by LCD, followed by a CA phase and a statistics reversion step.

Datasets

The paper evaluates the proposed algorithm entirely through synthetic numerical simulations. They construct a controlled environment ("Example 1") featuring $2d-1$ arms and $2d-2$ contexts to rigorously test how well the algorithm handles subtle context shifts and long stationary periods. No real-world datasets were used.

Key Insights and Ideas

  • Context Alignment Over Resetting: Traditional non-stationary bandit algorithms often reset their history when a change is detected. This paper highlights that aligning current contexts with past ones dramatically accelerates learning by reusing old data.
  • The Parallel Trick for Expected Complexity: Active change-detection algorithms inherently risk false alarms, making their expected sample complexity difficult to bound theoretically. Running a naïve baseline in parallel elegantly bypasses this theoretical bottleneck without degrading empirical performance.
  • Breaking the Dependency on $L_{max}$: Naïve approaches get bogged down if a single stationary segment lasts a very long time. PS$\varepsilon$BAI$^+$ breaks this dependency by actively identifying when it has collected sufficient data within a segment and moving on.

Key Results

  • Almost Asymptotically Optimal: The authors prove a theoretical lower bound for any $(\varepsilon, \delta)$-PAC algorithm in this setting and show that PS$\varepsilon$BAI$^+$ matches this lower bound up to logarithmic factors.
  • Massive Speedups: In numerical experiments, the sample complexity of PS$\varepsilon$BAI$^+$ was $\le 1\%$ of the naïve N$\varepsilon$BAI baseline.
  • Oracle-Level Competitiveness: Even when compared against oracle algorithms ($D\varepsilon$BAI) that are explicitly told exactly when changepoints occur and what the contexts are, PS$\varepsilon$BAI$^+$ remains highly competitive despite working completely in the dark.

Limitations and Future Work

  • Knowledge of Bounds: The algorithm still requires prior knowledge of the minimum ($L_{min}$) and maximum ($L_{max}$) segment lengths to configure its sliding windows, though empirical tests showed it is reasonably robust to slight misspecifications.
  • Finite Contexts: The model assumes a discrete and finite number of latent contexts ($N$).
  • Instance-Dependent Optimality: While the algorithm is minimax (worst-case) optimal, the authors note that adapting it to use more sophisticated allocation rules (like $\mathcal{XY}$-allocation) could unlock instance-dependent optimality.
  • Fixed-Budget Setting: Exploring how to adapt this framework to a fixed-time-horizon budget rather than a fixed-confidence threshold remains an open problem.

Summary updated

Abstract

We propose a {\em novel} piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent. We design {\em Piecewise-Stationary $\varepsilon$-Best Arm Identification$^+$} (PS$\varepsilon$BAI$^+$), an algorithm that is guaranteed to identify an $\varepsilon$-optimal arm with probability $\ge 1-δ$ and with a minimal number of samples. PS$\varepsilon$BAI$^+$ consists of two subroutines, PS$\varepsilon$BAI and {\sc Naïve $\varepsilon$-BAI} (N$\varepsilon$BAI), which are executed in parallel. PS$\varepsilon$BAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When PS$\varepsilon$BAI and N$\varepsilon$BAI are utilized judiciously in parallel, PS$\varepsilon$BAI$^+$ is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PS$\varepsilon$BAI$^+$ is optimal up to a logarithmic factor. We compare PS$\varepsilon$BAI$^+$ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both our analytical and numerical results corroborate that the efficacy of PS$\varepsilon$BAI$^+$ is due to the delicate change detection and context alignment procedures embedded in PS$\varepsilon$BAI.
BibTeX
@inproceedings{hou2024almost,
  author = {Yunlong Hou and Vincent Y. F. Tan and Zixin Zhong},
  title = {{Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=Q5e3ftQ3q3},
}
Figure