Paper deep dive
Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
Vikram Kakaria, Anish Kataria, Anany Kotawala
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/7/2026, 9:23:23 AM
Summary
This paper introduces a method for Combinatorial Thompson Sampling (CTS) that incorporates structure via an LLM-derived covariance matrix rather than injecting beliefs into the posterior. By querying an LLM once for an arm partition and converting it into a correlation matrix using an RBF kernel, the sampler induces correlations between arm selections. Theoretical analysis provides a Bayesian regret bound showing a transient improvement of $\sqrt{d/K}$ over independent sampling. Experiments on synthetic data and the Microsoft MIND benchmark demonstrate significant regret reduction (up to 41%) compared to standard CTS, while ablation studies confirm that the gain stems from the kernel's structural effect (tempering) rather than the quality of the LLM's partition or belief injection.
Entities (8)
Relation Signals (7)
Arm Partition → isconvertedto → Correlation Matrix
confidence 95% · the partition becomes a positive-definite correlation matrix Σ through an RBF kernel on cluster ranks
LLM → provides → Arm Partition
confidence 95% · an LLM is queried once for a partition of the arms, the partition becomes a positive-definite correlation matrix Σ
CorrCTS-Full → achievesregretreductionof → 19%
confidence 92% · The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families at T=2,500
CorrCTS-Full → achievesregretreductionof → 41%
confidence 92% · and by 41% on the Microsoft MIND-small news benchmark
Combinatorial Thompson Sampling → isimprovedby → LLM-Derived Covariance
confidence 90% · The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families... and by 41% on the Microsoft MIND-small news benchmark
Belief Injection → isineffectiveorharmful → Bandit Performance
confidence 88% · belief injection at matched oracle quality never helps... pseudo-observation warm starts give nothing
RBF Kernel → induces → Structural Gain
confidence 85% · on unstructured instances the gain is a property of the kernel shape (a random partition... reproduces it)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\Sigma$ through an RBF kernel on cluster ranks, and the per-round posterior sample is drawn with covariance $\Sigma$ 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.
Tags
Links
- Source: https://arxiv.org/abs/2610.07470v1
- Canonical: https://arxiv.org/abs/2610.07470v1
Trouble viewing inline? Open PDF directly →
Full Text
49,924 characters extracted from source content.
Expand or collapse full text
Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits Vikram Kakaria Affiliation: Princeton University Anish Kataria Affiliation: Princeton University Anany Kotawala Affiliation: 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 KlogTK T term from the K-cluster structure and a ridge term that grows to dlogTd T: the d/K 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%19\% over CTS on 16 synthetic Bernoulli families at T=2,500T=2,500 (66–7%7\% at T=25,000T=25,000 with data-adaptive kernels) and by 41%41\% on the Microsoft MIND-small news benchmark (d=200d=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. 1 Introduction Thompson sampling is a stochastic dynamical system: the learner’s state is a posterior, the control is a random draw from it, and the reward feedback closes the loop; this paper is about how the covariance of that draw changes exploration, how the effect decays with the horizon, and how an oracle in the loop couples to the learner’s state. In the combinatorial semi-bandit [5, 9], where m of d arms are played each round and each played arm returns its own Bernoulli reward, Combinatorial Thompson Sampling (CTS) [13] draws the d coordinates of that control independently, so its exploration dynamics carry no information about which arms are alike. Large language models are an obvious source of such information, and most LLM-augmented bandits inject it as a belief: a prior over means [2, 3], pseudo-observations, or a recommendation mixed into the action distribution [4, 8]. Belief injection has a feedback-loop failure mode that we observed directly (Appendix G): the LLM’s answer quality depends on the estimates it is shown, which depend on the learner’s own trajectory, and a wrong belief biases the posterior at a cost of real observations. We instead use the LLM for structure: one cluster query, converted to a correlation matrix Σ , changes only the covariance of the posterior draw, so posterior means and variances stay those of CTS (Proposition 1) and an arbitrarily bad Σ can distort the sampler’s motion but not corrupt its state. Contributions. (i) A statement of what Σ represents (Assumption 2) and a self-contained Bayesian regret bound for GP-CTS(Σ) GP-CTS( ) (Theorem 4) whose d/K d/K advantage is a transient, exact only as ρmax→1 _ → 1. (i) CorrCTS-Full as a fixed-correlation, calibrated-marginal approximation to GP-CTS(Σ) GP-CTS( ), partition-free accounts of why a fixed correlation changes top-m selection (Lemmas 5 and 6; in the equicorrelated case it is exactly a tempering), and a total-variation guarantee for the credibility gate (Proposition 7). (i) LLM experiments on synthetic families and real MIND click data, plus an LLM-free ablation in which every injection mode receives the same simulated partition of controlled quality, separating kernel shape from partition information and structure from belief. 2 Setting and algorithm Combinatorial semi-bandit. There are d arms with unknown means μ∈[0,1]dμ∈[0,1]^d. At round t the learner plays St⊆[d]S_t [d] with |St|=m|S_t|=m and observes Xi,t∼Bernoulli(μi)X_i,t ( _i) for each i∈Sti∈ S_t. With S⋆=argmax∑i∈S|S|=mμiS = _|S|=m _i∈ S _i, the regret is R(T)=∑t≤T(∑i∈S⋆μi−∑i∈Stμi)R(T)= _t≤ T ( _i∈ S _i- _i∈ S_t _i ). CTS [13] keeps Beta(αi,βi)Beta( _i, _i) posteriors, draws θi _i independently, plays the top-m of θ, and updates (αi,βi)( _i, _i) for i∈Sti∈ S_t. At a warmup time TwT_w the learner may send the empirical means μ μ (and, for MIND, article titles) to an oracle that returns a partition =C1,…,CKC=\C_1,…,C_K\ of [d][d] of unknown quality, which may depend on μ μ. From partition to covariance. Clusters are ranked by their mean μ μ at TwT_w (rank 00 is best), each arm receives the normalized rank fi=rk(i)/(K−1)∈[0,1]f_i=r_k(i)/(K-1)∈[0,1] of its cluster, and Σij=ρmaxexp(−(fi−fj)2/(2ℓ2))(i≠j),Σii=1. _ij= _ \! (-(f_i-f_j)^2/(2 ^2) )\ (i≠ j), _i=1. (1) Writing G for the RBF Gram matrix on the features f, Σ=ρmaxG+(1−ρmax)Id⪰(1−ρmax)Id = _ G+(1- _ )I_d (1- _ )I_d is positive definite for any partition, and rank(G)≤Krank(G)≤ K because f takes at most K distinct values; same-cluster arms have correlation ρmax _ and adjacent clusters keep positive correlation. CorrCTS-Full (pseudocode in Appendix B). Rounds t≤Twt≤ T_w are plain CTS. At TwT_w the partition is turned into Σ and its Cholesky factor L. Afterwards each round takes the Beta posterior mean and standard deviation (μ¯i,σi)( μ_i, _i) of every arm, draws ϵ∼(0,Id)ε (0,I_d) and plays the top-m of θ=μ¯+σ⊙(Lϵ)θ= μ+σ (Lε); the marginal of θi _i is the moment-matched Gaussian (μ¯i,σi2)N( μ_i, _i^2), and only the joint law changes. RobustCorrCTS adds a credibility weight w∈[0,1]w∈[0,1] (w=1w=1 initially), updated every Δcheck _check rounds as w←0.7w+0.3overlaptw← 0.7w+0.3\,overlap_t (overlaptoverlap_t: fraction of the empirical top-m in the oracle’s best cluster), and plays the top-m of wθcorr+(1−w)θindwθ^corr+(1-w)θ^ind (independent draws). CorrCTS-Prune and CorrCTS-KM refresh Σ from data at long horizons without new queries (Appendix D). Proposition 1 (Posterior integrity). For every reward sequence, the Beta parameters (αi,βi)( _i, _i) of every arm coincide under CorrCTS-Full, RobustCorrCTS and CTS; Σ enters only the sampling step, and Σ=Id =I_d gives CTS with moment-matched Gaussian marginals (“CTS-Gaussian”). 3 What a fixed correlation does to the sampling dynamics 3.1 What Σ stands for Assumption 2 (Structural prior). μ∼(μ0,τ2Σ)μ ( _01,τ^2 ) and, for i∈Sti∈ S_t, the observation is yi,t=μi+ηi,ty_i,t= _i+ _i,t with ηi,t∼(0,σ2) _i,t (0,σ^2) independent. Thus Σ is the prior correlation of the means and the oracle supplies an estimate of it; when the estimate is wrong the bound below does not apply, the situation Lemmas 5 and 6, the credibility gate and Section 4.2 address. GP-CTS(Σ) GP-CTS( ) denotes Thompson sampling under this model: θt∼(μt,Σt) _t ( _t, _t) from the exact Gaussian posterior, then top-m. 3.2 Bayesian regret of GP-CTS(Σ) GP-CTS( ) Let DT=diag(n1,…,nd)D_T=diag(n_1,…,n_d) count pulls after T rounds (∑ini=mT _in_i=mT) and let γT=12logdet(Id+σ−2τ2Σ1/2DTΣ1/2) _T= 12 (I_d+σ^-2τ^2\, ^1/2D_T ^1/2 ) be the information gain of the play sequence. Lemma 3 (Two-term information gain). For Σ=ρG+(1−ρ)Id =ρ G+(1-ρ)I_d with G⪰0G 0, Gii=1G_i=1, rank(G)≤Krank(G)≤ K, and N=mTN=mT, γT≤K2log(1+ρτ2NKσ2)+12min(1−ρ)τ2Nσ2,dlog(1+(1−ρ)τ2Ndσ2). _T\ ≤\ K2 (1+ ρτ^2NKσ^2 )+ 12 \ (1-ρ)τ^2Nσ^2,\ d (1+ (1-ρ)τ^2Ndσ^2 ) \. For any correlation matrix (e.g. Σ=Id =I_d), γT≤d2log(1+τ2N/(dσ2)) _T≤ d2 (1+τ^2N/(dσ^2)); conversely, if every arm has been pulled at least n times, γT≥d2log(1+(1−ρ)τ2n/σ2) _T≥ d2 (1+(1-ρ)τ^2n/σ^2), so the ridge term is not an artifact of the upper bound. Theorem 4 (Bayesian regret of GP-CTS(Σ) GP-CTS( )). Under Assumption 2, with c=mτ2/σ2c=mτ^2/σ^2, Cc=c/log(1+c)C_c=c/ (1+c) and βT=2log((dm)T2)≤2mlogd+4logT _T=2 ( dmT^2 )≤ 2m d+4 T, [R(T)]≤2Ccmσ2βTTγT+mτT,E[R(T)]\ ≤\ 2\,C_c\,m\,σ^2\, _T\,T\, _T\;+\; mτT, with γT _T bounded as in Lemma 3; the proof (Appendix A) follows Russo and Van Roy [11] with an elliptical-potential step. Reading the bound. With βT=O(mlog(dT)) _T=O(m (dT)) and the lemma, [R(T)]=O(CcmTlog(dT)[KlogT+min(1−ρ)τ2mT/σ2,dlogT]).E[R(T)]=O ( C_c\,m T (dT)\, [K T+ \(1-ρ)τ^2mT/σ^2,\ d T\ ] ). Because Σ has full rank d whenever ρ<1ρ<1, the bound never depends on K alone: the ridge term vanishes only as ρ→1ρ→ 1, where the rate becomes O~(mKT) O(m KT), a d/K d/K improvement over the O~(mdT) O(m dT) that the same argument gives for Σ=Id =I_d; for fixed ρ<1ρ<1 the two rates coincide once (1−ρ)τ2mT/σ2≳KlogT(1-ρ)τ^2mT/σ^2 K T. At the experimental values (d=50,m=5,ρ=0.7,τ2=1/12,σ2=1/4d=50,m=5,ρ=0.7,τ^2= 112,σ^2= 14) the crossover is below 150150 rounds (Proposition 9), so a proper Bayesian sampler should gain little at T=2,500T=2,500, as Section 4.2 confirms. 3.3 CorrCTS-Full versus GP-CTS(Σ) GP-CTS( ) CorrCTS-Full is not GP-CTS(Σ) GP-CTS( ): its marginals are the exact Beta moments, but its correlation stays fixed at Σ whereas the Gaussian posterior correlation shrinks as data accumulate; a fixed positive correlation changes top-m selection in two specific ways. Lemma 5 (Marginals kept, joint exceedance raised). Let θ∼(μ¯,diag(σ)Σdiag(σ))θ ( μ,diag(σ) \,diag(σ)) for a correlation matrix Σ with Σij≥0 _ij≥ 0 for all i,ji,j (every kernel of Equation 1, for any partition). Then each θi∼(μ¯i,σi2) _i ( μ_i, _i^2) exactly as under Σ=Id =I_d, and for every A⊆[d]A [d] and threshold vector c, ℙΣ(θi>ci∀i∈A)≥∏i∈Aℙ(θi>ci)P_ ( _i>c_i\ ∀ i∈ A)≥ _i∈ AP( _i>c_i), with the left side nondecreasing in each off-diagonal entry of Σ . This is Slepian’s inequality [12] and holds for any partition: per-arm concentration is untouched, while the joint optimism event, which independent sampling grants m near-optimal arms only with probability decaying like qmq^m, can only become more likely; correlation also shrinks the noise in the pairwise comparisons that top-m selection is made of, and in the equicorrelated case this is exactly a tempering. Lemma 6 (Comparison noise and tempering). Let θ∼(μ¯,diag(σ)Σdiag(σ))θ ( μ,diag(σ) \,diag(σ)). (i) Var(θi−θj)=σi2+σj2−2ΣijσiσjVar( _i- _j)= _i^2+ _j^2-2 _ij _i _j, which for σi=σj _i= _j equals the independent-sampling value times 1−Σij1- _ij. (i) If Σ=ρ⊤+(1−ρ)Id = 11 +(1-ρ)I_d and σi≡σ _i≡σ, then top-m(θ)top-m(θ) has exactly the law of top-m(μ¯+1−ρσϵ)top-m( μ+ 1-ρ\,σε) with ϵ∼(0,Id)ε (0,I_d), i.e. of independent sampling tempered by c=1−ρc= 1-ρ. With ρmax=0.7 _ =0.7, 1−ρmax≈0.55 1- _ ≈ 0.55, and Section 4.2 finds the best tempering factor near c=0.6c=0.6; CorrCTS-Full, whose σi _i differ across arms, is a heteroscedastic, kernel-shaped relaxation of (i). 3.4 The credibility gate Proposition 7 (Gate convergence in total variation). Given a common posterior, the per-round sampling distributions of RobustCorrCTS (correlation Σw=w2Σ+(1−w)2Id _w=w^2 +(1-w)^2I_d at credibility w) and CTS-Gaussian satisfy dTV≤32wt(ρmaxd+2d)d_TV≤ 32\,w_t\,( _ d+2 d). If the overlap statistic is 00 at every check after TwT_w, then ∑t>Twwt≤103Δcheck _t>T_ww_t≤ 103 _check and ∑t>TwdTV≤5(ρmaxd+2d)Δcheck _t>T_wd_TV≤ 5( _ d+2 d) _check for every T. We claim no regret inequality (that would need a coupling of trajectories sharing a posterior only until their first disagreement): the guarantee is that under sustained disagreement the gate returns to CTS-Gaussian within O(Δcheck)O( _check) rounds. Corralling with CTS [1] is the principled alternative (Appendix C). 4 Experiments 4.1 LLM experiments All comparisons are paired (same instance, same seed) with Holm–Bonferroni correction [7]; ρmax=0.7,ℓ=0.5,K=8,Tw=30 _ =0.7,\ =0.5,\ K=8,\ T_w=30 were chosen on a disjoint validation grid (Appendix E). Table 1 summarizes three experiments with an LLM partition (GPT-5.4 for E1–E2, Claude Sonnet 4.6 for E3; breakdowns in Appendix G). E1 (synthetic Bernoulli, T=2,500T=2,500): d∈25,50d∈\25,50\, m∈3,5m∈\3,5\, four gap families, 20 seeds (n=320n=320); gains grow with d (1212–15%15\% at d=25d=25, 1919–25%25\% at d=50d=50) and recommendation mixing collapses at d=50,m=5d=50,m=5 (Figure 1). E2 (T=25,000T=25,000; the 16 E1 families plus 16 held-out ones, 15 seeds, n=480n=480; Appendix G): CTS 615.9, static CorrCTS-Full 587.9 (+4.5%+4.5\%), CorrCTS-Prune 578.5 (+6.1%+6.1\%), CorrCTS-KM 573.8 (+6.8%+6.8\%), all p<10−4p<10^-4; the static advantage decays and the adaptive variants overtake it, as Theorem 4 predicts. E3 (MIND-small [14], d=200d=200 articles with empirical CTRs, m=5m=5, T=10,000T=10,000, three user profiles × three article samples, 15 seeds, n=135n=135): the reduction is stable across profiles (4040–42%42\%) while warm start is flooded by real data. Under adversarial clusters (true top-m grouped with the m worst arms, ranked first) CorrCTS-Full loses 16.5%16.5\% to CTS on E1 while RobustCorrCTS loses 1.8%1.8\%. 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). Exp. Algorithm Regret vs CTS W/L p E1 (n=320n=320) CorrCTS-Full 268.2 +18.9%+18.9\% 262/58 <10−4<10^-4 Rec.-mixing (belief) 279.5 +15.5%+15.5\% 143/97 0.00360.0036 RobustCorrCTS 284.2 +14.1%+14.1\% 237/83 <10−4<10^-4 RandomCorr (block, random partition) 307.2 +7.1%+7.1\% 227/93 <10−4<10^-4 E3 (n=135n=135) CorrCTS-Full 927.5 +41.1%+41.1\% 134/1 <10−6<10^-6 CorrCTS-KM 928.6 +41.0%+41.0\% 134/1 <10−6<10^-6 CorrCTS-Prune 943.7 +40.0%+40.0\% 133/2 <10−6<10^-6 Warm-start CTS (belief) 1591.4 −1.1%-1.1\% 53/82 0.0140.014 CorrCTS-Full RobustCorrCTS Rec.-mixing RandomCorr block-diagonal CTS CUCB Figure 1: E1 cumulative regret on the uniform-small family at d=25d=25 (left) and d=50d=50 (right), m=5m=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 Tw=30T_w=30 and the gap widens with d; recommendation mixing competes only at d=25d=25. 4.2 Controlled ablation with a simulated oracle The RandomCorr row of Table 1 changes the partition and the kernel, so it cannot attribute the gain to partition quality; we therefore re-implemented the E1 family and all LLM-free samplers (Table 3) and replaced the LLM by a simulated oracle: the quality-sorted partition into K=8K=8 groups with each label replaced by a random one with probability ε . All modes receive the same partition; the belief baselines inject its best-ranked cluster’s m best-μ μ arms as 55 pseudo-successes (warm start) or by recommendation mixing (Figure 2; Appendix F). CorrCTS-Full CorrCTS-Full, ε=0.5 =0.5 RobustCorrCTS GP-CTS(Σ) GP-CTS( ) warm start rec.-mixing RBF, random partition tempered, c=0.6c=0.6 Figure 2: LLM-free ablation. (a) Paired regret reduction versus CTS against oracle label noise ε (dashed: partition-free references; error bars: one standard error over 320 paired trials). (b) The same against the horizon (16 configurations, 10 seeds). Kernel shape versus partition information (Table 4). A random partition in random order through the RBF kernel already gives +13.8%+13.8\% over CTS, the quality-sorted partition +13.9%+13.9\%, and an adversarial partition that groups the true top-m with the m worst arms (keeping the μ μ rank order) +14.2%+14.2\%: on these unstructured instances the gain is a property of the kernel shape, not of the partition. Structure versus belief at matched oracle quality (Figure 2a, Table 6). Across ε∈[0,1] ∈[0,1] the structure samplers stay between +14%+14\% and +18%+18\%, warm start never differs from CTS, recommendation mixing falls from +5.8%+5.8\% to −10.5%-10.5\% as ε goes from 00 to 11, and the exact Bayesian GP-CTS(Σ) GP-CTS( ) gains at most +3.9%+3.9\% (Theorem 4). Tempering and the horizon (Figure 2b, Tables 4 and 5). The tempering reading of Lemma 6 is confirmed by the simplest control: independent CTS-Gaussian with posterior standard deviation scaled by c=0.6c=0.6 reduces regret by +27.1%+27.1\% at T=2,500T=2,500, more than any kernel. All are transient: at T=25,000T=25,000 the RBF samplers retain +3%+3\%, the tempered sampler +1%+1\%, and GP-CTS(Σ) GP-CTS( ) and the gated sampler fall slightly below CTS. 5 Discussion and limitations Moving LLM information from the posterior to the sampling covariance is safe by construction (Proposition 1) and beneficial at moderate horizons; belief injection at matched oracle quality is not. A fixed correlation changes the exploration dynamics (Lemmas 5 and 6) whether or not the partition is right, so a tempered sampler is the LLM-free competitor to beat; partition information buys a proper Bayesian sampler only a transient (Theorem 4) that matters where latent structure exists (E3). Limitations: Theorem 4 concerns GP-CTS(Σ) GP-CTS( ) rather than CorrCTS-Full; misspecification is covered only by Lemmas 5, 6 and 7; E3 uses one dataset and one LLM. References [1] A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire (2017) Corralling a band of bandit algorithms. In Proceedings of the 30th Annual Conference on Learning Theory (COLT), Cited by: Appendix C, §3.4. [2] P. A. Alamdari, Y. Cao, and K. H. Wilson (2024) Jump starting bandits with LLM-generated prior knowledge. arXiv preprint arXiv:2406.19317. Cited by: §1. [3] A. Bayley, K. H. Wilson, Y. Cao, R. Aoki, and X. Zhu (2025) Robustness of LLM-initialized bandits for recommendation under noisy priors. In Workshop on Generative AI for Recommender Systems and Personalization (GenAIRecP), Cited by: §1. [4] D. Bouneffouf and R. F. Ferreira (2025) Survey: multi-armed bandits meet large language models. arXiv preprint arXiv:2505.13355. Cited by: §1. [5] W. Chen, Y. Wang, and Y. Yuan (2013) Combinatorial multi-armed bandit: general framework and applications. In Proceedings of the 30th International Conference on Machine Learning (ICML), Cited by: §1. [6] L. Devroye, A. Mehrabian, and T. Reddad (2018) The total variation distance between high-dimensional Gaussians with the same mean. arXiv preprint arXiv:1810.08693. Cited by: §A.6. [7] S. Holm (1979) A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6 (2), p. 65–70. Cited by: §4.1. [8] A. Krishnamurthy, K. Harris, D. J. Foster, and A. Slivkins (2024) Can large language models explore in-context?. In Advances in Neural Information Processing Systems 37 (NeurIPS), Cited by: §1. [9] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvári (2015) Tight regret bounds for stochastic combinatorial semi-bandits. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: §1. [10] T. Lykouris and S. Vassilvitskii (2018) Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning (ICML), Cited by: Appendix C. [11] D. Russo and B. Van Roy (2014) Learning to optimize via posterior sampling. Mathematics of Operations Research 39 (4), p. 1221–1243. Cited by: §A.2, Theorem 4. [12] D. Slepian (1962) The one-sided barrier problem for Gaussian noise. Bell System Technical Journal 41 (2), p. 463–501. Cited by: §A.3, §3.3. [13] S. Wang and W. Chen (2018) Thompson sampling for combinatorial semi-bandits. In Proceedings of the 35th International Conference on Machine Learning (ICML), Cited by: §1, §2. [14] F. Wu, Y. Qiao, J. Chen, C. Wu, T. Qi, J. Lian, D. Liu, X. Xie, J. Gao, W. Wu, and M. Zhou (2020) MIND: a large-scale dataset for news recommendation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), Cited by: Appendix E, §4.1. Appendix A Proofs A.1 Proof of Lemma 3 Write Σ1=τ2Σ _1=τ^2 and M=σ−2Σ11/2DTΣ11/2M=σ^-2 _1^1/2D_T _1^1/2; then γT=12logdet(I+M) _T= 12 (I+M) and, since det(I+AB)=det(I+BA) (I+AB)= (I+BA), also γT=12logdet(I+σ−2DT1/2Σ1DT1/2) _T= 12 (I+σ^-2D_T^1/2 _1D_T^1/2). Decompose σ−2DT1/2Σ1DT1/2=A+Bσ^-2D_T^1/2 _1D_T^1/2=A+B with A=σ−2τ2ρDT1/2KDT1/2A=σ^-2τ^2ρ\,D_T^1/2KD_T^1/2 and B=σ−2τ2(1−ρ)DTB=σ^-2τ^2(1-ρ)D_T, both positive semidefinite. Step 1: det(I+A+B)≤det(I+A)det(I+B) (I+A+B)≤ (I+A) (I+B). det(I+A+B)=det(I+A)det(I+C) (I+A+B)= (I+A) (I+C) with C=(I+A)−1/2B(I+A)−1/2C=(I+A)^-1/2B(I+A)^-1/2. Since (I+A)−1/2(I+A)^-1/2 is a contraction, λj(C)≤λj(B) _j(C)≤ _j(B) for every j (Courant–Fischer), so det(I+C)≤det(I+B) (I+C)≤ (I+B). Step 2: AM–GM. For a positive semidefinite matrix M of rank at most r, logdet(I+M)=∑j≤rlog(1+λj)≤rlog(1+tr(M)/r) (I+M)= _j≤ r (1+ _j)≤ r (1+tr(M)/r) by concavity of log . A has rank at most rank(K)≤Krank(K)≤ K and tr(A)=σ−2τ2ρ∑iniKii=σ−2τ2ρNtr(A)=σ^-2τ^2ρ _in_iK_i=σ^-2τ^2ρ N; B is diagonal with trace σ−2τ2(1−ρ)Nσ^-2τ^2(1-ρ)N and rank at most d. Combining the two steps gives the first claim (the min uses log(1+x)≤x (1+x)≤ x on the second term); the second claim is Step 2 applied to the full matrix, whose trace is σ−2τ2Nσ^-2τ^2N for any unit-diagonal Σ . For the lower bound, Σ⪰(1−ρ)Id (1-ρ)I_d gives DT1/2Σ1DT1/2⪰τ2(1−ρ)DTD_T^1/2 _1D_T^1/2 τ^2(1-ρ)D_T, and logdet is monotone in the Loewner order, so 2γT≥∑ilog(1+σ−2τ2(1−ρ)ni)≥dlog(1+σ−2τ2(1−ρ)n)2 _T≥ _i (1+σ^-2τ^2(1-ρ)n_i)≥ d (1+σ^-2τ^2(1-ρ)n). ∎ A.2 Proof of Theorem 4 Let =S⊆[d]:|S|=mA=\S [d]:|S|=m\, f(S)=S⊤μf(S)=1_S μ, and let (μt,Σt)( _t, _t) be the Gaussian posterior mean and covariance of μ given the history ℋtH_t before round t (Σ1=τ2Σ _1=τ^2 ). Define the upper index Ut(S)=S⊤μt+βT‖S‖ΣtU_t(S)=1_S _t+ _T\,\|1_S\|_ _t, where ‖x‖Σt2=x⊤Σtx\|x\|_ _t^2=x _tx. Step 1: decomposition. Under Thompson sampling, StS_t and S⋆S have the same conditional law given ℋtH_t, and UtU_t is ℋtH_t-measurable, so [Ut(S⋆)∣ℋt]=[Ut(St)∣ℋt]E[U_t(S ) _t]=E[U_t(S_t) _t] [11, Prop. 1]. Hence [R(T)]=∑t≤T[f(S⋆)−Ut(S⋆)]+∑t≤T[Ut(St)−f(St)].E[R(T)]=E _t≤ T [f(S )-U_t(S ) ]+E _t≤ T [U_t(S_t)-f(S_t) ]. Step 2: the first sum is small. Given ℋtH_t, S⊤(μ−μt)∼(0,‖S‖Σt2)1_S (μ- _t) (0,\|1_S\|_ _t^2). For Z∼(0,s2)Z (0,s^2) and b>0b>0, [(Z−bs)+]=s∫b∞(z−b)ϕ(z)dz≤se−b2/2E[(Z-bs)_+]=s _b^∞(z-b)φ(z)\,dz≤ s\,e^-b^2/2. Therefore [(f(S⋆)−Ut(S⋆))+∣ℋt]≤∑S∈[(S⊤(μ−μt)−βT∥S∥Σt)+∣ℋt]≤||e−βT/2maxS∥S∥ΣtE[(f(S )-U_t(S ))_+ _t]≤ _S E[(1_S (μ- _t)- _T\|1_S\|_ _t)_+ _t]≤|A|\,e^- _T/2 _S\|1_S\|_ _t. Posterior variances never exceed prior variances, so ‖S‖Σt2≤m∑i∈S(Σt)ii≤m2τ2\|1_S\|_ _t^2≤ m _i∈ S( _t)_i≤ m^2τ^2, and with βT=2log(||T2) _T=2 (|A|T^2) the first sum is at most T⋅mτ/T2=mτ/T· mτ/T^2=mτ/T. Step 3: the second sum. StS_t is a function of ℋtH_t and of sampling noise independent of μ, so [St⊤(μt−μ)∣ℋt]=0E[1_S_t ( _t-μ) _t]=0 and the second sum equals βT∑t‖St‖Σt≤βTT∑t‖St‖Σt2 _T\,E _t\|1_S_t\|_ _t≤ _T\,E T _t\|1_S_t\|^2_ _t by Cauchy–Schwarz. Step 4: elliptical potential. Let xt=σ−2∑i∈St(Σt)ii≤mτ2/σ2=cx_t=σ^-2 _i∈ S_t( _t)_i≤ mτ^2/σ^2=c. Because x↦log(1+x)/x (1+x)/x is decreasing, xt≤Cclog(1+xt)x_t≤ C_c (1+x_t) with Cc=c/log(1+c)C_c=c/ (1+c). The precision recursion Σt+1−1=Σt−1+σ−2∑i∈Steiei⊤ _t+1^-1= _t^-1+σ^-2 _i∈ S_te_ie_i gives logdetΣt+1−1−logdetΣt−1=logdet(I+σ−2Σt1/2EStΣt1/2)≥log(1+xt) _t+1^-1- _t^-1= (I+σ^-2 _t^1/2E_S_t _t^1/2)≥ (1+x_t), using det(I+M)≥1+tr(M) (I+M)≥ 1+tr(M) for M⪰0M 0. Telescoping, ∑tlog(1+xt)≤logdet(Σ1ΣT+1−1)=2γT _t (1+x_t)≤ ( _1 _T+1^-1)=2 _T. Finally ‖St‖Σt2≤m∑i∈St(Σt)ii=mσ2xt\|1_S_t\|^2_ _t≤ m _i∈ S_t( _t)_i=mσ^2x_t, so ∑t‖St‖Σt2≤mσ2Cc⋅2γT _t\|1_S_t\|^2_ _t≤ mσ^2C_c· 2 _T. Combining Steps 1–4, [R(T)]≤2Ccmσ2βTTγT+mτ/TE[R(T)]≤ 2C_cmσ^2 _TT _T+mτ/T, where γT _T may be replaced by the deterministic bound of Lemma 3 because that bound depends on the play sequence only through N=mTN=mT. ∎ A.3 Proof of Lemma 5 The marginal claim is immediate since Σii=1 _i=1. Restrict to the coordinates in A and standardize: Zi=(θi−μ¯i)/σiZ_i=( _i- μ_i)/ _i is centered Gaussian with unit variances and correlations Σij _ij. Slepian’s inequality [12] states that for two centered Gaussian vectors with equal variances and Σij(1)≤Σij(2) ^(1)_ij≤ ^(2)_ij for all i≠ji≠ j, ℙ(Zi(1)≤ci∀i)≤ℙ(Zi(2)≤ci∀i)P(Z^(1)_i≤ c_i\ ∀ i) (Z^(2)_i≤ c_i\ ∀ i) for every c; applied to −Z(1),−Z(2)-Z^(1),-Z^(2) (same covariances) it gives the same monotonicity for Zi>ci∀i\Z_i>c_i\ ∀ i\. Taking Σ(1)=I|A| ^(1)=I_|A| and Σ(2)=ΣAA ^(2)= _A, which is admissible because Σij≥0 _ij≥ 0, yields the product lower bound; monotonicity in each entry follows from the same comparison. ∎ A.4 Proof of Lemma 6 (i) is the bilinearity of covariance: Var(θi−θj)=σi2+σj2−2Cov(θi,θj)Var( _i- _j)= _i^2+ _j^2-2\,Cov( _i, _j) and Cov(θi,θj)=σiσjΣijCov( _i, _j)= _i _j _ij; under independence the same expression has Σij=0 _ij=0, and for σi=σj=σ _i= _j=σ the ratio is 2σ2(1−Σij)/(2σ2)2σ^2(1- _ij)/(2σ^2). (i) An equicorrelated vector has the representation θ=μ¯+σ(ρZ+1−ρϵ)θ= μ+σ( ρ\,Z1+ 1-ρ\,ε) with Z∼(0,1)Z (0,1) independent of ϵ∼(0,Id)ε (0,I_d), since Cov(θ)=σ2(ρ⊤+(1−ρ)Id)Cov(θ)=σ^2( 11 +(1-ρ)I_d). The term σρZσ ρ\,Z1 adds the same number to every coordinate and therefore leaves the ordering of the coordinates, hence the top-m set, unchanged almost surely (ties have probability zero). Thus top-m(θ)=top-m(μ¯+1−ρσϵ)top-m(θ)=top-m( μ+ 1-ρ\,σε) pathwise, which is the claim. ∎ A.5 Two consequences of Lemmas 3 and 4 Corollary 8 (Independent prior). For Σ=Id =I_d (CTS-Gaussian under Assumption 2), [R(T)]≤Ccmσ2βTTdlog(1+τ2mT/(dσ2))+mτ/TE[R(T)]≤ C_c\,m\,σ^2\, _T\,T\,d (1+τ^2mT/(dσ^2))+mτ/T. Proof. Insert the second claim of Lemma 3 into Theorem 4. ∎ Proposition 9 (Crossover horizon). Let T⋆=supT:(1−ρ)τ2mT/σ2≤Klog(1+ρτ2mT/(Kσ2))T = \T:\,(1-ρ)τ^2mT/σ^2≤ K (1+ρτ^2mT/(Kσ^2))\. For every T≤T⋆T≤ T , γT≤Klog(1+ρτ2mT/(Kσ2)) _T≤ K (1+ρτ^2mT/(Kσ^2)), so the bound of Theorem 4 reads O(CcmKTlog(dT)logT)O( C_c\,m KT (dT) T), and T⋆≤4ρKσ2(1−ρ)2τ2m.T \ ≤\ 4ρ Kσ^2(1-ρ)^2τ^2m. Proof. For T≤T⋆T≤ T the second term of Lemma 3 is at most 12(1−ρ)τ2mT/σ2≤K2log(1+ρτ2mT/(Kσ2)) 12(1-ρ)τ^2mT/σ^2≤ K2 (1+ρτ^2mT/(Kσ^2)), which gives the first claim. For the second, write x=(1−ρ)τ2mT⋆/σ2x=(1-ρ)τ^2mT /σ^2; the defining inequality is x≤Klog(1+ρ(1−ρ)Kx)x≤ K (1+ ρ(1-ρ)Kx ), and log(1+y)≤2y (1+y)≤ 2 y gives x≤2Kρx/((1−ρ)K)x≤ 2K ρ x/((1-ρ)K), i.e. x≤2ρK/(1−ρ) x≤ 2 ρ K/(1-ρ), i.e. x≤4ρK/(1−ρ)x≤ 4ρ K/(1-ρ); solving for T⋆T gives the bound. At the experimental values (d=50d=50, m=5m=5, K=8K=8, ρ=0.7ρ=0.7, τ2=1/12τ^2= 112, σ2=1/4σ^2= 14) the bound is T⋆≤149T ≤ 149 rounds. ∎ A.6 Proof of Proposition 7 Given a common posterior, the two draws are μ¯+diag(σ)ξ μ+diag(σ)ξ with ξ∼(0,Σw)ξ (0, _w) and ξ∼(0,Id)ξ (0,I_d) respectively; total variation is invariant under the common affine map, so dTV=dTV((0,Σw),(0,Id))≤32‖Σw−Id‖Fd_TV=d_TV(N(0, _w),N(0,I_d))≤ 32\| _w-I_d\|_F by Devroye et al. [6, Thm. 1.1]. Now Σw−Id=w2(Σ−Id)−(2w−w2)Id _w-I_d=w^2( -I_d)-(2w-w^2)I_d, ‖Σ−Id‖F≤ρmaxd(d−1)≤ρmaxd\| -I_d\|_F≤ _ d(d-1)≤ _ d and ‖(2w−w2)Id‖F≤2wd\|(2w-w^2)I_d\|_F≤ 2w d, giving dTV≤32w(ρmaxd+2d)d_TV≤ 32w( _ d+2 d) since w≤1w≤ 1. Under zero overlap at every check, w equals 0.7k0.7^k during the Δcheck _check rounds following the k-th check, so ∑twt≤Δcheck∑k≥00.7k=103Δcheck _tw_t≤ _check _k≥ 00.7^k= 103 _check. ∎ Appendix B Pseudocode Algorithm 1 CorrCTS-Full Input: d,md,m, warmup TwT_w, kernel parameters ρmax,ℓ _ , , number of clusters K αi←1,βi←1 _i← 1,\ _i← 1 for all i; L←IdL← I_d; for t=1,…,Tt=1,…,T do if t≤Twt≤ T_w then θi∼Beta(αi,βi) _i ( _i, _i) independently; else if t=Tw+1t=T_w+1 then ←OracleClusterQuery(μ^,K)C← OracleClusterQuery( μ,K); build Σ from Equation 1; L←Cholesky(Σ+10−3Id)L ( +10^-3I_d); end if θ←μ¯+σ⊙(Lϵ)θ← μ+σ (Lε) with ϵ∼(0,Id)ε (0,I_d); end if play St=top-m(θ)S_t=top-m(θ); observe Xi,tX_i,t; αi←αi+Xi,t _i← _i+X_i,t, βi←βi+1−Xi,t _i← _i+1-X_i,t for i∈Sti∈ S_t; end for Appendix C Alternatives: GP-CTS(Σ) GP-CTS( ) directly, and corralling GP-CTS(Σ) GP-CTS( ) (as run in Section 4.2) uses prior (12,τ2Σ)N( 121,τ^2 ) with τ2=1/12τ^2= 112 (the variance of a Beta(1,1)Beta(1,1) mean) and σ2=1/4σ^2= 14 (the Bernoulli variance bound), a CTS warmup of TwT_w rounds, and thereafter the exact Gaussian posterior computed from all counts. It is the algorithm Theorem 4 is about. Its posterior correlation between two arms decays at rate 1/n1/n in their pull counts, which is why the structural effect is transient; CorrCTS-Full freezes the correlation and thereby trades Bayesian coherence for a persistent change in the sampling dynamics. A corralled combination [1] of CTS and GP-CTS(Σ) GP-CTS( ) would give a consistency–robustness guarantee of the learning-augmented type [10]: regret within O~(T) O( T) of the better base algorithm. The credibility gate of RobustCorrCTS is a heuristic with the same purpose and only the total-variation guarantee of Proposition 7; corralling is the right baseline for a follow-up and was not benchmarked here. Appendix D Data-adaptive variants CorrCTS-Prune keeps the initial kernel and, every 500500 rounds, zeroes Σij _ij whenever |μ^i−μ^j|>21/ni+1/nj| μ_i- μ_j|>2 1/n_i+1/n_j, then refactorizes. CorrCTS-KM blends the initial kernel with a kernel built from k-means on μ μ at t∈2,000,10,000t∈\2,000,10,000\ with weight w(t)=max(0.2,1−t/12,000)w(t)= (0.2,1-t/12,000) on the LLM kernel. Both make the decay of the correlation part of the dynamics rather than leaving it fixed. Appendix E Experimental details E1 instances. For (d,m)∈25,50×3,5(d,m)∈\25,50\×\3,5\: uniform-large (top m at 0.70.7, rest 0.550.55), uniform-small (rest 0.620.62), hard-gap (top m at 0.70.7, next m at 0.650.65, rest 0.50.5), staggered (means linearly spaced from 0.70.7 to 0.30.3); T=2,500T=2,500, 20 seeds. E2. The 16 E1 families plus 16 with fresh environment seeds; T=25,000T=25,000, 15 seeds. E3. MIND-small [14], 17,22617,226 articles with empirical CTRs; each instance samples d=200d=200 articles; three user profiles (“diverse”, “entertainment”, “tech”) reweight CTRs by category with weights fixed before any run; environment seeds 100,200,300\100,200,300\; T=10,000T=10,000, 15 seeds; oracle Claude Sonnet 4.6 (AWS Bedrock, temperature 0.30.3) receiving titles and μ μ and asked for K=8K=8 topic clusters. Hyperparameters. Tw=30T_w=30, K=8K=8, ρmax=0.7 _ =0.7, ℓ=0.5 =0.5; RobustCorrCTS Δcheck=100 _check=100; RandomCorr within-cluster ρ=0.6ρ=0.6; recommendation mixing τ=100τ=100, re-query every 100 rounds, one pseudo-success per recommended arm at each query; warm start 55 pseudo-successes. ρmax,ℓ,K,Tw _ , ,K,T_w were selected on (d,m)∈(25,3),(50,5)×uniform-large,hard-gap(d,m)∈\(25,3),(50,5)\×\uniform-large,hard-gap\ with environment seeds 700700–704704, disjoint from all test seeds. Sensitivity: reductions on E1 stay within 1515–20%20\% for ρmax∈[0.5,0.8] _ ∈[0.5,0.8] and ℓ∈[0.5,1.0] ∈[0.5,1.0]; ρmax=0.9 _ =0.9 and ℓ=0.25 =0.25 or 2.02.0 lose 22–44 points; Tw∈10,100T_w∈\10,100\ loses 22–44 points; K∈6,…,12K∈\6,…,12\ is flat. Simulated-oracle ablation. Same instances and seeds as E1; oracle label noise ε∈0,1/4,1/2,3/4,1 ∈\0, 14, 12, 34,1\; the adversarial partition places the true top-m and the m worst arms in one cluster and splits the remaining arms into K−1K-1 quality-sorted groups, with cluster order by μ μ as in Equation 1 (in the E1 adversarial test the merged cluster was additionally forced to rank first); all samplers share the CTS warmup and the kernel of Equation 1 with the E1 hyperparameters. The tempered control draws θ=μ¯+cσ⊙ϵθ= μ+c\,σ ε with independent ϵε. Each trial takes 0.020.02–0.20.2 s on one CPU core; the full sweep is about two minutes on ten cores. Compute. E1–E3 ran on a 16-core machine (33 s, 2525 s and 1212 s per trial respectively); total LLM cost about $12; LLM responses were cached. Appendix F Tables for the LLM-free ablation Table 3 checks the re-implementation, Table 4 is the kernel-shape ablation with the tempered controls, Table 6 tabulates Figure 2a, Table 5 tabulates Figure 2b, and Table 2 gives the per-(d,m)(d,m) breakdown. Table 2: Per-(d,m)(d,m) mean regret in the LLM-free ablation (T=2,500T=2,500; 4 gap families × 20 seeds =80=80 trials per cell). Sampler (25,3)(25,3) (25,5)(25,5) (50,3)(50,3) (50,5)(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 (ε=0 =0) 225.0 247.3 364.7 434.3 CorrCTS-Full (ε=0.5 =0.5) 223.4 233.8 338.9 413.4 CorrCTS-Full (ε=1 =1) 221.7 240.5 353.2 427.3 GP-CTS(Σ ) (ε=0 =0) 250.6 257.2 421.5 488.4 RobustCorrCTS (ε=0 =0) 250.6 247.9 390.3 438.6 Warm start (ε=0 =0) 256.1 280.4 452.7 496.1 Rec.-mixing (ε=0 =0) 254.2 239.1 431.2 466.0 Tempered CTS-Gaussian (c=0.6c=0.6) 196.8 241.3 281.6 356.5 Table 3: Re-implementation check of the LLM-free rows of Experiment 1 (16 configurations × 20 seeds, T=2,500T=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)(d,m) means. Algorithm Source Overall (25,3)(25,3) (25,5)(25,5) (50,3)(50,3) (50,5)(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, ρ=0.6ρ=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 Table 4: Kernel-shape versus partition-information ablation (LLM-free; n=320n=320 paired trials per row, T=2,500T=2,500). All RBF rows use the CorrCTS-Full kernel with identical (ρmax,ℓ,K)=(0.7,0.5,8)( _ , ,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 Partition Cluster order Regret vs CTS W/L (p) CTS — — 369.0 ± 6.6 — — Block-diagonal (RandomCorr) random none 351.2 ± 6.7 +4.8% 202/118 (<10−4<10^-4) RBF kernel random random 318.1 ± 6.6 +13.8% 239/81 (<10−4<10^-4) RBF kernel random by μ μ 309.9 ± 6.4 +16.0% 248/72 (<10−4<10^-4) RBF kernel oracle, ε=1 =1 by μ μ 310.7 ± 6.6 +15.8% 250/70 (<10−4<10^-4) RBF kernel oracle, ε=0.5 =0.5 by μ μ 302.4 ± 6.2 +18.0% 252/68 (<10−4<10^-4) RBF kernel oracle, ε=0 =0 by μ μ 317.8 ± 6.7 +13.9% 239/81 (<10−4<10^-4) RBF kernel adversarial by μ μ 316.4 ± 6.6 +14.2% 242/78 (<10−4<10^-4) RBF + credibility gate adversarial by μ μ 338.3 ± 6.7 +8.3% 208/112 (<10−4<10^-4) Tempered CTS-Gaussian (c=0.8c=0.8) none none 302.8 ± 6.1 +17.9% 247/73 (<10−4<10^-4) Tempered CTS-Gaussian (c=0.6c=0.6) none none 269.0 ± 7.1 +27.1% 273/47 (<10−4<10^-4) Tempered CTS-Gaussian (c=0.4c=0.4) none none 316.0 ± 11.0 +14.4% 220/100 (<10−4<10^-4) Table 5: Horizon dependence (LLM-free; 16 configurations × 10 seeds, T=25,000T=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. Sampler T=2.5T=2.5k 55k 1010k 2020k 2525k W/L RBF kernel, random partition/order +15.1% +14.2% +10.1% +4.3% +3.1% 114/46 CorrCTS-Full (ε=0 =0) +14.9% +12.6% +9.0% +5.0% +3.1% 113/47 CorrCTS-Full (ε=0.5 =0.5) +19.6% +18.8% +15.5% +11.1% +9.6% 122/38 GP-CTS(Σ ) (ε=0 =0) +2.2% +0.5% -1.9% -4.0% -4.6% 65/94 RobustCorrCTS (ε=0 =0) +10.8% +5.1% -1.6% -5.8% -6.6% 82/78 Tempered CTS-Gaussian (c=0.6c=0.6) +29.1% +25.8% +19.2% +6.6% +1.3% 112/48 Table 6: Structure versus belief injection at matched oracle quality (LLM-free; n=320n=320 paired trials per cell, T=2,500T=2,500). Every column receives the same simulated partition; ε is the fraction of arms whose cluster label is replaced by a uniformly random one (ε=0 =0: quality-sorted partition; ε=1 =1: random). NMI is against the top-m/rest partition (for reference, GPT-5.4 clusters in Experiment 1 had NMI 0.1550.155; random 0.100.10). Cells are paired regret reduction versus CTS (positive is better); W/L in brackets. ε NMI CorrCTS-Full GP-CTS(Σ ) 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 G Additional tables for the LLM experiments Table 7: E1 mean regret by (d,m)(d,m) (80 trials per cell) and E3 regret reduction by user profile (n=45n=45 per cell). E1 (25,3)(25,3) (25,5)(25,5) (50,3)(50,3) (50,5)(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 E3 Diverse Entmt. Tech CorrCTS-Full +41.4%+41.4\% +41.5%+41.5\% +40.4%+40.4\% CorrCTS-KM +41.2%+41.2\% +41.5%+41.5\% +40.3%+40.3\% CorrCTS-Prune +40.5%+40.5\% +39.6%+39.6\% +40.0%+40.0\% Warm-start −1.6%-1.6\% −0.3%-0.3\% −1.4%-1.4\% E2 by split. Mean regret on the original / held-out families (n=240n=240 each): CorrCTS-Prune 558.0558.0 / 598.9598.9, CorrCTS-Full 577.5577.5 / 598.3598.3, CTS 614.7614.7 / 617.1617.1; CorrCTS-KM was run on both splits jointly (573.8573.8). Pilot alternatives were at or below CTS at this horizon: per-arm damping 613.6613.6 (+0.4%+0.4\%), kernel decay toward IdI_d 623.8623.8 (−1.3%-1.3\%), a hierarchical-Bayes model over cluster means 630.5630.5 (−2.4%-2.4\%). Endogenous oracle quality. On the d=25,m=5d=25,m=5 family (20 seeds), the LLM’s best cluster covered 44 of 55 true top-m slots when μ μ came from 30 rounds of CTS warmup, but 0.150.15 of 55 on average when the same 30 rounds were round-robin, with only the numbers in the prompt differing; oracle quality is therefore endogenous to the learner’s trajectory, which is why we do not model it as an exogenous constant. E1 ablations. CorrCTS-Full beats RandomCorr by 12.7%12.7\% (p<10−4p<10^-4, 228/92); a block-diagonal kernel on the LLM partition (within-cluster correlation only, no rank ordering) does not beat RandomCorr (p=0.34p=0.34). Under adversarial clusters (true top-m grouped with the m worst arms, ranked first) CorrCTS-Full incurs 385.2385.2 against 330.7330.7 for CTS (+16.5%+16.5\% regret) and RobustCorrCTS 336.8336.8 (+1.8%+1.8\%). Section 4.2 shows that the margin over RandomCorr is explained by kernel shape. Cluster quality. NMI between the LLM partition and the top-m/rest partition over the 1,2801,280 E1 queries was 0.155±0.0020.155± 0.002 (random: 0.100.10), ranging from 0.090.09 at (50,3)(50,3) to 0.230.23 at (25,5)(25,5). NMI rose with model capability on the validation grid (GPT-4.1-mini 0.410.41, GPT-5-mini 0.440.44, GPT-5.4 0.520.52). Given Section 4.2, the E1 gain is not read as evidence of partition quality; the NMI numbers are reported for completeness. Cost. One cluster query is about 620620 tokens ($0.003 on GPT-5.4); recommendation mixing used about 25 queries per E1 trial. Per round, CorrCTS-Full costs one O(d2)O(d^2) matrix–vector product plus a one-time O(d3)O(d^3) Cholesky (<50<50 ms at d=200d=200); ESCB-style index maximization over (dm) dm subsets is infeasible at d=200,m=5d=200,m=5 without additional structure. Appendix H Additional figures Figure 3: The correlation matrix Σ of Equation 1 (ρmax=0.7 _ =0.7, ℓ=0.5 =0.5, K=8K=8) on a d=50d=50 staggered instance, arms sorted by true mean, for a quality-sorted partition, a noisy one (ε=0.5 =0.5), a random one, and the adversarial construction. Every matrix has unit diagonal and λmin≥1−ρmax _ ≥ 1- _ ; 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 γT _T of the kernel of Figure 3 under a uniform allocation (τ2=1/12τ^2= 112, σ2=1/4σ^2= 14, m=5m=5) against the two-term upper bound, the lower bound, and the independent-prior value. At ρmax=0.7 _ =0.7 the curves merge with the independent case within a few hundred rounds; at ρmax=0.97 _ =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.3q=0.3 upper quantile, as a function of the correlation ρ (2×1052× 10^5 Monte Carlo draws); dotted lines are the independent values qmq^m, the dashed line the limit q. Right: credibility wtw_t of RobustCorrCTS on the d=50,m=5d=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 Δcheck=100 _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 μ^i≈1 μ_i≈ 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 GP-CTS(Σ) GP-CTS( ) tracks CTS. Figure 7: Per-(d,m)(d,m) paired regret reduction versus CTS at T=2,500T=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=320n=320; c=1c=1 is CTS-Gaussian), with the two RBF samplers as dashed references and the value c=1−ρmaxc= 1- _ of Lemma 6(i) marked. CorrCTS-Full RobustCorrCTS Rec.-mixing RandomCorr block-diagonal CTS CUCB Figure 9: E1 cumulative regret (LLM partitions) on the uniform-small family at d=50d=50, m=3m=3 (20 seeds; bands are one standard error), complementing Figure 1.