Neuer, speicher‑effizienter Self‑Play-Algorithmus für modellfreies RL

In der schnell wachsenden Forschung zu Multi‑Agenten‑Reinforcement‑Learning (MARL) gibt es seit langem Probleme mit Speicherbedarf, hoher Stichprobenkomplexität und langen Lernzeiten. Ein neues Verfahren, das „Memory‑Efficient Nash Q‑Learning“ (ME‑Nash‑QL) genannt wird, adressiert diese Schwächen für zwei‑Spieler‑Null‑Summen‑Markov‑Spiele.

ME‑Nash‑QL liefert eine ε‑approximation des Nash‑Policys mit einer Speicherkomplexität von O(SABH) und einer Stichprobenkomplexität von ~O(H⁴SAB/ε²). Dabei sind S die Zustände, A und B die Aktionen der beiden Spieler und H die Spielhorizontlänge. Für tabellarische Fälle und lange Horizonte (wenn min{A,B} ≪ H²) übertrifft es bestehende Algorithmen sowohl in Speicher als auch in Stichprobenbedarf.

Darüber hinaus erreicht der Algorithmus die niedrigste Rechenkomplexität von O(T·poly(AB)) und hält dabei Markov‑Policies bei. Im Vergleich zu Vorgängern reduziert ME‑Nash‑QL den Burn‑In‑Kostenfaktor auf O(SAB·poly(H)), während frühere Methoden mindestens O(S³AB·poly(H)) erforderten, um dieselbe Leistungsstufe zu erreichen.