Learning in Matching Games with Bandit Feedback

Résumé Technique : Apprentissage dans les jeux d'appariement avec rétroaction de type bandit

Formulation du Problème
Cet article introduit un nouveau problème d'apprentissage situé à l'intersection des marchés d'appariement bilatéraux et de la théorie des jeux. Le cadre implique un marché généralisé avec deux ensembles distincts d'agents, $P$ et $A$, qui sont appariés par une plateforme centrale sur un horizon de temps $T$. Contrairement aux problèmes d'appariement traditionnels où les agents possèdent des préférences statiques et connues, ou aux configurations standards de Bandits Multi-Bras (MAB) où les agents reçoivent des gains stochastiques directs, ce cadre postule qu'une fois appariés, les agents s'engagent dans un jeu à somme nulle à deux joueurs (ZSG) avec une matrice de gains initialement inconnue.

Dans ce scénario, les agents doivent apprendre simultanément la dynamique sous-jacente du jeu et dériver leurs préférences à partir des résultats de ces interactions. À chaque étape $t$ :

1. Une plateforme centrale génère un appariement $m_t$ basé sur les estimations des préférences des agents.
2. Les agents appariés sélectionnent des stratégies (actions mixtes) et échantillonnent des actions spécifiques.
3. Les agents reçoivent une rétroaction de type bandit stochastique (récompenses) et observent les actions de leur partenaire d'appariement.
4. Les agents mettent à jour leurs estimations des matrices de gains et de leurs préférences pour le tour suivant.

Le défi central est d'apprendre un Équilibre d'Appariement, un concept de solution défini par [10] où l'appariement est stable (absence de paires bloquantes) et où les agents jouent un Équilibre de Nash (NE) avec leurs partenaires assignés. La difficulté réside dans le fait que les agents ne connaissent pas les matrices de gains a priori et doivent explorer pour former des préférences, tandis que le mécanisme d'appariement (généralement Gale-Shapley) repose sur ces préférences pour garantir la stabilité.

Méthodologie et Algorithme
Pour répondre à cela, les auteurs proposent UCB-MG, un algorithme basé sur le principe de « l'optimisme face à l'incertitude ». La méthodologie fonctionne comme suit :

• Estimations Optimistes : Les agents maintiennent des bornes supérieures de confiance (UCB) pour les matrices de gains des appariements potentiels. Plus précisément, pour une paire $(p, a)$, la matrice de gains estimée $\bar{A}_{p,a}$ est construite en ajoutant un bonus de confiance à la moyenne empirique des récompenses observées.
• Formation des Préférences : Sur la base de ces matrices de gains optimistes, les agents calculent la valeur optimiste du jeu ($\bar{V}^*$) en supposant un jeu optimal (stratégies minimax) contre chaque partenaire potentiel. Les agents classent ensuite leurs préférences selon ces valeurs de jeu optimistes.
• Appariement : La plateforme centrale collecte ces préférences rapportées et exécute l'algorithme de Gale-Shay (GS) pour générer un appariement stable pour le tour actuel.
• Exécution des Stratégies : Une fois appariés, les agents sélectionnent des actions basées sur les stratégies minimax dérivées de leurs matrices de gains optimistes, échantillonnent des actions et reçoivent une rétroaction pour mettre à jour leurs estimations.

Formulation du Regret : Instabilité de l'Appariement
Une contribution critique de l'article est la définition d'une métrique de regret appropriée, appelée Instabilité de l'Appariement (MI). Les définitions de regret standard issues des MAB ou de la théorie des jeux sont insuffisantes car l'objectif est de converger vers un équilibre conjoint de l'appariement et de la stratégie.

Les auteurs définissent la MI comme la solution d'un programme linéaire minimisant les subventions nécessaires pour stabiliser le marché étant donné un appariement $m$ et un profil de stratégie $X$. Mathématiquement, il s'agit de la solution d'un programme linéaire minimisant les subventions $s_a$ sous les contraintes suivantes :

