💬 NLP

On Advantage Estimates for Max@K Policy Gradients

Dieses Paper stellt MaxPO vor, eine neue Policy-Gradient-Methode zur Optimierung von Max@K-Zielen im Reinforcement Learning mit verifizierbaren Belohnungen, welche eine neuartige Leave-Two-Out-Baseline nutzt, um zentrierte Advantages zu gewährleisten, die Gradientenvarianz zu reduzieren und bestehende Schätzer für ein effektiveres LLM-Post-Training zu vereinheitlichen.

Ursprüngliche Autoren: Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim, Kohsei Matsutani, Gouki Minegishi, Yusuke Iwasawa, Takeshi Kojima, Yutaka Matsuo

Veröffentlicht 2026-06-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim, Kohsei Matsutani, Gouki Minegishi, Yusuke Iwasawa, Takeshi Kojima, Yutaka Matsuo

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 ein Lehrer, der versucht, einem Schüler beizubringen, eine sehr schwierige mathematische Aufgabe zu lösen. Der Schüler ist eine KI, und die Aufgabe ist eine „Reasoning-Aufgabe“ (Schlussfolgerungsaufgabe).

Auf dem alten Weg, diese KIs zu trainieren (Reinforcement Learning), würde der Lehrer den Schüler bitten, die Aufgabe einmal zu lösen. Wenn die Antwort falsch war, erhielt der Schüler kein Feedback (null Belohnung). Wenn sie richtig war, bekam er einen goldenen Stern. Das Problem? Der Schüler musste den richtigen Pfad in einem riesigen Labyrinth von Möglichkeiten erraten, und einen goldenen Stern zu bekommen, war so selten, dass der Schüler oft stecken blieb, ohne zu wissen, welche seiner Versuche „fast richtig“ und welche „völlig falsch“ waren.

Um dies zu beheben, begannen Forscher mit einer neuen Strategie: Der „Versuche es viele Male“-Ansatz.

Anstatt den Schüler zu bitten, die Aufgabe einmal zu lösen, bittet der Lehrer ihn, K verschiedene Lösungen gleichzeitig zu generieren. Das Ziel ist nicht nur, eine richtige Antwort zu erhalten, sondern sicherzustellen, dass mindestens einer dieser K Versuche korrekt ist. Dies wird als Optimierung auf Max@K (oder Pass@K) bezeichnet.

Das Problem mit den alten „Versuche viele Male“-Methoden

Das Paper argumentiert, dass dieser „Versuche viele Male“-Ansatz zwar großartig ist, aber die Mathematik, die verwendet wurde, um die KI zu lehren, wie sie sich verbessert, leicht fehlerhaft war.

Stellen Sie sich vor, Sie haben eine Gruppe von 8 Schülern (ein „Batch“), die versuchen, ein Rätsel zu lösen. Sie möchten jedem Schüler sagen, wie gut er abgeschnitten hat.

Die alte Methode (nur EI): Sie betrachtete die Antwort eines Schülers und verglich sie mit der besten Antwort der anderen 7 Schüler. Wenn ein Schüler besser abschnitt als die anderen, erhielt er ein riesiges „Gut gemacht!“-Signal. Wenn er schlechter abschnitt, erhielt er ein „0“-Signal.
Der Fehler: Da das „Gut gemacht!“-Signal immer positiv (oder null) und niemals negativ war, sagte der Lehrer im Wesentlichen: „Du bist immer besser als der Durchschnitt!“ Das ist irreführend. Es ist wie ein Trainer, der nur jemals „Super!“ sagt und nie darauf hinweist, dass ein Spieler eigentlich unter seinem wahren Potenzial bleibt. Dies erzeugt viel „Rauschen“ (Varianz) im Training, was das Lernen der KI instabil und langsam macht.

Die Lösung: Die „Leave-Two-Out“-Baseline

Die Autoren dieses Papers schlagen einen klügeren Weg vor, die Schüler zu bewerten, den sie MaxPO (Max@K Policy Optimization) nennen.

Sie führen eine neue Regel zur Bewertung ein, die sie die Leave-Two-Out (L2O)-Baseline nennen. So funktioniert sie anhand einer einfachen Analogie:

Stellen Sie sich vor, Sie bewerten eine Talentshow mit 8 Teilnehmern.

