Pith. sign in

REVIEW 2 major objections 5 minor 33 references

Fixed-Budget Change Point Identification in Piecewise Constant Bandits

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that fixed-budget change point identification in a piecewise constant bandit has two minimax error regimes, separated by a budget of order $\sigma^2/\Delta^2 \log(1/\eta)$, and gives algorithms that are near-optimal in…

desk verdict Solid first non-asymptotic treatment of a natural fixed-budget bandit problem; the backtracking operator is genuinely underspecified but easily fixable. read the letter →

arxiv 2501.12957 v1 pith:3SDIACYI submitted 2025-01-22 stat.ML cs.LG

Joseph Lazzaro , Ciara Pike-Burke This is my paper · ORCID
classification stat.MLcs.LG
keywords fixed-budgetbanditschangepointdetectionpiecewiseconstantrewardminimaxlowerboundsequentialhalvingadaptiveexplorationsub-Gaussiannoisepure
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

This paper establishes the first non-asymptotic, problem-dependent characterisation of how hard it is to locate one discontinuity in a piecewise constant reward function when the number of queries is fixed. Working on the action space $[0,1]$ with i.i.d. $\sigma^2$-sub-Gaussian noise and a pre-specified tolerance $\eta$, the authors prove minimax bounds on the probability that the estimated change point misses the true one by more than $\eta$. The bounds show two regimes: when the budget $T$ exceeds roughly $(\sigma^2/\Delta^2)\log(1/\eta)$, failure decays like $\exp(-\Theta(\Delta^2 T/\sigma^2))$ with extra precision costing only an additive log term; for smaller budgets failure decays like $\exp(-\Theta(\Delta^2 T/(\sigma^2 \log(1/\eta))))$, so demanding finer precision multiplies the sample cost. Two elimination algorithms, with and without backtracking, nearly match these lower bounds, and an adaptive algorithm achieves both rates without knowing $\Delta$ in advance.

What carries the argument

The argument is carried by phase-based elimination over the remaining interval, using five sampling points $\{0, a_1, a_2, a_3, 1\}$ in SHB and three points $\{a_1, a_2, a_3\}$ in SH. In each phase the algorithm compares absolute differences of empirical means, $|\hat{\mu}(a_1)-\hat{\mu}(a_2)|$ versus $|\hat{\mu}(a_2)-\hat{\mu}(a_3)|$, to decide which half of the interval contains the change point; SHB adds a second comparison that detects whether the change point has been eliminated entirely and, if so, backtracks to a previous interval. A phase counts as good when the right half is kept or a correct backtrack is made. SHB needs good decisions in at least three quarters of its $J = \lceil 6\log(1/2\eta)\rceil$ phases, while SH needs good decisions in every one of its $\lceil \log_2(1/2\eta)\rceil$ phases; this asymmetry is exactly why $\eta$ enters the small-budget exponent multiplicatively. Sub-Gaussian concentration, change-of-measure arguments between environments whose change points are spaced $2\eta$ apart, and Fano-style covering bounds supply the matching lower bounds.

What would settle it

With Gaussian rewards of variance $\sigma^2 = 1$, jump $\Delta = 2$, and tolerance $\eta = 0.1$, the small-budget lower bound forbids any policy from achieving failure probability below roughly $\exp(-\Delta^2 T/(\sigma^2 \log(1/2\eta)))$ for all $T < T_1$; a policy with adaptive sampling that provably beats this rate across a range of such $T$ would falsify Theorem 4 and the claimed minimax characterisation.

Watch

Extended reading notes

Core claim

The central claim is that the minimax error probability for fixed-budget change point identification is $\exp(-\Theta(\Delta^2 T/\sigma^2))$ when $T \geq T_1 \approx (\sigma^2/\Delta^2)\log(1/\eta)$ and $\exp(-\Theta(\Delta^2 T/(\sigma^2 \log(1/\eta))))$ when $T < T_1$. The paper proves an upper bound for Sequential Halving with Backtracking (SHB) and a matching lower bound for large budgets, plus an upper bound for Sequential Halving without backtracking (SH) and a matching lower bound for small budgets. An adaptive algorithm (SHA) spends a small fraction of the budget estimating $\Delta$, chooses between SH and SHB through the threshold $\tau = \gamma \sigma^2/\hat{\Delta}^2 \log(1/2\eta)$, and matches both lower bounds simultaneously up to constants. The separation is the main insight: when samples are scarce, finer tolerance degrades the error exponent multiplicatively, whereas in the large-budget regime precision adds only a constant number of log terms.

