A single algorithm for both restless and rested rotting bandits

1. Problem Definition

The paper addresses the Multi-Armed Bandit (MAB) problem in non-stationary environments where the expected reward of an action decreases over time. This phenomenon, termed "rotting," occurs in two distinct settings:

• Rested Rotting Bandits: The reward of an arm decays only when the arm is pulled (e.g., user boredom from repeated recommendations). The decay is a function of the number of pulls $n$.
• Restless Rotting Bandits: The reward of an arm decays over time regardless of whether it is pulled (e.g., news articles becoming outdated). The decay is a function of time $t$.

Key Challenge: Previous literature treated these as fundamentally different problems. Algorithms designed for restless bandits (which assume rewards change independently of actions) performed poorly in rested settings, and vice versa. Furthermore, it was an open question whether a single algorithm could achieve near-optimal regret in both settings without prior knowledge of the decay type, the magnitude of change, or the time horizon.

The authors define the reward functions $\mu_i(t, n)$ as non-increasing in both $t$ and $n$. They also establish a theoretical lower bound showing that if rewards were allowed to increase (non-monotonic), no algorithm could achieve sub-linear regret in a mixed setting. However, under the decreasing assumption, they prove that a unified approach is possible.

2. Methodology: RAW-UCB

The authors propose Rotting Adaptive Window UCB (RAW-UCB), a novel index-based algorithm that unifies the treatment of rested and restless rotting bandits.

Core Mechanism

Unlike standard UCB algorithms that use a global average or a fixed sliding window, RAW-UCB adaptively selects the optimal "window size" $h$ for each arm to compute its Upper Confidence Bound (UCB).

• Index Calculation: For each arm $i$ at time $t$, the algorithm computes the UCB index for every possible window size $h$ (from 1 to the number of times the arm has been pulled).
  $$\text{ind}(i, t) = \min_{h \le N_{i,t-1}} \left( \hat{\mu}^h_i(t) + c(h, \delta_t) \right)$$
  Where $\hat{\mu}^h_i(t)$ is the empirical average of the last $h$ pulls, and $c(h, \delta_t)$ is the confidence radius.
• Selection: The arm with the minimum index is selected.
  • Why Minimum? Since rewards are rotting (decreasing), the true future value is bounded by the average of the most recent $h$ pulls. By taking the minimum over all $h$, the algorithm effectively finds the tightest (most conservative) upper bound on the current value, preventing the selection of arms that appear good due to old, high-value pulls but have since decayed.

Efficient Implementation

The naive implementation has $O(t)$ complexity per round. The authors introduce EFF-RAW-UCB, which uses a geometric grid of window sizes ($h, mh, m^2h, \dots$) and a lazy update mechanism. This reduces the time and space complexity to $O(K \log_m t)$, making it scalable for large horizons.

3. Key Contributions

1. Impossibility Result for General Non-Stationarity: The authors prove that if rewards are allowed to increase (non-monotonic), no learning strategy can achieve $o(T)$ regret in a setting mixing rested and restless arms. This highlights the critical importance of the "rotting" (decreasing) assumption.
2. Unified Algorithm (RAW-UCB): They introduce RAW-UCB, which requires no prior knowledge of:
   • Whether the setting is rested or restless.
   • The type of non-stationarity (piece-wise constant, bounded variation, etc.).
   • The horizon $T$ or the variation budget $V_T$.
3. Theoretical Guarantees:
   • Minimax Optimality: RAW-UCB achieves the minimax regret rate for both settings (up to poly-logarithmic factors).
     • For Restless (Variation Budget $V_T$): $O((V_T K T^2 \log T)^{1/3})$.
     • For Piece-wise Stationary ($\Upsilon_T$ breakpoints): $O(\sqrt{\Upsilon_T K T \log T})$.
   • Problem-Dependent Bounds: In both settings, the algorithm recovers $O(\log T)$ regret bounds when the gaps between arms are constant, a result previously thought impossible in restless settings without active exploration.
4. Superiority over FEWA: The paper compares RAW-UCB to the state-of-the-art FEWA (Filtering Expanding Window Algorithm). While FEWA uses similar statistics, its complex filtering mechanism leads to looser bounds. RAW-UCB achieves a tighter bound (improving the constant factor by 4 in the rested case) and is computationally simpler.

4. Results and Experiments

The authors validated their theory on both synthetic data and a real-world dataset.

• Synthetic Benchmarks:
  • In Rested settings, RAW-UCB consistently outperformed FEWA, Exp3.S, and GLR-UCB. It demonstrated that passive forgetting (used by FEWA) is less effective than the adaptive window approach.
  • In Restless settings, RAW-UCB matched or exceeded the performance of algorithms specifically designed for restless bandits (like AdSwitch and Exp3.S), despite having no knowledge of the setting type.
• Real-World Experiment (Yahoo! Front Page):
  • Using the Yahoo! R6A click-log dataset, the authors simulated a rotting scenario where news articles lose relevance over time.
  • Performance: RAW-UCB (specifically the efficient version with empirical tuning $\alpha=1.4$) achieved the lowest cumulative regret across multiple days of data.
  • Efficiency: The efficient version of RAW-UCB ran approximately 10 times faster than GLR-UCB while maintaining superior or comparable regret performance.
  • Robustness: RAW-UCB performed well on both "hard" days (frequent switches in optimal arms) and "easy" days (one dominant arm), achieving logarithmic regret on easy instances.

5. Significance

This paper is significant because it bridges a major gap in non-stationary bandit theory.

• Unification: It demonstrates that a single, simple index policy can handle both action-dependent and time-dependent rotting, eliminating the need for practitioners to know the specific nature of the non-stationarity beforehand.
• Practicality: By introducing an efficient implementation ($O(K \log t)$) and showing that empirical tuning ($\alpha \approx 1.4$) works well, the authors make the algorithm viable for real-world applications like recommendation systems and intelligent tutoring.
• Theoretical Insight: It clarifies that the "rotting" assumption is a powerful structural constraint that allows for better learning rates ($O(\log T)$) in restless settings, which are generally impossible in fully adversarial or non-monotonic environments.

In conclusion, RAW-UCB represents a state-of-the-art solution for rotting bandits, offering near-optimal theoretical guarantees and superior empirical performance across diverse non-stationary environments.