# On Limited-Memory Subsampling Strategies for Bandits

arXiv: https://arxiv.org/abs/2106.10935 · HTML: https://mlsanity.com/paper/2106.10935/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 21 Jun 2021.

## Builds on (most cited first, 8 of 8)

- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [Sub-sampling for Efficient Non-Parametric Bandit Exploration](https://mlsanity.com/paper/2010.14323/) (2020)

## Built on by (most cited first, 8 of 8)

- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Efficient Algorithms for Extreme Bandits](https://mlsanity.com/paper/2203.10883/) (2022)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)
- [Towards an efficient and risk aware strategy for guiding farmers in identifying best crop management](https://mlsanity.com/paper/2210.04537/) (2022)

## Abstract (arXiv)

There has been a recent surge of interest in nonparametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the full history of rewards. Our first contribution is to show that a simple deterministic subsampling rule, proposed in the recent work of Baudry et al. (2020) under the name of ''last-block subsampling'', is asymptotically optimal in one-parameter exponential families. In addition, we prove that these guarantees also hold when limiting the algorithm memory to a polylogarithmic function of the time horizon. These findings open up new perspectives, in particular for non-stationary scenarios in which the arm distributions evolve over time. We propose a variant of the algorithm in which only the most recent observations are used for subsampling, achieving optimal regret guarantees under the assumption of a known number of abrupt changes. Extensive numerical simulations highlight the merits of this approach, particularly when the changes are not only affecting the means of the rewards.