💻 computer science

Expected Return Symmetries

Dieses Paper führt „Expected Return Symmetries“ ein, eine breitere Klasse von Symmetrien, die traditionelle Umgebungssymmetrien umfasst und es Agenten in dezentralen Multi-Agenten-Settings ermöglicht, eine überlegene Zero-Shot-Koordination zu erreichen, ohne dass vorab Wissen über die Ground-Truth-Symmetrien erforderlich ist.

Ursprüngliche Autoren: Darius Muglich, Johannes Forkel, Elise van der Pol, Jakob Foerster

Veröffentlicht 2026-06-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Darius Muglich, Johannes Forkel, Elise van der Pol, Jakob Foerster

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: Das „Links- vs. Rechts-Dilemma“

Stellen Sie sich zwei Roboter vor, die separat darauf trainiert wurden, ein kooperatives Spiel zu spielen, wie etwa eine hochkarätige Version von Hanabi (ein Kartenspiel, bei dem man seine eigenen Karten nicht sehen kann) oder Overcooked (ein chaotischer Kochsimulator). Beide sind brillant im Spiel, wenn sie alleine gegen sich selbst spielen.

Wenn man jedoch Roboter A mit Roboter B zusammenbringt, scheitern sie kläglich. Warum?

Weil sie während ihres Solo-Trainings versehentlich ihre eigenen Geheimsprachen erfunden haben.

Roboter A lernte: Wenn der andere Spieler eine Karte ablegt, bedeutet das „Ich bin glücklich“.
Roboter B lernte: Dieselbe Aktion bedeutet „Ich bin wütend“.

In der Fachsprache des Papers nennt sich das gegenseitig inkompatible Symmetriebrechung (mutually incompatible symmetry breaking). Die Roboter fanden eine Lösung, die für sie individuell funktionierte, aber da sie sich nicht darüber einig waren, welche Version der Lösung sie verwenden sollten, sind sie wie zwei Menschen, die sich die Hand geben wollen, aber einer bietet die linke Hand an und der andere die rechte. Beide sind in ihrem Kopf „korrekt“, aber sie können nicht koordinieren.

Die alte Lösung: „Other-Play“ (Der Regelbuch-Ansatz)

Zuvor versuchten Forscher, dies zu beheben, indem sie Roboter lehrten, die Symmetrien der Umgebung zu respektieren.

Stellen Sie sich die Spielumgebung wie einen Raum mit vier identischen Türen vor. Wenn Sie durch die Nordtür gehen, erhalten Sie eine Belohnung. Wenn Sie durch die Südtür gehen, erhalten Sie exakt dieselbe Belohnung. Der Raum ist „symmetrisch“.

Die alte Methode: Die Forscher sagten den Robotern: „Hey, Nord und Süd sind dasselbe. Merke nicht nur ‚Nord ist gut‘. Merke ‚Jede Tür, die wie Nord aussieht, ist gut‘.“
Die Einschränkung: Das funktioniert gut bei offensichtlichen Dingen wie Farben oder Richtungen. Aber es versagt, wenn die „Gleichheit“ nicht über das Layout des Raums geht, sondern über die Strategie selbst. Es ist, als würde man den Robotern sagen: „Es ist egal, ob du einen roten oder einen blauen Hut trägst“, aber man versäumt zu erkennen, dass es manchmal entscheidend ist, eine bestimmte Art von Hut zu tragen, um einem Partner zu signalisieren: „Ich bin bereit zu kochen“.

Die neue Lösung: „Expected Return Symmetries“ (Der „Was funktioniert“-Ansatz)

Die Autoren dieser Arbeit schlagen einen klügeren Weg vor, um diese verborgenen Verbindungen zu finden. Anstatt nach den Regeln des Raums (der Umgebung) zu suchen, schauen sie auf die Ergebnisse (die Belohnungen).

Sie führen das Konzept der Expected Return Symmetries (Erwartete Ertrags-Symmetrien) ein.

Die Analogie: Der „Magische Spiegel“
Stellen Sie sich vor, Sie haben einen magischen Spiegel. Wenn Sie vor ihm stehen und eine bestimmte Tanzbewegung machen, bekommen Sie einen goldenen Stern.

