Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits

The combinatorial multi-armed bandit (CMAB) is a cornerstone of sequential decision-making framework, dominated by two algorithmic families: UCB-based and adversarial methods such as follow the regularized leader (FTRL) and online mirror descent (OMD). However, prominent UCB-based approaches like CUCB suffer from additional regret factor log T that is detrimental over long horizons, while adversarial methods such as EXP3.M and HYBRID impose significant computational overhead. To resolve this trade-off, we introduce the Combinatorial Minimax Optimal Strategy in the Stochastic setting (CMOSS). CMOSS is a computationally efficient algorithm that achieves an instance-independent regret of Obig( (log k)√kmTbig ) when k≤ fracm2 and Obig((m-k)√log klog(m-k)Tbig ) when k>fracm2 under semi-bandit feedback, where m is the number of arms and k is the maximum cardinality of a feasible action. Crucially, this result eliminates the dependency on log T and matches the established lower bounds of Omegabig(√kmTbig) when k≤ fracm2 and Omegabig((m-k)√log (fracmm-k) Tbig) when k>fracm2 up to logarithmic terms of k and m. We then extend our analysis to show that CMOSS is also applicable to cascading feedback. Experiments on synthetic and real-world datasets validate that CMOSS consistently outperforms benchmark algorithms in both regret and runtime efficiency.