Neuer Ansatz liefert nahezu optimalen Regret für verteilte adversariale Banditen

Ein kürzlich veröffentlichtes Papier auf arXiv präsentiert einen Durchbruch im Bereich der verteilten adversarialen Banditen. Dabei arbeiten N Agenten zusammen, um den globalen durchschnittlichen Verlust zu minimieren, obwohl jeder Agent nur seine eigenen lokalen Verluste sieht.

Die Autoren zeigen, dass der minimax‑Regret für dieses Problem asymptotisch \(\tilde{\Theta}\!\bigl(\sqrt{(\rho^{-1/2}+K/N)\,T}\bigr)\) beträgt, wobei T die Zeitspanne, K die Anzahl der Aktionen und ρ das Spektral­lückenmaß der Kommunikationsmatrix ist. Ihr Algorithmus nutzt eine neuartige Black‑Box‑Reduktion auf Banditen mit verzögertem Feedback und erfordert lediglich Gossip‑Kommunikation. Damit wird das bisher beste Ergebnis \(\tilde{O}\!\bigl(\rho^{-1/3}(KT)^{2/3}\bigr)\) von Yi und Vojnovic (2023) deutlich übertroffen.

Ein ergänzendes Matching‑Lower‑Bound beweist, dass die Schwierigkeit des Problems in einen Kommunikations­kosten‑Term \(\rho^{-1/4}\sqrt{T}\) und einen Banditen‑Kosten‑Term \(\sqrt{KT/N}\) zerfällt. Darüber hinaus werden erste‑Ordnung‑ und Best‑of‑Both‑Worlds‑Grenzen für das verteilte adversariale Setting abgeleitet, was die Vielseitigkeit des Ansatzes unterstreicht.

Schließlich wird das Framework auf verteilte lineare Banditen in \(\mathbb{R}^d\) ausgeweitet. Dort erreicht der Algorithmus einen Regret‑Bound von \(\tilde{O}\!\bigl(\sqrt{(\rho^{-1/2}+1/N)\,dT}\bigr)\) bei lediglich \(O(d)\) Kommunikations­Kosten pro Agent und Runde, die über einen volumetrischen Spanner realisiert werden.