Sintesi Tecnica: Thompson Sampling con Correzione di Flusso per Banditi Contestuali Non Stazionari

Formulazione del Problema

Il paper affronta la sfida dei banditi contestuali lineari non stazionari, un contesto in cui la relazione tra contesti, azioni e ricompense evolve nel tempo. Nei banditi contestuali classici, il vettore di parametri $w_t$ è assunto come stazionario. Tuttavia, nelle applicazioni del mondo reale (ad esempio, sistemi di raccomandazione, prezzi dinamici, finanza), le preferenze degli utenti e le condizioni di mercato subiscono derive, rendendo i dati storici sistematicamente distorti se utilizzati ingenuamente.

La difficoltà principale risiede nel compromesso tra il mantenimento dei dati storici per ridurre la varianza della distribuzione a posteriori e lo scarto dei dati obsoleti per evitare distorsioni derivanti da modelli non più attuali. Gli approcci esistenti — come le finestre scorrevoli (sliding windows), lo sconto esponenziale e i riavvii periodici — trattano i dati storici principalmente come un onere da gestire attraverso lo scarto uniforme o la riduzione del peso. Gli autori sostengono che quando la non-stazionarietà presenta una struttura prevedibile (ad esempio, deriva graduale, periodicità o regimi ricorrenti), le osservazioni storiche contengono informazioni preziose che possono essere sfruttate se corrette per i cambiamenti ambientali intervenuti.

Metodologia: Thompson Sampling con Correzione di Flusso (FC-TS)

Gli autori propongono il Thompson Sampling con Correzione di Flusso (FC-TS), un framework bayesiano che trasforma le osservazioni storiche in "pseudo-osservazioni al tempo presente" prima di incorporarle nella distribuzione a posteriori. Il metodo scinde la gestione della non-stazionarietà in due componenti distinte: un operatore di trasporto e una regola di ponderazione della confidenza.

1. Meccanismo Centrale

In ogni round $t$, per ogni osservazione passata $(x_s, a_s, r_s)$, l'FC-TS costruisce una ricompensa trasportata $\hat{r}_{s \to t}$:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
dove $\hat{\Delta}_{s \to t}$ stima lo spostamento della media della ricompensa dal tempo $s$ al tempo $t$. Questo "fa fluire" efficacementmente la ricompensa passata in avanti per allinearla al modello di ricompensa attuale.

Per evitare che il rumore derivante da stime di deriva imprecise influenzi il modello, a ogni osservazione trasportata viene assegnato un peso di confidenza $\omega_{s,t} \in [0, 1]$. Questo peso controlla l'influenza dell'osservazione sulla distribuzione a posteriori, gonfiando la sua varianza di rumore effettiva qualora la correzione sia incerta.

La distribuzione a posteriori per l'azione $a$ viene aggiornata utilizzando queste osservazioni pesate e trasportate:
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
La selezione dell'azione procede tramite il classico Thompson sampling utilizzando la distribuzione gaussiana $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Istanze Strutturate

Il framework fornisce un modello unificato con specifiche istanze per tre comuni pattern di non-stazionarietà:

• Deriva Lineare (Linear Drift): Assume che i parametri evolvano come $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$. L'operatore di trasporto utilizza una stima di regressione ridge online $\hat{\delta}_t^{(a)}$ per traslare le ricompense: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. I pesi decadono esponenzialmente ($\omega_{s,t} = \gamma^{t-s}$) per tenere conto dell'incertezza di estrapolazione.
• Variazione Periodica (Periodic Variation): Assume che i parametri si ripetano con un periodo $P$. L'operatore di trasporto è l'identità ($\hat{r}_{s \to t} = r_s$) per le osservazioni nella stessa fase. I pesi sono determinati dalla distanza circolare tra le fasi, permettendo all'algoritmo di riutilizzare i dati dei cicli precedenti ($\omega_{s,t}$ dipende dalla vicinanza di fase).
• Regimi Ricorrenti (Recurring Regimes): Gestisce ambienti che oscillano tra un insieme finito di regimi. L'algoritmo mantiene un archivio di distribuzioni a posteriori specifiche per ogni regime. Al rilevamento di un punto di cambiamento (tramite CUSUM sui residui di predizione), l'algoritmi ricarica la distribuzione a posteriori del regime che si sta ripresentando, invece di ricominciare da zero.

Il framework supporta anche la composizione, consentendo di gestire simultaneamente la deriva lineare e la periodicità combinando i rispettivi operatore di trasporto e regole di ponderazione.

