# Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits

arXiv: https://arxiv.org/abs/2508.06247 · HTML: https://mlsanity.com/paper/2508.06247/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 8 Aug 2025.

## Builds on (most cited first, 15 of 15)

- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates](https://mlsanity.com/paper/1711.03591/) (2017)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Optimally Confident UCB: Improved Regret for Finite-Armed Bandits](https://mlsanity.com/paper/1507.07880/) (2015)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Networked Stochastic Multi-Armed Bandits with Combinatorial Strategies](https://mlsanity.com/paper/1503.06169/) (2015)

## Abstract (arXiv)

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.