Pith. sign in

REVIEW 4 major objections 5 minor 38 references

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap

T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2502.01067 v1 pith:55CZ3OYU submitted 2025-02-03 cs.LG cs.DS

Nikolai Karpov , Chen Wang This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q2568W2068W2768W40
keywords streamingmulti-armedbanditsbest-armidentificationpureexplorationpasscomplexitysamplememory-constrainedalgorithmsoptimalitygapeliminationalgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Section 3.3, Proposition 1] 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.
  2. [Section 4, Lemma 4.2, Condition C2] 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.
  3. [Section 3.2, Lemma 3.5 and Algorithm 1] 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.
  4. [Section 5, Lemma 5.5] 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.
minor comments (5)
  1. [Section 5, Algorithm 3] 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.
  2. [Section 5, Lemma 5.5] 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).
  3. [Section 6] 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."
  4. [Section 5, Remark 5.8] 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.
  5. [Appendix B, Lemma B.2] 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).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bound is self-contained and the lower bound reuses an external framework without assuming the target result.

full rationale

The paper's central claims are not circular. The upper bound (Theorem 2 and Algorithm 3) is fully self-contained: correctness follows from the Chernoff-Hoeffding concentration event (Lemma 5.2), the elimination arguments (Lemmas 5.3 and 5.4), and the sample-complexity accounting (Lemma 5.5); none of these steps assumes the theorem being proved. The lower bound (Theorem 1) does import Proposition 1 from Assadi-Wang [COLT'24], one of whose authors is also an author of the present paper. This import is load-bearing, but it is not the target result: Proposition 1 is a general batched-instance framework whose conditions (C1, C2, C3) are stated independently, and the paper verifies those conditions for its new P(B,C,gamma) construction using new information-theoretic lemmas (Lemmas 3.5 and 3.6). The framework's assumptions do not include the conclusion that streaming algorithms need Omega(log n / log log n) passes for the instance-optimal sample complexity with known Delta[2]. Two concerns in the lower-bound chain are real but are correctness risks rather than circularity: the paper asserts a strengthening of Proposition 1 (the B^2 factor in Eq. (1)) with only the comment that it is 'evident from their proofs' (Section 3.3), and the verification of condition C2 sets rho = nu in Lemma 4.2 while Lemma 3.6 is stated for rho in (0,1/2), so nu can exceed 1/2 without an explicit argument. Both are fixable in principle and neither amounts to defining the conclusion into the assumptions. The derivation does not reduce, by construction or by renamed fit, to its inputs.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim does not fit any empirical data. Its assumptions are standard concentration and information-theoretic inequalities plus a batched-instance framework imported from prior work. The hard-instance parameters (gamma, chi_b, B) are chosen by hand to make the lower bound go through; they are construction choices, not fitted constants, but they are load-bearing and listed for transparency.

free parameters (2)
  • gamma (gap in hard instance P(B,C,gamma)) = Theta(n^{-1/3}), constrained to 1/(20 n^{1/3}) <= gamma <= 1/(10 n^{1/3})
    Chosen by hand to keep Delta[2] invariant at gamma and to make inequalities in Section 4 go through. It is a construction parameter for the lower bound family, not a fitted constant.
  • chi_b decay schedule and batch count B = chi_1 = n^{1/3} gamma; chi_{b+1} = (1/(12C log n))^{15} chi_b; B = (1/(100C)) log n / log log n
    Chosen so the inter-batch gap ratios satisfy condition C3 and the sample-complexity conversion in Theorem 1 holds. Again a construction parameter.
