Summary
This paper addresses Thompson Sampling for stochastic combinatorial bandits with sub-Gaussian rewards. In this area, previous work has identified the interesting phenomenon that some versions of Thompson sampling incur a per-instance regret which is exponential in the (maximum) number of arms pulled per round, m. This is not experienced by UCB-style algorithms, although those tend to have a worse computational complexity.
This paper furthers the discussion around the performance of TS in combinatorial bandits by identifying a variant which incurs only polynomial dependence on m. This is achieved by using a distribution with inflated variance to draw Thompson samples, rather than the 'true' posterior.
The paper contains non-trivial theoretical work to derive this bound, and contains an experiment demonstrating the superiority of the new TS approach over 'natural' variants and its comparable performance to ESCB, a state-of-the-art UCB-based algorithm.
Strengths
I find the research questions considered in this paper very interesting, and think that the multi-armed bandits community at NeurIPS will value this work. Thompson Sampling is a very popular algorithm for all kinds of bandit problems, and the fact that its most natural extension to combinatorial bandits has poor performance is an important issue. The theoretical results in this paper meaningfully contribute to the understanding of where 'natural' Thompson sampling is necessary and where it is only 'some notion of adding randomness' that is needed.
The theoretical work is based on state-of-the-art tools, does include some novel steps and is likely to be of its own interest. It does not appear to be a routine translation of existing tools.
The paper is mostly well-written and clear, and for someone acquainted with combinatorial bandits it is quite easy to follow.
Weaknesses
The main weakness of the paper is that more could be done to articulate exactly where the results improve over existing bounds. The exponential and polynomial dependence on m is, as the paper states, in the constant order (wrt T) term. The main comparison between the results of the present paper and [18] is in terms of order results, and some constants are potentially large. It leaves the reader uncertain as to where in the space of T, m and d, the bound of this paper improves upon the bound of [18]. Adding some clarity around this would improve the paper, and help to establish the extent of its contribution.
There are some further points where I feel clarification could be made around theoretical and experimental results. I ask questions about these in the section below, and they are also central to me assessing the extent of the contribution.
There are some parts where the explanations are probably a bit too brief to be accessible to those without expert knowledge of the field - e.g. lines 52-64 discussing related literature use undefined technical terminology and discuss papers very quickly.
Questions
1. For which values of m and T specifically does the bound of this paper improve upon the bound in [18]? I appreciate this is problem dependent, but if this could at least be answered for the example considered in the experiments, that would be beneficial.
2. The situation in the experiments seems as though it could also be tackled by a 2-armed bandit policy that receives full-bandit feedback on [0,d/2] and essentially ignores the combinatorial structure. If those rewards were scaled to [0,1] would the combinatorial algorithms be outperformed by algorithms for 2-armed bandits?
3. When introducing B-CTS and G-CTS could you make clear if these are the variants to which the results of [18] and [22] apply?
4. The conclusion that using a mismatched variance term outperforms the natural variance is an interesting one, and seems to mirror some findings in the bandit literature that randomisation strategies that are not TS-like or based on a posterior distribution (explicitly) can perform well in bandit problems (e.g. Perturbed History Exploration and bootstrapping based approaches, Kveton et al. (2019) and subsequent work). Can you comment on whether this polynomial dependence relies on using something close to the posterior, or whether other randomisation strategies would seem to be sensible candidates?
5. Can you add to section 5 some clarity on what steps are novel and what are inspired by previous theoretical work? Some of the construction of a clear run seems to bear resemblance to (now) classic proofs for Thompson sampling (Agrawal and Goyal (2012), Kaufmann et al (2012), etc.) and the idea of using sample paths may have roots in other work too? (I'm not certain on that)
Agrawal and Goyal (2012) http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf
Kaufmann et al (2012) https://arxiv.org/pdf/1205.4217
Kveton, Szepesvari, et al. (2019) https://arxiv.org/abs/1902.10089