A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits

The stochastic K-armed bandit problem has been studied extensively due to its applications in various domains ranging from online advertising to clinical trials. In practice however, the number of arms can be very large resulting in large memory requirements for simultaneously processing them. In this paper we consider a streaming setting where the arms are presented in a stream and the algorithm uses limited memory to process these arms. Here, the goal is not only to minimize regret, but also to do so in minimal memory. Previous algorithms for this problem operate in one of the two settings: they either use Omega(log log T) passes over the stream (Rathod, 2021; Chaudhuri and Kalyanakrishnan, 2020; Liau et al., 2018), or just a single pass (Maiti et al., 2021). In this paper we study the trade-off between memory and regret when B passes over the stream are allowed, for any B ≥ 1, and establish tight regret upper and lower bounds for any B-pass algorithm. Our results uncover a surprising *sharp transition phenomenon*: O(1) memory is sufficient to achieve widetildeThetaBig(T^frac12 + frac12B+2-2Big) regret in B passes, and increasing the memory to any quantity that is o(K) has almost no impact on further reducing this regret, unless we use Omega(K) memory. Our main technical contribution is our lower bound which requires the use of information-theoretic techniques as well as ideas from round elimination to show that the *residual problem* remains challenging over subsequent passes.