🤖 machine learning

GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning

Dieser Beitrag stellt Variance-Reduced Policy Optimization (VRPO) vor, einen neuen Algorithmus, der einen $Q$ -Boosting-Variance-Reduced-Advantage-Schätzer einsetzt, um die hohe Varianz zu überwinden, die der herkömmlichen Generalized Advantage Estimation für Selbstspiel bei unvollständiger Information inhärent ist, und damit überlegene Leistung in kompetitiven Multi-Agenten-Spielen wie Dou Dizhu und Heads-Up No-Limit Texas Hold'em erzielt.

Ursprüngliche Autoren: Zhiyuan Fan, Gabriele Farina

Veröffentlicht 2026-05-20

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Zhiyuan Fan, Gabriele Farina

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 unterrichten eine Gruppe von Robotern, ein komplexes Kartenspiel wie Poker oder Dou Dizhu (ein beliebtes chinesisches Kartenspiel) zu spielen. Der Haken? Sie können die Karten der anderen nicht sehen, und sie spielen gegen Gegner, die versuchen, sie zu täuschen. Um zu gewinnen, müssen die Roboter eine Strategie erlernen, die so ausgeglichen und unvorhersehbar ist, dass kein Gegner sie ausnutzen kann. Dies nennt man das Finden eines „Gleichgewichts".

Lange Zeit war der beste Weg, diese Roboter zu unterrichten, Self-Play: Man lässt die Roboter Millionen Mal gegen Kopien ihrer selbst spielen. Der beliebteste Lehrer hierfür ist ein Algorithmus namens PPO (Proximal Policy Optimization).

Die Autoren dieses Papers haben jedoch einen versteckten „Fehler" entdeckt, wie PPO Roboter in diesen Spielen mit geheimen Karten unterrichtet. Hier ist die Aufschlüsselung des Problems und ihrer Lösung, unter Verwendung einfacher Analogien.

Das Problem: Das „verrauschte Flüstern" in einem vollen Raum

Bei Standard-PPO lernt der Roboter, indem er einen Pfad betrachtet, den er in der Vergangenheit zurückgelegt hat, und fragt: „War das ein guter Zug?" Um dies zu beantworten, verwendet er ein Werkzeug namens GAE (Generalized Advantage Estimation).

Stellen Sie sich GAE wie einen Trainer vor, der einem Spieler basierend auf einer Wiederholung des Spiels einen Rat zuflüstert.

In einem einfachen Spiel (wie Schach): Die Zukunft ist vorhersehbar. Wenn der Trainer sagt: „Sie haben hier den Bauern gezogen, und das führte zu einem Sieg", weiß der Spieler genau, warum.
In einem Spiel mit geheimen Karten (wie Poker): Die Zukunft ist voller Zufälligkeit. Das Flüstern des Trainers wird undeutlich, weil der Roboter raten muss, was die anderen Roboter als Nächstes tun könnten. Da die Roboter zufällig spielen (um ihre Gegner im Ungewissen zu lassen), wird der Rat des Trainers zu einem „verrauschten Flüstern".

Die Analogie: Stellen Sie sich vor, Sie versuchen, eine Tanzroutine in einem Raum zu lernen, in dem sich alle in zufällige Richtungen drehen.

Der alte Weg (GAE): Der Trainer versucht Ihnen zu sagen: „Wenn Sie nach links treten, sind Sie sicher." Aber weil alle anderen wild herumwirbeln, wird die Stimme des Trainers vom Chaos übertönt. Der Roboter hört: „Nach links treten... vielleicht? Oder vielleicht nach rechts? Es ist schwer zu sagen!" Dieses „Rauschen" macht das Lernen des Roboters wackelig und langsam.
Die Erkenntnis des Papers: Selbst wenn der Trainer perfekt ist (vollständige Kenntnis des Spiels hat), stammt das Rauschen daraus, dass die anderen Tänzer zufällig herumwirbeln. Der Roboter kann nicht zwischen einem schlechten Zug und einfach nur Pech unterscheiden, das durch die Zufälligkeit der anderen Spieler verursacht wird.

Die Lösung: „Q-Boosting" (Die Glaskugel)

Die Autoren haben ein neues Werkzeug namens Q-Boosting erfunden, um dieses Rauschen zu beheben.

Anstatt dass der Trainer basierend auf einem einzigen zufälligen Replay errät, was als Nächstes passiert, bittet Q-Boosting den Trainer, alle möglichen Zukünfte gleichzeitig zu betrachten und zu mitteln.

