Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
Authors: Sepehr Assadi
Chen Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Pure Exploration Multi-armed Bandits
Streaming Lower Bounds
Sublinear algorithms for machine learning
Large-scale Learning

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.

Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
Sepehr Assadi
Chen Wang
Department of Computer Science Rutgers University Piscataway, NJ 08854
Department of Computer Science Rutgers University Piscataway, NJ 08854 chen. wang cserutgerrss.... edu
sepehr assadi errssadirutgerss.oo edu
Abstract
Motivated by applications process massive datasets, we study streaming algo- rithms 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 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 [ is known, Assadi and Wang designed an algorithm that uses memory of just one arm and still achieves the sample complexity of Onn/ A which is worst-case optimal even for non-streaming al algorithms; here Áμ is the gap between the rewards of the best and the i-th best arms.
In this paper, we extended this line of work stochastic MABs in the streaming model with the mnstance-sensitiie sample complexity, i.c. the sample complexity O A7 log log (2,,)); similar in spirit to Karnin et.al. [ICMI. 2013] and
Jamieson et.al. [COLT 2014] 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 ((n) arms, even if the parameter Ap) is known. fact, the lower bound holds under much stronger assumptions, including the random order streams the knowledge of all gap parameters {A Y We complement our lower bounds by proposing a new algorithm that uses memory of single arm and achieves the instance-optimg sample complexity when all the strong assumptions hold simultancously.
Our results are developed based on novel arm trapping lemma. This generic complexity result shows that any algorithm to trap the index of the best arm among onn) indices (but not necessarily to find it) has to use (nn/ ) sample complexity. This result our knowledge, this the first result that captures the sample-space trade-off for 'trapping' arms in multi-armed bandits, and can be of independent interest.
restricted to the streaming setting, and to the best of
Introduction
The stochastic multi-armed bandits (MABs) is one of the most well-known models in machine learning and theoretical computer science. this model, we are given n arms with unknown reward
Author names are in alphabetical order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

