Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits

Vikram Kakaria; Anish Kataria; Anany Kotawala

cs.LGOct 5, 2026

Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits

Authors: Vikram Kakaria, Anish Kataria, Anany Kotawala

Organizations: Princeton University

Abstract

Combinatorial Thompson sampling (CTS) draws independent posterior samples for every arm, so its exploration dynamics ignore any relation among arms. We study a minimal change to those dynamics: an LLM is queried once for a partition of the arms, the partition becomes a positive-definite correlation matrix $Σ$ through an RBF kernel on cluster ranks, and the per-round posterior sample is drawn with covariance $Σ$ while the Beta posteriors are updated from real rewards only, so the LLM shapes how the sampler moves, not what it believes. We give a self-contained Bayesian regret bound for the idealized Gaussian sampler whose information gain splits into a $K\log T$ term from the $K$ -cluster structure and a ridge term that grows to $d\log T$ : the $\sqrt{d/K}$ improvement over independent sampling is a finite-horizon transient, exact only as the within-cluster correlation tends to one. The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families at $T=2{,}500$ (6-7% at $T=25{,}000$ with data-adaptive kernels) and by 41% on the Microsoft MIND-small news benchmark ( $d=200$ real articles), while pseudo-observation warm starts give nothing. An LLM-free ablation with a simulated oracle of controlled quality shows that on unstructured instances the gain is a property of the kernel shape (a random partition, or a plain tempering of the sampling noise, reproduces it), while belief injection at matched oracle quality never helps.

Figures & tables

Exp.	Algorithm	Regret	vs CTS	W/L	$p$
E1 ( $n{=}320$ )	CorrCTS-Full	268.2	$+18.9\%$	262/58	${<}10^{-4}$
	Rec.-mixing (belief)	279.5	$+15.5\%$	143/97	$0.0036$
	RobustCorrCTS	284.2	$+14.1\%$	237/83	${<}10^{-4}$
	RandomCorr (block, random partition)	307.2	$+7.1\%$	227/93	${<}10^{-4}$
E3 ( $n{=}135$ )	CorrCTS-Full	927.5	$+41.1\%$	134/1	${<}10^{-6}$
	CorrCTS-KM	928.6	$+41.0\%$	134/1	${<}10^{-6}$

Table 1: LLM experiments E1 and E3: paired regret reduction vs CTS (CTS mean regret 330.7 on E1, 1573.7 on E3), paired wins/losses, and Holm-corrected

p

(sign test for E1, Wilcoxon for E3).

Panel of Figure 1 — Figure 1: E1 cumulative regret on the uniform-small family at $d{=}25$ (left) and $d{=}50$ (right), $m{=}5$ (20 seeds; bands: one standard error; purple: a gated block-diagonal pilot variant). The correlated samplers separate from CTS just after the query at $T_{w}{=}30$ and the gap widens with $d$ ; recommendation mixing competes only at $d{=}25$ .

Panel of Figure 2 — Figure 2: LLM-free ablation. (a) Paired regret reduction versus CTS against oracle label noise $\varepsilon$ (dashed: partition-free references; error bars: one standard error over 320 paired trials). (b) The same against the horizon (16 configurations, 10 seeds).

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Sampler	$(25,3)$	$(25,5)$	$(50,3)$	$(50,5)$
CTS	256.7	284.4	442.2	492.6
RBF kernel, random partition/order	221.4	257.2	363.9	429.8
CorrCTS-Full ( $\varepsilon{=}0$ )	225.0	247.3	364.7	434.3
CorrCTS-Full ( $\varepsilon{=}0.5$ )	223.4	233.8	338.9	413.4
CorrCTS-Full ( $\varepsilon{=}1$ )	221.7	240.5	353.2	427.3
GP-CTS( $\Sigma$ ) ( $\varepsilon{=}0$ )	250.6	257.2	421.5	488.4

Appendix

Table 2: Per-

(d,m)

mean regret in the LLM-free ablation (

T{=}2{,}500

; 4 gap families

\times

20 seeds

=80

trials per cell).

