A Broader View of Thompson Sampling

Sintesi Tecnica: Una Visione Più Ampia del Campionamento di Thompson

Enunciato del Problema
Il Campionamento di Thompson (TS) è un'euristica ampiamente utilizzata per il problema del Bandito Multi-Arma (MAB), nota per il suo successo empirico e i suoi limiti teorici di rimpianto. Tuttavia, a differenza delle politiche Upper Confidence Bound (UCB) o dell'indice di Gittins, il principio di ottimizzazione esplicito che governa l'equilibrio di TS tra esplorazione e sfruttamento rimane opaco. Mentre Gittins (1979) ha formulato il MAB bayesiano come un Processo Decisionale di Markov (MDP) per derivare una politica ottimale, tale approccio si basa su ricompense scontate a orizzonte infinito. Questa formulazione porta a un "apprendimento incompleto" (fallimento nell'identificare l'arma ottimale infinite volte), il che contraddice l'obiettivo di minimizzazione del rimpianto a orizzonte finito centrale nella letteratura MAB (Robbins 1952; Lai e Robbins 1985). Il documento affronta il vuoto nella comprensione di TS cercando una formulazione stazionaria "fedele" che si allinei alla minimizzazione del rimpianto a orizzonte finito, mantenendo al contempo la trattabilità della programmazione dinamica.

Metodologia
Gli autori propongono un quadro di stazionalizzazione fedele per riformulare il problema non stazionario di minimizzazione del rimpianto a orizzonte finito in un problema di ottimizzazione online stazionario.

1. Obiettivo del Rimpianto Quadrato: Invece di minimizzare direttamente il rimpianto cumulativo $R_T$ o utilizzare ricompense scontate, gli autori introducono la minimizzazione del rimpianto cumulativo quadrato $R_2$. Stabiliscono un limite $R_T \leq \sqrt{R_2 \cdot T}$. Minimizzare la somma a orizzonte infinito dei rimpianti quadrati $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ garantisce che la politica raggiunga il tasso di rimpianto ottimale $O(\sqrt{T})$, fornendo al contempo un obiettivo stazionario.
2. Equazione di Bellman Stazionaria: Questo nuovo obiettivo produce un'equazione di Bellman stazionaria per la funzione di valore $V(\pi_t)$ (il minimo rimpianto quadrato futuro):
   $$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$$
   A differenza dell'indice di Gittins (che massimizza la ricompensa scontata lineare), questa minimizzazione è quadratica nelle probabilità di azione, portando a una politica ottimale randomizzata piuttosto che deterministica.
3. Forma di Ottimizzazione Online: Tramite un cambio di variabile focalizzato sulla ricompensa attesa del prossimo turno $x_t$, gli autori derivano che la politica ottimale $R_2$ ($Q_{R2}$) assume la forma di un problema di ottimizzazione online:
   $$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$$
   Qui, il primo termine rappresenta lo sfruttamento istantaneo (avidità), mentre il secondo termine è una regolarizzazione lineare che rappresenta l'esplorazione. Il regolarizzatore $\nu_{R2}(\pi_t)$ è derivato dall'equazione di Bellman e misura la tensione tra esplorazione e sfruttamento (la differenza nel valore futuro tra l'estrazione delle armi).
4. Reinterpretazione del Campionamento di Thompson: Gli autori dimostrano che il Campionamento di Thompson ammette la stessa identica forma di ottimizzazione online:
   $$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$$
   Tuttavia, il suo regolarizzatore $\nu_{TS}(\pi_t)$ è la covarianza biseriale tra il divario di ricompensa ($\theta_1 - \theta_2$) e l'identità dell'arma ottimale ($\text{sign}(\theta_1 - \theta_2)$). Questo regolarizzatore misura l'incertezza su quale arma sia migliore, piuttosto che la tensione tra ricompensa immediata e valore futuro.

Contributi Chiave

• Stazionalizzazione Fedele: Il documento introduce una formulazione stazionaria (minimizzazione del rimpianto quadrato) che preserva l'essenza della minimizzazione del rimpianto a orizzonte finito, colmando il divario tra campionamento euristico e programmazione dinamica basata su principi.
• Unificazione Strutturale: Rivela che sia il Campionamento di Thompson sia la politica ottimale di Bellman ($Q_{R2}$) sono istanze di algoritmi di ottimizzazione online che bilanciano avidità contro un regolarizzatore.
• Identificazione del Meccanismo: Il documento identifica il meccanismo specifico che guida TS: regolarizza l'avidità basandosi sull'incertezza (covarianza biseriale), mentre la politica ottimale regolarizza basandosi sulla tensione (differenza di valore futuro).
• Miglioramento della Politica: Sfruttando il quadro di Bellman, gli autori propongono un passo standard di miglioramento della politica per TS. Valutando la funzione di valore di TS e reinserendola nell'equazione di Bellman, derivano una politica migliorata ($Q_{TS'}$) che utilizza un regolarizzatore basato sulla tensione.

Risultati

• Divario di Prestazioni: Gli esperimenti numerici su banditi Gaussiani e Bernoulliani mostrano che la politica ottimale $R_2$ ($Q_{R2}$) raggiunge un rimpianto cumulativo significativamente inferiore rispetto al Campionamento di Thompson. Il divario è attribuito al fatto che il regolarizzatore di TS è una misura di incertezza che non riesce a catturare la "tensione" quando l'arma leader è incerta ma l'arma subottimale è sovra-sfruttata.
• Campionamento Guidato dall'Informazione (IDS): Il documento rileva che l'IDS, un'altra euristica, condivide la stessa struttura di regolarizzatore basato sulla tensione di $Q_{R2}$ e performa quasi identicamente alla politica ottimale di Bellman, colmando le prospettive dell'informazione teorica e della programmazione dinamica.
• Miglioramento in un Passo: Un singolo passo di miglioramento della politica applicato al Campionamento di Thompson colma circa il 90% del divario di prestazioni tra TS e il benchmark ottimale di Bellman. Questo miglioramento trasforma efficacemente il regolarizzatore di TS da una misura di incertezza a una misura di tensione.
• Proprietà Strutturale nel Caso a K Braccia: Nell'impostazione a $K$ braccia, la politica ottimale di Bellman (e la TS migliorata) assegna una probabilità positiva ad al massimo due braccia in ogni turno, mentre la TS standard può assegnare una probabilità positiva a tutte le braccia. Il passo di miglioramento della politica conferisce a TS questa sparsità strutturale.

Significato
Il documento afferma di fornire una "visione più ampia" del Campionamento di Thompson riformulandolo come un algoritmo di ottimizzazione online. Questa lente:

1. Spiega l'Euristica: Chiarisce che TS bilancia esplorazione e sfruttamento regolarizzando l'avidità con una misura di incertezza residua.
2. Identifica i Limiti: Individua che la dipendenza di TS dall'incertezza piuttosto che dalla tensione porta a comportamenti subottimali in regimi specifici (ad esempio, quando l'arma ottimale è incerta ma l'arma subottimale è chiaramente sovra-sfruttata).
3. Abilita un Miglioramento Principale: Offre un quadro rigoroso per migliorare gli algoritmi di campionamento posteriori. Allineando il regolarizzatore alla misura di tensione ottimale di Bellman, gli autori dimostrano che TS può essere significativamente potenziato con un sovraccarico computazionale minimo (un singolo passo di iterazione della politica), avvicinandolo all'ottimo teorico senza abbandonare la sua natura basata sul campionamento.