{"id":"f6ca05a4-a113-4c20-a5f0-2f99b23598b8","arxiv_id":"2502.01067","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"With a known optimality gap, streaming best-arm identification needs about log(n)/log log(n) passes with slightly sublinear memory, and O(log n) passes with a single arm of memory.","lead":"This paper nearly settles the pass-memory-sample trade-off for streaming multi-armed bandits when the optimality gap is known. It proves a near-tight lower bound and a matching algorithm for finding the best arm with instance-optimal sample complexity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bound rests on an unproved strengthening of Proposition 1 from [6]; if that strengthening fails, Theorem 1 collapses.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing step: Proposition 1 is imported from prior work and strengthened in two ways (P <= B and an extra B^2 factor in the sample bound) without proof. My reading of Section 3.3, Lemma 4.2, and Theorem 1 confirms that the entire lower bound is a direct application of Proposition 1 after verifying C1-C3. If the strengthened proposition is false, the Omega(log n / log log n) pass lower bound does not follow. The paper itself flags the omission by saying the modification is 'evident from their proofs,' but no proof or precise citation is supplied. I also note a secondary internal issue in the verification of condition C2, where Lemma 3.6's parameter rho is set to a conditional probability nu that may exceed 1/2, outside the lemma's stated range. This reinforces the need for a careful proof of the framework rather than a black-box invocation. The upper bound is largely self-contained and appears sound in the regime P = Theta(log n) that is needed for the main claim; the lower bound is the part that requires conditional acceptance. Since the reader already reached a CONDITIONAL verdict, my stress-test does not move the verdict.","tokens_in":31620,"tokens_out":22625,"duration_ms":226456,"concrete_test":"Obtain the full proof of the batched-instance lower bound in [6] (Assadi and Wang, COLT 2024) and re-derive Proposition 1 with P <= B and Eq (1) multiplied by B^2. Specifically, trace the step where the algorithm's sample budget is compared with n / eta_b^2 and verify that the argument still goes through after replacing P = B by P <= B and the budget by C B^2 n / eta_b^2. If the proof only yields the original P = B version without the B^2 factor, then Theorem 1 does not follow as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1) depends entirely on Proposition 1 in Section 3.3, which is a rephrased and strengthened version of the batched-instance lower bound of [6]. Two modifications are asserted without proof: (i) P <= B passes instead of P = B, and (ii) an extra B^2 factor in the sample-complexity condition Eq (1). The text says only \"it is evident from their proofs that we can add a B factor on the sample bound\" (Section 3.3, bullet 2), but the proposition actually contains B^2, not B, and no derivation or pointer to a specific theorem in [6] is given. Since Lemma 4.2 verifies conditions C1-C3 and then invokes Proposition 1 as a black box, any gap in this strengthening is fatal to the Omega(log n / log log n) lower bound. A related hazard appears in the verification of C2: Lemma 4.2 sets rho = nu for a conditional probability nu that can exceed 1/2, while Lemma 3.6 is stated only for rho in (0, 1/2); this needs an additional argument (e.g., symmetry or min(nu, 1-nu)) before the framework applies. Both issues are fixable in principle, but as written the lower bound is conditional on an unproved imported theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-pass streaming best-arm identification in multi-armed bandits under the assumption that the optimality gap Δ[2] is known. It claims a near-complete pass-memory-sample trade-off: Theorem 1 states that any algorithm with o(n/log^3 n) arm-memory and O(Σ_{i=2}^n Δ_{[i]}^{-2} log n) expected pulls must use Ω(log n / log log n) passes, and Theorem 2 gives a (P+1)-pass single-arm-memory elimination algorithm with O(log(nP/δ) Σ_{i=2}^n n^{2/P} Δ_{[i]}^{-2}) pulls, yielding O(log n) passes and O(Σ Δ_{[i]}^{-2} log n) pulls. The upper bound is a clean adaptation of elimination with geometrically decreasing thresholds, and the lower bound is built on a batched-instance framework imported and strengthened from Assadi–Wang [COLT 2024], with new double-armed bandit lemmas to handle two special arms per batch while keeping Δ[2] invariant.","tokens_in":31847,"tokens_out":10802,"duration_ms":113196,"significance":"If the claimed bounds are correct, the paper resolves the motivating open question: with known Δ[2], the pass complexity needed for near-instance-optimal sample complexity with sublinear memory is Θ(log n) up to a log log n factor. The upper bound is elegant, self-contained, and gives a smooth sample-pass trade-off with a single-arm memory, and the experiments provide supporting evidence. The paper also identifies a reusable batched-instance framework, which is a useful conceptual contribution. However, the lower bound is currently conditional on a strengthened form of Proposition 1 imported from prior work without proof, and one verification step in Lemma 4.2 uses Lemma 3.6 outside its stated regime. These are load-bearing gaps, not presentation issues, so the manuscript needs a major revision before the central claims can be considered established.","major_comments":[{"comment":"Proposition 1 is the engine of the lower bound, but it is imported from [6] in a strengthened form without proof. The statement changes the original in at least three ways: P ≤ B passes rather than P = B, memory n/(30000 B^3), and an extra B^2 factor in the conditional sample bound Eq (1). The text says only that the changes are \"evident from their proofs\" and then says \"we can add a B factor on the sample bound,\" while Eq (1) actually contains B^2. Since Lemma 4.2 and hence Theorem 1 invoke Proposition 1 as a black box, the lower bound collapses if this strengthened statement is not proved. Please provide a self-contained proof or a precise derivation from specific theorems/lemmas in [6], and reconcile the B versus B^2 discrepancy.","section":"Section 3.3, Proposition 1"},{"comment":"In verifying Condition C2, the proof sets ρ = ν, where ν is the posterior probability Pr(Θ_b = 1 | E). Lemma 3.6, however, is stated only for ρ ∈ (0, 1/2), and ν can exceed 1/2 after conditioning on information obtained by the algorithm. The manuscript does not explain how to handle this case, for example by symmetry or by replacing ν with min(ν, 1-ν) with an adjusted argument. As written, the application of Lemma 3.6 is outside its stated domain, and the verification of C2 is incomplete.","section":"Section 4, Lemma 4.2, Condition C2"},{"comment":"There is a numerical inconsistency in the proof of Lemma 3.5. The lemma requires the output set S to have size τ k / 40, but Algorithm 1's input specification says ALG outputs a collection of τ k / 20 arms. In the No-case analysis the proof then uses Pr(X(ℓ)=1) = |S|/k ≤ τ/40, which is inconsistent with τ k / 20. With |S|/k = τ/20, the union bound over the two special arms gives failure probability τ/10 rather than τ/20, so the claimed overall success probability after adding the Markov-bound failure is not exactly as stated. This is likely fixable with adjusted constants, but the proof as written does not establish the lemma.","section":"Section 3.2, Lemma 3.5 and Algorithm 1"},{"comment":"The proof of the sample-complexity bound uses Eq (10), which states 3/2 n^{1/P} ε_{p(i)} ≥ Δ_i for every suboptimal arm. This inequality follows from the minimality of p(i) only when p(i) ≥ 1; for arms with p(i) = 0, the preceding threshold ε_{p(i)-1} does not exist. Such arms exist: any arm with Δ_i > 3 ε_0 / 2 = 3 n Δ[2] / 8 has p(i)=0 but is not in the set B unless Δ_i > 3 n Δ[2] / 2. The total contribution of these arms can likely be bounded separately by n T_0 = O(log(nP/δ)/(n Δ[2]^2)), which is O(Σ_i n^{2/P}/Δ_i^2) for these arms up to a constant, so the claim is plausibly repairable, but the current derivation does not cover the p(i)=0 case.","section":"Section 5, Lemma 5.5"}],"minor_comments":[{"comment":"The pseudocode mixes the loop variable p with the symbol r: Line 7 says \"until the number of pulls reach T_r,\" Line 9 says \"max_{i ∈ I_r}\", and Line 10 uses I_p. These should all use p consistently.","section":"Section 5, Algorithm 3"},{"comment":"The sets S and B are defined with \"3nΔ/2\" without brackets; this should be 3 n Δ[2] / 2 for clarity. Also, Eq (12) says the optimal arm's number of pulls is \"equal to T_P,\" but the best arm is pulled in every pass, so the correct statement is that it is at most Σ_{p=0}^P T_p = O(T_P).","section":"Section 5, Lemma 5.5"},{"comment":"Some captions are inconsistent with the content: Figure 2(b) says \"JHTX stands for the single-pass algorithm of [18],\" but JHTX is an O(log(1/Δ[2]))-pass algorithm; Figure 4's caption says \"arithmetic progression setting\" while the text describes clustered instances; and Table 4's caption says \"uniform setting\" instead of \"clustered setting.\"","section":"Section 6"},{"comment":"Remark 5.8 says the gap search starts from O(√n Δ[2]), but Algorithm 3 sets ε_0 = n Δ[2] / 4, which is O(n Δ[2]). Please reconcile the stated starting threshold.","section":"Section 5, Remark 5.8"},{"comment":"The displayed bound after the Chernoff-Hoeffding application has \"2 exp(ϵ_r^2 T_r / 8)\" with a missing minus sign in the exponent; it should be 2 exp(-ϵ_r^2 T_r / 8).","section":"Appendix B, Lemma B.2"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound side is in good shape and seems sound after minor corrections. The chief risk is the lower bound's reliance on Proposition 1, which is a strengthened rephrasing of a theorem from prior work by one of the authors and is not proved here. Given that the paper already contains much of the technical machinery needed for the double-armed lemmas, a full proof or precise reduction to [6] in an appendix should be feasible; if it is not, the lower bound should be weakened accordingly. The C2 verification issue in Lemma 4.2 should also be addressed explicitly. I would not recommend rejection, but the manuscript is not ready until these points are resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the upper bound is real and the algorithm is simple; the lower bound is the main event and it is conditional. Theorem 2 gives a (P+1)-pass elimination algorithm with single-arm memory and O(log(nP/δ) * sum_i n^{2/P}/Δ_i^2) pulls. That's a clean, believable result. Plugging P = Θ(log n) gives O(log n) passes and near instance-optimal sample complexity, which is what the abstract promises. I checked the analysis; the geometric schedule ε_p = n^{1-p/P} Δ[2]/4 works, and I don't see a real hole there.\n\nTheorem 1, the Ω(log n / log log n) pass lower bound, is cleverer but shakier. The two-special-arms construction that keeps Δ[2] invariant is a nice idea, and the double-armed bandit lemmas are plausible. The problem is that the whole lower bound goes through Proposition 1, a rephrased version of Assadi-Wang's batched framework, and the paper asserts two strengthenings without proof: P ≤ B passes, and a B^2 factor in the sample-complexity condition (1). The text says 'it is evident from their proofs' — but the proposition as written contains B^2, not B, and gives no pointer to the specific theorem in [6]. Since Lemma 4.2 uses Proposition 1 as a black box, a failure of this strengthening would collapse Theorem 1. That's a load-bearing gap, not a cosmetic one.\n\nThe C2 verification also sets ρ = ν, where ν is a posterior probability that can exceed 1/2, while Lemma 3.6 is only stated for ρ < 1/2. Likely a symmetry argument fixes it, but it's not there. There are smaller warts: Lemma 5.5 says 'the number of pulls for arm i is T_{p(i)}' when it's actually the sum over passes up to p(i) — asymptotically the same, so minor; some typos in constants and a sign slip in the Fact A.5 usage.\n\nIf the authors can either prove the strengthened Proposition 1 or give a precise citation in [6], I'd be fairly confident the main results stand. As is, I'd treat Theorem 1 as 'likely true but unverified'.\n\nWho this is for: people working on streaming MABs and pass-memory-sample trade-offs. The upper bound alone is a useful contribution; the lower bound, if repaired, completes the table. This deserves a serious referee, not a desk reject. My advice: send it out, and ask the referee specifically to verify Proposition 1's strengthening and the C2 range.","headline":"Upper bound is solid; lower bound is conditional on an unproved strengthening of Assadi-Wang's framework — worth reviewing, but Theorem 1 needs a proof before I'd rely on it.","tokens_in":32429,"tokens_out":9790,"would_cite":true,"duration_ms":85334,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","68W27","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that streaming best-arm search with a known optimality gap still needs about log n passes under tiny memory, while O(log n) passes and one arm of memory suffice.","keywords":["streaming multi-armed bandits","best-arm identification","pure exploration","pass complexity","sample complexity","memory-constrained algorithms","optimality gap","elimination algorithm"],"falsifier":"Run a direct test of the strengthened framework on a small batched instance, say $B=4$ equal batches of $100$ Bernoulli arms with memory limited to roughly $n/(30000B^3)$ arms, and ask whether some $P\\le4$-pass algorithm can succeed with probability at least $999/1000$ while spending only $O(CB^2 k/(\\eta^{(1)})^2)$ pulls conditioned on a planted good batch. A positive answer would violate Proposition 1 in the exact regime the lower bound needs, so the $\\Omega(\\log n/\\log\\log n)$ bound would not follow. Equivalently, exhibit any streaming algorithm with $o(\\log n/\\log\\log n)$ passes, sublinear arm memory, and $O(\\sum_{i=2}^n \\Delta_{[i]}^{-2}\\mathrm{polylog}(n))$ pulls on the paper's $P(B,C,\\gamma)$ family; that would directly falsify Theorem 1.","tokens_in":31366,"feed_emoji":"🎰","tokens_out":11842,"duration_ms":109032,"temperature":0.7,"pith_summary":"The paper asks how many passes over the stream are needed to find the best arm in a multi-armed bandit when the optimality gap $\\Delta_{[2]}$ (the gap between the best and second-best mean reward) is known in advance and the target is the near-instance-optimal sample count $\\sum_{i=2}^n 1/\\Delta_{[i]}^2$. It answers with a nearly tight bound: every algorithm that uses $o(n/\\mathrm{polylog}(n))$ arm memory and $O(\\sum_{i=2}^n \\Delta_{[i]}^{-2} \\log n)$ pulls needs $\\Omega(\\log n / \\log\\log n)$ passes, while a $(P+1)$-pass algorithm with a single arm of memory achieves $O(\\log(nP/\\delta)\\sum_{i=2}^n n^{2/P}\\Delta_{[i]}^{-2})$ pulls, which becomes $O(\\log n)$ passes and the desired sample count at $P=\\Theta(\\log n)$. A sympathetic reader should care because this closes the last open corner of the pass-memory-sample trade-off for streaming pure exploration: knowing $\\Delta_{[2]}$ removes the huge pass cost that the unknown-gap lower bound imposes, but it does not reduce the pass count to a constant when the sample target is instance-optimal.","feed_headline":"Streaming best-arm search needs ~log n passes even with known gap","feed_subtitle":"A matching algorithm uses log n passes and one arm of memory; without the gap, prior bounds need far more passes.","key_machinery":"Two objects carry the argument. First, the hard instance family $P(B,C,\\gamma)$: $B+1$ batches arrive in reverse order, each batch plants two special arms whose means are $1/2+\\chi_b$ and $1/2+\\chi_b+\\gamma$, where $\\chi_{b+1} = (1/(12C\\log n))^{15}\\chi_b$ and $B=\\Theta(\\log n/\\log\\log n)$; the offset $\\gamma$ is the same in every batch, which pins $\\Delta_{[2]}$ at $\\gamma$ while still making later batches more attractive. The family is shown to satisfy conditions C1--C3 of the batched lower-bound framework (Proposition 1, rephrased from prior work), with the verification carried by new double-armed bandit lemmas that control trapping and learning when two high-reward arms are present. Second, the geometric elimination schedule of Algorithm 3: in pass $p$ the algorithm pulls each surviving arm $T_p\\approx 8\\log(2n(P+1)/\\delta)/(\\epsilon_p^2\\log e)$ times with $\\epsilon_p=\\Delta_{[2]}n^{1-p/P}/4$, eliminates any arm whose empirical mean is more than $\\epsilon_p$ below the current maximum, and keeps only the current arm in memory; this schedule is what converts knowledge of $\\Delta_{[2]}$ into a pass count independent of $1/\\Delta_{[2]}$.","core_discovery":"On the paper's own terms, the central discovery is a sharp dichotomy for streaming best-arm identification with known $\\Delta_{[2]}$: achieving sample complexity $\\widetilde{O}(\\sum_{i=2}^n 1/\\Delta_{[i]}^2)$ with sublinear arm memory requires $\\Omega(\\log n/\\log\\log n)$ passes, and $O(\\log n)$ passes are sufficient with only one arm held in memory. The lower bound is driven by a batched hard distribution in which each batch contains two planted arms with means $1/2+\\chi_b$ and $1/2+\\chi_b+\\gamma$, with $\\chi_b$ decaying geometrically and $\\gamma$ fixed across all batches; this makes $\\Delta_{[2]}=\\gamma$ for every realization, so revealing $\\Delta_{[2]}$ tells the algorithm nothing about where the good arms are. The upper bound is an elimination algorithm whose threshold in pass $p$ is $\\epsilon_p=\\Delta_{[2]}n^{1-p/P}/4$, which shrinks geometrically from a large multiple of typical gaps down to $\\Delta_{[2]}$ in $P$ passes and yields the sample-pass trade-off $n^{2/P}$ per arm.","pith_inferences":["If the strengthened Proposition 1 (extra $B^2$ factor, $P\\le B$, memory $n/(30000B^3)$) can be proved or further tightened, the remaining $\\log\\log n$ gap between the $\\Omega(\\log n/\\log\\log n)$ lower bound and the $O(\\log n)$ upper bound is likely to close from below; the paper's remark that larger gaps between the $\\chi_b$'s allow larger exponents in the sample bound points in that direction.","The two-arm invariant-gap construction is a reusable trick: in any instance-sensitive streaming problem where a known global parameter would otherwise identify the planted instance, planting two special arms at a fixed offset can make the parameter invariant while preserving hardness; this could transfer to top-$k$ identification or thresholding problems.","The sample-pass trade-off formula is directly testable: on synthetic gap instances, running Algorithm 3 with $P=1,2,4,\\dots$ should show pulls scaling like $n^{2/P}$ and passes exactly $P+1$, which would let practitioners pick a pass budget before deployment."],"forward_implications":["At $P=\\Theta(\\log n)$, Algorithm 3 finds the best arm with $O(\\sum_{i=2}^n \\Delta_{[i]}^{-2}\\log n)$ pulls, $O(\\log n)$ passes, and one arm of memory, matching the lower bound up to a $\\log\\log n$ factor.","For any fixed $P$, the algorithm's sample complexity is $O(\\log(nP/\\delta)\\sum_{i=2}^n n^{2/P}\\Delta_{[i]}^{-2})$, giving a smooth sample-pass trade-off: more passes reduce the per-arm factor $n^{2/P}$.","The lower bound holds even when the algorithm is handed the exact value of $\\Delta_{[2]}$, so the $\\Omega(\\log n/\\log\\log n)$ pass cost cannot be bypassed by knowing the gap; it is a memory-plus-sample limitation.","If the algorithm is run offline rather than over a stream, the same argument yields a best-arm algorithm with $O(\\sum_{i=2}^n \\Delta_{[i]}^{-2}\\log n)$ pulls whenever $\\Delta_{[2]}$ is known, replacing the gap-dependent $\\log\\log(1/\\Delta_{[i]})$ factor with a gap-independent $\\log n$.","Only a lower bound $\\gamma\\le\\Delta_{[2]}$ is needed in place of the exact gap; the guarantees survive with an additive $O(\\log(nP/\\delta)/(n\\gamma^2))$ term in the sample complexity."],"supporting_citations":[{"why":"Defines the streaming MAB model and gives the single-pass worst-case-optimal baseline that motivates the multi-pass question.","marker":"[4]"},{"why":"Provides the single-pass instance-sensitive lower bounds whose direct-sum technique the paper adapts to two special arms.","marker":"[5]"},{"why":"Supplies the batched-instance lower-bound framework that the paper rephrases as Proposition 1 and strengthens with an extra $B^2$ factor; the $\\Omega(\\log n/\\log\\log n)$ bound depends on it.","marker":"[6]"},{"why":"Gives the $O(\\log(1/\\Delta_{[2]}))$-pass elimination algorithm whose gap-binary-search schedule the new upper bound replaces with a geometric schedule.","marker":"[18]"},{"why":"Provides the near-instance-optimal elimination analysis and the gap-categorization argument used in the upper bound's sample-complexity proof.","marker":"[20]"},{"why":"Establishes the classical $\\Omega(\\sum_i 1/\\Delta_{[i]}^2)$ sample-complexity lower bound that fixes the target against which the new pass bounds are measured.","marker":"[26]"}],"fun_headline_variants":["Streaming best-arm needs ~log n passes even with known gap","Known gap doesn't cut streaming passes: still Ω(log n)","Sublinear memory forces ~log n passes in streaming bandits","Best-arm identification: known gap, still many passes","Log n passes needed even with known optimality gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Proposition 1, the batched-instance lower-bound framework imported and strengthened from prior work: the proof needs it to hold for $P\\le B$ passes, memory $n/(30000B^3)$ arms, and an extra $B^2$ factor in the sample bound. The paper does not prove the strengthened version, saying only that it is 'evident from their proofs'; if that strengthening fails, the $\\Omega(\\log n/\\log\\log n)$ pass lower bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Streaming best-arm needs ~log n passes even with known gap","Known gap doesn't cut streaming passes: still Ω(log n)","Sublinear memory forces ~log n passes in streaming bandits","Best-arm identification: known gap, still many passes","Log n passes needed even with known optimality gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000289,"raw_usage":{"total_tokens":1837,"prompt_tokens":1236,"completion_tokens":601,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":852,"completion_tokens_details":{"reasoning_tokens":518}},"tokens_in":852,"tokens_out":601,"duration_ms":6466,"temperature":1.0,"reasoning_tokens":518,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T16:42:22.518011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a direct test of the strengthened framework on a small batched instance, say $B=4$ equal batches of $100$ Bernoulli arms with memory limited to roughly $n/(30000B^3)$ arms, and ask whether some $P\\le4$-pass algorithm can succeed with probability at least $999/1000$ while spending only $O(CB^2 k/(\\eta^{(1)})^2)$ pulls conditioned on a planted good batch. A positive answer would violate Proposition 1 in the exact regime the lower bound needs, so the $\\Omega(\\log n/\\log\\log n)$ bound would not follow. Equivalently, exhibit any streaming algorithm with $o(\\log n/\\log\\log n)$ passes, sublinear arm memory, and $O(\\sum_{i=2}^n \\Delta_{[i]}^{-2}\\mathrm{polylog}(n))$ pulls on the paper's $P(B,C,\\gamma)$ family; that would directly falsify Theorem 1.","supporting_citations":[{"cited_title":"Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"Defines the streaming MAB model and gives the single-pass worst-case-optimal baseline that motivates the multi-pass question."},{"cited_title":"Single-pass streaming lower bounds for multi-armed bandits exploration with instance-sensitive sample complexity","cited_arxiv_id":null,"evidence_quote":"Provides the single-pass instance-sensitive lower bounds whose direct-sum technique the paper adapts to two special arms."},{"cited_title":"The best arm evades: Near-optimal multi-pass streaming lower bounds for pure exploration in multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the batched-instance lower-bound framework that the paper rephrases as Proposition 1 and strengthens with an extra $B^2$ factor; the $\\Omega(\\log n/\\log\\log n)$ bound depends on it."},{"cited_title":"Optimal streaming algorithms for multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"Gives the $O(\\log(1/\\Delta_{[2]}))$-pass elimination algorithm whose gap-binary-search schedule the new upper bound replaces with a geometric schedule."},{"cited_title":"Almost optimal exploration in multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"Provides the near-instance-optimal elimination analysis and the gap-categorization argument used in the upper bound's sample-complexity proof."},{"cited_title":"The Sample Complexity of Exploration in the Multi-Armed Bandit Problem","cited_arxiv_id":null,"evidence_quote":"Establishes the classical $\\Omega(\\sum_i 1/\\Delta_{[i]}^2)$ sample-complexity lower bound that fixes the target against which the new pass bounds are measured."}],"review_version":1}