Contributi Chiave

1. Aggiornamenti della Distribuzione a Posteriori Corretti dal Flusso: Il paper introduce una visione basata sul trasporto della non-stazionarietà, in cui le ricompense passate vengono corrette in pseudo-osservazioni al tempo presente e incorporate tramite aggiornamenti bayesiani pesati per confidenza, anziché essere scartate uniformemente.
2. Design Algoritmico Modulare: FC-TS è definito da un generico operatore di trasporto e una regola di ponderazione, istanziati per deriva lineare, variazione periodica e regimi ricorrenti. Ciò include una variante adattiva che combina trend e molteplici periodicità.
3. Validazione Empirica: Una valutazione estesa su cinque casi studio (deriva lineare, variazione periodica, regimi ricorrenti, non-stazionarietà composta e selezione di portafoglio semi-sintetica) dimostra che FC-TS supera le metodologie basate sull'oblio (forgetting-based) allo stato dell'arte.

Risultati Sperimentali

Gli autori hanno valutato FC-TS contro quattro baseline: Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) e Restarting TS (R-TS).

• Guadagni di Performance: FC-TS ha ottenuto il minor regret cumulativo in tutti e cinque gli scenari, con miglioramenti compresi tra il 14,1% e il 59,0% rispetto alla migliore baseline in ogni specifico ambiente.

• Approfondimenti Specifici per Caso:

  • Deriva Lineare: FC-TS ha eguagliato SW-TS durante la fase di warm-up, ma si è progressivamente distanziato man mano che le stime di deriva si stabilizzavano, vincendo in 8 casi su 10 seed.
  • Variazione Periodica: FC-TS ha mostrato il maggior guadagno sintetico (50,0%) grazie alla "memoria di fase", accumulando dati dai cicli precedenti. Il regret per ciclo è sceso da circa 70 a circa 4, mentre le baseline sono rimaste piatte.
  • Regimi Ricorrenti: FC-TS ha ottenuto un miglioramento del 59,0% ricaricando le distribuzioni a posteriori specifiche del regime al rilevamento di un cambio, evitando la penalità del "cold start" tipica dei riavvii.
  • Non-stazionarietà Composta: In ambienti con sia deriva che cambiamenti improvvisi, FC-TS ha combinato con successo la correzione della deriva (per l'evoluzione fluida) e il reset dei regimi (per i cambiamenti bruschi), ottenendo un miglioramento del 29,5%.
  • Portafoglio Semi-Sintetico: In un compito finanziario con cicli mensili/trimestrali sovrapposti e deriva crescita-valore (growth-to-value), la variante adattiva di FC-TS ha migliorato il regret del 28,1% rispetto alla migliore baseline (D-TS). Gli studi di ablazione hanno confermato che la correzione della deriva è stata la componente dominante di questo guadagno.

• Risultati dell'Ablazione:

  • Dimensione Campionaria Effettiva: Mantenere più dati senza la correzione di trasporto (l'ablazione "no-transport") ha portato a un regret maggiore rispetto ai metodi che scartano i dati, confermando che i dati obsoleti introducono una distorsione sistematica.
  • Valore del Trasporto: L'operatore di trasporto da solo ha rappresentato una riduzione del regret del 47–57% rispetto alla variante senza trasporto in varie scale di deriva, provando che il meccanismo di correzione, e non solo la ricostruzione della distribuzione a posteriori, guida le prestazioni.

Significato e Rivendicazioni

Il paper sostiene che la non-stazionarietà strutturata viene gestita meglio correggendo e riutilizzando l'esperienza piuttosto che scartandola uniformemente.

Gli autori sottolineano che quando la deriva dell'ambiente è prevedibile (graduale, periodica o ricorrente), i dati storici sono un asset piuttosto che un onere. Esplicitando il "flusso" della distribuzione delle ricompense nel tempo, FC-TS mantiene una dimensione campionaria effettiva molto più ampia rispetto ai metodi basati sull'oblio. I risultati suggeriscono che la chiave per l'efficienza campionaria nei banditi non stazionari risieda nel riponderare e correggere le osservazioni storiche in base alla specifica struttura temporale dell'ambiente, piuttosto che applicare una singola regola di oblio uniforme.

Il lavoro si conclude con una nota di modestia, segnalando che i lavori futuri includeranno l'apprendimento online delle strutture di deriva con incertezza calibrata, l'estensione del framework ai banditi neurali o lineari generalizzati e lo sviluppo di salvaguardie per contesti ad alto rischio con shift di distribuzione non modellati.