Riepilogo Tecnico: Apprendimento Online in MDP ad Albero Trattando le Politiche come Braccia di un Bandit

1. Definizione del Problema

Il documento affronta il problema dell'apprendimento online nei Processi Decisionali di Markov ad Albero (T-MDP). Un T-MDP è definito come un MDP a orizzonte finito in cui le transizioni di stato formano un albero radicato in uno stato iniziale $s_1$. Una caratteristica definitoria dei T-MDP è che ogni stato è raggiungibile da $s_1$ attraverso esattamente una traiettoria stato-azione.

Queste strutture sorgono naturalmente come astrazioni di giochi in forma estesa con memoria perfetta giocati contro avversari stazionari. L'obiettivo specifico dell'apprendimento è trovare una migliore risposta a un avversario sconosciuto ma stazionario attraverso interazioni ripetute nel gioco. L'agente non conosce le probabilità di transizione $p$ ma conosce la funzione di ricompensa $r$. L'agente interagisce con l'ambiente giocando episodi completi a partire da $s_1$, osservando le traiettorie e selezionando nuove politiche per gli episodi successivi.

Il documento indaga questo problema in due regimi:

1. PAC (Probabilmente Corretto in Approssimazione): L'obiettivo è produrre una politica $\pi$ tale che $V(\pi) \geq V(\pi^*) - \epsilon$ con probabilità almeno $1-\delta$, minimizzando il numero di episodi (complessità del campione).
2. Minimizzazione del Rimpianto: L'obiettivo è minimizzare il rimpianto cumulativo $R_T = \sum_{t=1}^T (V(\pi^*) - \mathbb{E}[V(\pi_t)])$ su $T$ episodi.

2. Metodologia

L'innovazione metodologica centrale consiste nel trattare ogni politica nel T-MDP come una braccia di un bandit. Sebbene questo approccio sia concettualmente semplice, il numero di politiche deterministiche è esponenziale rispetto al numero di stati ($|A|^{|S|}$), rendendo un'implementazione ingenua proibitiva dal punto di vista computazionale e della memoria.

Per superare ciò, gli autori propongono un framework in cui le politiche condividono dati basandosi sulla struttura ad albero dell'MDP.

2.1 Decomposizione del Valore

Gli autori stabiliscono che il valore di qualsiasi politica $\pi$, $V(\pi)$, può essere espresso come una combinazione convessa dei rendimenti terminali. Nello specifico, $V(\pi) = \sum_{\sigma \in X(\pi)} q(\sigma) \cdot \rho(\sigma)$, dove:

• $X(\pi)$ è l'insieme degli stati terminali coerenti con la politica $\pi$.
• $q(\sigma)$ è la probabilità di raggiungere lo stato terminale $\sigma$ da $s_1$ sotto $\pi$.
• $\rho(\sigma)$ è la ricompensa cumulativa scontata lungo il percorso verso $\sigma$.

Poiché la funzione di ricompensa è assunta nota, $\rho(\sigma)$ è noto. Il problema di apprendimento si riduce alla stima delle probabilità di transizione $q(\sigma)$ per gli stati terminali. Crucialmente, i dati per stimare $q(\sigma)$ possono essere raccolti giocando qualsiasi politica coerente con $\sigma$, non solo $\sigma$ stesso.

2.2 Limiti di Confidenza e Condivisione dei Dati

Il documento introduce un nuovo limite di confidenza per $V(\pi)$ che sfrutta la condivisione dei dati tra le politiche.

• Meccanismo di Conteggio: Per uno stato terminale $\sigma$, l'algoritmo traccia $n_t(\sigma)$, il numero di episodi in cui la politica giocata era coerente con $\sigma$, e $n_t^+(\sigma)$, il numero di volte in cui $\sigma$ è stato effettivamente raggiunto.
• Conteggio delle Politiche: Per una politica $\pi$, il "conteggio di gioco" $n_t(\pi)$ è definito come $\min_{\sigma \in X(\pi)} n_t(\sigma)$. Questo rappresenta la disponibilità di dati colli di bottiglia per la valutazione di $\pi$.
• Stimatore: Il valore empirico $\hat{V}_t(\pi)$ è uno stimatore non distorto costruito dalle probabilità empiriche $\hat{q}_t(\sigma) = n_t^+(\sigma) / n_t(\sigma)$.

2.3 Fondamento Teorico: Dipendenza Negativa dei Cilindri

Una sfida tecnica significativa è che le variabili casuali utilizzate per stimare $V(\pi)$ (esiti Bernoulli del raggiungimento degli stati terminali) sono dipendenti perché più politiche possono essere giocate nello stesso episodio.

• Gli autori dimostrano che queste variabili esibiscono Dipendenza Negativa dei Cilindri (NCD).
• Introducono "variabili gemelle" (variabili Bernoulli indipendenti con le stesse medie) per limitare la deviazione dello stimatore dipendente.
• Utilizzando la Disuguaglianza di Bernstein su queste variabili gemelle, derivano limiti di confidenza (UCB e LCB) che valgono con alta probabilità. Ciò permette l'applicazione di algoritmi bandit (Lucb e Ucb) all'insieme esponenziale di politiche con solo memoria e computazione polinomiale per passo.