Die Analogie: Anstatt dass der Trainer sagt: „Ich habe gesehen, wie Sie nach links getreten sind, und dieses eine Mal ist jemand in Sie hineingewirbelt", sagt der neue Trainer: „Ich habe berechnet, dass Sie bei 50 % der Fälle sicher sind, wenn Sie nach links treten, bei 30 % der Fälle blockiert werden und bei 20 % der Fälle stolpern. Im Durchschnitt ist es eine gute Idee, nach links zu treten."

Indem die Mathematik durchgeführt wird, um die Zufälligkeit bevor der Rat gegeben wird, herauszurechnen, entfernt der Trainer das „Rauschen". Der Roboter erhält ein klares, ruhiges Signal: „Dieser Zug ist im Durchschnitt gut", anstatt „Dieser Zug war dieses spezifische Mal gut, aber vielleicht dieses andere Mal schlecht".

Sie nennen diese neue Lehrmethode VRPO (Variance-Reduced Policy Optimization).

Die Ergebnisse: Intelligente Roboter, schnellere Siege

Das Paper testete diese neue Methode (VRPO) gegen den alten Standard (PPO) in mehreren Spielen:

Kleine Spiele (Die Testküche): Sie spielten Spiele wie „Liar's Dice" und „Phantom Tic-Tac-Toe". In diesen Spielen konnten sie mathematisch beweisen, wie gut der Roboter war.
- Ergebnis: VRPO lernte eine viel stärkere Strategie als PPO. Es war schwieriger, es zu täuschen, was bedeutet, dass es näher an der perfekten „Gleichgewichts"-Strategie war.
Mittlere Spiele (Die Arena): Sie spielten Dou Dizhu (ein komplexes Kartenspiel für drei Spieler).
- Ergebnis: VRPO besiegte die bisher beste KI (namens PerfectDou) in direkten Duellen, obwohl sie die gleiche Rechenleistung verwendeten. Es lernte, öfter zu gewinnen.
Große Spiele (Die Meisterschaft): Sie versuchten Heads-Up No-Limit Texas Hold'em (eine Variante des Pokers mit hohen Einsätzen).
- Ergebnis: VRPO schnitt gegen einen starken Poker-Bot namens Slumbot sehr gut ab. Es gelang ihm, über eine lange Sitzung hinweg Geld zu gewinnen, ohne irgendwelche „Tricks" wie das Voraussehen zukünftiger Karten oder das Durchführen komplexer Mathematik während des Spiels zu benötigen. Es lernte einfach durch Training eine bessere Strategie.

Zusammenfassung

Das Paper argumentiert, dass beim Unterrichten von Robotern für das Spielen von Kartenspielen mit geheimen Karten die alte Lernmethode (GAE) durch die Zufälligkeit der anderen Spieler verwirrt wird. Die neue Methode (VRPO mit Q-Boosting) wirkt wie ein superschlauer Trainer, der alle Möglichkeiten mittelt, bevor er Ratschläge erteilt. Dies beseitigt die Verwirrung und ermöglicht es den Robotern, schneller zu lernen, stabiler zu spielen und viel schwerer zu schlagen zu sein.

Technische Zusammenfassung: GAE bleibt bei Selbstspiel mit unvollständiger Information hinter den Erwartungen zurück

Problemstellung

Wettbewerbsorientiertes Multi-Agenten-Reinforcement-Learning (MARL) in Spielen mit unvollständiger Information erfordert, dass Agenten unter partieller Beobachtbarkeit gegen adversarische Gegner agieren, was stochastische Strategien notwendig macht. Während Selbstspiel-Reinforcement-Learning mit Proximal Policy Optimization (PPO) empirische Erfolge erzielt hat, steht es vor einer kritischen Engstelle beim Erlernen von Gleichgewichten: der Varianz der Vorteilsschätzung.

Standard-PPO-Implementierungen verlassen sich auf die Generalized Advantage Estimation (GAE), um mehrstufige Temporal-Difference (TD)-Residuen zu aggregieren. In Einzelagenten-Szenarien balanciert GAE effektiv Bias und Varianz aus. In unvollständigen Informations-Selbstspielen sind Gleichgewichtsstrategien jedoch inhärent stochastisch. GAE übernimmt Zufälligkeit aus der Stichprobenziehung zukünftiger Aktionen innerhalb ihrer mehrstufigen Spur. Da Gleichgewichtsstrategien verschiedenen Aktionen unterschiedliche Werte zuweisen, führt die Stichprobenziehung zukünftiger Aktionen zu intrinsischem Rauschen. Diese Varianz wird in Selbstspielszenarien verstärkt und bleibt bestehen, selbst wenn der Zustands-Wert-Kritiker ( $V$ -Kritiker) exakt ist. Folglich liefert die Standard-GAE hochvarianzbehaftete Gradientenschätzungen genau in den Regimen, in denen stabiles Lernen am kritischsten ist, was die Konvergenz zu hochwertigen Gleichgewichten behindert.

