Improving combinatorial bandit learning by adding structure to sampling
Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
Machine LearningArtificial Intelligence
Summary
This paper looks at how an AI model can help improve decision-making when choosing from many options with unknown rewards, like selecting articles to show readers. Usually, choices are made by sampling independently, ignoring how options are related. The authors propose using a language model to group related options and introduce correlations in sampling, which guides exploration better. They show this approach reduces mistakes in both synthetic tests and real news article recommendations, even when the model does not directly change what is believed about each option.
What this means in practice
- •For online content recommendation teams: Enhance article recommendation systems by incorporating structured correlations between content for better exploration and lower error rates.
- •For ad placement optimization teams: Use correlated sampling methods to improve ad selection from many correlated options, reducing learning time and regret in online campaigns.
Authors
Vikram Kakaria, Anish Kataria, Anany Kotawala
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.