Global Optimality for Constrained Exploration via Penalty Regularization

1. Probleemformulering

Het artikel behandelt de uitdaging van Constrained Maximum-Entropy Exploration (CME) in Reinforcement Learning (RL).

• Doel: Maximaliseren van de entropie van de state-action occupancy measure ($H(\lambda_\pi)$) om een diverse verkenning van de omgeving te stimuleren.
• Beperkingen: De verkenning moet voldoen aan algemene convexe beperkingen op de occupancy measure, zoals veiligheidslimieten (cumulatieve kosten), resource-budgetten of imitatie-eisen (nabijheid aan een referentiebeleid via KL-divergentie).
• Wiskundige Formulering:
  $$\max_{\theta \in \Theta} H(\lambda_{\pi_\theta}) \quad \text{s.t.} \quad R(\lambda_{\pi_\theta}) \leq 0$$
  waarbij $\pi_\theta$ een geparametriseerd beleid is (bijvoorbeeld softmax) en $\lambda_{\pi_\theta}$ de gegenereerde state-action occupancy measure is.
• Uitdagingen:
  1. Niet-convexiteit: Hoewel het probleem convex is in de ruimte van de occupancy measure ($\lambda$), maakt het parametriseren van het beleid ($\theta$) de doelstelling en beperkingen niet-convex.
  2. Gebrek aan Additieve Structuur: Entropiemaximalisatie mist de additieve Bellman-structuur, waardoor standaard Dynamic Programming of Actor-Critic-methoden niet toepasbaar zijn.
  3. Beperkingen van Eerder Werk: Bestaande methoden (bijvoorbeeld Ying et al., 2025) vertrouwen op primal-dual-benaderingen die slechts ergodische gemiddelden of zwakke regret garanderen. Deze zorgen er niet voor dat het uiteindelijke output-beleid (de laatste iteratie) haalbaar of bijna-optimaal is, wat cruciaal is voor implementatie.

2. Methodologie: Policy Gradient Penalty (PGP)

De auteurs stellen Policy Gradient Penalty (PGP) voor, een single-loop, primal-only algoritme dat direct werkt in de ruimte van beleidsparameters.

Kernmechanisme

In plaats van duale variabelen (Lagrange-multiplicatoren) te gebruiken die complexe duale updates vereisen, transformeert PGP het beperkte probleem naar een onbeperkt probleem met behulp van kwadratische penalty-regulering:
$$\min_{\theta \in \Theta} P(\theta) := -H(\lambda_{\pi_\theta}) + \beta [R(\lambda_{\pi_\theta})]_+^2$$
waarbij $[x]_+ = \max(0, x)$ en $\beta$ de penalty-parameter is.

Belangrijkste Algoritmische Innovaties

1. Pseudo-beloningen: Een grote nieuwigheid is de constructie van "pseudo-beloningen" om gradients te berekenen.

   • Standaard stochastische penalty-methoden vereisen aparte schatters voor de constraint-waarde en zijn gradient, wat leidt tot bias.
   • PGP maakt gebruik van de Policy Gradient Theorem om de gradient van de gepenaliseerde doelstelling te herinterpreteren als een standaard policy gradient met betrekking tot een geconstrueerde vector van pseudo-beloningen.
   • Specifiek wordt de gradient van de penalty-term $\nabla_\theta [R(\lambda)]_+^2$ berekend als $\nabla_\theta V^{\pi_\theta}(r_{pseudo})$, waarbij $r_{pseudo} = 2[R(\lambda)]_+ \nabla_\lambda R(\lambda)$.
   • Dit maakt het gebruik van een enkele traject-batch mogelijk om de volledige gradient van de gepenaliseerde doelstelling te schatten zonder hulpfunctie-waarde schatters.

2. Single-Loop SGD: Het algoritme voert Stochastic Gradient Descent (SGD) uit op de gepenaliseerde doelstelling met behulp van deze pseudo-beloningen, waardoor de geneste lussen of duale updates die typisch zijn voor primal-dual-methoden worden vermeden.

Theoretische Grondslag

De methode rust op het concept van Hidden Convexity:

• Hoewel het probleem niet-convex is in $\theta$, behoudt de mapping van beleidsparameters naar occupancy measures een verborgen convexe structuur.
• De auteurs bewijzen dat de kwadratische penalty-formulering deze verborgen convexiteit en gladheidseigenschappen behoudt.
• Onder de aanname van Strong Duality (wat zwakker is dan de Slater-voorwaarde en geldt voor hidden-convex problemen), stellen zij vast dat de oplossing van het gepenaliseerde probleem convergeert naar de beperkte oplossing.

