Struttura, non convinzioni: campionamento di Thompson correlato con covarianza ricavata da un LLM nei semi-bandit combinatori

Abstract degli autori

Il campionamento di Thompson combinatorio (CTS) estrae campioni indipendenti dalle distribuzioni a posteriori di ciascun braccio, perciò la sua dinamica di esplorazione ignora le relazioni tra i bracci. Studiamo una modifica minima di questa dinamica: interroghiamo una sola volta un LLM per ottenere una partizione dei bracci; tramite un kernel RBF applicato ai ranghi dei cluster, la partizione viene trasformata in una matrice di correlazione definita positiva $Σ$. A ogni turno, il campione viene estratto con covarianza $Σ$, mentre le distribuzioni a posteriori Beta vengono aggiornate solo in base alle ricompense reali: l’LLM determina come si muove il campionatore, non ciò in cui crede. Forniamo una dimostrazione autonoma di un limite superiore al regret bayesiano per il campionatore gaussiano idealizzato, il cui guadagno di informazione si scompone in un termine $K\log T$ dovuto alla struttura a $K$ cluster e in un termine ridge che cresce fino a $d\log T$: il miglioramento di $\sqrt{d/K}$ rispetto al campionamento indipendente è transitorio e limitato a un orizzonte finito, ed è esatto solo quando la correlazione all’interno dei cluster tende a uno. Il campionatore correlato riduce il regret del 19% rispetto a CTS su 16 famiglie sintetiche di Bernoulli a $T=2{,}500$ (del 6-7% a $T=25{,}000$ con kernel adattati ai dati) e del 41% sul benchmark di notizie Microsoft MIND-small ($d=200$ articoli reali), mentre le inizializzazioni con pseudo-osservazioni non apportano alcun beneficio. Un esperimento di ablazione senza LLM, con un oracolo simulato di qualità controllata, mostra che, nelle istanze prive di struttura, il vantaggio dipende dalla forma del kernel (lo riproducono sia una partizione casuale sia una semplice attenuazione del rumore di campionamento), mentre l’inserimento delle indicazioni dell’oracolo nelle distribuzioni a posteriori non aiuta mai, a parità di qualità dell’oracolo.