🤖 machine learning

Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Dieses Papier führt den Markov-Entscheidungswettbewerb als ein neues Framework für Reinforcement Learning mit paarweisen Präferenzen ein, wobei bewiesen wird, dass stationäre Markov-Policies optimal sind, und demonstriert wird, dass ein einfacher iterativer Algorithmus im Vergleich zu bisherigen Methoden eine überlegene Lerneffizienz in Problemen mit langem Zeithorizont und hoher Dimensionalität erreicht.

Ursprüngliche Autoren: Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

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 versuchen, einem Roboter das Gehen oder das Spielen eines Videospiels beizubringen. Auf die alte Art und Weise (genannt Reinforcement Learning) agieren Sie wie ein strenger Lehrer mit einem Bewertungsbogen. Sie sagen dem Roboter: „Wenn du diesen Schritt machst, bekommst du +10 Punkte. Wenn du fällst, bekommst du -5 Punkte.“ Das einzige Ziel des Roboters ist es, diese Punkte zu maximieren.

Doch manchmal ist es schwierig, dem Roboter eine spezifische Punktzahl zu geben. Es ist einfacher zu sagen: „Ich bevorzuge diese Art zu gehen gegenüber jener Art.“ Vielleicht wissen Sie nicht genau, warum die eine besser ist, Sie wissen nur, dass Sie sie lieber mögen. Dies nennt man paarweise Präferenz (pairwise preference).

Das Problem ist, dass die alten Methoden, um Roboter mit diesen „Ich bevorzuge dies gegenüber jenem“-Vergleichen zu trainieren, nur gut für kurze Spiele funktionieren. Wenn das Spiel lange dauert (wie etwa ein Roboter, der stundenlang lernt zu laufen), werden die alten Methoden verwirrt, langsam und ineffizient. Sie können auch nicht garantieren, dass eine einfache Entscheidungsregel „im Moment“ genauso gut ist wie eine komplexe Regel, die sich an alles erinnert, was in der Vergangenheit passiert ist.

Dieses Paper stellt einen neuen Weg vor, dieses Problem zu lösen, genannt Markov Decision Contest. So funktioniert es, unter Verwendung einiger einfacher Analogien:

1. Das neue Spiel: Ein „Wettbewerb“ statt eines Bewertungsbogens

Anstatt dem Roboter einen Bewertungsbogen zu geben, stellen Sie sich vor, der Roboter spielt ein Spiel gegen ein Spiegelbild seiner selbst.

Der Aufbau: Der Roboter spielt eine Runde. Dann spielt ein „Klon“ des Roboters eine Runde mit einer anderen Strategie.
Der Richter: Ein Richter betrachtet beide Runden und sagt: „Ich bevorzuge die erste Runde“, oder „Ich bevorzuge die zweite Runde“ oder „Sie sind gleichwertig“.
Das Ziel: Der Roboter möchte eine Strategie finden, die so gut ist, dass der Richter, egal welche Strategie sein Klon verwendet, niemals konsistentent die Strategie des Klons gegenüber der des Roboters bevorzugen wird.

Dies ist das, was die Autoren einen Markov Decision Contest nennen. Es verwandelt das Problem des „Lernens aus Präferenzen“ in ein faires Spiel zwischen zwei Spielern.

2. Die große Überraschrasun: Einfachheit gewinnt

In vielen komplexen Spielen könnte man denken, dass man sich an jede einzelne Bewegung erinnern muss, die man je gemacht hat (eine „historienabhängige“ Strategie), um zu gewinnen. Aber die Autoren haben etwas Überraschendes bewiesen: Man braucht kein Gedächtnis.

Sie haben bewiesen, dass eine „stationäre“ Strategie – also eine, die nur die aktuelle Situation betrachtet und entscheidet, was man jetzt gerade tun soll, ohne sich um die Vergangenheit zu sorgen – tatsächlich genauso gut ist wie jede komplexe Strategie, die die gesamte Historie im Gedächtnis behält.

Analogie: Stellen Sie sich vor, Sie spielen Schach. Sie denken vielleicht, dass Sie die letzten 50 Züge im Kopf haben müssen, um den besten Zug zu machen. Die Autoren haben bewiesen, dass man für diesen speziellen Typ von Spiel nur das Brett jetzt gerade betrachten muss, um den perfekten Zug zu machen. Dies macht das Problem viel einfacher zu lösen.

3. Das Rätsel effizient lösen

Die Autoren zeigten, dass das Lösen dieses „Wettbewerbs“ mathematisch handhabbar ist.

