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

Yuchen He, Zichun Ye, Chihao Zhang

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<n$ arms and their statistic…