Alte Sichtweise: Der Spiegel reflektiert nur Dinge, die exakt gleich aussehen (z. B. wenn Sie die linke Hand heben, hebt die Reflexion die rechte Hand).
Neue Sichtweise (Expected Return): Der Spiegel ist intelligenter. Er fragt: „Wenn ich deine Tanzbewegung in etwas völlig anderes ändere, bekommst du immer noch einen goldenen Stern?“

Wenn die Antwort Ja lautet, dann sind diese zwei unterschiedlichen Tanzbewegungen im Sinne des Papers „symmetrisch“. Sie mögen völlig verschieden aussehen, führen aber zum gleichen Erfolg.

Das Paper argumentiert, dass Roboter durch das Erkennen dieser „ergebnisbasierten“ Symmetrien viel flexibler werden. Sie lernen, dass „Aktion X“ und „Aktion Y“ austauschbar sind, weil beide zu einem glücklichen Ausgang führen, auch wenn die Spielregeln nicht explizit sagen, dass sie dasselbe sind.

Wie sie es gemacht haben (Die „Versuch und Irrtum“-Maschine)

Das Paper rät diese Symmetrien nicht einfach nur; es hat eine Methode entwickelt, um sie automatisch zu finden.

Der Pool der Experten: Zuerst trainierten sie eine ganze Menge Roboter zu Experten im Spiel (mittels einer Methode namens Self-Play).
Das Mischspiel: Dann nahmen sie diese Experten-Roboter und begannen, ihr Verhalten zu „mischen“. Sie probierten das Vertauschen von Aktionen, das Verändern von Beobachtungen und das Vermischen von Strategien.
Der Punktezähler: Sie fragten: „Wenn wir die Strategie von Roboter A mit der Strategie von Roboter B tauschen, erzielen sie dann immer noch die gleiche hohe Punktzahl?“
- Wenn die Punktzahl hoch bleibt, ist dieser Tausch eine gültige „Expected Return Symmetry“.
- Wenn die Punktzahl abstürzt, ist der Tausch schlecht.
Das Ergebnis: Sie fanden eine Reihe von „magischen Täuschen“, die den Erfolg des Spiels bewahren. Dann lehrten sie neue Roboter, diese Täusche während des Trainings anzuwenden.

Die Ergebnisse: Warum es wichtig ist

Das Paper testete dies in drei verschiedenen Szenarien:

Ein einfaches Hebel-Spiel: Eine grundlegende Koordinationsaufgabe.
Overcooked V2: Ein komplexes Kochspiel, bei dem Timing und Kommunikation entscheidend sind.
Hanabi: Ein sehr schwieriges Kartenspiel mit versteckter Information.

Die Erkenntnisse:

Roboter, die mit dieser neuen „Expected Return“-Methode trainiert wurden, koordinierten sich signifikant besser mit Fremden als Roboter, die mit der alten „Environment Symmetry“-Methode trainiert wurden.
Im Overcooked-Spiel reduzierte die neue Methode die Lücke zwischen „Spielen mit sich selbst“ und „Spielen mit einem Fremden“ um eine enorme Menge.
In Hanabi, das notorisch schwer zu koordinieren ist, übertraf die neue Methode die bisherigen State-of-the-Art-Methoden, obwohl die neue Methode keinen „Spickzettel“ über die Spielregeln hatte (wie etwa das Wissen, dass Rot und Blau nur Farb-Austausch-Varianten sind).

Das Fazative Fazit

Das Paper behauptet, dass wir KI-Agenten, damit sie ohne vorherige Koordination gut zusammenarbeiten, nicht nur die Regeln des Spiels lehren sollten. Stattdessen sollten wir sie lehren, zu erkennen, welche unterschiedlichen Verhaltensweisen zum gleichen Erfolg führen.

Indem sie sich auf das Ergebnis (den erwarteten Ertrag/Expected Return) statt nur auf den Input (das Layout der Umgebung) konzentrieren, lernen die Roboter eine breitere, flexiblere Auswahl an „geheimen Handschlägen“. Dies ermöglicht es ihnen, sich viel schneller und effektiver an neue Partner anzupassen und löst das „Links- vs. Rechts-Problem“, das die Multi-Agenten-KI seit Jahren beschäftigt.

Technische Zusammenfassung: Erwartete Rücksymmetrien (Expected Return Symmetries)

