TL;DR
This paper investigates whether it is possible to achieve optimal, "instance-sensitive" sample complexity for finding the best arm in a streaming Multi-Armed Bandit (MAB) problem using limited memory. The authors prove strong lower bounds demonstrating that achieving this efficiency with sublinear memory in a single pass is impossible without heavy assumptions. However, they complement these negative results with a novel single-arm memory algorithm that succeeds when specific conditions—such as random arrival order and known gap parameters—are met.
The Problem: Streaming Multi-Armed Bandits
In the standard "pure exploration" Multi-Armed Bandit problem, an algorithm pulls different arms to find the one with the highest expected reward while minimizing total pulls (sample complexity). In modern applications involving massive datasets or crowdsourcing, arms arrive in a continuous stream, and the algorithm cannot store all of them in memory. This is known as the streaming MAB problem.
Previous research established that achieving worst-case optimal sample complexity—$O(n/\Delta_{[2]}^2)$, where $\Delta_{[2]}$ is the reward gap between the best and second-best arm—is possible while storing only a single arm in memory. However, in non-streaming setups, algorithms can do much better by being instance-sensitive. Instead of being bottlenecked purely by the second-best arm, these algorithms scale with the gaps of all arms, achieving a much lower sample complexity proportional to $H_2 = \sum_{i=2}^n \frac{1}{\Delta_{[i]}^2} \log\log(\frac{1}{\Delta_{[i]}})$.
This paper asks a fundamental theoretical question: Can we achieve this highly efficient instance-sensitive sample complexity in a single-pass stream while still only keeping a tiny number of arms in memory?
Methodology
The authors tackle this question through both information-theoretic lower bounds and a new algorithmic upper bound:
1. The Arm-Trapping Lemma (Lower Bound)
The authors develop a novel mathematical proof demonstrating the fundamental difficulty of merely keeping the best arm in memory. They prove that any algorithm trying to output a small subset of arms ($o(n)$) that contains the best arm must use $\Omega(n/\Delta_{[2]}^2)$ pulls. By using adversarial stream constructions—placing the best arm early in the stream and hiding highly rewarding decoy arms at the end—they force algorithms into a dilemma: either over-explore early on (wasting pulls) or risk dropping the best arm from memory forever.
2. Instance-Sensitive-Game-of-Arms (Algorithm)
To prove what is possible, they design a "king of the hill" style streaming algorithm that holds exactly one "king" arm in memory. As new arms arrive, they challenge the king. To avoid the massive sample costs of previous worst-case algorithms, this new algorithm uses the known instance-sensitive complexity parameter ($H_2$) to strictly budget the number of pulls allowed for each arriving arm, iteratively refining its estimate of the best arm's true reward.
Key Insights and Results
The paper reveals a harsh reality regarding the sample-space trade-off in streaming MABs. While there is no trade-off between memory and sample complexity if you only care about worst-case bounds, the moment you try to achieve instance-sensitive bounds, a sharp trade-off emerges. You either need $\Omega(n)$ memory, or you have to sacrifice sample efficiency.
Negative Results (Lower Bounds): * The Absolute Necessity of $\Delta_{[2]}$: Without knowing the gap between the best and second-best arm ($\Delta_{[2]}$) in advance, no single-pass algorithm with $o(n)$ memory can bound its sample complexity. It will inevitably discard the best arm by mistake. * Adversarial Streams are Unsolvable: Even if $\Delta_{[2]}$ is known, achieving instance-sensitive sample complexity $O(H_2)$ with $o(n)$ memory is impossible unless the stream is randomly ordered and the algorithm knows the other gap parameters. * Trapping is as Hard as Finding: A surprising theoretical takeaway is that merely "trapping" the best arm (keeping it in a small candidate pool without necessarily knowing it is the absolute best yet) is fundamentally just as expensive as finding it outright in a streaming setting.
Positive Result (Upper Bound): * The authors provide an algorithm that uses exactly 1 arm of memory and achieves instance-sensitive sample complexity $O(H_2 + \text{poly}(\log n / \Delta_{[2]}))$. However, this requires three strong assumptions: the arms must arrive in a random order, $\Delta_{[2]}$ must be known, and the overall complexity parameter $H_2$ must be known.
Limitations and Future Work
The authors are transparent about the strict assumptions required for their algorithm. Assuming the stream arrives in a random order and that the algorithm has prior knowledge of the complexity parameter $H_2$ limits real-world applicability (though it fits scenarios where historical data provides good estimates). Additionally, their algorithm's sample complexity includes an additive polynomial term that doesn't exist in classical offline algorithms.
Future work directions include determining if this additive term is strictly necessary, exploring how allowing multiple passes over the stream might relax these harsh assumptions, and testing the empirical performance of the algorithm against existing heuristics.
Summary updated