Résumé technique : Optimisation Primal-Duale de la Politique pour les CMDP Linéaires avec Pertes Adversariales

Contexte du problème

Ce papier aborde le défi de l'Apprentissage par Renforcement (RL) Sécurisé dans des environnements où les contraintes de sécurité doivent être satisfaites malgré des perturbations adversariales. Plus précisément, les auteurs considèrent des Processus de Décision Markoviens Contraints (CMDP) Linéaires Adversariales à Horizon Fini.

Le cadre est défini par le tuple $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, où :

• Pertes Adversariales : Les fonctions de perte $f^k = \{f^k_h\}$ sont choisies arbitrairement par un adversaire au début de chaque épisode $k$ (retour d'information complet). Ces pertes ne sont pas tirées d'une distribution fixe.
• Coûts Stochastiques : Les fonctions de coût $g^k = \{g^k_h\}$ sont échantillonnées de manière i.i.d. à partir d'une distribution fixe $G$ (retour d'information en bande), représentant les contraintes de sécurité.
• Structure Linéaire : Les noyaux de transition, les fonctions de perte et les fonctions de coût possèdent une structure linéaire par rapport à une application de caractéristiques connue $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Objectif : L'agent cherche une politique qui minimise la perte espérée cumulative tout en garantissant que le coût cumulé espéré ne dépasse pas un budget $b$.

La performance est mesurée par le Regret (différence de perte cumulative par rapport à la politique optimale) et la Violation de Contrainte (coût excédentaire cumulatif par rapport au budget). L'objectif est d'obtenir des bornes sous-linéaires pour ces deux métriques.

Méthodologie

Les auteurs proposent un algorithme d'Optimisation Primal-Duale de la Politique (Algorithme 1) conçu pour gérer l'interaction entre les pertes adversariales et les contraintes stochastiques dans un cadre d'approximation de fonction linéaire. L'algorithme intègre quatre composants principaux :

1. Initialisation d'Époque et Contraction des Caractéristiques :
   L'algorithme fonctionne par époques. Une époque commence lorsque le déterminant de la matrice de conception $\Lambda^k_h$ augmente d'un facteur multiplicatif. Lors de l'initialisation, la politique est réinitialisée à une politique uniforme, et la variable duale est réinitialisée à zéro. Crucialement, l'algorithme emploie une contraction des caractéristiques, réduisant la caractéristique originale $\phi$ à l'aide d'une fonction sigmoïde pour empêcher les estimations de la fonction Q de s'étendre de manière incontrôlable. Cette technique, adaptée de Cassel & Rosenberg (2024), simplifie la représentation de la politique pour les arguments de nombre de couverture.

2. Exécution de la Politique et Estimation :
   Dans chaque épisode, l'agent exécute des actions basées sur la politique actuelle, observe la perte adversarielle et le coût stochastique, et met à jour la matrice de conception. Il estime ensuite les paramètres des fonctions de perte et de coût, et calcule les estimations de la fonction Q ($\hat{Q}$) et les estimations de la fonction de valeur ($\hat{V}$) en utilisant les caractéristiques contractées et des bonus optimistes.

3. Mélange Périodique de la Politique :
   Une innovation centrale est le mélange périodique de la politique. Au lieu de mélanger la politique (en la perturbant vers une politique uniforme) à chaque épisode, l'algorithme applique le mélange uniquement tous les $K^B$ épisodes (où $B=3/4$).

   • Motivation : Un mélange fréquent est nécessaire pour borner la variable duale (via une analyse de dérive) mais augmente la complexité de la classe de politiques (nombre de couverture). Le mélange périodique équilibre ces exigences concurrentes.
   • Mécanisme : Tous les $K^{3/4}$ épisodes, la politique actuelle $\hat{\pi}^k$ est mélangée avec la politique uniforme $\pi_{unif}$ via une combinaison convexe : $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Mise à Jour Duale Régularisée :
   La variable duale $Y^k$ (associée à la contrainte de coût) est mise à jour en utilisant une étape d'ascension de gradient régularisée :
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   Les termes de régularisation ($-4\alpha\eta H^3 Y^k$ et les constantes) sont conçus pour ramener la variable duale vers zéro, permettant une analyse de dérive de Lyapunov pour borner $Y^k$ sans dépendre des hypothèses de dualité forte qui échouent dans les contextes adversariaux.

