Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap

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 Delta[2]. Here, and throughout, the optimality gap Delta[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 Delta[2], a pass complexity of Theta(log(1/Delta[2])) (up to loglog(1/Delta[2]) terms) is necessary and sufficient to obtain the *worst-case optimal* sample complexity of O(n/Delta2[2]) with a single-arm memory. However, our understanding of multi-pass algorithms with known Delta[2] is still limited. Here, the key open problem is how many passes are required to achieve the complexity, i.e., O( sumi=2n1/Delta2[i]) arm pulls, with a sublinear memory size. In this work, we show that the ``right answer'' for the question is Theta(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(sumi=2n1/Delta2[i]· log(n)) arm pulls has to make Omega(fraclognloglogn) passes over the stream. We then show a nearly-matching algorithm that assuming the knowledge of Delta[2], finds the best arm with O( sumi=2n1/Delta2[i] · logn) arm pulls and a *single arm* memory.