Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits

2024/05/30 by He, Yuchen, Ye, Zichun, Zhang, Chihao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2405.19752

Abstract

We study the stochastic multi-armed bandit problem in the P-pass streaming model. In this problem, the n arms are present in a stream and at most m

Related

• A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
• Streaming Algorithms for Stochastic Multi-armed Bandits
• Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
• On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck
• Tight Memory-Regret Lower Bounds for Streaming Bandits