2025/02/03 by Nikolai Karpov, Chen Wang, Karpov, Nikolai +1
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.2502.01067
openalex publication_date 2025/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the sample-memory-pass trade-offs for pure exploration in multi-pass streaming multi-armed bandits (MABs) with the *a priori* knowledge of the optimality gap Δ[2]. Here, and throughout, the optimality gap Δ[i] is defined as the mean reward gap between the best and the i-th best arms. A recent line of results by Jin, Huang, Tang, and Xiao [ICML'21] and Assadi and Wang [COLT'24] have shown that if there is no known Δ[2], a pass complexity of Θ(log(1/Δ[2])) (up to loglog(1/Δ[2]) terms) is necessary and sufficient to obtain the *worst-case optimal* sample complexity of O(n/Δ2[2]) with a single-arm memory. However, our understanding of multi-pass algorithms with known Δ[2] is still limited. Here, the key open problem is how many passes are required to achieve the complexity, i.e., O( ∑i=2n1/Δ2[i]) arm pulls, with a sublinear memory size. In this work, we show that the ``right answer'' for the question is Θ(logn) passes (up to loglogn terms). We first present a lower bound, showing that any algorithm that finds the best arm with slightly sublinear memory -- a memory of o(n/polylog(n)) arms -- and O(∑i=2n1/Δ2[i]⋅ log(n)) arm pulls has to make Ω(\fraclognloglogn) passes over the stream. We then show a nearly-matching algorithm that assuming the knowledge of Δ[2], finds the best arm with O( ∑i=2n1/Δ2[i] ⋅ logn) arm pulls and a *single arm* memory.