[Submitted on 12 Aug 2026 (v1), last revised 3 Nov 2026 (this version, v3)]
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. 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-delta$, regret against the best action in hindsight of $R_T =O(sqrt{dTlog(K/delta)}). $ This matches the high-probability regret bound of the finite-action EXP3 with Kiefer-Wolfowitz exploration 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. This resolves an open problem posed by Maiti et al. We complement this upper bound with a matching high-probability lower bound. For all sufficiently small $delta$ and all sufficiently large horizons, every randomized algorithm admits an adaptive non-anticipating adversary for which, with probability at least $delta$, $R_T=Omega( sqrt{dTlog(K/delta)}). $ Thus, the rate is minimax optimal up to universal constants in this regime. In particular, setting $m=1$ shows that the $log K$ factor in the high-probability regret bound for ordinary $K$-armed bandits against adaptive non-anticipating adversaries is unavoidable. This strengthens the lower bound of Gerchinovitz and Lattimore, closing the remaining $sqrt{log K}$ gap between high-probability upper and lower regret bounds.
Submission history
From: Francesco Bacchiocchi [view email]
[v1] Wed, 12 Aug 2026 16:28:06 UTC (30 KB)
[v2] Tue, 25 Aug 2026 16:57:37 UTC (47 KB)
[v3] Tue, 3 Nov 2026 10:20:45 UTC (59 KB)