Methodik

Q-Boosting-Schätzer

Um die durch die Stichprobenziehung von Aktionen eingeführte Varianz zu adressieren, schlagen die Autoren Q-Boosting vor, einen varianzreduzierten Vorteilsschätzer. Die Kerninnovation besteht darin, die in GAE verwendete gestichproberte mehrstufige TD-Spur durch eine mehrstufige Expected SARSA( $\lambda$ )-Spur zu ersetzen, die auf einem zentralisierten Aktionswert-Kritiker ( $Q$ -Kritiker) berechnet wird.

Mechanismus: Anstatt durch gestichproberte nächste Aktionen zu bootstrappen (was Rauschen einführt), berechnet Q-Boosting Strategieerwartungen an jedem Backup-Schritt. Es mittelt das Rauschen stochastischer zukünftiger Aktionen heraus, indem es den Erwartungswert über die durch die aktuelle Strategie definierte Aktionsverteilung bildet.
Formulierung: Gegeben ein zentralisierter $Q$ -Kritiker $Q_i(s, a)$ und eine gemeinsame Strategie $\pi$ , wird der Zustandswert berechnet als $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$ . Der Q-Boosting-Vorteilsschätzer $\hat{A}^{boost}_{i,\tau}$ ist definiert als:
$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$
wobei das Expected SARSA TD-Residuum $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$ ist.
Theoretische Garantie: Die Autoren beweisen, dass für on-policy-Trajektorien und $\lambda=1$ der Q-Boosting-Schätzer eine erwartungstreue Schätzung des Score-Funktions-Strategiegradient-Terms liefert. Ferner ist, falls der $Q$ -Kritiker hinreichend genau ist, der mittlere quadratische Fehler des Q-Boosting-Schätzers strikt niedriger als der von GAE mit einem exakten $V$ -Kritiker, sofern zukünftige Aktionen eine von Null verschiedene Varianz in ihren Aktionswerten aufweisen.

Varianzreduzierte Strategieoptimierung (VRPO)

Die Autoren integrieren Q-Boosting in einen PPO-artigen Algorithmus namens Variance-Reduced Policy Optimization (VRPO).

Architektur: VRPO folgt dem Paradigma des zentralisierten Trainings mit dezentraler Ausführung (CTDE). Es nutzt dezentralisierte Akteure für die Ausführung und einen zentralisierten $Q$ -Kritiker für das Training.
Zielsetzung: Der Algorithmus behält die abgeschnittene surrogate-Zielfunktion und Trust-Region-Updates von PPO bei, modifiziert jedoch die Verfahren zur Vorteilsschätzung und zum Kritikerlernen.
Trainingsablauf:
1. Akteur-Update: Akteure werden unter Verwendung der Q-Boosting-Vorteilsschätzungen aktualisiert. Um On-Policy-Eigenschaften zu wahren, werden die Strategieerwartungsterme in der Vorteilsberechnung unter Verwendung aktueller Akteur-Wahrscheinlichkeiten neu berechnet, während die Kritikerwerte fixiert bleiben.
2. Kritiker-Update: Die zentralisierten $Q$ -Kritiker werden durch Minimierung des quadrierten Regressionsverlusts gegen das Q-Boosting-Ziel (eine mehrstufige Expected SARSA-Spur) trainiert.
3. Regularisierung: Eine explizite KL-Divergenz-Strafe relativ zu einer Gleichverteilung wird zur Strategiezielfunktion hinzugefügt, um Exploration zu fördern und die Konvergenz der letzten Iteration zu unterstützen.
Umgang mit großen Aktionsräumen: Für Spiele mit massiven Aktionsmengen (z. B. Dou Dizhu) zerlegen die Autoren komplexe Entscheidungen in mehrere Zeitschritte. Dies reduziert die Anzahl der verfügbaren Aktionen pro Schritt auf eine handhabbare Größe und ermöglicht die für die Strategieerwartung in der Q-Boosting-Spur erforderliche Enumeration.

Hauptbeiträge