Der alte Weg: Um Teilnehmer A zu bewerten, vergleichen Sie ihn mit dem Besten der anderen 7. Wenn A der Beste ist, erhält er eine hohe Punktzahl. Wenn nicht, erhält er eine Null. Dies ist voreingenommen, da das „Bestleistung der anderen 7“ ein bewegliches Ziel ist, das sich ändert, je nachdem, wer im Raum ist.
Der neue Weg (L2O): Um Teilnehmer A zu bewerten, entfernen Sie vorübergehend sowohl Teilnehmer A als auch Teilnehmer B aus dem Raum. Dann schauen Sie sich die verbleibenden 6 Personen an, um zu sehen, was eine „faire“ Durchschnittsleistung darstellt.
- Sie berechnen, wie gut Teilnehmer A gegen diese „faire“ Gruppe abgeschnitten hätte.
- Entscheidend ist, dass Sie durch das Entfernen von zwei Personen sicherstellen, dass die „faire“ Gruppe nicht versehentlich die Person enthält, die Sie gerade beurteilen wollen (Teilnehmer A), oder einen spezifischen „Rivalen“ (Teilnehmer B), der den Vergleich verzerren könnte.

Warum ist das besser?
Diese Methode stellt sicher, dass die „Durchschnitts“-Punktzahl der gesamten Gruppe exakt null ist. Einige Schüler erhalten eine positive Punktzahl (sie waren besser als der faire Durchschnitt), und einige erhalten eine negative Punktzahl (sie waren schlechter). Diese positiven und negativen Punktzahlen heben sich perfekt auf.

Das Ergebnis: Die KI erhält ein viel klareres, weniger „verrauschtes“ Signal. Sie weiß genau, wo sie im Verhältnis zu einer fairen Baseline steht, anstatt nur zu hören: „Du bist großartig“ oder „Du bist nichts“.

Was das Paper herausgefunden hat

Die Forscher haben diese neue „Leave-Two-Out“-Methode auf zwei Arten getestet:

In einfachen Spielen (Bandits und Mazes): Sie zeigten, dass ihre neue Methode das „Rauschen“ im Lernsignal in einem riesigen Maße reduzierte (bis zu 77 % weniger Rauschen in einigen Fällen). Das bedeutet, die KI lernt stetiger und wird nicht durch zufällige Schwankungen verwirrt.
In echten KI-Modellen (LLMs): Sie testeten dies an großen Sprachmodellen (wie Llama und Qwen), die versuchten, mathematische Probleme zu lösen.
- Das Ergebnis: Die KI, die mit ihrer neuen Methode (MaxPO) trainiert wurde, wurde signifikant besser darin, Probleme zu lösen, wenn sie viele Versuche hatte (z. B. Pass@256).
- Beim Qwen-Modell verbesserte sie die Erfolgsquote um 5,2 %.
- Beim Llama-Modell verbesserte sie die Erfolgsquote um 2,4 %.

Das große Ganze

Denken Sie an die alte Methode als einen Trainer, der überoptimistisch ist und jedem einen „Gut gemacht!“-Aufkleber gibt, selbst wenn dieser Schwierigkeiten hat. Die neue Methode (MaxPO) ist ein Trainer, der ein strenges, faires und ausgewogenes Bewertungssystem verwendet. Durch das Eliminieren des „Rauschens“ und das Sicherstellen, dass die Punktzahlen um den Nullpunkt zentriert sind, kann die KI viel schneller und effektiver lernen, insbesondere wenn das Ziel darin besteht, mindestens eine korrekte Antwort aus vielen Versuchen zu finden.

Das Paper kommt zu dem Schluss, dass dieser „Leave-Two-Out“-Ansatz der mathematisch korrekte Weg ist, um KIs für diese „Versuche viele Male“-Aufgaben zu trainieren, und bietet eine einheitliche und stabile Grundlage für zukünftige Verbesserungen.

Technisches Resümee: Über Advantage-Schätzungen für Max@K Policy Gradients

Problemstellung

Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) ist ein dominantes Paradigma für das Post-Training von Large Language Models (LLMs) bei Denkaufgaben. Diese Settings verlassen sich jedoch typischerweise auf spärliche, ergebnisbasierte Belohnungen (z. B. ein binäres korrekt/inkorrekt Signal), was die Exploration in großen kombinatorischen Räumen erschwert. Während Methoden wie Entropie-Regularisierung und count-basierte Boni existieren, führen diese zusätzliche Zielsetzungen ein, die eine sorgfältige Abstimmung erfordern.

