An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits
2026-08-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a problem where a learner picks groups of items and only sees the total loss of the chosen group, making it hard because the number of groups can be very large. They created a new efficient algorithm that cleverly uses the fact that each group's loss comes from individual item losses, so it doesn't need to check every group explicitly. Their method achieves a strong performance guarantee similar to previous best algorithms but is much more practical as it uses less memory and runs faster. This work solves a previously open problem raised by other researchers.
adversarial combinatorial banditsm-set actionsregret boundsEXP3 algorithmadaptive adversariescomputational efficiencyhigh-probability guaranteessampling distributionscombinatorial optimizationpolynomial time algorithms
Authors
Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
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-δ$, 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.