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

AI summary

Overview

Research area: Machine learning — combinatorial semi-bandits, Thompson sampling, and LLM-augmented decision making.

Technical level: Advanced. The paper combines a self-contained Bayesian regret analysis (elliptical potential, Slepian's inequality, information-gain decompositions) with an empirical study using two named LLMs and the Microsoft MIND benchmark.

One-sentence scope: The paper shows that querying an LLM once for a partition of arms and using that partition only to correlate the sampler's random draws (rather than to inject beliefs about rewards) produces consistent but finite-horizon regret improvements, and that on unstructured instances the gain comes from the shape of the correlation kernel rather than the information in the partition.

What This Paper Is About

Combinatorial Thompson sampling (CTS) draws an independent random value for every arm each round, so its exploration behaviour carries no information about which arms resemble each other. The authors ask what changes if an LLM is queried once for a grouping of the arms, that grouping is converted into a positive-definite correlation matrix, and the per-round posterior sample is drawn with that correlation — while the Beta posteriors themselves are still updated from real rewards only. The goal is to move LLM information out of the learner's beliefs (where a wrong answer biases the posterior at the cost of real observations) and into the covariance of the sampling step (where a wrong answer can distort the sampler's motion but cannot corrupt its state).

Key Contributions

1. A formal statement of what the correlation matrix represents and a regret bound for the idealized sampler. Assumption 2 defines Σ as the prior correlation of the arm means, and GP-CTS(Σ) is Thompson sampling under that Gaussian model. Theorem 4 gives a self-contained Bayesian regret bound 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 √(d/K) improvement over independent sampling is shown to be a finite-horizon transient, exact only as the within-cluster correlation ρ_max tends to 1.

