2025-11-18T08:49:13.884110

Perturbing Best Responses in Zero-Sum Games

Dziwoki, Horcik
This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.
academic

Perturber les Meilleures Réponses dans les Jeux à Somme Nulle

Informations Fondamentales

Résumé

Cet article étudie l'impact des perturbations sur les algorithmes basés sur la meilleure réponse, utilisés pour approximer l'équilibre de Nash dans les jeux à somme nulle, en se concentrant particulièrement sur les algorithmes Double Oracle et Fictitious Play. L'étude suppose que l'oracle calculant la meilleure réponse perturbe les utilités avant de sélectionner la meilleure réponse. La recherche montre que l'utilisation d'un tel oracle perturbé peut réduire le nombre d'itérations pour les deux algorithmes. Dans certains cas, une perturbation appropriée peut garantir que le nombre d'itérations attendu est de niveau logarithmique. Bien que la perturbation des utilités nécessite de parcourir toutes les stratégies pures, ce qui est coûteux en calcul, l'étude démontre que pour les jeux où les stratégies pures possèdent une structure interne (comme les jeux stochastiques partiellement observables), la perturbation peut être mise en œuvre efficacement.

Contexte et Motivation de la Recherche

Problème Central

Le calcul de l'équilibre de Nash dans les jeux bipartites à somme nulle avec des espaces de stratégies de grande taille est un problème intensif en calcul. Bien qu'il soit théoriquement établi qu'il existe des ε-équilibres de Nash de taille O(log n) (où n est le nombre de stratégies pures), les algorithmes traditionnels basés sur l'oracle de meilleure réponse (BRO) comme Fictitious Play (FP) et Double Oracle (DO) nécessitent Ω(n) itérations dans le pire cas.

Importance

  1. Écart théorie-pratique: Althöfer et Lipton et al. ont prouvé l'existence d'ε-NE de taille logarithmique, mais les algorithmes pratiques ne peuvent pas atteindre cette complexité
  2. Limitations des bornes inférieures: Hazan et Koren ont prouvé que tout algorithme basé sur BRO nécessite au moins Ω(√n/log³n) itérations
  3. Besoins d'application pratique: Les algorithmes d'apprentissage par renforcement profond (comme Policy Space Response Oracles) dépendent de ces algorithmes fondamentaux

Limitations des Méthodes Existantes

  1. FP et DO: Nécessitent O(n) itérations dans le pire cas
  2. Algorithme Hazan-Koren: Bien qu'il fournisse une complexité O(√n/ε²), l'algorithme est complexe et n'offre qu'une amélioration de racine carrée
  3. Méthodes de régularisation: Comme PU et OMWU, bien qu'elles atteignent O(log n) itérations, elles nécessitent de maintenir les distributions de probabilité de toutes les stratégies pures, ce qui ne convient pas aux jeux de grande taille

Motivation de la Recherche

En introduisant des perturbations dans l'oracle de meilleure réponse pour le rendre plus puissant, dépasser les limitations des bornes inférieures théoriques et réaliser une vitesse de convergence de niveau logarithmique.

Contributions Principales

  1. Introduction d'un Oracle de Meilleure Réponse Perturbée (PBRO): Proposition d'un mécanisme de perturbation aléatoire des utilités avant le calcul de la meilleure réponse
  2. Résultats Théoriques:
    • Preuve que Stochastic Fictitious Play (SFP) atteint une complexité d'itération O(log n/ε²) en espérance
    • Preuve que Stochastic Double Oracle (SDO) atteint O(log n) itérations en espérance pour des instances difficiles spécifiques (exemple de Zhang et Sandholm)
  3. Schéma d'Implémentation Efficace: Proposition de méthodes de perturbation efficaces pour les jeux avec structure interne (comme POSG, jeux de planification de chemins), sans nécessiter de parcourir toutes les stratégies pures
  4. Vérification Expérimentale: Validation de l'efficacité de la méthode de perturbation sur plusieurs types de jeux, incluant les jeux matriciels, les jeux stochastiques et les jeux de planification de chemins
  5. Outils Théoriques: Utilisation de l'astuce Gumbel-max pour établir le lien entre SFP et le prédicteur exponentiel pondéré aléatoire (REWF)

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée: Jeu matriciel M ∈ ℝ^(m×n), paramètre de précision ε > 0 Sortie: Paire de stratégies ε-équilibre de Nash ⟨p*, q*⟩ Contrainte: Minimiser le nombre d'itérations (nombre d'appels d'oracle)

