De la récurrence de Poincaré à la convergence dans les jeux à information imparfaite : Trouver l'équilibre par régularisation

Résumé :

Dans cet article, nous étudions la dynamique du suivi du leader régularisé dans les jeux séquentiels à information imparfaite (IIG). Nous généralisons les résultats existants de la récurrence de Poincaré des jeux de forme normale aux jeux d'information imparfaits à deux joueurs à somme nulle et à d'autres paramètres de jeux séquentiels. Nous étudions ensuite comment l'adaptation de la récompense (en ajoutant un terme de régularisation) du jeu peut donner de fortes garanties de convergence dans les jeux monotones. Nous continuons en montrant comment cette technique d'adaptation de la récompense peut être exploitée pour construire des algorithmes qui convergent exactement vers l'équilibre de Nash. Enfin, nous montrons comment ces idées peuvent être directement utilisées pour construire des algorithmes sans modèle de pointe pour les jeux à somme nulle et à deux joueurs à information imparfaite (IIG).