We define a general framework for a large class of combinatorial multi-armed
bandit (CMAB) problems, where subsets of base arms with unknown distributions
form super arms. In each round, a super arm is played and the base arms
contained in the super arm are played and their outcomes are observed. We
further consider the extension in which more based arms could be
probabilistically triggered based on the outcomes of already triggered arms.
The reward of the super arm depends on the outcomes of all played arms, and it
only needs to satisfy two mild assumptions, which allow a large class of
nonlinear reward instances. We assume the availability of an offline
(\alpha,\beta)-approximation oracle that takes the means of the outcome
distributions of arms and outputs a super arm that with probability {\beta}
generates an {\alpha} fraction of the optimal expected reward. The objective of
an online learning algorithm for CMAB is to minimize
(\alpha,\beta)-approximation regret, which is the difference between the
\alpha{\beta} fraction of the expected reward when always playing the optimal
super arm, and the expected reward of playing super arms according to the
algorithm. We provide CUCB algorithm that achieves O(log n)
distribution-dependent regret, where n is the number of rounds played, and we
further provide distribution-independent bounds for a large class of reward
functions. Our regret analysis is tight in that it matches the bound of UCB1
algorithm (up to a constant factor) for the classical MAB problem, and it
significantly improves the regret bound in a earlier paper on combinatorial
bandits with linear rewards. We apply our CMAB framework to two new
applications, probabilistic maximum coverage and social influence maximization,
both having nonlinear reward structures. In particular, application to social
influence maximization requires our extension on probabilistically triggered
arms.

该研究提出了一种通用的组合多臂赌博问题框架，将未知分布的基础臂组成超级臂进行玩耍，进一步探讨了更多可能基于已激发臂的结果触发概率的扩展，旨在通过在线学习算法实现最小化（α，β）- 逼近遗憾。