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 ${\mathrm{\Delta }}_{[2]}$. Here, and throughout, the optimality gap ${\mathrm{\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 ${\mathrm{\Delta }}_{[2]}$, a pass complexity of $\mathrm{\Theta }(\log (1\mathrm{/}{\mathrm{\Delta }}_{[2]}))$ (up to $\log \log (1\mathrm{/}{\mathrm{\Delta }}_{[2]})$ terms) is necessary and sufficient to obtain the worst-case optimal sample complexity of $O(n\mathrm{/}{\mathrm{\Delta }}_{[2]}^2)$ with a single-arm memory. However, our understanding of multi-pass algorithms with known ${\mathrm{\Delta }}_{[2]}$ is still limited. Here, the key open problem is how many passes are required to achieve the complexity, i.e., $O({\sum }_{i=2}^{n}1\mathrm{/}{\mathrm{\Delta }}_{[i]}^2)$ arm pulls, with a sublinear memory size. In this work, we show that the ``right answer’’ for the question is $\mathrm{\Theta }(\log n)$ passes (up to $\log \log n$ 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\mathrm{/}\text{polylog}(n))$ arms – and $O({\sum }_{i=2}^{n}1\mathrm{/}{\mathrm{\Delta }}_{[i]}^2\cdot \log (n))$ arm pulls has to make $\mathrm{\Omega }(\frac{\log n}{\log \log n})$ passes over the stream. We then show a nearly-matching algorithm that assuming the knowledge of ${\mathrm{\Delta }}_{[2]}$, finds the best arm with $O({\sum }_{i=2}^{n}1\mathrm{/}{\mathrm{\Delta }}_{[i]}^2\cdot \log n)$ arm pulls and a single arm memory.