Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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$).

$*\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.
strengths_and_weaknesses: **Strengths**

This 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].

In general, I think the authors do a nice job of explaining and giving intuition in a simple manner for all of their results.

**Weaknesses**

I 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.

So, 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]}$).

Another (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.

Finally, 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?

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:

- 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”?
- 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)?
- 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.
- 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? 
- 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$?
- 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?
- 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?

limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
- 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).
- 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.

Weaknesses
- 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: * Strengths
** 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.
** This paper is the first to show impossible result when the goal is to design a near-optimal instance-sensitive single-pass streaming algorithm

* Weaknesses
** 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.
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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

Strengths:
- Arm trapping Lemma is strong, and formalizes intuition regarding the streaming setting.
- Originality: instance-sensitive sample complexity for this setting is new.
- Quality: this work formalizes intuition regarding the difficulty of this problem without additional information.
- Clarity: the paper is written very clearly.

Weaknesses:
- 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.
Even 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?
- 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.
- 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?
- 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.
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?
2. 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.

Post-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).
review_title: null

Meta-review: metareview: This paper studies the pure exploration in the streaming MAB model.  The main message it delivers is that any single pass streaming algorithm must either have a large sample complexity or store a linear number of arms.  The reviewers agreed that the results are interesting and that the analysis in the paper is novel and technically strong.  Some questions were raised regarding the requirement of knowing Delta_[2] in the algorithms and the high dependence on 1/Delta_[2] in the upper bounds. These questions have been largely addressed by the authors' responses.  There are still some questions regarding the motivation of the streaming bandit model; it will be nice if the authors can give some real-world applications for this model in the next version.
confidence: Certain
Decision: Accept