Résumé technique : Convergence à la dernière itération quasi-optimale pour les jeux à somme nulle avec rétroaction en bande et actions de l'adversaire

Énoncé du problème

L'article aborde le problème de l'apprentissage dans les jeux à somme nulle à deux joueurs sous rétroaction en bande, où les joueurs n'observent que la perte/récompense bruitée de la paire d'actions spécifique jouée à chaque tour, plutôt que le gradient complet de leur stratégie mixte. Une distinction critique dans ce travail est l'hypothèse que les joueurs observent également l'action de l'adversaire en plus de leur propre perte.

L'objectif principal est d'atteindre une convergence à la dernière itération vers un équilibre de Nash, mesurée par l'écart de dualité $DGap(x_t, y_t) \to 0$ lorsque les tours $t \to \infty$. Cela se distingue et est plus fort que la convergence par itération moyenne (convergence des stratégies moyennées dans le temps) ou la convergence par itération aléatoire.

Des travaux antérieurs ont établi une séparation stricte entre la convergence par itération moyenne et la convergence à la dernière itération en l'absence de rétroaction sur les actions de l'adversaire :

• Itération moyenne : Taux optimal de $O(t^{-1/2})$.
• Dernière itération (sans actions de l'adversaire) : Les taux optimaux sont limités à $O(t^{-1/3})$ en espérance et à $O(t^{-1/4})$ avec une haute probabilité.

La question centrale posée est de savoir si l'information supplémentaire de l'observation de l'action de l'adversaire permet une convergence à la dernière itération plus rapide, comblant spécifiquement l'écart vers le taux optimal $O(t^{-1/2})$.

Méthodologie

L'algorithme : PMO-LB

Les auteurs proposent l'Optimisation Minimax par Phases avec Régularisation par Barrière Logarithmique (PMO-LB). L'algorithme fonctionne par époques de longueur double ($2^{s-1}$ à $2^s - 1$).

1. Estimation : Au sein de chaque époque $s$, les joueurs collectent des données pour calculer un estimateur empirique $\hat{A}_s$ de la matrice du jeu $A$.
2. Mise à jour de la stratégie : Au début de chaque époque, les joueurs calculent une nouvelle paire de stratégies mixtes $(x_s, y_s)$ en résolvant un jeu régularisé par barrière logarithmique estimé. La fonction de gain est définie comme :
   $$\Phi_s(x, y) \triangleq x^\top \hat{A}_s y + \gamma_s \sum_{i=1}^d \log \frac{1}{x_i} - \gamma_s \sum_{j=1}^d \log \frac{1}{y_j}$$
   où $\gamma_s$ est un taux d'apprentissage décroissant avec l'époque.
3. Exécution : Les joueurs échantillonnent des actions à partir de $(x_s, y_s)$ pendant la durée de l'époque.
4. Indépendance : Malgré la nature couplée du jeu, l'algorithme est découplé ; chaque joueur peut calculer sa stratégie indépendamment en utilisant uniquement les actions de l'adversaire observées et ses propres pertes.

Approche analytique

L'article soutient que les techniques standard de la littérature sur les bandits (à la fois l'élimination dure et l'élimination douce) ne parviennent pas à se généraliser aux jeux, même avec une rétroaction sur les actions de l'adversaire.

• Élimination dure : Échoue car l'estimation de l'écart de dualité d'une paire de stratégies pures $(e_i, e_j)$ nécessite de jouer d'autres stratégies potentiellement « mauvaises » pour trouver les meilleures réponses, ce qui contredit l'objectif de maintenir un faible regret à chaque tour.
• Élimination douce standard (style FALCON) : Les analyses existantes reposent sur une propriété « faible regret-faible variance » où la variance de l'estimation d'une action est contrôlée par son regret. Les auteurs montrent que cette propriété est insuffisante pour les jeux car l'estimation de l'écart de dualité d'une paire de stratégies nécessite de jouer des stratégies qui peuvent elles-mêmes avoir des écarts de dualité élevés.

Pour surmonter cela, les auteurs développent une nouvelle analyse basée sur la stabilité multiplicative.

• Ils prouvent que les stratégies consécutives $x_s$ et $x_{s-1}$ (et de même pour $y$) sont multiplicativement proches ($x_{s,i} \leq \alpha x_{s-1,i}$) avec une haute probabilité.
• Cette stabilité est rendue possible par le régularisateur par barrière logarithmique, qui empêche la masse de probabilité de se concentrer trop rapidement sur un sous-ensemble d'actions, contrôlant ainsi la variance des estimateurs de perte.
• L'analyse établit une propriété « faible écart de dualité-faible variance » qui, combinée à la stabilité multiplicative, permet de borner le véritable écart de dualité sans exiger que l'algorithme joue explicitement de mauvaises stratégies.

Contributions clés

1. Convergence optimale à la dernière itération : L'article démontre qu'avec une rétroaction sur les actions de l'adversaire, il est possible d'atteindre une convergence à la dernière itération en $O(t^{-1/2})$ avec une haute probabilité. Cela correspond au taux optimal pour la convergence par itération moyenne, fermant efficacement l'écart entre les deux notions dans ce contexte.
2. Efficacité algorithmique : L'algorithme proposé est computationnellement efficace, ne nécessitant que $\log t$ mises à jour (résolution d'un problème d'optimisation de point selle) après $t$ tours.
3. Nouveauté théorique : Le travail identifie des obstacles fondamentaux dans la généralisation des analyses de bandits à un seul joueur aux jeux à plusieurs joueurs. Il introduit un nouveau cadre analytique reposant sur la stabilité multiplicative entre les stratégies consécutives, distinct des analyses basées sur le regret précédentes.
4. Amélioration des bandits de duel : Comme cas particulier où la matrice du jeu est antisymétrique (bandits de duel), les résultats fournissent les premières garanties de convergence à la dernière itération pour ce contexte, améliorant les travaux antérieurs qui ne proposaient que des bornes de regret.

Résultats

Garanties théoriques

Théorème 4.1 : Pour tout $\delta \in (0, 1)$ fixé, l'Algorithme 2 avec un calendrier spécifique de taux d'apprentissage garantit qu'avec une probabilité d'au moins $1-\delta$ :
$$DGap(x_t, y_t) = O\left( \frac{d^2 \sqrt{\log(d \log t / \delta)}}{\sqrt{t}} \right)$$
pour tout $t \geq 1$. Cela représente un taux de convergence en $t^{-1/2}$.

Validation expérimentale

Les auteurs ont évalué PMO-LB sur des benchmarks de jeux de sécurité (tailles $61 \times 21$ et $39 \times 35$) par rapport à cinq lignes de base :

• Méthodes antérieures sans rétroaction sur les actions de l'adversaire (Cai et al. [2023, 2025], Fiegel et al. [2025, 2026]).
• Une ligne de base naïve qui utilise les actions de l'adversaire mais mélange la meilleure stratégie empirique avec une exploration uniforme (Algorithme 3).

Résultats :

• PMO-LB a constamment surpassé toutes les lignes de base.
• Les pentes de convergence empiriques correspondaient aux prédictions théoriques :
  • PMO-LB : $\approx -0,5$ (correspondant à $t^{-1/2}$).
  • Ligne de base naïve : $\approx -0,25$ (correspondant à $t^{-1/4}$).
  • Méthodes antérieures (sans actions de l'adversaire) : Les pentes variaient de $-0,175$à$-0,301$ (correspondant à $t^{-1/8}$ à $t^{-1/3}$).

Importance et affirmations

L'article prétend résoudre une question ouverte de longue date concernant l'impact de l'information sur les actions de l'adversaire sur la convergence à la dernière itération. En montrant qu'une convergence en $t^{-1/2}$ est réalisable, le travail démontre que la « voie plus difficile » de la convergence à la dernière itération dans les contextes de rétroaction en bande n'est pas intrinsèquement plus lente que la convergence par itération moyenne, à condition que les actions de l'adversaire soient observables.

Les auteurs soulignent que leur contribution est principalement théorique et algorithmique. Ils notent que bien que la dépendance en $d^2$ dans la borne puisse être sous-optimale, le taux $t^{-1/2}$ est optimal à des facteurs de dimension près. Le travail met également en évidence que leurs techniques d'analyse (stabilité multiplicative via régularisation par barrière logarithmique) peuvent présenter un intérêt indépendant pour les problèmes de bandits à un seul joueur, offrant une alternative aux analyses existantes basées sur le regret.

L'article conclut que l'observation des actions de l'adversaire atténue fondamentalement la tension exploration-exploitation requise pour la convergence à la dernière itération, permettant aux algorithmes d'éviter les taux lents précédemment considérés comme inévitables dans les contextes de rétroaction en bande.