Riepilogo Tecnico: Apprendimento Off-Policy Sequenziale con Smoothing Logaritmico

Enunciato del Problema

L'apprendimento off-policy consente l'addestramento di politiche a partire da dati di interazione registrati generati da una politica di comportamento. Sebbene le fondamenta teoriche dell'apprendimento off-policy siano ben consolidate nell'ambito batch (dove una singola politica viene appresa da un dataset statico generato da una politica di comportamento), i sistemi del mondo reale operano in modo diverso. Nella pratica, le politiche vengono aggiornate e ridistribuite ripetutamente in modo sequenziale: una politica viene addestrata su tutti i dati storici, distribuita per generare nuove interazioni e quindi riaddestrata sul dataset espanso per la successiva iterazione.

Nonostante l'ubiquità di questo paradigma sequenziale in applicazioni come i sistemi di raccomandazione e la collocazione degli annunci pubblicitari, esso rimane largamente inesplorato a livello teorico. Gli approcci sequenziali esistenti spesso si basano su assunzioni forti, come la copertura uniforme dello spazio delle azioni o strategie di raccolta dati irrealistiche (ad esempio, dimensioni dei batch che crescono esponenzialmente). Inoltre, gli attuali algoritmi offline all'avanguardia, che utilizzano il principio del pessimismo e i framework PAC-Bayesiani, non sono stati estinti con successo al contesto sequenziale con garanzie di convergenza rigorose. Questo articolo colma il divario tra la distribuzione sequenziale pratica e le garanzie teoriche, mirando a sviluppare algoritmi di apprendimento off-policy sequenziale che siano sia teoricamente solidi che empiricamente efficaci.

Metodologia

Gli autori propongono un framework basato sui Banditi Contestuali, in cui un agente interagisce con un flusso di dati nel tempo, agli istanti $k \geq 0$. Ad ogni passo, una nuova politica di comportamento $\pi_k$ viene distribuita per raccogliere un batch di dati $S_k$, e l'agente aggiorna la propria politica utilizzando la storia cumulativa $S_{0:k}$.

La metodologia si fonda su due principali contributi algoritmici, entrambi che sfruttano strumenti di apprendimento PAC-Bayesiano Online e stimatori di Smoothing Logaritmico (LS):

1. Smoothing Logaritmico Sequenziale (Algoritmo 1)

Il primo contributo estende lo stimatore offline di Smoothing Logaritmico (introdotto da Sakhi et al., 2024) al contesto sequenziale.

• Stimatore: L'algoritmo utilizza il regolarizzatore LS standard $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$.
• Meccanismo: Ad ogni passo $k$, l'algoritmo minimizza un limite superiore PAC-Bayesiano sul rischio, combinando il rischio LS empirico su tutti i dati accumulati $S_{0:k}$ e un termine di divergenza KL rispetto a una distribuzione a priori $P$.
• Garanzia Teorica: Il Teorema 3.2 stabilisce un limite di generalizzazione per l'output sequenziale $\pi_{k+1}$. Il tasso di convergenza risulta essere $O(1/\sqrt{N_k})$, dove $N_k$ è il numero totale di campioni. Questo corrisponde al tasso ottimale del contesto batch ma si applica all'accumulo sequenziale di dati.
• Limitazione: Gli autori identificano che il termine di pseudo-varianza nel limite di convergenza non si annulla nemmeno se la politica di comportamento si avvicina alla politica ottimale, portando a un tasso di convergenza che non accelera oltre $O(1/\sqrt{N_k})$.

2. Smoothing Logaritmico Sequenziale Aggiustato (Algoritmo 2)

Per superare la lenta convergenza dell'Algoritmo 1, gli autori introducono un nuovo stimatore di Smoothing Logaritmico Aggiustato (AdjLS).

