🤖 machine learning

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

Diese Arbeit befasst sich mit Fairness in Multi-User-Dueling-Bandits, indem sie eine Nash-Social-Welfare-Zielgröße zur Vermeidung der Marginalisierung von Minderheiten einführt, eine neuartige $O(T^{2/3})$ -Regret-Untergrenze für heterogene Präferenzen etabliert und Algorithmen vorschlägt, die passende Obergrenzen erreichen.

Ursprüngliche Autoren: Maheed H. Ahmed, Mahsa Ghasemi

Veröffentlicht 2026-06-16

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maheed H. Ahmed, Mahsa Ghasemi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der DJ auf einer riesigen Party mit Hunderten von Gästen. Ihre Aufgabe ist es, das perfekte Lied auszuwählen, das als Nächstes gespielt werden soll. Aber hier ist der Haken: Sie dürfen nicht jeden fragen: „Was wollt ihr hören?“ Stattdessen müssen Sie raten, indem Sie zwei Lieder direkt hintereinander spielen und sehen, welches dem Publikum besser gefällt. Dies ist die Grundidee eines Dueling Bandit-Problems: zu lernen, was die Leute mögen, indem man Optionen vergleicht, anstatt nach Bewertungen zu fragen.

Stellen Sie sich nun vor, die Party ist in verschiedene Gruppen unterteilt. Einige lieben Heavy Metal, andere Jazz und wieder andere Pop. Wenn Sie einfach versuchen, den „Durchschnittsmenschen“ zu gefallen, landen Sie vielleicht bei einem langweiligen Mix, den niemand wirklich genießt, oder schlimmer noch, Sie ignorieren die kleine Gruppe, die Jazz liebt, völlig, weil die Metal-Fans lauter sind.

Dieses Paper schlägt einen neuen Weg vor, der DJ zu sein, der sicherstellt, dass jeder eine faire Chance bekommt, Musik zu hören, die er mag, und nicht nur die Mehrheit.

Das Kernproblem: Die „Durchschnitts“-Falle

In den meisten Computersystemen ist das Ziel, die „Gesamtzugleichheit“ (die Summe der Freude aller) zu maximieren. Wenn 90 Leute Rock lieben und 10 Leute Jazz, wird das System nur Rock spielen. Die 10 Jazz-Fans erhalten null Glück. Das ist unfair. Das Paper argumentiert, dass ein System, das fair ist, auch die „Jazz-Fans“ nicht zurücklassen darf, selbst wenn sie eine Minderheit sind.

Die Lösung: Die „Gruppen-Glück“-Formel

Um dies zu lösen, verwenden die Autoren ein Konzept namens Nash Social Welfare (NSW).

Denken Sie an Folgendes:

Der alte Weg (Utilitaristisch): Sie addieren das Glück aller Personen. $90 + 10 = 100$ . Wenn Sie Rock spielen, sind die 90 Fans glücklich, aber die 10 sind unglücklich. Der Gesamtwert ist hoch, aber es ist unfair.
Der neue Weg (Nash Social Welfare): Anstatt zu addieren, multiplizieren Sie das Glück aller Beteiligten.
- Wenn die 10 Jazz-Fans ein Glück von 0 haben, wird der Gesamtwert zu 0 ( $90 \times 0 = 0$ ).
- Um einen hohen Wert zu erzielen, muss jeder zumindest ein kleines bisschen Glück empfinden.

Dieser mathematische Trick zwingt den Algorithmus, sich um die kleinste Gruppe zu kümmern. Es ist wie eine Kette: Die Kette ist nur so stark wie ihr schwächstes Glied.

Wie der Algorithmus funktioniert

Das Paper stellt zwei Hauptstrategien (Algorithmen) vor, um die beste Mischung an Liedern (oder „Arms“, wie sie in der Mathematik genannt werden) zu finden, die diese Fairness-Regel erfüllt.

Die „Erst lernen, dann spielen“-Strategie (Fair-Explore-Then-Commit):
- Phase 1 (Der Geschmackstest): Der DJ verbringt viel Zeit damit, verschiedene Paare von Liedern zu spielen, nur um genau herauszufinden, was jede Gruppe mag. Er sucht nach dem „Condorcet-Gewinner“ für jede Gruppe – im Grunde das eine Lied, das alle anderen für diese spezifische Gruppe schlägt.
- Phase 2 (Die Setlist): Sobald er sich sicher ist, dass er weiß, was alle mögen, hört er auf zu raten und spielt für den Rest der Party die perfekte Mischung, die das Glück aller Menschen ausbalanciert.
Die „Mix es auf“-Strategie (Fair- $\epsilon$ -Greedy):
- Diese Strategie ist flexibler. Sie spielt hauptsächlich die beste Mischung, die sie bisher kennt, spielt aber ab und zu absichtlich ein zufälliges Paar von Liedern, um ihre Annahmen zu überprüfen. Wenn sie merkt, dass sie sich über das irrte, was die Jazz-Fans mögen, kann sie ihre Meinung sofort ändern. Es ist wie ein DJ, der immer ein paar Überraschungssongs in der Tasche hat, falls sich die Stimmung der Menge ändert.