Algorithm	Source	Overall	$(25,3)$	$(25,5)$	$(50,3)$	$(50,5)$
CTS	reported	330.7	224.5	223.8	415.7	458.8
	re-run	369.0	256.7	284.4	442.2	492.6
CUCB	reported	776.3	546.4	560.6	933.2	1065.2
	re-run	735.8	539.0	583.4	800.2	1020.7
RandomCorr (block, $\rho{=}0.6$ )	reported	307.2	210.9	216.7	386.8	414.4
	re-run	351.2	253.2	261.4	407.8	482.4

Appendix

Table 3: Re-implementation check of the LLM-free rows of Experiment 1 (16 configurations

\times

20 seeds,

T{=}2{,}500

). “Reported” are the numbers from the LLM experiment harness; “re-run” are from an independent re-implementation of the same instance family and algorithms. Cells are mean cumulative regret; the four right-hand columns are the per-

(d,m)

means.

Sampler	Partition	Cluster order	Regret	vs CTS	W/L ( $p$ )
CTS	—	—	369.0 $\pm$ 6.6	—	—
Block-diagonal (RandomCorr)	random	none	351.2 $\pm$ 6.7	+4.8%	202/118 ( ${<}10^{-4}$ )
RBF kernel	random	random	318.1 $\pm$ 6.6	+13.8%	239/81 ( ${<}10^{-4}$ )
RBF kernel	random	by $\hat{\mu}$	309.9 $\pm$ 6.4	+16.0%	248/72 ( ${<}10^{-4}$ )
RBF kernel	oracle, $\varepsilon{=}1$	by $\hat{\mu}$	310.7 $\pm$ 6.6	+15.8%	250/70 ( ${<}10^{-4}$ )
RBF kernel	oracle, $\varepsilon{=}0.5$	by $\hat{\mu}$	302.4 $\pm$ 6.2	+18.0%	252/68 ( ${<}10^{-4}$ )

Appendix

Table 4: Kernel-shape versus partition-information ablation (LLM-free;

n{=}320

paired trials per row,

T{=}2{,}500

). All RBF rows use the CorrCTS-Full kernel with identical

(\rho_{\max},\ell,K)=(0.7,0.5,8)

and differ only in what the partition and cluster order contain. “vs CTS” is the paired mean regret reduction; W/L are paired wins/losses;

p

is a two-sided Wilcoxon signed-rank test.

Sampler	$T{=}2.5$ k	$5$ k	$10$ k	$20$ k	$25$ k	W/L
RBF kernel, random partition/order	+15.1%	+14.2%	+10.1%	+4.3%	+3.1%	114/46
CorrCTS-Full ( $\varepsilon{=}0$ )	+14.9%	+12.6%	+9.0%	+5.0%	+3.1%	113/47
CorrCTS-Full ( $\varepsilon{=}0.5$ )	+19.6%	+18.8%	+15.5%	+11.1%	+9.6%	122/38
GP-CTS( $\Sigma$ ) ( $\varepsilon{=}0$ )	+2.2%	+0.5%	-1.9%	-4.0%	-4.6%	65/94
RobustCorrCTS ( $\varepsilon{=}0$ )	+10.8%	+5.1%	-1.6%	-5.8%	-6.6%	82/78
Tempered CTS-Gaussian ( $c{=}0.6$ )	+29.1%	+25.8%	+19.2%	+6.6%	+1.3%	112/48

Appendix

Table 5: Horizon dependence (LLM-free; 16 configurations

\times

10 seeds,

T{=}25{,}000

). Paired regret reduction versus CTS at intermediate horizons, read off the cumulative-regret curves of the same runs; the last column is the final W/L.

$\varepsilon$	NMI	CorrCTS-Full	GP-CTS( $\Sigma$ )	RobustCorrCTS	Warm-start (belief)	Rec.-mixing (belief)
0.00	0.218	+13.9% [239/81]	+3.9% [189/131]	+10.1% [216/104]	-0.6% [155/165]	+5.8% [210/110]
0.25	0.172	+15.3% [249/71]	+2.0% [175/145]	+12.1% [224/96]	-2.2% [143/177]	-0.1% [171/149]
0.50	0.139	+18.0% [252/68]	+1.7% [179/141]	+11.9% [231/89]	-0.8% [153/167]	-2.7% [143/177]
0.75	0.104	+16.6% [257/63]	-0.0% [152/168]	+12.4% [223/96]	-0.3% [158/162]	-8.6% [105/215]
1.00	0.097	+15.8% [250/70]	+1.8% [171/149]	+11.3% [231/89]	-0.6% [160/160]	-10.5% [88/232]

