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:
- PS$\varepsilon$BAI (Active Learner): This subroutine actively manages non-stationarity using two custom procedures:
- Linear-Change Detection (LCD): Uses a sliding window mechanism to monitor rewards and trigger an alarm when a context change occurs.
- 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.
- 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.
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