Die große Entdeckung: Fairness hat einen Preis

Die Autoren haben bewiesen, dass Fairness schwieriger ist als Effizienz.

Im alten „Durchschnitts“-System konnte der DJ das beste Lied sehr schnell lernen. Aber in diesem „fairen“ System muss der DJ zusätzliche Zeit investieren, um herauszufinden, was die leisen Minderheitsgruppen mögen, selbst wenn dies den Prozess verlangsamt, das „beste“ Lied für die Mehrheit zu finden.

Sie haben genau berechnet, wie viel langsamer dies ist. Sie fanden heraus, dass das „Regret“ (der Betrag an Glück, der verloren geht, weil der DJ das perfekte Lied noch nicht kannte) in einem spezifischen Verhältnis wächst: etwa proportional zur Zeit zum Quadrat, geteilt durch die Kubikwurzel der Anzahl der Gruppen.

Einfache Übersetzung: Je mehr verschiedene Gruppen es gibt und je mehr Optionen man zur Auswahl hat, desto länger dauert es, eine Lösung zu finden, die alle glücklich macht, im Vergleich zu einem System, das nur die Mehrheit glücklich macht.

Die Ergebnisse: Funktioniert es?

Die Autoren haben ihre Ideen mit Simulationen und echten Daten (unter Verwendung eines Datensatzes über die Sushi-Vorlieben von Menschen) getestet.

Das Ergebnis: Ihre „fairen“ Algorithmen konnten den „Gini-Koeffizienten“ (ein Maß für Ungleichheit) erfolgreich niedrig halten.
Der Kompromiss: Die „unfairen“ Algorithmen (die nur das Gesam Glück maximieren) machten die Mehrheit sehr glücklich, ließen die Minderheit aber mit fast nichts zurück. Die „fairen“ Algorithmen machten die Mehrheit etwas weniger glücklich als die unfairen, aber sie stellten sicher, dass die Minderheit ebenfalls zufrieden war.
Der Gewinner: Die „fairen“ Algorithmen erreichten den höchsten Nash Social Welfare-Wert, was bedeutet, dass sie die beste Balance fanden, bei der keine Gruppe völlig ignoriert wurde.

Zusammenfassung

Dieses Paper lehrt uns, dass wir, wenn wir ein System bauen wollen, das jeden fair behandelt, nicht einfach nur auf den Durchschnitt schauen können. Man muss eine spezielle mathematische Linse verwenden (Nash Social Welfare), die das System dazu zwingt, sich auch um die kleinsten Gruppen zu kümmern. Es erfordert etwas mehr Zeit und Mühe, zu lernen, was jeder möchte, aber das Ergebnis ist ein System, in dem niemand im Kalten stehen gelassen wird.

Technisches Resümee: Multi-User Dueling Bandits: Ein fairer Ansatz unter Verwendung von Nash-Sozialwohlfahrt

Problemdefinition

Die Arbeit befasst sich mit dem Fair Multi-User Dueling Bandit Problem, einem Szenario, in dem ein Agent aus paarweisen Präferenzdaten lernt, die von $D$ unterschiedlichen Nutzern über einen Zeithorizont $T$ mit $K$ Armen bereitgestellt werden. Im Gegensatz zu Standard-Dueling-Bandits, die eine einzige Präferenzmatrix oder aggregierte Präferenzen in eine einzige Matrix annehmen, betrachtet diese Arbeit ein Szenario, in dem jeder Nutzer $d$ eine potenziell eigene Präferenzmatrix $P_d$ besitzt.

Die zentrale Herausforderung besteht darin, eine Policy zu erlernen, die die Interessen dieser heterogenen Nutzer ausbalanciert, ohne Minderheiten zu marginalisieren. Standardansätze, die auf das durchschnittliche (utilitäre) Wohlfahrt optimieren, bevorzugen oft die statistische Mehrheit, was zu unfairen Ergebnissen für Nutzer mit divergierenden Präferenzen führt. Um dies zu adressieren, definieren die Autoren das Ziel mittels der Nash-Sozialwohlfahrt (NSW), welche das Produkt der Nutzer-Utilitäten maximiert. Dieses Ziel bestraft Ungleichheit inhärent und stellt sicher, dass der Nutzen eines einzelnen Nutzers nicht gegen Null geht.

