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

Motivated by the recency effect in online learning, we study algorithms for single-pass \emph{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 \emph{limited memory}, \textcolor{red}{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 \emph{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 algorithms. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Many online systems, such as recommendation platforms and online advertising, must adapt quickly because recent information matters more than older information. We study how to make good decisions in these changing environments when only a small amount of memory is available. We analyze the trade-off between memory and performance for learning the best recent choices from streaming data. Our results show that exactly identifying the best choice can be impossible with limited memory, but finding a near-best choice is still efficient. We also design algorithms with strong theoretical guarantees and validate them through experiments.