Neue Erkenntnisse: Logarithmischer Regret in Zero‑Sum‑Spielen mit Bandit‑Feedback

In einer kürzlich veröffentlichten Arbeit auf arXiv (2602.06348v1) zeigen die Autoren, wie man in Nullsummenspielen mit Bandit‑Feedback – also nur dem eigenen Gewinn als Rückmeldung – das sogenannte Pure‑Strategy‑Maximin‑Regret logarithmisch begrenzen kann. Das Ergebnis ist ein bedeutender Fortschritt gegenüber dem bekannten \(\Omega(\sqrt{T})\)-Regret, das in solchen Settings unvermeidlich ist.

Die Studie unterscheidet zwei Feedback‑Modelle. Im „uninformed“ Modell erhält der Lernende lediglich die Auszahlung seiner gewählten Aktion. Hier demonstriert der Tsallis‑INF‑Algorithmus einen instanzabhängigen Regret‑Wert von \(O(c \log T)\), wobei \(c\) ein spielabhängiger Parameter ist. Ein dazugehöriger Informationstheoretischer Lower Bound bestätigt, dass die Abhängigkeit von \(c\) unvermeidlich ist.

Im „informed“ Modell, bei dem zusätzlich die Aktion des Gegners offengelegt wird, führen die Autoren den Maximin‑UCB‑Algorithmus ein. Dieser erzielt ebenfalls einen logarithmischen Regret‑Wert, jedoch mit einem anderen Parameter \(c'\), der in vielen Fällen deutlich kleiner sein kann als \(c\). Damit wird gezeigt, dass zusätzliche Feedback‑Informationen die Lernschwierigkeit erheblich reduzieren.

Schließlich werden die Resultate auf bilineare Spiele über allgemeine, la…