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

• URL: http://arxiv.org/abs/2606.08977v1
• Date: Mon, 08 Jun 2026 03:21:54 GMT
• Title: Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
• Abstract summary: We study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper.<n>In this setting, we are given $n$ arms with unknown sub-Gaussian reward distributions and a parameter $W$.<n>The arms arrive in a single-pass stream, and only the most recent $W$ arms are considered valid.
• Score: 28.239402296592967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• On the Problem of Best Arm Retention [2.9772441757190746]
  We study the problem of Best Arm Retention (BAR), which has recently found applications in streaming algorithms for multi-armed bandits.<n>We first investigate pure exploration for the BAR problem under different criteria, and then minimize the regret with specific constraints.
  arXiv  Detail & Related papers  (2025-04-16T08:41:20Z)
• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  This paper is in the field of sequential Multi-Armed Bandits (MABs)<n>We study a particular case of the rested bandits in which the arms' expected reward is monotonically non-decreasing and concave.<n>We empirically compare our algorithms with state-of-the-art methods for non-stationary MABs over several synthetically generated tasks and an online model selection problem for a real-world dataset.
  arXiv  Detail & Related papers  (2024-11-06T22:00:46Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible.<n>We study multi-fidelity best-arm identification, in which the can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost.<n>Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm.
  arXiv  Detail & Related papers  (2024-06-05T08:02:40Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  We study the Borda regret minimization problem for dueling bandits, which aims to identify the item with the highest Borda score. We propose a rich class of generalized linear dueling bandit models, which cover many existing models. Our algorithm achieves an $tildeO(d2/3 T2/3)$ regret, which is also optimal.
  arXiv  Detail & Related papers  (2023-03-15T17:59:27Z)
• Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
  We consider the Scale-Free Adversarial Multi Armed Bandit(MAB) problem. We design a Follow The Regularized Leader(FTRL) algorithm, which comes with the first scale-free regret guarantee for MAB. We also develop a new technique for obtaining local-norm lower bounds for Bregman Divergences.
  arXiv  Detail & Related papers  (2021-06-08T21:26:57Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)
• Streaming Algorithms for Stochastic Multi-armed Bandits [1.4932318540666543]
  We study the Multi-armed Bandit problem under bounded arm-memory. For regret minimization, we show Omega(T2/3) cumulative regret in expectation for arm-memory size of (n-1), where n is the number of arms. For best-arm identification, we study two algorithms. First, we present an O(r) arm-memory r-round adaptive streaming algorithm to find an epsilon-best arm.
  arXiv  Detail & Related papers  (2020-12-09T16:28:05Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially chooses actions and observes rewards for the actions it took. While the majority of algorithms try to minimize the regret, i.e., the cumulative difference between the reward of the best action and the agent's action, this criterion might lead to undesirable results. We suggest a new, more lenient, regret criterion that ignores suboptimality gaps smaller than some $epsilon$.
  arXiv  Detail & Related papers  (2020-08-10T08:30:52Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  We study a regret problem with the existence of multiple best/near-optimal arms in a bandit setting. Our goal is to design algorithms that can automatically adapt to the unknown hardness of the problem.
  arXiv  Detail & Related papers  (2020-06-26T04:01:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.