Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity

Sepehr Assadi, Chen WangNeurIPS 2022 · OpenReview

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

Abstract

Motivated by applications to process massive datasets, we study streaming algorithms for pure exploration in Stochastic Multi-Armed Bandits (MABs). This problem was first formulated by Assadi and Wang [STOC 2020] as follows: A collection of $n$ arms with unknown rewards are arriving one by one in a stream, and the algorithm is only allowed to store a limited number of arms at any point. The goal is to find the arm with the largest reward while minimizing the number of arm pulls (sample complexity) and the maximum number of stored arms (space complexity). Assuming $\Delta_{[2]}$ is known, Assadi and Wang designed an algorithm that uses a memory of just one arm and still achieves the sample complexity of $O(n/\Delta_{[2]}^2)$ which is worst-case optimal even for non-streaming algorithms; here $\Delta_{[i]}$ is the gap between the rewards of the best and the $i$-th best arms.In this paper, we extended this line of work to stochastic MABs in the streaming model with the instance-sensitive sample complexity, i.e. the sample complexity of $O(\sum_{i=2}^{n} \frac{1}{\Delta_{[i]}^2}\log\log{(\frac{1}{\Delta_{[i]}})})$, similar in spirit to Karnin et.al. [ICML 2013] and Jamieson et.al. [COLT 2014] in the classical setting. We devise strong negative results under this setting: our results show that any streaming algorithm under a single pass has to use either asymptotically higher sample complexity than the instance-sensitive bound, or a memory of $\Omega(n)$ arms, even if the parameter $\Delta_{[2]}$ is known. In fact, the lower bound holds under much stronger assumptions, including the random order streams or the knowledge of all gap parameters $\{\Delta_{[i]}\}_{i=2}^n$. We complement our lower bounds by proposing a new algorithm that uses a memory of a single arm and achieves the instance-optimal sample complexity when all the strong assumptions hold simultaneously.Our results are developed based on a novel arm-trapping lemma. This generic complexity result shows that any algorithm to trap the index of the best arm among $o(n)$ indices (but not necessarily to find it) has to use $\Theta(n/\Delta_{[2]}^2)$ sample complexity. This result is not restricted to the streaming setting, and to the best of our knowledge, this is the first result that captures the sample-space trade-off for `trapping' arms in multi-armed bandits, and it can be of independent interest.
BibTeX
@inproceedings{assadi2022single,
  author = {Sepehr Assadi and Chen Wang},
  title = {{Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=OIguPajE0Nf},
}
Figure