Résumé technique : Bandits duel multi-utilisateurs : une approche équitable utilisant le bien-être social de Nash

Définition du problème

L'article traite du problème des Bandits Duel Multi-Utilisateurs Équitables (Fair Multi-User Dueling Bandits), un cadre où un agent apprend à partir de données de préférences par paires fournies par $D$ utilisateurs distincts sur un horizon de temps $T$ avec $K$ bras. Contrairement aux bandits duel standards qui supposent un modèle de préférence unique ou agrègent les préférences en une seule matrice, ce travail considère un scénario où chaque utilisateur $d$ possède une matrice de préférences potentiellement distincte $P_d$.

Le défi central est d'apprendre une politique qui équilibre les intérêts de ces utilisateurs hétérogènes sans marginaliser les groupes minoritaires. Les approches standard, qui optimisent le bien-être moyen (utilitaire), favorisent souvent la majorité statistique, conduisant à des résultats injustes pour les utilisateurs ayant des préférences divergentes. Pour y remédier, les auteurs définissent l'objectif en utilisant le Bien-être Social de Nash (NSW - Nash Social Welfare), qui maximise le produit des utilités des utilisateurs. Cet objectif pénalise intrinsèquement l'inégalité, garantissant qu'aucun utilisateur ne voit son utilité tomber à zéro.

Un obstacle technique critique dans ce cadre est l'absence de récompenses absolues ; le retour d'information est purement relatif (résultats binaires indiquant quel bras est préféré entre deux bras). Pour définir l'utilité dans ce cadre relatif, les auteurs supposent l'existence d'un vainqueur de Condorcet pour chaque utilisateur (un bras qui bat tous les autres bras avec une probabilité $> 0,5$). L'utilité de l'utilisateur est alors définie comme un score dérivé de la probabilité qu'un bras batte le vainqueur de Condorcet spécifique de cet utilisateur.

Méthodologie

Cadre théorique

Les auteurs formalisent le problème en définissant une fonction de score $s_d(i) = 2P_{d, i, a^*_d}$, où $a^*_d$ est le vainqueur de Condorcet pour l'utilisateur $d$. L'utilité d'une politique $\pi$ pour l'utilisateur $d$ est l'espérance du score $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. L'objectif global est le Bien-être Social de Nash :
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
Le but est de minimiser le regret cumulé attendu par rapport à la politique optimale $\pi^*$ qui maximise ce produit.

Analyse de complexité (Hardness)

L'article établit une borne inférieure de regret fondamentale de $\Omega(T^{2/3} \min(K, D)^{1/3})$. Ce résultat démontre que l'exigence de maximiser le NSW parmi des utilisateurs ayant des vainqueurs de Condorcet conflictuels introduit une difficulté significative par rapport aux bandits duel standards (qui atteignent généralement un regret de $O(\log T)$). La difficulté réside dans le fait que l'algorithme doit jouer des vainqueurs de Condorcet "mauvais" (optimaux pour un utilisateur mais produisant une utilité proche de zéro pour les autres) afin de les distinguer des vainqueurs "bons", créant ainsi un compromis entre les coûts d'exploration et le regret instantané.

Algorithmes

Deux algorithmes sont proposés pour atteindre cet objectif, intégrant tous deux une phase d'identification du vainqueur de Condorcet :

1. Fair-Explore-Then-Commit (Fair-ETC) :

   • Phase 1 (Identification) : Utilise un algorithme de tournoi Dvoretzky-Kiefer-Wolfowitz (DKWT) modifié pour identifier l'ensemble des vainqueurs de Condorcet $\hat{A}^*$ pour tous les $D$ utilisateurs. Cette phase exploite les interactions partagées pour mettre à jour simultanément les marges empiriques pour tous les utilisateurs.
   • Phase 2 (Exploration) : Estime les scores de tous les bras par rapport aux vainqueurs de Condorcet identifiés.
   • Phase 3 (Engagement) : Calcule la politique $\hat{\pi}$ qui maximise le NSW empirique et s'y engage pour le reste de l'horizon.

2. Fair-$\epsilon$-Greedy :

   • Cet algorithme entrelace exploration et exploitation tout au long de l'horizon.
   • Il commence par la même phase d'identification du vainqueur de Condorcet.
   • À chaque étape $t$, avec une probabilité $\epsilon_t$, il explore en jouant des paires impliquant les vainqueurs de Condorcet estimés (en utilisant un calendrier round-robin) pour affiner les estimations de score.
   • Avec une probabilité $1-\epsilon_t$, il exploite en jouant la politique qui maximise le NSW empirique actuel.
   • Le taux d'exploration $\epsilon_t$ décroît au fil du temps pour assurer la convergence.

