💬 NLP

Online Learning and Equilibrium Computation with Ranking Feedback

Diese Arbeit untersucht Online-Lernmodelle mit Rangordnungs-Feedback statt numerischer Nutzenwerte, zeigt Grenzen der Regret-Minimierung auf und entwickelt Algorithmen, die unter bestimmten Bedingungen sublinearen Regret sowie die Konvergenz zu einem grob korrelierten Gleichgewicht in Spielen ermöglichen.

Ursprüngliche Autoren: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

Veröffentlicht 2026-03-20

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

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

Das große Problem: Wir können nicht immer Zahlen nennen

Stell dir vor, du bist ein Koch, der neue Gerichte entwickelt. Normalerweise würdest du von deinen Gästen eine Bewertung auf einer Skala von 1 bis 10 erwarten. Aber in der echten Welt funktioniert das oft nicht:

Privatsphäre: Die Gäste wollen nicht verraten, wie viel Geld sie für das Essen ausgeben würden.
Schwierigkeit: Es ist für Menschen viel einfacher zu sagen: "Ich mag das Curry eher als das Pizza", als eine genaue Zahl zu nennen.

Das ist das Kernproblem, das dieses Papier untersucht: Wie lernt ein System (wie ein Algorithmus), wenn es nur Reihenfolgen (Ranglisten) bekommt, aber keine genauen Zahlen?

Die zwei Arten von Feedback

Die Forscher unterscheiden zwischen zwei Szenarien, wie diese Ranglisten entstehen:

Der "Sofort-Effekt" (InstUtil): Ein Gast kommt, probiert drei Gerichte, sagt "Das Curry war am besten, dann die Pizza, dann die Pasta" und geht sofort wieder. Die Bewertung basiert nur auf diesem einen Moment.
Der "Langzeit-Effekt" (AvgUtil): Ein Stammgast kommt jeden Tag. Er vergleicht das Essen nicht nur heute, sondern mit dem, was er in den letzten Wochen gegessen hat. "Heute war das Curry gut, aber letzte Woche war es noch besser." Die Bewertung basiert auf dem Durchschnitt über die Zeit.

Die schlechte Nachricht: Manchmal ist es unmöglich

Die Forscher haben herausgefunden, dass es in manchen Fällen unmöglich ist, aus diesen Ranglisten zu lernen, wenn die Umgebung sehr chaotisch ist (wie ein listiger Gegner, der absichtlich verwirrende Gerichte serviert).

Die Analogie: Stell dir vor, du versuchst, die beste Route durch eine Stadt zu finden, aber die Ampeln schalten sich zufällig um, und du bekommst nur gesagt: "Route A war schneller als Route B". Wenn sich die Straßenbedingungen zu schnell ändern, kannst du keine stabile Regel finden.
Das Ergebnis: Wenn die "Temperatur" (ein Maß für Unsicherheit im System) sehr niedrig ist (die Leute sind sich also sehr sicher in ihren Vorlieben), aber die Umgebung extrem chaotisch ist, wird der Algorithmus scheitern. Er kann keine sublineare "Reue" (Regret) erreichen. Das bedeutet: Er wird immer schlechter abschneiden als der perfekte Koch, der alles im Nachhinein gewusst hätte.

Die gute Nachricht: Wir haben einen Plan!

Aber keine Sorge! Die Forscher haben nicht aufgegeben. Sie haben neue Algorithmen entwickelt, die funktionieren, wenn wir eine kleine Annahme machen:

Die Annahme: Die Vorlieben der Gäste ändern sich nicht plötzlich und wild, sondern eher langsam und stetig. (Wenn die Gäste heute Curry mögen, mögen sie es morgen wahrscheinlich auch noch, vielleicht mit einer kleinen Änderung).

Unter dieser Bedingung haben sie Algorithmen gebaut, die:

Die Ranglisten clever in Schätzwerte umwandeln.
Schritt für Schritt lernen, welche Aktionen (Gerichte) die besten sind.
Am Ende fast so gut abschneiden wie der perfekte Koch.

Der Clou: Das Gleichgewicht im Spiel

Das Papier geht noch einen Schritt weiter und betrachtet ein Spiel mit vielen Spielern (z. B. ein Online-Dating-Portal oder eine Ride-Sharing-App wie Uber).

Das Ziel: Nicht nur, dass jeder für sich lernt, sondern dass sich ein Gleichgewicht einstellt. Niemand hat einen Grund, seine Strategie zu ändern, weil alle zufrieden sind.
Das Ergebnis: Wenn alle Spieler den neuen Algorithmus benutzen, finden sie automatisch ein stabiles Gleichgewicht, auch wenn sie nur Ranglisten (wer mag wen?) sehen und keine Zahlen (wie sehr mag ich wen?) austauschen.

Ein echtes Beispiel: KI-Routing

Um zu zeigen, dass das funktioniert, haben die Forscher ein Szenario mit Künstlicher Intelligenz (LLMs) simuliert.

Die Situation: Ein Nutzer stellt eine Frage. Der Server hat Zugriff auf verschiedene KI-Modelle (z. B. eines ist gut in Mathe, eines in kreatives Schreiben).
Das Problem: Der Server weiß nicht genau, welches Modell der Nutzer gerade braucht.
Die Lösung: Der Server schlägt dem Nutzer mehrere Antworten vor. Der Nutzer sagt nur: "Antwort A war besser als Antwort B".
Der Erfolg: Der Algorithmus lernt aus diesen Vergleichen, welches Modell für welchen Nutzer am besten passt, und wird mit der Zeit immer besser darin, die richtige KI auszuwählen.

Zusammenfassung in einem Satz

Dieses Papier zeigt, wie man Computer lehren kann, aus bloßen "Besser-als"-Vergleichen zu lernen (statt aus genauen Zahlen), damit sie in chaotischen Umgebungen und bei komplexen Spielen (wie Dating-Apps oder KI-Routing) die bestmöglichen Entscheidungen treffen können, solange sich die Vorlieben nicht zu wild ändern.

1. Problemstellung

Das Paper untersucht das Online-Lernen in nicht-stochastischen und potenziell adversären Umgebungen, wobei die Rückmeldung (Feedback) nicht in Form numerischer Nutzenwerte (Utilities), sondern als Rangfolge (Ranking) über vorgeschlagene Aktionen erfolgt.

Kontext: In vielen realen Anwendungen (z. B. RLHF bei Sprachmodellen, Empfehlungssysteme, Dating-Plattformen) ist es für Nutzer oft einfacher, eine Rangfolge von Optionen zu erstellen, als genaue numerische Bewertungen abzugeben. Zudem können numerische Werte aus Datenschutzgründen unzugänglich sein.
Herausforderung: Die meisten bestehenden Algorithmen für Online-Lernen und Gleichgewichtsberechnung in der Spieltheorie (z. B. zur Berechnung von Coarse Correlated Equilibria, CCE) setzen numerisches Feedback voraus. Das Fehlen numerischer Werte erschwert die Schätzung der tatsächlichen Nutzenfunktionen und die Minimierung des externen Regrets (External Regret).
Feedback-Modelle: Das Paper unterscheidet zwei Arten der Rangfolge-Bildung basierend auf dem Plackett-Luce-Modell (PL) mit einem Temperatur-Parameter $\tau$ $τ$ :
1. InstUtil Rank: Die Rangfolge basiert auf der momentanen Nutzenfunktion $u(t)$ zum Zeitpunkt $t$ .
2. AvgUtil Rank: Die Rangfolge basiert auf der zeitlichen Durchschnittsnutzenfunktion $\frac{1}{t}\sum_{s=1}^t u(s)$ bis zum Zeitpunkt $t$ .
Feedback-Szenarien: Unterscheidung zwischen Full-Information (alle Aktionen werden vorgeschlagen und gerankt) und Bandit (nur eine Teilmenge von $K$ Aktionen wird vorgeschlagen).