1. Absence de Paires Bloquantes : Garantir qu'aucune paire $(p, a)$ ne peut améliorer son utilité en déviant, compte tenu des stratégies actuelles.
2. Rationalité Individuelle : Garantir que les agents préfèrent leur appariement actuel plutôt que de ne pas être appariés.
3. Garantie de Valeur : Garantir que les agents reçoivent une utilité au moins égale à la valeur minimax de leur jeu (une relaxation de la condition stricte de Nash pour faciliter une analyse traitable).

Le regret cumulé $R_T$ est défini comme la somme de l'Instabilité de l'Appariement sur l'horizon $T$.

Contributions Clés

1. Définition du Problème d'Apprentissage : L'article formalise le premier cadre d'apprentissage où les agents d'un marché bilatéral doivent apprendre des jeux à somme nulle inconnus pour former des préférences pour l'appariement.
2. Métrique de Regret : Il introduit l'Instabilité de l'Appariement, étendant le concept d'Instabilité de Sous-ensemble [8, 17] à des contextes où les agents appariés jouent des jeux. Cette métrique quantifie la distance par rapport à un Équilibre d'Appariement.
3. Conception d'Algorithme : Les auteurs proposent un algorithme basé sur l'UCB (UCB-MG) qui intègre l'estimation optimiste de la valeur du jeu avec le mécanisme de Gale-Shapley.
4. Garanties Théoriques : L'article prouve que l'algorithme proposé atteint une borne de regret sous-linéaire et indépendante de l'instance de $\tilde{O}(\sqrt{Tmkpa})$, où $T$ est l'horizon, $m$ et $k$ sont le nombre d'actions par agent, et $p$ et $a$ sont le nombre d'agents de chaque côté.
5. Généralisation : La borne théorique unifie les résultats existants. Lorsque $m=k=1$, elle retrouve la borne pour l'appariement bilatéral classique ($\tilde{O}(\sqrt{Tpa})$). Lorsque $p=a=1$, elle retrouve la borne pour l'auto-jeu dans les jeux à somme nulle ($\tilde{O}(\sqrt{Tmk})$).

Résultats et Preuves Empiriques
Les auteurs fournissent une validation empirique à l'aide d'instances synthétiques où les matrices de gains sont échantillonnées à partir d'une distribution normale. Ils comparent trois scénarios :

• Auto-Jeu (Self-Play) : Les deux côtés suivent l'algorithme UCB-MG.
• Réponse-Nash (Nash-Response) : Un côté connaît les vraies matrices de gains et joue la stratégie d'Équilibre de Nash, tandis que l'autre apprend.
• Meilleure Réponse (Best-Response) : Un côté connaît les vraies matrices et les stratégies de l'adversaire, jouant la meilleure réponse.

Les résultats indiquent que le système apprend un résultat stable dans tous les scénarios, présentant une croissance sous-linéaire du regret. Comme prévu, le scénario Réponse-Nash produit le regret le plus faible. Curieusement, bien que le scénario Meilleure Réponse surpasse initialement l'Auto-Jeu, ses performances se dégradent à mesure que la taille du marché (nombre d'agents et d'actions) augmente, probablement en raison de la complexité introduite par un côté exploitant l'autre.

Signification et Directions Futures
L'article revendique une importance en tant que première étape vers la compréhension de l'apprentissage dans des environnements où les agents ne reçoivent des gains qu'après avoir interagi via des actions dans un jeu, plutôt que de recevoir des signaux de préférence directs. Il démontre que des résultats stables peuvent être appris efficacement dans des contextes aussi complexes et couplés.

Les auteurs présentent ce travail avec modestie comme une fondation pour la recherche future. Ils identifient plusieurs directions ouvertes :

• Étendre le modèle des jeux à somme nulle vers les jeux à somme générale.
• Intégrer des algorithmes d'apprentissage sans regret (comme Exp3) dans le cadre d'appariement pour gérer les dynamiques de non-somme nulle.
• Relâcher l'hypothèse selon laquelle les agents observent les actions de leur partenaire.
• Explorer d'autres modèles de jeux (jeux de Markov, jeux de Stackelberg) et des structures d'appariement (marchés de un-à-plusieurs).
• Étudier des contextes décentralisés où les agents sélectionnent à la fois les appariements et les stratégies sans coordinateur central.