Problemstellung
In der kooperativen Multi-Agenten-Reinforcement-Learning (MARL) stellt die Zero-Shot-Koordination (ZSC) eine grundlegende Herausforderung dar: die Fähigkeit von Agenten, die unabhängig voneinander trainiert wurden, zur Testzeit effektiv mit neuen Partnern zu koordinieren, ohne vorherige Kommunikation. Ein primärer Ausfallmodus in der ZSC ist die gegenseitig inkompatible Symmetriebrechung. Wenn Agenten isoliert trainieren, können sie zu äquivalenten, aber inkompatiblen Strategien konvergieren (z. B. vereinbart ein Team, das Signal „spielen“ mit der Farbe Blau zu kennzeichnen, während ein anderes Rot verwendet).

Bestehende Lösungen, wie das Other-Play (OP)-Ziel, adressieren dies durch die Erzwingung der Kompatibilität zwischen Strategien, die unter Dec-POMDP-Symmetrien (Umkennzeichnungen von Zuständen, Aktionen und Beobachtungen, die die Übergangs- und Belohnungsfunktionen invariant lassen) äquivalent sind. Dieses Vorgehen hat jedoch zwei Einschränkungen:

Koordinationsfehler-Modi: Die Symmetriebrechung in der Umgebung ist nur eine Art des Koordinationsfehlers. Agenten können immer noch überkoordinieren, indem sie selbst in Abwesenheit nicht-trivialer Dec-POMDP-Symmetrien übermäßig spezifische Konventionen bilden.
Zugänglichkeit von Symmetrien: Aktuelle Methoden erfordern Vorabwissen über die Symmetrien der Umgebung. Das automatische Entdecken dieser Symmetrien in groß angelegten Dec-POMDPs ist oft rechentechnisch nicht machbar, und viele Methoden verlassen sich auf privilegierte Informationen (z. B. die Grundwahrheit der Dynamik oder Symmetriegruppen), die in realen Szenarien nicht verfügbar sind.

Methodik
Die Arbeit führt Erwartete Rücksymmetrien (Expected Return (ER) Symmetries) ein, eine breitere Klasse von Symmetrien, die Dec-POMDP-Symmetrien als Untergruppe enthält.