2. Methodik und Algorithmen

Die Autoren entwickeln einen Rahmen, der es ermöglicht, numerische Nutzenvektoren aus den beobachteten Permutationen zu schätzen und diese Schätzungen in Standard-Online-Lernalgorithmen (wie FTRL oder Projektionsgradientenabstieg) zu integrieren.

A. Härteergebnisse (Lower Bounds)

Bevor positive Ergebnisse erzielt werden, werden fundamentale Grenzen aufgezeigt:

InstUtil Rank: Es wird bewiesen, dass sublineares Regret im Allgemeinen unmöglich ist, selbst wenn nur zwei Aktionen existieren. Der Grund liegt darin, dass bei adversären Nutzenvektoren die Rangfolgen in verschiedenen Szenarien identisch sein können, während die optimalen Strategien diametral entgegengesetzt sind.
AvgUtil Rank: Auch hier ist sublineares Regret unmöglich, wenn das Ranking-Modell zu deterministisch ist (d. h. $\tau \to 0$ oder sehr klein im Verhältnis zu $T$ ). In diesem Fall enthält das Feedback zu wenig Information über die Lücken zwischen den Nutzenwerten.

B. Positive Ergebnisse unter Annahmen

Um sublineares Regret zu erreichen, führen die Autoren die Annahme einer sublinearen Variation der Nutzenvektoren ein (Assumption 5.2): Die kumulierte Variation $\sum \|u(t) - u(t-1)\|$ wächst sublinear mit $T$ .

Utility Estimation (Schätzung der Nutzen):
- Der Kern der Methode ist ein Schätzer (Algorithmus 1), der die beobachteten Permutationen nutzt, um die zugrunde liegenden Nutzenwerte zu rekonstruieren.
- Da das PL-Modell nicht-konvex ist, wird das Ranking in paarweise Vergleiche zerlegt. Die Wahrscheinlichkeit, dass Aktion $a$ vor $b$ rangiert, folgt einer logistischen Funktion der Nutzen-Differenz. Durch Umkehrung dieser Funktion (unter Nutzung der Monotonie) können die Nutzenwerte geschätzt werden.
- Der Schätzfehler hängt von der Fenstergröße $m$ , der Temperatur $\tau$ und der Variation der Nutzenvektoren ab.
Algorithmen für InstUtil Rank (Algorithmus 2):
- Der Algorithmus nutzt den Schätzer $\hat{u}(t)$ , um einen Standard-Oracle-Algorithmus (z. B. FTRL) zu speisen.
- Im Bandit-Setting wird eine Explorationsstrategie verwendet (Mischung aus der Oracle-Strategie und einer uniformen Verteilung), um sicherzustellen, dass alle Aktionen mit positiver Wahrscheinlichkeit vorgeschlagen werden.
- Ergebnis: Unter der Annahme sublinearer Variation wird sublineares Regret erreicht.
Algorithmen für AvgUtil Rank (Algorithmus 3):
- Hier wird nicht der momentane Nutzen, sondern der kumulierte Durchschnitt geschätzt.
- Ein entscheidender Vorteil: Im Full-Information-Setting kann die Annahme der sublinearen Variation entfernt werden, wenn $\tau$ eine Konstante ist. Die Stabilität des Schätzers und der gewählten Algorithmen (Assumption 7.1, erfüllt z. B. durch FTRL mit stark konvexer Regularisierung) reicht aus, um sublineares Regret zu garantieren.
- Im Bandit-Setting bleibt die Annahme sublinearer Variation notwendig (mit zusätzlichen Einschränkungen an die Exponenten der Variation).

C. Gleichgewichtsberechnung (Equilibrium Computation)

