Sintesi Tecnica: Apprendimento di una Politica da una Singola Traiettoria in un MDP a Ricompensa Media

Definizione del Problema

Il documento affronta la sfida di trovare una politica $\epsilon$-ottimale in MDP a ricompensa media (average-reward MDPs) utilizzando garanzie di complessità campionaria finita derivate da una singola traiettoria.

Mentre esiste una vasta letteratura sulla complessità campionaria per gli MDP a ricompensa cumulativa scontata (discounted), le analisi per gli MDP a ricompensa media si sono storicamente basate su ipotesi restrittive. I lavori esistenti richiedono tipicamente uno dei seguenti requisiti:

1. Modelli generativi (accesso a un simulatore in grado di resettare in qualsiasi stato).
2. Dati offline i.i.d. (indipendenti e identicamente distribuiti).
3. Forti assunzioni strutturali, come l'ergodicità (dove ogni politica induce una singola classe ricorrente) o specifiche condizioni di copertura sulla politica di comportamento.

Il vuoto specifico che questo lavoro mira a colmare è l'ambiente debolmente comunicante (weakly communicating). Negli MDP debolmente comunicanti, lo spazio degli stati si decompone in una singola classe ricorrente e un insieme di stati transienti sotto qualsiasi politica "ben comportata", ma il sistema non è necessariamente ergodico (esistono stati transienti). Prima di questo lavoro, l'analisi della complessità campionaria finita per l'RL a ricompensa media da una singola traiettoria in questo contesto non era stata esplorata.

Metodologia

Gli autori sviluppano un framework teorico e nuovi algoritmi model-free che sfruttano le proprietà strutturali degli MDP debolmente comunicanti, specificamente la classificazione ricorrente-transiente degli stati.

1. Analisi Strutturale delle Singole Traiettorie

Il nucleo del contributo tecnico è l'analisi stocastica di una singola traiettoria generata da una politica di comportamento $\pi_b$. Gli autori stabiliscono che:

• Invarianza Ricorrente-Transiente: Per le politiche nell'interno dello spazio delle politiche ($\Pi_+$), la classificazione degli stati in una singola classe ricorrente ($R$) e un insieme transiente ($T$) è invariante e determinata esclusivamente dal kernel di transizione $P$, non dalla specifica scelta della politica.
• Uscita dagli Stati Transienti: Utilizzando la disuguaglianza di Markov e la proprietà di Markov forte, dimostrano che una traiettoria che parte da uno stato transiente raggiungerà la classe ricorrente $R$ entro un tempo di hitting ($t_{hit}$) finito con alta probabilità.
• Copertura della Classe Ricorrente: Una volta in $R$, la traiettoria copre tutti gli stati in $R$ entro un tempo di copertura ($t_{cov}$) finito.
• Campionamento i.i.d. tramite Tempi di Arresto: Utilizzando i tempi di arresto (specificamente, i tempi in cui la traiettoria ritorna in uno stato specifico $s$), gli autori dimostrano che i campioni da una singola traiettoria possono essere trattati come indipendenti e identicamente distribuiti (i.i.d.) ai fini delle disuguaglianze di concentrazione (Lemma 2.3). Ciò risolve i problemi di dipendenza inerenti all'analisi di singola traiettoria senza richiedere assunzioni sul tempo di mixing.

2. Metodo Basato sul Valore: SAVIC

Stochastic Anchored Value Iteration (SAVIC) è un algoritmo model-free basato sul valore progettato per MDP debolmente comunicanti. Opera in tre fasi:

1. Identificazione degli Stati Ricorrenti: L'agente esegue una politica di comportamento per uscire dagli stati transienti e raccogliere un elenco di tutti gli stati ricorrenti ($R$) utilizzando l'Algoritmo 1 (RECUR).
2. Iterazione Ancorata con Riduzione della Varianza: All'interno della classe ricorrente, l'algoritmo esegue la Anchored Value Iteration (Anc-QI). A differenza della standard VI, Anc-QI calcola l'iterata successiva come una combinazione convessa dell'aggiornamento di Bellman e del punto iniziale ($Q_0$). Questo termine di "ancora" garantisce la convergenza non asintotica.
   • Per ottenere una complessità campionaria efficiente, il metodo impiega una tecnica di campionamento ricorsivo. Invece di stimare l'intero operatore di Bellman $T(Q_k)$ ad ogni passo, stima la differenza $T(Q_k) - T(Q_{k-1})$ utilizzando un campionamento con riduzione della varianza.
3. Perturbazione della Politica: Poiché l'algoritmo ottimizza solo sulla classe ricorrente $R$, la politica finale viene perturbata per garantire che sia $\epsilon$-ottimale su l'intero spazio degli stati $S$, inclusi gli stati transienti.