Exakte Lösung: Wenn das Problem nicht zu groß ist, kann man es perfekt mit Standard-Mathematikwerkzeugen lösen, und es wird nicht ewig dauern. Es liegt in derselben „Komplexitätsklasse“ wie Standard-Mathematikprobleme, die wir bereits zu lösen wissen.
Approximative Lösung (Der „HPI“-Algorithmus): Für riesige, komplexe Probleme (wie die hochdimensionale Robotersteuerung) haben sie einen einfachen, iterativen Algorithmus namens Hedged Policy Iteration (HPI) entwickelt.
- Wie es funktioniert: Der Roboter probiert eine Strategie aus, sieht, wie sie sich im Vergleich zu einem Klon schlägt, und passt seine Strategie leicht an, um beim nächsten Mal besser abzuschneiden. Er macht dies immer und immer wieder.
- Das Ergebnis: Der Robot wird immer besser und konvergiert mit einer vorhersehbaren Geschwindigkeit gegen die bestmögliche Strategie.

4. Hat es funktioniert? (Die Experimente)

Die Autoren haben ihre neue Methode gegen die besten existierenden Methoden zum Lernen aus Präferenzen getestet. Sie verwendeten einen Satz schwieriger, langfristiger Robotersteuerungsaufgaben (simulierte Umgebungen, in denen Roboter über tausende Schritte hinweg gehen, greifen oder rennen müssen).

Das Ergebnis: Ihre neue Methode (HPI) lernte viel schneller und effizienter als die alten Methoden.
Der „Nicht-transitive“ Twist: Sie testeten sogar Szenarien, in denen Präferenzen seltsam sind. Zum Beispiel: „Ich bevorzuge A gegenüber B, B gegenüber C, aber C gegenüber A“ (wie bei Stein-Schere-Papier). Alte Methoden haben damit zu kämpfen, aber das neue „Contest“-Modell verarbeitet dies auf natürliche Weise.

Zusammenfassung

Das Paper besagt: „Versuchen Sie nicht, Roboter dazu zu zwingen, eine komplexe Punktzahl zu maximieren, wenn Sie eigentlich nur Präferenzen haben. Lassen Sie sie stattdin einen ‚Wettbewerb‘ gegen sich selbst spielen. Wir haben bewiesen, dass einfache Entscheidungen ‚im Moment‘ ausreichen, um diesen Wettbewerb zu gewinnen, und wir haben einen schnellen, zuverlässigen Algorithmus entwickelt, um ihnen beizubringen, wie sie das tun können, selbst für sehr lange und komplexe Aufgaben.“

Dies ist besonders nützlich für Dinge wie das Training von Large Language Models (wie dem, mit dem Sie gerade sprechen), bei denen das „Spiel“ (ein Gespräch oder eine Aufgabe) sehr lange dauern kann und es oft einfacher ist zu sagen „Ich mag diese Antwort lieber“, als eine spezifische Zahl dafür zuzuweisen.

Technische Zusammenfassung: Reinforcement Learning mit paarweisen Präferenzen in langfristigen Entscheidungsproblemen

Problemdefinition
Traditionelles Reinforcement Learning (RL) formuliert Ziele als Maximierung des Erwartungswerts einer skalaren Belohnungsfunktion innerhalb eines Markov-Entscheidungsprozesses (MDP). In vielen Anwendungen, wie etwa der Feinabstimmung von Large Language Models (LLMs), ist jedoch die Angabe paarweiser Präferenzen (z. B. „Trajektorie A ist besser als Trajektorie B“) oft natürlicher und praktikabler als die Definition einer skalaren Belohnung. Bestehende Methoden für RL mit paarweisen Präferenzen, die entweder eine Belohnungsfunktion inferieren oder direkt auf Präferenzen optimieren, leiden unter zwei kritischen Einschränkungen:

Sie stützen sich auf endliche, feste Zeithorizonte, was für langfristige Entscheidungsprobleme, bei denen Agenten nicht nach einer festen Anzahl von Schritten terminieren, unpraktisch ist.
Es fehlt ihnen an theoretischen Garanten dafür, dass stationäre Markov-Policies optimal gegenüber geschichtshängigen (history-dependent) Policies sind – ein Eckpfeiler der Standard-MDP-Theorie.

Darüber hinaus scheitern Standardansätze oft daran, nicht-transitive Präferenzen (z. B. das Condorcet-Paradoxon) zu erfassen, bei denen die aggregierte Präferenz einer Gruppe oder eine Multi-Feature-Evaluierung keine transitive Ordnung bildet.

Methodik: Markov Decision Contests (MDCs)
Die Autoren schlagen ein neues Problemmodell namens Markov Decision Contest (MDC) vor, um diese Lücken zu schließen. Ein MDC wird durch eine endliche Umgebung $(S, A, P, \mu)$ und eine Markov-Präferenzmarge $M: (S \times A) \times (S \times A) \to \mathbb{R}$ definiert. Das Ziel besteht darin, eine Policy $\pi$ zu finden, die die durchschnittliche Präferenzmarge gegen jede andere Policy $\pi'$ maximiert, formuliert als Nullsummenspiel:
$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$
wobei $x_\pi$ die Grenzwert-Häufigkeitsverteilung der Zustands-Aktions-Paare (occupancy measure) darstellt.