• Stimatore: Viene definito un nuovo regolarizzatore: $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. Questo aggiustamento modifica l'obiettivo di prestazione per controllare la differenza tra il rischio della politica corrente e una media ponderata dei rischi passati.
• Meccanismo: L'Algoritmo 2 minimizza lo stimatore di rischio aggiustato sui dati cumulativi.
• Garanzia Teorica: Il Teorema 4.4 dimostra che, sotto assunzioni lievi (nello specifico, che le azioni ottimali siano coperte dalla classe di politiche e che il problema abbia un certo grado di separabilità, quantificato da $\Delta_u > 0$), l'Algoritmo 2 raggiunge un tasso di convergenza accelerato di $O(1/N_k^\alpha)$ per qualsiasi $\alpha \in [0.5, 1)$.
• Insight Chiave: A differenza dello stimatore LS standard, il termine di errore dello stimatore aggiustato $L(\pi^*, \pi_j)$ si annulla man mano che la politica di comportamento $\pi_j$ si avvicina alla politica ottimale $\pi^*$, consentendo una convergenza più rapida.

Contributi Chiave

1. Primi Algoritmi PAC-Bayes Sequenziali: L'articolo presenta i primi algoritmi off-policy PAC-Bayesiani progettati specificamente per il contesto sequenziale, fornendo garanzie di convergenza teorica che interpolano tra regimi completamente batch e completamente online.
2. Convergenza Accelerata tramite Aggiustamento: Gli autori identificano una limitazione fondamentale nell'applicazione sequenziale di stimatori offline standard e propongono un aggiustamento principiale (AdjLS) che produce tassi di convergenza accelerati dimostrabilmente sotto assunzioni ragionevoli.
3. Assunzioni Rilassate: L'analisi teorica richiede solo che la classe di politiche copra le azioni ottimali (Assunzione 3.4), che è strettamente più debole delle assunzioni di copertura uniforme richieste dai lavori sequenziali precedenti (ad esempio, Zenati et al., 2023).
4. Generalizzazione a Contesti Non-IID: Il framework si dimostra adattabile ad ambienti non stazionari dove le distribuzioni dei contesti evolvono nel tempo, rilassando l'assunzione di i.i.d. sui contesti.

Risultati Empirici

Gli autori valutano i loro metodi su dataset standard multiclasse (MNIST, FashionMNIST, EMNIST, CIFAR100) convertiti in problemi di banditi contestuali.

• Sequenziale vs Batch: Gli esperimenti dimostrano che aumentare il numero di aggiornamenti intermedi della politica ($k$) migliora costantemente le prestazioni della politica finale rispetto a un singolo aggiornamento batch ($k=1$). Ciò convalida il beneficio del framework sequenziale.
• Confronto tra Algoritmi:
  • SeqAdjLS (Algoritmo 2) supera costantemente SeqLS (Algoritmo 1), confermando il vantaggio teorico dello stimatore aggiustato.
  • Entrambi i metodi proposti superano significativamente SCRM (Minimizzazione del Rischio Controfattuale Sequenziale, Zenati et al., 2023). Gli autori notano che SCRM tende a essere eccessivamente conservativo, specialmente nei round iniziali con dimensioni dei batch ridotte, e si basa su strategie di raccolta dati irrealistiche (batch a crescita esponenziale) che scartano i dati storici.
• Impatto della Politica Iniziale: L'approccio sequenziale mostra guadagni sostanziali quando la politica di comportamento iniziale è lontana dall'ottimo, in particolare negli spazi delle azioni ad alta dimensionalità (ad esempio, CIFAR100 con 100 azioni).

Significato e Affermazioni

L'articolo afferma di colmare il divario teorico tra l'apprendimento off-policy sequenziale pratico e le garanzie rigorose. Combinando tecniche PAC-Bayes online con un nuovo stimatore di smoothing logaritmico, gli autori forniscono algoritmi che:

• Generalizzano gli approcci offline all'avanguardia (eguagliandone le prestazioni nel limite batch).
• Accelerano l'apprendimento nei contesti sequenziali sfruttando il raffinamento progressivo della politica di comportamento.
• Evitano assunzioni irrealistiche (come la copertura uniforme) che ostacolano l'applicabilità dei metodi sequenziali esistenti.

Gli autori sottolineano che, sebbene la loro analisi teorica si basi sulla copertura delle azioni ottimali da parte della classe di politiche, questo rappresenta un rilassamento significativo rispetto ai lavori precedenti. Concludono che la combinazione di PAC-Bayes online e banditi contestuali sequenziali offre una direzione promettente per un apprendimento robusto ed efficiente in sistemi dinamici del mondo reale.