3. Metodo Model-Free senza Conoscenza Previa: SAVIC+

Per gli MDP comunicanti (dove $S=R$, ovvero non ci sono stati transienti), gli autori introducono SAVIC+.

• Questa variante elimina la necessità di conoscenza pregressa di costanti dipendenti dal problema (come $t_{hit}$, $t_{cov}$ o la probabilità minima della distribuzione stazionaria $d_{min}$).
• Impiega un trucco del raddoppio (doubling trick) e una regola di arresto esplicita basata sull'errore empirico del residuo di Bellman ($\|Q - TQ\|_{sp}$).
• Utilizza l'Algoritmo 4 (SAMPLE+) per raccogliere automaticamente campioni finché non viene raggiunto un conteggio sufficiente per ogni coppia stato-azione.

4. Metodo Basato sulla Politica: SCPMA

Stochastic $\alpha$-clipped Policy Mirror Ascent (SCPMA) è un metodo di gradiente di politica per MDP debolmente comunicanti.

• Utilizza un nuovo algoritmo di valutazione della politica (SAVIPE) che approssima la funzione valore stato-azione utilizzando gli stessi meccanismi di ancoraggio e riduzione della varianza di SAVIC.
• L'aggiornamento della politica segue il framework Policy Mirror Ascent ma applica l'$\alpha$-clipping per garantire che la politica rimanga nell'interno dello spazio delle politiche ($\Pi_\alpha$). Questo clipping è cruciale per limitare i coefficienti nell'analisi della complessità campionaria.
• Il metodo supporta sia step size costanti che adattivi.

Risultati Chiave

Il documento stabilisce le prime garanzie di complessità campionaria finita per MDP a ricompensa media da una singola traiettoria in contesti debolmente comunicanti.

1. SAVIC (Basato sul Valore):

   • Raggiunge una complessità campionaria di $\tilde{O}(1/\epsilon^2)$ per trovare una politica $\epsilon$-ottimale.
   • Il limite dipende dal tempo di hitting ($t_{hit}$), dal tempo di copertura ($t_{cov}$), dall'ampiezza (span) della funzione valore ottimale ($\|Q^*\|_{sp}$) e dall'inverso della probabilità minima della distribuzione stazionaria ($1/d_{min}^\pi$).

2. SAVIC+ (Model-Free, Senza Conoscenza Previa):

   • Per gli MDP comunicanti, SAVIC+ raggiunge una complessità campionaria di $\tilde{O}(1/\epsilon^2)$.
   • Fondamentalmente, non richiede alcuna conoscenza pregressa di quantità dipendenti dal problema (come $t_{cov}$ o $d_{min}$) per impostare i parametri.

3. SCPMA (Basato sulla Politica):

   • Raggiunge una complessità campionaria di $\tilde{O}(1/\epsilon^4)$ (con step size costante) o tassi migliorati con step size adattivi.
   • Questo rappresenta la prima garanzia di complessità campionaria finita per i metodi di gradiente di politica in MDP debolmente comunicanti da una singola traiettoria.

Significato e Rivendicazioni

Gli autori affermano che questo lavoro fornisce le prime garanzie di complessità campionaria finita per l'apprendimento in MDP a ricompensa media da una singola traiettoria nel setting debolmente comunicante.

• Rottura delle Assunzioni di Ergodicità: A differenza dei lavori precedenti che richiedevano l'ergodicità (dove tutti gli stati sono ricorrenti), questo lavoro gestisce il caso più generale debolmente comunicante dove esistono stati transienti.
• Realismo della Singola Traiettoria: I risultati vanno oltre le assunzioni irrealistiche di modelli generativi o dati i.i.d., fornendo garanzie per lo standard setting di apprendimento online dove un agente interagisce sequenzialmente con l'ambiente.
• Efficienza Model-Free: I metodi proposti sono model-free e, nel caso di SAVIC+, non richiedono la conoscenza pregressa delle proprietà di mixing dell'MDP o della distribuzione stazionaria, rendendoli più pratici per ambienti sconosciuti.
• Strumentazione Teorica: Il documento introduce nuovi strumenti teorici, tra cui l'uso di tempi di arresto e proprietà di Markov forte per generare campioni i.i.d. da una singola traiettoria in MDP debolmente comunicanti, consentendo l'applicazione di disuguaglianze di concentrazione precedentemente riservate ai setting i.i.d.

Il documento conclude osservando che, sebbene il metodo basato sul valore raggiunga un limite più stretto di $\tilde{O}(1/\epsilon^2)$ rispetto al $\tilde{O}(1/\epsilon^4)$ del metodo basato sulla politica, colmare questo divario ed estendere questi risultati all'approssimazione di funzione parametrizzata rimangono direzioni future aperte.