An Efficient Near-Optimal Algorithm for Adversarial m-Set Bandits

arXiv:2608.12231v1 Announce Type: new 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=inom{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-elta, regret against the best fixed action of [ R_T = Oleft(sqrt{dTlog(K/elta)}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.

Source: arXiv cs.LG | 2026-08-13