REVIEW 4 major objections 6 minor 26 references
Fast, Precise Thompson Sampling for Bayesian Optimization
T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper claims that Stagger Thompson Sampling (STS), a Hit-and-Run Markov-chain sampler with a log-uniform 'stagger' proposal and a start at the GP mean's maximizer, produces more precise Thompson samples in Bayesian optimization while…
desk verdict The algorithm is empirically promising and the ablations are solid, but the claim that STS samples from p*(x) is false: the stagger proposal is asymmetric and the Hastings correction is missing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is $p^*(x)$, the probability that a position $x$ is the global maximizer of the Gaussian process model; the ideal Thompson acquisition is a draw from $p^*$, and STS is an engine for approximating those draws. The engine combines three parts: (1) a Hit-and-Run Markov chain that moves along lines from the current point to uniformly random targets inside $[0,1]^d$; (2) a 'stagger' proposal whose step length is log-uniform, $s \sim e^{-kU}$, chosen so a single scale parameter $k=\ln 10^{-6}$ covers both tiny and large perturbations without adaptation; and (3) a Metropolis-style acceptance step that uses one joint GP sample at the pair of points, accepting whichever has the higher draw. The whole loop runs about $M=30$ times and returns the final point as an approximate Thompson arm.
What would settle it
Take a low-dimensional GP with a known posterior, run STS for $M=30$ iterations many times, and compare the empirical distribution of arms against a high-accuracy reference for $p^*(x)$ computed by dense-grid or exhaustive Monte Carlo integration; a substantial total-variation distance, or a clear increase in a standard MCMC mixing diagnostic with the number of iterations, would refute the claim that STS samples from $p^*$. A second check would time STS against standard TS with 10,000 candidates on the same GP: if TS already achieves the same or better precision in less wall-clock time, the speed claim fails.
Extended reading notes
Core claim
The paper's central discovery is that a useful Thompson sample can be computed by a short Metropolis-Hastings walk rather than by maximizing a GP draw over a large set of i.i.d. candidates. The walk, STS, starts at $\tilde{x}^* = \arg\max_x\mu(x)$, and in each of $M \approx 30$ iterations chooses a target $x_t \sim U([0,1]^d)$ and a step length $s \sim e^{-k U([0,1])}$ with $k=\ln 10^{-6}$, proposing $x'_a = x_a + s(x_t - x_a)$. The proposal is accepted if $y' > y$ for a single joint GP sample $[y,y'] \sim \mathrm{GP}([x_a,x'_a])$, an approximation to the Metropolis ratio that the paper calls iterated Thompson sampling. The experiments reported in the paper are designed to show that this produces arms with smaller RMSE to the true maximizer than standard TS, at lower wall-clock cost, and that the resulting acquisition scores highest in rank-based comparisons across dimensions.
Load-bearing premise
Everything rests on the assumption that Algorithm 1's short Markov chain, started at the GP mean's maximizer and filtered by one joint GP draw per step, actually converges to $p^*(x)$; the paper offers no mixing proof, and its Appendix A check (low standard deviation of estimated $p_{\max}$ values) is explicitly a necessary condition, not a sufficient one.
Editorial extensions
If this is right
- Standard TS's candidate flood can be replaced by roughly 30 short walk iterations per arm, cutting per-arm computation while improving precision.
- STS works without modification in dimensions 3 to 300, so high-dimensional Bayesian optimization does not require a trust region or a separate adaptation phase for this acquisition method.
- STS is a drop-in replacement for PSS inside MTV: the paper reports that mtv+sts matches mtv across dimensions and batch sizes, while also performing well as a standalone sampler.
- Because STS starts from $\tilde{x}^*$ and uses log-uniform steps, its samples concentrate near the current best guess; the appendix attributes the improvement over TS to reduced scale of the sample distribution rather than to reduced bias.
Reading between the lines
- If STS's mixing assumption holds, the single-joint-GP-draw acceptance filter is a general recipe: any model with cheap paired draws could be used to build approximate Thompson samplers, so the idea is not GP-specific.
- A natural test not run in the paper is to replace the single joint draw with an exact Metropolis ratio estimated by many Monte Carlo samples and compare mixing; if the exact-ratio chain does not mix materially better, the single-draw filter is not the main source of bias.
- The rank-based score used in the experiments may obscure absolute objective gains; an unpublished but testable comparison is simple-regret curves (best value versus evaluations) on the same distorted test functions.
- STS's lack of an initialization requirement suggests a unified acquisition for both initial design and later batches in MTV+STS, potentially removing Sobol seeding from batch BO.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Stagger Thompson Sampler (STS), a Markov-chain-based acquisition method for Bayesian optimization. STS modifies Hit-and-Run with a log-uniform "stagger" perturbation, initializes the chain at the posterior mean maximizer, and uses a single joint Gaussian process sample to decide whether to accept a proposal. The authors claim that STS draws samples from p*(x), the probability that a point is the global maximizer under the GP model, and report that STS outperforms Thompson sampling, PSS, and several other acquisition functions on nine test functions across dimensions 3-300, while also matching PSS when used as the input to the Minimal Terminal Variance batching algorithm. The appendix provides ablations on initialization and proposal distribution and a tuning study for the iteration count M.
Significance. The empirical study is broad and carefully structured: nine test functions, multiple random distortions, several dimensions, multiple baselines, and error bars are included, and the ablation studies are informative. If the central sampling claim were correct, STS would be a simple and dimension-scalable Thompson sampling method, and the combination STS+MTV would be a practically useful contribution. The empirical results may indeed describe a useful heuristic, but the paper's theoretical foundation, which is the basis for calling STS a Thompson sampler, is not established and, as shown below, is in fact invalid for the algorithm as stated.
major comments (4)
- [Section 2, Algorithm 1] The stagger proposal is not symmetric, so the chain does not target p*(x). For a fixed s, the transformation x' = x + s(xt - x) has Jacobian s^{-d} with respect to xt, and the set of s values for which xt = (x' - (1-s)x)/s lies in [0,1]^d depends on x and x' asymmetrically. In d=1, take x=0.1, x'=0.5, and s_min -> 0. The forward move requires s >= 0.4/0.9 = 0.444, giving q(x'|x) proportional to ∫_{0.444}^{1} s^{-2} ds = 1.25; the reverse move requires s >= 0.4/0.5 = 0.8, giving q(x|x') proportional to ∫_{0.8}^{1} s^{-2} ds = 0.25. Thus q(x'|x)/q(x|x') = 5, so the proposal is not symmetric. Since Algorithm 1 accepts with min{1, p*(x')/p*(x)} and omits the Hastings correction, the chain is not reversible with respect to p* and its stationary distribution is not p*. The statement in Section 2 that 'a log-uniform distribution is a symmetric proposal' is therefore incorrect, and this affects a load-bearing claim: even a fully mixed chain following Algorithm 1 would not produce Thompson samples from p*(x).
- [Section 2, acceptance rule; Appendix A] The acceptance rule uses a single joint GP sample at {x, x'} and accepts x' when y' > y. The target p*(x) is the probability that x is the global maximizer over the whole domain, but the event y' > y only compares the two points under the GP draw. Therefore the acceptance does not implement min{1, p*(x')/p*(x)} even if the proposal were symmetric; the chain has a different, unspecified stationary distribution. Appendix A's std(p_max) diagnostic is, as the paper itself acknowledges, only a necessary condition and not sufficient; it cannot establish that the samples come from p*. No mixing proof, convergence rate, or stationary-distribution analysis is provided. This is a second load-bearing gap between Algorithm 1 and the Thompson-sampling interpretation.
- [Section 3.2 and Appendix B, Figure 7] The hyperparameter M (the number of refinement iterations) is selected by sweeping on the same nine test functions used in the main evaluation (Figure 3), and the value M=30 is then used in the main comparisons. This constitutes model selection on the evaluation set, so the reported performance advantage may be inflated. The paper should either tune M on a separate held-out set of functions or report the main results across a range of M values to show that the conclusion is robust to this choice.
- [Section 3, experimental protocol] The empirical protocol is under-specified. No code is provided, and the GP kernel, hyperparameter handling, lengthscale bounds, noise model, and the random distortion procedure 'as in [17]' are not described. Without these details, the results of the 874,800-evaluation comparison cannot be reproduced or checked for implementation errors, which is particularly important given that the theoretical sampler claims are in question.
minor comments (6)
- [Section 1, reference [10]] Expected Improvement is cited as [10], but that reference is about experimental design for generalized linear models, not the EI acquisition function; the canonical citation is [12] (Mockus).
- [Section 3.1] The score definition uses the symbol M for the number of methods, but M is already used in Algorithm 1 for the number of refinement iterations; this notation collision is confusing.
- [Figure 5 caption] The caption calls sobol an 'optimizer' that 'proposes arms uniformly randomly'; it is a quasi-random sampling method, not an optimizer, and the wording should be corrected.
- [Appendix B, Figure 7] The sweep over M is shown without error bars or multiple runs; the claim that performance 'stabilizes around M=30' is based on point estimates and needs statistical support.
- [Section 3.3] The text reports '1.2 · 106' function evaluations, which appears to be a typographical error for 1.2 × 10^6.
- [Section 2, Algorithm 1] The paper should state explicitly that the stagger proposal is log-uniform on [10^{-6}, 1] and provide its density; the current description 's = e^{-kU}' requires the reader to infer the range and normalization.
Circularity Check
No significant circularity: the headline empirical claims are benchmarked against external baselines, and the sampler-convergence assertion is an omitted proof rather than a reduction to its inputs.
full rationale
Walking the paper's argument chain, I find no step in which a claimed prediction is identical to an input by construction. The headline comparison (STS vs TS, PSS, EI, UCB, GIBBON, TuRBO, CMA-ES, etc.) is an external benchmark study on standard test functions; the score is defined from ranks of measured function values, not from STS's own internal parameters. The theoretical claim that Algorithm 1 samples p*(x) rests on the assertion in Section 2 that 'a log-uniform distribution is a symmetric proposal' and on Appendix A's numerical check. That assertion is not established (the induced proposal kernel is not symmetric), and Appendix A itself concedes the pmax test is only necessary: 'While low std(pmax) is a necessary condition to claim that xi ∼ p∗(x), it is not sufficient.' This is an omitted or incorrect proof of stationarity, not a case where the result equals its input by construction; the algorithm is not defined in terms of p*(x) beyond the standard Metropolis acceptance target and its coarse single-sample approximation. The self-citations are not load-bearing: [17] supplies the PSS baseline, the MTV objective, and the function-distortion protocol, while [21] only supplies the term 'stagger' and a proposal idea; neither is invoked as an external theorem that forces the paper's conclusions. The tuning of M=30 and k=ln(10^-6) on the same benchmark functions is a methodological weakness, but hyperparameter selection followed by evaluation is not a fitted-input-called-prediction pattern, since the reported scores are measured function values, not the fitted parameters. Verdict: no significant circularity.
Assumptions & free parameters
free parameters (2)
- k (stagger proposal exponent) =
ln(1e-6) approximately -13.8
- M (number of refinement iterations) =
30
assumptions (3)
- domain assumption The Gaussian process posterior accurately models the objective f and its maximizer distribution p*(x).
- ad hoc to paper The Hit-and-Run Markov chain with a single joint GP sample as the Metropolis acceptance approximation converges to p*(x).
- ad hoc to paper The log-uniform stagger proposal is symmetric on the state space [0,1]^d.
Cite this review
Pith. "Pith review of Fast, Precise Thompson Sampling for Bayesian Optimization." pith.science (2026). https://pith.science/paper/LAPZDXCA
@misc{pith2026241117071,
author = {Pith},
title = {Pith review of: Fast, Precise Thompson Sampling for Bayesian Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/LAPZDXCA}},
note = {Machine review of arXiv:2411.17071}
}
read the original abstract
Thompson sampling (TS) has optimal regret and excellent empirical performance in multi-armed bandit problems. Yet, in Bayesian optimization, TS underperforms popular acquisition functions (e.g., EI, UCB). TS samples arms according to the probability that they are optimal. A recent algorithm, P-Star Sampler (PSS), performs such a sampling via Hit-and-Run. We present an improved version, Stagger Thompson Sampler (STS). STS more precisely locates the maximizer than does TS using less computation time. We demonstrate that STS outperforms TS, PSS, and other acquisition methods in numerical experiments of optimizations of several test functions across a broad range of dimension. Additionally, since PSS was originally presented not as a standalone acquisition method but as an input to a batching algorithm called Minimal Terminal Variance (MTV), we also demon-strate that STS matches PSS performance when used as the input to MTV.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[17]
Optimal Initialization of Batch Bayesian Optimization
Jiuge Ren and David Sweet. Optimal Initialization of Batch Bayesian Optimization . 2024. arXiv: 2404.17997 [cs.LG]. URL: https://arxiv.org/abs/2404.17997. 6
work page Pith review arXiv 2024
-
[1]
Further Optimal Regret Bounds for Thompson Sampling
Shipra Agrawal and Navin Goyal. Further Optimal Regret Bounds for Thompson Sampling
-
[2]
A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization
Hildo Bijl et al. A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization. 2017. arXiv: 1604 . 00169 [stat.ML]. URL: https : / / arxiv . org / abs / 1604.00169
arXiv 2017
-
[3]
An Empirical Evaluation of Thompson Sampling
Olivier Chapelle and Lihong Li. “An Empirical Evaluation of Thompson Sampling”. In: Ad- vances in Neural Information Processing Systems . Ed. by J. Shawe-Taylor et al. V ol. 24. Curran Associates, Inc., 2011. URL: https://proceedings.neurips.cc/paper_files/ paper/2011/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf
work page 2011
-
[4]
Unexpected improvements to expected improvement for Bayesian optimization
Samuel Daulton et al. “Unexpected improvements to expected improvement for Bayesian optimization”. In: Proceedings of the 37th International Conference on Neural Information Processing Systems. NIPS ’23. New Orleans, LA, USA: Curran Associates Inc., 2024
work page 2024
-
[5]
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
Thomas Desautels, Andreas Krause, and Joel Burdick. Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization . 2012. arXiv: 1206.6402 [cs.LG]. URL: https://arxiv.org/abs/1206.6402
work page Pith review arXiv 2012
-
[6]
Scalable Global Optimization via Local Bayesian Optimization
David Eriksson et al. “Scalable Global Optimization via Local Bayesian Optimization”. In: Advances in Neural Information Processing Systems. Ed. by H. Wallach et al. V ol. 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper_files/paper/ 2019/file/6c990b7aca7bc7058f5e98ea909e924b-Paper.pdf
work page 2019
- [7]
Show all 26 references
-
[8]
The CMA Evolution Strategy: A Tutorial
Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial . 2023. arXiv: 1604 . 00772 [cs.LG]. URL: https://arxiv.org/abs/1604.00772
2023 arXiv
-
[9]
Parallelised Bayesian Optimisation via Thompson Sampling
Kirthevasan Kandasamy et al. “Parallelised Bayesian Optimisation via Thompson Sampling”. In: Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. Ed. by Amos Storkey and Fernando Perez-Cruz. V ol. 84. Proceedings of Machine Learni...
2018
-
[10]
An efficient algorithm for Elastic I-optimal design of generalized linear models
Yiou Li and Xinwei Deng. “An efficient algorithm for Elastic I-optimal design of generalized linear models”. In: Canadian Journal of Statistics 49.2 (2021), pp. 438–470. DOI: https: //doi.org/10.1002/cjs.11571 . eprint: https://onlinelibrary.wiley.com/doi/ pdf/10.1002/cjs.1157...
2021 doi
-
[11]
Meta. BoTorch. 2024. URL: https://botorch.org
2024
-
[12]
On bayesian methods for seeking the extremum
J. Mo ˇckus. “On bayesian methods for seeking the extremum”. In: Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974. Ed. by G. I. Marchuk. Berlin, Hei- delberg: Springer Berlin Heidelberg, 1975, pp. 400–404. ISBN : 978-3-540-37497-8
1974
-
[13]
GIBBON: General-purpose Information-Based Bayesian Optimisa- tion
Henry B. Moss et al. “GIBBON: General-purpose Information-Based Bayesian Optimisa- tion”. In: Journal of Machine Learning Research 22.235 (2021), pp. 1–49. URL: http:// jmlr.org/papers/v22/21-0120.html
2021
-
[14]
Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes
Elvis Nava, Mojmir Mutny, and Andreas Krause. “Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes”. In:Proceedings of The 25th International Conference on Artificial Intelligence and Statistics . Ed. by Gustau Camps-Valls, Francisco J. R....
2022
-
[15]
Optuna. Optuna. 2024. URL: https://optuna.org
2024
-
[16]
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. MIT Press, 2006, pp. I–XVIII, 1–248. ISBN : 026218253X
2006
-
[18]
Santner, Brian J
Thomas J. Santner, Brian J. Williams, and William I. Notz. The Design and Analysis of Com- puter Experiments. Springer New York, NY, 2019. ISBN : 9781493988471. DOI: https:// doi.org/10.1007/978-1-4939-8847-1 . URL: https://link.springer.com/book/ 10.1007/978-1-4939-8847-1
2019 doi
-
[19]
The hit-and-run sampler: a globally reaching Markov chain sampler for generating arbitrary multivariate distributions
Robert L. Smith. “The hit-and-run sampler: a globally reaching Markov chain sampler for generating arbitrary multivariate distributions”. In: Proceedings of the 28th Conference on Winter Simulation. WSC ’96. Coronado, California, USA: IEEE Computer Society, 1996, pp. 260–264. ...
1996
-
[20]
Surjanovic and D
S. Surjanovic and D. Bingham. Virtual Library of Simulation Experiments: Test Functions and Datasets. Accessed: 2024-08-20. 2024. URL: https : / / www . sfu . ca /~ssurjano / optimization.html
2024
-
[21]
Stagger-and-Step Method: Detecting and Computing Chaotic Saddles in Higher Dimensions
David Sweet, Helena E. Nusse, and James A. Yorke. “Stagger-and-Step Method: Detecting and Computing Chaotic Saddles in Higher Dimensions”. In: Phys. Rev. Lett. 86 (11 Mar. 2001), pp. 2261–2264. DOI: 10 . 1103 / PhysRevLett . 86 . 2261. URL: https : / / link . aps.org/doi/10.11...
2001 doi
-
[22]
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
William R Thompson. “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples”. In:Biometrika 25.3-4 (Dec. 1933), pp. 285–294. ISSN : 0006-3444. DOI: 10 . 1093 / biomet / 25 . 3 - 4 . 285. eprint: https : / / academic . oup . com/bi...
1933 doi
-
[23]
Tree-structured Parzen estimator: Understanding its algorithm components and their roles for better empirical performance
S. Watanabe. “Tree-structured Parzen estimator: Understanding its algorithm components and their roles for better empirical performance”. In: arXiv preprint arXiv:2304.11127 (2023)
2023 arXiv
-
[24]
Wilson et al
James T. Wilson et al. The reparameterization trick for acquisition functions . 2017. arXiv: 1712.00424 [stat.ML]. URL: https://arxiv.org/abs/1712.00424
2017 arXiv
-
[25]
Improving sample efficiency of high dimensional Bayesian optimization with MCMC
Zeji Yi et al. Improving sample efficiency of high dimensional Bayesian optimization with MCMC. 2024. arXiv: 2401 . 02650 [cs.LG]. URL: https : / / arxiv . org / abs / 2401 . 02650. 7 A Speed, Precision, and Thompson Sampling In this appendix we provide numerical support for t...
2024
-
[2012]
URL: https://arxiv.org/abs/1209.3353
arXiv: 1209.3353 [cs.LG]. URL: https://arxiv.org/abs/1209.3353
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.