5. Politiques Softmax LogSumExp Pondérées :
   La classe de politiques résultante est un softmax LogSumExp pondéré. En raison du mélange périodique, la politique n'est pas une simple exponentielle de la somme des fonctions Q, mais une somme pondérée d'exponentielles de sommes partielles d'estimations de fonctions Q. Cette structure permet à la politique de s'adapter aux pertes choisies de manière adversarielle tout en maintenant un nombre de couverture traitable.

Contributions Clés

1. Premières Bornes Sous-Linéaires pour les CMDP Linéaires Adversariaux :
   Le papier présente le premier algorithme à atteindre des bornes de regret et de violation de contrainte sous-linéaires dans le cadre des CMDP linéaires avec pertes adversariales et coûts stochastiques. Les bornes sont de l'ordre de $\tilde{O}(K^{3/4})$, où $K$ est le nombre d'épisodes.

2. Nouvel Argument de Nombre de Couverture :
   Les auteurs établissent un nouvel argument de nombre de couverture pour les politiques softmax LogSumExp pondérées. Contrairement aux politiques softmax standard où les poids sont uniformes, le processus de mélange introduit des paramètres de poids variables $\zeta_i$. Les auteurs prouvent que le logarithme du nombre de couverture pour cette classe croît comme $\tilde{O}(n^2 d^2)$, où $n$ est le nombre d'étapes de mélange et $d$ est la dimension des caractéristiques. Ce résultat est non trivial car les paramètres de poids dépendent à la fois du paramètre de mélange et des estimations de la fonction Q.

3. Composants Algorithmiques pour le Contrôle :
   Le papier introduit deux nouveaux composants pour contrôler conjointement le nombre de couverture et la variable duale :

   • Mélange Périodique de la Politique : Régule la fréquence du mélange pour empêcher le nombre de couverture de devenir trop grand (ce qui se produirait avec $O(K)$ étapes de mélange) tout en se produisant suffisamment souvent pour borner la variable duale.
   • Mise à Jour Duale Régularisée : Une nouvelle règle de mise à jour qui incorpore un terme de régularisation pour faciliter l'analyse basée sur la dérive, permettant de borner la variable duale en l'absence de dualité forte.

Résultats

Garanties Théoriques :
Sous la condition de Slater (Hypothèse 1) et en supposant $H^2 \leq K$, avec une probabilité d'au moins $1-\delta$, l'algorithme atteint :

• Regret : $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Violation de Contrainte : $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Les deux métriques évoluent de manière sous-linéaire avec $K$ (spécifiquement $K^{3/4}$), indiquant que le regret moyen et la violation de contrainte moyenne convergent vers zéro à mesure que le nombre d'épisodes augmente.

Expériences Numériques :
L'algorithme a été évalué sur un CMDP de planification de tâches modifié avec des pertes adversariales. Sur $100\,000$ épisodes :

• Regret : A augmenté de manière sous-linéaire, confirmant la borne théorique.
• Violation de Contrainte : A initialement augmenté rapidement mais a convergé vers zéro après environ 45 000 épisodes, validant la capacité de l'algorithme à satisfaire les contraintes de sécurité à long terme.

Importance et Revendications

Le papier revendique être le premier algorithme prouvé efficace pour le RL sécurisé avec approximation de fonction linéaire dans des contextes adversariaux. Son importance réside dans le fait de combler le fossé entre :

1. CMDP Adversariaux Tabulaires : Les travaux précédents (par exemple, Qiu et al., 2020) gèrent les contextes adversariaux mais étaient limités à de petits espaces d'états finis.
2. CMDP Linéaires Stochastiques : Les travaux précédents (par exemple, Ghosh et al., 2022) gèrent de grands espaces d'états mais supposent des environnements stationnaires (stochastiques).

En introduisant la politique softmax LogSumExp pondérée et la stratégie de mélange périodique, les auteurs démontrent qu'il est possible de gérer de grands espaces d'états (via l'approximation linéaire) et des pertes adversariales simultanément. Le papier note modestement que bien que $\tilde{O}(K^{3/4})$ soit atteint, la borne optimale $\tilde{O}(\sqrt{K})$ reste une question ouverte pour ce cadre spécifique, en particulier concernant le compromis entre les étapes de mélange et les nombres de couverture. Le travail met également en évidence la difficulté d'étendre les mises à jour duales basées sur la mesure d'occupation aux méthodes basées sur la politique dans les CMDP linéaires adversariaux, justifiant l'approche proposée d'optimisation primal-duale de la politique.