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 tilde Oleft((n-m)^1+frac2P-22P+1-1 n^frac2-2P+12P+1-1 T^frac2P2P+1-1right) regret and complement it with an tilde Omegaleft((n-m)^1+frac2P-22P+1-1 n^frac2-2P+12P+1-1 T^frac2P2P+1-1right) lower bound when the number of rounds T is sufficiently large. Our results are tight up to a logarithmic factor in n and P.