assumptions (5)
  • standard math Chernoff-Hoeffding concentration inequality
    Used in Lemma A.1 and in upper bound Lemma 5.2.
  • standard math Pinsker's inequality, KL chain rule, conditioning increases KL, and Fact A.5 on best decision from a sample
    These are the information-theoretic backbone of Lemmas 3.1, 3.3, 3.5, and 3.6.
  • domain assumption Proposition 1 from Assadi-Wang COLT'24 holds in the strengthened form used here (P <= B passes, memory n/(30000 B^3), extra B^2 factor in the sample bound)
    The paper rephrases and slightly strengthens the framework from [6] without proving the modified statement; the lower bound relies on it.
  • domain assumption Streaming model allows unlimited free statistics transcript pi; memory counts stored arms only
    Assumed in Section 2.2 and used to claim single-arm memory despite storing indices and estimates.
  • domain assumption Rewards are Bernoulli, equivalently sub-Gaussian with support in [0,1]
    Stated in Remark 2.1; both upper and lower bounds are proved for this family.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap." pith.science (2026). https://pith.science/paper/55CZ3OYU

@misc{pith2026250201067,
  author       = {Pith},
  title        = {Pith review of: Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/55CZ3OYU}},
  note         = {Machine review of arXiv:2502.01067}
}
abstract

We investigate the sample-memory-pass trade-offs for pure exploration in multi-pass streaming multi-armed bandits (MABs) with the *a priori* knowledge of the optimality gap $\Delta_{[2]}$. Here, and throughout, the optimality gap $\Delta_{[i]}$ is defined as the mean reward gap between the best and the $i$-th best arms. A recent line of results by Jin, Huang, Tang, and Xiao [ICML'21] and Assadi and Wang [COLT'24] have shown that if there is no known $\Delta_{[2]}$, a pass complexity of $\Theta(\log(1/\Delta_{[2]}))$ (up to $\log\log(1/\Delta_{[2]})$ terms) is necessary and sufficient to obtain the *worst-case optimal* sample complexity of $O(n/\Delta^{2}_{[2]})$ with a single-arm memory. However, our understanding of multi-pass algorithms with known $\Delta_{[2]}$ is still limited. Here, the key open problem is how many passes are required to achieve the complexity, i.e., $O( \sum_{i=2}^{n}1/\Delta^2_{[i]})$ arm pulls, with a sublinear memory size. In this work, we show that the ``right answer'' for the question is $\Theta(\log{n})$ passes (up to $\log\log{n}$ terms). We first present a lower bound, showing that any algorithm that finds the best arm with slightly sublinear memory -- a memory of $o({n}/{\text{polylog}({n})})$ arms -- and $O(\sum_{i=2}^{n}{1}/{\Delta^{2}_{[i]}}\cdot \log{(n)})$ arm pulls has to make $\Omega(\frac{\log{n}}{\log\log{n}})$ passes over the stream. We then show a nearly-matching algorithm that assuming the knowledge of $\Delta_{[2]}$, finds the best arm with $O( \sum_{i=2}^{n}1/\Delta^2_{[i]} \cdot \log{n})$ arm pulls and a *single arm* memory.

Figures

Figures reproduced from arXiv: 2502.01067 by the authors.