Appendix

Table 6: Structure versus belief injection at matched oracle quality (LLM-free;

n{=}320

paired trials per cell,

T{=}2{,}500

). Every column receives the same simulated partition;

\varepsilon

is the fraction of arms whose cluster label is replaced by a uniformly random one (

\varepsilon{=}0

: quality-sorted partition;

\varepsilon{=}1

: random). NMI is against the top-

m

/rest partition (for reference, GPT-5.4 clusters in Experiment 1 had NMI

0.155

; random

0.10

). Cells are paired regret reduction versus CTS (positive is better); W/L in brackets.

E1	$(25,3)$	$(25,5)$	$(50,3)$	$(50,5)$
CorrCTS-Full	192.0	195.1	312.5	373.3
RobustCorrCTS	191.3	198.6	351.0	395.8
Rec.-mixing	214.1	219.8	393.3	543.8
RandomCorr	210.9	216.7	386.8	414.4
CTS	224.5	223.8	415.7	458.8
CUCB	546.4	560.6	933.2	1065.2

Appendix

Table 7: E1 mean regret by

(d,m)

(80 trials per cell) and E3 regret reduction by user profile (

n{=}45

per cell).

Figure 3: The correlation matrix $\Sigma$ of Equation 1 ( $\rho_{\max}{=}0.7$ , $\ell{=}0.5$ , $K{=}8$ ) on a $d{=}50$ staggered instance, arms sorted by true mean, for a quality-sorted partition, a noisy one ( $\varepsilon{=}0.5$ ), a random one, and the adversarial construction. Every matrix has unit diagonal and $\lambda_{\min}\geq 1-\rho_{\max}$ ; only the placement of the off-diagonal mass changes, which is what Section 4.2 shows matters little on unstructured instances.

Figure 4: Numerical check of Lemma 3 : exact information gain

\gamma_{T}

of the kernel of Figure 3 under a uniform allocation (

\tau^{2}{=}\nicefrac{{1}}{{12}}

\sigma^{2}{=}\nicefrac{{1}}{{4}}

m{=}5

) against the two-term upper bound, the lower bound, and the independent-prior value. At

\rho_{\max}{=}0.7

the curves merge with the independent case within a few hundred rounds; at

\rho_{\max}{=}0.97

the structural regime is visibly longer, as Proposition 9 predicts.

Figure 5: Left: Lemma 5 numerically. Probability that all

m

equicorrelated standard Gaussian samples exceed the

q{=}0.3

upper quantile, as a function of the correlation

\rho

(

2\times 10^{5}

Monte Carlo draws); dotted lines are the independent values

q^{m}

, the dashed line the limit

q

. Right: credibility

w_{t}

of RobustCorrCTS on the

d{=}50,m{=}5

hard-gap family (10 seeds; band is the min–max range) for a quality-sorted partition, a random one, and the adversarial construction with the merged cluster ranked first. The decay is geometric at the checks every

\Delta_{\mathrm{check}}{=}100

rounds as in Proposition 7 , but the overlap statistic compares the oracle’s best cluster with the top-

m

of the raw empirical means, which rarely pulled arms with

\hat{\mu}_{i}\approx 1

enter; the gate therefore also decays under a good partition (the cost visible in Tables 4 and 6 ), and it does not fire when the merged adversarial cluster contains the true top-

m

. A lower-confidence-bound statistic would remove both effects.

Figure 6: LLM-free cumulative regret on the uniform-small family (20 seeds; bands are one standard error) for the independent re-implementation of Section 4.2 : the RBF kernel on a random partition and CorrCTS-Full on the quality-sorted partition are nearly indistinguishable, the tempered sampler is lowest at this horizon, and the exact Bayesian

\textsc{GP-CTS}(\Sigma)