3. Belangrijkste Bijdragen

1. Algoritme (PGP): Introductie van een single-loop, primal-only policy gradient-methode voor beperkte entropiemaximalisatie die beperkingen afdwingt via kwadratische penalties zonder duale variabelen.
2. Global Last-Iterate Convergence: Theoretisch bewijs dat de laatste iteratie van het algoritme convergeert naar een $(\epsilon, \epsilon)$-optimale oplossing (bijna-optimale doelstelling en bijna-haalbare beperkingen) met hoge waarschijnlijkheid. Dit is een aanzienlijke verbetering ten opzichte van eerdere ergodische/zwakke-regret-garanties.
3. Sample Complexity: Vestiging van een niet-asymptotische sample complexity van $\tilde{O}(\epsilon^{-6})$ voor algemene beleidsparametrisaties onder strong duality. Dit is de eerste dergelijke garantie voor beperkte maximum-entropy verkenning in deze setting.
4. Constructie van Pseudo-beloningen: Een nieuwe techniek om de kettingregel in stochastische penalty-methoden te hanteren door gradients te herinterpreteren als policy gradients, waardoor de noodzaak voor meerdere bemonsteringsstappen per iteratie wordt geëlimineerd.

4. Experimentele Resultaten

De auteurs hebben PGP gevalideerd op zowel discrete als continue controletaken:

• Grid World (FrozenLake):

  • Taak: Entropie maximaliseren terwijl "gat"-toestanden worden vermeden (veiligheidsbeperking).
  • Vergelijking: Presteerde beter dan de state-of-the-art Primal-Dual Policy Gradient (PDPG)-methode (Ying et al., 2025).
  • Observatie: PDPG vertoonde oscillaties rond de constraint-grens (zwakke regret-gedrag), terwijl PGP convergeerde naar een stabiel beleid dat de beperkingen strikt naleefde terwijl het een hoge entropie behield.
  • Robuustheid: PGP toonde robuustheid ten opzichte van de penalty-parameter $\beta$ en stapgrootte $\eta$.

• Continue Controle (PointMass & SafeCartpole):

  • PointMass (Imitatie): Verkende de omgeving terwijl het dicht bij een referentie SAC-beleid bleef. PGP slaagde erin verkenning en imitatie in evenwicht te brengen, waarbij het beleid afweek van de referentie naarmate het constraint-budget ($R_{max}$) toenam.
  • SafeCartpole: Een uitdagende swing-up taak waarbij de karpositie binnen veiligheidsgrenzen moet blijven. PGP leerde een "bang-bang"-controlestrategie om de pool omhoog te zwaaien terwijl het strikt de positiebeperkingen naleefde, wat schaalbaarheid naar hoogdimensionale continue ruimtes demonstreert.

5. Betekenis en Impact

• Theoretische Doorbraak: Dit werk overbrugt de kloof tussen convex optimalisatietheorie en praktisch RL door last-iterate convergence-garanties te bieden voor niet-convexe, beperkte verkenningsproblemen. Eerdere methoden konden niet garanderen dat het uiteindelijke ingezette beleid veilig of optimaal was.
• Praktische Toepasbaarheid: De single-loop aard van PGP maakt het computatie-efficiënt en eenvoudiger te implementeren dan primal-dual-methoden, die vaak lijden aan tuneerproblemen met duale variabelen.
• Generaliseerbaarheid: Het kader reikt verder dan RL naar algemene hidden-convex beperkte optimalisatieproblemen, en biedt een uniforme aanpak voor veiligheidskritische verkenning, imitatielearning en resource-beperkte taken.
• Adresseren van Real-World Behoeften: Door algemene convexe beperkingen (veiligheid, kosten, imitatie) te hanteren met rigoureuze garanties, adresseert de methode een kritieke bottleneck bij het implementeren van RL-agenten in real-world scenario's waar veiligheid en haalbaarheid niet onderhandelbaar zijn.

Kortom, het artikel presenteert een rigoureuze, schaalbare en theoretisch onderbouwde oplossing voor beperkte verkenning, die voorbijgaat aan heuristische benaderingen en zwakke convergentiegaranties om een implementeerbaar algoritme te bieden met garanties voor globale optimaliteit.