A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem

We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves $\sqrt{T}$ regret over general convex action sets. Our algorithm attains $\widetilde{\mathcal{O}}(d^{5/4}\sqrt{T})$ regret using only linear optimization oracles, and the near-optimal $\widetilde{\mathcal{O}}(d\sqrt{T})$ regret when an optimal-design exploration distribution is further available. This improves on the $T^{2/3}$ regret of the FTPL algorithm of Dani and Hayes (2006) for general convex sets, and generalizes the $\sqrt{T}$ regret of Lévy et al. (2026) over two special action sets (hypercube and Euclidean ball). Compared to previous oracle-efficient linear bandit algorithms based on continuous exponential weights, the FTPL approach generally has better computational efficiency, and is much simpler to implement. The key algorithmic element is a perturbation distribution that adapts to the estimated rewards. Its simplest form, an adaptive Gaussian perturbation, is straightforward to implement and already attains the regret bound above. We further extend it to two general constructions, random-weighting and elliptical perturbations, each covering distributions from light tails (Gaussian) to heavy tails (Student-$t_2$). On the technical side, we develop a systematic way to analyze the stability term in the FTPL regret through the Fisher information of the perturbation distribution. This builds a general framework for FTPL beyond existing ones such as the hazard rate and the FTRL-FTPL duality.

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-δ$, regret against the best fixed action of $$R_T = O\left(\sqrt{dT\log(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 $δ$, $$R_T = Ω\left(\sqrt{dT\log(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 $\sqrt{\log K}$ gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.

We show upper and lower bounds on the regret of $m$-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.