Eine kritische technische Hürde in diesem Setting ist das Fehlen absoluter Belohnungen; das Feedback ist rein relativ (binäre Ergebnisse, die angeben, welcher von zwei Armen bevorzugt wird). Um den Nutzen in diesem relativen Setting zu definieren, nehmen die Autoren die Existenz eines Condorcet-Gewinners für jeden Nutzer an (ein Arm, der jeden anderen Arm mit einer Wahrscheinlichkeit $>0,5$ schlägt). Der Nutzer-Nutzen wird dann als ein Score definiert, der aus der Wahrscheinlichkeit abgeleitet ist, mit der ein Arm den spezifischen Condorcet-Gewinner dieses Nutzers schlägt.

Methodik

Theoretischer Rahmen

Die Autoren formalisieren das Problem, indem sie eine Scoring-Funktion $s_d(i) = 2P_{d, i, a^*_d}$ definieren, wobei $a^*_d$ der Condorcet-Gewinner für Nutzer $d$ ist. Der Nutzen einer Policy $\pi$ für Nutzer $d$ ist der erwartete Score $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$ . Das globale Ziel ist die Nash-Sozialwohlfahrt:
$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$
Das Ziel ist es, den erwarteten kumulativen Regret im Verhältnis zur optimalen Policy $\pi^*$ zu minimieren, die dieses Produkt maximiert.

Komplexitätsanalyse (Hardness Analysis)

Die Arbeit etabliert eine fundamentale Regret-Untergrenze von $\Omega(T^{2/3} \min(K, D)^{1/3})$ . Dieses Ergebnis zeigt, dass die Anforderung, die NSW unter Nutzern mit widersprüchlichen Condorcet-Gewinnern zu maximieren, eine signifikante Schwierigkeit gegenüber Standard-Dueling-Bandits (die typischerweise einen Regret von $O(\log T)$ erreichen) einführt. Die Schwierigkeit ergibt sich daraus, dass der Algorithmus „schlechte“ Condorcet-Gewinner spielen muss (optimal für einen Nutzer, aber mit einem Nutzen nahe Null für andere), um sie von „guten“ Gewinnern zu unterscheiden, was einen Trade-off zwischen Explorationskosten und instantanem Regret erzeugt.

Algorithmen

Es werden zwei Algorithmen vorgeschlagen, die dieses Ziel verfolgen und beide eine Identifikationsphase für den Condorcet-Gewinner beinhalten:

Fair-Explore-Then-Commit (Fair-ETC):
- Phase 1 (Identifikation): Verwendet einen modifizierten Dvoretzky-Kiefer-Wolfowitz-Tournament (DKWT) Algorithmus, um die Menge der Condorcet-Gewinner $\hat{A}^*$ für alle $D$ Nutzer zu identifizieren. Diese Phase nutzt gemeinsame Interaktionen, um die empirischen Margen für alle Nutzer gleichzeitig zu aktualisieren.
- Phase 2 (Exploration): Schätzt die Scores aller Arme relativ zu den identifizierten Condorcet-Gewinnern.
- Phase 3 (Commitment): Berechnet die Policy $\hat{\pi}$ , die die empirische NSW maximiert, und verpflichtet sich an diese für den verbleibenden Horizont.
Fair- $\epsilon$ -Greedy:
- Dieser Algorithmus verwebt Exploration und Exploitation über den gesamten Horizont hinweg.
- Er beginnt mit derselben Identifikationsphase für den Condorcet-Gewinner.
- In jedem Schritt $t$ exploriert er mit einer Wahrscheinlichkeit $\epsilon_t$ , indem er Paare spielt, die die geschätzten Condorcet-Gewinner beinhalten (unter Verwendung eines Round-Robin-Schemas), um die Score-Schätzungen zu verfeinern.
- Mit einer Wahrscheinlichkeit von $1-\epsilon_t$ exploriert er, indem er die Policy spielt, die die aktuelle empirische NSW maximiert.
- Die Explorationsrate $\epsilon_t$ nimmt über die Zeit ab, um die Konvergenz zu gewährleisten.

Beide Algorithmen erfüllen eine Regret-Obergrenze von $\tilde{O}(T^{2/3})$ , was der Abhängigkeit der Untergrenze vom Zeithorizont $T$ bis auf logarithmische Faktoren entspricht.

