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

2026-06-08 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, quick

Summary

"Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits" introduces a new model for multi-armed bandits (MABs) where only the most recent W arms are valid in a single-pass stream. This model extends traditional streaming MABs by incorporating a recency effect. The research provides a comprehensive analysis of both pure exploration and regret minimization problems within this framework, considering limited memory. Key findings include the difficulty of finding the exact best arm with sublinear memory, while an approximate best arm can be found efficiently. The study also defines a new notion of regret and establishes sharp memory-regret trade-offs for single-pass algorithms, supported by experimental validation.

Key takeaway

For AI scientists designing online learning systems with dynamic data streams, understanding the inherent challenges of sliding-window multi-armed bandits is crucial. Your algorithm design should account for the trade-offs between memory, exploration, and regret, recognizing that finding an exact best arm with limited memory is difficult. Prioritize efficient approximate solutions when recency effects are significant, and consider the sharp memory-regret curves when allocating computational resources.

Key insights

Sliding-window streaming MABs require balancing pure exploration and regret minimization under recency and memory constraints.

Principles

• Exact best arm finding is hard with sublinear memory.
• Approximate best arm finding is efficient.
• Sharp memory-regret trade-offs exist.

Topics

• Online Learning
• Multi-armed Bandits
• Sliding Window Algorithms
• Streaming Algorithms
• Pure Exploration
• Regret Minimization
• Memory-Regret Trade-offs

Best for: Research Scientist, AI Scientist

Related on AIssential

• Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees — UCB-AA addresses dynamic regret in multi-armed bandits where new arms arrive sequentially, improving efficiency.
• RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems — RELOAD improves RL-based query optimization by enhancing robustness and accelerating convergence to expert-level plan quality.
• ARROW: Augmented Replay for RObust World models — Augmented replay to a World Model significantly reduces catastrophic forgetting in continual reinforcement learning.
• Regret Minimization with Adaptive Opponents in Repeated Games — Repeated Policy Regret (RP-Regret) enables finding higher-utility equilibria in repeated games by modeling adaptive opponents and dynamic strategies.
• Best of both worlds: Stochastic & adversarial best-arm identification — Optimal best-arm identification across both stochastic and adversarial bandit rewards is generally impossible.
• Batched Single-Index Global Multi-Armed Bandits with Covariates — BIDS is a novel batched multi-armed bandit algorithm that uses single-index regression to efficiently manage covariates and related arm rewards.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.