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

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 statistics can be stored in the memory. We give a complete characterization of the optimal regret in terms of $m, n$ and P. Specifically, we design an algorithm with O((n-m)^1+2P-22P+1-1 n^2-2P+12P+1-1 T^2P2P+1-1) regret and complement it with an Ω((n-m)^1+2P-22P+1-1 n^2-2P+12P+1-1 T^2P2P+1-1) lower bound when the number of rounds T is sufficiently large. Our results are tight up to a logarithmic factor in n and P.