Global Optimality for Constrained Exploration via Penalty Regularization

1. Formulation du Problème

L'article aborde le défi de l'Exploration à Entropie Maximale Contrainte (CME) dans l'Apprentissage par Renforcement (RL).

• Objectif : Maximiser l'entropie de la mesure d'occupation état-action ($H(\lambda_\pi)$) pour encourager une exploration diversifiée de l'environnement.
• Contraintes : L'exploration doit satisfaire des contraintes convexes générales sur la mesure d'occupation, telles que des limites de sécurité (coût cumulatif), des budgets de ressources, ou des exigences d'imitation (proximité avec une politique de référence via la divergence KL).
• Formulation Mathématique :
  $$\max_{\theta \in \Theta} H(\lambda_{\pi_\theta}) \quad \text{s.t.} \quad R(\lambda_{\pi_\theta}) \leq 0$$
  où $\pi_\theta$ est une politique paramétrée (par exemple, softmax), et $\lambda_{\pi_\theta}$ est la mesure d'occupation état-action induite.
• Défis :
  1. Non-Convexité : Bien que le problème soit convexe dans l'espace des mesures d'occupation ($\lambda$), la paramétrisation de la politique ($\theta$) rend l'objectif et les contraintes non convexes.
  2. Absence de Structure Additive : La maximisation de l'entropie manque de structure additive de type Bellman, rendant les méthodes standard de Programmation Dynamique ou Actor-Critic inapplicables.
  3. Limites des Travaux Antérieurs : Les méthodes existantes (par exemple, Ying et al., 2025) reposent sur des approches primales-duales qui ne garantissent que des moyennes ergodiques ou un faible regret. Elles ne garantissent pas que la politique de sortie finale (la dernière itération) est réalisable ou quasi-optimale, ce qui est critique pour le déploiement.

2. Méthodologie : Pénalité de Gradient de Politique (PGP)

Les auteurs proposent la Pénalité de Gradient de Politique (PGP), un algorithme à boucle unique, purement primal, opérant directement dans l'espace des paramètres de la politique.

Mécanisme Central

Au lieu d'utiliser des variables duales (multiplicateurs de Lagrange) qui nécessitent des mises à jour duales complexes, la PGP transforme le problème contraint en un problème non contraint en utilisant une régularisation par pénalité quadratique :
$$\min_{\theta \in \Theta} P(\theta) := -H(\lambda_{\pi_\theta}) + \beta [R(\lambda_{\pi_\theta})]_+^2$$
où $[x]_+ = \max(0, x)$ et $\beta$ est le paramètre de pénalité.

Innovations Algorithmiques Clés

1. Faux-Récompenses (Pseudo-Rewards) : Une nouveauté majeure est la construction de "faux-récompenses" pour calculer les gradients.

   • Les méthodes de pénalité stochastiques standard nécessitent des estimateurs séparés pour la valeur de la contrainte et son gradient, entraînant un biais.
   • La PGP exploite le Théorème du Gradient de Politique pour réinterpréter le gradient de l'objectif pénalisé comme un gradient de politique standard par rapport à un vecteur de faux-récompenses construit.
   • Spécifiquement, le gradient du terme de pénalité $\nabla_\theta [R(\lambda)]_+^2$ est calculé comme $\nabla_\theta V^{\pi_\theta}(r_{pseudo})$, où $r_{pseudo} = 2[R(\lambda)]_+ \nabla_\lambda R(\lambda)$.
   • Cela permet d'utiliser un seul lot de trajectoires pour estimer le gradient complet de l'objectif pénalisé sans estimateurs de valeurs de fonctions auxiliaires.

2. Descente de Gradient Stochastique (SGD) à Boucle Unique : L'algorithme effectue une SGD sur l'objectif pénalisé en utilisant ces faux-récompenses, évitant ainsi les boucles imbriquées ou les mises à jour duales typiques des méthodes primales-duales.

Fondement Théorique

La méthode repose sur le concept de Convexité Cachée :

