Search papers, labs, and topics across Lattice.
This paper addresses the challenge of adversarial combinatorial bandits with $m$-set actions, where the learner selects $m$ items from a potentially exponential set of $K=\binom{d}{m}$ actions. The authors introduce a novel algorithm that efficiently computes regret bounds without the need to enumerate all possible actions, achieving a regret of \( R_T = O\left(\sqrt{dT\log(K/未)}\right) \) against adaptive adversaries. This approach not only matches the performance of existing algorithms but also significantly reduces computational complexity, resolving a key open problem in the field.
Achieving near-optimal regret in adversarial $m$-set bandits without exponential space requirements could redefine efficiency benchmarks in combinatorial learning.
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.
