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

arXiv: https://arxiv.org/abs/2608.12231 · HTML: https://mlsanity.com/paper/2608.12231/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 31 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 2 of 2)

- [An efficient high-probability algorithm for Linear Bandits](https://mlsanity.com/paper/1610.02072/) (2016)
- [Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex](https://mlsanity.com/paper/2607.13990/) (2026)

## Abstract (arXiv)

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=binomdm 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-δ, regret against the best fixed action of [ RT = Oleft(√dTlog(K/δ)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 δ, every randomized policy admits a deterministic adaptive non-anticipating adversary for which, with probability at least δ, [ RT = Omegaleft(√dTlog(K/δ)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 √log K gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.