Riepilogo Tecnico: Metodo del Lagrangiano Aumentato per la Convergenza all'Ultima Iterazione per MDP Vincolati

Formulazione del Problema

Il documento affronta il problema dell'ottimizzazione della politica per Processi Decisionali di Markov (MDP) vincolati a orizzonte infinito e scontati. In questo contesto, un agente deve massimizzare una ricompensa cumulativa $V^\pi_r(\rho)$ garantendo al contempo che le ricompense cumulative per i vincoli $V^\pi_{c_i}(\rho)$ soddisfino le soglie prescritte $b_i$ per $m$ vincoli. A differenza degli MDP standard, dove le politiche ottimali sono deterministiche, le politiche ottimali per gli MDP vincolati (CMDP) sono generalmente stocastiche.

Una sfida pratica significativa deriva dalle limitazioni dei metodi Primal-Dual (PD) esistenti. Sebbene esistano garanzie teoriche per i metodi PD, queste si applicano tipicamente solo a una politica mista (una media uniforme di tutte le politiche intermedie generate durante l'addestramento). Implementare tale mistura è computazionalmente e in termini di memoria oneroso, poiché richiede l'archiviazione di tutte le politiche intermedie. Inoltre, in applicazioni critiche per la sicurezza, fare affidamento su una mistura è rischioso perché una politica campionata casualmente dalla mistura potrebbe violare i vincoli in modo significativo, anche se la mistura li soddisfa in media. Di conseguenza, i praticanti spesso implementano la politica dell'ultima iterazione (la politica finale generata), ma i metodi PD standard mancano di garanzie teoriche per questa specifica politica, esibendo spesso comportamenti oscillatori e fallendo nel convergere verso una soluzione ammissibile.

I lavori recenti che tentano di dimostrare la convergenza all'ultima iterazione sono stati in gran parte limitati a contesti tabellari o si basano su varianti algoritmiche (ad esempio, regolarizzazione pesante) che sono difficili da implementare o poco pratiche per problemi su larga scala.

Metodologia

Gli autori propongono un framework generale basato sul metodo del Lagrangiano Aumentato (AL), un approccio classico nell'ottimizzazione vincolata, per ottenere una convergenza all'ultima iterazione dimostrabile per i CMDP.

1. Il Framework del Lagrangiano Aumentato

Invece del Lagrangiano standard utilizzato nei metodi PD, il framework ottimizza la funzione del Lagrangiano Aumentato $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)$$
dove $\beta > 0$ è un parametro di penalità e $\lambda$ sono i moltiplicatori di Lagrange. Il termine di penalità quadratica scoraggia le violazioni dei vincoli. L'algoritmo aggiorna iterativamente la politica (variabile primaria) per massimizzare approssimativamente questa funzione e aggiorna le variabili duali (moltiplicatori di Lagrange) in base alle violazioni dei vincoli.

2. Risoluzione del Sottoproblema AL

La sfida principale è che $L_\beta(\pi, \lambda)$ è non concava rispetto alla politica $\pi$, rendendo difficile la risoluzione del sottoproblema. Gli autori scompongono la soluzione in due contesti:

• Contesto Tabellare: Gli autori propongono di risolvere il sottoproblema AL utilizzando l'Ascesa Q Proiettata (PQA). Derivano il gradiente della politica per il sottoproblema AL, che coinvolge una pseudo-ricompensa non stazionaria $\Gamma(\pi)$ che dipende dal livello di soddisfazione dei vincoli della politica corrente. Utilizzando la PQA, stabiliscono garanzie di convergenza globale all'ultima iterazione per il sottoproblema.
• Approssimazione di Funzione (Politiche Log-Lineari): Per gestire spazi stato-azione grandi, il framework è esteso a politiche parametriche (nello specifico, politiche log-lineari). Gli autori derivano un gradiente della politica AL che si scompone linearmente nelle componenti di ricompensa e vincolo originali, permettendo l'impiego di strumenti di stima standard (come quelli utilizzati in PPO o SPMA). Introducono un aggiornamento PQA Proiettato (PPQA), che comporta:
  1. Calcolare un aggiornamento ideale della politica (passo PQA).
  2. Proiettare questo aggiornamento sulla classe di politiche ammissibili utilizzando la divergenza KL in avanti, formulata come un problema di ottimizzazione surrogato (regressione logistica multiclasse con etichette soft).

3. Analisi della Convergenza

Gli autori forniscono un'analisi modulare:

