Résumé technique : Minimisation du regret avec des adversaires adaptatifs dans les jeux répétés

Énoncé du problème

L'article traite du défi de la minimisation du regret dans les jeux répétés où les adversaires sont adaptatifs, c'est-à-dire qu'ils peuvent ajuster leurs stratégies en fonction de l'historique de jeu. Les auteurs soutiennent que la métrique standard du regret externe dans l'apprentissage en ligne est insuffisante pour ce contexte. Le regret externe suppose que les séquences de pertes sont des fonctions des pas de temps uniquement, traitant implicitement les adversaires comme non adaptatifs. Dans un cadre de théorie des jeux, cependant, la réponse d'un adversaire à l'action d'un joueur peut modifier les pertes futures. Par conséquent, minimiser le regret externe dans les jeux répétés conduit souvent à des équilibres sous-optimaux (par exemple, le résultat « défection-défection » dans le Dilemme du Prisonnier Itéré) et ne parvient pas à capturer des stratégies coopératives efficaces comme le « tit-for-tat », qui peut pourtant souffrir d'un regret externe linéaire malgré des utilités plus élevées.

Les alternatives existantes, telles que le Regret de Politique (qui prend en compte la mémoire dans les fonctions de perte) ou le Regret de Réponse (qui considère des stratégies mixtes dépendantes de l'historique), présentent des limitations significatives. Le Regret de Politique repose souvent sur des hypothèses restrictives de mémoire $m$-bornée qui ne tiennent pas dans les jeux répétés où les déviations précoces peuvent avoir des effets à long terme. Le Regret de Réponse, bien que théoriquement solide, nécessite un espace de stratégies exponentiellement grand, ce qui le rend informatiquement intractable.

Méthodologie

1. Regret de Politique Répété (RP-Regret)

Les auteurs introduisent le Regret de Politique Répété (RP-Regret), une nouvelle métrique de performance native aux jeux répétés.

• Définition : Le RP-Regret mesure la différence entre l'utilité cumulée réalisée et la meilleure utilité cumulée a posteriori, en supposant que tous les joueurs (y compris l'adversaire) répondent de manière adaptative à l'historique de jeu.
• Distinction clé : Contrairement au regret externe, une déviation vers une stratégie de comparaison à l'instant $t$ affecte non seulement la perte à $t$, mais aussi toutes les pertes ultérieures, car les adversaires adaptatifs changent leurs stratégies en réponse au nouvel historique.
• Conditions nécessaires : L'article établit que l'obtention d'un RP-Regret sous-linéaire est impossible sans contraintes spécifiques. Deux conditions nécessaires sont identifiées :
  1. Variation sous-linéaire : La stratégie de comparaison ne doit pas changer trop rapidement au fil du temps.
  2. Mémoire imparfaite : Les joueurs (et la stratégie de comparaison) ne peuvent pas avoir un rappel parfait de l'historique complet. Plus précisément, l'article propose l'Exponentiel Decay Memory (EDM - Mémoire à Décroissance Exponentielle), où l'influence de l'historique passé sur la stratégie actuelle décroît exponentiellement. Cela empêche le « passage d'état » via les actions et garantit que la longueur effective de la mémoire ne croît que logarithmiquement par rapport aux exigences de précision.

2. Algorithmes de minimisation

Puisque la fonction objectif pour le RP-Regret est non convexe en raison du produit des stratégies au fil du temps, l'article propose trois approches pour la minimiser :

