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

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 against adaptive non-anticipating adversaries is unavoidable, closing the remaining $\sqrt{\log K}$ gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.

Machine Learning (cs.LG)

arXiv:2608.12231 [cs.LG]

(or arXiv:2608.12231v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.12231 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.