2. CorrCTS-Full as a fixed-correlation, calibrated-marginal approximation to GP-CTS(Σ). Two lemmas characterize what a fixed correlation does to top-m selection: Lemma 5 (Slepian's inequality: per-arm marginals are untouched while joint exceedance probabilities rise and are nondecreasing in each off-diagonal entry) and Lemma 6 (correlation shrinks the variance of pairwise comparisons; in the equicorrelated case top-m selection is exactly independent sampling tempered by c = √(1−ρ)). Proposition 7 provides a total-variation guarantee for the credibility gate.

3. LLM experiments on synthetic Bernoulli families and real MIND click data. GPT-5.4 supplies partitions for E1–E2 and Claude Sonnet 4.6 for E3, with paired comparisons and Holm–Bonferroni correction; a breakdown by LLM appears in the appendices.

4. An LLM-free ablation with a simulated oracle of controlled quality. Every injection mode receives the same simulated partition, separating kernel shape from partition information and structure from belief.

Main Findings

• Regret reduction on synthetic families: The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families at T = 2,500. On E1 (d ∈ {25, 50}, m ∈ {3, 5}, four gap families, 20 seeds, n = 320), gains grow with d: 12–15% at d = 25 and 19–25% at d = 50.

• E1 headline table: CTS mean regret 330.7. CorrCTS-Full 268.2 (+18.9%, 262/58 wins/losses, p < 10⁻⁴); recommendation mixing (a belief method) 279.5 (+15.5%, 143/97, p = 0.0036); RobustCorrCTS 284.2 (+14.1%, 237/83, p < 10⁻⁴); RandomCorr with a block random partition 307.2 (+7.1%, 227/93, p < 10⁻⁴).

• The advantage decays with the horizon: At T = 25,000 (E2; 16 E1 families plus 16 held-out, 15 seeds, n = 480) CTS reaches 615.9, static CorrCTS-Full 587.9 (+4.5%), CorrCTS-Prune 578.5 (+6.1%), CorrCTS-KM 573.8 (+6.8%), all p < 10⁻⁴. The static advantage decays and the data-adaptive variants overtake it, as Theorem 4 predicts. The abstract states the horizon effect as 6–7% at T = 25,000 with data-adaptive kernels.

• Strong result on real news data: On MIND-small (d = 200 real articles, m = 5, T = 10,000, three user profiles × three article samples, 15 seeds, n = 135) the reduction is 41% versus CTS. CTS mean regret is 1573.7; CorrCTS-Full 927.5 (+41.1%, 134/1), CorrCTS-KM 928.6 (+41.0%, 134/1), CorrCTS-Prune 943.7 (+40.0%, 133/2), all p < 10⁻⁶. The reduction is stable across profiles (40–42%).

• Pseudo-observation warm starts give nothing: Warm-start CTS scores 1591.4, i.e. −1.1% versus CTS (53/82, p = 0.014) on E3; the benefit is flooded by real data. In the ablation, warm start never differs from CTS across ε ∈ [0,1].

• Adversarial partitions expose the gate: Under adversarial clusters (true top-m grouped with the m worst arms and ranked first) CorrCTS-Full loses 16.5% to CTS on E1 while RobustCorrCTS loses 1.8%.

• Kernel shape, not partition information: In the LLM-free ablation with a simulated oracle, a random partition in random order through the RBF kernel already gives +13.8% over CTS; the quality-sorted partition gives +13.9%; an adversarial partition that groups the true top-m with the m worst arms (keeping the μ̂ rank order) gives +14.2%.

• Tempering is the LLM-free competitor to beat: Independent CTS-Gaussian with posterior standard deviation scaled by c = 0.6 reduces regret by +27.1% at T = 2,500 — more than any kernel. With ρ_max = 0.7, √(1−ρ_max) ≈ 0.55, and the best tempering factor found is near c = 0.6.

• Belief injection degrades with oracle quality: Across ε ∈ [0,1], the structure samplers stay between +14% and +18%, recommendation mixing falls from +5.8% to −10.5% as ε goes from 0 to 1, and the exact Bayesian GP-CTS(Σ) gains at most +3.9%.

• Everything is transient: At T = 25,000 the RBF samplers retain +3%, the tempered sampler +1%, and GP-CTS(Σ) and the gated sampler fall slightly below CTS.

• Theory matches the crossover: At the experimental values (d = 50, m = 5, ρ = 0.7, τ² = 1/12, σ² = 1/4) Proposition 9 bounds the crossover at T* ≤ 149 rounds, so a proper Bayesian sampler should gain little at T = 2,500 — which Section 4.2 confirms.

• Posterior integrity: Proposition 1 shows the Beta parameters of every arm coincide under CorrCTS-Full, RobustCorrCTS and CTS for every reward sequence; Σ enters only the sampling step, and Σ = I_d recovers CTS.

Methodology in Plain English

Setting. There are d arms with unknown means in [0,1]. Each round the learner plays m of them and observes a Bernoulli reward from each played arm. Regret is the gap between the reward of the best possible set of m arms and the set actually played.

Baseline. CTS keeps a Beta posterior per arm, draws one independent sample per arm, plays the top m of those samples, and updates only the played arms.

The one-shot query. At a warmup time T_w the learner may send the empirical means (and, for MIND, article titles) to an LLM that returns a partition of the arms into K clusters of unknown quality. Clusters are ranked by their empirical mean at T_w; each arm receives a normalized rank f_i = r_{k(i)}/(K−1) in [0,1]. The correlation matrix is Σ_ij = ρ_max exp(−(f_i − f_j)²/(2ℓ²)) for i ≠ j and Σ_ii = 1. Writing G for the RBF Gram matrix on the features, Σ = ρ_max G + (1 − ρ_max) I_d, which is positive definite for any partition, with rank(G) ≤ K.

CorrCTS-Full. Rounds t ≤ T_w are plain CTS. At T_w the partition becomes Σ and its Cholesky factor L. Afterwards each round takes the Beta posterior mean μ̄_i and standard deviation σ_i, draws ε ~ N(0, I_d), and plays the top m of θ = μ̄ + σ ⊙ (Lε). The marginal of θ_i is the moment-matched Gaussian N(μ̄_i, σ_i²) — identical to what independent sampling would give — and only the joint law changes.

Robustness and adaptivity. RobustCorrCTS adds a credibility weight w updated every Δ_check rounds via w ← 0.7w + 0.3·overlap_t, where overlap_t is the fraction of the empirical top-m inside the oracle's best cluster, and plays the top m of a weighted mixture of the correlated and independent draws. CorrCTS-Prune and CorrCTS-KM refresh Σ from data at long horizons without new LLM queries.

Theory. The analysis is conducted for GP-CTS(Σ), the exact Gaussian-posterior sampler, under Assumption 2 (μ ~ N(μ₀1, τ²Σ), Gaussian observation noise). Lemma 3 bounds the information gain; Theorem 4 converts it to a Bayesian regret bound via an elliptical-potential argument following Russo and Van Roy.

Evaluation. Paired comparisons on the same instance and seed, with Holm–Bonferroni correction. The synthetic experiments use four gap families (uniform-large: top m at 0.7, rest 0.55; uniform-small: rest 0.62; hard-gap: top m at 0.7, next m at 0.65, rest 0.5; staggered: means linearly spaced from 0.7 to 0.3). E3 uses MIND-small with 17,226 articles carrying empirical CTRs, sampling d = 200 per instance, with weights fixed before any run and environment seeds {100,200,300}; the oracle is Claude Sonnet 4.6 on AWS Bedrock at temperature 0.3, asked for K = 8 topic clusters. Hyperparameters (T_w = 30, K = 8, ρ_max = 0.7, ℓ = 0.5) were selected on a validation grid with environment seeds 700–704, disjoint from all test seeds.

The ablation. To separate partition quality from kernel shape, the researchers replace the LLM with a simulated oracle: the quality-sorted partition into K = 8 groups with each label randomized with probability ε. All modes — including warm start and recommendation mixing — receive the same partition. Warm start injects 5 pseudo-successes for the best-ranked cluster's arms; recommendation mixing re-queries every 100 rounds with τ = 100 and one pseudo-success per recommended arm per query.

Why This Matters

Impact on research. The paper isolates a distinction that most LLM-augmented bandit work blurs: using a model to shape how a stochastic learner explores versus using it to shape what the learner believes. It backs this with a posterior-integrity result (the Beta parameters are unchanged, so a bad Σ cannot corrupt the state), a regret bound, and an ablation that shows the gain on unstructured instances is reproducible by a random partition or by plain tempering of sampling noise. That last finding is a direct challenge to attribution claims in the LLM-for-bandits literature.

Real-world applications:

• News and content recommendation. The strongest empirical result is on MIND-small, where the reduction is stable at 40–42% across three user profiles.
• Advertising and ranking systems. Any setting that selects a fixed-size slate of items per round and observes per-item feedback matches the combinatorial semi-bandit model.
• Adaptive experiment design. Clinical or industrial trials that assign m of d treatments per batch and need principled exploration under a fixed horizon.
• LLM-augmented decision pipelines. Systems that already have access to a language model's semantic grouping of items can use it at a single query point rather than as a continuous belief source.

Industry relevance. The method requires exactly one LLM query, which matters for cost and latency in production. It is safe by construction against bad model output, and the paper is explicit that the benefit is transient and largest where latent structure exists — a useful scoping statement for deployment. The paper also documents a direct observation of belief injection's feedback-loop failure mode, in which answer quality depends on the estimates the model is shown, which depend on the learner's own trajectory.

Future Directions

1. Corralling as the principled alternative. The authors note that a corralled combination of CTS and GP-CTS(Σ) would give a consistency–robustness guarantee of the learning-augmented type: regret within Õ(√T) of the better base algorithm. They state that corralling is the right baseline for a follow-up and was not benchmarked here.

2. Closing the theory–algorithm gap. Theorem 4 concerns GP-CTS(Σ), not CorrCTS-Full. Misspecification is covered only by Lemmas 5, 6 and 7. A regret analysis of the fixed-correlation sampler, or a coupling argument for trajectories that share a posterior only until their first disagreement, remains open — the paper explicitly declines to claim a regret inequality for the gate.

3. Broadening the empirical base. E3 uses one dataset and one LLM, and the abstract names Microsoft MIND-small as the sole real benchmark. Additional domains, additional oracles, and multi-query settings are untested.

4. Understanding the transient more sharply. The √(d/K) advantage is exact only as ρ_max → 1, and at the experimental values the crossover is bounded by T* ≤ 149 rounds. Whether longer-horizon structures exist — for example the data-adaptive refresh rules in CorrCTS-Prune and CorrCTS-KM — can convert a decaying correlation into a persistent one is left to future work.

Target Audience

Researchers working on bandit algorithms, sequential decision making, and LLM-augmented learning systems will find the theoretical

Authors’ 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.