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 (Δᵢ)i∈ [n] where Δᵢ 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≥ 2/3n with regret at most O_α((n-m)T1/α + 1n^1 + 1/α + 1∑i:Δᵢ > 0Δᵢ1 - 2α) and another applicable for m<2/3n with regret at most O_α(T1/α+1m1/α+1∑i:Δᵢ > 0Δᵢ1 - 2α). 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 Ω_α((k-m+1) T1/α+1k1 + 1/α+1 ∑i:Δᵢ > 0Δᵢ1-2α). This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an O(∑iΔ>0 √Tlog TΔᵢ) 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 Θ(1√m∑iΔ>0√TΔᵢ).