Minimax-Optimal Policy Regret in Partially Observable Markov Games

Résumé Technique : Regret de Politique Minimax-Optimal dans les Jeux de Markov Partiellement Observables

Formulation du Problème
Cet article traite de la prise de décision séquentielle dans des environnements partiellement observables face à des adversaires stratégiques et adaptatifs, modélisés comme des Jeux de Markov Partiellement Observables (POMG). Le défi central réside dans l'apprentissage de la dynamique latente du monde à partir d'observations partielles, tout en faisant face à un adversaire dont le comportement s'adapte à la stratégie de l'apprenant. Les notions standard de regret externe sont inadéquates dans ce contexte car la réponse de l'environnement dépend des actions passées de l'apprenant, créant des dépendances contrefactuelles. Par conséquent, l'article adopte le regret de politique (policy regret) comme métrique de performance, qui compare la récompense cumulative de l'apprenant à la meilleure politique fixe $\pi^*$, en supposant que l'adversaire aurait fini par converger vers une réponse stationnaire $R_\infty(\pi^*)$ si l'apprenant s'était engagé dans $\pi^*$ dès le début.

Le cadre implique deux joueurs : un apprenant et un adversaire, opérant tous deux sous observabilité partielle. L'apprenant observe des signaux $o^A$ et l'adversaire observe $o^B$, tandis que les transitions d'états latents se basent sur les actions des deux joueurs. L'adversaire est supposé être limité en mémoire par $m$ (m-memory bounded), ce qui signifie que sa réponse à n'importe quel épisode dépend uniquement des politiques de l'apprenant au cours des $m$ derniers épisodes.

Méthodologie et Cadre Algorithmique
Les auteurs proposent un algorithme d'Estimation du Maximum de Vraisemblance (MLE) optimiste par époques (Algorithme 1) pour minimiser le regret de politique. La méthodologie repose sur plusieurs composants structurels clés :

1. Décomposition Causale : Une contribution théorique centrale est la décomposition de l'opérateur observable $J_{\xi,\pi}^h$ en deux composantes distinctes :

   • Un canal du monde (world channel) $W_h^\theta$, qui dépend uniquement de la dynamique du monde (noyaux de transition et d'émission) et est indépendant du modèle de réponse de l'adversaire.
   • Un opérateur d'agrégation de l'adversaire $G_{\Phi,\pi}^h$, qui dépend de la fonction de réponse de l'adversaire et de la politique de l'apprenant, mais est indépendant du paramètre du monde $\theta$.
     Cette factorisation permet à l'algorithme de séparer l'estimation de la dynamique du monde du contrôle des réponses de l'adversaire.

2. Hypothèses Structurelles :

   • Adversaire Posterior-Lipschitzien : La réponse de l'adversaire varie de manière fluide avec la politique de l'apprenant. Crucialement, cette lissité est définie par rapport à une mesure de référence fixe $\mu_{ref}$ (indépendante de la stratégie réelle de l'adversaire) pour éviter les dépendances circulaires dans la définition.
   • Révélation Faible Multi-étapes : Les observations sont suffisamment informatives sur les états latents sur une fenêtre de $\kappa$ étapes, garantissant que les écarts dans la dynamique du monde sont détectables.
   • Dimension d'Eluder : La complexité de la classe de modèles conjointe monde-adversaire est mesurée par la dimension d'Eluder agrégée uniforme ($d_E$).

3. Exécution par Époques : L'algorithme divise le temps en époques à croissance géométrique ($T_e = 2^e$). Au sein de chaque époque :

   • Une politique unique $\pi_e$ est sélectionnée de manière optimiste à partir d'un ensemble de confiance construit cumulativement à partir des données passées.
   • Une phase de préchauffage (warm-up phase) ($m-1$ épisodes) permet à l'adversaire à mémoire $m$ de se stabiliser vers sa réponse stationnaire pour la politique actuelle.
   • La politique est exécutée pendant $T_e$ épisodes de collecte de données.
     Cette structure garantit que l'apprenant ne déploie que $O(\log T)$ politiques distinctes sur $T$ épisodes, ce qui est critique pour contrôler le coût de comparaison des réponses de l'adversaire entre différentes politiques.

Résultats Clés
L'article établit une borne supérieure minimax-optimale sur le regret de politique et une borne inférieure correspondante.

• Borne Supérieure : Sous les hypothèses énoncées, l'algorithme atteint un regret de politique de :
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  où $\bar{\beta}_T = H\beta_T + H^2 \log T$. Le terme $H^2 \log T$ représente le « coût de transport » de la comparaison des réponses de l'adversaire à travers les $O(\log T)$ politiques distinctes déployées. La dépendance en $\sqrt{T}$ est obtenue grâce à la structure d'époques géométriques ; le déploiement de $O(\sqrt{T})$ politiques (comme dans le lotissement plat ou flat batching) entraînerait un taux de regret de $T^{3/4}$ dû à l'accumulation des coûts de transport.

• Borne Inférieure : Les auteurs prouvent une borne inférieure de $\Omega(\sqrt{d_E T})$ pour tout algorithme, même dans les POMG totalement révélateurs avec des adversaires sans mémoire. Cela confirme que la dépendance en $\sqrt{T}$ et $d_E$ dans la borne supérieure est optimale à l'exclusion des facteurs dépendant du problème ou logarithmiques.

• Extensions : Le cadre est étendu pour gérer :

  • Horizons Inconnus : L'algorithme s'adapte à un $T$ inconnu sans modification.
  • Adversaires à Mémoire Décroissante : Les résultats sont valables pour des adversaires ayant une mémoire décroissant géométriquement, avec un coût de préchauffage proportionnel à $O(\frac{H \log^2 T}{1-\gamma})$.
  • Contextes Tabulaires : Des bornes explicites sont dérivées en termes de tailles d'espaces d'états, d'actions et d'observations.

Signification et Revendications
L'article prétend fournir un traitement théorique complet de la minimisation du regret de politique dans les POMG face à des adversaires adaptatifs. Sa signification principale réside dans la démonstration qu'un apprentissage efficace (avec un regret de $\sqrt{T}$) est possible dans ce cadre complexe, à condition que la réponse de l'adversaire soit lisse (Posterior-Lipschitzienne) et que les observations soient faiblement révélatrices.

Les auteurs soulignent deux innovations techniques spécifiques permettant ce résultat :

1. Formulation Non-Circulaire : En définissant la condition Posterior-Lipschitzienne par rapport à une mesure de référence fixe, ils évitent les problèmes de circularité présents dans les formulations antérieures où la métrique de lissité dépendait de la contrainte imposée à l'adversaire.
2. Coût de Transport Logarithmique : En limitant l'apprenant à $O(\log T)$ politiques distinctes via la structure par époques, ils garantissent que le coût de transport des erreurs de réponse de l'adversaire reste logarithmique, préservant ainsi le taux optimal de $\sqrt{T}$. Cela contraste avec les approches de lotissement plat (flat-batching) qui, selon les auteurs, mènent à des taux sous-optimaux de $T^{3/4}$ en raison d'une croissance polynomiale des coûts de transport.

Ce travail est présenté comme une étape fondamentale pour la conception d'algorithmes d'apprentissage dotés de garanties de performance fiables dans les environnements multi-agents où les agents sont à la fois partiellement observables et stratégiquement adaptatifs. Les auteurs notent que si les garanties statistiques sont établies, la tractabilité computationnelle de l'étape de planification optimiste reste une direction ouverte pour des travaux futurs, particulièrement pour les classes de modèles généraux.