This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting, we first derive problem-specific regret lower bounds, and analyze how these bounds scale with the dimension of the decision space. We then propose COMBUCB, algorithms that efficiently exploit the combinatorial structure of the problem, and derive finite-time upper bound on their regrets. These bounds improve over regret upper bounds of existing algorithms, and we show numerically thatCOMBUCB significantly outperforms any other algorithm. In the adversarial setting, we propose two simple algorithms, namely COMBEXP-1 and COMBEXP-2 for semi-bandit and bandit feedback, respectively. Their regrets have similar scaling as state-of-the-art algorithms, in spite of the simplicity of their implementation.

本文研究了随机和对抗性组合多臂赌博问题。在随机情况下，我们提出了一种特定问题的遗憾下限，并讨论了其与决策空间维数的比例关系。我们提出了ESCB算法，该算法能有效地利用问题的结构，并对其遗憾进行了有限时间分析。ESCB具有比现有算法更好的性能保证，并在实践中显着优于这些算法。在对抗性情况下，我们提出了CombEXP算法，其遗憾比比现有最先进算法相同，但对于某些组合问题具有较低的计算复杂度。

组合赌博机再审