In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound, where $K$ is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the $O(K)$ factor to $O(\log K)$ or $O(\log^2 K)$ in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on $K$ in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of $O(\log K)$. Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.

本研究探讨组合良带(Bandits)的算法, 针对其大小批次(K)对后悔束缚的依赖性进行优化, 发现一种可替代平滑性条件的新型触发概率和方差调节(TPVM)条件, 进行后悔分析并提出基于置信区间和方差的BCUCB-T算法，将大小批次(K)的项降低至对数级别, 并在非触发CMAB中将其完全去除。实验结果表明, 我们的算法在不同领域具有优越的性能。

概率触发臂或独立臂组合半匪徒问题的无关批量大小的后悔界限