A Modularized Framework for Piecewise-Stationary Restless Bandits

1. Problem Definition

The paper addresses the Piecewise-Stationary Restless Multi-Armed Bandit (PS-RMAB) problem.

• Restless Bandits (RMAB): Unlike classical stochastic bandits where unselected arms remain frozen, RMAB arms evolve as Markov chains regardless of whether they are selected. This models dynamic environments like spectrum access, healthcare scheduling, and information freshness.
• Piecewise-Stationarity: The environment is not static; it consists of $M$ segments where the transition kernels and reward distributions of the Markov chains remain constant within a segment but change abruptly at unknown "change points."
• Core Challenge: The learner must balance exploration (to detect changes) and exploitation (to maximize rewards). In restless settings, distinguishing between natural state transitions of a Markov chain and genuine environmental changes is difficult, leading to high false alarm rates or delayed detection. Existing methods often require prior knowledge of the number of change points ($M$) or rely on passive forgetting mechanisms (e.g., sliding windows) that may fail in restless dynamics.

2. Methodology

The authors propose a modular framework that integrates three distinct components, allowing for "plug-and-play" compatibility with existing solvers and detectors.

A. Modular Architecture

The framework consists of:

1. Base Solver ($B$): Any stationary RMAB algorithm (e.g., RestlessUCB, Colored-UCRL2).
2. Change Detector ($D$): Any standard change detection module (e.g., CUSUM, GLR, window-based tests) that monitors arm reward streams.
3. Diminishing Exploration ($E$): A novel scheduling mechanism that triggers forced exploration rounds.

B. Diminishing Exploration (DE)

This is the core innovation. Instead of using a uniform exploration rate (which requires knowing $M$ to optimize the trade-off), DE adaptively reduces the frequency of forced exploration over time.

• Mechanism: Within a segment, the algorithm performs uniform exploration (pulling all arms) at specific intervals. The time gap between these exploration sessions increases as time progresses within the segment.
• Formula: The start time of the $j$-th exploration session in segment $i$ is defined recursively:
  $$u^{(j)}_i = \left\lceil u^{(j-1)}_i + \frac{K}{\alpha}\sqrt{u^{(j-1)}_i} + \frac{K^2}{4\alpha^2} \right\rceil$$
  where $K$ is the number of arms and $\alpha$ is a parameter.
• Benefit: This ensures sufficient statistical evidence for change detection early in a segment while minimizing unnecessary exploration later, achieving near-optimal regret without prior knowledge of $M$.

C. Reset Mechanism

When the change detector $D$ signals a change, the framework immediately:

1. Resets the base solver $B$ to discard outdated history.
2. Resets the exploration schedule $E$ to restart the diminishing sequence.
3. Resets the change detector's internal state.

3. Key Contributions

1. Modular Framework for PS-RMAB: The first framework to systematically integrate arbitrary stationary RMAB solvers with change detection and a diminishing exploration schedule. It isolates the costs of exploration and detection from the intrinsic regret of the base solver.
2. Refined Excess Regret Notion: The authors introduce a metric called Excess Regret ($R_{excess}$), defined as the difference between the learner's performance and a "Segment Oracle" (an oracle that knows the true change points and restarts the base solver at those exact moments). This isolates the overhead caused specifically by the non-stationary adaptation mechanism.
3. Theoretical Guarantees:
   • They prove a general excess regret bound of $\tilde{O}(\sqrt{MKT})$ (ignoring logarithmic factors), where $L$ is the maximum mixing time of the Markov chains.
   • This bound matches the minimax rate for piecewise-stationary bandits, proving that the framework does not degrade the performance of near-optimal stationary solvers.
   • They establish a Transfer Principle: If a base solver is near-optimal for stationary RMABs, the framework preserves this near-optimality in the piecewise-stationary setting.
4. No Prior Knowledge of $M$: Unlike many active methods (e.g., M-UCB) that require $M$ to set exploration rates, the diminishing exploration scheme adapts automatically.

4. Results

Theoretical Analysis

• One-State Case (Reduction to PS-MAB): When arms have only one state, the framework reduces to the classical piecewise-stationary bandit problem. The analysis shows the excess regret scales as $O(\sqrt{KMT \log T})$.
• General RMAB Case: For general Markov chains, the analysis incorporates the mixing time ($L$). The regret bound becomes $O(\sqrt{MKLT \log T})$. The proof relies on concentration inequalities for ergodic Markov chains to handle the temporal dependence of rewards.
• False Alarms & Detection Delay: The framework rigorously bounds the probability of false alarms (making them vanish as $1/T$) and the expected detection delay, ensuring they do not dominate the regret.

Simulation Results

• Setup: Simulations were conducted with $T=100,000$, $M=5$ segments, and $K=3$ arms (3-state Markov chains).
• Performance:
  • The framework (using RestlessUCB and Colored-UCRL2 as base solvers) achieved excess regret close to the Segment Oracle.
  • It significantly outperformed base solvers without change detection (which suffer from sharp regret growth when environments change).
  • It outperformed passive methods (like sliding windows) in scenarios with abrupt changes.
• Scalability: The diminishing exploration scheme consistently achieved lower regret and computation time compared to uniform exploration and other active methods (like Master+UCB) across varying $M$ and $T$, even when assumptions about change magnitude were violated.

5. Significance

• Bridging Theory and Practice: The paper provides a practical recipe for extending stationary RMAB algorithms to dynamic environments without redesigning the core solver.
• Handling Restlessness: It addresses a critical gap in the literature: most non-stationary bandit literature assumes i.i.d. rewards. This work specifically tackles the complexity introduced by Markovian state evolution, where state transitions can mimic environmental changes.
• Efficiency: By eliminating the need for prior knowledge of the number of changes ($M$) and using a low-complexity diminishing schedule, the framework is highly applicable to real-world systems where change frequency is unknown and computational resources are limited.
• Theoretical Rigor: The derivation of the $\tilde{O}(\sqrt{MKT})$ bound for restless settings sets a new benchmark for non-stationary RMAB research, proving that active adaptation can be as efficient as passive forgetting in terms of asymptotic regret.