Définition Mathématique de la Meilleure Réponse Perturbée

Pour le joueur ligne, étant donné la stratégie mixte du joueur colonne q ∈ Δ_n:

B̃R_r(q) ∈ argmin_{i∈[m]} π_i(Mq - u)

où u est un vecteur aléatoire dont les composantes sont des variables aléatoires i.i.d.

Pour le joueur colonne, étant donné la stratégie mixte du joueur ligne p ∈ Δ_m:

B̃R_c(p) ∈ argmax_{j∈[n]} π_j(p^⊤M + v)

Stochastic Fictitious Play (SFP)

Flux d'Algorithme:

  1. Initialisation: t←1, p←e_k, q←e_l (stratégies pures initiales)
  2. Calcul des limites de condition de terminaison: lb←BRVal_r(q), ub←BRVal_c(p)
  3. Tant que ub - lb > tε:
    • t←t+1
    • i←B̃R_r(q), j←B̃R_c(p) (meilleures réponses perturbées)
    • p←p+e_i, q←q+e_j (accumulation de stratégies)
    • Mise à jour des limites
  4. Retour de la stratégie moyenne: ⟨p*/t, q*/t⟩

Innovations Clés:

  • Utilisation d'un oracle perturbé plutôt qu'un oracle déterministe
  • Maintien de vecteurs de stratégies cumulées, retour de la stratégie moyenne finale
  • Condition de terminaison utilisant les valeurs de meilleure réponse non perturbées

Fondement Théorique de la Perturbation Gumbel

Astuce Gumbel-max (Lemme 1): Pour un vecteur x ∈ ℝ^n, si z a des composantes indépendantes et identiquement distribuées selon la distribution Gumbel G(0,β):

P(argmax_i π_i(x+z) = i*) = π_i*(softmax(x/β))

Cela signifie que l'utilisation de la meilleure réponse perturbée par Gumbel équivaut à l'échantillonnage à partir de la distribution softmax.

Lien avec REWF:

  • Le choix de stratégie du joueur ligne dans SFP équivaut à la stratégie REWF
  • Au tour t, échantillonnage à partir de softmax(-η∑^{t-1} Me)
  • Le paramètre η = 1/β contrôle le compromis exploration-exploitation

Analyse Théorique Centrale

Théorème 3 (Complexité SFP): Pour un jeu matriciel normalisé à 0,1 M ∈ ℝ^(m×n), m ≤ n, en posant β = (2+√(2ln n))/(ε√(8ln n)), SFP trouve un ε-NE en O(log n/ε²) itérations en espérance.

Esquisse de Preuve:

  1. Définition du nombre d'itérations T = ((2+√(2ln n))/ε)² ∈ O(log n/ε²)
  2. Utilisation du Corollaire 2 (borne de regret REWF), avec probabilité ≥3/4: 
    ∑_{t=1}^T M(i_t,j_t) - min_i ∑_{t=1}^T M(i,j_t) ≤ √T(1 + √(ln n)/2)
  3. Application du résultat dual pour le joueur colonne (probabilité ≥3/4)
  4. Occurrence simultanée des deux événements avec probabilité ≥1/2
  5. Combinaison des deux inégalités pour obtenir ub - lb ≤ ε
  6. Nombre d'exécutions attendu ≤2

Stochastic Double Oracle (SDO)

Caractéristiques de l'Algorithme:

  • Maintien de sous-ensembles de stratégies R ⊆ m, C ⊆ n
  • Calcul à chaque tour de l'équilibre de Nash du sous-jeu MR,C
  • Utilisation d'un oracle perturbé pour ajouter de nouvelles stratégies

Analyse pour des Jeux Spécifiques:

Exemple 1 (Matrice L):

L = [0   1   ...  1  ]
    [-1  0   ...  1  ]
    [⋮   ⋮   ⋱   ⋮  ]
    [-1  -1  ... 0  ]

Lemme 4 (Espérance de Perturbation Uniforme): Pour la k-ième ligne x = ⟨1,...,1,0,-1,...,-1⟩, utilisant une perturbation U(-1/2,1/2), l'indice de meilleure réponse perturbée attendu EI = k/2

Théorème 6: SDO trouve l'équilibre de Nash de L en O(log n) itérations en espérance

