Résumé Technique : Optimisation Bi-niveau sur les Points de Selle des Jeux de Markov à Somme Nulle

1. Formulation du Problème

Ce travail aborde l'Apprentissage par Renforcement Bi-niveau (BRL) dans des contextes où le problème de niveau inférieur (LI) n'est pas un Processus de Décision Markovien (MDP) standard à politique unique, mais plutôt un jeu de Markov à somme nulle min-max régularisé (MMZSMG).

Dans ce cadre hiérarchique :

• Niveau Supérieur (NS) : Un optimiseur sélectionne des paramètres $x$ (par exemple, des structures d'incitation ou une mise en forme des récompenses) pour minimiser un objectif $f(x, \phi, \psi)$.
• Niveau Inférieur (LI) : Deux agents opposés (joueur minimisant avec la politique $\pi_\phi$ et joueur maximisant avec la politique $\pi_\psi$) interagissent dans un jeu de Markov paramétré par $x$. Ils recherchent un équilibre de point de selle (Équilibre de Nash) qui résout :
  $$(\phi^*(x), \psi^*(x)) \in \arg\min_{\phi'} \max_{\psi'} J(x, \phi', \psi')$$
  où $J$ est la fonction de valeur régularisée du jeu.
• Objectif : L'objectif du NS est évalué à l'équilibre induit par le jeu du LI :
  $$\min_x F(x) \equiv f(x, \phi^*(x), \psi^*(x))$$

Le défi central réside dans le couplage stratégique entre les deux joueurs du LI. Contrairement aux MDP à politique unique, la réponse optimale d'un joueur dépend du comportement de l'autre, rendant le calcul des hypergradients (dérivées de l'objectif du NS par rapport à $x$) coûteux en calcul et structurellement complexe. Les méthodes BRL existantes reposent souvent sur des informations d'ordre deux (inverses de Hessiens) ou des hypothèses structurelles spécifiques aux MDP à politique unique, qui échouent à se généraliser à la structure min-max couplée des MMZSMG.

2. Méthodologie : PANDA

Les auteurs proposent PANDA (Descente-Ascent de Nikaido–Isoda Augmentée par Pénalité), un algorithme de gradient stochastique de politique d'ordre un conçu pour résoudre cette Optimisation Bi-niveau sur les Points de Selle des Jeux de Markov (BOSMG) sans nécessiter de dérivées d'ordre deux.

Composants Clés :

1. Reformulation Basée sur la Pénalité :
   Au lieu de calculer directement les hypergradients, PANDA reformule le problème bi-niveau contraint en utilisant la fonction Nikaido–Isoda (NI), $g(x, \phi, \psi)$, qui mesure l'écart entre la paire de politiques actuelle et l'Équilibre de Nash. Le problème contraint est transformé en un objectif pénalisé non contraint :
   $$L_\lambda(x, \phi, \psi) = f(x, \phi, \psi) + \lambda g(x, \phi, \psi)$$
   où $\lambda$ est un paramètre de pénalité.

2. Algorithme Itératif en Trois Étapes :
   L'algorithme fonctionne dans une boucle externe (mise à jour de $x$) et une boucle interne (mise à jour des politiques $\phi, \psi$) :

   • Étape 1 : Approximation de la Meilleure Réponse : L'algorithme approxime les politiques de meilleure réponse ($\tilde{\phi}, \tilde{\psi}$) pour les politiques actuelles en utilisant la descente de gradient de politique (pour le joueur minimisant) et l'ascent (pour le joueur maximisant). Cela permet d'estimer la fonction NI $g(x, \phi, \psi) \approx J(x, \phi, \tilde{\psi}) - J(x, \tilde{\phi}, \psi)$.
   • Étape 2 : Approximation du Sous-problème de Pénalité : L'algorithme met à jour les paramètres de politique $(\phi, \psi)$ par descente de gradient stochastique pour minimiser l'objectif substitut pénalisé $h(x, \phi, \psi) = \frac{1}{\lambda}f(x, \phi, \psi) + g(x, \phi, \psi)$. Cette étape conduit les politiques du LI vers le point de selle.
   • Étape 3 : Étape d'Hypergradient : Le paramètre du NS $x$ est mis à jour en utilisant une estimation de gradient stochastique de l'objectif pénalisé $L_\lambda$. Crucialement, ce gradient est calculé en utilisant des informations d'ordre premier issues des trajectoires échantillonnées, évitant ainsi l'inversion du Hessien du LI.

3. Estimation Stochastique :
   La méthode repose sur des simulations de Monte Carlo avec des horizons tronqués pour estimer les gradients des fonctions de valeur et l'écart NI, la rendant adaptée aux contextes à grande échelle basés sur des échantillons.

3. Contributions Théoriques

L'article établit des garanties de convergence rigoureuses pour PANDA sous des hypothèses standard (récompenses bornées, continuité de Lipschitz, et conditions de Polyak-Łojasiewicz (PŁ)).

• Convergence vers des Points Stationnaires : PANDA est prouvé pour converger vers un point $\epsilon$-stationnaire du problème bi-niveau original sans nécessiter d'hypothèses de convexité sur les objectifs du NS ou du LI.
• Bornes de Complexité :
  • Complexité d'Itération : $\tilde{O}(\epsilon^{-1})$ d'itérations externes.
  • Complexité d'Échantillon : $\tilde{O}(\epsilon^{-3})$.
    Ces taux correspondent aux bornes de l'état de l'art précédemment connues uniquement pour le BRL avec des MDP du LI à politique unique, malgré la complexité ajoutée du jeu min-max couplé.
• Propriétés Structurelles : Les auteurs prouvent de nouveaux résultats structurels pour les MMZSMG régularisés, notamment :
  • L'unicité de la paire de politiques d'équilibre sous régularisation générale.
  • La propriété PŁ non uniforme de la fonction NI par rapport aux paramètres de politique, qui est critique pour l'analyse de convergence.
  • Les propriétés de régularité et de continuité de Lipschitz de la fonction NI et de l'hyper-objectif.

4. Résultats Expérimentaux

Les auteurs valident PANDA par des expériences numériques dans deux contextes :

1. Problème de Conception d'Incitation Synthétique :

   • Configuration : Un concepteur du NS fixe des incitations pour influencer deux agents concurrents dans un petit MDP.
   • Lignes de Base : Comparé à Meta-Gradient (heuristique), Arbitrage Différentiable (DA, ordre deux), et PBRL (pénalité à politique unique).
   • Résultats : PANDA atteint la récompense d'incitation du NS la plus élevée et converge vers un écart d'Équilibre de Nash (NE) proche de zéro. Il se comporte de manière comparable à une ligne de base "Oracle" utilisant la programmation dynamique exacte et des informations d'ordre deux, surpassant significativement les autres lignes de base d'ordre un.

2. Jeu Sentinelle-Intrus :

   • Configuration : Un jeu sur grille où une sentinelle tente de capturer un intrus. L'objectif du NS est de minimiser les visites de la sentinelle dans des zones restreintes (dangereuses) tout en maintenant un jeu compétitif.
   • Échelle : Testé sur des grilles de $5 \times 5$ et $20 \times 20$.
   • Résultats : PANDA atteint systématiquement une perte du NS plus faible (moins de visites dans les zones restreintes) et des écarts NE plus petits par rapport à DA, PBRL et Meta-Gradient, démontrant une évolutivité et une robustesse dans des environnements plus grands et plus complexes.

5. Importance et Revendications

L'article revendique que PANDA est le premier algorithme stochastique d'ordre un avec des garanties de convergence prouvées pour les problèmes bi-niveau où le niveau inférieur est un MMZSMG régularisé.

• Combler le Fossé : Il adresse un fossé critique dans la littérature BRL où les méthodes existantes échouent à gérer efficacement les interactions multi-agents compétitives au niveau inférieur.
• Efficacité : En évitant les informations d'ordre deux (inversion de Hessien), PANDA reste computationnellement faisable pour les problèmes à grande échelle tout en atteignant des taux de complexité d'échantillon ($\tilde{O}(\epsilon^{-3})$) qui égalent les meilleurs résultats connus pour des contextes à politique unique plus simples.
• Applicabilité Pratique : La méthode est conçue pour des contextes basés sur des échantillons, la rendant directement applicable à des scénarios réels tels que la conception d'incitations, la conception de mécanismes et l'entraînement adversarial où les équilibres compétitifs sont centraux.

Les auteurs concluent que, bien que leur travail actuel se concentre sur les MMZSMG régularisés, le cadre offre une direction prometteuse pour étendre l'optimisation bi-niveau aux jeux min-max généraux et à des contextes multi-agents plus larges.