PSRO ohne Spielsimulation: Neue Methode reduziert Rechenaufwand drastisch

Die Policy Space Response Oracles (PSRO) kombinieren spieltheoretische Gleichgewichtssuche mit maschinellem Lernen und sind damit ein leistungsstarkes Werkzeug zur Annäherung an Nash-Gleichgewichte in Nullsummenspielen. In der Praxis wird ihre Anwendung jedoch durch hohe Rechenkosten eingeschränkt, wobei die Spielsimulation den größten Aufwand verursacht.

Um dieses Problem zu lösen, wurde das Konzept der Simulation‑Free PSRO entwickelt. Dabei werden die klassischen Spielsimulationen komplett weggelassen und stattdessen alternative Verfahren eingesetzt, die die gleiche Zielsetzung verfolgen. Zu diesen Verfahren gehören bereits existierende Ansätze, die die Simulationen durch analytische oder approximative Methoden ersetzen.

Der neue Ansatz, Dynamic Window‑based Simulation‑Free PSRO, führt ein sogenanntes Strategie‑Fenster ein, das die ursprüngliche, oft sehr große Strategiemenge durch eine begrenzte Auswahl ersetzt. Durch die Begrenzung der Fenstergröße wird die Auswahl des Gegner‑Strategie‑Sets vereinfacht und die Robustheit der besten Antwort verbessert. Zusätzlich wird die Strategie, die eliminiert werden soll, mithilfe von Nash‑Clustering bestimmt, wodurch die Größe des Fensters effektiv kontrolliert bleibt.

Experimentelle Tests in verschiedenen Umgebungen zeigen, dass das Dynamic‑Window‑Verfahren die Exploitability deutlich senkt im Vergleich zu bestehenden Methoden und gleichzeitig eine hervorragende Kompatibilität aufweist. Der zugehörige Code ist auf GitHub verfügbar.