Ein komplementärer Ansatz ist die direkte Optimierung von Inferenz-Zeit-Zielsetzungen wie pass@K (die Wahrscheinlichkeit, dass mindestens eine von $K$ Stichproben korrekt ist) und deren kontinuierlicher Verallgemeinerung, max@K (der erwartete maximale Reward unter $K$ Stichproben). Mehrere aktuelle Arbeiten haben unvoreingenommene Policy-Gradient (PG) Schätzer für diese Zielsetzungen vorgeschlagen. Die Beziehungen zwischen diesen Schätzern bleiben jedoch unklar. Speziell nutzen bestehende Schätzer oft unterschiedliche Signale, Baselines und Normalisierungen. Ein kritisches Problem, das in dieser Arbeit identifiziert wurde, ist, dass führende Schätzer (z. B. basierend auf Expected Improvement) zwar unvoreingenommene PG-Schätzer sind, aber nicht-zentrierte Advantages liefern. Ein nicht-zentrierter Advantage (einer mit einem Mittelwert ungleich Null) entspricht einer unterschätzten Baseline, was die Optimierung in Richtung suboptimaler Aktionen lenken und die Gradienten-Varianz erhöhen kann.

Methodik

Die Arbeit schlägt MaxPO (Max@K Policy Optimization) vor, eine Methode, die eine Leave-Two-Out (L2O) Baseline einführt, um die Advantage-Schätzung für max@K-Zielsetzungen zu korrigieren.

1. Analyse bestehender Schätzer

Die Autoren untersuchen den Expected Improvement (EI) Schätzer, der in vorangegangenen Arbeiten (z. B. Walder und Karkhanis [54]) verwendet wird. Sie zeigen, dass der EI-basierte Schätzer zwar ein unvoreingenommener PG-Schätzer ist, das resultierende Advantage-Signal $s(a)$ jedoch strikt nicht-negativ ist (aufgrund der ReLU-Operation in der EI-Definition). Folglich ist $E[s(a)] > 0$ , was bedeutet, dass der Advantage nicht zentriert ist. Dieser Mangel an Zentrierung lässt Raum für Varianzreduktion.

2. Die Leave-Two-Out (L2O) Baseline

Um einen exakt zentrierten Advantage zu erreichen und gleichzeitig die PG-Unvoreingenommenheit zu bewahren, führen die Autoren die L2O-Baseline ein.

Die Herausforderung: Eine Standard Leave-One-Out (L1O) Baseline versagt im max@K-Setting, da der Reward einer Stichprobe $i$ den Advantage-Berechnung anderer Stichproben $j$ implizit beeinflussen kann (da $i$ als potenzieller Komparator in der max-Operation fungiert). Diese Abhängigkeit verletzt die Unabhängigkeitsbedingung, die für eine unvoreingenommene PG-Schätzung erforderlich ist.
Die Lösung: Die L2O-Baseline $b_{-i}^{L2O}$ wird berechnet, indem die Expected Improvement Scores aller anderen Stichproben $j$ gemittelt werden, wobei jeder Score über einer Teilmenge von Komparatoren berechnet wird, die sowohl die Ziel-Stichprobe $i$ als auch die Stichprobe $j$ selbst ausschließt.
Eigenschaften:
- Unabhängigkeit: Durch den Ausschluss von $i$ aus dem Komparator-Set für alle $j$ ist die Baseline $b_{-i}^{L2O}$ unabhängig vom Reward $r_i$ , was sicherstellt, dass der PG-Schätzer unvoreingenommen bleibt.
- Zentrierung: Die Autoren beweisen, dass der realisierte Batch-Durchschnitt des Advantages exakt Null ist: $\frac{1}{B}\sum_{i=1}^B (s_i - b_{-i}^{L2O}) = 0$ .
- Effizienz: Während eine naive Berechnung $O(B^3)$ beanspruchen würde, leiten die Autoren eine vektorisierte Implementierung unter Verwendung von ReLU-Formulierungen ab, die die L2O-Baseline in $O(B^2)$ Zeit berechnet, was eine praktikable Anwendung für GPU-beschleunigtes LLM-Training ermöglicht.

3. Kanonischer Finite-Batch Advantage

Die Arbeit leitet einen kanonischen Finite-Batch Advantage für max@K ab, definiert als $u_i - v_i$ :