Definition: Eine Transformation $\phi$ ist eine ER-Symmetrie, wenn sie die Menge der selbstspiel-optimalen Boltzmann-explorativen Strategien ( $\Pi^*_\alpha$ ) bewahrt. Speziell gilt: $\Phi_{ER} = \{ \phi \in \Psi \mid \forall \pi \in \Pi^*_\alpha: \phi(\pi) \in \Pi^*_\alpha \}$ . Im Gegensatz zu Dec-POMDP-Symmetrien, die die Invarianz der Übergangs- und Belohnungsfunktionen erfordern, verlangen ER-Symmetrien lediglich, dass die Transformation optimale Strategien auf andere optimale Strategien abbildet (den erwarteten Ertrag bewahrt).
Theoretische Eigenschaften: Die Autoren beweisen, dass $\Phi_{ER}$ unter Funktionskomposition eine Gruppe bildet. Entscheidend ist, dass $\Phi_{ER}$ in vielen Fällen eine strikte Obermenge der Dec-POMDP-Symmetrien ist und dadurch Koordinationsunterschiede basierend auf der Strategie statt nur auf Label-Permutationen erfasst.
Lernalgorithmus: Da $\Phi_{ER}$ $Φ_{E R}$ nicht im Voraus bekannt ist, schlägt das Paper skalierbare Methoden vor, um approximative ER-Symmetrien mittels gradientenbasierter Optimierung zu lernen, ohne Zugriff auf die Grundwahrheit der Symmetrien oder der Umgebungsdynamik zu benötigen.
- Zielgröße 1 (Ertragserhaltung): Maximierung des erwarteten Ertrags transformierter Strategien: $\max_\theta \mathbb{E}_{\pi \sim \Pi'} [J(\phi_\theta(\pi))]$ , wobei $\Pi'$ ein Pool von Selbstspiel-optimalen Strategien ist.
- Zielgröße 2 (Kompositionalität & Invertierbarkeit): Eine regularisierte Zielgröße wird eingeführt, um sicherzustellen, dass die gelernten Transformationen eine Gruppe bilden (Erzwingung von Abgeschlossenheit und Invertierbarkeit), indem Abweichungen von der Identität nach doppelter Anwendung bestraft und Erträge unter komponierten Transformationen maximiert werden.
- Zielgröße 3 (Cross-Play Maximierung): Ein alternativer Ansatz optimiert direkt für die Cross-Play-Performance zwischen Paaren von Strategien.
- Die Methode setzt eine minimale Struktur voraus: Sie fixiert die Zustands-Transformation auf die Identität und lernt Beobachtungs- und Aktions-Transformationen (oft über die Suche nach Aktionspermutationen und neuronale Netze für Beobachtungen).

Zentrale Beiträge

Definition von ER-Symmetrien: Das Paper definiert eine neue Symmetriegruppe basierend auf der Bewahrung des erwarteten Ertrags für optimale Strategien, welche die traditionellen Dec-POMDP-Symmetrien subsumiert.
Modellfreies Entdecken: Die Autoren führen Algorithmen ein, um diese Symmetrien rein aus Interaktionen zwischen Agent und Umgebung zu lernen, was kein privilegiertes Wissen über die Struktur oder Dynamik der Umgebung erfordert.
Verbesserte ZSC-Performance: Das Paper zeigt, dass die Kombination der OP-Lernregel mit gelernten ER-Symmetrien das Standard-Self-Play und OP mit Dec-POMDP-Symmetrien signifikant übertrifft, um Überkoordination zu verhindern.
Robustheit in anspruchsvollen Settings: Die Methode zeigt Erfolg in Umgebungen, in denen State-of-the-Art-Methoden wie Off-Belief Learning (OBL) und Cognitive Hierarchies scheitern (z. B. spezifische Hebelspiele und Overcooked V2).

Experimentelle Ergebnisse
Die Autoren evaluieren ihre Methode in vier Umgebungen:

Iterated Three-Lever Game: In diesem Setting fallen ER-Symmetrien mit den Dec-POMs-Symmetrien zusammen, und die Methode findet erfolgreich die optimale ZSC-Strategie.
Toy Coordination Game: Die Methode findet erfolgreich eine nicht-triviale ER-Symmetrie (einen Aktions-Swap), die keine Dec-POMDP-Symmetrie ist, was die Fähigkeit demonstriert, Symmetrien außerhalb der traditionellen Gruppe zu entdecken.
Overcooked V2: In diesem asymmetrischen, stochastischen Benchmark erreichten Agenten, die gelernte ER-Symmetrien nutzen, einen mittleren Cross-Play (XP) Score von 15,8, was das Self-Play-Baseline-Ergebnis von 6,74 deutlich übertrifft und die Varianz in den Koordinationsergebnissen reduziert.
Hanabi: In diesem komplexen Kartenspiel erreichten Agenten mit 11 gelernten ER-Symmetrien einen mittleren XP-Score von 21,64, was sowohl die IPPO-Baseline (4,02) als auch die durch alle 120 bekannten Dec-POMDP-Symmetrien beschränkte IPPO-Baseline (8,61) übertrifft. Die Ergebnisse deuten darauf hin, dass ER-Symmetrien die Optimalität besser bewahren und gleichzeitig die Kompatibilität erzwingen.

Bedeutung und Behauptungen
Das Paper behauptet, dass Expected Return Symmetries eine signifikante Weiterentwicklung für ZSC darstellen, indem sie:

Symmetrie generalisieren: Über starre Umgebungsinvarianzen hinausgehen zu einer flexibleren, strategiezentrierten Definition von Symmetrie, die die Vielfalt optimaler Strategien besser adressiert.
Privilegiertes Wissen entfernen: Die erste Symmetrie-basierte Methode zu sein, die ZSC verbessert, ohne Vorabwissen über Symmetrien oder Dynamiken zu benötigen, was sie für Settings anwendbar macht, in denen solche Informationen nicht verfügbar sind.
Koordinationsfehler lösen: Eine Lösung für Überkoordination bieten, die selbst in Umgebungen effektiv ist, in denen bisherige symmetrie- oder diversitätsbasierte Methoden (wie OBL) versagen.

Die Autoren räumen Einschränkungen ein und merken an, dass die Ausdrucksstärke des Suchraums (beschränkt auf Bijektionen auf Aktions-/Beobachtungsräumen) möglicherweise nicht für alle Umgebungen (z. B. die Zwei-Hebel-Variante des Spiels) ausreicht und dass der Erfolg der Methode von der Qualität der zum Lernen der Symmetrien verwendeten Strategien abhängt.