Résumé technique : Apprentissage indépendant des équilibres de Nash dans les jeux de Markov partiellement observables à potentiel avec dynamiques découplées

Contexte du problème

Ce travail aborde le défi de l'apprentissage des équilibres de Nash dans les jeux de Markov partiellement observables (POMG). Dans l'apprentissage par renforcement multi-agents (MARL) standard, on suppose souvent que les agents ont un accès complet à l'état de l'environnement. Cependant, dans des scénarios pratiques tels que la conduite autonome ou le contrôle multi-robots, les agents opèrent sous une observabilité partielle, ne recevant que des observations bruitées ou limitées.

Le problème général du calcul des équilibres de Nash dans les POMG est intraitable sur le plan computationnel. Les approches antérieures reposent souvent sur une coordination centralisée ou un partage d'informations, ce qui introduit une « malédiction de la multi-agentivité » où la complexité croît exponentiellement avec le nombre de joueurs ($N$). De plus, même dans les processus de décision de Markov partiellement observables (POMDP) à agent unique, les politiques optimales dépendent généralement de l'historique complet des actions et des observations, entraînant une complexité statistique et computationnelle exponentielle.

Les auteurs se concentrent sur une sous-classe spécifique de POMG caractérisée par deux hypothèses structurelles :

1. Dynamiques découplées : Bien que les agents soient couplés par leurs fonctions de récompense, leurs dynamiques de transition d'état et leurs noyaux d'observation sont indépendants entre les joueurs. Autrement dit, la transition d'état de l'agent $i$ dépend uniquement de son propre état et de sa propre action, et non des états ou des actions des autres agents.
2. Structure de potentiel de Markov : Le jeu de Markov entièrement observé sous-jacent (si les agents pouvaient observer l'état réel) est un jeu de potentiel de Markov. Cela implique l'existence d'une fonction de potentiel telle que les variations de l'utilité d'un agent dues à un changement de politique reflètent les variations du potentiel global.

L'objectif est de concevoir un algorithme d'apprentissage indépendant où les agents ne communiquent rien, n'observent que leurs propres historiques locaux, et convergent vers un équilibre de Nash approximatif sans subir la malédiction de la multi-agentivité.

Méthodologie

L'approche proposée comble le fossé entre le POMG intraitable et un modèle de substitution traitable grâce aux étapes suivantes :

1. Approximation par jeu de Markov de super-états

Pour gérer l'observabilité partielle sans maintenir un historique infini, les auteurs approximent le POMG en utilisant un jeu de Markov de super-états ($G_m$).

• Politiques à fenêtre finie : Au lieu de politiques dépendant de l'historique complet, les agents utilisent des politiques basées sur une fenêtre finie des $m$ dernières étapes d'action-observation (le « super-état »).
• Construction : L'espace d'états de $G_m$ est constitué de ces fenêtres d'historique tronquées. Le noyau de transition et les récompenses dans $G_m$ sont définis en marginalisant sur les états latents cohérents avec les fenêtres observées, en utilisant un état de croyance dérivé de la distribution initiale et des dynamiques du modèle.
• Stabilité du filtre : La validité de cette approximation repose sur une hypothèse de stabilité du filtre. Cette hypothèse postule que l'influence du prior initial sur la croyance a posteriori décroît exponentiellement au fil du temps (contrôlée par un facteur de contraction $\rho$). Dans ces conditions, les politiques basées sur des fenêtres finies fournissent des garanties d'approximation suffisantes pour le POMG original.

2. Propriétés structurelles

Les auteurs établissent deux propriétés théoriques critiques du jeu de Markov de super-états $G_m$ :

• Préservation de l'équilibre : Ils prouvent qu'un équilibre de Nash $\epsilon$-approché dans $G_m$ induit un équilibre de Nash $(\epsilon + \delta)$-approché dans le POMG original, où l'erreur $\delta$ dépend de la taille de la fenêtre $m$ et du paramètre de stabilité du filtre $\rho$.
• Structure de quasi-potentiel : Bien que $G_m$ ne soit pas un jeu de potentiel exact en raison de l'erreur d'approximation, il est démontré qu'il s'agit d'un jeu de Markov de quasi-potentiel. L'écart par rapport à une véritable structure de potentiel est borné par un terme proportionnel à l'erreur d'approximation. Cette propriété structurelle est cruciale pour permettre des garanties de convergence pour les algorithmes d'apprentissage indépendant.

3. Algorithme d'apprentissage indépendant

S'appuyant sur la structure de quasi-potentiel, les auteurs proposent un algorithme d'apprentissage indépendant (Algorithme 1) qui fonctionne comme suit :

• Protocole de jeu contre soi-même : Les agents interagissent avec l'environnement sur $K$ itérations (épisodes). À chaque itération, les agents suivent une politique fixe, collectent des trajectoires d'actions, d'observations et de récompenses locales, et mettent à jour leurs politiques individuellement. Aucune information n'est partagée entre les agents.
• Estimation du modèle : Les agents estiment les probabilités de transition et les fonctions de récompense du jeu de Markov de super-états $G_m$ en utilisant les fréquences empiriques de leurs trajectoires locales.
• Itération de politique douce : Les agents effectuent une forme d'itération de politique douce (ou Q-learning avec régularisation) sur le jeu de super-états estimé. Ils mettent à jour leurs politiques pour maximiser les valeurs Q estimées, en utilisant un calendrier de pas assurant la convergence.

Contributions clés

1. Garanties d'approximation théoriques : L'article établit que, sous la stabilité du filtre, le jeu de Markov de super-états $G_m$ préserve les équilibres de Nash du POMG original avec des bornes d'erreur explicites. Cela étend les résultats d'approximation des POMDP à agent unique au cadre multi-agent.
2. Structure de quasi-potentiel : Les auteurs prouvent que le jeu de Markov de super-états hérite d'une structure de quasi-potentiel des dynamiques découplées sous-jacentes. Cela permet d'appliquer des techniques d'apprentissage indépendant conçues pour les jeux de potentiel au cadre partiellement observable.
3. Algorithme d'apprentissage indépendant : Un algorithme sans communication est présenté, où les agents apprennent uniquement à partir d'observations locales. L'algorithme combine l'estimation de modèle à fenêtre finie avec l'itération de politique douce.
4. Analyse de complexité : Le résultat théorique principal (Théorème 1) prouve que l'algorithme converge vers un équilibre de Nash $\epsilon$-approché avec une complexité en échantillons et computationnelle quasi-polynomiale. Crucialement, cette complexité ne croît pas exponentiellement avec le nombre de joueurs $N$, brisant ainsi la « malédiction de la multi-agentivité » pour cette classe spécifique de jeux.

Résultats

L'article fournit une analyse de convergence rigoureuse montrant que, avec des choix appropriés de la taille de la fenêtre $m$, du nombre d'épisodes $T$ et du nombre d'itérations $K$, la politique conjointe converge vers un équilibre de Nash $\epsilon$-approché avec une forte probabilité ($1-\delta$).

La complexité en échantillons est bornée par :
$$O\left( \left( \frac{NHAO}{\beta \alpha \epsilon} \right)^{O(\rho^{-1} \log(A/(\beta \epsilon)))} \log(1/\delta) \right)$$
où $A$ et $O$ sont les tailles maximales des espaces d'action et d'observation, $H$ est l'horizon, et $\alpha, \beta, \rho$ sont des paramètres liés à la visite des états, au bruit d'observation et à la stabilité du filtre, respectivement.

La conclusion principale est que la complexité est quasi-polynomiale par rapport aux paramètres du problème et linéaire (ou polynomiale) par rapport au nombre de joueurs, évitant ainsi la dépendance exponentielle à $N$ trouvée dans l'apprentissage général des POMG ou les approches centralisées.

Importance et affirmations

Les auteurs affirment que ce travail représente la première méthode d'apprentissage indépendant prouvable pour les équilibres de Nash dans les jeux de Markov partiellement observables.

• Surmonter la malédiction de la multi-agentivité : En exploitant les dynamiques découplées et les structures de potentiel, la méthode évite l'échelle exponentielle sur le nombre de joueurs qui affecte les approches centralisées ou de partage d'informations (par exemple, [30]).
• Relier la théorie à agent unique et multi-agent : Le travail étend le cadre de « stabilité du filtre », précédemment réussi dans les POMDP à agent unique (par exemple, [11, 13]), au domaine multi-agent, démontrant que des hypothèses structurelles similaires peuvent permettre un apprentissage efficace dans des contextes multi-agents complexes.
• Pertinence pratique : L'hypothèse de dynamiques découplées est motivée par des applications réelles telles que les réseaux sans fil, les réseaux intelligents d'énergie et les systèmes multi-robots, où les agents ont souvent des évolutions d'état indépendantes mais des récompenses couplées.
• Modestie : Les auteurs reconnaissent que leurs résultats sont limités aux POMG avec des dynamiques découplées et des structures de potentiel. Ils notent que la compréhension de la frontière entre les régimes traitables et intraitables dans les POMG reste une direction ouverte. De plus, la dépendance à l'hypothèse 4 (visite suffisante des états) est une limitation, et son assouplissement vers des conditions de désaccord de distribution plus faibles est suggéré comme travail futur.

En résumé, l'article fournit une fondation théorique pour un apprentissage indépendant évolutif dans une classe spécifique mais pratiquement pertinente de systèmes multi-agents partiellement observables, offrant des garanties quasi-polynomiales là où les méthodes précédentes échouaient soit à fournir des garanties, soit à souffrir d'une complexité exponentielle.