• Bien que le problème soit non convexe en $\theta$, l'application des paramètres de politique aux mesures d'occupation préserve une structure convexe cachée.
• Les auteurs prouvent que la formulation par pénalité quadratique préserve cette convexité cachée et les propriétés de régularité.
• Sous l'hypothèse de Dualité Forte (qui est plus faible que la condition de Slater et vaut pour les problèmes à convexité cachée), ils établissent que la solution du problème pénalisé converge vers la solution contrainte.

3. Contributions Clés

1. Algorithme (PGP) : Introduction d'une méthode de gradient de politique à boucle unique, purement primal, pour la maximisation d'entropie contrainte, qui impose les contraintes via des pénalités quadratiques sans variables duales.
2. Convergence Globale de la Dernière Itération : Preuve théorique que la dernière itération de l'algorithme converge vers une solution $(\epsilon, \epsilon)$-optimale (objectif quasi-optimal et contraintes quasi-réalisables) avec une forte probabilité. C'est une amélioration significative par rapport aux garanties précédentes de type ergodique/faible regret.
3. Complexité Échantillonnaire : Établissement d'une complexité échantillonnaire non asymptotique de $\tilde{O}(\epsilon^{-6})$ pour des paramétrisations de politiques générales sous dualité forte. C'est la première garantie de ce type pour l'exploration à entropie maximale contrainte dans ce contexte.
4. Construction de Faux-Récompenses : Une technique novatrice pour gérer la règle de la chaîne dans les méthodes de pénalité stochastiques en réinterprétant les gradients comme des gradients de politique, éliminant ainsi le besoin de multiples étapes d'échantillonnage par itération.

4. Résultats Expérimentaux

Les auteurs ont validé la PGP sur des tâches de contrôle discrètes et continues :

• Monde en Grille (FrozenLake) :

  • Tâche : Maximiser l'entropie tout en évitant les états "trous" (contrainte de sécurité).
  • Comparaison : A surpassé la méthode de Gradient de Politique Primal-Dual (PDPG) de l'état de l'art (Ying et al., 2025).
  • Observation : La PDPG présentait des oscillations autour de la frontière de la contrainte (comportement de faible regret), tandis que la PGP convergeait vers une politique stable satisfaisant strictement les contraintes tout en maintenant une entropie élevée.
  • Robustesse : La PGP a montré une robustesse face au paramètre de pénalité $\beta$ et au pas d'apprentissage $\eta$.

• Contrôle Continu (PointMass & SafeCartpole) :

  • PointMass (Imitation) : Exploration de l'environnement tout en restant proche d'une politique de référence SAC. La PGP a réussi à équilibrer exploration et imitation, la politique s'écartant de la référence à mesure que le budget de contrainte ($R_{max}$) augmentait.
  • SafeCartpole : Une tâche difficile de basculement où la position du chariot doit rester dans des limites de sécurité. La PGP a appris une stratégie de contrôle "bang-bang" pour faire basculer le pôle tout en adhérant strictement aux contraintes de position, démontrant une évolutivité vers des espaces continus de haute dimension.

5. Signification et Impact

• Avancée Théorique : Ce travail comble le fossé entre la théorie de l'optimisation convexe et le RL pratique en fournissant des garanties de convergence de la dernière itération pour des problèmes d'exploration contraints non convexes. Les méthodes précédentes ne pouvaient garantir que la politique déployée finale était sûre ou optimale.
• Applicabilité Pratique : La nature à boucle unique de la PGP la rend computationnellement efficace et plus facile à mettre en œuvre que les méthodes primales-duales, qui souffrent souvent de difficultés de réglage avec les variables duales.
• Généralisabilité : Le cadre s'étend au-delà du RL pour couvrir des problèmes d'optimisation contraints à convexité cachée en général, offrant une approche unifiée pour l'exploration critique pour la sécurité, l'apprentissage par imitation et les tâches à ressources contraintes.
• Réponse aux Besoins Réels : En traitant des contraintes convexes générales (sécurité, coût, imitation) avec des garanties rigoureuses, la méthode adresse un goulot d'étranglement critique dans le déploiement d'agents RL dans des scénarios réels où la sécurité et la faisabilité sont non négociables.

En résumé, l'article présente une solution rigoureuse, évolutive et théoriquement fondée à l'exploration contrainte, dépassant les approches heuristiques et les garanties de convergence faibles pour fournir un algorithme déployable avec des assurances d'optimalité globale.