• Approche par Oracle : En supposant l'accès à un oracle d'optimisation non convexe (comme dans les travaux antérieurs sur l'apprentissage non convexe en ligne), les auteurs montrent qu'un RP-Regret sous-linéaire est réalisable sous les conditions nécessaires (Variation sous-linéaire et EDM). Cela sert de base théorique.
• Regret de Politique Répété Local (LRP-Regret) : Pour assurer la tractabilité computationnelle, les auteurs proposent une métrique de substitution, le LRP-Regret. Cette métrique restreint les déviations à un seul pas de temps (déviation locale) plutôt qu'à un changement global de stratégie.
  • Convexification : L'espérance de la perte à un instant donné, lorsqu'elle est vue comme une fonction d'une déviation à un seul pas, devient linéaire (et donc convexe) par rapport à la stratégie à ce pas.
  • Algorithme : Les auteurs proposent un algorithme de Descente de Gradient Projetée (PGD) pour minimiser le LRP-Regret. Les garanties théoriques montrent que si les adversaires satisfont la condition EDM, l'algorithme atteint un LRP-Regret sous-linéaire.
• Reformulation en Jeu de Markov : Pour le cas où les adversaires changent également de stratégie lentement (satisfaisant la condition de Variation sous-linéaire), les auteurs reformulent le jeu répété avec une mémoire bornée en un Jeu de Markov à horizon infini.
  • Mesures d'occupation : Au lieu d'optimiser la stratégie directement, l'algorithme optimise la mesure d'occupation (fréquences de visite état-action). Cela transforme le problème non convexe en un problème convexe dans l'espace des mesures d'occupation.
  • Contraintes : L'algorithme gère des contraintes variant dans le temps pour s'assurer que la mesure d'occupation correspond à un profil de stratégie produit valide contre les adversaires adaptatifs.
  • Résultat : Cette approche minimise directement le RP-Regret original (et non seulement son substitut) et atteint un regret sous-linéaire.

Résultats Clés

1. Résultats de dureté : L'article prouve que sans les conditions de variation sous-linéaire et de mémoire imparfaite (spécifiquement l'EDM), la minimisation du RP-Regret est impossible (résultant en un regret linéaire).
2. Garanties algorithmiques :
   • L'algorithme de minimisation du LRP-Regret atteint une borne de regret de $\tilde{O}(|A|^{m+1}\sqrt{P_T/T})$, où $P_T$ est la variation du comparateur et $m$ est la longueur de la mémoire.
   • L'algorithme basé sur le Jeu de Markov atteint un RP-Regret sous-linéaire lorsque les adversaires changent de stratégie lentement.
3. Calcul d'équilibre : Les auteurs établissent un lien théorique entre la minimisation de ces notions de regret et le calcul d'équilibres.
   • Si tous les joueurs minimisent le RP-Regret (ou le LRP-Regret), les stratégies moyennes temporelles convergent vers un Équilibre de Nash de Sous-Jeux Parfait (SPNE) approximatif ou un Équilibre Corrélation Grossière de Sous-Jeux Parfait (SPCCE) avec déviation bornée.
   • Plus précisément, pour les jeux répétés à l'infini, la trajectoire converge vers un équilibre qui est robuste aux déviations à l'intérieur d'un certain budget de variation.
4. Validation Expérimentale : Les expériences sur le jeu Stag-Hunt démontent que la minimisation du LRP-Regret permet aux joueurs de converger vers l'équilibre coopératif (Cerf-Cerf) avec une utilité plus élevée plus fréquemment que les méthodes minimisant le regret externe, qui se retrouvent souvent bloquées dans l'équilibre dominant le risque mais de plus faible utilité (Lièvre-Lièvre).

Signification et Revendications

L'article affirme fournir une métrique de regret native et naturelle pour les jeux répétés qui tient compte de l'adaptativité de l'adversaire sans imposer les hypothèses restrictives de mémoire bornée des travaux antérieurs sur le Regage de Politique, ni l'intractabilité informatique du Regret de Réponse.

• Contribution Théorique : Il identifie les limites fondamentales (conditions nécessaires) pour l'apprentissage dans les environnements adaptatifs et fournit les premiers algorithmes prouvables pour minimiser une métrique de regret de théorie des jeux qui permet des comparateurs dynamiques et des adversaires adaptatifs.
• Implication Pratique : En minimisant le RP-Regret (ou son substitut convexe LRP-Regret), les joueurs peuvent apprendre à coopérer dans des jeux comme le Dilemme du Prisonnier Itéré et le Stag-Hunt, atteignant des utilités plus élevées que celles dictées par les équilibres de Nash standards dans les jeux à un coup.
• Sélection d'Équilibre : Ce travail suggère que la minimisation du regret dans les jeux répétés peut servir de mécanisme pour sélectionner de meilleurs équilibres (par exemple, coopératifs) qui ne sont pas nécessairement l'Équilibre de Nash unique du jeu à un coup sous-jacent.

Les auteurs restent modestes quant à la complexité computationnelle, reconnaissant que la nature non convexe du problème nécessite généralement des oracles ou des hypothèses structurelles spécifiques (comme des adversaires changeant lentement) pour être traitable. Ils présentent leur travail comme ouvrant de nouvelles directions de recherche pour l'étude de notions d'équilibres plus faibles et de la sélection d'équilibres via la minimisation du regret.