Figure 1
Figure 1. An illustration of the general (B + 1)-batched instance distribution (Definition 1) and the P(B, C, γ) instance distribution. The mean rewards of arms are ranked in the decrement order from left to right for illustration purposes – their positions inside the batches are uniformly at random. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. The comparison between algorithms on the sample complexity and the number of passes in the [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. The comparison between algorithms on the sample complexity and the number of passes in the [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The comparison between algorithms on the sample complexity and the number of passes in the [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 36 canonical work pages

  1. [2]

    A sharp memory-regret trade-off for multi-pass streaming bandits

    Arpit Agarwal, Sanjeev Khanna, and Prathamesh Patil. A sharp memory-regret trade-off for multi-pass streaming bandits. In Po-Ling Loh and Maxim 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

    work page 2022

  2. [6]

    The best arm evades: Near-optimal multi-pass streaming lower bounds for pure exploration in multi-armed bandits

    Sepehr Assadi and Chen Wang. The best arm evades: Near-optimal multi-pass streaming lower bounds for pure exploration in multi-armed bandits. In Proceedings of the 37th Conference on Learning Theory, COLT 2024, 2024

    work page 2024

  3. [1]

    Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons

    Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 39–75, 2017

    work page 2017

  4. [3]

    Online models for content optimization

    Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung-Taek Park, Raghu Ramakrishnan, Scott Roy, and Joe Zachariah. Online models for content optimization. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, D...

    work page 2008

  5. [4]

    Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits

    Sepehr Assadi and Chen Wang. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June...

    work page 2020

  6. [5]

    Single-pass streaming lower bounds for multi-armed bandits exploration with instance-sensitive sample complexity

    Sepehr Assadi and Chen Wang. Single-pass streaming lower bounds for multi-armed bandits exploration with instance-sensitive sample complexity. In NeurIPS, 2022

    work page 2022

  7. [7]

    On multi-armed bandit designs for dose-finding clinical trials

    Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding clinical trials. The Journal of Machine Learning Research, 22(1):686–723, 2021

    work page 2021

  8. [8]

    Tight (lower) bounds for the fixed budget best arm identification bandit problem

    Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In COLT, pages 590–604, 2016

    work page 2016

Show all 38 references
  1. [9]

    On the Optimal Sample Complexity for Best Arm Identification

    Lijie Chen and Jian Li. On the Optimal Sample Complexity for Best Arm Identification. arXiv preprint arXiv:1511.03774, 2015

    2015 arXiv

  2. [10]

    Open problem: Best arm identification: Almost instance-wise optimality and the gap entropy conjecture

    Lijie Chen and Jian Li. Open problem: Best arm identification: Almost instance-wise optimality and the gap entropy conjecture. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th 28 Conference on Learning Theory, COLT 2016, New York, USA, Ju...

    2016

  3. [11]

    Nearly instance optimal sample complexity bounds for top-k arm selection

    Lijie Chen, Jian Li, and Mingda Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 Apri...

    2017

  4. [12]

    Towards instance optimal bounds for best arm identification

    Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identification. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 , volume 65 of Proceedings o...

    2017

  5. [13]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006

    2006

  6. [14]

    PAC Bounds for Multi-Armed Bandit and Markov Decision Processes

    Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC Bounds for Multi-Armed Bandit and Markov Decision Processes. In COLT, 2002

    2002

  7. [15]

    Understanding memory-regret trade-off for streaming stochastic multi-armed bandits

    Yuchen He, Zichun Ye, and Chihao Zhang. Understanding memory-regret trade-off for streaming stochastic multi-armed bandits. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA,...

    2025

  8. [16]

    Distributed exploration in multi-armed bandits

    Eshcar Hillel, Zohar Shay Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In NIPS, pages 854–862, 2013

    2013

  9. [17]

    Jamieson, Matthew Malloy, Robert D

    Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, and Sébastien Bubeck. lil’ UCB : An optimal exploration algorithm for multi-armed bandits. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, COLT 20...

    2014

  10. [18]

    Optimal streaming algorithms for multi-armed bandits

    Tianyuan Jin, Keke Huang, Jing Tang, and Xiaokui Xiao. Optimal streaming algorithms for multi-armed bandits. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of P...

    2021

  11. [19]

    Efficient Selection of Multiple Bandit Arms: Theory and Practice

    Shivaram Kalyanakrishnan and Peter Stone. Efficient Selection of Multiple Bandit Arms: Theory and Practice. In ICML, 2010

    2010

  12. [20]

    Almost optimal exploration in multi-armed bandits

    Zohar Shay Karnin, Tomer Koren, and Oren 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, volume 28 of JMLR Workshop and Conference Proceedings, pag...

    2013

  13. [21]

    Collaborative top distribution identifications with limited interaction (extended abstract)

    Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction (extended abstract). In FOCS, pages 160–171, 2020

    2020

  14. [22]

    Complexity of best-arm identification in multi-armed bandit models

    Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. Complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1–42, 2016

    2016

  15. [23]

    Koval, Jennifer E

    Michael C. Koval, Jennifer E. King, Nancy S. Pollard, and Siddhartha S. Srinivasa. Robust trajectory selection for rearrangement planning as a multi-armed bandit problem. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, ...

    2015

  16. [24]

    Tight memory-regret lower bounds for streaming bandits

    Shaoang Li, Lan Zhang, Junhao Wang, and Xiang-Yang Li. Tight memory-regret lower bounds for streaming bandits. CoRR, abs/2306.07903, 2023. 29

    2023 arXiv

  17. [25]

    Multi-armed bandits with bounded arm-memory: Near-optimal guarantees for best-arm identification and regret minimization

    Arnab Maiti, Vishakha Patil, and Arindam Khan. Multi-armed bandits with bounded arm-memory: Near-optimal guarantees for best-arm identification and regret minimization. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edit...

    2021

  18. [26]

    The Sample Complexity of Exploration in the Multi-Armed Bandit Problem

    Shie Mannor and John N Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research, 5:623–648, 2004

    2004

  19. [27]

    Learning diverse rankings with multi-armed bandits

    Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th international conference on Machine learning, pages 784–791, 2008

    2008

  20. [28]

    Some aspects of the sequential design of experiments

    Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527–535, 1952

    1952

  21. [29]

    Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions

    Nícollas Silva, Heitor Werneck, Thiago Silva, Adriano CM Pereira, and Leonardo Rocha. Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions. Expert Systems with Applications, 197:116669, 2022

    2022

  22. [30]

    Introduction to multi-armed bandits

    Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12(1-2):1–286, 2019

    2019

  23. [31]

    Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges

    Sofía S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015

    2015

  24. [32]

    Tight regret bounds for single-pass streaming multi-armed bandits

    Chen Wang. Tight regret bounds for single-pass streaming multi-armed bandits. In Proceedings of the 40th International Conference on Machine Learning, ICML 2023, Proceedings of Machine Learning Research, 2023. A Standard technical tools A.1 Concentration Inequalities We use th...

    2023

  25. [33]

    (23) For arms from the set B by Lemma B.4 we have that the number of pulls assigned to an arm i ∈ B is bounded by P T0 ≤ 128 n2∆2

    log e log 2n(P + 1)2 δ ! . (23) For arms from the set B by Lemma B.4 we have that the number of pulls assigned to an arm i ∈ B is bounded by P T0 ≤ 128 n2∆2

  26. [34]

    We note that the size of B is bounded by n

    log e log 2n(P + 1)2 δ ! . We note that the size of B is bounded by n. Therefore, the total sample complexity for arms from B is bounded by n · 128 n2∆2

  27. [35]

    log e log 2n(P + 1)2 δ ! ≤ 128 ∆2

  28. [36]

    (24) As such, combining Eq (22), Eq (23), and Eq (24), we have T = TS + TB ≤ P 128 ∆2

    log e log 2n(P + 1)2 δ ! . (24) As such, combining Eq (22), Eq (23), and Eq (24), we have T = TS + TB ≤ P 128 ∆2

  29. [37]

    log e log 2n(P + 1)2 δ ! + X i:i̸=⋆ P 18 ∆2 i log e log 2n(P + 1)2 δ ! + TB (by Eq (22), Eq (23)) ≤ O P log nP δ · nX i=2 n2/P ∆2 [i] ! + 128 ∆2

  30. [38]

    36 Finalizing the proof of Theorem 3

    log e log 2n(P + 1)2 δ ! (by Eq (24)) = O P log nP δ · nX i=2 n2/P ∆2 [i] ! , as desired. 36 Finalizing the proof of Theorem 3. The algorithm makes P + 1 passes over the stream by the algorithm design. The memory efficiency is guaranteed by Lemma B.1, and the correctness and t...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.