Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
2026-06-08 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors study a problem where you watch a stream of slot machines (arms), but can only remember the last few you saw (a sliding window). They focus on how to find the best or nearly best machine while using limited memory, and also how to minimize losses over time (regret). They show it’s hard to find the exact best machine without lots of memory, but you can find a good enough one efficiently. Their work also introduces a new way to measure regret and explores how using more or less memory affects performance, backed up by experiments.
multi-armed banditssliding windowstreaming algorithmspure explorationregret minimizationsub-Gaussian distributionsmemory constraintssingle-pass algorithmapproximate best armsample complexity
Authors
Vladimir Braverman, Chen Wang, Liudeng Wang, Samson Zhou
Abstract
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.