Technische Samenvatting: Augmented Lagrangian-methode voor convergentie van de laatste iteratie voor Beperkte MDP's

Probleemformulering

Het artikel behandelt het probleem van beleidsoptimalisatie voor onbepaalde horizon, afgekapte Beperkte Markov Beslissingsprocessen (CMDP's). In deze setting moet een agent een cumulatieve beloning $V^\pi_r(\rho)$ maximaliseren, terwijl ervoor wordt gezorgd dat cumulatieve beperkingsbeloningen $V^\pi_{c_i}(\rho)$ voldoen aan voorgeschreven drempels $b_i$ voor $m$ beperkingen. In tegenstelling tot standaard MDP's, waarbij optimale beleidsplannen deterministisch zijn, zijn optimale beleidsplannen voor CMDP's over het algemeen stochastisch.

Een aanzienlijke praktische uitdaging vloeit voort uit de beperkingen van bestaande Primaal-Duale (PD) methoden. Hoewel theoretische garanties voor PD-methoden bestaan, zijn deze doorgaans alleen van toepassing op een mixture-beleid (een uniform gemiddelde van alle tussentijdse beleidsplannen die tijdens het trainen worden gegenereerd). Het inzetten van zo'n mixture is rekenkundig en geheugenintensief, omdat het vereist dat alle tussentijdse beleidsplannen worden opgeslagen. Bovendien is het in veiligheidskritieke toepassingen riskant om te vertrouwen op een mixture, omdat een willekeurig uit de mixture getrokken beleid de beperkingen aanzienlijk kan schenden, zelfs als de mixture ze in verwachting voldoet. Bijgevolg zetten practitioners vaak het beleid van de laatste iteratie (het gegenereerde eindbeleid) in, maar standaard PD-methoden missen theoretische garanties voor dit specifieke beleid, vertonen vaak oscillerend gedrag en falen in het convergeren naar een haalbare oplossing.

Recente werken die proberen convergentie van de laatste iteratie te bewijzen, zijn grotendeels beperkt tot tabulaire settings of vertrouwen op algoritmische varianten (bijvoorbeeld zware regularisatie) die moeilijk te implementeren zijn of onpraktisch voor grootschalige problemen.

Methodologie

De auteurs stellen een algemeen raamwerk voor op basis van de Augmented Lagrangian (AL)-methode, een klassieke aanpak in beperkte optimalisatie, om bewezen convergentie van de laatste iteratie voor CMDP's te bereiken.

1. Het Augmented Lagrangian-raamwerk

In plaats van de standaard Lagrangiaan die in PD-methoden wordt gebruikt, optimaliseert het raamwerk de Augmented Lagrangian-functie $L_\beta(\pi, \lambda)$:
$$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$$
waarbij $\beta > 0$ een straffparameter is en $\lambda$ Lagrange-multiplicatoren zijn. De kwadratische strafterm ontmoedigt beperkingsschendingen. Het algoritme werkt iteratief het beleid (primaal variabele) bij om deze functie ongeveer te maximaliseren en werkt de duale variabelen (Lagrange-multiplicatoren) bij op basis van beperkingsschendingen.

2. Het oplossen van het AL-subprobleem

De kernuitdaging is dat $L_\beta(\pi, \lambda)$ niet-concaaf is met betrekking tot het beleid $\pi$, wat het subprobleem moeilijk oplosbaar maakt. De auteurs ontleden de oplossing in twee settings:

• Tabulaire Setting: De auteurs stellen voor het AL-subprobleem op te lossen met Projected Q-Ascent (PQA). Zij leiden de beleidsgradiënt voor het AL-subprobleem af, die een niet-stationaire pseudo-beloning $\Gamma(\pi)$ omvat die afhankelijk is van het niveau van beperkingstevredenheid van het huidige beleid. Door PQA te gebruiken, vestigen zij globale garanties voor convergentie van de laatste iteratie voor het subprobleem.
• Functiebenadering (Log-lineaire Beleidsplannen): Om grote staten-actie-ruimtes te hanteren, wordt het raamwerk uitgebreid naar parametrische beleidsplannen (specifiek log-lineaire beleidsplannen). De auteurs leiden een AL-beleidsgradiënt af die lineair decomposeert in de oorspronkelijke belonings- en beperkingscomponenten, waardoor standaard schattingshulpmiddelen (zoals die gebruikt in PPO of SPMA) kunnen worden ingezet. Zij introduceren een Projected PQA (PPQA)-update, die omvat:
  1. Het berekenen van een geïdealiseerde beleidsupdate (PQA-stap).
  2. Het projecteren van deze update op de haalbare beleidsklasse met behulp van voorwaartse KL-divergentie, geformuleerd als een surrogaat-optimalisatieprobleem (multiclasse logistische regressie met zachte labels).

3. Convergentieanalyse

De auteurs leveren een modulaire analyse:

1. Zij bewijzen eerst dat de onnauwkeurige AL-methode convergeert naar een $\epsilon$-optimale oplossing voor de CMDP als de subprobleemoplosser een specifieke nauwkeurigheid bereikt ($O(1/\epsilon^2)$ iteraties voor de buitenste lus).
2. Zij analyseren vervolgens de specifieke oplossers (PQA en PPQA) om aan te tonen dat zij de vereiste nauwkeurigheid voor het subprobleem kunnen bereiken.
3. Door deze resultaten te combineren, bewijzen zij dat het algehele algoritme globale convergentie van de laatste iteratie bereikt met een steekproefcomplexiteit van $O(1/\epsilon^6)$ gradiëntevaluaties voor zowel tabulaire als log-lineaire settings.

Belangrijkste Bijdragen

1. Generiek Onnauwkeurig AL-raamwerk: Het artikel introduceert een modulair raamwerk voor het oplossen van CMDP's met behulp van de onnauwkeurige AL-methode. Het scheidt de analyse van de AL-iteraties van de keuze van de subprobleemoplosser, en bewijst dat $O(1/\epsilon^2)$ buitenste iteraties voldoende zijn om een $\epsilon$-optimaal beleid te vinden, mits het subprobleem met voldoende nauwkeurigheid wordt opgelost.
2. Convergentie van de laatste iteratie in tabulaire setting: Door het raamwerk te instantiëren met Projected Q-Ascent (PQA) voor de tabulaire setting, vestigen de auteurs globale convergentie van de laatste iteratie met een complexiteit van $O(1/\epsilon^6)$. Dit adresseert de niet-stationariteit van de pseudo-beloning in het AL-subprobleem.
3. Uitbreiding naar Functiebenadering: Het raamwerk wordt gegeneraliseerd naar log-lineaire beleidsplannen. De auteurs leiden de AL-beleidsgradiënt af en stellen een geprojecteerde variant (PPQA) voor die vergelijkbare $O(1/\epsilon^6)$ convergentiegaranties bereikt. In tegenstelling tot eerdere werken vereist deze methode geen niet-standaard algoritmische modificaties (zoals projecteren op beperkte simplex) of restrictieve structurele aannames (zoals compatibele functiebenadering) en ondersteunt het meerdere beperkingen.
4. Empirische Validatie: Het raamwerk wordt geïstantieerd met PPO en SPMA (een recent beleidsoptimalisatie-algoritme) en geëvalueerd op grootschalige continue controle-taken uit Safety-Gymnasium. De resultaten tonen aan dat de voorgestelde aanpak vergelijkbaar presteert met zwaar geengineerde baselines zoals PPO-Lag en CPO, terwijl het theoretische garanties biedt voor het eindbeleid.

Resultaten

• Theoretisch: Het artikel bewijst dat het voorgestelde algoritme een stochastisch beleid oplevert dat een $\epsilon$-benaderende oplossing is voor het CMDP-probleem na $O(1/\epsilon^6)$ gradiëntevaluaties. Dit geldt voor zowel tabulaire als log-lineaire beleidsklassen.
• Empirisch (Tabulair): In tabulaire omgevingen (Constrained Cliff World, Constrained Deep Sea Treasure) convergeren de voorgestelde PQA-ALM- en PPQA-ALM-methoden soepel naar het optimale beleid met minimale oscillatie, en presteren ze beter dan of gelijk aan andere methoden voor de laatste iteratie zoals RPG-PD en ReLOAD.
• Empirisch (Continue Controle): Op Safety-Gymnasium-taken (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity) bereiken de SPMA-ALM- en PPO-ALM-varianten opbrengsten en beperkingsschendingen die vergelijkbaar zijn met PPO-Lag en CPO. Opmerkelijk is dat de op AL gebaseerde methoden minder oscillerend gedrag vertonen en een consistentere beperkingstevredenheid (lagere gemiddelde en staartschendingen) tonen in vergelijking met baselines.

Betekenis en Claims

Het artikel claimt de kloof te dichten tussen theoretische garanties en praktische inzet in beperkte versterkende learning.

• Praktijktoepasbaarheid: In tegenstelling tot eerdere werken over convergentie van de laatste iteratie die ofwel beperkt zijn tot tabulaire settings of vertrouwen op onpraktische regularisaties, is dit raamwerk ontworpen om efficiënt en schaalbaar te zijn voor grote problemen met behulp van standaard functiebenadering.
• Veiligheid: Door convergentie te garanderen voor het beleid van de laatste iteratie in plaats van een mixture, zorgt de methode ervoor dat het ingezette beleid zelf voldoet aan beperkingen, wat kritiek is voor veiligheidskritieke toepassingen waarbij willekeurig bemonsteren uit een mixture onaanvaardbaar is.
• Principiële Aanpak: De methode vertrouwt op de klassieke Augmented Lagrangian-methode, waardoor een duidelijke theoretische grondslag wordt geboden zonder de noodzaak van ad-hoc heuristieken die vaak worden aangetroffen in praktische beperkte RL-implementaties (bijvoorbeeld het schalen van doelen door multiplicatoren).

De auteurs erkennen beperkingen, specifiek de sterke afhankelijkheid van de minimum bezochte statiekans ($\rho_{min}$) in de tabulaire setting en de bias-term ($\epsilon_{bias}$) voor log-lineaire beleidsplannen, en suggereren deze als richtingen voor toekomstig werk. Zij merken ook op dat toekomstige richtingen het incorporeren van actor-critic- of off-policy-methoden in het theoretische raamwerk omvatten.