Résumé Technique : Maîtriser les Malédictions de la Multi-Agence dans les Jeux de Markov Robustes à Grand Espace d'États par Approximation Linéaire de Fonction

1. Formulation du Problème

Ce travail aborde le défi de l'Apprentissage par Renforcement Multi-Agent (MARL) Robuste Distributionnellement dans des contextes à espaces d'états grands ou infinis. Les auteurs se concentrent sur les Jeux de Markov Linéaires Robustes (R-LMGs), qui combinent deux difficultés critiques :

1. Robustesse : Les agents doivent optimiser la performance dans le pire des cas lorsque l'environnement s'écarte d'un modèle nominal au sein d'un ensemble d'incertitude prescrit (défini spécifiquement par la distance de variation totale).
2. Évolutivité (La Malédiction de la Multi-Agence) : Dans le MARL standard, l'espace d'actions conjointe croît exponentiellement avec le nombre d'agents ($n$), entraînant une complexité d'échantillonnage qui évolue exponentiellement en $n$. Cela est exacerbé lorsque les espaces d'états sont grands ou infinis, rendant les méthodes tabulaires inapplicables.

Alors que les algorithmes existants prouvés efficaces pour les Jeux de Markov Robustes (RMGs) sont limités aux contextes tabulaires (espaces d'états/actions finis), et que le seul travail antérieur sur l'approximation linéaire de fonction (LFA) pour les RMGs repose sur des hypothèses restrictives (valeur minimale s'annulant) et souffre toujours de la malédiction de la multi-agence, cet article pose la question suivante : La malédiction de la multi-agence peut-elle être maîtrisée dans les jeux de Markov robustes à espaces d'états à grande échelle ?

2. Méthodologie

L'article propose des algorithmes prouvés efficaces en données pour les R-LMGs sous deux mécanismes distincts de collecte de données : un cadre de Modèle Génératif et un nouveau cadre Interactif en Ligne. Les deux cadres utilisent une Approximation Linéaire de Fonction Indépendante par Agent (LFA), où les fonctions de transition et de récompense pour chaque agent sont modélisées comme des fonctions linéaires d'un vecteur de caractéristiques $\phi(s, a_i)$, indépendamment des actions des autres agents.

2.1 Cadre du Modèle Génératif

Dans ce cadre, l'algorithme a accès à un simulateur capable de générer des échantillons à partir du noyau de transition nominal $P^0$ pour toute paire état-action.

• Algorithme : L-Robust-Q-FTRL.
• Innovation Clé (Réduction Infini-Fini) : Contrairement aux méthodes tabulaires qui nécessitent un échantillonnage exhaustif, les auteurs construisent un ensemble de support fini de paires état-action ($Y_i$) utilisant une distribution $\rho_i$ dérivée du Lemme 1 (basée sur la géométrie de l'espace de caractéristiques). Cela permet d'échantillonner uniquement à partir d'un sous-ensemble fini de taille $O(d^2)$ tout en garantissant la couverture de l'ensemble de l'espace d'états (potentiellement infini) via une régression ridge.
• Mécanisme : L'algorithme effectue une rétro-propagation. À chaque itération, il échantillonne à partir de l'ensemble fini construit, estime le modèle nominal (récompenses et transitions) via régression ridge, et met à jour la fonction Q robuste en utilisant la forme duale de l'équation de Bellman robuste. Il emploie une stratégie Follow-the-Regularized-Leader (FTRL) pour mettre à jour les politiques.

2.2 Cadre Interactif en Ligne

Ce cadre est plus pratique, où les agents interagissent avec l'environnement pour collecter des trajectoires. Un défi clé est que le noyau de transition réel du pire des cas est inconnu, et que les noyaux de l'ensemble d'incertitude ne satisfont pas nécessairement la structure linéaire supposée pour le noyau nominal.

• Algorithme : Online-L-Robust-Q-FTRL.
• Innovation Clé (Échantillonnage Hybride & Estimations Pessimistes) :
  • Approximation de l'Adversaire : Puisque le noyau du pire des cas réel est inconnu, l'algorithme ne peut pas échantillonner directement à partir de celui-ci. Au lieu de cela, il introduit une séquence d'estimations de valeur robustes pessimistes. Ces estimations sont utilisées pour interroger un « environnement adversaire approximatif » (Définition 1) au sein de l'ensemble d'incertitude.
  • Stratégie d'Échantillonnage Hybride : Pour maintenir la validité de l'estimation du modèle linéaire (qui ne s'applique qu'au noyau nominal), l'algorithme utilise un schéma d'échantillonnage hybride. Pour les $h-1$ premières étapes d'une trajectoire, les agents interagissent avec l'environnement adversaire approximatif (en utilisant les estimations pessimistes). À l'étape finale $h$, ils passent à l'échantillonnage à partir du noyau nominal. Cela préserve la distribution d'occupation état-action induite par la dynamique du pire des cas jusqu'à l'étape $h-1$ tout en garantissant que les données de transition finales proviennent du modèle nominal approximable linéairement.
  • Estimations Duales : L'algorithme maintient à la fois des estimations de valeur optimistes (pour les mises à jour de politique) et des estimations de valeur pessimistes (pour guider l'échantillonnage adversaire), s'écartant des jeux de Markov linéaires standards qui reposent généralement uniquement sur l'optimisme.

3. Contributions Clés

1. Briser la Malédiction de la Multi-Agence dans les Grands Espaces d'États : L'article fournit les premiers algorithmes prouvés efficaces en données pour les R-LMGs à grands espaces d'états (éventuellement infinis) qui brisent la malédiction de la multi-agence. La complexité d'échantillonnage et les bornes de regret dépendent polynomialement de la dimension des caractéristiques $d$ et de la taille maximale de l'espace d'actions individuel $\max_i A_i$, plutôt que de l'espace d'actions conjoint $\prod A_i$.
2. Garanties du Modèle Génératif : Dans le cadre du modèle génératif, l'algorithme proposé atteint un Équilibre de Corrélation Grossier (CCE) $\epsilon$-approché avec une complexité d'échantillonnage $\tilde{O}(H^9 d^3 / \epsilon^4)$. C'est la première garantie de ce type pour les R-LMGs sous un modèle génératif, indépendamment de la formulation de l'ensemble d'incertitude.
3. Protocole Interactif en Ligne : Les auteurs proposent un protocole en ligne pratiquement significatif où les agents peuvent échantillonner à partir de noyaux de transition au sein de l'ensemble d'incertitude (environnements adverses approximatifs). Ils prouvent que leur algorithme atteint un regret sous-linéaire de $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$.
4. Nouveauté Technique :
   • Réduction Infini-Fini : Une méthode pour échantillonner un sous-ensemble fini afin de généraliser aux espaces d'états infinis dans des contextes robustes.
   • Échantillonnage Hybride : Un mécanisme novateur pour estimer le modèle nominal tout en préservant la distribution d'occupation de l'environnement adversaire, surmontant la non-linéarité de l'ensemble d'incertitude.
   • Dualité Pessimiste-Optimiste : L'introduction d'estimations de valeur pessimistes pour approximer l'environnement adversaire en l'absence de valeurs robustes réelles.

4. Résultats et Garanties Théoriques

• Modèle Génératif (Théorème 2) : L'algorithme produit un CCE $\epsilon$-robuste avec une probabilité $1-\delta$ en utilisant $N_{all} \ge O(H^9 d^3 / \epsilon^4)$ échantillons. Dans la réduction tabulaire ($d = S \max A_i$), cela donne une complexité de $\tilde{O}(H^9 S^3 (\max A_i)^3 / \epsilon^4)$, qui est polynomiale en tous les paramètres, contrairement à la dépendance exponentielle des méthodes tabulaires robustes antérieures.
• Cadre en Ligne (Théorème 3) : L'algorithme atteint une borne de regret de $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$. Si le nombre d'épisodes $T$ satisfait $T > H^4 d^2 (\max_i A_i)^2 / \epsilon^2$, la sortie est un CCE $\epsilon$-robuste.
• Comparaison : Les résultats améliorent considérablement le seul travail existant sur les RMGs linéaires (Zheng et Lin, 2025), qui nécessitait une hypothèse restrictive de « valeur minimale s'annulant » et souffrait de la malédiction de la multi-agence ($d_{curse} = S \prod A_i$). La méthode proposée supprime ces restrictions et atteint une dépendance polynomiale par rapport au nombre d'agents.

5. Importance et Revendications

Les auteurs affirment que ce travail fournit les premiers algorithmes prouvés efficaces en données pour les jeux de Markov linéaires robustes à grands espaces d'états (éventuellement infinis) qui surmontent avec succès la malédiction de la multi-agence.

• Robustesse : Le travail étend la portée du MARL robuste des petits domaines tabulaires aux environnements continus à grande échelle pertinents pour des applications réelles telles que la conduite autonome, la robotique et les marchés financiers.
• Efficacité des Données : En brisant la dépendance exponentielle par rapport au nombre d'agents, les algorithmes rendent l'apprentissage robuste réalisable dans les systèmes multi-agents où l'espace d'actions conjoint serait autrement intraitable.
• Praticité : Le cadre interactif en ligne proposé, qui permet l'échantillonnage à partir d'environnements adverses approximatifs, s'aligne sur les paradigmes pratiques utilisés dans les applications critiques pour la sécurité (par exemple, transfert sim-to-real, entraînement adversaire) et garantit que le problème reste bien posé pour atteindre un regret sous-linéaire.

L'article conclut que la stratégie d'échantillonnage hybride proposée et l'utilisation d'estimations de valeur pessimistes sont des contributions techniques clés qui pourraient présenter un intérêt indépendant pour la recherche future en apprentissage par renforcement robuste.