Batched Combinatorial Semi-Bandits Problem

In this paper, we study stochastic combinatorial semi-bandits with batched feedback, referred to as the batched combinatorial semi-bandit problem. For linear reward functions, Kim et al. (2025) showed that O(mloglogT) batches are sufficient to achieve near-optimal worst-case regret, where m is the number of base arms, and T is the time horizon. We propose SE-BC, which achieves near-optimal worst-case regret for general non-linear reward functions while removing the factor m from the batch complexity. We also prove a matching lower bound showing that any algorithm attaining worst-case optimal regret must use at least Ω(loglogT) batches. Therefore, the batch complexity of SE-BC is optimal up to constant factors. Simulation results show that SE-BC achieves lower regret while using fewer batches.