On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck

2021/11/30 by Santanu Rathod, Rathod, Santanu
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2112.06130

openalex publication_date 2021/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work we explore multi-arm bandit streaming model, especially in cases where the model faces resource bottleneck. We build over existing algorithms conditioned by limited arm memory at any instance of time. Specifically, we improve the amount of streaming passes it takes for a bandit algorithm to incur a O(√(Tlog(T))) regret by a logarithmic factor, and also provide 2-pass algorithms with some initial conditions to incur a similar order of regret.

Related

• Tight Memory-Regret Lower Bounds for Streaming Bandits
• A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
• Streaming Algorithms for Stochastic Multi-armed Bandits
• Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits