A stochastic combinatorial semi-bandit with linear payoff is a class of sequential learning problems, where at each step a learning agent chooses a subset of ground items subject to some combinatorial constraints, then observes noise-corrupted weights of all chosen items, and receives their sum as payoff. Based on the existing bandit literature, it is relatively straightforward to propose a UCB-like algorithm for this class of problems, which we refer to as CombUCB1. The key advantage of CombUCB1 is its computational efficiency, the method is computationally efficient when the offline variant of the combinatorial optimization problem can be solved efficiently. CombUCB1 has been applied to various problems and it is well established that its $n$-step regret is $O(K^2 L (1 / \Delta) \log n)$, where $L$ is the number of ground items, $K$ is the maximum number of chosen items, and $\Delta$ is the gap between the expected weights of the best and second best solutions. In this work, we derive novel upper bounds on the $n$-step regret of CombUCB1, most notably a $O(K L (1 / \Delta) \log n)$ gap-dependent upper bound and a $O(\sqrt{K L n \log n})$ gap-free upper bound. Both bounds are significant improvements over the state of the art. Moreover, we prove that the $O(K L (1 / \Delta) \log n)$ upper bound is tight by showing that it matches a lower bound up to a constant independent of $K$, $L$, $\Delta$, and $n$; and that the $O(\sqrt{K L n \log n})$ upper bound is "almost tight" by showing that it matches a lower bound up to a factor of $\sqrt{\log n}$.

本研究利用UCB-like算法解决计算和采样高效的随机组合半贝叶斯在线学习问题，并分析了其$n$步遗憾的上界，这里的遗憾是指最优解和次优解之间的预期回报差距。

随机组合半赌博机的紧急遗憾上限