Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs

Sintesi Tecnica: Convergenza Lineare Globale del Gradiente di Politica Softmax con Regularizzazione di Entropia Oltre gli MDP Tabulari

Enunciato del Problema
Questo articolo indaga le proprietà di convergenza globale dei metodi del gradiente di politica (PG) per processi decisionali di Markov (MDP) a orizzonte infinito con regularizzazione di entropia, dotati di spazi di stato e azione continui. Sebbene la regularizzazione di entropia (introducendo un termine di divergenza KL con intensità $\tau > 0$) sia nota per migliorare il paesaggio di convergenza delle politiche softmax negli ambienti tabulari (con $S$ e $A$ finiti), estendere tali garanzie agli spazi continui con approssimazione di funzione rimane una sfida teorica significativa.

Nello specifico, gli autori considerano politiche softmax log-lineari definite da:
$$\pi_\theta(da|s) \propto \exp(\langle \theta, g(s, a) \rangle) \mu(da)$$
dove $g: S \times A \to \mathbb{R}^p$ rappresenta una base di caratteristiche, $\theta \in \mathbb{R}^p$ sono i parametri e $\mu$ è una misura di riferimento. L'obiettivo è minimizzare la funzione valore regolarizzata $V^\pi_\tau(\rho)$. La difficoltà principale risiede nella non convessità dell'obiettivo rispetto a $\theta$, anche con la regularizzazione di entropia, e nella potenziale degenerazione della Matrice di Informazione di Fisher (FIM) o delle matrici di covarianza delle caratteristiche negli ambienti continui, che può impedire che le dimostrazioni di convergenza standard siano valide.

Metodologia
L'analisi si basa su una formulazione del flusso di gradiente in tempo continuo:
$$\frac{d}{dt}\theta_t = -\nabla_\theta V^{\pi_{\theta_t}}_\tau(\rho)$$
La strategia di dimostrazione procede in tre fasi principali:

1. Disuguaglianza Non Uniforme di Polyak–Łojasiewicz (PŁ):
   Gli autori stabiliscono innanzitutto una disuguaglianza PŁ non uniforme della forma:
   $$V^{\pi_\theta}_\tau(\rho) - V^{\pi^*_\tau}_\tau(\rho) \leq C(\theta) \|\nabla_\theta V^{\pi_\theta}_\tau(\rho)\|^2$$
   Questa disuguaglianza collega il gap di subottimalità al quadrato della norma del gradiente. Crucialmente, la costante $C(\theta)$ dipende dalla geometria della politica, in particolare dal più piccolo autovalore della FIM (o di una matrice di covarianza delle caratteristiche non centrata per caratteristiche del simpletto) e dai limiti di densità della politica. A differenza del caso tabulare, dove $C$ può essere uniforme, qui $C(\theta)$ è non uniforme e potrebbe teoricamente degenerare al tendere di $\|\theta\|$ all'infinito.

2. Assunzione di Realizzabilità Q$\pi_\tau$:
   L'analisi assume che per qualsiasi politica $\pi$, la funzione valore stato-azione regolarizzata $Q^\pi_\tau$ possa essere rappresentata esattamente dalla base lineare di caratteristiche:
   $$\langle \theta(\pi), g(s, a) \rangle = -\frac{1}{\tau} Q^\pi_\tau(s, a)$$
   Questa assunzione garantisce che la politica ottima $\pi^*_\tau$ giaccia all'interno della classe parametrizzata, ovvero $\pi^*_\tau = \pi_{\theta^*}$ per un certo $\theta^*$.