Load-bearing premise

The whole result depends on the reward function being exactly constant on each side of exactly one discontinuity, with i.i.d. $\sigma^2$-sub-Gaussian noise, and for the adaptive algorithm additionally on knowing $\sigma$ and getting an accurate estimate of the jump size from the two endpoints $0$ and $1$.

Editorial extensions

If this is right

  • For budgets above roughly $(\sigma^2/\Delta^2)\log(1/\eta)$, SHB fails with probability at most $\exp(-\Delta^2 T/(600\sigma^2) + 13\log(1/2\eta))$, and the lower bound shows the additive $\log(1/\eta)$ dependence is unavoidable.
  • For budgets below that threshold, SH fails with probability at most $2\lceil\log_2(1/2\eta)\rceil \exp(-T\Delta^2/(36\sigma^2 \log_2(1/2\eta)))$, matching the small-budget lower bound up to constants and a $\log\log(1/\eta)$ term.
  • The adaptive algorithm SHA matches both lower bounds without knowing the jump size $\Delta$, so a practitioner needs only the tolerance, the budget, and the noise scale.
  • The large-budget lower bound also sharpens the lower bound for monotonic thresholding bandits, showing that the additive dependence on precision in that problem is fundamental rather than an artifact of the upper-bound analysis.
  • Even in the noiseless setting, at least $\lceil \log_2(1/2\eta)\rceil$ samples are needed, so the sample requirement of SH is close to the information-theoretic floor.

Reading between the lines

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

  • The same two-regime structure should reappear with several change points or a multidimensional action space, with the budget threshold set by the smallest jump and the desired resolution, although the proof would need new covering arguments.
  • A testable prediction follows directly: on Gaussian simulations, plotting failure probability against budget should show a kink near $T_1$, and sweeping $\eta$ should reveal the multiplicative versus additive role of $\log(1/\eta)$ in the two regimes.
  • For bounded rewards with a known range, the adaptive algorithm's reliance on a known $\sigma$ could plausibly be replaced by bounding the sub-Gaussian constant with the range, extending SHA to settings where the noise variance is unknown.
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

2 major / 5 minor

Summary. The manuscript studies the fixed-budget identification of a single change point in a piecewise constant mean-reward function on [0,1], with sub-Gaussian bandit feedback and a pre-specified tolerance η. The central claims are: (i) a two-regime minimax characterization, with error probability exp(−Θ(Δ²T/σ²) + Θ(log(1/2η))) for large budgets T ≥ T1 and exp(−Θ(Δ²T/(σ² log(1/2η)))) for small budgets; (ii) the algorithms SHB and SH that attain these rates up to constants; (iii) the adaptive algorithm SHA, which estimates Δ from samples at the endpoints 0 and 1 and then runs SH or SHB, attaining near-optimal rates in both regimes simultaneously; and (iv) experiments comparing SH, SHB, and SHA against SRR, SR, and ACPD. Theorems 1 and 3 give upper bounds, Theorems 2 and 4 give matching lower bounds, and Theorem 5 bounds SHA's error probability in both regimes.

Significance. If the proofs are correct, this is the first non-asymptotic, problem-dependent characterization of the fixed-budget change-point-location problem under bandit feedback, and the two-regime separation in the dependence on η is a genuine contribution. The proof machinery is mostly self-contained and standard: concentration inequalities for the upper bounds, and change-of-measure and Fano/covering arguments for the lower bounds; the flat-environment change-of-measure technique in the large-budget lower bound is a nice ingredient that is also claimed to yield improved thresholding-bandit bounds. The algorithms are simple and the experiments are reproducible in principle, although no code is shipped. The main concerns are formal rather than conceptual: the backtracking operator P in SHB is underspecified, and Theorems 2 and 4 omit a domain condition on η. Both are repairable within the manuscript's scope.