Les deux algorithmes sont prouvés pour atteindre une borne supérieure de regret de $\tilde{O}(T^{2/3})$, correspondant à la dépendance de la borne inférieure vis-à-vis de l'horizon temporel $T$ à un facteur logarithmique près.

Contributions clés

1. Formalisation du problème : La première formalisation du problème du Bandit Duel Multi-Utilisateurs Équitable, modélisant les utilités distinctes des utilisateurs basées sur leurs vainqueurs de Condorcet individuels et adoptant le NSW comme objectif d'équité.
2. Borne inférieure de regret : La dérivation d'une borne inférieure de regret de $\Omega(T^{2/3} \min(K, D)^{1/3})$, ce que les auteurs affirment être le premier résultat quantifiant le coût de l'équité dans les bandits duel avec des préférences hétérogènes.
3. Solutions algorithmiques : La proposition des algorithmes Fair-ETC et Fair-$\epsilon$-Greedy, accompagnés de bornes supérieures de regret théoriques qui correspondent à la dépendance de la borne inférieure vis-à-vis de $T$.
4. Validation empirique : Des simulations approfondies démontrant que les algorithmes proposés surpassent les bases utilitaires en termes de métriques d'équité (coefficient de Gini, utilité minimale de l'utilisateur) tout en maintenant un regret cumulé compétitif.

Résultats expérimentaux

Les auteurs ont évalué leurs algorithmes sur des préférences générées aléatoirement et sur des données réelles (le jeu de données Sushi, regroupées en utilisateurs macroscopiques).

• Préférences aléatoires : À travers diverses configurations d'utilisateurs ($D$) et de bras ($K$), tant Fair-ETC que Fair-$\epsilon$-Greedy ont démontré un regret sous-linéaire, surpassant systématiquement les bases utilitaires et une base uniforme sur les utilisateurs.
• Métriques d'équité : Les algorithmes proposés ont atteint le Bien-être Social de Nash le plus élevé et des coefficients de Gini nettement inférieurs par rapport aux approches utilitaires. Ils ont également maintenu une utilité minimale d'utilisateur plus élevée, indiquant une meilleure protection des préférences minoritaires.
• Préférences groupées (Clustered) : Dans des scénarios de clusters distincts (majorité et minorité) simulant des préférences polarisées, les algorithmes utilitaires favorisaient la majorité, entraînant une forte inégalité. Les algorithmes équitables proposés ont réussi à équilibrer les intérêts, maintenant de faibles coefficients de Gini et une utilité minimale élevée.
• Jeu de données Sushi : Sur les données réelles, les méthodes proposées ont obtenu le regret cumulé le plus faible dans les configurations de clusters $D=5$ et $D=10$. Bien qu'une base uniforme ait montré une équité légèrement meilleure dans le cas fragmenté $D=10$, elle souffrait d'un regret nettement inférieur.

Signification et affirmations

L'article affirme être le premier travail à quantifier le coût de l'équité dans les bandits duel avec des préférences hétérogènes, établissant une borne inférieure de regret fondamentale de $\Omega(T^{2/3})$. Les auteurs positionnent leur travail comme une étape nécessaire vers un apprentissage automatique centré sur l'humain, où l'optimisation de la préférence moyenne est insuffisante et potentiellement préjudiciable aux groupes minoritaires.

En intégrant l'objectif du Bien-être Social de Nash dans le cadre du bandit duel, ce travail fournit une base théorique et algorithmique pour apprendre des politiques qui équilibrent efficacité et équité. Les auteurs notent que leur approche est distincte des travaux antérieurs sur les bandits multi-agents (ex: Hossain et al., 2021 ; Jones et al., 2023) car elle opère dans un cadre de préférence relative plutôt qu'avec des récompenses absolues, nécessitant des techniques d'estimation d'utilité fondamentalement différentes.

L'article conclut modestement, reconnaissant que des travaux futurs pourraient étendre ce cadre aux bandits duels contextuels, aux espaces d'actions continus, et aux scénarios où l'hypothèse du vainqueur de Condorcet ne tient pas (en utilisant potentiellement les scores de Copeland ou de Borda).