Wenn alle Spieler in einem Normalform-Spiel (Normal-Form Game) diese Algorithmen verwenden, konvergiert die zeitliche Durchschnittsstrategie gegen ein $\epsilon$ -Coarse Correlated Equilibrium (CCE).
Dies gilt sowohl für InstUtil als auch für AvgUtil Feedback, sofern die Strategien der Spieler selbst eine sublineare Variation aufweisen (was bei Standard-No-Regret-Algorithmen der Fall ist).

3. Wichtige Beiträge

Fundamentale Härteergebnisse: Nachweis, dass Online-Lernen mit Ranking-Feedback im adversären Setting ohne zusätzliche Annahmen (wie sublineare Variation oder nicht-zu-kleines $\tau$ ) unmöglich ist. Dies schließt eine Lücke im Verständnis der Grenzen von Dueling Bandits und verwandten Modellen.
Neue Algorithmen: Entwicklung von Algorithmen, die numerische Nutzen aus Rankings rekonstruieren und sublineares Regret unter realistischen Annahmen (sublineare Variation) garantieren.
Entfernung der Annahme im Full-Information-Setting: Ein bemerkenswertes Ergebnis ist, dass für AvgUtil Rank mit vollem Information-Feedback die Annahme der sublinearen Variation nicht mehr benötigt wird, solange $\tau$ konstant ist.
Spieltheoretische Implikation: Beweis, dass das wiederholte Spielen dieser Algorithmen in Multi-Agenten-Systemen zu einem approximierten CCE führt, was die Anwendbarkeit auf Gleichgewichtsberechnung in Umgebungen mit menschlichem Feedback unterstreicht.
Anwendung auf LLM-Routing: Demonstration der Praktikabilität durch ein Szenario, bei dem ein Router Benutzeranfragen basierend auf Rankings verschiedener Large Language Models (LLMs) leitet.

4. Ergebnisse

Theoretische Garantien: Die Algorithmen erreichen sublineares Regret ( $O(T^\alpha)$ mit $\alpha < 1$ ) in den definierten Szenarien. Die genauen Exponenten hängen von der Feedback-Art (Full-Info vs. Bandit) und der Variationsannahme ab.
Experimentelle Validierung:
- Simulationen auf dem HH-RLHF-Datensatz mit verschiedenen LLMs (Qwen, Phi, GPT-4o, Llama) zeigen, dass der durchschnittliche Regret über die Zeit abnimmt.
- Der Algorithmus nähert sich schnell der Leistung des besten festen Modells an, das im Nachhinein (hindsight) gewählt worden wäre.
- Die Ergebnisse sind robust gegenüber verschiedenen Temperaturen $\tau$ und Anzahlen der vorgeschlagenen Aktionen $K$ .

5. Bedeutung und Ausblick

Brücke zwischen RLHF und Online Learning: Das Paper bietet eine theoretische Fundierung für Reinforcement Learning from Human Feedback (RLHF), wo oft nur Rankings vorliegen, und verbindet dies mit der klassischen Online-Lerntheorie.
Robustheit: Die Ergebnisse gelten für adversäre Umgebungen, was sie robuster macht als viele existierende stochastische Bandit-Ansätze.
Zukünftige Forschung: Die Autoren identifizieren eine Lücke zwischen den unteren Schranken und den positiven Ergebnissen für das Bandit-Setting bei AvgUtil Rank mit konstantem $\tau$ . Die Schließung dieser Lücke (Entweder Härte beweisen oder Algorithmen ohne Variationsannahme finden) ist eine offene Frage. Zudem wird die Anwendung auf reale Datensätze (Ride-Sharing, Dating) als vielversprechend erachtet.

Zusammenfassend stellt das Paper einen wesentlichen Fortschritt im Verständnis von Online-Lernen mit eingeschränktem Feedback dar und liefert praktische Algorithmen für Anwendungen, in denen numerisches Feedback nicht verfügbar ist.