Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits

Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li · 2025

Read Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits by Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06247.txt.

Introduction

Zichun Ye, Runqi Wang, Xutong Liu, and Shuai Li design a learning algorithm for repeated group choices in a 2025 paper. The setting is a bandit problem, where a learner picks a set of options each round and sees rewards for the picked set only. Good methods exist, but some pay an extra penalty that grows with time, while others cost heavy computing.

Their method, CMOSS, removes that time penalty while staying cheap to run. Its regret, the loss versus the best fixed choice, nearly matches the known lower limits. The analysis covers two cases based on how large the picked set can be. The method also extends to settings where rewards arrive in a cascade. Tests on made-up and real data back the theory.

Catalog record

CREATORZichun Ye, Runqi Wang, Xutong Liu, Shuai Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06247

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li Abstract 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 \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 O ⁡ ( ( log ⁡ k ) 2 ​ k ​ m ​ T ) O\big((\log k)^{2}\sqrt{kmT}\big) under semi-bandit feedback, where m m is the number of arms and k k is the maximum cardinality of a feasible action. Crucially, this result eliminates the dependency on log ⁡ T \log T and matches the established Ω ⁡ ( k ​ m ​ T ) \Omega\big(\sqrt{kmT}\big) lower bound up to O ⁡ ( ( log ⁡ k ) 2 ) O\big((\log k)^{2}\big) . 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. 1 Introduction The stochastic multi-armed bandit (MAB) is a fundamental T -round sequential decision-making game that has been widely studied in the past two decades ( Audibert and Bubeck 2009 ; Auer et al. 1995 ; Auer et al. 2002 ; Robbins 1952 ) . In this game, one player faces m arms. In each round t\in[T] , the player chooses an arm A_{t} among the m arms and gets a reward drawn from a predetermined but unknown reward distribution with mean \mu_{A_{t}}\in[0,1] . The arm with the largest reward mean \mu_{*} is called the best arm. The total expected regret is defined as \mathbf{E}\left[R(T)\right]=\mathbf{E}\left[\sum_{t=1}^{T}\left(\mu_{*}-\mu_{A_{t}}\right)\right], where the expectation is over the randomness from the player’s strategy and the random reward outcome. And the aim is to minimize the minimax regret, namely the regret of the best algorithm against the worst input. The Upper Confidence Bounds (UCB) algorithm ( Auer, Cesa-Bianchi, and Fischer 2002 ) is a well-known approach for addressing the stochastic MAB problem, achieving an expected regret of O\left(\sqrt{mT\log T}\right) . Building on this foundation, its variant, the Minimax Optimal Strategy in the Stochastic case (MOSS) algorithm ( Audibert and Bubeck 2009 ; Degenne and Perchet 2016 ; Ménard and Garivier 2017 ) , improves the regret bound to O\left(\sqrt{mT}\right) by refining the upper confidence bounds and employing a distinct regret analysis. These results align with the minimax lower bound of \Omega\left(\sqrt{mT}\right) established in ( Auer et al. 2002 ) , demonstrating their optimality in the stochastic setting. In parallel, the EXP3 algorithm ( Auer et al. 1995 ; Littlestone and Warmuth 1994 ) provides a solution for adversarial environments. EXP3 is a classic implementation of the follow the regularized leader (FTRL) framework using a negative entropy regularizer ( Shalev-Shwartz et al. 2012 ) . This approach, also known through the dual perspective of online mirror descent (OMD), achieves a regret of O\left(\sqrt{mT\log m}\right) in both adversarial and stochastic regimes, notably avoiding dependence on \log T . In many real-world applications, however, decision-making problems often extend beyond the simple MAB framework to involve combinatorial actions among multiple arms. For instance, in online advertising ( Kveton et al. 2015a ) , an advertiser could select up to k web pages to display ads, constrained by a budget. Each user visits a subset of pages, and the advertiser must learn the unknown click-through probabilities to maximize clicks. Similarly, in viral marketing ( Gai, Krishnamachari, and Jain 2012 ; Tang et al. 2017 ) , a marketer selects seed nodes in a social network to initiate information cascades, learning influence probabilities to maximize the reach of campaigns. These scenarios highlight the need for algorithms that efficiently address the combiantorial MAB (CMAB) problem. While a number of works ( Combes et al. 2015 ; Kveton et al. 2015c ; Chen et al. 2016 ; Wang and Chen 2017 ; Liu et al. 2022 ; Liu et al. 2024 ; Liu et al. 2025 ) have focused on the CMAB problem, existing algorithms either suffer from additional \log T terms in their regret bounds or incur high computational costs in practice. Among them, the Combinatorial UCB (CUCB) algorithm ( Chen, Wang, and Yuan 2013 ; Kveton et al. 2015c ; Wang and Chen 2017 ; Liu et al. 2022 ) is one of the most prominent and widely adopted approaches. The CUCB algorithm extends the classic UCB framework by selecting the action (super arm) from a feasible set that solves a combinatorial optimization problem defined over the upper confidence bounds of the base arms. Kveton et al. ( Kveton et al. 2015c ) establish an upper regret bound of O\left(\sqrt{kmT\log T}\right) for CUCB, which matches the lower bound of \Omega\left(\sqrt{kmT}\right) only up to a \sqrt{\log T} factor. A separate line of work ( Cesa-Bianchi and Lugosi 2012 ; Combes et al. 2015 ; Uchiya, Nakamura, and Kudo 2010 ; Zimmert, Luo, and Wei 2019 ) focuses on adapting algorithms derived from FTRL and OMD frameworks that could be applied to CMAB setting. The best-known result in this line ( Zimmert, Luo, and Wei 2019 ) achieves a regret of O\left(\sqrt{kmT}\right) when k\leq\frac{m}{2} and O\left((m-k)\sqrt{\log\left(\frac{m}{m-k}\right)T}\right) when k>\frac{m}{2} , successfully removing the \log T term. However, these adversarially designed algorithms are often computationally expensive, limiting their practical utility. This gap—between computational efficiency and regret optimality—has remained unresolved for over a decade, highlighting the critical need for “MOSS-like” algorithms in CMAB that achieve minimax-optimal regret without \log T dependence. 1.1 Our results To address the above limitation, we study the stochastic combinatorial semi-bandit problem and propose the CMOSS algorithm. Our contribution is to show that CMOSS is not only computationally efficient but also has a regret of O\left((\log k)^{2}\sqrt{kmT}\right) . We also extend the setting to cascading feedback and compare our result with CUCB, since the other three algorithms can not be applied to the scenarios where arms in A_{t} are probabilistically triggered. The results are summarized in Table 1 . Algorithm \star Semi-Bandit Feedback Cascading Feedback \circ Computation Complexity Per-Round (Average, 10^{-5} sec) \dagger COMBEXP O\left(\sqrt{k^{3}mT\log m}\right) None Too large CUCB O\left(\sqrt{kmT\log T}\right) O\left(\sqrt{kmT\log T}\right) 5.743 EXP3.M O\left(\sqrt{kmT\log\left(\frac{m}{k}\right)}\right) None 43.095 HYBRID \ddagger O\left(\sqrt{kmT}\right) , k\leq\frac{m}{2} None 72.772 O\left((m-k)\sqrt{\log\left(\frac{m}{m-k}\right)T}\right) , k>\frac{m}{2} None None CMOSS O\left((\log k)^{2}\sqrt{kmT}\right) O\left(\frac{(\log k)^{2}}{p^{*}}\sqrt{kmT}\right) 6.706 Table 1: Theoretical regret bounds and empirical computational cost per-round for algorithms on the CMAB problem. \star COMBEXP is from ( Combes et al. 2015 ) . CUCB is from ( Chen, Wang, and Yuan 2013 ; Kveton et al. 2015c ; Liu et al. 2024 ) . EXP3.M is from ( Uchiya, Nakamura, and Kudo 2010 ) . HYBRID is from ( Zimmert, Luo, and Wei 2019 ) . The detailed regret bound of CMOSS is given in Theorem 1 and Theorem 5 . \circ “None” means these methods can not deal with this case. p^{*} denotes the minimal

Read the complete text