3. Analisi di Lyapunov e Non Limitatezza Radiale:
   Per dimostrare la convergenza lineare globale, gli autori devono mostrare che la costante non uniforme $C(\theta_t)$ rimane limitata lungo la traiettoria del flusso di gradiente. Ciò richiede di dimostrare che la traiettoria $\{\theta_t\}$ rimane in un insieme compatto.

   • Utilizzano l'obiettivo regolarizzato $V^{\pi_\theta}_\tau(\rho)$ come funzione di Lyapunov, notando che essa decresce monotonicamente.
   • Dimostrano che, sotto condizioni specifiche sulla base di caratteristiche $g$, il termine di divergenza KL $KL(\pi_\theta | \mu)$ è non limitato radialmente (cioè, $KL \to \infty$ al tendere di $\|\theta\|$ all'infinito). Questa proprietà impedisce ai parametri di divergere all'infinito mentre la funzione valore rimane limitata, garantendo così che la traiettoria rimanga all'interno di una regione compatta dove gli autovalori delle matrici rilevanti sono limitati inferiormente da zero.

Contributi e Risultati Chiave

L'articolo identifica due regimi distinti per le basi di caratteristiche nei quali si ottiene la convergenza lineare globale:

1. Caratteristiche a Span Affino Completo:

   • Assunzione: La mappa di caratteristiche $g(s, \cdot)$ ha dimensione affina completa e l'insieme dei massimizzatori di qualsiasi proiezione lineare di $g$ ha misura nulla rispetto a $\mu$.
   • Risultato: La divergenza KL è non limitata radialmente in tutte le direzioni. Di conseguenza, il più piccolo autovalore della FIM rimane limitato inferiormente da una costante positiva dipendente dall'inizializzazione.
   • Convergenza: Il decadimento della subottimalità è $O(e^{-Ct})$ per un certo $C > 0$.

2. Caratteristiche a Valore Simplettico:

   • Assunzione: Le caratteristiche giacciono nel simpletto di probabilità ($\sum g_i = 1, g_i \geq 0$). La condizione sull'insieme dei massimizzatori è rilassata per applicarsi solo ai vettori ortogonali al vettore di tutti uni.
   • Risultato: La divergenza KL è non limitata radialmente solo nel sottospazio ortogonale al vettore di tutti uni (la direzione della ridondanza dei parametri). Gli autori dimostrano che il flusso di gradiente preserva la proiezione di $\theta$ sul vettore di tutti uni, confinando efficacemente la dinamica al sottospazio rilevante.
   • Convergenza: Utilizzando una matrice di covarianza delle caratteristiche non centrata invece della FIM, stabiliscono un limite inferiore uniforme sugli autovalori, ottenendo lo stesso tasso di convergenza lineare globale $O(e^{-Ct})$.

Significato e Affermazioni
Gli autori affermano che questo lavoro estende la teoria di convergenza globale del gradiente di politica softmax con regularizzazione di entropia oltre l'impostazione tabulare stabilita da Agarwal et al. (2020), Bhandari e Russo (2024) e Mei et al. (2020).

• Novità negli Ambienti Continui: L'articolo affronta l'intrattabilità computazionale dei metodi tabulari negli spazi continui analizzando rigorosamente l'approssimazione lineare di funzione.
• Gestione della Non Convessità: Stabilendo una disuguaglianza PŁ non uniforme e controllando la costante non uniforme tramite tecniche di Lyapunov, gli autori superano la non convessità della parametrizzazione softmax negli spazi continui.
• Ruolo della Regularizzazione KL: L'articolo evidenzia un uso innovativo della divergenza KL come funzione di Lyapunov per garantire la non limitatezza radiale, una proprietà che non vale nel caso tabulare standard (dove il termine KL è finito per qualsiasi politica con supporto completo).
• Sensibilità delle Caratteristiche: Il lavoro fornisce esempi specifici (ad esempio, caratteristiche trigonometriche, polinomi di Bernstein) che soddisfano le condizioni di convergenza e controesempi (ad esempio, funzioni a cappello) in cui la non limitatezza radiale fallisce, chiarificando le proprietà geometriche necessarie delle basi di caratteristiche per la convergenza lineare.

I risultati implicano che, sotto realizzabilità $Q^\pi_\tau$ e condizioni adeguate sulle caratteristiche, il gradiente di politica con regularizzazione di entropia converge globalmente e linearmente alla politica ottima in spazi generali di stato e azione, eguagliando i tassi favorevoli precedentemente noti solo per ambienti tabulari o lineari-quadratici.