Résumé Technique : Regret Bidirectionnel Indépendant du Temps pour les Marchés d'Appariement avec Entretiens Limités

1. Énoncé du Problème

L'article aborde le problème de l'apprentissage par bandits bidirectionnel dans les marchés d'appariement, où les participants doivent apprendre leurs préférences par interaction tout en faisant face à des contraintes significatives. Le cadre implique $n$ agents et $m$ entreprises ($n \le m$) avec des préférences strictes et inconnues les uns sur les autres. Les défis principaux identifiés sont :

1. Dépistage Limité (Entretiens) : Les participants ne peuvent évaluer qu'une petite fraction des partenaires potentiels avant de s'engager. Le modèle formalise cela par une phase d'entretien « pré-appariement » où les agents sélectionnent un sous-ensemble d'entreprises à interviewer. Ces interactions produisent des signaux bruités et stochastiques (indices) sur la qualité de l'appariement, mais ne garantissent pas de récompense. Crucialement, les agents ne peuvent postuler qu'aux entreprises qu'ils ont interviewées.
2. Incertitude Bidirectionnelle : Contrairement aux travaux antérieurs qui supposent souvent que les entreprises ont des préférences connues et fixes, ce modèle suppose que les entreprises sont également incertaines et doivent apprendre leurs préférences au fil du temps.
3. Rétroaction Limitée : Dans les contextes décentralisés, les agents ne reçoivent que des signaux côté entreprise grossiers et anonymes. Deux modèles de rétroaction sont considérés :
   • Vacance uniquement ($V$) : Les agents observent quelles entreprises sont actuellement vacantes.
   • Changement d'embauche ($V^+$) : Les agents observent quelles entreprises ont changé leur statut d'embauche (vacante ou ayant embauché un agent différent), sans révéler les identités.
4. Différence Stratégique : Pour gérer l'incertitude des entreprises, l'article introduit un nouvel espace d'actions où les entreprises peuvent différer stratégiquement (rester vacantes) plutôt que d'embaucher leur meilleur candidat actuel si elles soupçonnent que leurs estimations sont incorrectes. Ce mécanisme est conçu pour corriger les engagements prématurés et stabiliser les dynamiques décentralisées.

