Sintesi Tecnica: Bootstrap basato su Modello per Catene di Markov Controllate

Enunciato del Problema

Il lavoro affronta la sfida dell'inferenza statistica per Catene di Markov Controllate (CMC) finite in contesti in cui la politica di comportamento che genera i dati può essere non stazionaria o dipendente dalla storia. Questo scenario è prevalente nell'apprendimento per rinforzo (RL) offline, dove i dati sono raccolti da una politica $\pi_b$ sconosciuta che non soddisfa necessariamente le ipotesi di stazionarietà o di Markovianità.

I metodi di bootstrap esistenti per le catene di Markov spesso si basano sulla stazionarietà o su specifiche condizioni di mixing che non valgono per CMC generali con controlli dipendenti dalla storia. Inoltre, gli intervalli di confidenza (IC) standard basati sul metodo plug-in e derivati dai Teoremi del Limite Centrale (CLT) richiedono la stima della covarianza, il che può degradare le prestazioni su campioni finiti. Gli autori identificano due problemi aperti:

1. È possibile sviluppare un bootstrap basato su modello per CMC finite senza richiedere stazionarietà o Markovianità della politica di controllo?
2. È possibile stabilire la consistenza distribuzionale di un tale stimatore bootstrap e estenderlo a compiti RL a valle come la Valutazione Fuori Politica (OPE) e il Recupero della Politica Ottimale (OPR)?

Metodologia

Modello e Impostazione dei Dati

Gli autori considerano una CMC finita $\{(X_i, A_i)\}_{i \ge 0}$ con spazio degli stati $\mathcal{S}$ e spazio delle azioni $\mathcal{A}$. Il kernel di transizione è $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. Il dataset offline osservato $\mathcal{D}_n$ consiste di $K$ episodi di lunghezza fissa $T$ (dove $n=KT$), generati da una politica di comportamento $\pi_b$ sconosciuta. La politica $\pi_b$ può essere non stazionaria e dipendente dalla storia.

Da $\mathcal{D}_n$, gli autori calcolano:

• Stimatore empirico delle transizioni basato sui conteggi: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Politica di comportamento empirica: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Procedura di Bootstrap Basata su Modello

Il metodo proposto costruisce una CMC bootstrap $\{(X^*_i, A^*_i)\}_{i \ge 0}$ utilizzando il kernel di transizione empirico $\hat{M}$ e la politica di comportamento empirica $\hat{\pi}_b$.

1. Inizializzazione: Per ogni replica bootstrap $j$, il processo inizia dallo stato iniziale osservato dell'episodio originale, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulazione: Le transizioni sono generate sequenzialmente campionando le azioni $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ e i prossimi stati $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Stima: Dal dataset simulato $\mathcal{D}^*_n$, viene calcolato uno stimatore bootstrap delle transizioni $\hat{M}^*$.
4. Replicazione: Questo processo viene ripetuto $B$ volte per ottenere le repliche bootstrap $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$.

Applicazioni a Valle

Il bootstrap viene applicato a due target a valle:

• Valutazione Fuori Politica (OPE): Stima delle funzioni valore $V_\pi$ e delle funzioni Q $Q_\pi$ per una politica target fissa $\pi$ risolvendo le equazioni di Bellman con $\hat{M}$ e $\hat{M}^*$.
• Recupero della Politica Ottimale (OPR): Stima delle funzioni valore ottimali $V_\star$ e $Q_\star$ risolvendo le equazioni di Bellman ottimali con $\hat{M}$ e $\hat{M}^*$.

Gli intervalli di confidenza sono costruiti utilizzando i quantili empirici delle repliche bootstrap (IC percentili) o tramite metodi pivot.

Principali Contributi Teorici

1. Consistenza Distribuzionale del Bootstrap

Il lavoro stabilisce i primi risultati di consistenza distribuzionale per bootstrap basati su modello in CMC finite con politiche potenzialmente non stazionarie o dipendenti dalla storia.

• Regime a Singola Catena ($K=1, T \to \infty$): Il Teorema 1 dimostra che, condizionatamente ai dati $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ converge in distribuzione a un limite Gaussiano $N(0, \bar{\Lambda})$, corrispondente alla distribuzione asintotica dello stimatore originale $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Regime Episodico ($T$ fissato, $K \to \infty$): La Proposizione 1 estende questo risultato all'impostazione episodica incorporando gli episodi in una singola catena tramite pseudo-transizioni. Conferma che il bootstrap rimane consistente anche quando gli episodi sono separati da reset.