Identifikation der Varianzquelle: Das Papier identifiziert, dass die Stichprobenziehung zukünftiger Aktionen in GAE zusätzliche Varianz im stochastischen Selbstspiel einführt, die selbst bei exakten Wertfunktionen bestehen bleibt.
Q-Boosting-Schätzer: Die Autoren leiten Q-Boosting ab, einen mit PPO kompatiblen Schätzer, der eine Expected SARSA( $\lambda$ )-Spur auf einen zentralisierten $Q$ -Kritiker anwendet, um das Rauschen der zukünftigen Aktionsstichproben herauszumitteln.
VRPO-Algorithmus: Der Vorschlag von VRPO, einem PPO-artigen Algorithmus, der Q-Boosting nutzt, um verbesserte Stabilität und Leistung zu erreichen.
Empirische Validierung: Der Nachweis, dass die Reduzierung der Varianz der Vorteilsschätzung erhebliche Gewinne in der Qualität der Gleichgewichte über Spiele unterschiedlicher Skalierung hinweg erzielt.

Experimentelle Ergebnisse

Mittelgroße Spiele (Exakte Ausnutzbarkeit)

Die Autoren haben VRPO an mittelgroßen Spielen getestet, bei denen die exakte Ausnutzbarkeit berechnet werden kann: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) und Liar's Dice mit 2 Würfeln und 5 Seiten (LiDi 2D5F).

Leistung: VRPO erreichte konsistent eine um mehr als 15 % geringere Ausnutzbarkeit im Vergleich zu verschiedenen PPO-basierten Baselines (IPPO, MAPPO, MMD, PPG) unter einem gemeinsamen Trainingsplan.
Ablation: Experimente bestätigten, dass die Leistungsgewinne über verschiedene Spurparameter ( $\lambda$ ), Regularisierungskoeffizienten ( $\alpha$ ) und PPO-Abschneidekoeffizienten ( $\epsilon$ ) hinweg robust sind.

Großskalige Spiele

Die Autoren bewerteten VRPO in großskaligen Domänen, in denen die exakte Ausnutzbarkeit unlösbar ist.

Dou Dizhu: VRPO wurde gegen den vorherigen State-of-the-Art-Agenten PerfectDou trainiert. Bei einem angepassten Trainingsbudget ( $\approx 2,65 \times 10^9$ Zeitschritte) übertraf VRPO PerfectDou bereits nach nur 40 % der Trainingsschritte. In direkten Vergleichen über 100.000 Deals erzielte VRPO positive Gewinne gegen PerfectDou, DouZero und sich selbst (in Rollentausch-Matches) und etablierte einen neuen State of the Art.
Heads-Up No-Limit Texas Hold'em (HUNL): VRPO wurde an HUNL mit einem Stack von 200 Big Blinds trainiert. Im Vergleich zu IPPO und MAPPO reduzierte VRPO die Standardabweichung der Vorteilsschätzungen während des Trainings signifikant. Gegen die starke Baseline Slumbot erzielte der VRPO-Agent einen durchschnittlichen Gewinn von $33 \pm 19$ mBB/Hand über 1.000.000 Hände. Bemerkenswerterweise wurde diese Leistung ohne Online-Suche, Teilspiellösung oder blaupausenbasiertes Erhöhen der Einsatzhöhe erreicht.

Bedeutung und Umfang

Das Papier behauptet, dass der Hauptbeitrag die Identifikation der Varianz der Vorteilsschätzung als Engstelle im Gleichgewichts-Selbstspiel ist und der Nachweis, dass Q-Boosting dieses Problem effektiv mildert. Die Ergebnisse deuten darauf hin, dass die Reduzierung der Varianz in der Vorteilsschätzung erhebliche Gewinne in der Qualität erlernter Gleichgewichte bringen kann.

Die Autoren halten einen bescheidenen Umfang bezüglich ihrer Behauptungen:

Der Ansatz wird für Spiele mit großen diskreten Aktionsmengen (via Zerlegung) validiert, adressiert jedoch keine hochdimensionalen kontinuierlichen Aktionsräume.
Der empirische Fokus liegt auf stochastischem Selbstspiel mit zentralisierten Kritikern; die Autoren behaupten keine allgemeinen Verbesserungen gegenüber GAE in Standard-Einzelagenten-RL-Benchmarks.
Die Methode beruht auf der Fähigkeit, Strategieerwartungen über Aktionen zu berechnen, was in den getesteten Domänen machbar ist, aber für extrem große Aktionsräume spezifische architektonische Überlegungen erfordern kann.

Zusammenfassend stellt VRPO einen bedeutenden Schritt vorwärts bei der Anwendung von Strategiegradient-Methoden auf Spiele mit unvollständiger Information dar, indem eine spezifische, zuvor unteridentifizierte Varianzquelle, die dem stochastischen Gleichgewichtslernen inhärent ist, adressiert wird.