L'objectif est de minimiser le regret, défini comme l'écart entre la récompense attendue de l'appariement stable d'un agent (selon les préférences de vérité terrain) et la récompense cumulative acquise sur $T$ tours. L'article cible spécifiquement le regret indépendant de l'horizon (c'est-à-dire $O(1)$ ou $O(\text{poly}(n,m))$ indépendant de $T$), une amélioration significative par rapport aux bornes $O(\log T)$ typiques des appariements par bandits sans entretiens.

2. Méthodologie

L'article propose des algorithmes pour les contextes de marché centralisés et décentralisés, exploitant le concept d'entretiens comme « indices de bandits ».

Mécanismes Principaux

• Entretiens comme Indices : Les agents interviewent $k$ entreprises par tour (généralement $k=2$). Une entreprise est sélectionnée via un schéma Round-Robin ($f^{RR}_a(t)$) pour assurer une exploration uniforme, et l'autre est l'entreprise cible de candidature ($f^{apply}_a(t)$) déterminée par les estimations de préférence.
• Politique de Rejet Stratégique (Algorithme 1) : Les entreprises incertaines maintiennent des estimations de la qualité des agents. Si le meilleur candidat actuel d'une entreprise n'est pas estimé comme dominant tous les agents précédemment rejetés (qui pourraient désormais être préférés à mesure que les estimations évoluent), l'entreprise s'abstient stratégiquement d'embaucher. Cela crée un signal de vacance ($V$ ou $V^+$) qui alerte les agents à réévaluer, brisant les impasses potentielles causées par des erreurs d'estimation précoces du côté des entreprises.
• Moyennes Empiriques : Les agents et les entreprises utilisent les moyennes empiriques des récompenses observées pour mettre à jour leurs listes de préférences.

Paradigmes Algorithmiques

1. Contexte Centralisé (Algorithme 6) :

   • Un Allocateur Central d'Entretiens (CIA) coordonne les entretiens.
   • Le CIA exécute l'algorithme de Gale-Shapley (GS) sur les préférences estimées actuelles pour déterminer l'entreprise cible de candidature pour chaque agent.
   • Les agents interviewent leur cible et une entreprise round-robin, puis postulent à la cible.
   • Ce contexte atteint un regret indépendant du temps en garantissant que, une fois les estimations « valides » (correctement ordonnées par rapport à l'appariement stable), le système converge immédiatement.

2. Contexte Décentralisé :

   • Coordonné (Algorithme 7, sous rétroaction $V$) : Les agents opèrent dans des phases alternées de mise à jour et d'engagement.
     • Mise à jour : Les agents exécutent de manière synchrone une exécution distribuée de GS basée sur un instantané fixe des préférences.
     • Engagement : Les agents postulent à leurs appariements assignés.
     • Coordination : Si un agent détecte une incohérence de préférence ou un rejet stratégique (via des signaux de vacance), il signale un retour à la phase de mise à jour en s'abstenant de postuler.
   • Sans Coordination (Algorithmes 3 et 9, sous rétroaction $V^+$) :
     • Les agents agissent indépendamment, réagissant aux changements d'embauche ($V^+$).
     • Les agents maintiennent un ensemble de candidats d'entreprises qui ne les ont jamais rejetés ou qui ont récemment changé d'embauche.
     • Marchés Généraux (Algorithme 9) : Pour prévenir les cycles infinis dans les marchés avec plusieurs appariements stables, les agents utilisent $k=3$ entretiens (cible actuelle, cible précédente, round-robin) et postulent à un ensemble d'entreprises avec une probabilité $\lambda$. Cette randomisation brise les cycles de paires bloquantes.

3. Contributions Clés

1. Différence Stratégique pour les Entreprises Incertaines : L'article introduit la différence comme un primitif modulaire pour l'apprentissage bidirectionnel. C'est le premier travail à étendre l'espace d'actions des entreprises au-delà de « toujours embaucher », permettant aux entreprises de corriger les erreurs précoces et de stabiliser l'apprentissage décentralisé sous rétroaction limitée.
2. Regret Indépendant de l'Horizon avec Entretiens Constants : Les auteurs prouvent qu'un nombre constant d'entretiens par tour (spécifiquement $k=2$) suffit pour atteindre un regret indépendant du temps. Cela améliore les garanties $O(\log T)$ de la littérature antérieure sur l'appariement par bandits.
3. Résolution de Conjectures Ouvertes : Dans le cas d'un agent unique, l'article résout une conjecture ouverte de Bhaskara et al. [6], montrant que deux indices (entretiens) suffisent pour un regret indépendant du temps en utilisant des moyennes empiriques, alors que trois étaient précédemment conjecturés comme nécessaires.
4. Apprentissage Décentralisé sous Anonymat : Le travail fournit les premiers algorithmes décentralisés atteignant un regret indépendant du temps en utilisant uniquement des signaux de statut côté entreprise anonymes (vacance ou changements d'embauche), même lorsque les entreprises sont incertaines et stratégiques.

4. Résultats

L'article établit les bornes de regret suivantes (où $\Delta$ représente l'écart de récompense minimum) :

• Centralisé (Algorithme 6) :

  • Regret : $O(nm^2 \Delta^{-2})$.
  • Optimalité : Dans un facteur $m$ de la borne inférieure information-théorique $\Omega(nm)$. Les auteurs conjecturent que $O(nm^2)$ est serré.

• Décentralisé Coordonné (Algorithme 7, rétroaction $V$) :

  • Marchés $\alpha$-réductibles : $O(n^3m^2 \Delta^{-2})$.
  • Marchés généraux : $O(n^4m^2 \Delta^{-2})$.
  • Ces bornes reflètent le coût de l'exécution distribuée de GS ($O(n^2)$) multiplié par le coût d'apprentissage centralisé.

• Décentralisé Sans Coordination (Algorithmes 3/9, rétroaction $V^+$) :

  • Marchés $\alpha$-réductibles ($k=2$) : $O(n^3m^2 \Delta^{-2})$ (constantes dépendantes du marché).
  • Marchés généraux ($k=3$) : $O(\epsilon^{-1} n^5 m^4 \Delta^{-2})$, où $\epsilon$ dépend du paramètre de randomisation $\lambda$ et décroît exponentiellement avec $n$ et $m$.
  • Le facteur exponentiel dans les marchés généraux découle de la nécessité de briser les dynamiques cycliques de paires bloquantes sans coordination.

5. Signification et Revendications

L'article revendique fournir un cadre plus général pour l'apprentissage décentralisé bidirectionnel en modélisant explicitement l'incertitude des entreprises et en introduisant la différence stratégique. Sa signification réside dans :

• Assouplissement des Hypothèses Fortes : Il améliore les travaux antérieurs (par exemple, Liu et al. [19]) en supprimant l'hypothèse que les entreprises ont des préférences connues et en opérant sous une rétroaction significativement plus faible (signaux anonymes vs révélation complète de l'identité de l'appariement).
• Efficacité : Il démontre que les appariements stables peuvent être appris avec un regret indépendant de l'horizon, proche de l'optimal, en utilisant uniquement un nombre constant d'interactions pré-appariement peu coûteuses par tour.
• Stabilisation : Le mécanisme de différence stratégique s'avère essentiel pour corriger l'instabilité dans les systèmes décentralisés où les entreprises apprennent, empêchant le système de rester bloqué dans des états sous-optimaux dus à des erreurs d'estimation précoces.

Les auteurs notent que, bien que leurs bornes soient proches de l'optimalité pour les contextes centralisés et décentralisés structurés, les constantes exponentielles dans les marchés généraux sans coordination soulignent la difficulté inhérente à la résolution des paires bloquantes sans coordination ou rétroaction plus riche. Ils laissent la dérivation de bornes inférieures serrées pour les algorithmes sans coordination dans les marchés non structurés comme un problème ouvert.