$u_i$ : Der bedingte erwartete max@K Wert einer Gruppe, die Antwort $i$ enthält.
$v_i$ : Der Leave-One-Out erwartete max@K Wert, berechnet aus Gruppen, die $i$ ausschließen.
Die Autoren zeigen, dass der MaxPO-Schätzer (EI + L2O) exakt dieses kanonische Signal ( $s_i - b_{-i}^{L2O} = u_i - v_i$ ) wiederherstellt. Dies bietet eine vereinheitlichte Sicht auf bestehende Schätzer und klassifiziert sie in "nicht-zentriert" (z. B. EI-only/PKPO) und "(normalisierte) kanonisch" (z. B. MaxPO und bestimmte analytische pass@K Varianten).

4. Integration in das LLM-Training

MaxPO wird in gruppenbasierte RL-Algorithmen (wie GRPO) integriert. Für jeden Prompt wird eine Gruppe von $G$ Outputs generiert. Die L2O-Baseline wird innerhalb jeder Gruppe berechnet, um Sequence-Level Advantages zu generieren, die dann an Token-Level Losses weitergegeben werden.

Zentrale Beiträge

Identifikation von Nicht-Zentrierten Advantages: Die Arbeit identifiziert, dass führende max@K PG-Schätzer (speziell EI-basierte) zwar unvoreingenommene Gradientenschätzer sind, aber keine zentrierten Advantages erzeugen, was zu suboptimalen Varianzeigenschaften führt.
Leave-Two-Out (L2O) Baseline: Ein neuartiges Baseline-Design, das die PG-Unvoreingenommenheit im nicht-linearen max@K-Setting bewahrt und gleichzeitig sicherstellt, dass der realisierte Batch-Average genau den Mittelwert Null hat.
Kanonische Vereinheitlichung: Die Ableitung des kanonischen Finite-Batch Advantage ( $u_i - v_i$ ) und der Beweis, dass MaxPO dieses Signal wiederherstellt, bietet einen vereinheitlichten Rahmen zum Vergleich und zur Kategorisierung bestehender pass@K/max@K Schätzer.
Effiziente Implementierung: Ein $O(B^2)$ vektorisierter Algorithmus zur Berechnung der L2O-Baseline, der die praktische Anwendung im LLM Post-Training ermöglicht.

Experimentelle Ergebnisse

Die Autoren validieren die Methode durch kontrollierte Bandit/Maze-Experimente und LLM-Reasoning-Aufgaben.

Varianzreduktion: In Bandit-Umgebungen reduziert die L2O-Baseline die Gradienten-Varianz im Vergleich zu rohen EI-Schätzern signifikant, wobei der Effekt mit zunehmender Größe des Aktionsraums wächst. Im LLM-Training (Llama-3.2-3B-Instruct) reduzierte die Methode die Proxy der Gradienten-Varianz um 77,4 % im Vergleich zu PKPO (der EI-only Baseline).
Leistungssteigerungen: Bei fünf mathematischen Reasoning-Benchmarks (AIME24, AIME25, AMC23, MATH500, Minerva) übertraf MaxPO starke Baselines wie PKPO, GRPO und Entropy-Adv.
- Auf Qwen2.5-Math-7B verbesserte MaxPO den Task-Average pass@256 um 5,2 % gegenüber PKPO.
- Auf Llama-3.2-3B-Instruct verbesserte es pass@256 um 2,4 % gegenüber PKPO.
Skalierung der Inferenz-Rechenleistung: Die Leistungssteigerungen von MaxPO waren bei höheren Inferenz-Rechenleistung-Niveaus (größeres $k$ in pass@k) am ausgeprägtesten, was darauf hindeutet, dass die Methode der Policy hilft, zusätzliche Test-Zeit-Samples besser zu nutzen.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass MaxPO eine fundierte Basis für das Design und den Vergleich von Policy-Gradient-Schätzern für Inferenz-Zeit-Zielsetzungen wie max@K bietet. Durch die Identifizierung der kanonischen Advantage-Form und die Korrektur der Bias in bestehenden Schätzern bietet die Arbeit eine Methode zur Verbesserung der Effizienz und Stabilität von Post-Training Reasoning Modellen.

Die Autoren merken bescheiden an, dass sich ihre Analyse auf die Finite-Batch, On-Policy Schätzung unter i.i.d. Sampling konzentriert. Sie räumen ein, dass Off-Policy Training, adaptives Sampling und Settings mit korrelierten Generationen Richtungen für zukünftige Arbeiten sind. Darüber hinaus betonen sie, dass die Verbesserung der Optimierung von wiederholten Sampling-Reasoning-Objectives breitere Auswirkungen hat, was potenziell Modelle stärken könnte, die für täuschende Unterstützung oder automatisierte Problemlösung missbraucht werden könnten.