Technique de Preuve:

  • Définition de la fonction potentielle X_t = max{r_t, c_t}, où r_t = min R_t, c_t = min C_t
  • Utilisation de la théorie de la dérive (drift theory) pour prouver X_t - EX_{t+2} ≥ X_t/2
  • Application du Corollaire 17 pour obtenir ET ≤ 2ln n

Implémentation Efficace de la Perturbation

Méthode de Clustering: Pour les jeux avec structure interne (comme les jeux stochastiques):

  1. Identification des éléments matriciels correspondant aux mêmes états terminaux
  2. Clustering des éléments matriciels en K groupes
  3. Application de la même valeur de perturbation aléatoire à chaque groupe

Formule de Perturbation:

B̃R_r(q) = argmin_{i∈[m]} π_i((L + ∑_{k=1}^K z_k B_k)q)

où B_k est une matrice de masque identifiant les éléments du k-ième groupe

Avantages:

  • Génération de seulement K nombres aléatoires (K << mn)
  • Préservation de la sémantique de la structure du jeu
  • Applicabilité aux jeux avec structure (POSG, EFG, etc.)

Configuration Expérimentale

Ensembles de Données et Types de Jeux

  1. Jeux Matriciels Aléatoires: Matrices n×n, éléments échantillonnés uniformément à partir de 0,1, 100 instances générées par taille
  2. Matrices L et U^⊤: Instances difficiles des Exemples 1 et 2
  3. Jeu f-finger Morra: Jeu classique, taille matricielle f²×f²
  4. Jeu Colonel Blotto: 5 champs de bataille, budgets d'unités différents
  5. Jeu Stochastique n-bit Aléatoire: Correspondant à une matrice 2^n×2^n, avec structure arborescente
  6. Jeu de Planification de Chemins: Grille n×n, une partie cherche le chemin le plus court, l'autre choisit les arêtes pour augmenter le coût

Métriques d'Évaluation

  • Nombre d'itérations: Nombre d'appels d'oracle nécessaires pour atteindre ε-NE
  • Valeur ε: Définie à 0,1
  • Statistiques: Moyenne et écart-type de 10 expériences répétées

Méthodes de Comparaison

  1. FP: Fictitious Play Standard
  2. AFP: Anticipatory Fictitious Play
  3. SAFP: Version perturbée d'AFP
  4. DO: Double Oracle Standard
  5. SDO: Version perturbée de Double Oracle

Détails d'Implémentation

  • Langage de Programmation: Python
  • Matériel: AMD Ryzen 7 PRO 7840U
  • Génération de Nombres Aléatoires: Bibliothèque numpy, graine initiale 1
  • Initialisation: Indice du pire cas (k=l=n)
  • Résolution des Égalités: Sélection de l'indice minimum de meilleure réponse
  • Paramètre β de SFP: Défini selon le Théorème 3
  • Distribution de Perturbation SDO:
    • Analyse théorique: U(-1,1)
    • Application pratique: U(-0.01,0.01) et U(-0.001,0.001)

Résultats Expérimentaux

Résultats Principaux

Performance de SFP sur Différents Jeux

Jeux Matriciels Aléatoires 0,1:

  • AFP montre la meilleure performance, significativement supérieure aux autres méthodes
  • SFP et SAFP montrent des performances similaires, légèrement supérieures à FP
  • L'avantage de la perturbation n'est pas évident dans les jeux aléatoires
  • Le nombre d'itérations augmente de manière quasi-linéaire avec la taille

Matrice U^⊤:

  • FP et AFP montrent la complexité du pire cas O(n)
  • SFP et SAFP réduisent significativement le nombre d'itérations
  • Pour n=1000, SFP nécessite environ 10-15 itérations, tandis que FP en nécessite 1000
  • Vérification de la complexité théorique O(log n)

Jeu f-finger Morra:

  • SFP et SAFP convergent rapidement, même pour les grands f
  • Le nombre d'itérations de FP et AFP augmente avec f²
  • Pour f=10, SFP nécessite environ 50 itérations, FP en nécessite 200+

Performance de SDO sur Différents Jeux

