Technische Samenvatting: Multi-User Dueling Bandits: Een Rechtvaardige Benadering met behulp van Nash Social Welfare

Probleemdefinitie

Het artikel behandelt het Fair Multi-User Dueling Bandit probleem, een scenario waarin een agent leert van gepaard gegroeide voorkeurscdata van $D$ verschillende gebruikers over een tijdshorizon $T$ met $K$ armen. In tegenstelling tot standaard dueling bandits die een enkel voorkeursmodel veronderstellen of voorkeuren aggregeren in een enkele matrix, beschouwt dit werk een scenario waarin elke gebruiker $d$ een potentieel onderscheidende voorkeursmatrix $P_d$ bezit.

De kernuitdaging is het leren van een beleid dat de belangen van deze heterogene gebruikers in evenwicht brengt zonder minderheidsgroepen te marginaliseren. Standaard benaderingen die optimaliseren voor gemiddelde (utilitaire) welvaart zijn vaak gericht op de statistische meerderheid, wat leidt tot onrechtvaardige uitkomsten voor gebruikers met afwijkende voorkeuren. Om dit aan te pakken, definiëren de auteurs het doel via Nash Social Welfare (NSW), wat de product van de gebruikersnutten maximaliseert. Dit doel bestraft inherent ongelijkheid en zorgt ervoor dat het nut van geen enkele gebruiker naar nul wordt gedreven.

Een kritieke technische hindernis in deze setting is het gebrek aan absolute beloningen; feedback is puur relatief (binaire uitkomsten die aangeven welke van twee armen de voorkeur geniet). Om nut in deze relatieve setting te definiëren, nemen de auteurs aan dat er voor elke gebruiker een Condorcet-winnaar bestaat (een arm die elke andere arm verslaat met een waarschijnlijkheid $>0.5$). Het nut van een gebruiker wordt dan gedefinieerd als een score afgeleid van de waarschijnlijkheid dat een arm die specifieke Condorcet-winnaar van die gebruiker verslaat.

Methodologie

Theoretisch Kader

De auteurs formaliseren het probleem door een scorefunctie $s_d(i) = 2P_{d, i, a^*_d}$ te definiëren, waarbij $a^*_d$ de Condorcet-winnaar is voor gebruiker $d$. Het nut van een beleid $\pi$ voor gebruiker $d$ is de verwachte score $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. Het globale doel is de Nash Social Welfare:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
Het doel is om de verwachte cumulatieve regret te minimaliseren ten opzichte van het optimale beleid $\pi^*$ dat deze product maximaliseert.

Hardheidsanalyse

Het artikel stelt een fundamentele regret lower bound vast van $\Omega(T^{2/3} \min(K, D)^{1/3})$. Dit resultaat toont aan dat de vereiste om NSW te maximaliseren bij gebruikers met conflicterende Condorcet-winnaars een significante hardheid introduceert vergeleken met standaard dueling bandits (die doorgaans $O(\log T)$ regret bereiken). De moeilijkheid ontstaat doordat het algoritme "slechte" Condorcet-winnaars moet spelen (optimaal voor één gebruiker maar met bijna nul nut voor anderen) om hen te onderscheiden van "goede" winnaars, wat een afweging creëert tussen exploratiekosten en instantane regret.

Algoritmen

Twee algoritmen worden voorgesteld om dit doel te bereiken, die beide een Condorcet-winnaar identificatiefase bevatten:

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

   • Fase 1 (Identificatie): Gebruikt een aangepast Dvoretzky-Kiefer-Wolfowitz Tournament (DKWT) algoritme om de verzameling Condorcet-winnaars $\hat{A}^*$ voor alle $D$ gebruikers te identificeren. Deze fase maakt gebruik van gedeelde interacties om de empirische marges voor alle gebruikers simultaan bij te werken.
   • Fase 2 (Exploratie): Schat de scores van alle armen relatief aan de geïdentificeerde Condorcet-winnaars.
   • Fase 3 (Commitment): Berekent het beleid $\hat{\pi}$ dat de empirische NSW maximaliseert en zet zich hiervoor in voor de rest van de horizon.

2. Fair-$\epsilon$-Greedy:

   • Dit algoritme wisselt exploratie en exploitatie gedurende de horizon af.
   • Het begint met dezelfde Condorcet-winnaar identificatiefase.
   • Op elk tijdstip $t$ verkent het met waarschijnlijkheid $\epsilon_t$ door paren te spelen die de geschatte Condorcet-winnaars bevatten (met een round-robin schema) om de score-schattingen te verfijnen.
   • Met waarschijnlijkheid $1-\epsilon_t$ exploiteert het door het beleid te spelen dat de huidige empirische NSW maximaliseert.
   • De exploratiesnelheid $\epsilon_t$ neemt in de loop van de tijd af om convergentie te waarborgen.

