Résumé Technique : Méthode du Lagrangien Augmenté pour la Convergence à la Dernière Itération des MDP Contraints

Formulation du Problème

L'article aborde le problème de l'optimisation de politique pour les Processus de Décision Markoviens (MDP) contraints à horizon infini et à facteur d'actualisation. Dans ce contexte, un agent doit maximiser une récompense cumulative $V^\pi_r(\rho)$ tout en s'assurant que les récompenses cumulatives de contraintes $V^\pi_{c_i}(\rho)$ satisfont des seuils prescrits $b_i$ pour $m$ contraintes. Contrairement aux MDP standards où les politiques optimales sont déterministes, les politiques optimales pour les MDP contraints sont généralement stochastiques.

Un défi pratique majeur découle des limitations des méthodes Primal-Dual (PD) existantes. Bien que des garanties théoriques existent pour les méthodes PD, elles s'appliquent généralement uniquement à une politique de mélange (une moyenne uniforme de toutes les politiques intermédiaires générées durant l'entraînement). Déployer un tel mélange est coûteux en calcul et en mémoire, car il nécessite de stocker toutes les politiques intermédiaires. De plus, dans des applications critiques pour la sécurité, s'appuyer sur un mélange est risqué car une politique échantillonnée aléatoirement à partir du mélange peut violer les contraintes de manière significative, même si le mélange les satisfait en espérance. Par conséquent, les praticiens déploient souvent la politique de la dernière itération (la politique finale générée), mais les méthodes PD standards manquent de garanties théoriques pour cette politique spécifique, exhibant souvent un comportement oscillatoire et échouant à converger vers une solution réalisable.

Les travaux récents tentant de prouver la convergence à la dernière itération ont été largement limités aux environnements tabulaires ou reposent sur des variantes algorithmiques (par exemple, une régularisation lourde) difficiles à mettre en œuvre ou peu pratiques pour des problèmes à grande échelle.

Méthodologie

Les auteurs proposent un cadre général basé sur la méthode du Lagrangien Augmenté (AL), une approche classique en optimisation contrainte, pour atteindre une convergence prouvée à la dernière itération pour les MDP contraints.

1. Le Cadre du Lagrangien Augmenté

Au lieu du Lagrangien standard utilisé dans les méthodes PD, le cadre optimise la fonction du Lagrangien Augmenté $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)$$
où $\beta > 0$ est un paramètre de pénalité et $\lambda$ sont les multiplicateurs de Lagrange. Le terme de pénalité quadratique décourage les violations de contraintes. L'algorithme met à jour itérativement la politique (variable primale) pour maximiser approximativement cette fonction et met à jour les variables duales (multiplicateurs de Lagrange) en fonction des violations de contraintes.

2. Résolution du Sous-problème AL

Le défi central est que $L_\beta(\pi, \lambda)$ est non concave par rapport à la politique $\pi$, rendant le sous-problème difficile à résoudre. Les auteurs décomposent la solution en deux contextes :

• Contexte Tabulaire : Les auteurs proposent de résoudre le sous-problème AL en utilisant l'Ascent de Q Projeté (PQA). Ils dérivent le gradient de politique pour le sous-problème AL, qui implique une pseudo-récompense non stationnaire $\Gamma(\pi)$ dépendant du niveau de satisfaction des contraintes de la politique actuelle. En utilisant PQA, ils établissent des garanties de convergence globale à la dernière itération pour le sous-problème.
• Approximation de Fonction (Politiques Log-Linéaires) : Pour gérer de grands espaces d'état-action, le cadre est étendu aux politiques paramétriques (spécifiquement les politiques log-linéaires). Les auteurs dérivent un gradient de politique AL qui se décompose linéairement en composantes de récompense et de contrainte originales, permettant l'utilisation d'outils d'estimation standards (comme ceux utilisés dans PPO ou SPMA). Ils introduisent une mise à jour PQA Projeté (PPQA), qui implique :
  1. Le calcul d'une mise à jour de politique idéalisée (étape PQA).
  2. La projection de cette mise à jour sur la classe de politiques réalisables en utilisant la divergence KL forward, formulée comme un problème d'optimisation de substitution (régression logistique multi-classes avec étiquettes douces).

3. Analyse de Convergence

Les auteurs fournissent une analyse modulaire :

1. Ils prouvent d'abord que la méthode AL inexacte converge vers une solution $\epsilon$-optimale pour le MDP contraint si le solveur de sous-problème atteint une précision spécifique ($O(1/\epsilon^2)$ itérations pour la boucle externe).
2. Ils analysent ensuite les solveurs spécifiques (PQA et PPQA) pour montrer qu'ils peuvent atteindre la précision requise pour le sous-problème.
3. En combinant ces résultats, ils prouvent que l'algorithme global atteint une convergence globale à la dernière itération avec une complexité en échantillons de $O(1/\epsilon^6)$ évaluations de gradient pour les contextes tabulaires et log-linéaires.

