Riepilogo Tecnico: PFN-TS

Enunciato del Problema

I banditi contestuali affrontano il processo decisionale sequenziale in condizioni di incertezza, dove un agente osserva un contesto, seleziona un'azione e riceve una ricompensa stocastica. L'obiettivo è minimizzare il rimorso cumulativo nel tempo. Thompson Sampling (TS) è una strategia standard che mantiene una distribuzione a posteriori bayesiana sulle funzioni di ricompensa e campiona le azioni in modo greedy da tale posterior. Tuttavia, l'efficacia di TS dipende dalla qualità del modello di ricompensa sottostante.

Nelle applicazioni tabellari (ad esempio, salute mobile, raccomandazioni), i modelli di ricompensa lineari sono spesso specificati in modo errato perché non riescono a catturare comportamenti umani complessi come interazioni, effetti di soglia ed eterogeneità. Sebbene esistano alternative più ricche (metodi kernel, reti neurali, ensemble di alberi), queste soffrono di problemi di scalabilità, elevati costi computazionali o assunzioni strutturali rigide. Inoltre, tali modelli richiedono tipicamente iperparametri difficili da ottimizzare in contesti online.

Le Reti Adattate ai Dati Priori (Prior-Data Fitted Networks - PFN), come TabPFN e TabICL, offrono un'alternativa promettente. Si tratta di modelli basati su transformer addestrati per approssimare le distribuzioni predittive a posteriori (PPD) su un ampio prior di processi di generazione dei dati. Operano tramite apprendimento in contesto (ICL), non richiedendo aggiornamenti dei parametri né ottimizzazione degli iperparametri. Tuttavia, esiste un divario critico: le PFN producono PPD (incertezza sulle ricompense future rumorose), mentre TS richiede incertezza sulla funzione di ricompensa media latente. Campionare direttamente dalla PPD non equivale a campionare dalla posterior della funzione media, portando a un'esplorazione subottimale.

Metodologia: PFN-TS

Gli autori propongono PFN-TS, un algoritmo di Thompson Sampling che colma questo divario convertendo le predittive posteriori delle PFN in campioni della funzione di ricompensa media latente. La metodologia consta di tre componenti fondamentali:

1. Teorema del Limite Centrale Predittivo Campionato (SubCLT)

Per recuperare la distribuzione a posteriori della media latente $f_0(x)$ dalla sequenza predittiva della PFN, gli autori sfruttano un Teorema del Limite Centrale (CLT) predittivo.

• Fondamento Teorico: Sotto specifiche assunzioni (varianza asintotica, condizioni di quasi-martingala e momenti limitati), la coda della sequenza della media predittiva converge a una distribuzione Gaussiana centrata sulla media latente.
• Innovazione in Efficienza: Gli approcci tradizionali per stimare la varianza a posteriori richiedono il calcolo della media predittiva su tutti gli $n$ prefissi del dataset, il che è computazionalmente proibitivo per i banditi online ($O(n)$ passaggi in avanti). PFN-TS introduce un stimatore campionato che calcola la varianza utilizzando solo $O(\log n)$ prefissi spaziati geometricamente ($t_0, t_1, \dots, t_J$).
• Stima della Varianza: La varianza è stimata utilizzando incrementi di blocco $D_j = m_{t_j}(x) - m_{t_{j-1}}(x)$ ponderati armonicamente ($w_j$). Gli autori dimostrano che questo stimatore campionato è consistente ($\hat{V}_{s_n} \xrightarrow{p} V(x)$) e soddisfa il CLT, permettendo un'approssimazione Gaussiana trattabile $N(m_{s_n}(x), \hat{V}_{s_n}(x)/s_n)$ per il Thompson Sampling.

2. Memorizzazione e Ottimizzazione Computazionale

Per ridurre ulteriormente il costo per round, PFN-TS sfrutta l'architettura di TabICL (la specifica PFN utilizzata):