Um die theoretische Handhabbarkeit in unendlichen Horizonten zu gewährleisten, setzen die Autoren voraus, dass die Übergangswahrscheinlichkeitsfunktion unichain und aperiodisch ist. Unter diesen Bedingungen etablieren sie, dass die Menge der Häufigkeitsverteilungen für geschichtshängige Policies äquivalent zum konvexen Hull der Häufigkeitsverteilungen für stationäre deterministische Policies ist.

Wesentliche Beiträge

Optimalität stationärer Policies: Die Arbeit beweist, dass innerhalb endlicher unichain MDCs eine stationäre randomisierte Policy unter allen geschichthängigen Policies optimal ist. Dies rechtfertigt die Beschränkung des Suchraums auf Markov-Policies und schließt eine Lücke zwischen Theorie und Praxis für präferenzbasiertes RL.
Komplexität der Berechnung: Die Autoren zeigen, dass das exakte Lösen eines MDC in P (Polynomialzeit) liegt. Konkret konstruieren sie ein lineares Programm mit $|S||A| + |S| + 1$ Variablen und $2|S||A| + |S| + 1$ Nebenbedingungen. Diese Komplexität ist vergleichbar mit Standard-Average-Reward-MDPs, obwohl MDCs eine strengere Verallgemeinerung darstellen, die nicht-transitive Präferenzen unterstützt.
Hedged Policy Iteration (HPI): Ein approximativer iterativer Algorithmus, die Hedged Policy Iteration (HPI), wird eingeführt. Er nutzt den Hedge-Algorithmus, um Entscheidungsregeln basierend auf „marginalen Werten“ (kumulativen Präferenzmargen) zu aktualisieren.
- Konvergenz: HPI konvergiert mit einer sublinearen Rate von $O(1/\sqrt{K})$ gegen eine optimale Policy, wobei $K$ die Anzahl der Iterationen ist.
- Skalierbarkeit: Die Autoren leiten eine Policy-Gradient-Form von HPI und eine Deep-Learning-Implementierung (Algorithmus 3) ab, die Buffer und Wertfunktionsapproximationen nutzt, wodurch sie für hochdimensionale Umgebungen geeignet ist.

Experimentelle Ergebnisse
Die Autoren evaluierten HPI und eine abgeschnittene Variante (HPI-Clip) gegen Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) in 13 hochdimensionalen Aufgaben mit langen Zeithorizonten (2048 Schritte) unter Verwendung der Mujoco-v5-Suite.

Setup: Die Aufgaben umfassten Standardprobleme der kontinuierlichen Steuerung (bei denen die Präferenzen aus Differenzen der Belohnungen abgeleitet wurden) sowie „Mujoco-NT“-Aufgaben, die explizit nicht-transitive Präferenzmargen aufweisen (z. B. Best-Two-out-of-Three-Regeln).
Leistung: In 12 von 13 Aufgaben zeigten HPI und HPI-Clip eine signifikant höhere Lerneffizienz (gemessen am Area Under the Curve der episodischen Rückkehr oder der invertierten Optimalitätslücke) im Vergleich zu SPPO.
Ablation: Die Ergebnisse blieben auch bestehen, wenn die Präferenzmodelle aus Offline-Daten gelernt wurden.

Bedeutung und Ansprüche
Das Paper behauptet, dass Reinforcement Learning mit paarweisen Präferenzen in langfristigen Entscheidungsproblemen handhabbarer ist als bisher angenommen. Durch die Einführung des MDC-Modells bieten die Autoren einen Rahmen, in dem:

Stationäre Policies theoretisch ausreichend sind, was die Notwendigkeit komplexer geschichtshängiger Strategien aufhebt.
Das Problem rechentechnisch effizient bleibt (in P), selbst bei nicht-transitiven Präferenzen.
Praktische Algorithmen (HPI) auf hochdimensionale, langfristige Probleme skalieren und bestehende State-of-the-Art-Methoden übertreffen.

Die Autoren merken an, dass diese Ergebnisse zwar vielversprechend für Anwendungen wie LLMs in langfristigen Aufgaben sind, weitere Untersuchungen jedoch erforderlich sind, um zu bestimmen, wann das Lernen von Präferenzmargen das Lernen von Belohnungen überwiegt und wie effektiv diese Methoden Sprachmodelle in der Praxis ausrichten können. Die Arbeit zielt darauf ab, Theorie und Praxis von paarweisem Präferenz-RL näher zusammenzuführen.