A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback

Da-shan Shiu; Davide Buffelli; Joseph Lazzaro; Sattar Vakili

arxiv: 2604.25025 · v1 · submitted 2026-04-27 · 📊 stat.ML · cs.LG

A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback

Joseph Lazzaro , Davide Buffelli , Da-shan Shiu , Sattar Vakili This is my paper

Pith reviewed 2026-05-07 17:41 UTC · model grok-4.3

classification 📊 stat.ML cs.LG

keywords Thompson samplingBayesian optimizationpreferential feedbackpairwise comparisonsfinite-time analysisdueling kernelregret boundsanchor invariance

0 comments

The pith

Thompson sampling for Bayesian optimization matches standard finite-time performance when feedback is given only as pairwise preferences.

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

The paper introduces a Thompson sampling procedure for Bayesian optimization that receives only comparative feedback rather than scalar values. Comparisons are modeled by passing latent utility differences through a monotone link function, which induces a dueling kernel from any base kernel. A finite-time analysis is derived that shows the resulting regret bounds are identical to those of ordinary Thompson sampling under scalar observations. The result matters because many real design and discovery loops naturally supply comparative judgments from humans or instruments, and matching guarantees remove a theoretical obstacle to deploying the method in those settings.

Core claim

The proposed Thompson sampling algorithm, built on the dueling kernel and using anchor-invariant challenger selection together with a double-TS pairing variant, attains the same finite-time regret bounds as standard Thompson sampling for scalar Bayesian optimization. The analysis exploits the invariance property to control the selection of challengers and demonstrates that the preference model introduces no additional asymptotic or finite-time penalty under the stated kernel and link assumptions.

What carries the argument

The dueling kernel induced by a base kernel combined with a monotone link function on latent utility differences, which lets the preference model inherit the concentration and regret properties required for the finite-time analysis.

If this is right

The same theoretical guarantees apply immediately to human-in-the-loop and expert-in-the-loop design tasks.
Anchor invariance removes the need for extra computation when selecting which point to compare against the current best.
The double-TS pairing variant supplies a practical implementation that preserves the proven bounds.
Performance equivalence holds on both synthetic benchmarks and real-world preference data sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same construction may be combined with other link functions or non-stationary kernels while retaining finite-time control.
Hybrid feedback schemes that mix occasional scalar observations with comparisons could inherit the same bounds without modification.
The invariance argument might extend to settings with multiple simultaneous comparators or group-level preferences.

Load-bearing premise

Pairwise comparisons can be represented as the output of a monotone link applied to the difference of two latent utilities, and the resulting dueling kernel satisfies the technical conditions needed for the regret analysis to hold.

What would settle it

A specific kernel and link function pair where the cumulative regret of the preferential Thompson sampling exceeds the scalar Thompson sampling bound by more than a constant factor on a simple one-dimensional test problem.

Figures

Figures reproduced from arXiv: 2604.25025 by Da-shan Shiu, Davide Buffelli, Joseph Lazzaro, Sattar Vakili.

**Figure 1.** Figure 1: Selected xt under TS (blue) and UCB (orange) as the anchor x0 varies. Utility is the Ackley function; the history contains 200 uniformly sampled pairs. TS is anchor invariant: the chosen xt does not change with x0, whereas the point chosen by UCB depends on the anchor. which is the primary focus of this paper. Nevertheless, the uncertainty estimates used by our method can themselves be approximated. For… view at source ↗

**Figure 2.** Figure 2: Regret of PF-TS, MR-LPF, MaxMinLCB, POP-BO, and GP-TS. Mean over 30 runs; bands show view at source ↗

**Figure 3.** Figure 3: Instantaneous (simple) regret versus total view at source ↗

**Figure 4.** Figure 4: Regret of PF-TS, MR-LPF, MaxMinLCB, POP-BO, and GP-TS. Mean over 30 runs; shaded bands view at source ↗

**Figure 5.** Figure 5: Visualization of Ackley utility function used in experiments. view at source ↗

**Figure 6.** Figure 6: Visualization of utility function sampled from RKHS used in experiments. view at source ↗

read the original abstract

