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

In the adversarial m-set bandit problem, a learner selects $m$ items out of $d$ at each round and observes only the aggregate loss. With $K = \binom{d}{m}$ possible actions, the action space is exponentially large, making standard algorithms like EXP3-KW computationally infeasible. The authors seek a polynomial-time algorithm that achieves the same near-optimal regret rate as finite-action algorithms without explicitly enumerating the action set.

The authors utilize the family of weighted m-set distributions, which can be represented by only $d$ parameters. The primary challenge is that the standard quadratic correction used in EXP3-KW to achieve high-probability regret bounds does not preserve this distribution family. To overcome this, the authors construct a novel affine majorant of the leverage score using the covariance bound of Cesari and Colomboni. This allows them to perform multiplicative-weights updates that remain within the weighted m-set family while maintaining the necessary control over estimation error.

The proposed algorithm achieves a high-probability regret bound of $\tilde{O}(\sqrt{dmT})$, which matches the minimax optimal rate for this problem. This result resolves an open problem posed by Maiti et al. by providing a polynomial-time implementation that avoids the exponential space requirements of previous near-optimal approaches. The authors demonstrate that their method is computationally efficient, relying on elementary symmetric polynomials to compute marginal probabilities and sample from the distribution without enumerating the action space.

This work bridges the gap between statistical optimality and computational efficiency in combinatorial bandits. By providing a polynomial-time algorithm that matches the regret bounds of exponential-time counterparts, it enables the practical application of near-optimal bandit strategies in large-scale combinatorial settings where the number of possible subsets is too vast to track individually.