• Riutilizzo della KV-Cache: TabICL memorizza in cache le matrici di attenzione chiave-valore per un dataset di addestramento fisso. PFN-TS riutilizza queste rappresentazioni in cache tra i vari round.
• Punti di Aggiornamento: L'algoritmo esegue nuovi passaggi in avanti solo ai "punti di aggiornamento" geometrici ($t_j$) definiti dalla griglia SubCLT. Tra i punti di aggiornamento, utilizza l'approssimazione Gaussiana istantanea derivata dall'ultimo stato in cache. Ciò riduce la complessità da $O(n)$ a $O(\log n)$ passaggi in avanti per braccio per round.

3. Strategia di Codifica Adattiva

Il lavoro affronta la scelta progettuale su come rappresentare l'identità del braccio nell'input:

• Codifica Disgiunta: Mantiene modelli indipendenti per ogni braccio.
• Codifica Congiunta: Aggiunge l'identità del braccio come vettore one-hot al contesto, permettendo la condivisione di informazioni tra i bracci.
• Selezione Adattiva: Poiché nessuna codifica domina universalmente, PFN-TS esegue entrambe in parallelo durante una fase di "dual-encoding". Seleziona la codifica attiva basandosi sul Continuous Ranked Probability Score (CRPS), una regola di punteggio strettamente propria che misura la calibrazione. La codifica con il CRPS cumulativo inferiore viene mantenuta, mentre la sfidante viene scartata dopo un tempo di switch predefinito.

Contributi Chiave

1. Ponte Algoritmico: PFN-TS è il primo metodo che adatta con successo le PFN (che producono PPD) per il Thompson Sampling, derivando uno stimatore consistente per la varianza a posteriori della media latente tramite un CLT campionato.
2. Garanzie Teoriche:
   • Consistenza: Dimostra la consistenza dello stimatore di varianza campionato sotto assunzioni lievi.
   • Limite di Rimorso: Deriva un limite di rimorso bayesiano per PFN-TS. Il limite si scompone nel rimorso del Thompson Sampling esatto sotto il prior della PFN più un termine di errore dipendente dalla qualità dell'approssimazione della PFN e dal processo di campionamento.
3. Efficienza: Dimostra che $O(\log n)$ passaggi in avanti sono sufficienti per una stima consistente della varianza, rendendo i banditi basati su PFN fattibili per il deployment online.
4. Prestazioni Empiriche:
   • Benchmark Sintetici: PFN-TS ottiene il miglior rango medio su compiti sintetici non lineari (varianti di Friedman) e rimane competitivo su compiti lineari.
   • Benchmark OpenML: Supera le linee di base (LinTS, NeuralTS, BFTS, XGBoostTS) su sei degli otto dataset di classificazione-a-bandit.
   • Applicazione Reale: In una valutazione offline del trial di salute mobile Drink Less, PFN-TS raggiunge il valore di politica stimato più alto (SNIPS) all'orizzonte finale, superando BFTS e altre linee di base.

Significato e Affermazioni

Il lavoro afferma che PFN-TS dimostra che l'apprendimento in contesto tabellare può fungere da modello di ricompensa efficace per il processo decisionale sequenziale una volta implementate un'estrazione efficiente dell'incertezza e una codifica adattiva.

• Flessibilità del Modello: A differenza dei modelli tradizionali, PFN-TS non richiede ottimizzazione degli iperparametri e si adatta automaticamente alla struttura dei dati (sparsità, regolarità, non linearità) intrinseca nel prior ampio della PFN.
• Fattibilità Pratica: Riducendo il collo di bottiglia computazionale della stima dell'incertezza da lineare a logaritmico rispetto alla dimensione del dataset, il metodo rende pratico il deployment di modelli fondazionali in contesti di banditi online.
• Robustezza: Il metodo si dimostra robusto attraverso processi di generazione dei dati diversificati, performando bene sia su compiti sintetici non lineari che su dati reali di salute mobile.

Gli autori mantengono un tono modesto riguardo alle limitazioni, notando che il tempo di esecuzione rimane un vincolo a causa delle valutazioni ripetute del modello, e che la calibrazione su campioni finiti può essere scarsa quando le storie dei bracci sono brevi o scarsamente informative. Suggeriscono lavori futuri su stime di varianza regolarizzate e limiti di rimorso più stringenti per i prior specifici TabPFN/TabICL.