Combinatorial Bandits Revisited
This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the adversarial setting under bandit feedback, we propose COMBEXP, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.
The contributions of this paper are threefold:1) For the stochastic combinatorial semi-bandits, the authors have derived a problem-specific lower bound and discussed its scaling.2) For the stochastic combinatorial semi-bandits, the authors have achieved an improved regret bound under some *additional assumptions*.3) For the adversarial combinatorial bandits, the authors have proposed an algorithm with the same regret scaling as the state of the arts, but with lower computational complexity for some problems.To the best of my knowledge, all these contributions are novel and nontrivial, though I have not seen a *fundamentally new* idea in this paper. The authors are quite familiar with the literature and have done a good literature review. I think the paper is ready to be published in NIPS after some appropriate revisions.My major comment is that the authors should position the paper better with respect to some existing literature. In particular, with respect to Kveton et al. 2015 [11], contribution 2) of this paper has achieved better regret bound under some *additional assumptions* (i.e. this paper assumes the rewards are Bernoulli and independent across actions, while [11] does not make these assumptions). The authors should clarify these differences in the next version of this paper. Moreover, since [11] claims that their regret bound is tight, to avoid confusion, the authors should explicitly mention that the particular example [11] used to derive their lower bound does not satisfy the assumptions of this paper.There are some recent papers on combinatorial bandits/semi-bandits, and the authors might consider citing them:http://jmlr.org/proceedings/papers/v40/Neu15.html http://jmlr.org/proceedings/papers/v37/wen15Some minor comments:1) Line 222, \Delta^M should be \Delta_M;2) In equation 2, both M and t(n) are vectors, so Mt(n) is not well defined.