TL;DR
This paper tackles the challenge of efficiently finding the best option (arm) in a streaming environment where options arrive sequentially and memory is limited. The authors establish near-optimal bounds for how many times you need to revisit the data (passes) and how much memory you need, specifically when you have some prior knowledge about how "good" the options are (the optimality gap). This work fills a crucial theoretical gap in understanding the trade-offs for efficient exploration in these constrained settings.
What Problem Does This Paper Address?
Imagine you're trying to find the best product to recommend to users, but new products (arms) are constantly being added to your catalog (stream). You can't store all product information in memory, and you can only process the stream a limited number of times. This is the essence of the "streaming multi-armed bandit" (MAB) problem. Specifically, this paper focuses on the "pure exploration" variant, where the sole goal is to identify the best arm, not to balance exploration and exploitation.
A key challenge in MABs is the "optimality gap" – the difference in reward between the best arm and any other arm. Knowing this gap can significantly improve efficiency. While previous work has established bounds for scenarios where this gap is unknown or when aiming for worst-case optimal sample complexity, a critical open question remained: what are the tightest bounds for finding the instance-optimal solution when the optimality gap is known and memory is limited? This paper aims to answer this by characterizing the interplay between the number of passes over the data stream, the memory required, and the sample complexity (total number of pulls).
Methods
The paper's core contribution lies in establishing tight theoretical bounds. They achieve this by:
- Lower Bound: They construct a challenging instance distribution designed to be difficult for any algorithm with limited memory and a known optimality gap. This construction, inspired by prior work on MABs without known gaps, is adapted to specifically test the limits of algorithms when the optimality gap is provided. The key idea is to create a scenario where the optimality gap remains constant across different "batches" of arms, making it hard to distinguish between arms based solely on that gap. This leads to a lower bound of $\Theta(\log \log n)$ passes.
- Upper Bound: They propose a novel streaming algorithm that achieves near-optimal performance. This algorithm uses an "elimination-based" approach, similar to classical MAB algorithms, but adapted for the streaming and multi-pass setting. A crucial innovation is how they set the "elimination gaps" across passes. Instead of a fixed strategy, they use a geometric series that depends on the total number of passes ($P$) and the known optimality gap ($\Delta_{[2]}$). This allows them to achieve the desired sample complexity with a single-arm memory and $O(\log n)$ passes.
Datasets
The paper does not use pre-existing datasets. Instead, they introduce a novel "batched instance distribution" specifically designed to challenge streaming MAB algorithms. This distribution is parameterized by $P$ (number of passes), $C$, and $\gamma$ (related to the optimality gap). They also conduct experiments on "uniform setting" instances where arm rewards are drawn from a uniform distribution on $[0, 1]$.
Key Insights and Ideas
- The Power of Known Optimality Gap: Knowing the optimality gap ($\Delta_{[2]}$) significantly reduces the required number of passes from potentially polynomial in $n$ (when unknown) to logarithmic ($O(\log n)$) for instance-optimal sample complexity.
- Sharp Memory-Pass Trade-off: The paper demonstrates a clear trade-off: with $O(\log n)$ passes, a single-arm memory is sufficient. Conversely, if you try to do it in fewer passes ($o(\log n / \log \log n)$), you'd need almost full memory ($o(n)$ arms).
- Bridging Theory and Practice: The proposed algorithm not only achieves theoretical near-optimality but also shows strong empirical performance, outperforming existing methods in terms of both sample complexity and passes.
- A New Lower Bound Construction: The paper contributes a new technique for constructing lower bounds in streaming MABs, particularly for scenarios where the optimality gap is known. This involves carefully designing instances to exploit the limitations of memory and pass constraints.
Key Results
- Lower Bound: Any streaming algorithm with $o(n/\text{polylog}(n))$ memory and a known optimality gap $\Delta_{[2]}$ requires $\Omega(\log \log n)$ passes to find the best arm with high probability and near instance-optimal sample complexity.
- Upper Bound: The authors present a $(P+1)$-pass streaming algorithm that finds the best arm with a single-arm memory and $O(\sum_{i=2}^n \frac{1}{\Delta_{[i]}} \log n)$ arm pulls. By setting $P = O(\log n)$, this matches the lower bound, achieving $O(\log n)$ passes.
- Empirical Validation: Experiments show that their algorithm achieves lower sample complexity and requires significantly fewer passes compared to existing single-pass (AW) and multi-pass (JHTX) algorithms, especially in uniform settings.
Limitations and Future Work
- Generalization of Sub-Gaussian: While the paper states results apply to general sub-Gaussian distributions, the formal proofs and constructions are primarily detailed for Bernoulli distributions. Further work could explore the nuances of other sub-Gaussian families.
- Shaving the Log-Log Term: A natural open problem is whether the $\Omega(\log \log n)$ lower bound on passes can be improved, or if an algorithm can achieve this without the $\log \log n$ factor.
- Sample Complexity Dependence on Passes: The paper's upper bound has a sample complexity that depends on the number of passes $P$. An interesting future direction is to derive a sample lower bound that explicitly depends on $P$, mirroring the structure of their upper bound.
Summary updated