Riassunto Tecnico: Apprendimento On-Policy e Off-Policy per Spazi di Azione Grandi

Definizione del Problema

La tesi affronta la sfida fondamentale dell'apprendimento in sistemi interattivi, specificamente nei bandit contestuali, dove lo spazio delle azioni $K$ è estremamente grande (da migliaia a milioni). In tali contesti, gli algoritmi standard sia per l'apprendimento on-policy (online) che off-policy (offline) affrontano gravi colli di bottiglia di scalabilità:

• On-Policy: Le strategie di esplorazione standard come Thompson Sampling (TS) o Upper Confidence Bound (UCB) si basano tipicamente su modelli disgiunti in cui ogni azione ha un parametro indipendente. In spazi di azione grandi, apprendere ogni parametro indipendentamente è statisticamente inefficiente, portando a un alto regret cumulativo. Al contrario, i modelli congiunti che condividono parametri tra tutte le azioni sono spesso computazionalmente intrattabili a causa della complessità $O(K^2)$ o $O(K^3)$ nel mantenere e aggiornare una matrice di covarianza completa.
• Off-Policy: L'apprendimento da dati statici registrati da una politica di logging $\pi_0$ affronta tre problemi principali:
  1. Inefficienza Statistica: I metodi diretti (DM) soffrono di un alto bias quando le azioni sono raramente osservate.
  2. Varianza: Gli stimatori Inverse Propensity Scoring (IPS) mostrano una varianza esplosiva quando la probabilità di logging $\pi_0(a|x)$ è piccola.
  3. Intrattabilità dell'Ottimizzazione: La tesi sostiene che, in spazi di azione grandi, il panorama di ottimizzazione degli obiettivi standard basati su IPS diventa altamente non concavo, con plateau piatti ed esponenzialmente molti massimi locali, causando il fallimento degli ottimizzatori basati sul gradiente indipendentemente dalla qualità statistica dello stimatore.

Metodologia e Contributi

La tesi è divisa in due parti, proponendo nuovi metodi per ciascun paradigma di apprendimento.

Parte I: Apprendimento On-Policy (Scalare il Thompson Sampling)

L'intuzione centrale è mantenere la flessibilità dei modelli di ricompensa disgiunti introducendo al contempo prior bayesiani strutturati che consentano la condivisione delle informazioni tra le azioni.

1. Mixed-Effect Thompson Sampling (meTS) - Capitolo 3

• Metodologia: Gli autori introducono un modello bayesiano gerarchico in cui i parametri delle azioni $\theta_a$ sono accoppiati attraverso $L$ parametri di effetto latente condivisi $\Psi = (\psi_\ell)_{\ell \in [L]}$. Il processo generativo assume $\theta_a | \Psi \sim p_0(\cdot|\Psi)$.
• Algoritmo: meTS esegue un campionamento gerarchico: prima campiona gli effetti globali $\Psi_t$ dalla loro distribuzione a posteriori, poi campiona i singoli parametri delle azioni $\theta_{t,a}$ condizionati da $\Psi_t$.
• Risultati Teorici: Per modelli lineari-gaussiani, gli autori derivano aggiornamenti a posteriori esatti in forma chiusa. Dimostrano un limite di regret bayesiano di $\tilde{O}(\sqrt{Td K_{eff}})$, dove $K_{eff}$ è il numero effettivo di azioni. Quando il numero di effetti $L \ll K$, allora $K_{eff} \ll K$, ottenendo un miglioramento moltiplicativo rispetto allo standard TS.
• Complessità: Il metodo riduce la complessità di memoria da $O(K^2d^2)$ a $O((L^2 + K)d^2)$ e il tempo di esecuzione da $O(K^3d^3)$ a $O((L^3 + K)d^3)$.
• Estensioni: Il framework viene esteso ai Modelli Lineari Generalizzati (GLM) utilizzando approssimazioni di Laplace trattabili.

2. Diffusion Thompson Sampling (dTS) - Capitolo 4

• Metodologia: Per catturare dipendenze non lineari più complesse tra le azioni, gli autori sostituiscono la struttura latente a singolo livello con una gerarchia profonda di variabili latenti governate da modelli di diffusione pre-addestrati. Il prior è definito come una catena di Markov di variabili latenti $\psi_L \to \dots \to \psi_1 \to \theta_a$ collegate da funzioni di link non lineari $f_\ell$.
• Algoritmo: dTS impiega una procedura di inferenza ricorsiva. Approssima la distribuzione a posteriori intrattabile mantenendo un "modello di diffusione a posteriori" dove le funzioni di link e le covarianze vengono aggiornate tramite aggiornamenti di tipo gaussiano (combinando la precisione del prior e la precisione dei dati) senza effettuare backpropagation attraverso la rete neurale.
• Risultati Teorici: In un contesto lineare-gaussiano, il limite di regret scala con il numero effettivo di azioni e la somma delle varianze attraverso i $L$ livelli. La complessità scala linearmente con $L$, ovvero $O((L+K)d^2)$, migliorando rispetto a meTS.
• Significato: Questo dimostra che i modelli generativi profondi possono essere utilizzati non solo per la rappresentazione, ma per strutturare l'incertezza necessaria per un'esplorazione efficiente.

