Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

1. Problemstellung

Das Paper adressiert zwei-spielerige, general-sum (nicht-nullsummen) stochastische Stackelberg-Spiele (SSGs). In diesem Setting interagieren ein Leader (Spieler A) und ein Follower (Spieler B) in einer dynamischen Umgebung, die durch einen Markov-Prozess modelliert wird.

• Follower-Verhalten: Der Follower ist als „Best-Response-Follower" definiert. Das bedeutet, er wählt immer eine deterministische stationäre Strategie, die seinen eigenen erwarteten diskontierten kumulativen Reward maximiert, gegeben die Strategie des Leaders.
• Leader-Ziel: Der Leader möchte eine stationäre Strategie finden, die seinen eigenen Reward maximiert, unter der Annahme, dass der Follower optimal auf diese Strategie reagiert. Das ideale Ziel ist die Berechnung einer Stationären Stackelberg-Gleichgewichtslösung (SSE).
• Das Kernproblem:
  1. Nicht-Existenz von SSEs: Im Gegensatz zu Nullsummenspielen oder kooperativen Settings existiert eine SSE in general-sum SSGs nicht immer. Es kann vorkommen, dass keine einzelne Strategie den Reward über alle Zustände hinweg gleichzeitig maximiert (Trade-off zwischen Zuständen).
  2. Versagen bestehender Methoden: Existierende Algorithmen basieren entweder auf dynamischen Programmieroperatoren (Value Iteration) oder Policy-Gradient-Methoden.
     • Operatoren-basierte Methoden (z. B. Bucarey et al., 2022) konvergieren zu einem Fixpunkt, der jedoch nicht notwendigerweise eine SSE ist und keine Garantie für eine monotone Verbesserung des Leader-Rewards bietet.
     • Policy-Gradient-Methoden garantieren Konvergenz zu lokalen Gleichgewichten (DSE), die jedoch nicht immer Best-Responses des Followers entsprechen, und bieten keine Garantie für monotone Verbesserung.

Das Paper sucht nach einem Algorithmus, der monotone Verbesserungen des Leader-Rewards garantiert und auch dann konvergiert, wenn keine SSE existiert.

2. Methodik

Die Autoren entwickeln einen neuen Policy-Iteration-Algorithmus, der auf einem neuartigen Policy-Improvement-Theorem für SSGs basiert.

A. Analyse bestehender Operatoren

Zunächst wird gezeigt, dass der Fixpunkt des in der Literatur verwendeten dynamischen Programmieroperators $T$ (basierend auf Bucarey et al., 2022) nicht mit der SE-Wertfunktion übereinstimmt. Der Operator maximiert den Leader-Reward nur unter einer spezifischen, vom Follower-Value abhängigen Reaktion $R_B(f, V_B)$, nicht aber unter der wahren Best-Response $R^*_B(f)$. Dies führt dazu, dass die erhaltene Policy suboptimal sein kann.

B. Pareto-Optimalität als neues Ziel

Da SSEs nicht immer existieren, führen die Autoren das Konzept der Pareto-Optimalität (PO) als erweiterte Optimalitätsbedingung ein.

• Eine Policy ist Pareto-optimal, wenn ihre Wertfunktion $V_A$ im Raum der erreichbaren Wertfunktionen nicht von einer anderen Policy strikt dominiert wird (d.h. es gibt keine andere Policy, die in allen Zuständen einen höheren oder gleichen Reward liefert und in mindestens einem Zustand strikt besser ist).
• Es wird bewiesen, dass eine PO-Policy immer existiert und, falls eine SSE existiert, mit dieser übereinstimmt.

C. Policy-Improvement-Theorem (Satz 8)

Ein zentrales Ergebnis ist die Herleitung eines Policy-Improvement-Theorems für SSGs mit Best-Response-Followern.

