Abstract
Subsampling-based algorithms for multi-armed bandits (MAB) provide a robust, non-parametric approach to decision-making under uncertainty. However, traditional subsampling methods often require storing the entire reward history and involve expensive random sampling. This paper introduces the Last-Block Subsampling Duelling Algorithm (LB-SDA), which utilizes a deterministic rule to achieve asymptotic optimality. We demonstrate that storing only a polylogarithmic fraction of observations (LB-SDA-LM) is sufficient for optimality, drastically reducing memory and computational requirements. Additionally, we extend this approach to non-stationary environments via a sliding-window variant (SW-LB-SDA), which achieves state-of-the-art dynamic regret performance.
Introduction
The Multi-Armed Bandit problem is a fundamental framework for balancing exploration and exploitation. While parametric methods like Upper Confidence Bound (UCB) and Thompson Sampling (TS) are widely used, they often rely on specific distributional assumptions. Subsampling-based methods offer a non-parametric alternative by using raw data to guide exploration. Despite their appeal, these methods are typically "memory hogs," requiring $O(T)$ storage for a horizon $T$, and are computationally intensive due to repeated random sampling. Furthermore, standard models often fail in non-stationary environments where reward distributions change over time.
Methodology
The core of our approach is the Last-Block Subsampling Duelling Algorithm (LB-SDA). Unlike previous methods that rely on complex random sampling, LB-SDA employs a deterministic comparison: when a "challenger" arm duels a "leader" arm, the challenger's average reward is compared against the average of the most recent observations of the leader.
We propose two primary variants:
- LB-SDA-LM (Limited Memory): This version caps stored observations at $O((\log T)^2)$. By discarding the oldest data once the limit is reached, it maintains a minimal memory footprint.
- SW-LB-SDA (Sliding Window): Designed for non-stationary environments, this variant uses a sliding window of size $\tau$ and incorporates "diversity flags" to ensure the algorithm can pivot when a previously sub-optimal arm becomes the best choice.
Experimental Results
We evaluated our algorithms through extensive numerical simulations on Bernoulli and Gaussian bandits.
Stationary Environments
In stationary settings, LB-SDA and its limited-memory counterpart, LB-SDA-LM, match the theoretical lower bound for regret. Notably, for a horizon of $T=10,000$, storing as few as 50 to 150 samples resulted in negligible performance loss compared to full-history storage.
As shown in the figure above, LB-SDA variants significantly outperform UCB1 and are competitive with kl-UCB and Thompson Sampling, despite their reduced memory requirements.
Non-Stationary Environments
In environments with abrupt changes in reward distributions, SW-LB-SDA achieves a dynamic regret of $O(\sqrt{\Gamma_T T \log T})$, where $\Gamma_T$ is the number of breakpoints. This matches the best known theoretical bounds.
The results in the non-stationary case demonstrate that SW-LB-SDA is highly robust, adapting to changes in both mean and variance more effectively than established competitors like EXP3S or CUSUM-based methods.
Key Insights
- Deterministic Sufficiency: A key finding is that the "diversity" of random sampling is not required for optimality; deterministic comparison against the most recent block of leader rewards provides sufficient exploration.
- Passive Forgetting: Limiting memory or using a sliding window allows the algorithm to naturally "forget" obsolete data, which is critical for maintaining performance when the underlying environment shifts.
- Efficiency: LB-SDA-LM reduces storage requirements from $O(T)$ to $O((\log T)^2)$, making it suitable for resource-constrained applications.
Conclusion and Future Work
This work proves that simple, deterministic subsampling is a powerful and efficient tool for MAB problems. Future research will focus on making the algorithms "anytime" (removing the need to know the horizon $T$ in advance) and extending theoretical guarantees to multi-parameter exponential families.
Summary updated