On Limited-Memory Subsampling Strategies for Bandits

Dorian Baudry, Yoan Russac, Olivier Cappé

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:

  1. 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.
  2. 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.

Regret performance of LB-SDA and LB-SDA-LM compared to standard bandit algorithms in a stationary environment.

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.

Dynamic regret of SW-LB-SDA in a non-stationary environment with abrupt changes in reward distributions.

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

BibTeX
@inproceedings{baudry2021limited,
  author = {Dorian Baudry and Yoan Russac and Olivier Cappé},
  title = {{On Limited-Memory Subsampling Strategies for Bandits}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=oFggsMVudOW},
}
Figure