Contributions Clés

1. Cadre AL Inexact Générique : L'article introduit un cadre modulaire pour résoudre les MDP contraints en utilisant la méthode AL inexacte. Il sépare l'analyse des itérations AL du choix du solveur de sous-problème, prouvant que $O(1/\epsilon^2)$ itérations externes suffisent pour trouver une politique $\epsilon$-optimale, à condition que le sous-problème soit résolu avec une précision suffisante.
2. Convergence à la Dernière Itération Tabulaire : En instanciant le cadre avec l'Ascent de Q Projeté (PQA) pour le contexte tabulaire, les auteurs établissent une convergence globale à la dernière itération avec une complexité de $O(1/\epsilon^6)$. Cela aborde la non-stationnarité de la pseudo-récompense dans le sous-problème AL.
3. Extension à l'Approximation de Fonction : Le cadre est généralisé aux politiques log-linéaires. Les auteurs dérivent le gradient de politique AL et proposent une variante projetée (PPQA) qui atteint des garanties de convergence comparables de $O(1/\epsilon^6)$. Contrairement aux travaux antérieurs, cette méthode ne nécessite pas de modifications algorithmiques non standards (comme la projection sur des simplexes restreints) ni d'hypothèses structurelles restrictives (comme l'approximation de fonction compatible) et prend en charge plusieurs contraintes.
4. Validation Empirique : Le cadre est instancié en utilisant PPO et SPMA (un algorithme récent d'optimisation de politique) et évalué sur des tâches de contrôle continu à grande échelle issues de Safety-Gymnasium. Les résultats démontrent que l'approche proposée performe de manière comparable à des bases de référence fortement ingénierées comme PPO-Lag et CPO, tout en offrant des garanties théoriques pour la politique finale.

Résultats

• Théoriques : L'article prouve que l'algorithme proposé renvoie une politique stochastique qui est une solution $\epsilon$-approchée du problème MDP contraint après $O(1/\epsilon^6)$ évaluations de gradient. Cela vaut pour les classes de politiques tabulaires et log-linéaires.
• Empiriques (Tabulaire) : Dans des environnements tabulaires (Monde de la Falaise Contraint, Trésor des Mers Profondes Contraint), les méthodes PQA-ALM et PPQA-ALM proposées convergent de manière fluide vers la politique optimale avec une oscillation minimale, surpassant ou égalant d'autres méthodes à la dernière itération comme RPG-PD et ReLOAD.
• Empiriques (Contrôle Continu) : Sur les tâches de Safety-Gymnasium (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity), les variantes SPMA-ALM et PPO-ALM atteignent des retours et des violations de contraintes comparables à PPO-Lag et CPO. Notamment, les méthodes basées sur AL exhibent un comportement moins oscillatoire et une satisfaction des contraintes plus cohérente (violations moyennes et de queue plus faibles) par rapport aux bases de référence.

Importance et Revendications

L'article prétend combler le fossé entre les garanties théoriques et le déploiement pratique dans l'apprentissage par renforcement contraint.

• Praticité : Contrairement aux travaux précédents sur la convergence à la dernière itération qui sont soit limités aux contextes tabulaires, soit reposent sur des régularisations peu pratiques, ce cadre est conçu pour être efficace et évolutif vers de grands problèmes en utilisant une approximation de fonction standard.
• Sécurité : En garantissant la convergence pour la politique de la dernière itération plutôt que pour un mélange, la méthode assure que la politique déployée elle-même satisfait les contraintes, ce qui est critique pour les applications critiques pour la sécurité où l'échantillonnage aléatoire à partir d'un mélange est inacceptable.
• Approche Principée : La méthode repose sur la méthode classique du Lagrangien Augmenté, fournissant une fondation théorique claire sans avoir besoin d'heuristiques ad hoc souvent trouvées dans les implémentations pratiques de RL contraint (par exemple, le scaling des objectifs par des multiplicateurs).

Les auteurs reconnaissent des limitations, spécifiquement la forte dépendance à la probabilité minimale de visite d'état ($\rho_{min}$) dans le contexte tabulaire et le terme de biais ($\epsilon_{bias}$) pour les politiques log-linéaires, suggérant ceux-ci comme des directions pour des travaux futurs. Ils notent également que les directions futures incluent l'intégration de méthodes acteur-critique ou hors politique dans le cadre théorique.