Strumenti Tecnici:

• Una nuova Legge dei Grandi Numeri (LLN) per il Bootstrap per i conteggi di visita ($N^*_s/n \to p_s$ q.c.).
• Una nuova applicazione del Teorema del Limite Centrale (CLT) per Martingale per gli incrementi delle transizioni bootstrap, utilizzando condizioni di mixing debole (Assunzioni 1–3) per gestire la struttura di dipendenza.

2. Validità per OPE e OPR

La Proposizione 2 estende la consistenza distribuzionale agli stimatori delle funzioni valore e Q utilizzando il Metodo Delta.

• Gli autori verificano la differenziabilità di Hadamard degli operatori di Bellman rispetto alla matrice a blocchi delle transizioni.
• Per l'OPE, le repliche bootstrap di $V_\pi$ e $Q_\pi$ convergono agli stessi limiti Gaussiani degli stimatori originali.
• Per l'OPR, sotto una condizione di non degenerazione (gap strettamente positivo tra azioni ottimali e subottimali), anche le repliche bootstrap di $V_\star$ e $Q_\star$ raggiungono la consistenza distribuzionale.

Risultati Sperimentali

Gli autori valutano le prestazioni su campioni finiti sul problema RiverSwim ($S=6, A=2$), un benchmark noto per l'esplorazione difficile a causa di frequenze di visita sbilanciate e politiche ottimali quasi degeneri.

• Impostazione: I confronti sono stati effettuati contro il bootstrap episodico (Hao et al., 2021) e gli IC basati su CLT plug-in (Zhu et al., 2024; Su et al., 2026) su varie dimensioni campionarie ($n$) e lunghezze degli episodi ($T$).
• Risultati:
  • Gli IC percentili del bootstrap basato su modello proposti superano sostanzialmente le linee di base, raggiungendo una copertura vicina al nominale (ad es. 0,48–0,54 per il 50%, 0,87–0,94 per il 90%, 0,92–0,97 per il 95%) in regimi ben campionati ($n \ge 500$).
  • Le linee di base (bootstrap episodico e CLT plug-in) mostrano una sottocopertura sistematica, in particolare a dimensioni campionarie piccole e lunghezze degli episodi brevi.
  • Il bootstrap episodico fallisce completamente a $n=50$ quando $T \ge 50$ (collassando a copertura zero) perché un singolo episodio elimina la variazione bootstrap.
  • Le prestazioni sono più deboli per le coppie stato-azione visitate raramente (vicino allo stato 6) e per orizzonti brevi ($T=10$), in linea con i vincoli teorici della normalità asintotica e della non degenerazione.

Significato e Limitazioni

Significato:
Il lavoro fornisce una solida fondazione teorica per l'uso di bootstrap basati su modello nell'RL offline, affrontando specificamente il gap in cui le politiche di comportamento sono non stazionarie o dipendenti dalla storia. Dimostra che tali bootstrap producono intervalli di confidenza asintoticamente validi sia per i kernel di transizione che per gli obiettivi RL a valle, senza richiedere una stima esplicita della covarianza.

Limitazioni e Direzioni Future (come stated dagli autori):

• Funzione di Ricompensa: L'analisi assume una funzione di ricompensa nota. Sebbene gli autori notino che la validità probabilmente vale se la stima della ricompensa converge, gli effetti su campioni finiti dell'errore di stima della ricompensa non sono analizzati.
• Spazio Stato-Azione: I risultati attuali sono limitati a spazi stato-azione finiti. L'estensione all'approssimazione di funzioni o a spazi continui è lasciata a lavori futuri.
• Regimi Asintotici: L'analisi episodica assume $T$ fissato e $K \to \infty$. La consistenza del bootstrap nel regime in cui $K$ è fissato ($K>1$) e $T \to \infty$ rimane una questione aperta.
• Politiche Non Stazionarie: Sebbene la teoria accolga politiche non stazionarie, gli esperimenti numerici hanno utilizzato principalmente politiche di comportamento stazionarie; sono suggeriti ulteriori esperimenti con politiche non stazionarie.