2.4 Algoritmi

Gli autori adattano due algoritmi bandit standard:

1. Lucb-T: Un adattamento dell'algoritmo Lucb per il regime PAC. Seleziona iterativamente la politica con la stima di valore più alta e la politica con il limite di confidenza superiore (UCB) più alto tra le restanti, giocandole finché non sono separate da $\epsilon$.
2. Ucb-T: Un adattamento dell'algoritmo Ucb per la minimizzazione del rimpianto. Seleziona la politica con il limite di confidenza superiore (UCB) più alto in ogni episodio.

Entrambi gli algoritmi utilizzano una procedura chiamata PU (Politica con UCB più alto) per calcolare efficientemente la politica massimizzante in tempo $O(|S||A||k_{max}| + |\Sigma|)$, evitando la necessità di enumerare tutte le politiche.

3. Contributi Chiave

1. Risultato Analitico: Una nuova disuguaglianza di concentrazione (Teorema 2) che stabilisce limiti di confidenza per i valori delle politiche nei T-MDP. Questo risultato gestisce la dipendenza tra i dati condivisi dalle politiche e potrebbe avere una più ampia applicabilità all'apprendimento in compiti sequenziali.
2. Progettazione Algoritmica: Algoritmi concettualmente semplici (Lucb-T e Ucb-T) che trattano le politiche come braccia di un bandit ma sfruttano la struttura ad albero per un'implementazione efficiente.
3. Garanzie Teoriche:
   • Complessità del Campione (Teorema 9): Un limite superiore dipendente dall'istanza per Lucb-T che somma un "termine di gap" sugli stati terminali ($\sum_{\sigma \in \Sigma} \frac{1}{(\Delta^\epsilon_\sigma)^2}$) piuttosto che sulle politiche.
   • Limite del Rimpianto (Teorema 10): Un limite superiore dipendente dall'istanza per Ucb-T, anch'esso sommato sugli stati terminali.
4. Validazione Empirica: Implementazione e test su tre giochi a informazione imperfetta di scale variabili: Kuhn Poker (piccolo), Leduc Poker (medio) e Reconnaissance Blind Tic-Tac-Toe (RBT, grande, con milioni di stati).

4. Risultati

• Scalabilità: Gli algoritmi proposti superano costantemente le alternative disponibili (come Lucb vanilla, Bpi-Ucrl, Mdp-GapE, Mccfr e Uct) all'aumentare della dimensione del problema.
• Efficienza della Condivisione dei Dati: Su problemi piccoli (Kuhn Poker a 3 carte), Lucb vanilla (senza condivisione di dati) è competitivo. Tuttavia, su varianti più grandi (Kuhn Poker a 5 carte, Leduc, RBT), le varianti "ad albero" (Lucb-T, Ucb-T) superano significativamente le baseline senza condivisione, dimostrando la necessità della condivisione dei dati per la scalabilità.
• Prestazioni su RBT: Gli algoritmi gestiscono con successo RBT, un gioco con fino a $2 \times 10^7$ stati, dove altri algoritmi PAC (Bpi-Ucrl, Mdp-GapE) non sono riusciti a performare bene.
• Teoria vs Pratica: Gli esperimenti evidenziano lacune tra i limiti teorici e le prestazioni pratiche, in particolare nel regime PAC dove i tempi di arresto possono essere proibitivamente grandi, suggerendo che, sebbene gli algoritmi siano teoricamente solidi, un'adeguata regolazione pratica è essenziale.

5. Significato e Affermazioni

Il documento afferma che il suo contributo primario è la generalizzazione di algoritmi bandit ben noti (Lucb e Ucb) ai T-MDP trattando le politiche come braccia. Il significato risiede in:

• Superamento della Complessità Esponenziale: Dimostrare che si può ottenere una complessità di memoria e computazione polinomiale nonostante il numero esponenziale di politiche, sfruttando la struttura ad albero per condividere i dati.
• Limiti Dipendenti dall'Istanza: Fornire garanzie teoriche che dipendono dal "gap" agli stati terminali piuttosto che dal numero totale di politiche, offrendo un'analisi più raffinata rispetto ai limiti nel caso peggiore.
• Applicabilità Pratica: Validare l'approccio su giochi a informazione imperfetta su larga scala (in particolare RBT), che servono come benchmark per la fattibilità dell'apprendimento di migliori risposte in problemi complessi di decisione sequenziale contro avversari fissi.

Gli autori notano che la loro assunzione di una funzione di ricompensa nota è ragionevole per il loro dominio motivante (giochi a informazione imperfetta) ma è una restrizione rispetto agli MDP generali in cui le ricompense possono essere sconosciute. Riconoscono inoltre che, sebbene i loro limiti evitino la dipendenza dalle probabilità di visita degli stati (che possono essere arbitrariamente piccole negli MDP generali), questo è un vantaggio specifico della struttura T-MDP e delle ricompense note.