An Efficient Minimax-Optimal Algorithm for Adversarial $m$-Set Bandits

Sicherheitsmeldung mit Schweregrad noch nicht bewertet. Technische Details im Tab „Originaltext“; empfohlene Schritte in der Checkliste.

Originaltext der Quelle (nicht übersetzt) – die deutsche Zusammenfassung findest du im Tab „Kurzfassung".

arXiv:2608.12231v2 Announce Type: replace Abstract: We study adversarial combinatorial bandits with $m$-set actions, where at each round the learner selects $m$ out of $d$ items and observes only the aggregate loss of the selected items. The resulting action set contains $K=\binom{d}{m}$ elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same $d$-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least $1-\delta$, regret against the best fixed action of \[ R_T = O\left(\sqrt{dT\log(K/\delta)}\right). \] This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with $d$ parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al. We complement this upper bound with a matching high-probability lower bound. For all sufficiently small $\delta$, every randomized policy admits a deterministic adaptive non-anticipating adversary for which, with probability at least $\delta$, \[ R_T = \Omega\left(\sqrt{dT\log(K/\delta)}\right). \] Thus, the rate is minimax optimal up to universal constants in this regime. In particular, setting $m=1$ proves that the $\log K$ for ordinary $K$-armed bandits …

Vollständiger Originalartikel ↗

• Betroffenheit im eigenen Stack prüfen: Versionen/Komponenten abgleichen.
• Originalquelle / Hersteller-Advisory lesen: https://arxiv.org/abs/2608.12231
• Verfügbaren Patch oder Workaround einspielen und dokumentieren.