Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Sintesi Tecnica: Raggiungere la Complessità Campionaria $\tilde{O}(\epsilon^{-2})$ per Actor-Critic a Ciclo Singolo sotto Assunzioni Minime

Enunciato del Problema
L'apprendimento per rinforzo (RL) mira a risolvere i Processi Decisionali di Markov (MDP) attraverso metodi basati sui dati. Mentre i metodi nello spazio dei valori, come il Q-learning, hanno stabilito una complessità campionaria di $\tilde{O}(\epsilon^{-2})$ sotto assunzioni minime (specificamente, l'esistenza di una politica di comportamento irriducibile), i metodi nello spazio delle politiche, come l'actor-critic, sono storicamente rimasti indietro per quanto riguarda le garanzie teoriche. Le analisi esistenti degli algoritmi actor-critic che raggiungono una complessità di $\tilde{O}(\epsilon^{-2})$ fanno tipicamente affidamento su due condizioni restrittive:

1. Implementazioni a loop annidati: Dove il critic aggiorna più volte mentre l'actor rimane fisso, una struttura distinta dagli algoritmi pratici a ciclo singolo.
2. Assunzioni forti, dipendenti dall'algoritmo: Come richiedere che tutte le politiche incontrate durante la traiettoria dell'algoritmo (o l'intera classe di politiche) inducano catene di Markov irriducibili e aperiodiche con tassi di mescolamento e proprietà di esplorazione uniformemente limitati.

Queste assunzioni creano una dipendenza circolare: verificare le proprietà di mescolamento richiede il controllo della sequenza di politiche generata dall'algoritmo, che è proprio l'oggetto dell'analisi di convergenza. Inoltre, gli algoritmi actor-critic pratici operano in modalità a ciclo singolo e singola scala temporale con apprendimento off-policy, dove il critic traccia una politica target variabile nel tempo. Ciò introduce sfide riguardanti equazioni di aggiornamento accoppiate e iterati potenzialmente illimitati a causa del campionamento per importanza, che i quadri teorici esistenti faticano ad affrontare senza assunzioni forti.

Metodologia
Gli autori propongono un algoritmo actor-critic off-policy a ciclo singolo e singola scala temporale, dove l'actor e il critic vengono aggiornati simultaneamente ad ogni iterazione. L'actor impiega aggiornamenti incrementali verso una politica target $\tilde{\pi}_t$ derivata tramite iterazione di politica approssimata (API) o gradiente di politica naturale (NPG), mentre il critic esegue l'apprendimento per differenza temporale (TD) off-policy. Gli autori considerano due varianti del critic:

• Campionamento per Importanza (IS): Corrisponde lo squilibrio di distribuzione utilizzando un rapporto di peso per importanza.
• Differenza Temporale Attesa (ETD): Calcola direttamente la funzione Q attesa al prossimo stato, evitando pesi per importanza espliciti.

L'innovazione tecnica centrale risiede nel quadro di analisi. Per gestire l'accoppiamento tra gli aggiornamenti dell'actor e del critic e la natura illimitata degli iterati off-policy, gli autori impiegano un quadro di deriva di Lyapunov accoppiato.

1. Funzioni di Lyapunov: Costruiscono funzioni di Lyapunov separate per l'actor ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) e per il critic ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$).
2. Disuguaglianze di Deriva: Stabiliscono disuguaglianze di deriva negativa per entrambe le funzioni. Crucialmente, queste disuguaglianze contengono termini incrociati che rappresentano l'errore del sistema accoppiato (ad esempio, l'errore del critic che appare nella deriva dell'actor e viceversa).
3. Sovra-dominio Incrociato: L'analisi si basa su una proprietà di "sovradosaggio incrociato". Selezionando attentamente i rapporti dei passi di apprendimento e assicurando che i termini di errore di accoppiamento siano dominati dai termini di deriva negativa dei rispettivi sistemi, gli autori combinano le due disuguaglianze di deriva in un'unica ricorrenza per $V_t + W_t$. Questo approccio è ispirato dalla teoria del piccolo guadagno nei sistemi dinamici, ma qui è adattato per gestire il rumore markoviano, i target variabili nel tempo e gli iterati illimitati in modo unificato.

Contributi e Risultati Chiave
Il lavoro stabilisce i primi tassi di convergenza all'ultima iterazione per un algoritmo actor-critic a ciclo singolo che raggiunge una complessità campionaria $\tilde{O}(\epsilon^{-2})$ sotto assunzioni minime.

• Assunzioni Minime: L'unica assunzione richiesta è l'esistenza di una politica che induca una catena di Markov irriducibile sullo spazio degli stati. Questa politica non deve essere visitata dall'algoritmo, né l'algoritmo deve controllare le proprietà di mescolamento delle politiche che genera. Ciò si contrappone ai lavori precedenti che richiedevano ergodicità uniforme su tutta la traiettoria o sull'intera classe di politiche.
• Complessità Campionaria: Sotto questa assunzione minima, l'algoritmo raggiunge una complessità campionaria di $\tilde{O}(\epsilon^{-2})$ per trovare una politica $\epsilon$-ottimale. Questo tasso è quasi minimax-ottimale rispetto a $\epsilon$.
• Schemi di Passo di Apprendimento: I risultati valgono per sequenze di passi di apprendimento costanti, armoniche e polinomiali. Nello specifico, l'uso di passi di apprendimento armonici con parametri appropriati produce il tasso ottimale.
• Varianti dell'Algoritmo: L'analisi copre sia i critic basati su IS che quelli basati su ETD. Sebbene entrambi raggiungano lo stesso ordine di complessità, la variante ETD mostra una dipendenza più lieve dai parametri del problema (dimensione dello spazio degli stati $n$, dimensione dello spazio delle azioni $m$ e fattore di sconto $\gamma$) perché evita la stocasticità aggiuntiva introdotta dai rapporti di campionamento per importanza.
• Iterati Illimitati: Il quadro gestisce con successo gli iterati potenzialmente illimitati indotti dall'apprendimento off-policy (in particolare con IS), una sfida che spesso necessitava di forti assunzioni di limitatezza nella letteratura precedente.

Significato e Affermazioni
Gli autori affermano che questo lavoro colma un significativo divario teorico tra i metodi nello spazio dei valori e quelli nello spazio delle politiche. Dimostrando che i metodi actor-critic possono raggiungere una complessità campionaria minimax-ottimale senza loop annidati o forti assunzioni di mescolamento dipendenti dall'algoritmo, il lavoro sfida la nozione secondo cui i metodi nello spazio delle politiche sono intrinsecamente meno efficienti dal punto di vista del campionamento o richiedono condizioni più forti.

Il quadro analitico basato sulla deriva di Lyapunov accoppiata e sul sovra-dominio incrociato è presentato come un contributo di interesse indipendente, potenzialmente applicabile ad altri algoritmi iterativi accoppiati con iterati illimitati. Il lavoro nota esplicitamente che, sebbene la dipendenza da $\epsilon$ sia quasi ottimale, la dipendenza dalle costanti specifiche del problema ($n, m, (1-\gamma)^{-1}$) potrebbe essere subottimale rispetto ai metodi basati sui valori, suggerendo che le tecniche di riduzione della varianza potrebbero essere una direzione per futuri miglioramenti. Il lavoro evita di fare affermazioni su impostazioni di approssimazione di funzioni (la "triade mortale") o su applicazioni empiriche specifiche, concentrandosi rigorosamente sull'impostazione tabellare e sulle garanzie teoriche.