Global Optimality for Constrained Exploration via Penalty Regularization

1. Formulazione del Problema

Il lavoro affronta la sfida dell'Esplorazione a Entropia Massima Vincolata (CME) nell'Apprendimento per Rinforzo (RL).

• Obiettivo: Massimizzare l'entropia della misura di occupazione stato-azione ($H(\lambda_\pi)$) per incentivare un'esplorazione diversificata dell'ambiente.
• Vincoli: L'esplorazione deve soddisfare vincoli convessi generali sulla misura di occupazione, come limiti di sicurezza (costo cumulativo), budget di risorse o requisiti di imitazione (vicinanza a una politica di riferimento tramite divergenza KL).
• Formulazione Matematica:
  $$\max_{\theta \in \Theta} H(\lambda_{\pi_\theta}) \quad \text{s.t.} \quad R(\lambda_{\pi_\theta}) \leq 0$$
  dove $\pi_\theta$ è una politica parametrizzata (ad esempio, softmax) e $\lambda_{\pi_\theta}$ è la misura di occupazione stato-azione indotta.
• Sfide:
  1. Non Convessità: Sebbene il problema sia convesso nello spazio delle misure di occupazione ($\lambda$), la parametrizzazione della politica ($\theta$) rende non convessi sia l'obiettivo che i vincoli.
  2. Mancanza di Struttura Additiva: La massimizzazione dell'entropia manca della struttura additiva di Bellman, rendendo inapplicabili i metodi standard di Programmazione Dinamica o Actor-Critic.
  3. Limiti dei Lavori Precedenti: I metodi esistenti (ad esempio, Ying et al., 2025) si basano su approcci primali-duali che garantiscono solo medie ergodiche o rimpianto debole. Questi non assicurano che la politica di output finale (l'ultima iterazione) sia ammissibile o quasi-ottimale, aspetto critico per il dispiegamento.

2. Metodologia: Penalità del Gradiente di Politica (PGP)

Gli autori propongono la Penalità del Gradiente di Politica (PGP), un algoritmo a ciclo singolo e puramente primario che opera direttamente nello spazio dei parametri della politica.

Meccanismo Principale

Invece di utilizzare variabili duali (moltiplicatori di Lagrange) che richiedono aggiornamenti duali complessi, PGP trasforma il problema vincolato in uno non vincolato utilizzando la regolarizzazione quadratica a penalità:
$$\min_{\theta \in \Theta} P(\theta) := -H(\lambda_{\pi_\theta}) + \beta [R(\lambda_{\pi_\theta})]_+^2$$
dove $[x]_+ = \max(0, x)$ e $\beta$ è il parametro di penalità.

Innovazioni Chiave dell'Algoritmo

1. Ricompense Pseudo: Una novità maggiore è la costruzione di "ricompense pseudo" per calcolare i gradienti.

   • I metodi stocastici standard a penalità richiedono stimatori separati per il valore del vincolo e il suo gradiente, portando a bias.
   • PGP sfrutta il Teorema del Gradiente di Politica per reinterpretare il gradiente dell'obiettivo penalizzato come un gradiente di politica standard rispetto a un vettore di ricompense pseudo costruito.
   • Nello specifico, il gradiente del termine di penalità $\nabla_\theta [R(\lambda)]_+^2$ è calcolato come $\nabla_\theta V^{\pi_\theta}(r_{pseudo})$, dove $r_{pseudo} = 2[R(\lambda)]_+ \nabla_\lambda R(\lambda)$.
   • Ciò consente l'uso di un singolo batch di traiettorie per stimare l'intero gradiente dell'obiettivo penalizzato senza stimatori ausiliari del valore della funzione.

2. SGD a Ciclo Singolo: L'algoritmo esegue la Discesa del Gradiente Stocastico (SGD) sull'obiettivo penalizzato utilizzando queste ricompense pseudo, evitando i cicli annidati o gli aggiornamenti duali tipici dei metodi primali-duali.

Fondamento Teorico

Il metodo si basa sul concetto di Convessità Nascosta:

• Sebbene il problema sia non convesso in $\theta$, la mappatura dai parametri della politica alle misure di occupazione preserva una struttura convessa nascosta.
• Gli autori dimostrano che la formulazione a penalità quadratica preserva questa convessità nascosta e le proprietà di regolarità.
• Sotto l'ipotesi di Dualità Forte (che è più debole della condizione di Slater e vale per problemi a convessità nascosta), stabiliscono che la soluzione del problema penalizzato converge alla soluzione vincolata.

3. Contributi Chiave

1. Algoritmo (PGP): Introduzione di un metodo a gradiente di politica a ciclo singolo e puramente primario per la massimizzazione dell'entropia vincolata che impone i vincoli tramite penalità quadratiche senza variabili duali.
2. Convergenza Globale dell'Ultima Iterazione: Dimostrazione teorica che l'ultima iterazione dell'algoritmo converge a una soluzione $(\epsilon, \epsilon)$-ottimale (obiettivo quasi-ottimale e vincoli quasi-ammissibili) con alta probabilità. Questo rappresenta un miglioramento significativo rispetto alle garanzie precedenti di tipo ergodico/rimpianto debole.
3. Complessità Campionaria: Stabilimento di una complessità campionaria non asintotica di $\tilde{O}(\epsilon^{-6})$ per parametrizzazioni generali della politica sotto dualità forte. Questa è la prima garanzia di questo tipo per l'esplorazione a entropia massima vincolata in questo contesto.
4. Costruzione di Ricompense Pseudo: Una tecnica innovativa per gestire la regola della catena nei metodi stocastici a penalità reinterpretando i gradienti come gradienti di politica, eliminando la necessità di più passaggi di campionamento per iterazione.

4. Risultati Sperimentali

Gli autori hanno validato PGP su compiti di controllo sia discreti che continui:

• Grid World (FrozenLake):

  • Compito: Massimizzare l'entropia evitando gli stati "buco" (vincolo di sicurezza).
  • Confronto: Ha superato il metodo Primal-Dual Policy Gradient (PDPG) all'avanguardia (Ying et al., 2025).
  • Osservazione: PDPG ha mostrato oscillazioni attorno al confine del vincolo (comportamento di rimpianto debole), mentre PGP è converso a una politica stabile che ha soddisfatto rigorosamente i vincoli mantenendo un'alta entropia.
  • Robustezza: PGP ha mostrato robustezza rispetto al parametro di penalità $\beta$ e al passo di apprendimento $\eta$.

• Controllo Continuo (PointMass & SafeCartpole):

  • PointMass (Imitazione): Ha esplorato l'ambiente restando vicino a una politica SAC di riferimento. PGP ha bilanciato con successo esplorazione e imitazione, con la politica che si è discostata dal riferimento all'aumentare del budget del vincolo ($R_{max}$).
  • SafeCartpole: Un compito di ribaltamento impegnativo in cui la posizione del carrello deve rimanere entro limiti di sicurezza. PGP ha appreso una strategia di controllo "bang-bang" per sollevare il palo rispettando rigorosamente i vincoli di posizione, dimostrando la scalabilità negli spazi continui ad alta dimensionalità.

5. Significato e Impatto

• Svolta Teorica: Questo lavoro colma il divario tra la teoria dell'ottimizzazione convessa e il RL pratico fornendo garanzie di convergenza dell'ultima iterazione per problemi di esplorazione vincolata non convessi. I metodi precedenti non potevano garantire che la politica finale dispiegata fosse sicura o ottimale.
• Applicabilità Pratica: La natura a ciclo singolo di PGP lo rende computazionalmente efficiente e più facile da implementare rispetto ai metodi primali-duali, che spesso soffrono di difficoltà di sintonizzazione con le variabili duali.
• Generalizzabilità: Il framework si estende oltre il RL ai problemi generali di ottimizzazione vincolata a convessità nascosta, offrendo un approccio unificato per l'esplorazione critica per la sicurezza, l'apprendimento per imitazione e compiti con vincoli di risorse.
• Risposta a Esigenze Reali: Gestendo vincoli convessi generali (sicurezza, costo, imitazione) con garanzie rigorose, il metodo affronta un collo di bottiglia critico nel dispiegamento di agenti RL in scenari reali dove sicurezza e ammissibilità sono non negoziabili.

In sintesi, il lavoro presenta una soluzione rigorosa, scalabile e teoricamente fondata all'esplorazione vincolata, superando approcci euristici e garanzie di convergenza deboli per fornire un algoritmo dispiegabile con assicurazioni di ottimalità globale.