Metraipolis › archive › dc_fc70f5a4d408

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07470
License (as archived)
CC0-1.0
Archived
2026-10-07T11:20:43.245Z
SHA-256 of the archived text
4f1d3f0d8202fd812724cc8359903d40c6ffc3e5945d2127eb3ef6d6c28fc4f0
Stable URL of this page
https://metraipolis.com/documento/dc_fc70f5a4d408

How to cite

Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits — arXiv:2610.07470 — arXiv (en), https://arxiv.org/abs/2610.07470 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fc70f5a4d408 (Metraipolis archive dc_fc70f5a4d408, sha256 4f1d3f0d8202fd812724cc8359903d40c6ffc3e5945d2127eb3ef6d6c28fc4f0)
BibTeX
@misc{dcfc70f5a4d408,
  title = {Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits — arXiv:2610.07470},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07470},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fc70f5a4d408; sha256 4f1d3f0d8202fd812724cc8359903d40c6ffc3e5945d2127eb3ef6d6c28fc4f0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07470. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.07470 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:15:24.720Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).