• Es wird eine Q-Funktion $Q^{f' \dagger}_A(s, f)$ definiert, die den erwarteten Reward der neuen Policy $f$ unter der Annahme beschreibt, dass der Follower auf $f$ mit seiner Best-Response reagiert, aber die zukünftigen Werte nach der alten Policy $f'$ bewertet werden.
• Theorem: Wenn $Q^{f' \dagger}_A(\cdot, f) \succeq V^{f' \dagger}_A$ (d.h. die neue Policy ist in jedem Zustand mindestens so gut wie die alte unter der neuen Reaktion), dann gilt $V^{f \dagger}_A \succeq V^{f' \dagger}_A$.
• Dies ermöglicht es, eine neue Policy zu wählen, die garantiert den Leader-Reward verbessert, ohne die exakte Wertfunktion der neuen Policy sofort berechnen zu müssen.

D. Der Algorithmus (Pareto-Optimal Policy Iteration)

Der vorgeschlagene Algorithmus (Algorithmus 1) funktioniert wie folgt:

1. Initialisierung: Zufällige Start-Policy $f_0$.
2. Bewertung: Berechnung der Wertfunktion $V^{f_t \dagger}_A$ durch Iteration des Bellman-Operators unter der aktuellen Policy und der Best-Response des Followers.
3. Verbesserung: Suche nach einer neuen Policy $f_{t+1}$, die die Bedingung $Q^{f_t \dagger}_A(\cdot, f) \succeq V^{f_t \dagger}_A$ erfüllt.
4. Skalarisierung: Um eine spezifische Policy aus der Menge der verbessernden Policies auszuwählen, wird eine Pareto-konforme Skalarisierungsfunktion $L$ (z.B. gewichtete Summe der Zustandswerte) maximiert.
5. Konvergenz: Der Prozess wiederholt sich, bis keine weitere strikte Verbesserung mehr möglich ist.

Für den Fall, dass der Leader myopisch ist ($\gamma_A = 0$), wird bewiesen, dass der Algorithmus garantiert zu einer Pareto-optimalen Policy konvergiert. Für $\gamma_A > 0$ konvergiert er zu einem Punkt am Rand der erreichbaren Wertfunktionen, der die Pareto-Front approximiert.

3. Wichtige Beiträge

1. Analyse von DP-Operatoren: Die Autoren zeigen explizit, dass der Fixpunkt bestehender Operatoren (Bucarey et al., Zhang et al.) nicht notwendigerweise eine SSE darstellt und keine monotone Leistungsverbesserung garantiert.
2. Policy-Improvement-Theorem für SSGs: Die erste theoretische Herleitung eines Policy-Improvement-Theorems für general-sum SSGs mit Best-Response-Followern, das monotone Verbesserungen garantiert.
3. Neuer Algorithmus: Entwicklung eines Policy-Iteration-Algorithmus, der auf dem obigen Theorem basiert und monoton zum Pareto-Front konvergiert.
4. Konvergenzgarantie: Beweis, dass der Algorithmus auch dann konvergiert und eine „vernünftige" Lösung (Pareto-optimal) liefert, wenn keine SSE existiert. Dies ist die erste theoretische Garantie für general-sum SSGs mit myopischen Leadern.
5. Pareto-Optimalität als Ersatz: Die Einführung von Pareto-Optimalität als sinnvolles Ziel, wenn SSEs nicht existieren, und der Nachweis, dass SSEs und PO-Policies in diesem Kontext übereinstimmen, falls SSEs existieren.

4. Ergebnisse

• Theoretische Garantie: Der Algorithmus garantiert eine monotone Steigerung der Zustandswerte des Leaders ($V_{t+1} \succeq V_t$).
• Konvergenzverhalten:
  • Im Fall $\gamma_A = 0$ (myopischer Leader) konvergiert die Folge der Wertfunktionen garantiert gegen eine Pareto-optimale Wertfunktion.
  • Im allgemeinen Fall ($\gamma_A > 0$) konvergiert der Algorithmus gegen einen Punkt am Rand der Menge der erreichbaren Wertfunktionen ($\partial V$), der die Pareto-Front einschließt.
• Vergleich: Im Gegensatz zu bestehenden Methoden, die in Fällen ohne SSE scheitern oder zu suboptimalen Lösungen konvergieren, bietet der vorgeschlagene Ansatz eine robuste Alternative, die immer eine Verbesserung liefert.

5. Bedeutung und Ausblick

Die Arbeit ist von erheblicher Bedeutung für das Feld des Multi-Agent Reinforcement Learning (MARL) und der Spieltheorie, insbesondere in Szenarien mit hierarchischer Entscheidungsfindung (Leader-Follower).

• Praktische Relevanz: Viele reale Anwendungen (z.B. E-Commerce-Plattformen, Cyber-Sicherheit, Policy-Teaching) lassen sich als SSGs modellieren, bei denen SSEs oft nicht existieren. Der vorgestellte Algorithmus bietet hier eine verlässliche Methode zur Optimierung.
• Theoretischer Fortschritt: Die Arbeit schließt eine Lücke in der Theorie, indem sie zeigt, wie man auch ohne Existenz eines Gleichgewichts (SSE) eine garantierte Verbesserung erreichen kann, indem man das Ziel auf Pareto-Optimalität verschiebt.
• Zukünftige Arbeiten: Die Autoren identifizieren Limitationen, wie die Notwendigkeit effizienter Suchstrategien für den nächsten Policy-Schritt (da die Suche im gesamten Policy-Raum teuer sein kann) und die Erweiterung auf Szenarien, in denen die Transitionsfunktion unbekannt ist (RL-Setting).

Zusammenfassend stellt dieses Paper einen bedeutenden theoretischen und algorithmischen Durchbruch dar, der die Zuverlässigkeit von Optimierungsverfahren in komplexen, nicht-nullsummen stochastischen Spielen unter der Annahme rationaler Follower erheblich verbessert.