major comments (2)
  1. [Section 4, Algorithm 1 line 15 and the paragraph defining P] The backtracking step `A_{j+1} ← P(A_j)` is not well-defined as written. In phase j=1 there is no previous phase, so P(A_1) has no value; the text never supplies a base case. Moreover, the formal definition "P(A_j) = A_i for an i such that A_j = R(A_i) or L(A_i)" does not specify a unique phase, because R and L are non-injective: for example, R({0,0,0.9,1,1}) = R({0,0.5,0.9,1,1}) = {0,0.9,0.95,1,1}. Different choices of the preimage can change the backtracked interval's width by more than a factor of two, so the width argument underlying Lemma 1 (which requires incorrect backtracks to at most double the interval width) is not guaranteed by the text. Since Theorems 1 and 5 are bounds for these algorithms, the central upper bounds are currently attached to an underspecified policy. The intended fix is straightforward and does not affect the rates: set P(A_1) := A_1 and define P as returning the most recent zoom parent, maintained via a stack (or otherwise fix a deterministic tie-break); with "most recent zoom parent" the backtracked interval has exactly twice the current width, and Lemma 1 goes through. The authors should add this specification and re-verify Lemma 1 under it.
  2. [Theorems 2 and 4, Sections 4.2 and 5.2] Both lower bounds omit the condition η < 1/4 (or η ≤ 1/4) that their proofs require. The constructions use K = ⌊1/2η⌋ environments with pairwise disjoint η-neighborhoods, and Lemma 7 and the Fano covering in Appendix E both need K ≥ 2. For η ∈ [1/4, 1/2), the right-hand side of Theorem 4 contains a division by log(⌊1/2η⌋) = 0, and the right-hand side of Theorem 2 contains log(0), so the statements are undefined outside the intended regime. Theorem 1 already states η < 1/4; the same hypothesis should be added to Theorems 2 and 4 (and the proof of Theorem 4 should state explicitly why T < T1 ensures the bootstrap step involving e^{-x} ≤ 1 − x/2 has 0 ≤ x ≤ 1.59).
minor comments (5)
  1. [Appendix C.4, Lemma 3] The statement of Lemma 3 declares C2 = 34, but the proof concludes with 13 log(1/2η), and Theorem 1's displayed bound uses 13. The statement and proof should be aligned.
  2. [Section 7 and Appendix B.1] The experimental hyperparameters for SHA are L = T/20 and γ = 120, but Theorem 5 requires γ ∈ ((√(104/B)+√1.59)², 1800/(1−B)); for B = 1/20 this lower bound is approximately 2195, so γ = 120 is outside the range covered by the theorem. The paper should either state that the theory is loose and does not cover the experimental parameters, or present experiments with parameters inside the theoretical range.
  3. [Algorithm 4, Section 6] The initial phase "Play actions 0,1 each L/2 times" requires L to be even, but the stated condition B ∈ (2/T, 1 − 2/T) with L = BT does not guarantee this. Add rounding or state that L is taken to be even.
  4. [Section 4.2] The claim that Theorem 2 yields "tighter lower bounds for Thresholding Bandits with large budgets" is made twice but no such statement is actually included in the paper; either provide the statement or soften the claim.
  5. [Throughout] There are several typos and notation slips: "Theorem 4 holds for hold for small budgets" (Section 5.2), "PAHS" for "PSHA" in Appendix H's equation (53), "to to the setting" (Appendix B.2), "beyong" (Appendix G.2), and "the the T Δ²" (Appendix B.1). The notation log vs. log2 is also used without a uniform base convention between Section 4 and Section 5; a brief clarifying sentence would help.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivation chain is self-contained (Hoeffding-based upper bounds, independent change-of-measure and Fano lower bounds, no load-bearing self-citations); the flagged issues - the underspecified backtracking operator P and experimental SHA hyperparameters lying outside Theorem 5's stated range - are formal gaps, not reductions of predictions to inputs.

full rationale