1. Dimostrano prima che il metodo AL inesatto converge a una soluzione $\epsilon$-ottimale per il CMDP se il risolutore del sottoproblema raggiunge una specifica accuratezza ($O(1/\epsilon^2)$ iterazioni per il ciclo esterno).
2. Analizzano quindi i risolutori specifici (PQA e PPQA) per mostrare che possono raggiungere l'accuratezza richiesta per il sottoproblema.
3. Combinando questi risultati, dimostrano che l'algoritmo complessivo achieve convergenza globale all'ultima iterazione con una complessità di campionamento di $O(1/\epsilon^6)$ valutazioni del gradiente sia per i contesti tabellari che log-lineari.

Contributi Chiave

1. Framework AL Inesatto Generico: Il documento introduce un framework modulare per risolvere i CMDP utilizzando il metodo AL inesatto. Separa l'analisi delle iterazioni AL dalla scelta del risolutore del sottoproblema, dimostrando che $O(1/\epsilon^2)$ iterazioni esterne sono sufficienti per trovare una politica $\epsilon$-ottimale, a condizione che il sottoproblema sia risolto con sufficiente accuratezza.
2. Convergenza all'Ultima Iterazione in Contesto Tabellare: Istanteando il framework con l'Ascesa Q Proiettata (PQA) per il contesto tabellare, gli autori stabiliscono la convergenza globale all'ultima iterazione con una complessità di $O(1/\epsilon^6)$. Questo affronta la non stazionarietà della pseudo-ricompensa nel sottoproblema AL.
3. Estensione all'Approssimazione di Funzione: Il framework è generalizzato alle politiche log-lineari. Gli autori derivano il gradiente della politica AL e propongono una variante proiettata (PPQA) che raggiunge garanzie di convergenza comparabili di $O(1/\epsilon^6)$. A differenza di lavori precedenti, questo metodo non richiede modifiche algoritmiche non standard (come la proiezione su semplici ristretti) o assunzioni strutturali restrittive (come l'approssimazione di funzione compatibile) e supporta vincoli multipli.
4. Validazione Empirica: Il framework è istanziato utilizzando PPO e SPMA (un recente algoritmo di ottimizzazione della politica) e valutato su compiti di controllo continuo su larga scala tratti da Safety-Gymnasium. I risultati dimostrano che l'approccio proposto performa in modo comparabile a baseline fortemente ingegnerizzate come PPO-Lag e CPO, offrendo al contempo garanzie teoriche per la politica finale.

Risultati

• Teorici: Il documento dimostra che l'algoritmo proposto restituisce una politica stocastica che è una soluzione $\epsilon$-approssimata al problema CMDP dopo $O(1/\epsilon^6)$ valutazioni del gradiente. Questo vale sia per le classi di politiche tabellari che log-lineari.
• Empirici (Tabellari): Negli ambienti tabellari (Constrained Cliff World, Constrained Deep Sea Treasure), i metodi proposti PQA-ALM e PPQA-ALM convergono fluidamente verso la politica ottimale con oscillazioni minime, superando o eguagliando altri metodi all'ultima iterazione come RPG-PD e ReLOAD.
• Empirici (Controllo Continuo): Sui compiti di Safety-Gymnasium (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity), le varianti SPMA-ALM e PPO-ALM raggiungono ritorni e violazioni dei vincoli comparabili a PPO-Lag e CPO. In modo notevole, i metodi basati su AL esibiscono un comportamento meno oscillatorio e una soddisfazione dei vincoli più coerente (violazioni medie e di coda inferiori) rispetto alle baseline.

Significato e Affermazioni

Il documento afferma di colmare il divario tra garanzie teoriche e implementazione pratica nell'apprendimento per rinforzo vincolato.

• Praticità: A differenza di lavori precedenti sulla convergenza all'ultima iterazione che sono limitati a contesti tabellari o si basano su regolarizzazioni poco pratiche, questo framework è progettato per essere efficiente e scalabile a problemi grandi utilizzando l'approssimazione di funzione standard.
• Sicurezza: Garantendo la convergenza per la politica dell'ultima iterazione piuttosto che per una mistura, il metodo assicura che la politica implementata soddisfi essa stessa i vincoli, aspetto critico per applicazioni dove il campionamento casuale da una mistura è inaccettabile.
• Approccio Principale: Il metodo si basa sul classico metodo del Lagrangiano Aumentato, fornendo una solida base teorica senza la necessità di euristiche ad hoc spesso riscontrate nelle implementazioni pratiche di RL vincolato (ad esempio, scalare gli obiettivi per moltiplicatori).

Gli autori riconoscono le limitazioni, in particolare la forte dipendenza dalla probabilità minima di visita degli stati ($\rho_{min}$) nel contesto tabellare e dal termine di bias ($\epsilon_{bias}$) per le politiche log-lineari, suggerendo questi come direzioni per lavori futuri. Notano inoltre che le direzioni future includono l'incorporazione di metodi actor-critic o off-policy nel framework teorico.