Zentrale Beiträge

Problemformulierung: Die erste Formalisierung des Fair Multi-User Dueling Bandit Problems, welches distinkte Nutzer-Utilitäten basierend auf individuellen Condorcet-Gewinnern modelliert und die NSW als Fairness-Ziel verwendet.
Regret-Untergrenze: Die Ableitung einer Regret-Untergrenze von $\Omega(T^{2/3} \min(K, D)^{1/3})$ , die die Autoren als das erste Ergebnis anführen, welches die Kosten der Fairness in Dueling Bandits mit heterogenen Präferenzen quantifiziert.
Algorithmische Lösungen: Der Vorschlag der Algorithmen Fair-ETC und Fair- $\epsilon$ -Greedy, begleitet von theoretischen Regret-Obergrenzen, die der Abhängigkeit der Untergrenze von $T$ entsprechen.
Empirische Validierung: Umfangreiche Simulationen, die zeigen, dass die vorgeschlagenen Algorithmen utilitäre Baselines in Fairness-Metriken (Gini-Koeffizient, minimaler Nutzer-Nutzen) übertreffen und gleichzeitig kompetitive kumulative Regret beibehalten.

Experimentelle Ergebnisse

Die Autoren evaluierten ihre Algorithmen sowohl mit zufällig generierten Präferenzen als auch mit realen Daten (dem Sushi-Datensatz, gruppiert in makroskopische Nutzer).

Zufällige Präferenzen: Über verschiedene Konfigurationen von Nutzern ( $D$ ) und Armen ( $K$ ) zeigten sowohl Fair-ETC als auch Fair- $\epsilon$ -Greedy einen sublinearen Regret und übertrafen konsistent utilitäre Baselines sowie eine Uniform-über-Nutzer-Baseline.
Fairness-Metriken: Die vorgeschlagenen Algorithmen erreichten die höchste Nash-Sozialwohlfahrt und signifikant niedrigere Gini-Koeffizienten im Vergleich zu utilitären Ansätzen. Sie hielten auch einen höheren minimalen Nutzer-Nutzen aufrecht, was auf einen besseren Schutz für Minderheiten-Präferenzen hindeutet.
Geklusterte Präferenzen: In Szenarien mit distinkten Mehrheits- und Minderheiten-Clustern (was polarisierte Präferenzen simuliert), bevorzugten utilitäre Algorithmen die Mehrheit, was zu hoher Ungleichheit führte. Die vorgeschlagenen fairen Algorithmen balancierten die Interessen erfolgreich aus und hielten niedrige Gini-Koeffizienten sowie hohen minimalen Nutzen aufrecht.
Sushi-Datensatz: Bei realen Daten erreichten die vorgeschlagenen Methoden den geringsten kumulativen Regret in beiden $D=5$ und $D=10$ Cluster-Settings. Während eine Uniform-Baseline im hochgradig fragmentierten $D=10$ Fall eine etwas bessere Fairness zeigte, litt sie unter einem wesentlich schlechteren Regret.

Bedeutung und Ansprüche

Die Arbeit beansprucht, die erste Arbeit zu sein, welche die Kosten der Fairness in Dueling Bandits mit heterogenen Präferenzen quantifiziert und eine fundamentale Regret-Untergrenze von $\Omega(T^{2/3})$ etabliert. Die Autoren positionieren ihre Arbeit als notwendigen Schritt hin zu einem menschenzentrierten maschinellen Lernen, bei dem die Optimierung für die durchschnittliche Präferenz unzureichend und potenziell schädlich für Minderheitengruppen ist.

Durch die Integration des Nash-Sozialwohlfahrt-Ziels in das Dueling-Bandit-Framework bietet die Arbeit eine theoretische und algorithmische Grundlage für das Erlernen von Policies, die Effizienz mit Fairness in Einklang bringen. Die Autoren merken an, dass sich ihr Ansatz von vorheriger Multi-Agent-Bandit-Arbeit unterscheidet (z. B. Hossain et al., 2021; Jones et al., 2023), da er in einem relativen Präferenzsetting operiert statt mit absoluten Belohnungen, was grundlegend andere Techniken zur Schätzung des Nutzens erfordert.

Die Arbeit schließt bescheiden mit dem Hinweis, dass zukünftige Arbeiten diesen Rahmen auf kontextuelle Dueling Bandits, kontinuierliche Aktionsräume und Szenarien erweitern könnten, in denen die Condorcet-Gewinner-Annahme nicht gilt (potenziell unter Verwendung von Copeland- oder Borda-Scores).