Preference feedback, in the form of pairwise comparisons rather than scalar scores, has seen increasing use in applications such as human-, laboratory-, and expert-in-the-loop design, as well as scientific discovery. We propose a Thompson Sampling (TS) approach to Bayesian optimization with preferential feedback that models comparisons using a monotone link on latent utility differences and leverages the dueling kernel induced by a base kernel. We provide a finite-time analysis showing that the performance of the proposed method matches that of standard TS for conventional Bayesian optimization with scalar feedback. The analysis exploits the anchor invariance of TS for challenger selection and introduces a double-TS pairing variant. We also demonstrate the performance of the method on both synthetic and real-world examples.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper adapts Thompson Sampling to preferential Bayesian optimization and shows the finite-time regret bound carries over unchanged from the scalar-feedback case.

read the letter

This paper adapts Thompson Sampling to preferential Bayesian optimization and shows the finite-time regret bound carries over unchanged from the scalar-feedback case. They model pairwise comparisons with a monotone link on latent utility differences, induce a dueling kernel from a base kernel, and use the anchor invariance of TS to pick challengers. A double-TS pairing handles the comparison step. The analysis then reuses the standard TS regret machinery, and they include experiments on synthetic functions plus some real preference data. That clean transfer of the bound is the main new piece. Prior preferential BO work mostly lacked this kind of finite-time guarantee for TS, so the extension is useful on its own terms. The experiments at least show the method runs without obvious collapse. The modeling choice is standard, but the bounds only hold if the link and kernel actually describe the feedback process. The paper does not test robustness when that assumption slips, which is a real limitation in human-in-the-loop settings where preferences can be noisy or inconsistent. The double-TS step also adds queries per iteration; without reported overhead numbers it is hard to judge the practical cost. This is for people already working on Bayesian optimization with ranking or preference feedback, especially in design or discovery loops. A reader who needs a theoretical handle on TS in the preferential setting will get something concrete from it. It deserves a serious referee because the claim is specific, the reduction looks direct, and the gap it fills is clear. I would send it to peer review.

Referee Report

1 major / 2 minor

Summary. The manuscript proposes a Thompson Sampling (TS) algorithm for Bayesian optimization (BO) with preferential feedback, where observations are pairwise comparisons rather than scalar values. Comparisons are modeled via a monotone link function applied to latent utility differences, inducing a dueling kernel from a base kernel. The central contribution is a finite-time analysis showing that the regret performance of this preferential TS matches that of standard TS for conventional scalar-feedback BO. The analysis relies on the anchor invariance property of TS for challenger selection and introduces a double-TS pairing variant. Synthetic and real-world empirical results are also presented.

Significance. If the finite-time analysis holds under the stated modeling assumptions, the result is significant: it extends existing TS regret bounds to the preferential setting without performance degradation, which is relevant for human-in-the-loop and expert-feedback applications. The matching performance via anchor invariance is a strong theoretical feature. The paper does not mention machine-checked proofs or open reproducible code, but the explicit finite-time claim and empirical validation provide a clear basis for further work.

major comments (1)

[§4 (finite-time analysis)] The finite-time analysis (presumably Theorem 1 or equivalent in §4) claims matching performance to scalar TS; however, the weakest assumption noted is that the dueling kernel induced by the base kernel supports the same concentration and regret arguments. Please provide the precise statement of the regret bound and confirm that no additional factors arise from the link function or the double-TS pairing.

minor comments (2)

[§3] Clarify the definition and implementation of the 'double-TS pairing variant' early in the algorithm section, as it is central to the analysis but only mentioned in the abstract.
[§2] The abstract states that comparisons are modeled with a 'monotone link on latent utility differences'; ensure the exact form of the link (e.g., logistic or probit) and any required regularity conditions are stated explicitly before the analysis.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation for minor revision. We address the major comment below.

read point-by-point responses

Referee: [§4 (finite-time analysis)] The finite-time analysis (presumably Theorem 1 or equivalent in §4) claims matching performance to scalar TS; however, the weakest assumption noted is that the dueling kernel induced by the base kernel supports the same concentration and regret arguments. Please provide the precise statement of the regret bound and confirm that no additional factors arise from the link function or the double-TS pairing.