Derivation-chain audit. Upper bounds: Theorem 1 (SHB) rests on Lemmas 1-3: a combinatorial 'bad in fewer than 1/4 of phases' argument (Lemma 1, Appendix C.2), per-phase sub-Gaussian/Hoeffding tail bounds on the five empirical means (Lemmas 4-6, Appendix C.3), and a Chernoff/kl phase-counting bound (Lemma 3). No bound quantity is fitted: t_j = floor(T/5J) and J = ceil(6 log(1/2eta)) are fixed by the algorithm, and the 1/600 constant emerges from algebra. Theorem 3 (SH) is the same concentration machinery union-bounded over J = ceil(log2(1/2eta)) phases; the 1/log2(1/2eta) factor is forced because every phase must be correct. Lower bounds: Theorem 2 is a change-of-measure/Bretagnolle-Huber argument (Lemmas 7-10, Appendix D) over K = floor(1/2eta) hypotheses spaced 2eta apart; the additive log(1/eta) arises from the packing of the change-point grid, not from the upper bounds. Theorem 4 is a Fano/covering argument (Lemma 11, Appendix E); the 1/log(floor(1/2eta)) factor is the Fano denominator. The regime threshold T1 = (sigma^2/Delta^2)(1.59 log(floor(1/2eta)) - 2 log 2) is a proof constant, not a fitted value: 1.59 is the point where e^{-x} <= 1 - x/2 holds, and each theorem is proven independently on its side of T1, so the claimed regime separation is a statement about two independent bounds. Self-citations: none are load-bearing; the bibliography contains no Lazzaro/Pike-Burke works, and the only delegation is to Cheshire et al. (2021), an external ICML paper, for proof skeletons of Lemmas 1 and 3, with Lemmas 2, 4-6 supplying the continuous-action-space and unknown-mean adaptations. SHA (Theorem 5, Appendix H) decomposes failure probability by the chosen sub-algorithm and bounds the mis-choice probability by Hoeffding on Delta-hat_L; the threshold event is an algebra inversion (T >= tau iff Delta-hat_L >= theta_Delta), not an estimate renamed as a prediction. No step reduces a claimed result to its own inputs. Flagged but non-circular concerns: (a) Algorithm 1 line 15 applies P(A_j) with no base case at j = 1, and the formal definition 'P(Aj) = Ai such that Aj = R(Ai) or L(Ai)' is ambiguous because R and L are non-injective (R ignores its first interior point, L ignores its last), so the immediate backtracking parent is not a function of the set A_j; this is an executability gap in the central algorithms, not a circular step, and it is benign at j = 1 because a1 = 0 and a3 = 1 force Q1 = max(Q2, Q3), making E_{P,1} identically false.

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

The theoretical results introduce no fitted parameters beyond the problem inputs (T, η, Δ, σ). The algorithms contain design constants (the 3/4 in E_{P,j}, the phase counts J) and two user-chosen SHA hyperparameters (γ, B) for which a range of values is proven sufficient. The only ad hoc element is the underspecified backtracking operator in phase 1. No new physical or model entities are introduced.

free parameters (2)
  • γ (SHA threshold scaling) = 120 in experiments
    SHA's regime threshold τ = γ σ²/Δ̂_L² log(1/2η). Theorem 5 states a range for γ that makes the universal bound hold; the experiments fix γ=120 as a practical choice.
  • B = L/T (SHA exploration fraction) = 1/20 in experiments
    SHA spends L=BT samples estimating Δ. Theorem 5 specifies a range for B; experiments use B=1/20.
assumptions (4)
  • domain assumption Reward function is exactly step-shaped with a single discontinuity and i.i.d. sub-Gaussian noise
    This is the problem definition in Section 3; all theorems are proved under it. If the function is only approximately piecewise constant or the noise is heavy-tailed, the stated error bounds do not follow.
  • domain assumption For SHA, the noise scale σ is known to the learner
    Stated in Section 6, footnote 1. SHA's threshold uses σ as an input; without it, the regime selection cannot be implemented as claimed.
  • standard math Standard concentration and information-theoretic inequalities (Hoeffding, sub-Gaussian tail bounds, Fano, Bretagnolle-Huber, KL divergence decomposition)
    Used throughout Appendices C-H. These are standard results invoked without proof.
  • ad hoc to paper The backtracking operator P is well-defined in every phase including phase 1
    Algorithm 1 calls P(A_j) whenever E_{P,j} holds, but in phase 1 there is no previous set of actions. The paper does not specify P(A_1); the proof of the good event G_1 assumes this case is handled.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fixed-Budget Change Point Identification in Piecewise Constant Bandits." pith.science (2026). https://pith.science/paper/3SDIACYI

