arXiv cs.AI· Vikram Kakaria, Anish Kataria, Anany Kotawala·· 10 天前AI 评分22
用 LLM 推导的协方差做相关 Thompson 采样：组合半臂老虎机中的结构与信念
Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
AI 导读
研究者提出一种组合 Thompson 采样（CTS）的最小改动：用 LLM 查询一次臂的分区，经 RBF 核在簇排名上转成正定相关矩阵 Σ，每轮后验样本按 Σ 采样，而 Beta 后验仍只用真实奖励更新，让 LLM 影响采样器的移动方式而非其信念。
正文 · 原文
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.
| Comments: | 15 pages. Accepted (poster) at DynaFront 2026: Dynamics at the Frontiers of Optimization, Sampling, and Games, NeurIPS 2026 Workshop |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.07470 [cs.LG] |
| (or arXiv:2610.07470v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07470 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Vikram Kakaria [view email]
[v1]
Mon, 5 Oct 2026 22:35:58 UTC (203 KB)
来源：arXiv cs.AI · arxiv.org