Authors: Theorem 1 in §4 states that the expected cumulative regret of the proposed preferential TS is upper-bounded by exactly the same expression as the standard scalar-feedback TS regret bound from the referenced prior work on TS for BO, with no multiplicative or additive factors. The proof relies on the anchor invariance property of TS, which ensures the challenger is drawn from the identical posterior distribution as in the scalar case, independent of the fixed anchor. The double-TS pairing is used solely to generate valid preferential observations while preserving the information gain and posterior concentration; it introduces no extra regret because each pair is drawn from the same posterior. The monotone link function induces a dueling kernel that inherits the sub-Gaussian tail bounds and RKHS norm properties of the base kernel (formalized in Lemma 2 of §3), so the concentration and regret arguments apply verbatim. We will revise the manuscript to restate the bound explicitly in the theorem and add a short remark confirming the absence of extra factors from the link function or pairing. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central finite-time analysis claims performance equivalence to standard scalar-feedback TS by exploiting the anchor invariance property of TS (a stated algorithmic feature) and a double-TS pairing variant. This relies on the modeling choice of a monotone link function on latent utilities and the induced dueling kernel from a base kernel, which are standard extensions rather than self-referential. No load-bearing step reduces by construction to a fitted parameter renamed as prediction, a self-citation chain, or an ansatz smuggled via prior work by the same authors. The derivation is self-contained with independent content from the regret analysis techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the latent utility model with monotone link and the dueling kernel construction. No free parameters or invented entities are explicitly introduced in the abstract beyond standard kernel and link assumptions.

axioms (1)

domain assumption Preference comparisons can be modeled using a monotone link function on latent utility differences.
Stated directly in the abstract as the modeling approach for comparisons.

pith-pipeline@v0.9.0 · 5423 in / 1118 out tokens · 56737 ms · 2026-05-07T17:41:26.805087+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

[Yes] This has been outlined in detail in Sec- tions 2 and 3

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes] This has been outlined in detail in Sec- tions 2 and 3. (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] One main focus of this paper is the ana...

work page
[2]

[Yes] Assumptions have been clearly stated in Section 2 and for Theorem statements in Section 4

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] Assumptions have been clearly stated in Section 2 and for Theorem statements in Section 4. Any miss- ing details are readily available in the ap- pendix. (b) Complete proofs of all theoretical results. [Yes] Complete proofs can ...

work page
[3]

[Yes] Code and directions can be found in the supplementary material

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (ei- ther in the supplemental material or as a URL). [Yes] Code and directions can be found in the supplementary material. (b) All the training details (e.g., data splits, hy- perparameters...

work page
[4]

[Yes] (b) The license information of the assets, if ap- plicable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses ex- isting assets. [Yes] (b) The license information of the assets, if ap- plicable. [Not Applicable] (c) New assets either in the supplemental mate- rial or as a URL, if applicable. [Not Applic...

work page
[5]

[Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Appli- cable] (c) The estimated hourly wage paid...

work page
[6]

well-understood

For eachx∈ X, therepresenter functionk(·, x) belongs toH k. 2.Reproducing property:For allf∈ H k and allx∈ X, f(x) =⟨f, k(·, x)⟩ Hk . Intuitively,H k is the completion of the linear span of{k(·, x) :x∈ X }with respect to the inner product induced byk. The RKHS norm∥f∥ Hk measures the smoothness offrelative to the kernelk, and plays a central role in the t...

work page 2017

[1] [1]

[Yes] This has been outlined in detail in Sec- tions 2 and 3

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes] This has been outlined in detail in Sec- tions 2 and 3. (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] One main focus of this paper is the ana...

work page

[2] [2]

[Yes] Assumptions have been clearly stated in Section 2 and for Theorem statements in Section 4

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] Assumptions have been clearly stated in Section 2 and for Theorem statements in Section 4. Any miss- ing details are readily available in the ap- pendix. (b) Complete proofs of all theoretical results. [Yes] Complete proofs can ...

work page

[3] [3]

[Yes] Code and directions can be found in the supplementary material

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (ei- ther in the supplemental material or as a URL). [Yes] Code and directions can be found in the supplementary material. (b) All the training details (e.g., data splits, hy- perparameters...

work page

[4] [4]

[Yes] (b) The license information of the assets, if ap- plicable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses ex- isting assets. [Yes] (b) The license information of the assets, if ap- plicable. [Not Applicable] (c) New assets either in the supplemental mate- rial or as a URL, if applicable. [Not Applic...

work page

[5] [5]

[Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Appli- cable] (c) The estimated hourly wage paid...

work page

[6] [6]

well-understood

For eachx∈ X, therepresenter functionk(·, x) belongs toH k. 2.Reproducing property:For allf∈ H k and allx∈ X, f(x) =⟨f, k(·, x)⟩ Hk . Intuitively,H k is the completion of the linear span of{k(·, x) :x∈ X }with respect to the inner product induced byk. The RKHS norm∥f∥ Hk measures the smoothness offrelative to the kernelk, and plays a central role in the t...

work page 2017