@misc{pith2026250112957,
  author       = {Pith},
  title        = {Pith review of: Fixed-Budget Change Point Identification in Piecewise Constant Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3SDIACYI}},
  note         = {Machine review of arXiv:2501.12957}
}
abstract

We study the piecewise constant bandit problem where the expected reward is a piecewise constant function with one change point (discontinuity) across the action space $[0,1]$ and the learner's aim is to locate the change point. Under the assumption of a fixed exploration budget, we provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback. We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability and provide algorithms with near matching upper bounds. Interestingly, our results show a separation in the complexity of the two regimes. We then propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.

Figures

Figures reproduced from arXiv: 2501.12957 by the authors.

Figure 1
Figure 1. Example of a piecewise constant mean reward function, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Example illustration of action space A = [0, 1] in (Top) phase j with sampling points Aj = {0, a j 1 , a j 2 , a j 3 , 1} and (Bottom) phase j + 1 with sampling points Aj+1 = {0, a j+1 1 , a j+1 2 , a j+1 3 , 1}, where the shaded regions have been eliminated. In this example, ER,j held and region [a j 1 , a j 2 ) was eliminated in phase j. at any point we think the remaining region no longer contains the change poin… view at source ↗
Figure 3
Figure 3. Proportion of final estimates more than η away from x ∗ against the inputted budget, T, with Gaussian rewards, ∆ = 2 and 90% CIs. (a) compares the SH, SHB, and SHA by running each algorithm 1000 times with different budgets. (b,c) both compare SH, SRR, and ACPD. We run SH and SRR 500 times each at different budgets, while the anytime ACPD algorithm is run a total of 500 times for T = 60 and we plot the evolution of … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Proportion of final estimates more than η away from x ∗ against the inputted budget, T, with Gaussian rewards, ∆ = 2 and 90% CIs. SH, SHB, and SHA were each run 1000 times with different budgets. In [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Proportion of final estimates more than η away from x ∗ against the inputted budget, T, with Gaussian rewards, ∆ = 2 and 90% CIs. SH, SHB, and SHA were each run 1000 times with different budgets. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: Proportion of final estimates more than η away from x ∗ against the inputted budget, T, with Gaussian rewards, ∆ = 2 and 90% CIs. SH, SHB, SHA, SRR, and SR were each run 500 times with different budgets, while the anytime ACPD algorithm is run a total of 500 times for …
Figure 7
Figure 7. Figure 7: Proportion of final estimates more than η away from x ∗ against the inputted budget, T, with Gaussian rewards, ∆ = 2 and 90% CIs. SH, and tuned SRR were each run 500 times with different budgets. In (a) the tuned constants for SRR tuned were α ≈ 0.28, β ≈ 0.41. In (b) …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 28 canonical work pages

  1. [1]

    Abbasi-Yadkori, D

    Y. Abbasi-Yadkori, D. P\' a l, and C. Szepesv\' a ri. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011

    work page 2011

  2. [2]

    Agarwal, D

    A. Agarwal, D. P. Foster, D. J. Hsu, S. M. Kakade, and A. Rakhlin. Stochastic convex optimization with bandit feedback. In Advances in Neural Information Processing Systems, 2011

    work page 2011

  3. [3]

    Aminikhanghahi and D

    S. Aminikhanghahi and D. Cook. A survey of methods for time series change point detection. Knowledge and Information Systems, 2017

    work page 2017

  4. [4]

    Audibert, S

    J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In COLT 2010 - The 23rd Conference on Learning Theory, 2010

    work page 2010

  5. [5]

    L. D. Brown, T. T. Cai, and A. DasGupta. Interval Estimation for a Binomial Proportion . Statistical Science, 2001

    work page 2001

  6. [6]

    Bubeck, R

    S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvári. X-armed bandits. Journal of Machine Learning Research, 2011

    work page 2011

  7. [7]

    Carpentier and A

    A. Carpentier and A. Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Annual Conference Computational Learning Theory, 2016

    work page 2016

  8. [8]

    R. M. Castro and R. D. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 2008

    work page 2008

Show all 33 references
  1. [9]

    R. M. Castro, R. M. Willett, and R. D. Nowak. Faster rates in regression via active learning. In Advances in Neural Information Processing Systems, 2005

    2005

  2. [10]

    Chen and A

    J. Chen and A. K. Gupta. Parametric Statistical Change Point Analysis: With Applications to Genetics, Medicine, and Finance; 2nd ed. Springer, 2012

    2012

  3. [11]

    Cheshire, P

    J. Cheshire, P. Menard, and A. Carpentier. Problem dependent view on structured thresholding bandit problems. In Proceedings of the 38th International Conference on Machine Learning, 2021

    2021

  4. [12]

    Dasgupta

    S. Dasgupta. Coarse sample complexity bounds for active learning. Advances in Neural Information Processing Systems, 2005

    2005

  5. [13]

    Garivier and E

    A. Garivier and E. Moulines. On upper-confidence bound policies for switching bandit problems. In Algorithmic Learning Theory, 2011

    2011

  6. [14]

    Garivier, P

    A. Garivier, P. Ménard, and G. Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 2016

    2016

  7. [15]

    Gramacy and H

    R. Gramacy and H. Lee. Adaptive design and analysis of supercomputer experiments. Technometrics, 2008

    2008

  8. [16]

    Hall and I

    P. Hall and I. Molchanov. Sequential methods for design-adaptive estimation of discontinuities in regression curves and surfaces . The Annals of Statistics, 2003

    2003

  9. [17]

    Hayashi, Y

    S. Hayashi, Y. Kawahara, and H. Kashima. Active change-point detection. In Proceedings of The Eleventh Asian Conference on Machine Learning, 2019

    2019

  10. [18]

    Karnin, T

    Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, 2013

    2013

  11. [19]

    R. M. Karp and R. D. Kleinberg. Noisy binary search and its applications. In ACM-SIAM Symposium on Discrete Algorithms, 2007

    2007

  12. [20]

    Kleinberg, A

    R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008

    2008

  13. [21]

    Y. Lan, M. Banerjee, and G. Michailidis. Change-point estimation under adaptive sampling. The Annals of Statistics, 2009

    2009

  14. [22]

    Lattimore and C

    T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020

    2020

  15. [23]

    Locatelli, M

    A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In Proceedings of The 33rd International Conference on Machine Learning, 2016

    2016

  16. [24]

    Z. Lu, M. Banerjee, and G. Michailidis. Intelligent sampling for multiple change-points in exceedingly long time series with rate guarantees. In ArXiv Preprint ArXiv:1710.07420, 2020

    2020 arXiv

  17. [25]

    Mannor, J

    S. Mannor, J. Tsitsiklis, K. Bennett, and N. Cesa-bianchi. The sample complexity of exploration in the multi-armed bandit problem. 2004

    2004

  18. [26]

    C. Park, P. Qiu, J. Carpena-Núñez, R. Rao, M. Susner, and B. Maruyama. Sequential adaptive design for jump regression estimation. In ArXiv Preprint ArXiv:1904.01648, 2021

    1904 arXiv

  19. [27]

    C. Park, R. Waelder, B. Kang, B. Maruyama, S. Hong, and R. Gramacy. Active learning of piecewise gaussian process surrogates. In ArXiv Preprint ArXiv:2301.08789, 2023

    2023 arXiv

  20. [28]

    Sikorski

    K. Sikorski. Bisection is optimal. Numerische Mathematik, 40: 0 111--118, 1982

    1982

  21. [29]

    Srinivas, A

    N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML 2010 - Proceedings, 27th International Conference on Machine Learning, 2010

    2010

  22. [30]

    Thuot, A

    V. Thuot, A. Carpentier, C. Giraud, and N. Verzelen. Active clustering with bandit feedback. In ArXiv Preprint ArXiv:2406.11485, 2024

    2024 arXiv

  23. [31]

    M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019

    2019

  24. [32]

    J. Yang, Z. Zhong, and V. Y. F. Tan. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 2022

    2022

  25. [33]

    R. C. Yavas, Y. Huang, V. Y. F. Tan, and J. Scarlett. A general framework for clustering and distribution matching with bandit feedback. In ArXiv Preprint ArXiv:2409.05072, 2024

    2024 arXiv

Pith tools

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