tracks CTS.

Figure 7: Per-

(d,m)

paired regret reduction versus CTS at

T{=}2{,}500

for the samplers of Section 4.2 (80 trials per cell). The ordering is the same in every cell: tempering and the RBF samplers (whatever the partition) gain the most, the exact Bayesian sampler and the belief-injection baselines gain little or nothing.

Figure 8: Tempering sweep. Paired regret reduction of independent CTS-Gaussian with posterior standard deviation scaled by

c

(

n{=}320

;

c{=}1

is CTS-Gaussian), with the two RBF samplers as dashed references and the value

c=\sqrt{1-\rho_{\max}}

of Lemma 6 (ii) marked.

Figure 9: E1 cumulative regret (LLM partitions) on the uniform-small family at

d{=}50

m{=}3

(20 seeds; bands are one standard error), complementing Figure 1 .

Explore similar work

May 10, 2026cs.LG

Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

We revisit combinatorial Thompson sampling (CTS) for semi-bandits with sleeping arms, where arm availability varies over time and actions must satisfy combinatorial constraints, as in wireless mesh routing with fluctuating link availability. Despite its practical relevance, CTS has been hindered by several long-standing problems: (i) the absence of worst-case regret guarantees in the semi-bandit setting even without sleeping arms, (ii) the lack of theory under adversarially varying availability, and (iii) the consistently weak empirical performance of CTS with Gaussian priors (CTS-G). This paper resolves these long-standing issues by providing the first worst-case regret analysis of CTS-G, proving an upper bound of

\tilde{O}(m\sqrt{NT})

and a matching lower bound of

\tildeΩ(m\sqrt{NT})

. To bridge the gap between theory and practice, we further propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. We show that CL-SG achieves an improved regret bound of

\tilde{O}(\sqrt{mNT})

, together with a matching lower bound

Ω(\sqrt{mNT})

. Experiments on real-world datasets demonstrate that CL-SG consistently outperforms strong baselines including CTS-G and CTS-B, and we open-source our implementation for reproducibility.

Zhiming Huang, Bingshan Hu, Jianping Pan

Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada

Thompson Sampling Stochastic Multi-Armed Bandits Worst-Case

Ask PDF

Jan 5, 2026cs.LG

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits

\tilde{O}(σd \sqrt{T} + d r \sqrt{\mathrm{Tr}(Σ_0)})

Bayesian regret in the linear-Gaussian bandit with a

\mathcal{N}(μ_0, Σ_0)

prior distribution on the coefficients, where

d

is the dimension,

T

is the time horizon,

r

is the maximum

\ell_2

norm of the actions, and

σ^2

is the noise variance. In contrast to existing regret bounds, this shows that to within logarithmic factors, the prior-dependent

burn-in'' term $d r \sqrt{\mathrm{Tr}(Σ_0)}$ decouples additively from the minimax (long run) regret $σd \sqrt{T}$. Previous regret bounds exhibit a multiplicative dependence on these terms. We establish these results via a new

elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.

Yifan Zhu, John C. Duchi, Benjamin Van Roy

Department of Electrical Engineering, Stanford University, California, United States.

Thompson Sampling Regret Prior Knowledge Integration Diffusion Dynamics

Ask PDF

Jun 1, 2026math.OC

MINTS: Minimalist Thompson Sampling

The Bayesian paradigm offers principled tools for sequential decision-making under uncertainty, but its reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints. We introduce a minimalist Bayesian framework that places a prior only on the location of the optimum, while eliminating nuisance parameters through profile likelihood. This yields a generalized posterior that naturally accommodates structural constraints. As a direct instantiation, we develop MINimalist Thompson Sampling (MINTS). For multi-armed bandits with mean constraints, we establish near-optimal non-asymptotic regret guarantees and sharp almost-sure asymptotic regret characterizations. In particular, MINTS attains the classical Lai--Robbins constant in the unstructured setting and automatically adapts to unimodal structure, achieving the sharp constant determined only by the immediate neighbors of the optimal arm.

Kaizheng Wang

Department of IEOR and Data Science Institute, Columbia University.

Thompson Sampling Bayesian

Ask PDF