Parte II: Apprendimento Off-Policy (Affrontare Stima e Ottimizzazione)

La tesi sfida il paradigma prevalente "centrato sulla stima" e propone tre approcci complementari.

1. Structured Direct Method (sDM) - Capitolo 6

• Metodologia: Analogamente a meTS, sDM introduce un vettore latente condiviso $\psi$ per accoppiare i parametri delle azioni nell'ambito offline. Calcola la distribuzione a posteriori sugli effetti latenti e le distribuzioni a posteriori condizionali per i parametri delle azioni.
• Risultati: Gli autori dimostrano che sDM raggiunge una convergenza $O(1/\sqrt{n})$ nella subottimalità bayesiana senza richiedere l'assunzione restrittiva di "pieno supporto di logging" (full logging support). Il limite dipende dall'allineamento tra la politica di logging e la politica ottimale.
• Intuizione: Sotto il criterio di subottimalità bayesiana considerato, si dimostra che le politiche greedy sono ottimali e possono superare le politiche pessimistiche, contrastando con i contesti frequentisti dove il pessimismo è spesso necessario.

2. L'Ottimizzazione Conta Più della Stima - Capitolo 7

• Metodologia: Gli autori dimostrano che, in spazi di azione grandi, l'errore di ottimizzazione domina l'errore di stima. Gli obiettivi standard basati su IPS inducono paesaggi non concavi che intrappolano gli ottimizzatori.
• Proposta: Invece di stimare il valore e poi ottimizzare, la tesi raccomanda obiettivi di Policy-Weighted Log-Likelihood (PWLL):
  $$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$$
• Risultati: Per politiche softmax lineari, gli obiettivi PWLL sono concavi (e fortemente concavi con regolarizzazione $\ell_2$), garantendo un massimo globale unico. Gli esperimenti su dataset con fino a un milione di azioni mostrano che questi obiettivi semplici e stabili superano costantemente i metodi basati sulla stima del valore più sofisticati.

3. Pessimismo Principiato per l'Exponential Smoothing - Capitolo 8

• Metodologia: Per affrontare la varianza di IPS, gli autori introducono stimatori di Exponential Smoothing (ES) differenziabili che interpolano tra assenza di regolarizzazione e forte riduzione della varianza.
• Teoria: Viene derivato un limite di generalizzazione PAC-Bayesiano a due lati per questi stimatori regolarizzati. Questo limite decompone l'errore in divergenza, bias di regolarizzazione e varianza residua.
• Applicazione: Il limite produce un obiettivo di apprendimento pessimistico, pienamente differenziabile, che può essere ottimizzato tramite salita del gradiente stocastico. Il framework è unificato per coprire altri regolarizzatori come il clipping e l'esplorazione implicita.
• Estensione: Gli autori introducono anche il Logarithmic Smoothing (LS), un'alternativa morbida e differenziabile al clipping che raggiunge limiti di concentrazione più stretti.

Risultati Sperimentali

I metodi proposti sono validati su dataset sintetici e reali:

• On-Policy: Nei bandit lineari e logistici sintetici, meTS e dTS superano significativamente i baseline (LinTS, GLM-TS, HierTS), con il divario di performance che aumenta all'aumentare dello spazio delle azioni $K$. Negli esperimenti MovieLens (sistemi di raccomandazione), meTS ottiene il regret più basso anche quando il modello di ricompensa reale è errato, dimostrando robustezza.
• Off-Policy:
  • sDM supera i metodi diretti standard, con guadagni che aumentano al crescere di $K$.
  • Gli obiettivi PWLL (Capitolo 7) superano costantemente i metodi basati su IPS all'avanguardia su dataset con fino a un milione di azioni, mostrando una superiore robustezza alla sintonizzazione degli iperparametri.
  • Gli obiettivi pessimistici PAC-Bayesiani (Capitolo 8) ottengono ricompense migliori rispetto ai baseline (inclusi London et al. e Sakhi et al.) attraverso varie qualità della politica di logging, particolarmente quando la politica di logging non è uniforme.

Significato e Rivendicazioni

La tesi sostiene di colmare il divario tra gli algoritmi teorici per i bandit e i vincoli dei moderni sistemi industriali (ad esempio, i sistemi di raccomandazione con milioni di articoli). Il suo argomento centrale è che scalare verso grandi spazi di azione richiede:

1. Strutturare l'Incertezza: Utilizzare prior gerarchici e basati sulla diffusione per condividere la forza statistica tra le azioni (On-Policy).
2. Rivalutare gli Obiettivi: Riconoscere che, in spazi grandi, la trattabilità del panorama di ottimizzazione è critica quanto l'accuratezza statistica dello stimatore (Off-Policy).
3. Pessimismo Differenziabile: Sviluppare obiettivi pessimistici teoricamente fondati, ma computazionalmente fattibili, che controllino varianza e bias senza dipendere da costanti intrattabili.

Il lavoro afferma che, allontanandosi dalla modellazione di azioni indipendenti e dalla standard stima del valore, i bandit contestuali possono essere efficacemente implementati in ambienti dove gli spazi di azione superano regolarmente le migliaia o i milioni.