Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits

We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). 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 establish tight non-asymptotic regret bounds regarding all relevant parameters, including the number of arms n, the memory size m, the number of rounds T and (Deltai)i∈ [n] where Deltai is the reward mean gap between the best arm and the i-th arm. These gaps are not known in advance by the player. Specifically, for any constant α ≥ 1, we present two algorithms: one applicable for m≥ frac23n with regret at most OαBig(frac(n-m)T^frac1α + 1n^1 + frac1α + 1displaystylesumi:Deltai > 0Deltai1 - 2αBig) and another applicable for m<frac23n with regret at most OαBig(fracT^frac1α+1m^frac1α+1displaystylesumi:Deltai > 0Deltai1 - 2αBig). We also prove matching lower bounds for both cases by showing that for any constant α≥ 1 and any m≤ k < n, there exists a set of hard instances on which the regret of any algorithm is OmegaαBig(frac(k-m+1) T^frac1α+1k^1 + frac1α+1 sumi:Deltai > 0Deltai1-2αBig). This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an OBig(sumicolonDelta>0 frac√Tlog TDeltaiBig) upper bound for the special case of α=1 and m=O(1) was established by Agarwal, Khanna and Patil (COLT'22). In contrast, our results provide the correct order of regret as ThetaBig(frac1√msumicolonDelta>0frac√TDeltaiBig).