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

Abstract

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 $\log \log (1/{\Delta }_{[2]})$ terms) is necessary and sufficient to obtain the *worst-case optimal* sample complexity of $O(n/{\Delta }_{[2]}^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({\sum }_{i=2}^{n}1/{\Delta }_{[i]}^2)$ arm pulls, with a sublinear memory size. In this work, we show that the ``right answer'' for the question is $\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/\text{polylog}(n))$ arms -- and $O({\sum }_{i=2}^{n}1/{\Delta }_{[i]}^2\cdot \log (n))$ arm pulls has to make $\Omega (\frac{\log n}{\log \log n})$ passes over the stream. We then show a nearly-matching algorithm that assuming the knowledge of ${\Delta }_{[2]}$, finds the best arm with $O({\sum }_{i=2}^{n}1/{\Delta }_{[i]}^2\cdot \log n)$ arm pulls and a *single arm* memory.

AAAI 2025