Matrices L et U^⊤ (Perturbation théorique U(-1,1)):

  • SDO atteint la complexité logarithmique prédite théoriquement
  • Pour n=2000, SDO nécessite environ 10-15 itérations
  • DO nécessite n itérations (non affiché dans le graphique en raison de l'échelle)
  • Vérification parfaite des Théorèmes 6 et 7

Jeu f-finger Morra:

  • La perturbation réduit significativement le nombre d'itérations
  • U(-0.01,0.01) et U(-0.001,0.001) sont tous deux efficaces
  • La perturbation plus petite (U(-0.001,0.001)) montre une performance plus stable à grande échelle

Jeu Colonel Blotto:

  • 5 champs de bataille, budget d'unités 0-40
  • La méthode de perturbation surpasse continuellement la version sans perturbation
  • U(-0.01,0.01) montre la meilleure performance globale

Expériences de Perturbation Efficace

Jeu Stochastique n-bit (Correspondant à L et U^⊤):

  • Utilisation de la méthode de perturbation par clustering
  • Pour n=2000 (échelle 2^11), nécessite environ 100 itérations
  • Bien que légèrement plus lent que la perturbation théorique, bien supérieur à la complexité linéaire de DO
  • Preuve de la faisabilité de l'implémentation efficace

Jeu de Planification de Chemins:

  • Test sur grille n×n
  • La perturbation réduit significativement le nombre d'itérations
  • L'avantage devient plus apparent avec l'augmentation de la taille de la grille
  • Pour n=14, la version perturbée nécessite environ 100 itérations, la version sans perturbation en nécessite 200+

Observations des Expériences d'Ablation

Impact de l'Intensité de Perturbation:

  • Une perturbation trop grande peut endommager la convergence (observée dans les jeux aléatoires)
  • U(-0.001,0.001) montre une performance stable dans la plupart des cas
  • U(-0.01,0.01) est plus efficace dans les jeux structurés

Choix de la Distribution de Perturbation:

  • Distribution Gumbel: Théoriquement optimale, appropriée pour SFP
  • Distribution Uniforme: Plus simple en pratique, efficace dans SDO
  • Les deux montrent des performances similaires dans les expériences

Découvertes Clés

  1. Dépendance au Type de Jeu: La perturbation est très efficace dans les instances structurées/difficiles, l'avantage n'est pas évident dans les jeux aléatoires
  2. Cohérence Théorie-Pratique: Les résultats expérimentaux sont hautement cohérents avec les prédictions théoriques
  3. Faisabilité de l'Implémentation Efficace: La méthode de clustering maintient l'efficacité tout en réduisant considérablement les coûts de calcul
  4. Robustesse: La méthode de perturbation montre une performance stable sur plusieurs types de jeux

Travaux Connexes

Recherche sur la Convergence de Fictitious Play

  • Robinson (1951): Preuve de la convergence de FP vers NE dans les jeux à somme nulle
  • Conjecture de Karlin: Le plus ancien problème ouvert sur la vitesse de convergence de FP
  • Résultats Partiels: Résultats d'Abernethy et al. (2021), Daskalakis et Pan (2014) pour des types matriciels spécifiques
  • AFP: Proposé par Cloud et al. (2023), nécessite toujours O(n) itérations mais avec des constantes plus petites, appelle 4 fois BRO par tour

Méthodes de Régularisation

  • Hofbauer et Sandholm (2002): Preuve du lien entre perturbation et régularisation
  • PU et OMWU: Variantes régularisées d'AFP par Cen et al. (2024), atteignent O(log n) mais nécessitent de maintenir les distributions de probabilité de toutes les stratégies
  • Distinction de cet Article: PBRO ne nécessite de maintenir que le sous-ensemble de stratégies sélectionnées, applicable aux jeux de grande taille

Recherche sur Double Oracle

  • Complexité Fondamentale: DO nécessite Θ(n) itérations, mais manque d'études théoriques approfondies
  • Zhang et Sandholm (2024): Preuve de la borne inférieure exponentielle de DO sur POSG
  • Variantes: Self-Play PSRO de McAleer et al. (2022), etc., mais sans garanties de convergence
  • Contribution de cet Article: Première étude systématique des propriétés de convergence de SDO

Limites Théoriques des Algorithmes BRO

  • Althöfer (1994), Lipton et Young (1994): Existence d'ε-NE de taille O(log n)
  • Hazan et Koren (2016):
    • Borne Inférieure: Tout algorithme BRO nécessite Ω(√n/log³n) itérations
    • Borne Supérieure: Algorithme proposé O(√n/ε²)
  • Percée de cet Article: Dépasser la borne inférieure théorique en renforçant BRO (ajout de perturbation)

Applications d'Apprentissage par Renforcement Profond

  • Série PSRO: Lanctot et al. (2017), McAleer et al. (2022), Bighashdel et al. (2024)
  • Lien: Ces méthodes dépendent du cadre DO, SDO de cet article peut être directement appliqué
  • Impact Potentiel: Le mécanisme de perturbation peut améliorer les stratégies d'exploration en RL profond

Conclusion et Discussion

Conclusions Principales

  1. Percée Théorique:
    • SFP atteint une complexité d'espérance O(log n/ε²), première preuve de convergence logarithmique pour les algorithmes PBRO
    • SDO atteint une complexité d'espérance O(log n) sur des instances difficiles spécifiques
  2. Valeur Pratique:
    • La méthode de perturbation réduit significativement le nombre d'itérations dans les jeux structurés
    • Le schéma d'implémentation efficace rend la méthode applicable aux jeux de grande taille
  3. Contributions Méthodologiques:
    • Établissement du lien théorique entre SFP et REWF
    • Fourniture d'un cadre utilisant la théorie de la dérive pour analyser SDO

Limitations

  1. Complexité Générale de SDO Non Résolue:
    • Seule la complexité logarithmique pour des instances spécifiques est prouvée
    • La complexité générale reste un problème ouvert
  2. Performance sur Jeux Stochastiques:
    • L'avantage de la perturbation n'est pas évident dans les jeux générés aléatoirement
    • Peut être dû au fait que les jeux aléatoires ont déjà une meilleure réponse aléatoire
  3. Sélection des Paramètres de Perturbation:
    • Le paramètre théoriquement optimal (β) peut être trop grand en pratique
    • Nécessite d'ajuster l'intensité de perturbation selon le jeu spécifique
  4. Approximation de l'Implémentation Efficace:
    • La perturbation par clustering n'est pas complètement équivalente à la perturbation complète
    • Les garanties théoriques s'appliquent uniquement à la perturbation complète
  5. Coût de Calcul:
    • Bien que réduisant le nombre d'itérations, chaque itération nécessite la génération de nombres aléatoires
    • Pour certains jeux, le bénéfice peut ne pas compenser les frais supplémentaires

Directions Futures

  1. Analyse de Complexité Générale de SDO:
    • Preuve ou réfutation de la complexité logarithmique de SDO dans le cas général
    • Identification des caractéristiques des classes de jeux où SDO est efficace
  2. Stratégies de Perturbation Adaptatives:
    • Ajustement dynamique de l'intensité de perturbation selon la convergence
    • Exploration des propriétés théoriques de différentes distributions de perturbation
  3. Intégration d'Apprentissage par Renforcement Profond:
    • Intégration de PBRO dans le cadre PSRO
    • Étude de l'effet de la perturbation lors de l'approximation de BRO par réseaux de neurones
  4. Classes de Jeux Plus Larges:
    • Extension aux jeux généraux
    • Étude des mécanismes de perturbation dans les jeux multi-joueurs
  5. Vérification d'Application Pratique:
    • Test dans des scénarios de jeux réels (poker, jeux de stratégie)
    • Évaluation de la performance sous les contraintes de ressources de calcul réelles

Évaluation Approfondie

Points Forts

  1. Rigueur Théorique:
    • Preuves mathématiques complètes, de l'astuce Gumbel-max à la théorie de la dérive
    • Établissement clair du lien entre SFP et l'algorithme d'apprentissage en ligne classique (REWF)
    • Résultats théoriques hautement cohérents avec les expériences
  2. Sélection du Problème Important:
    • Aborde l'écart théorie-pratique de longue date dans le domaine
    • Dépasse la borne inférieure de Hazan-Koren (en renforçant l'oracle)
    • Valeur d'application directe à l'apprentissage par renforcement profond
  3. Innovation Méthodologique:
    • Mécanisme de perturbation simple mais efficace
    • Schéma d'implémentation efficace résolvant le goulot d'étranglement de calcul
    • Cadre unifié applicable aux deux classes d'algorithmes FP et DO
  4. Complétude Expérimentale:
    • Couverture des instances théoriques, jeux classiques, jeux aléatoires, jeux structurés
    • Comparaison avec plusieurs méthodes de base
    • Rapport honnête des résultats négatifs dans les jeux aléatoires
  5. Clarté de la Rédaction:
    • Introduction de contexte suffisante, motivation claire
    • Détails techniques complets, forte reproductibilité
    • Code source fourni

Insuffisances

  1. Complétude Théorique:
    • La complexité générale de SDO n'est pas résolue, seulement l'analyse de cas particuliers
    • Manque d'explication théorique pour les cas d'échec de perturbation (jeux aléatoires)
    • L'écart théorique entre perturbation efficace et perturbation complète n'est pas quantifié
  2. Conception Expérimentale:
    • L'échelle des expériences sur jeux aléatoires est relativement petite (n≤1000)
    • Manque de comparaison directe avec l'algorithme Hazan-Koren
    • Pas de rapport du temps d'exécution réel, seulement le nombre d'itérations
  3. Considérations de Praticité:
    • Manque de directives universelles pour la sélection des paramètres de perturbation
    • Absence de critères pour décider quand utiliser la perturbation
    • Portée d'applicabilité du schéma d'implémentation efficace insuffisamment claire
  4. Profondeur d'Analyse:
    • Explication intuitive insuffisante de l'efficacité du mécanisme de perturbation
    • Analyse insuffisante de la relation entre la structure du jeu et l'effet de perturbation
    • Expériences d'ablation relativement simples
  5. Équité de Comparaison:
    • AFP appelle 4 fois BRO par tour, tandis que FP/SFP n'en appellent que 2
    • Devrait également rapporter la comparaison du nombre total d'appels BRO

Impact

  1. Contribution Théorique:
    • Fournit une nouvelle direction pour la recherche sur les algorithmes BRO
    • Démontre le potentiel du renforcement d'oracle
    • Peut inspirer la recherche sur d'autres problèmes d'optimisation combinatoire
  2. Valeur Pratique:
    • Directement applicable aux cadres DO/FP existants
    • Potentiel d'amélioration de la méthode PSRO en RL profond
    • Le schéma d'implémentation efficace est opérationnellement réalisable
  3. Limitations:
    • Nécessite un développement théorique supplémentaire pour devenir une méthode standard
    • La performance dans les jeux aléatoires limite l'universalité
    • Les frais de calcul doivent être vérifiés dans les applications à grande échelle
  4. Reproductibilité:
    • Code source fourni, forte reproductibilité
    • Description d'algorithme claire, facile à implémenter
    • Configuration expérimentale détaillée

Scénarios d'Application

Fortement Recommandé:

  1. Jeux avec structure explicite (EFG, POSG)
  2. Jeux avec plusieurs meilleures réponses équivalentes
  3. Instances difficiles où FP/DO convergent lentement
  4. Jeux avec espace de stratégies énorme mais structure interne

Utilisation Prudente:

  1. Jeux complètement aléatoires
  2. Jeux où la meilleure réponse est unique et explicite
  3. Scénarios avec ressources de calcul extrêmement limitées
  4. Applications nécessitant des garanties déterministes

Non Recommandé:

  1. Jeux de petite taille (résolution directe plus rapide)
  2. Jeux généraux sans structure (avantage de perturbation non évident)
  3. Scénarios de prise de décision en temps réel (l'aléatoire peut être inacceptable)

Références

Fondements Théoriques Clés:

  1. Althöfer (1994) - Existence d'ε-NE de taille logarithmique
  2. Hazan & Koren (2016) - Limites théoriques des algorithmes BRO
  3. Hofbauer & Sandholm (2002) - Preuve de convergence de SFP
  4. Cesa-Bianchi & Lugosi (2006) - Algorithme REWF

Travaux Connexes: 5. Zhang & Sandholm (2024) - Borne inférieure exponentielle de DO 6. Cloud et al. (2023) - Anticipatory Fictitious Play 7. Lanctot et al. (2017) - Policy Space Response Oracles 8. Cen et al. (2024) - Algorithmes de jeux régularisés

Évaluation Globale: Ceci est un excellent article combinant bien la théorie et la pratique. La contribution principale est la preuve que le mécanisme de perturbation peut permettre aux algorithmes BRO d'atteindre une complexité logarithmique, dépassant la borne inférieure théorique connue (en renforçant l'oracle). Le résultat théorique de SFP est complet et rigoureux, l'analyse de SDO, bien qu'incomplète, fournit des perspectives précieuses. La conception expérimentale est complète, rapportant honnêtement la portée d'applicabilité de la méthode. Les principales insuffisances sont que la complexité générale de SDO n'est pas résolue et que le manque de performance dans les jeux aléatoires manque d'explication théorique. Ce travail ouvre une nouvelle direction pour la recherche en algorithmes de théorie des jeux et a une valeur d'application potentielle à l'apprentissage par renforcement profond, méritant une recherche approfondie.