Beide algoritmen zijn bewezen een regret upper bound van $\tilde{O}(T^{2/3})$ te bereiken, wat de afhankelijkheid van de algoritme-efficiëntie van de tijdshorizon $T$ matcht tot aan de logaritmische factoren.

Belangrijkste Bijdragen

1. Probleemformulering: De eerste formalisering van het Fair Multi-User Dueling Bandit probleem, waarbij afzonderlijke gebruikersnutten worden gemodelleerd op basis van individuele Condorcet-winnaars en NSW als het rechtvaardigheidsdoel wordt aangenomen.
2. Regret Lower Bound: De afleiding van een regret lower bound van $\Omega(T^{2/3} \min(K, D)^{1/3})$, wat volgens de auteurs het eerste resultaat is dat de kosten van rechtvaardigheid kwantificeert in dueling bandits met heterogene voorkeuren.
3. Algoritmische Oplossingen: De voorstel van de Fair-ETC en Fair-$\epsilon$-Greedy algoritmen, vergezeld van theoretische regret upper bounds die de afhankelijkheid van de lower bound van $T$ matchen.
4. Empirische Validatie: Uitgebreide simulaties die aantonen dat de voorgestelde algoritmen de utilitaire baselines overtreffen op het gebied van rechtvaardigheidsmetrieken (Gini-coëfficiënt, minimum gebruikerswelvaart) terwijl ze een concurrerende cumulatieve regret behouden.

Experimentele Resultaten

De auteurs hebben hun algoritmen geëvalueerd op zowel willekeurig gegenereerde voorkeuren als op echte data (de Sushi-dataset, geclusterd in macroscopische gebruikers).

• Willekeurige Voorkeuren: Over diverse configuraties van gebruikers ($D$) en armen ($K$), vertoonden zowel Fair-ETC als Fair-$\epsilon$-Greedy sublineaire regret, waarbij ze de utilitaire baselines en een uniform-over-gebruikers baseline consistent overtroffen.
• Rechtvaardigheidsmetrieken: De voorgestelde algoritmen bereikten de hoogste Nash Social Welfare en aanzienlijk lagere Gini-coëfficiënten vergeleken met utilitaire benaderingen. Ze behielden ook een hogere minimum gebruikerswelvaart, wat wijst op een betere bescherming van minderheidsvoorkeuren.
• Geclusterde Voorkeuren: In scenario's met duidelijke meerderheids- en minderheidsclusters (simulatie van gepolariseerde voorkeuren), bevoordeelden utilitaire algoritmen de meerderheid, wat leidde tot hoge ongelijkheid. De voorgestelde rechtvaardige algoritmen brachten de belangen succesvol in evenwicht, waarbij lage Gini-coëfficiënten en een hoge minimum welvaart werden behouden.
• Sushi Dataset: Op echte data bereikten de voorgestelde methoden de laagste cumulatieve regret in zowel de $D=5$ als de $D=10$ clusterinstellingen. Hoewel een uniforme baseline in de sterk gefragmenteerde $D=10$ casus een iets betere rechtvaardigheid vertoonde, leed deze aan een vele malen inferieure regret.

Betekenis en Claims

Het artikel claimt het eerste werk te zijn dat de kosten van rechtvaardigheid in dueling bandits met heterogene voorkeuren kwantificeert, door een fundamentele regret lower bound van $\Omega(T^{2/3})$ vast te stellen. De auteurs positioneren hun werk als een noodzakelijke stap naar mensgerichte machine learning, waarbij het optimaliseren voor de gemiddelde voorkeur onvoldoende is en potentieel schadelijk voor minderheidsgroepen.

Door de Nash Social Welfare doelstelling in het dueling bandit framework te integreren, biedt het werk een theoretische en algoritmische basis voor het leren van beleid dat efficiëntie met rechtvaardigheid in evenwicht brengt. De auteurs merken op dat hun benadering verschilt van eerdere multi-agent bandit werk (bijv. Hossain et al., 2021; Jones et al., 2023) omdat het opereert in een setting van relatieve voorkeuren in plaats van een setting met absolute beloningen, wat fundamenteel andere technieken voor nutsschatting vereist.

Het artikel sluit bescheiden af door te erkennen dat toekomstig werk dit framework kan uitbreiden naar contextuele dueling bandits, continue actieruimtes, en settings waar de Condorcet-winnaar assumptie niet standhoudt (mogelijk door gebruik te maken van Copeland of Borda scores).