# Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 8 Jun 2026.

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

- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Context Attentive Bandits: Contextual Bandit with Restricted Context](https://mlsanity.com/paper/1705.03821/) (2017)
- [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022)
- [Adversarially Robust Submodular Maximization under Knapsack Constraints](https://mlsanity.com/paper/1905.02367/) (2019)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Sliding Window Algorithms for k-Clustering Problems](https://mlsanity.com/paper/2006.05850/) (2020)
- [Improved Algorithms for Time Decay Streams](https://mlsanity.com/paper/1907.07574/) (2019)
- [Truly Perfect Samplers for Data Streams and Sliding Windows](https://mlsanity.com/paper/2108.12017/) (2021)
- [Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches](https://mlsanity.com/paper/2110.15533/) (2021)
- [The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2309.03145/) (2023)
- [Optimal Streaming Algorithms for Multi-Armed Bandits](https://mlsanity.com/paper/2410.17835/) (2024)
- [Near-Optimal k-Clustering in the Sliding Window Model](https://mlsanity.com/paper/2311.00642/) (2023)
- [Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2405.19752/) (2024)
- [Fair Clustering in the Sliding Window Model](https://mlsanity.com/paper/2503.05173/) (2025)
- [Online Learning with Limited Information in the Sliding Window Model](https://mlsanity.com/paper/2601.03533/) (2026)
- [Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows](https://mlsanity.com/paper/1805.00212/) (2018)
- [Symmetric Norm Estimation and Regression on Sliding Windows](https://mlsanity.com/paper/2109.01635/) (2021)
- [Differentially Private L2-Heavy Hitters in the Sliding Window Model](https://mlsanity.com/paper/2302.11081/) (2023)
- [Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap](https://mlsanity.com/paper/2502.01067/) (2025)
- [Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2503.02428/) (2025)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [Incremental Sliding Window Connectivity over Streaming Graphs](https://mlsanity.com/paper/2406.06754/) (2024)
- [Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model](https://mlsanity.com/paper/2504.21175/) (2025)

## Abstract (arXiv)

Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper. In this setting, we are given n arms with unknown sub-Gaussian reward distributions and a parameter W. The arms arrive in a single-pass stream, and only the most recent W arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.