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

Technische Samenvatting: Globale Lineaire Convergentie van Entropie-geregulariseerde Softmax Policy Gradient Buiten Tabulaire MDP's

Probleemstelling
Dit artikel onderzoekt de globale convergentie-eigenschappen van policy gradient (PG) methoden voor oneindig-horizont entropie-geregulariseerde Markov Decision Processes (MDP's) met continue ruimte en actie-ruimtes. Hoewel entropie-regularisatie (het invoeren van een KL-divergentie-term met intensiteit $\tau > 0$) bekend staat om het verbeteren van het convergentielandschap van softmax-policies in tabulaire settings (eindige $S$ en $A$), blijft het uitbreiden van deze garanties naar continue ruimtes met functiebenadering een aanzienlijke theoretische uitdaging.

Specifiek beschouwen de auteurs log-lineaire softmax-policies gedefinieerd door:
$$\pi_\theta(da|s) \propto \exp(\langle \theta, g(s, a) \rangle) \mu(da)$$
waarbij $g: S \times A \to \mathbb{R}^p$ een feature-basis voorstelt, $\theta \in \mathbb{R}^p$ de parameters zijn, en $\mu$ een referentiemaat is. Het doel is om de geregulariseerde waardenfunctie $V^\pi_\tau(\rho)$ te minimaliseren. De kernmoeilijkheid ligt in de niet-convexiteit van het doel met betrekking tot $\theta$, zelfs met entropie-regularisatie, en de potentiële degeneratie van de Fisher Informatie Matrix (FIM) of feature-covariantiematrices in continue settings, wat kan voorkomen dat standaard convergentiebewijzen opgaan.

Methodologie
De analyse steunt op een continu-tijd gradient-flow formulering:
$$\frac{d}{dt}\theta_t = -\nabla_\theta V^{\pi_{\theta_t}}_\tau(\rho)$$
De bewijsstrategie verloopt in drie hoofdfasen:

1. Niet-uniforme Polyak–Łojasiewicz (PŁ) Ongelijkheid:
   De auteurs stellen eerst een niet-uniforme PŁ-ongelijkheid vast van de vorm:
   $$V^{\pi_\theta}_\tau(\rho) - V^{\pi^*_\tau}_\tau(\rho) \leq C(\theta) \|\nabla_\theta V^{\pi_\theta}_\tau(\rho)\|^2$$
   Deze ongelijkheid koppelt de suboptimaliteitskloof aan het gekwadrateerde gradiëntnorm. Cruciaal is dat de constante $C(\theta)$ afhangt van de policy-geometrie, specifiek de kleinste eigenwaarde van de FIM (of een ongecentreerde feature-covariantiematrix voor simplex-features) en de dichtheidsgrenzen van de policy. In tegenstelling tot de tabulaire case waar $C$ uniform kan zijn, is hier $C(\theta)$ niet-uniform en zou deze theoretisch kunnen degenereren naarmate $\|\theta\| \to \infty$.

2. Q$\pi_\tau$-Realiseerbaarheidsaanneming:
   De analyse gaat ervan uit dat voor elke policy $\pi$, de geregulariseerde state-action waardenfunctie $Q^\pi_\tau$ exact kan worden weergegeven door de lineaire feature-basis:
   $$\langle \theta(\pi), g(s, a) \rangle = -\frac{1}{\tau} Q^\pi_\tau(s, a)$$
   Deze aanneming garandeert dat de optimale policy $\pi^*_\tau$ binnen de geparametriseerde klasse ligt, d.w.z. $\pi^*_\tau = \pi_{\theta^*}$ voor een zekere $\theta^*$.

3. Lyapunov-analyse en Radiale Onbegrensheid:
   Om globale lineaire convergentie te bewijzen, moeten de auteurs aantonen dat de niet-uniforme constante $C(\theta_t)$ begrensd blijft langs de gradient-flow-trajectorie. Dit vereist het bewijzen dat de trajectorie $\{\theta_t\}$ binnen een compacte set blijft.

   • Zij gebruiken de geregulariseerde doel $V^{\pi_\theta}_\tau(\rho)$ als Lyapunov-functie, met de vaststelling dat deze monotoon afneemt.
   • Zij bewijzen dat onder specifieke voorwaarden aan de feature-basis $g$, de KL-divergentie-term $KL(\pi_\theta | \mu)$ radiaal onbegrensd is (d.w.z. $KL \to \infty$ als $\|\theta\| \to \infty$). Deze eigenschap voorkomt dat de parameters divergeren naar oneindig terwijl de waardenfunctie begrensd blijft, waardoor wordt gegarandeerd dat de trajectorie binnen een compact gebied blijft waar de eigenwaarden van de relevante matrices begrensd zijn weg van nul.

Belangrijkste Bijdragen en Resultaten

Het artikel identificeert twee distincte regimes voor feature-bases waaronder globale lineaire convergentie wordt bereikt:

1. Full-Affine-Span Features:

   • Aanneming: De feature-map $g(s, \cdot)$ heeft volledige affiene dimensie, en de verzameling van maximalisatoren van elke lineaire projectie van $g$ heeft maat nul onder $\mu$.
   • Resultaat: De KL-divergentie is radiaal onbegrensd in alle richtingen. Bijgevolg blijft de kleinste eigenwaarde van de FIM begrensd onderaan door een positieve constante die afhankelijk is van de initialisatie.
   • Convergentie: De suboptimaliteit neemt af als $O(e^{-Ct})$ voor zekere $C > 0$.

2. Simplex-gevaloriseerde Features:

   • Aanneming: De features liggen in de waarschijnlijkheidssimplex ($\sum g_i = 1, g_i \geq 0$). De voorwaarde aan de verzameling van maximalisatoren wordt versoepeld tot het toepassen op vectoren die orthogonaal zijn op de vector van enen.
   • Resultaat: De KL-divergentie is radiaal onbegrensd alleen in de deelruimte orthogonaal op de vector van enen (de richting van parameterredundantie). De auteurs bewijzen dat de gradient-flow de projectie van $\theta$ op de vector van enen behoudt, waardoor de dynamiek effectief wordt beperkt tot de relevante deelruimte.
   • Convergentie: Door een ongecentreerde feature-covariantiematrix te gebruiken in plaats van de FIM, stellen zij een uniforme ondergrens vast voor de eigenwaarden, wat resulteert in dezelfde globale lineaire convergentiesnelheid $O(e^{-Ct})$.

Betekenis en Claims
De auteurs claimen dat dit werk de theorie van globale convergentie van entropie-geregulariseerde softmax policy gradient uitbreidt buiten de tabulaire setting die is vastgesteld door Agarwal et al. (2020), Bhandari en Russo (2024), en Mei et al. (2020).

• Noviteit in Continue Settings: Het artikel adresseert de computationele onuitvoerbaarheid van tabulaire methoden in continue ruimtes door een rigoureuze analyse van lineaire functiebenadering.
• Omgaan met Niet-Convexiteit: Door het vaststellen van een niet-uniforme PŁ-ongelijkheid en het beheersen van de niet-uniforme constante via Lyapunov-technieken, overwinnen de auteurs de niet-convexiteit van de softmax-parametrisatie in continue ruimtes.
• Rol van KL-regularisatie: Het artikel benadrukt een novel gebruik van de KL-divergentie als Lyapunov-functie om radiale onbegrensheid te waarborgen, een eigenschap die niet geldt in de standaard tabulaire case (waar de KL-term eindig is voor elke policy met volledige steun).
• Feature-sensitiviteit: Het werk biedt specifieke voorbeelden (bijv. trigonometrische features, Bernstein-polynomen) die aan de convergentievoorwaarden voldoen en contra-voorbeelden (bijv. hoed-functies) waar radiale onbegrensheid faalt, waardoor de noodzakelijke geometrische eigenschappen van feature-bases voor lineaire convergentie worden verduidelijkt.

De resultaten impliceren dat, onder $Q^\pi_\tau$-realiseerbaarheid en geschikte feature-voorwaarden, entropie-geregulariseerde policy gradient globaal en lineair convergeert naar de optimale policy in algemene ruimte en actie-ruimtes, wat overeenkomt met de gunstige snelheden die eerder alleen bekend waren voor tabulaire of lineair-kwadratische settings.