distributions, and we are required to find some arms for certain goals. The pure exploration version of the stochastic MABs studies how to find the best arm(s). and it has been extensively investigated
in the literature 20 33
15 The model captures many fundamental problems in finding the best items among many, has various applications in experiment design [36] 9)
6
25 26 23 3
28
crowdsourcing [16 43 10), search ranking [99 [3 35),
networking 422 40], and others.
We study the problem of finding the best (one) arm in stochastic MABs. Since the distribution of the rewards is unknown, the natural strategy is to pull each arm multiple times and use the empirical rewards to find the best arm. Accordingly, the goal of the algorithms in this problem is to identify the best arm with high constant probability and number of arm pulls (sample complexity) that is as small as possible. Following the classical upper bound of (20] and lower bound of [3], it is well known that (n//2 (y)) arm pulls are both necessary and sufficient throughout, A is the gap between the rewards of the best and the i-th-best arms. Going beyond worst-case, the main focus of the literature has been on obtaining instance-sensifive algorithms for the problem, resulting in
algorithms of and 26 with O 27 log log
قفف arm pulls (see also [.5 and references
therein for various extensions). This upper bound has at most a doubly-logarithm gap from known instance-optimal lower bounds [33 23 15.
Almost the entirety of algorithms in the literature for best arm identification require the entire set of the arms to be repeatedly visited, and therefore, memory of Q(n) arms is inevitably needed. More recently, motivated by applications to processing massive number of arms (e.g., in online advertisements) or the situations when the arms are arriving online (e.g. crowd-sourcing), the space requirements of algorithms for stochastic MABs has also received considerable attention [5] 31 In particular, [5] recently formulated and studied the problem of pure exploration in streaming stochastic multi-armed bandits. In their model, the arms arrive one by one in a stream, and the algorithm can only output or pull past arm if it is stored. The largest number of arms stored at any point is named the space complexity; see also 31 30 24 ( designed an algorithm that given arm pulls the knowledge of Ap2), finds the best arm with high constant probability using O (/))
32 12 30 2]
and memory of a single arm.
The algorithm of (5] achieves the worst-case optimal sample and space complexity simultaneously. thus asserting that no trade-off is needed between the sample and space for this problem. On the flip side, this upper bound is only worst-case optimal and not instance-sensitiee shows that if we are allowed to make (log( ( 2/D passes over the stream, is possible to find
In a recent result, [24]
the best arm with the instance-sensitive sample complexity in the same spirit of [23] 26]. and only
use a single-arm memory. However, allowing (loo //D))) passes seems to be a strong condition
especially in streaming applications. Therefore, a natural open question is whether we can achieve Destacce-sensitive sample complexity, while maintaining a small memory, preferably still a single arm, in single pass of the streaming model.
The main result of this paper is that finding the best arm with the mnstance-sensitive sample complexity in single pass is indeed hard: if we are only given the parameter A any single-pass streaming algorithm must either use asymptotically higher sample complexity than the instance-sensitive bound, or use memory of M(1) arms. Furthermore, the lower bound holds even if we are given additional strong assumption of either (i) the arms arrive in a random order or (ii) the parameters of all reward gaps { (A Y En route to proving the above lower bounds, also provide an even stronger lower bound for single-pass streaming algorithms without any parameter (not even Apy): we show that in such a case, any single-pass pass streaming algorithm with memory of o(n) has to use an unhounded sample complexity. Finally, we complement our lower bounds with single-pass streaming algorithm that uses a single-arm memory and achieves the instance-sensitive sample complexity. if given the parameter Ayy and conditions of both random order stream and a known quantity of the instance- sensitive sample complexity, where the latter is a weaker condition than (it).
1.1 Instance-sensitive Sample Complexity
As stated earlier, the worst-case sample complexity of stochastic MABs is O(n/Ag)) However, in most instances of interest, one can hope for much better sample complexity that exploits the rewards of different arms in more fine-grained way. This is the basic idea behind instance- sensitive algorithms that have received significant attention in the context of stochastic MABs. We follow the same approach in this paper. In particular, we aim to achieve the sample complexity
2

---

of CE log logl - arm pulls the same bound achieved by classical algorithms for Af non-streaming stochastic MABs [23 [26].
A
Following the standard notation used in the literature 23
26
we denote the reward gap between
the best and the i-th best arm as At: As such, we use {
(
N to denote the set of all gap
parameters. The standard settance-sessitine complexity is as follows:
H
H
Σ 1=
1
log log
A
The algorithms of 23
26 use (H2) arm pulls. It is worth noting that no known algorithm has achieved the OH sample complexity, and whether w(H1) sample complexity is necessary is an open problem even in the offline setting. As such, we only focus on the ((H2) sample complexity in this paper. The term ((lmostt instance-sensine
is derived from "instance-optimal" [ [5]. We use such term an analogy to the "truly instance-optimal" ((H)) sample complexity, and this term is shared by recent work like [27]. Moreover, since there is a factoor difference between H2 and the mnstance-sensitvv sample complexity (i.e., H₂ vs. (HH)), we denote the latter as INST-complexity in this work.
in the literature [3
1.2 Our Contributions
Our main contribution is set of lower bounds showing that it is almost impossible achieve the instance-sensitiv sample complexity with low memory for any single-pass streaming algorithm. Moreover, no parameter is provided (especially Ap] is not known), it impossible achieve any bounded sample complexity with low memory:
Result 1 (Informal). There are families of stochastic multi-armed bandits instances such that:
ii) If the knowledge of d is provided, but the knowledge of all other gap parameters (=))= and the random arrival of arms are not both provided, the sample complexity of any single-pass streaming algorithm with o)n) -arm memory is w (H2)).
(ii) the knowledge of Arg is not provided and other parameter is provided, the sample complexity of any single-pass streaming algorithm with o(ni)-rmm memory is unbounded as function of n and Ag2;
Note that (i) of Result captures three cases: only A/2 is known; A|2) is known and the stream is in a random order; and all the gap parameters { ( a /r are known (but the stream is in an adversarial order). Compared to the positive results in [5]. our lower bounds rule out any mnstance-sensitive algorithms under the same parameter settings. Moreover, they provide a strong, justificatiii for the knowledge of Ag2 in the algorithm of (5) (and any streaming MAB algorithms).
Another remark of Result is the separation of the complexity for multi-armed bandits under the streaming and the classical models. The algorithm in [5) implies that with the worst-case sample complexity and known Ayyj- there is no separation of hardness for pure exploration MABs between the streaming and the classical settings, i.e. no sample-space trade-off. On the other hand, our results suggest that if we switch to the regime of instance-sensine assumption of Arg)- sample-space trade-off starts to emerge (note that there exist algorithms that achieve O O(H)) sample complexity without the knowledge of [ under the classical setting).
sample complexity, or if we remove the
To complement the lower bounds, we design an algorithm that uses a single arm memory and achieves instance-sensitive sample complexity when A22] is not too small. The algorithm is conditioned on the knowledge of A and both the random order stream and the knowledge of INST-complexity. The latter condition, combined with the knowledge of Agg] a weaker form of all gap parameters one can certainly compute H₂ if parameters (4 Vi= are given.
Result 2 (Informal). Assuming the knowledge of A12) and INST-complexity, and when the arms arrive in a random order, there is a streaming algorithm that finds the best arm in streaming stochastic multi-armed bandits with O (22 + poly( ( Aيg
logn arm pulls and a memory of a single
arm with high (constant) probability.
We should note that the sample complexity of our algorithm in Result has an additive term compared to the ((H)) obtained in the non-streaming setting [23 26). This term however is typically negligible

---

except for pathological cases where A22 is extremely small compared to both average values of A 's and the number of arms.
A key ingredient of our proof towards Result 1 is an arm-trapping lemma that characterizes the hardness to keep the arm in the memory, shown as below:
Result 3 (Arm-trapping lemma, informal). There are families of stochastic multi-armed bandits instances such that any algorithm that outputs o(n) arms that contains the index of the best arm (with high constant probability) has use Q
arm pulls. As a result, any single-pas, pass streaming algorithm that keeps the best arm by the end of the stream (with high constant probability) has to use either
arm pulls or an - memory.
A
To the best of our knowledge, this is the first Multi-armed Bandits lower bound that explicitly establishes trade-off between sample and space complexity for trapping an and Note that this statement is stronger than the usual lower bounds on finding arms: our lower bound holds even if the algorithm is only required to output a collection of indices that contains the index of the best arm (possibly without knowing which arm is the best).
1.3 Related Work
Originated in the work of Robbins 36 almost 70 years ago, the study of stochastic MABs ba- sically follows two popular branches: the pure exploration problem, which aims to find the best 15]; and the inloorattooneepliiaattiii
arm 20 3 13
problem, which focus on the regret Covering the vast literature on regret minimization is beyond the scope of this paper but we should note that even regret minimization is studied in streaming setting
28
11
minimization
12
although mostly for multi-pass algorithms 31 12 30 2
The worst-case optimal bounds on the sample complexity of exploration problem was established by 20 (upper bound) and [33] (lower bound). Besides the best arm identification, (20) also introduced the s-best arm variation of the pure exploration problem. The problem is motivated by learning under the PAC(e, -frmmerwo where the algorithm aims to find an arm with reward at most s-far from the best arm. The e-best arm problem is also studied extensively. It has recently been considered in the streaming model as well by [1 who designed streaming algorithms for g-best arm problem with ((1) memory and (nn/²²) arm pulls
(we (we note that [31 also designed a heuristic for this problem on random streams with O(1) memory that works well empirically but does not have the same theoretical guarantee).
The instance-sensine sensitive sample complexity of O (H2) was first achieved by [26], followed up by 23 who achieved the same asymptotic complexity but better performance in practice. 2X also
discovered that for the problem with 2 arms, Q x log log( 3 )) arm pulls are necessary - lower
bound that is due to a classical result of 21 from over half of a century ago. 23 conjectured that the lower bound holds for arms (and the complexity will be "instance-optimal" ); nonetheless, later
work by [3] shows that for some instances, an algorithm with O 27
arm pulls is possible
and formulated a 'gap-entropy' conjecture for capturing the instance-optimal bounds (see 15 for further progress on this conjecture).
2
Preliminaries
Problem Definition
The formal description of the stochastic multi-armed bandit model that we study is as follows. Problem 1 (Pure exploration MABs). There is a set of n arms {arm,) with unknown rewards, each following a sub- lub-Gaussian distribution with means {p: 1n Our goal is to find the best arm with the highest expected reward, i.e., Pi, by pulling them and observing the empirical rewards.
By definition, we need to solve Problem with randomized algorithms. As such, we aim to design algorithms that find the best arm with high constani probability. The reason to not consider the high
2 A concurrent work 2 presents streaming MABs lower bound with a different sample-spac trade-off.
3 'The algorithms in 5 31 uses log" (n)-arm memory. A newer version of the algorithm in [5] achieves
(11) arm memory, and 24 takes different approach which arrives at the same asymptotic guarantees.

---

1 is that it is impossible to get such high success probability without an probability of 1 - poly(n)
(llo((n) multiplicatiie factor to the sample complexity, which is considered large in the literature. We study [Problem I Junder the streaming model, which means the arms arrive one by one from the set; for each arriving arm, the algorithm can pull it multiple times to observe the empirical reward or store the memory (so it can be pulled later). However, if an arm not stored, it is lost forever and the algorithm can neither pull nor restore it. We refer to the number of arm pulls by the algorithm as the sample complexity, and the maximum number of arms stored as the spuce complexity.
The sample complexity of stochastic MABs is characterized by the gap parameters {A (A1))22> which denotes the difference between the reward of the best arm and the arm with the i-th highest reward. By definition, we have (Ag < [3] < ... < pn)) We assume that these parameters are greater than - an assumption that is common in the literature 220 25 17 381 Note that the gap parameters not necessarily given to the algorithm, although it is common to assume the knowledge of App- In fact, we provide a comprehensive treatment to the necessity of the Ag in this work.
It is impossible to cover all of the wide range of assumptions used in the MABs literature. As such, we restrict our attention to the following set of assumptions and conditions.
The knowledge of pp]-
(it) The (uniform) random order of arm arrival.
(181) The knowledge of additional gap parameters {A
(iv)
The knowledge of the INST-complextyy H2 (or Hş); the instance-sensitive sample complexity.
Note that conditions and 1822 forms stronger condition than conditions i can be computed given the former, but not vice versa.
tte latter
3 The Arm Trapping Lemma
Our lower bounds are built upon an arm trapping lemma, which is a information-theoreli sample- space trade-off for any algorithm to 'trap' the best arm (not restricted to the streaming setting). Compared to the classical lower bounds for finding arms in stochastic MABs, our lemma stands out by showing that even trapping the best arm (possibly without knowing which one is the best among the trapped arms) requires a lot of arm pulls. As a direct corollary, we show that for any streaming algorithm with a memory of o(n) arms, storing the best arm in the stream takes 2 a arm pulls.
A2
Our hard distribution for the arm-trapping lemma is quite natural: consider a collection of n arms with one of them having a reward of 2. and all other arms having reward of N/2 - 3 for some B. The high level idea behind the proof is non-standard reduction from this problem to the problem of distinguishing whether the reward of a single arm is 1/2 1/2 3; problem that provably requires 0(1/3?) samples. The reduction places this 'special arm' in a collection of n - arms with reward 1/2 - B, uniformly permute them, and then gives them input to any algorithm that can supposedly contradict Lemma 3.1 The proof then shows that if the algorithm can only place this special arm with non-trivial probability among the output 'trap' set, this arm actually has reward of 1/2 and not 1/2 - B. Combining this with a simple 'direct sum style' argument then proves the lower bound. We now formally define the hard family of instances as follows.
DIST: A hard distribution for trapping the best arm
1. An index i" sampled uniform at random from [n]].
For * i", let the arms be with reward p; = 2 B.
3. For i = i", let the arm be with reward p.- 1
Based on the definition of DIST, we can give the formal statement of our streaming arm trapping lemma.
Lemma 3.1 (Arm Trapping Lemma). Any algorithm that outputs (indices of) 8 arms which contains
the best arm DIST with probability at least 2/f has use at least T200 32 arm pulls.
The proof of Lemma 3.T
follows a (non-standard) reduction from the complexity to distinguish two arms with 3-reward gap, specified as follows:
5

---

Lemma 3.2. Consider an arm with the reward from the following distribution
*p =p= 2 with probability b;
* pp= 2 3. with probability 1 2'
Any algorithm to determine the reward of the arm with 3 < : and a success probability of at least has to use
7 12
144 B2 arm pulls.
Lemma 3.2 is an tiieooetiinntheorettic lower bound similar to the ones in [33 The bound shows that for any algorithm to distinguish an arm with reward either 3 or (2 - 33,, it has to pull the arm B times (if sufficiently small). This argument standard and is provided for completeness as similar results, such as classical Farrell's s bound [21 23 [3], have just subtle differences with this bound, which in fact prohibits us from using them. Limited by space, we defer the proof's of Lemma 3.1 and Lemma 3.2 to Appendix C.
As natural corollary of Lemma 3.1 any single-pase passs streaming algorithm to store the best arm with
memory of o(n) arms has to use S
arm pulls.
Corollary 3.3. Any streaming algorithm that stores the best arm on DIST with a memory of 8 arms
with probability at least 2 has to use Q
arm pulls.
33
Corollary 3.3 gives a powerful tool to prove space lower bounds in streaming MABs by exploiting the dilemma between necessity of the exploration of best arm in the early part of the stream and the cost of doing so. In particular, consider instances where (n)) arms follow DIST in Corollary 3.3 appear in the first part of the stream, and few arms by the end of the stream are either with very high or with very low rewards. If the algorithm explores the best arm in the earlier stream, risks to 'waste' a large number of arm pulls since the late arm high-reward case renders the exploration unnecessary. On the other hand, if the algorithm decides to forgo the best arm in the earlier part, it runs the risk that the late arms are with very low rewards, and the best arm will be missed.
4 Streaming Lower Bounds for Multi-armed Bandits with Instance-sensitive Sample Complexity
In this section, we provide the main lower bounds for single-pass streaming MABs. On the high level, our lower bound states that for any streaming algorithm with memory of o(n) arms that finds the best arm, if some parameters are not given, the sample complexity of the algorithm can be far more than the instance-sensitive θ (Hz) or even unbounded.
Remark 4.1. To be consistent with the definition of streaming MAB, in our lower bounds, we only measure the space of the algorithms in terms of the number of arms they store; the algorithms otherwise are allowed to maintain any arbitrary statistics on the input. What we show in all these lower bounds is that if the sample complexity is "small", then at some point the algorithm must have mistakenly discarded the best arm from its memory without the knowledge of even the index of this arm; thus the end of the stream, the algorithm has no way of recovering the best arm (even given the arbitrary statistics it has collected).
4.1 A lower bound without the knowledge of A and other parameters
We begin with showing that if no additional parameter provided other than the stream itself, the sample complexity can be arbitrarily high, and even O(n/ (2)) arm pulls are not sufficient. In fact, we show that in this case, the sample complexity cannot be bounded as function of n and App. In contrast, the algorithm in [1. which assumes the knowledge of A(2]. achieves O P arm pulls with the memory of single arm. Therefore, our lower bound asserts the importance of A for exploring the best arm under the streaming model.
Theorem 1. For any function J (0, + (0, 1), there always exists family of streaming stochastic multi-armed bandit instances, such that any algorithum to find the best arm with a memory of n-1 arms and a success probability of at least has to use w
arm pulls, if no furthe knowledge (())))))
other than the arms themselves are provided.
On the high level, the adversarial distribution for Theorem as follows. We let the first (n - 1) arms in the stream to follow DIST in Corollary 3.3 and the last arm to have either very high or

---

very low reward, with probability 2/2 each. As such, to guarantee a high enough success probability, the algorithm needs to trap the arm with the p reward among the first (n 1) arms. However, the sample complexity to keep such an arm becomes unbounded when the last arm is with a very high reward. We defer the proof of Theorem to Appendix B.T
4.2
Instance-sensitive Lower bounds with the knowledge of A
Going beyond the case where none of the conditions are given, we now show the lower bound with Au provided. Recall that [3] already solved the problem with O - arm pulls; therefore, it is
[2)
pointless to expect any result as strong as Theorem Instead, we prove lower bound of w (H2) by
exploiting the gap between θ (n/A and θ (H2). We first present the lower bound with only the knowledge of A2)-
Theorem 2. There exists a family of streaming stochastic multi-armed bandit instances, such that given the knowledge of (2), any algorithm to find the best arm with a memory of m arms and
success probability of at least has to use w (22)
(E
log log
Aru arm pulls.
We have noted that it is pointless to expect any result as strong as Theorem Indeed, the hard distribution in SSection 4.1 does not work anymore - by the change of the reward of the final arm, the value of [ر2 is 3 in one case and _/ >> an algorithm can determine whether to store the best arm among the first (n 1) arms, which makes the distribution impossible to 'fool' the algorithm.
the other. Therefore, by simply checking the parameter,
As an alternative idea, we modify the distribution of the instances to satisfy the following properties. Firstly, it forces the algorithm to make S2( 2 arm pulls to find the best arm. Secondly, it leaves a
large gap between A[ and other [1]. Vi 2 2 such that there is w (H2). And finally, Apa is static (the same version) for all the instances.
Limited by space, we defer the formal proof of Theorem to Appendix B.2 We also remark that the proof of Theorem 2] works under an approximate knowledge of Ap2, which can lead to slightly stronger lower bounds (see (see| Remark B.2 for details).
We now provide lower bounds with either the Random Arrival the quantity of H2 (but not both) in Theorem Theoremm 4
Theorem 3. There exists a family of streaming stochastic multi armee bandit instances, such that given the knowledge of A22) and the random arrival of arms, any algorithm to find the best arm
with a memory of n - 1) arms and success probability of at least 80 has to use w H2 SI
21
Ei
1. log log ) arm pulls. A/p
Theorem 4. There exists a family of streaming stochastic multi-armed bandit instances, such that given the knowledge of all gap parameters ( any algorithm to find the best arm with
memory of & arms for I o(n) and success probability of at least has to use 52 (2H2 (H2) arm pulls.
The idea to prove the lower bound with random arrival is quite simple: we show that with at least constant probability, the distribution of an instance with random arrival will resemble the instance we used for Theorem 2 More specifically, suppose each arm arrives at any position with probability 1. Then, with probability 1 the arm with reward! appears in the first 1 -fraction of the stream; n.
3. Similarly, with probability - 3. both of the last two arms in the distribution of Theorem 2 will not pop up until the late 2
z/ fraction of the stream. The family of the instances with both of the above properties indeed resembles the distribution we used earlier, and we can show that the algorithm is forced to use a lot of arm pulls under this scenario. The hard instance for Theorem is developed with different idea. Due space limits, we defer the proofs Appppddixx B
5 An Instance-sensitive Streaming Algorithm
We begin with introducing notations used this section. We denote the best arm with arm". Furthermore, we denote the instance-sensitive complexity (INST-complextry) for solving the problem
7

---

with probability of success at least 1- ô as H := Ei= only differ from the correct probability; if one sets ő to be constant, H and H become the same asymptotically.
log log Aqg
Note H2 and H
As mentioned before, our algorithm makes two assumptions on the stream of arms, namely:
Random arrival stream: the stream is random permutation of the arms {arm:
Known INST-complexity: The parameter H2 (or an a-approximation of it with O(1) being a fixed and known constant) given:
Assumption
(8 is a weaker version of all gap parameters {Ag) used in the lower bound of
Theorem 4 If the gap parameters are given, we can simply compute H2 and H.. The reverse direction is not generally possible.
Although the assumptions are strong, they are common in existing work of streaming models and stochastic MABs. The random order stream is standard assumption in the streaming setting (see (7 4 54 39), to name few). The knowledge of H; is similar-in-spee in-sprrt (albeit not identical) to the fixed-budger stochastic MABs, which has been studied intensively in the literature; see, e.g. [26 11. Furthermore, from a practical point of view, the knowledge of A [2] can be satisfied by an estimation that is at most Az2- The stronger assumptions of (t) and (tt) can be satisfied under the following scenarios:
The arms are stored in a 'bank" and local machine reads the arms with a small working memory. This allows the arms be 'served' in a random order from the external bank.
There exists historical data such that one can roughly estimate the quantity of INST-complexiy.
While the scenarios are restricted, does capture non-negligible range of applications. The formal guarantees of our algorithm is as follows.
Theorem 5. There is streaming algorithm that for any confidence parameter in random order, gap parameter Dr2), and INST-complexity H² Σin 27
> O, given n arms
1
log log (=))))
finds the best arm w.p. at least - using O H + pulls and a memory of a single arm.
I. logg( )2 log" (1 log A S/2l
arm
The algorithm in Theorem 5 contains additive term in sample complexity beside the standard Н& term. For most reasonable choices of parameters, this additive term is in fact negligible - in other words, our streaming algorithm in Theorem 5] achieves the same sample complexity as that of non-streaming algorithms of [26] (23 From a practical perspective, assuming H2 2 100n and constant success probability, we only need n to be in 106 10 and [2)] be around 0.1 ~ 0.2 to make H2 the dominating term, which seems reasonable in practice.
5.1 The Algorithm
Since we only maintain a single arm memory through the stream, we define the stored arm as the king in manner similar to the GAME-OF-COnE equivalent to a coin). We also adopt the challenge procedure first developed by 5]: for each arriving arm, if there already exists a king, the new arm will begin challenge procedure. If the challenge is successful, the challenger becomes the new king to be challenged by the later arms; otherwise, the challenger discarded, and the existing king retains its position and will be challenged by later arms. By the end of the stream, the algorithm outputs the king that is finally stored.
algorithm of [5] (an arm with Bernoulli reward is
The crucial part of our algorithm (similar GAMB-OF-ConE process. Following (5), the generic strategy for this is to compare the empirical reward on many levels. That is, on each level, we pull both the king and the challenger for certain times, and observe which arm has a lower empirical reward, to identify the defeated arm. If the challenger is defeated, we can simply discard it; but, if the king is defeated, we increase the number of arm pulls and compare the empirical rewards again. The king will not be discarded until some certain conditions are met.
of (5) is how design the challenge
The challenge procedure in [5] inherently requires ((1/A2)) arm pulls for each challenger even on level 1. Therefore, the algorithm inevitably requires 0(n 23) arm pulls. Our main task here is to design new challenge with fewer arm pulls, while maintaining the correctness of the algorithm.
8

---

To this end, we now formally introduce the algorithm. Let us first set up the parameters as follows.
{ { t=1 : A
2
(the guess of the gap at the current level)
8
(6 :64= = 50
(the confidence parameter)
4
{8r]
log( 88
(number of pulls)
Mearly ==
A7
30
log 2 n
log²
[ log
A [2)
(number of the 'warm-up" arms)
H
b b: 1800
(budget allocated to king for each arriving arm)
We also need some new definitions. We refer to the period of time between the introduction of new king and the time is discarded (or the end the stream) as an epuch. For each epoch, we define the early arms as the first Mearyy arms, and the the late arms the arms afterwards. During each epoch, we maintain a fixed estimate for the value p" as a parameter Pest that will only be updated after this epoch ends (and Pest is increasing throughout the updates of the algorithm).
can now present the algorithm:
Main Algorithm: INSTANCE- SENSITIVE-AAME ARMS::
a) Initialize the first arm as king and the first guess p* as Post
Ar
20
b) For each epoch:
Run GAME-OF-COINS of [5] on early arms with parameters:
A [2]
5
n''
mearly
and 8'
while setting the reward of the king to be Post (start their algorithm with an "artificial" first arm/coin with reward Pest). Terminate if GAME-Or-COIN, dis- cards king and jump Line (Mii otherwise, initialize the budget of the king Mearly-
B +-
(ii) For each late arm, give the king budget of b, i.e., B +- B + b; run Instance- Sensitive Challenge Subroutine (below) for king, challenger, budget B, and
Post-
(iis) If the king is discarded, set the challenger king and update Pest follows: log( { times and record the new Pehallenger-
(1) Pull the challenger A/
(2) Set Pest + max (Pehalleenrr Pest +
A 20
c) Run till the end the stream, and output the king as the best arm.
Instance-Sensitive Challenge Subroutine:
Input: the king and its budget B; challenger arm; the estimation parameter Pest-
1. For levels 1,2, .... long 5:
64 A
lolgog)))
(a) If se. let B St and pull challenger sæ times get empirical reward
P.
(b) I < Pest
A,/4, drop the challenger and terminate.
64 2. Pull the challenger ( log( + times and record its empirical reward fo:
(a) If p Pest
Apl /4, declare the challenge successful, and discard the king:
otherwise, declare the challenge unsuccessful, and discard the challenger.
In nutshell, the intuitions for the algorithm are as follows. Classical offline algorithms for instance- sensitive explorations (e.g. the algorithm in (26)) often estimations A for gaps Apj. and argue

---

that by iteratively comparing the arm rewards with the best arm, the distinction between the best and the i-th best arms becomes very clear after ås S [i)- The value of åe takes (log Z iterations to converge; as such, it takes (
3 log log( x arm pulls to distinguish the best and the i-th best arms. The strategy inherently requires the best arm to be stored in the beginning of the algorithm. Alas, migrating to the streaming setting, the above strategy no longer works: we cannot assume the best arm is stored in the beginning - it may appear in very late part of the stream. As such, we face the challenges of (i). it is unclear how use the reward of the best arm as in the offline setting, and (ti). the comparisons between sub-optimal arms may take too many arm pulls.
It turns out our assumptions are helpful to tackle the above challenges. On the very high level, we use the knowledge of Aμ2 to "guess" the reward of the best arm this allows us to iteratively update the value Pest in the algorithm, and eventually arrive at an estimation that is (c Ape) to the best reward (c 1). Furthermore, we use the the random order of the stream and the knowledge of H. to 'budget' the number of arm pulls for each arriving arm. It turns out this allows us to argue the budget sufficient for the real best arm in an amortized manner.
Limited by space, we defer the detailed overview and the formal analysis of the algorithm to Appendix D
Remark 5.1. Our lower bounds in Section s/swws that if we are given the knowledge of A12). but not both the random order of arrival and the knowledge of H (in the stronger form of { yi it impossible to arrive at the INST-complexity sample complexity. On the other hand, it leaves the possibility for an algorithm to find the best arm with o(n) memory, assuming no knowledge of A but with given parameters {A )== and the random arm arrival. Indeed, it appears the following modification of our algorithm works for such a scenario: sample each arm in the stream with probability 2. and run INSTANCE- SENSNNEVEEESSSEIEEEEEE GAAEEE--A-E----- OF-M--OF-AMMS by replacing A with [3) and
the H. with the quantity Ei= 1 log (1 log (si,)) By the sampling of arms, with probability 1
8. the best arm and third-best arm join the stream, while the second- best arm does not. Therefore, we can run O (log(1 (1/ (1))) copies of the algorithm, and output the top arm among the O (log(1/5) copies by running the offline algorithm in (26) at the end of the stream. Verifying whether the above strategy works will be an interesting immediate next-step for the work.
6 Discussion and Conclusion
In this paper, we studied the limitations for streaming MABs algorithm with the instance-sensitive sample complexity in single pass. We proved a collection of lower bounds showing that achieving the instance-sensittee
sample complexity with a small memory in a angle-pass stream is hard: with the absence of various (subsets of) assumptions, including the knowledge of A the additional gap parameters { A and the random arrival of arms, no algorithm can achieve the mestiiv--eensiivve bound with ((n)) - memory. Furthermore, as a byproduct of the lower bounds, we establish the crucial role of A Ag in streaming MABs: without such parameter, any algorithm with a memory even as large as a constant fraction of n cannot achieve any bounded sample complexity. We complemented our lower bounds by an algorithm that achieves the instance-sensitive bound under most realistic parameters and with a memory of a single arm when (almost) all assumptions hold. Our lower and upper bounds demonstrate a sharp dichotomy.
Our results open the door for various future work in this line of research. One open problem posed by our results is whether one can refine the streaming algorithm (or design new one) that drops the additive term on the sample complexity. Currently. we do not rule out the possibility that the additive term is necessary. Moreover, from the application side, an interesting problem to explore the empirical performances of our algorithm, and observe the numerical ad advantages compared to the algorithm in [5] And finally, a more challenging open problem to understand the tight number of passes that are necessary and sufficient to achieve the instance instance-sensitive sample complexity (with no or minimum assumptions) under the streaming MABs model.
Acknowledgments and Disclosure of Funding
Research supported in part by a NSF CAREER Grant CCF-2047061, a gift from Google Research, and Rutgers Research Council Fulcrum Award.
10

---

References
[1] A. Agarwal, S. Agarwal, S. Assadi, and S. Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proceedings of the 30th Conference Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 39-75, 2017.
[2] A. Agarwal, S. Khanna, and P. Patil. A sharp memory-regret trade-off for multi-pass streaming bandits. In P. Loh and M. Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1423-1462.
PMLR, 2022.
1.3 2 C.6
[3] D. Agarwal, B. Chen, P. Elango, N. Motgi, S. Park, R. Ramakrishnan, Roy, and Zachariah. Online models for content optimization. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Secun Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 17-24, 2008.
[4] S. Assadi and S. Behnezhad. Beating two-thirds for random-ordes streaming matching. In N. Bansal, E. Merelli, and J. Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland ( (Virtual Conference). volume 198 of L.Plcs, pages 19:1 19:1-19:13. Schloss Dagstuhl Leibniz-Zentrum für
Informatik, 2021. 5
[5] Assadi and Wang. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armes bandits. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago. II. USA, June 22-26, 2020, pages 1237-1250. ACM, 2020.
5.1
6
A
A.4 D.1
[6] J. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi ailli-armed bandits. In COLT 2010 - The 23rd Conference on Learning T'heory, Haifa, Israel, June 27-29, 2010, pages 41-53, 2010. 0]
[7] A. Bernstein. Improved bounds for matching in random-order streams, In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automala, Languages, and Program- ming, ICALP 2020, July 8-11 11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPlcs, pages 12:1-12:13. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020. 5
[8] S. Bubeck and N. bandit problems. Found. Trends Mach. Learn., 5(1):1-122, 2012. I.3
Regret analysis of stochastic and nonstochastic multi-armed
[9] G. Burtini, J. Loeppky, and R. Lawrence. A survey of online experiment design with the stochastic multi- bandit. arXiv preprint arXiv:1510.00757, 2015. [
[10] W. Cao, J. Li, Y. Tao, and Z. Li. On top-k selection multi-armed bandits and hidden bipartite graphs. In NIPS, volume 8, page 3, 2015.
[11] A. Carpentier and A. Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Proceedings of the 29th Conference Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 590-604, 2016.
[12] A. R. Chaudhuri and S. Kalyanakrishnan. Regret minimisation in nulti-armed bandits using bounded arm memory. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI
2020, The Sheroy-Second Innovative Applications Artificial Intelligence Conference, IAAI
2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI
2020, New York, NY, USA, February 7-12, 2020, pages 10085-10092, 2020. L
[13] L. Chen and J. Li. On the optimal sample complexity for best arm identification. CoRR, abs/151 00s/1511.033 1.03774, 2015.
1.3
[14] L. Chen, J. Li, and M. Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In A. Singh and X. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL. USA, volume 54 of Proceedings of Machine I Learning Research, pages 101-110. PMLR, 2017.
11

---

[15] L. Chen, J. Li, and M. Qiao. Towards instance optimal bounds for best arm identification. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 535-592, 2017. 1.3
[16] X. Chen, N. Bennett, K. Collins-Thompson and E. Horvitz. Pairwise ranking aggregation crowdsourced setting. Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, Rome, Italy, February 4-8, 2013, pages 193-202, 2013.
[17] Y. Chen and C. Suh. Spectral MLE: top-k rank aggregation from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine Learning. ICML 2015, Lille, France, 6- July 2015, pages 371-380 2015. 2
[18] S. Dong. T. Ma, and B. V. Roy. On the performance of thompson sampling on logistic bandits. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 1158-1166 2019.
[19] C. Dwork, R. Kumar, M. Naor, and Sivakumar. Rank aggregation methods for the web, In Proceedings of the Tenth International World Wide Web Conference, WWW 10, Hong Kong, China, May 1-5, 2001, pages 613-622, 2001.
[20] E. Even-Dar, S. Mannor, and Y. Mansour. PAC bounds for multi-armed bandit and markov deci- sion processes. In Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8- 10, 2002, Proceedings, pages 255-270, 2002.
[21] R. H. Farrell. Asymptotic behavior of expected sample size in certain one sided tests. The Annals of Mathematical Statistics, pages 36-72, 1964. 1.3
[22] W. Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages
Springer, 1994. A.3
[23] K. G. Jamieson, M. Malloy, R. D. Nowak, and S. Bubeck. lil' UCB An optimal exploration algorithm for multi-armed bandits. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, pages 423-439, 2014.
[24] T. Jin, K. Huang, J. Tang, and X. Xiao. Optimal streaming algorithms for multi-armed bandits. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 5045 5054. PMLR, 2021.
1.3
[25] S. Kalyanakrishnan and P. Stone. Efficient selection of multiple bandit arms: Theory and practice. Proceedings of the 27th International Conference on Machine Learning (ICML-10). June 21 21-24, 2010, Haifa, Israel, pages 511-518, 2010. 12
[26] S. S. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta,
GA, USA, 16-21 June 2013, pages 1238-1246, 2013.
5.1 D.I
[27] N. Karpov and Q Zhang. mnstance-sensitive algorithms for pure exploration in multinomial logit bandit. CoRR, abs/2012.01149, 2020. L.I
[28] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. J. Mach. Learn. Res., 17:1:1-1:42, 2016.
1.3
C.I
[29] Komiyama, J. Honda, and H. Nakagawa, Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays. In International Conference on Machine Learning, pages 1152-1161. PMLR, 2015.
[30] D. Liau, Z. Song, F. Price, and G. Yang. Stochastic multi-armed bandits in constant space. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-// April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pages 386-3944 2018
L.3
[31] A. Maiti, V. Patil, and A. Khan. Streaming algorithms for stochastic multi-armed bandits. arXiv preprint arXiv: 0514222,, 2020.
12

---

[32] A. Maiti, V. Patil, and A. Khan. aemti-armed bandits with bounded arm- mem-mrrry: Near rear-optimal guarantees for best-arm arm identification and regret minimization. M. Ranzato, Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pages 19553-19565, 2021.
[33] S. Mannor and J. N. Tsitsiklis. Lower bounds the sample complexity of exploration in the multi-armed bandit problem. In Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLI/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pages 418-432 2003.
[34] Peng and Sohler. Estimating graph parameters from random order streams. In A. Czumaj editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2449-2466. SIAM, 2018. 5
[35] Radlinski, R. Kleinberg, and T. Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th international conference on Machine learning, pages 784-791, 2008.
[36] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 5855)5277 1952.
[37] R. J. Serfling. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pages 39 48, 1974. A.3
[38] N. B. Shah and M. Wainwright. Simple, robust and optimal ranking from pairwise compar- isons. J. Mach. Learn. Res., 18: 18:199:1-199:38 2017. 2
[39] V. Srinivas, D. P. Woodruff, Z. Xu, and S. Zhou. Memory bounds for the experts problem. In S. Leonardi and A. Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1158-1171. ACM, 2022. 5
[40] M. S. Talebi, Z. Zou, R. Combes, A. Proutière, and M. Johansson. Stochastic online shortest path routing: The value of feedback. IEEE Trans. Automat. Contr, 63(4):915-930, 2018. [
[41] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-244 1933.
[42] Y. Xue, P. Zhou, T. Jiang, S. Mao, and X. Huang. Distributed learning for multi-channel selection in wireless network monitoring. In 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), pages 1-9. IEEE, 2016. !
[43] Y. Zhou, X. Chen, and J. Li. Optimal PAC multiple arm identification with applications to crowdsourcing. Proceedings of the 31th International Conference on Machine Learning. ICML 2014, Beijing, China, 21-26 June 2014, pages 217-225, 2014. [
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. . You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
13

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have discussed the problems left open by our work both in the corresponding sections and in [Section 6 All the assumptions are explicitly stated the paper.
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] This is theoretical work and we cannot identify any immediate positive negative societal
impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please see the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "OfUhR6x1geV", "reviewer": "Reviewer_dDQ4", "summary": "This paper studies space vs. sample complexity tradeoffs for stochastic multi-armed bandits. While it is possible to achieve optimal worst-case sample complexity while storing only a single arm in the streaming model, this paper investigates whether the same is true for instance-optimal bounds. The main result is a lower bound, showing that any single pass streaming algorithm must either incur a worse sample bound or store $\\Omega(n)$ arms. The authors show that this lower bound holds even under several stronger assumptions. Finally, the authors give an upper bound in the case where the stream is randomly ordered and the algorithm is furnished with some statistics about the problem instance.", "questions": "- Is there generally an understanding of the relationship between the arm finding and trapping problems? Is there a regime in which there is a separation between the problems (i.e. trapping is easier than separation)?", "limitations": "This paper is removed from direct applications, and I am satisfied with the authors' response.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The main technical tool in the paper is an interesting lemma in its own right which states that in the worst-case, $\\Omega(n/\\Delta^2_{[2]})$ samples are needed to output a set of $o(n)$ arms which contain the best arm (where $\\Delta_{[2]}$ is the gap between the best and second best arms).\n- Leveraging this lemma, the paper elegantly shows exactly which pieces of extra information/conditions on the stream are needed to circumvent this lower bound.   For instance, prior works assumed knowledge of $\\Delta_{[2]}$, but this paper shows that without such knowledge, any algorithm with $o(n)$ memory requires arbitrarily high sample access. As a result, the paper gives a very clear (and somewhat surprising) picture of memory/sample tradeoffs for this problem.\n\nWeaknesses\n- I think the paper would benefit from including some text explaining how the main results connect in the overview. In particular, explaining how the arm trapping lemma (which describes a worst-case distribution) can be applied to give lower bounds in the instance-optimal regime earlier on would be helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HvrWfODvEKH", "reviewer": "Reviewer_LGML", "summary": "This paper considers the tradeoffs between samples (i.e., number of arm-pulls) and space (i.e., maximum number of arms kept in memory) in the pure exploration stochastic multi-armed bandit problem. The objective in their MAB setting is to output, with a fixed probability, the arm with the highest mean reward, while minimizing the sample complexity (i.e., the total number of arm pulls), and while storing as few arms in memory as possible. They prove that any algorithm which stores $o(n)$ arms must have sample complexity that is $\\omega(\\text{INST-complexity})$, unless the arms arrive in uniformly random order and the algorithm knows the $\\text{INST-complexity}^*$. Further, any algorithm which stores $o(n)$ arms has sample complexity which is unbounded as a function of $n$ and $\\Delta_{[2]}$, unless some parameter of the problem (e.g., $\\Delta_{[2]}$) is known. They complement this result by proving that, assuming the INST-complexity and $\\Delta_{[2]}$ are known to the algorithm, and the arms arrive in a uniformly random order, then there is an algorithm which uses the memory of a single arm, and has sample complexity which nearly matches the best-known upper-bound (achievable with an arm memory of $n$).\n\n$*\\text{While}$ this is the claim of the paper, I _think_ the actual result requires weaker knowledge on the suboptimality gaps than INST-complexity. More on this later.", "questions": "Many of my concerns are listed in the **Weaknesses** section above. My main questions (some not listed in that section above) are as follows:\n\n- It may be useful to formalize what it means for an algorithm to not know a particular parameter. If a parameter is known only up to a $(1+\\epsilon)$ multiplicative factor, for instance, what is the smallest value of $\\epsilon$ which constitutes “not knowing”?\n- It seems that Theorem 4 does not require knowledge of INST-complexity exactly, but some function on the suboptimality gaps (e.g., $H_1$) also seems sufficient. Could you characterize exactly what information is needed for your lower bounds to still hold? Can you rephrase Result 1(i) to be more accurate (as discussed above)?\n- On the upper bound side – if the algorithm instead knew $H_1$ instead of $H_2^\\delta$, would your sample complexity results still hold? It would be interesting to me to see if the proof breaks down, or not.\n- Regarding the random arrival order – could you formalize exactly how random the arrival order needs to be? I suppose a uniformly-random arrival order works, but what if the arrival order is slightly biased? It seems if this bias is small, then your lower bound techniques likely would still work. Is there hope for a guarantee for arrival order distribution that is at most $\\epsilon$-far away (in TV distance, for example) from the uniform distribution? \n- You mention on line 41 that the goal is to identify the best arm with high _constant_ probability. Is there any hope for similar results that hold, e.g., with probability $1/n$?\n- Do you think there is any hope to show a lower bound on the necessity of the second-order terms in your sample complexity upper bound? Or do you think that these could be removed with a more refined analysis?\n- A question about the streaming setting you consider – if I understand correctly, your model constrains the memory in terms of the number of arms that can be pulled at any time, but not on the statistics that you can maintain about previous arms. So, for instance, an algorithm which maintained statistics on all $n$ arms (thus, in a different sense, using $O(n)$ memory), could still be considered “sublinear memory” in your model, right? Can you give any motivation for this setting, where you are constrained only on the number of arms you can pull simultaneously? Is this the most natural streaming model one could consider for your problem setting? Or is constraining the memory used for statistics also interesting?\n", "limitations": "N/A\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThis paper makes significant progress on an interesting and natural problem of the sample complexity of limited-memory pure exploration problems. The lower bounds show that instance-sensitive algorithms with the correct sample complexity are not achievable without some side information provided to the algorithm. Their bounds give some evidence for what side information may be necessary to solve the problem. On the upper-bound side, they provide an algorithm which achieves a near-optimal sample complexity with the memory of only a single arm, given the side information of $\\Delta_{[2]}$, $H_2$, and a uniformly random arrival order. The proof here appears quite interesting, and it seems an interesting extension of the ideas used in [4].\n\nIn general, I think the authors do a nice job of explaining and giving intuition in a simple manner for all of their results.\n\n**Weaknesses**\n\nI think the theorem statements for some of the lower bounds are presented a bit too informally. In particular, I think it would be helpful to formally define what is meant by an algorithm not knowing parameters such as $\\Delta_{[2]}$ or $H_2$. For instance, if the algorithm does know $\\Delta_{[2]}$ exactly, but knows this parameter to a $(1+\\epsilon)$ multiplicative factor for small $\\epsilon$, I guess this is still sufficient, right? Perhaps it would be good to specify how large $\\epsilon$ can be to still achieve your results. Further, if I understand it correctly, it seems that knowledge of $H_2$ is not really necessary for Theorem 4 to hold. For example, it seems like the lower bound would also be true if instead, the algorithm did not know $H_2$, but knew $H_1$ instead. In fact, I think this lower bound is true as long as the algorithm knows some value $f(\\\\{\\Delta_i\\\\}_{i\\neq i^*})$ (perhaps with some constraints on how perturbing a $\\Delta_i$ affects the function value), right? So it is not clear to me what information about the instance should actually be necessary to obtain near-optimal sample complexity with $o(n)$ arm storage.\n\nSo, in this sense, Result 1 (i) on line 99 is not quite correct, right? (I realize that this is meant to be an informal statement, but perhaps it would be better to reword it to be more accurate). Since if INST-complexity is not known, but, say, $H_1$ is known instead, then it is possible to have $O(H_2)$ regret, right (assuming random arrival orders and knowledge of $\\Delta_{[2]}$).\n\nAnother (very slight) weakness of the lower bounds result is that the meaning of “instance-sensitive” seems slightly different than is standard in multi-arm bandit literature (at least, as I understand it – please point out if I am mistaken). The style of instance-dependent lower bounds I am familiar with holds for _any_ instance with suboptimality gaps $\\\\{\\Delta_i\\\\}\\_{i\\in[n]}$. See, for example, Lemma 16.1 from “Bandit Algorithms”,  Lattimore and Szepesvári 2020. By contrast, I think your lower bounds are _slightly_ weaker than this, in the sense that they only hold for _some_ environment which has suboptimality gaps $\\\\{\\Delta_i\\\\}_{i\\in [n]}$. Perhaps it would be good to make this distinction a bit more clear somewhere in your paper.\n\nFinally, I find it somewhat unfortunate that the streaming algorithm you provide gets such little attention in the main body of the paper. I realize that you have very limited space, and the lower bound techniques are cool! But perhaps there is a way to discuss this a bit more in the main body, since the upper bound techniques also seem quite interesting! One possible idea is to cut down on the discussion of the arm trapping lemma proof – perhaps this can be just a sketch, and move the full proof to the appendix?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FvEsDBnXUWD", "reviewer": "Reviewer_MeNT", "summary": "This paper tackles a recently proposed streaming multi-armed bandit problem with limited memory. They construct an instance-sensitive algorithm when given additional information as input, and provide lower bounds showing that additional information is necessary to achieve good performance with sublinear memory.", "questions": "1. The lower bounds indicate classes of instances, to be contrasted with other bandit information theoretic lower-bounds which hold on an instance by instance basis. What are these classes of instances, and can this be generalized?\n2. The authors claim that if an $O(1)$-approximation of $H_2^{\\delta}$ is given, then the algorithm can still be run successfully. This does not seem to make sense, as if this quantity is rescaled unbeknownst to the algorithm, then it seems as though it will not be able to maintain $\\delta$ correctness. Further explanation (and explicitly showing where this parameter is used in the main algorithm) would be helpful.", "limitations": "Yes.\n\nPost-discussion: the authors have provided further clarification regarding how the algorithm functions, the motivating setting, and the dependence on $\\Delta_{[2]}^{-7}$ (in addition to potential ways that improve it). Incorporating these changes will greatly strengthen this paper in my eyes, and so I am increasing my score by 1 to 6 (weak accept).", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Significance: the paper does not seem to be of practical utility, as it seems unreasonable to assume knowledge of either $\\Delta_2$ or INST-complexity. This paper appears to have a theoretically significant results however, in the form of the arm-trapping Lemma.\n\nStrengths:\n- Arm trapping Lemma is strong, and formalizes intuition regarding the streaming setting.\n- Originality: instance-sensitive sample complexity for this setting is new.\n- Quality: this work formalizes intuition regarding the difficulty of this problem without additional information.\n- Clarity: the paper is written very clearly.\n\nWeaknesses:\n- The $\\Delta_2^{-7}$ dependence in Theorem 5 seems artifical and quite bad. If we consider problem settings where the minimal gap is scaling as $1/\\sqrt(n)$, as is commonly done when considering worst-case scenarios, this term dominates, yielding a sample complexity of $n^{5/2} \\Delta_2^{-2}$, dramatically worse than the $n\\Delta_2^{-2}$ of the minimax algorithm.\nEven for less aggressive choices of $\\Delta_2$, it seems as though this will still be a bottleneck (for any $\\Delta_2<n^{-1/5}$). Is this fundamental, or can this be improved?\n- Almost 2 pages are devoted to proving Lemma 3.1 in the main text; this doesn't help improve intuition, and would be better suited for the appendix. The authors could then present and discuss the algorithms in the main text.\n- The algorithms, which are relegated to the appendix, require further explanation; for example, what does the main algorithm take as input? How does it use the input parameter INST-complexity?\n- Finally, this work does not seem to be a good fit for NeurIPS. This paper tackles the problem of multi-armed bandits from a theoretical computer science perspective, as can be seen by the key papers this work builds on, which are from COLT and STOC. As this is a subjective point, I am not reducing my score because of it, but I think it merits discussion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A8cC3DHzp9u", "reviewer": "Reviewer_qt4b", "summary": "This paper studies the classical multi-armed bandits problem under the streaming setting with the goal of identifying the best arm using a fixed confidence. Unlike the previous work by Assadi and Wang [STOC 2020] which introduces a worst-case optimal algorithm, this paper aims to design a near-optimal instance-sensitive single-pass streaming algorithm which performs better when input problem instance is not hard. The contribution of this paper is three-fold: 1) It shows negative result that it is impossible to achieve such an algorithm even when the smallest gap $\\Delta_{[2]}$ is known beforehand. 2) There exists a near-optimal algorithm when $\\Delta_{[2]}$ and the complexity of the input instance are known, and the arms arrive completely randomly. 3) A by-product of this paper is the arm-trapping lemma which applies to the goal of outputting $o(n)$ arms that contains the best arm.", "questions": "Instead of designing a one-pass streaming algorithm, it might be more interesting to see if multiple passes could help to this problem? Have the author(s) considered such direction?", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths\n** The paper is written well and in good presentation which makes it easy to follow. I did not check the proof details in the appendix. But the proofs in the main part look solid and reasonable to me.\n** This paper is the first to show impossible result when the goal is to design a near-optimal instance-sensitive single-pass streaming algorithm\n\n* Weaknesses\n** The proposed algorithm is not practical since one has to know $\\Delta_{[2]}$ and the complexity of the input instance which is hard to know beforehand.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept