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

Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson Sampling Stochastic Multi-Armed Bandits
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
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Regret
Department of Electrical Engineering, Stanford University, California, United States.
MINTS: Minimalist Thompson Sampling
Jun 1, 2026Kaizheng WangThompson Sampling Bayesian
Department of IEOR and Data Science Institute, Columbia University.

May 10, 2026, cs.LGJ/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

MINTS: Minimalist Thompson Sampling