On the Suboptimality  of Thompson Sampling in High Dimensions
Authors: Raymond Zhang
Richard Combes
Venue: NeurIPS 2021 Poster (2021)
Keywords: Combinatorial Bandits
Thompson sampling

Abstract: In this paper we consider Thompson Sampling for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, Thompson Sampling is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions in the Bernoulli distribution setting. We also show that including a fixed amount of forced exploration to Thompson Sampling does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice Thompson Sampling indeed can perform very poorly in some high dimension situations.

On the Suboptimality of Thompson Sampling in High Dimensions
Raymond Zhang
ENS Paris Saclay, Département de Mathématiques, Gif-sur- Yvette, France raymond, peefeees-paiisseeee paris-saclay..F
Richard Combes
Centrale-Supelec, Laboratoire des Signaux et Systèmes (L2S), Gif-sur- France richard. cen
Abstract
In this paper we consider Thompson Sampling (TS) for combinatorial We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions, with Bernoulli distributed rewards and uniform priors. We also show that including fixed amount forced exploration to TS does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice TS indeed can perform very poorly in some high dimensional situations.
Introduction
We consider the problem of combinatorial bandits with semi-bandit feedback. At time = 1,,.... T learner selects decision ætt) X' where X' C. {0, 1 is the set of available decisions. The environment then draws random vector Z(t) E 12d, The learner then observes Y Y()) xxt) @ (t), where @ denotes the Hadamard (elementwise) product. This setting is called semi bandit feedback. We assume that (Z()))22 i.i.d., and that (1),... ..., Za(t) independent and distributed as (t) ~ Bernoulli(e,) for all f,i Then the learner receives reward f(x(t), Z(t)) where f is known function.
The goal to minimize the regret:
T Ef(2, 2(0)) - - 2())
R(T, 0) 7 max
xEX
Initially 9 is unknown to the learner and minimizing regret involves exploring suboptimal decisions just enough in order to identify the optimal decision. For any decision X, define the reward gap
A max [E,( Z(t)) - Ef(x, Z(t)),
zex
which is the amount of regret incurred by choosing æ instead of optimal decision
x² arg max
(())
and Ami = minnex AS the minimal gap. We define m A maxnex Ed (xg maximal decision.
size the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

For this problem, an algorithm which has attracted a lot of interest is Thompson Sampling (TS), which time selects the decision maximizing x ト fzz ((t) where V(t) is random variable distributed as the posterior distribution of ( knowing the information available at time i, which is y())...,, (tt - 1). The prior distribution of can be chosen in various ways, the most natural being a non-informative distribution such as the uniform distribution.
TS is usually computationally simple to implement, for instance when f is linear, since it involves maximizing f over X. Also, for some problem instances it tends to perform well numerically. A particular case of interest is linear combinatorial cemi-bandits where f(r, 0) 0 x so that the reward is a linear function of the decision.
Our contribution. We show that the regret of TS in general does not scale polynomially in the ambient dimension d.
(i) We provide several examples, both for linear and non-linear combinatorial bandits, where the regret of TS does not scale polynomially the dimension (in fact in some cases may scale even faster than exponentially in the dimension). In some cases, we show that one must wait for amount of time greater than (dd)) for TS to perform at least as well as random choice where one simply chooses st() uniformly distributed in X' at every round. Therefore, in high dimensions, in some instances, TS in general can perform strictly worse than random choice for all practically relevant time horizons.
(ii) We show that the minimax regret TSS scales at least as -)(+'=+) so that it is not minimax optimal, as there exists algorithms such as CUCB and ESCB with minimax regret Oppoly (d) V /T(nT)). In fact, in high dimensions, the minimax regret of TS is almost linear.
(iii) We further show that adding forced exploration as an initialization step to TS does not correct the minimax problem, so that this is not an artifact due to initialization.
(iv) Using numerical experiments, show that indeed, for reasonable time horizons, TS performs very poorly in high dimensions in some instances.
We believe that our results highlight two general characteristics of TS. First, TS tends to be much more greedy than optimistic algorithms such as ESCB and CUCB. This greedy behavior explains why the regret of TS is, in some instances, much smaller than that of optimistic algorithms. In fact is sometimes so greedy that it misses the optimal decision. Second, TS tends to be by nature a "risky" algorithm so that its regret exhibits very large fluctuations across runs. In some cases it finds the optimal arm very quickly and with little to no regret, while in other cases it simply misses the optimal decision and performs worse than random choice.
Related work. Combinatorial bandits are generalization of classical bandits studied in [15]. Several asymptotically optimal algorithms are known for classical bandits, including the algorithm of [16],
KL-UCB [4], DMED [12] and TS [20, 13J. Other algorithms include the celebrated UCBI [2]. A large number of algorithms for combinatorial semi-bandits have been proposed, many of which naturally extend algorithms for classical bandits to the combinatorial setting. CUCB [5, 14] is a natural extension of UCBI to the combinatorial setting. ESCB [7. 9] is improvement of CUCB which leverages the independence of rewards between items. AESCB [8] is an approximate version of ESCB with roughly the same performance guarantees and reduced computational complexity. TS for combinatorial bandits was considered in [10, 21, 18]. Also, combinatorial semi bandits are a particular case of structured bandits, for which there exists asymptotically optimal algorithms such as OSSB [6]. Table presents the best known regret upper bounds for CUCB, ESCB and TS. For completeness, we also recall the complete regret upper bound for ESCB as Theorem 9 (Appendix B).
We provide two types of bounds for TS: problem dependent bounds (sometimes called gap-dependent bounds) and minimax bounds (or gap-free bounds). The former involves T, d, m and Amin. while the latter hold for any value of Amin-
An important observation is that all of the known regret upper bounds for TS [10], [21], [18] feature at least one term that does not scale polynomially with the dimension. In particular, the paper [18] shows that there exists a universal constant C 2 0 such that the regret of TS is upper bounded by
R(T) < C [dlm m² (n((/)))/A////mmmm Amin + dmm
m((m² + 1)/ A Ami) )++4m))
This is general bound for all combinatorial sets of interest. The bound has a super exponential term (that does not depend on 7): m((m² + 1)/Aman )+ Regret bounds for CUCB and ESCB do
2

---

Table Algorithms and best known regret bounds.
Algo.
Regret
(i) problem dependent and (ii) mínimax)
CUCB
(i) [dm (I T)/ ( [14][Theorem 4]
(ii) O dmT(In T) + dm) [14][Theorem 6]
ESCB
(i) (d((In mm) / min + dmn / /A [9][Theorem 2] (ii) O( d(In m) ))
dm) [9][Corollary 1]
TS
(i) (()(Ium) In( (T) + dmm/Amin. + mm(m² + 1)/ min) 22tmm)
[18][Theorem 1] (ii) not available
not feature this exponential dependency in the dimension. However, since TS tends to perform very well in all the numerical experiments presented in the literature, a natural intuition would be that all known upper bounds simply not sharp, and that the true regret of TS does not really grow exponentially with the dimension. We show in this work that this intuition is incorrect, and that the regret of 'S really does scale (at least) exponentially in the dimension i.e. it suffers from the "curse of dimensionality". This directly implies that, in high dimensions, and for some combinatorial sets, CUCB and ESCB perform much better than TS.
In order to alleviate this problem, would be natural to attempt to modify the prior distribution used by TS, since it is known to have a strong influence on its performance [3, 17]. Similarly, in a related problem, [1] suggests to use correlated Thompson samples, and [11] studies the influence the prior on numerical performance. We believe that this is interesting open problem.
Prior knowledge to the learner: combinatorial set X' C {0, 1] function f : x [0, 1]dt + R Fort t I.
1. The learner computes statistics A(t) E (()) o x<s) and B(t) Σ x(s)
Z(s) @ xx(s)
2. The learner draws (()) with Vi -. Va(t) independent and Vi(() (eta(A;(1)
1, (,( + +1)
3. The learner chooses decision sr() E arg m (f(x, V()))
4. The environment draws ((t) with Z1 (t), (t(t) independent and (t) ~ Ber(O.)
5. The learner observes Z(t) @ xt)) and receives the reward f(((t), (t))
Performance metric: expected regret R(T,0) 0) = T' ((t))))
ΣT= (tt
Figure 1: TS for combinatorial
with Bernoulli rewards and uniform prior.
Model
2.1 Problem Dependent Regret and Minimax Regret
In order to evaluate the performance of an algorithm over the set of instances [0, 1]d, there are two main figures of merit that study in this paper. The first is the problem-dependent regret which R(T, 8) when [0, 1]d is fixed. The second the minimax regret which the worse case over for T fixed: maxes(o,1y R(T,0)
2.2 TS
The basic TS algorithm works as follows. For i 1, d, define (, Σ'-1 (s(s) and (t = E1=1(1 (s)) which represent the number of successes and failures observed when getting sample to estimate 0,, We define N,(() A.(() + (() Σ (.) the number of samples available at time to estimate 6, and
A²
0,(t)
max (N)
3

---

the corresponding estimate of 8, which is simply the empirical mean.
The TS algorithm selects decision
xxt E arg max sE
+ f(z V(t) where Vi(t) ~ (eta(A,(t)++,, + 1),
and (t) (t) are independent. Vector (t) is called the Thompson sample at time t. TS is based on a Bayesian argument, (tt) is drawn according to the posterior distribution of 8 knowing the information available at time I, where the prior distribution for 0 is uniform over [0, 1]4. Choosing decision æ(t) as done above should ensure that one explores just enough to find the optimal decision. In the linear case, the decision be computed by linear maximization over X':
xxt)) E arg max (t) x}. zEX
This explains the practical appeal of TS, since whenever linear maximization over X' can be imple- mented efficiently, the algorithm has low computational complexity.
2.3 TS with Forced Exploration
natural extension of TS is to add & forced exploration rounds, where is fixed number, in order to avoid some artifacts that could possibly occur due to the prior distribution. The algorithm operates as follows. time S t S l, one selects xxt) E such that Zx(2) (t) with
i(l) min Ni(l).
1= 1=1.....d
Otherwise for 2 + 1 one selects
art) E arg max fax (t)), ZEX
with V(t) the Thompson sample defined above. Namely, one first performs forced exploration during& rounds then apply TS. This guarantees that (t) 2 |e/d] samples are available to estimate 0 for all i I,... d, then one subsequently applies TS. We call this variant TS with é forced exploration rounds.
3
Main Results
We now state our main theoretical results. All proofs are found in the appendix.
3.1 Some Combinatorial Sets of Interest
We will provide several examples of combinatorial where the regret of TS indeed scales exponen- tially with the dimension, so that this phenomenon is quite general and is not an artifact that only occurs for one particular family of combinatorial structures. We define X the set of paths of the directed acyclic graph depicted in figure 2. This set has two disjoint decisions (1,..., 1, 0,... 0) and
(0....,O, 0, 1,..., 1) of equal size m =
d We define nmm the set of matchings of the bipartite graph 2-
depicted in figure 2. This graph has d vertices and edges.
Figure 2: Paths in directed acyclic graph (left) and matchings of the Z graph (right)
The combinatorial sets presented are very simple. However our results can by generalised for more complex set of interest without losing the exponential nature of the regret. For example the two path

---

environment can be generalized to k > 2 paths. It can also be generalized for non disjoint paths if the optimal path does not share "a lot" of edges with all the other paths. This could be the case for real life applications like shortest path routing or in medical trials where treatments cannot be associated with each other. With those simple examples in mind many other more complex sets that exhibit exponential regret can be found. However we do not provide formal proof for those more complex examples as the simple example of paths is sufficient to prove the suboptimality of IS here.
3.2 Linear Combinatorial Bandits
We focus on linear bandits, where the expected reward function is linear i.e. f(x,0)== xx' xx T. For the non linear case see Appendix C. There, we consider non linear problems inspired by [21][The 3). where the Thompson sample of sub-optimal decisions has no variance. One could be lead to think that the exponential dependency of the regret on the dimension could be caused by this feature, and is hence natural to investigate the linear case, which is not only more common, but also where the Thompson sample of any decision always has a non-null variance.
In Theorem we consider a linear problem over the combinatorial set R which is formed of two disjoint paths. We show that the regret of TS does scale exponentially in the dimension for this problem. Therefore this phenomenon is not linked to a particular, well chosen, non- non-linear reward function, but also occurs for the classical case of linear reward functions.
Theorem 1. Consider a linear combinatorial bandit problem over combinatorial set X and param- eter 0, = 1 if S d/2 and 0; =1 otherwise. Assume that m
Then the regret of TS is lower bounded by
A
2m
1 2
A
R(T, 0) 2
4pA (1 - (1 (1- (1-PA)=-)), with PA = exp
Theorem is proven by showing that the first time that the optimal decision is selected is exponentially large in general. The central argument can be summarized as follows. Consider such that times 1.... t only the suboptimal decision has been selected. The probability of selecting the optimal decision is IP Th Vi(t) Ei-m+1 Vi(t) B(t)) where Vttt)..... Va(t) are independent, distributed in [0, 1). and their respective expectations are
if1 S S m,
E (((O)A()), B())
2
Ad0+1 122
mm + 1 S 1 sisk d.
Furthermore, from the law of large numbers, when / is large, Dd >i=++ A:(l) R (1 A ) since we have sampled the sub-optimal decision & times. Therefore D B(V((t))((t) B(t))
and again because t is large, Ei=+4 ((V)))) B(t)) = m A. Since (t) Va(t) are independent and distributed in [0, 1]. their sums must concentrate around their expectation, and from Hoeffding's inequality:
PP
ViO0)
Σ ((())A(), B()) s so -mmml
<0(e-mmit A A1)²) )
where u >> 0 is some positive exponent related to how concentrated the Thompson samples are. This implies that, for large f, the probability of selecting the optimal decision exponentially small if has never been selected previously.
Also, that this phenomenon of lack of exploration by TS is typically high dimensional phenomenon. In short, the Thompson samples of decisions will tend to concentrate around their expectation, so that TS will, most of the time, act greedily and simply select the decision maximizing the empirical reward. We can also emphasize the fact that when m grows, we can have an arbitrary large gap A and still have exponential regret. This is unexpected, since the difficulty of bandit problem is usually a decreasing function of the gap A. Furthermore another version of Theorem I which exhibits exponential behavior can be shown with parameters 0 u if < S d/2 and u no otherwise, under the condition A + 7m < 1 where E] 1]. We chose the parameters of Theorem for the sake of clarity and being at the edge of the parameter space is not necessary condition to have exponential regret.
5

---

3.3 Linear Combinatorial Bandits: Small Gap Regime
Theorem is another regret bound for TS which more accurate in the regime where A is small, allows to deduce lower bound for the minimax regret as well. The proof is a more intricate version of the proof of Theorem highlighted above. Corollary 3 states that the minimax regret of TS scales as ( for T S m!, and least as 12(TI-ā) for T 2 m!. Of course, in practice, when m is large we have T < m! for any reasonable time horizon, so that the regret of TS is linear in this regime. Also, as stated by Corollary 3, TS is provably not minimax optimal, as there exist algorithms with minimax regret scaling at most as O(d//4/T (mTT).
Theorem 2. Consider linear combinatorial bandit problem over combinatorial set XP and param- eter 02 = if1 S S d/2 and 0; = m otherwise.
Then there exists universal constants C2. C3 such that for all To(m) C2m2 Inm, and A < 1/6 and m 2 5, the regret of IS is lower bounded by
(1 (1 -Pa) + C3A (1 94) To (1 94
T-To+1
R(T,0) Z 4p
9a
with
(2A) m m!
2m
1
A
2
and PA exp
9
2
m
Vm
Corollary 3. Consider linear combinatorial bandit problem over combinatorial set X with m 2 5. IfT 2n ml then the minimax regret of TS is lower bounded by
max R(T, 0) 2 CauA @E[0.1]
Otherwise it is lower bounded by
max R(T, 0) 2 C 0E[0,]
with C4, C4 > universal constants.
The minimax regret of ESCB for this set X2 is upper bounded by:
max R(T, 0) S Cgd' VTIT. 0E
with Cs 2 a universal constant. Therefore TS is not minimax optimal.
3.4 Linear Combinatorial Bandits with Forced Exploration
We finally extend our results to show that, even when forced exploration is added, TS still provably incurs regret growing exponentially with the dimension, stated by Theorem 4 and Theorem 5. In particular, if the number of forced exploration rounds satisfies
A
+2
mm
In
3
then Theorem 4 implies that the regret of TS still increases exponentially in m, in spite of the forced exploration added the algorithm. In fact it is impossible happening, unless the learner knows the value of the gap A in advance. Indeed, for any fixed f, the above inequality always holds providing that A small enough.
to prevent exponential regret from
Theorem 4. Consider a linear combinatorial bandit problem over combinatorial set X and param- eter = 1 if Si d/2 and 9; A otherwise.
4+2 the regret of with E forced exploration rounds lower bounded by Then if + vm
R(T,0) 0) 2
(1 - PA) TT1),,), with
4p A
A exp {
Vm )) /1 + 333]
2n
2

---

Theorem 5. Consider a linear combinatorial bandit problem over combinatorial set XP with m 2 5 and parameter 8; = 1 if 1 S 2/2 and 0; = - otherwise.
Then if m! and > (o 1) = CBm² (lm))mm the minimax regret of TS with & forced exploration rounds is lower bounded by
max R(T,0) C) TT- 0E(0.1]=
Otherwise it is bounded by
max R(T,0) 2 C,O(E, T 0E
E with Co. C7, C4 > O universal constants and C such that VE E N, ci C(e, =
4 Numerical Experiments
We now illustrate the exponential regret of TS in practical settings using numerical experiments. Due to this exponential nature, some of those experiments involve a significant amount of computing time in high dimensions. Due to limited space, we solely consider the linear case, which is the most often considered in the literature. Unless specified otherwise we use 1000 independent sample paths for averaging, and 95% confidence intervals are presented on the plots.
First selection of the optimal decision As shown by our theoretical results, the first time that the optimal decision is selected causes exponential regret. On Figure 3, we present the c.d.f. (cumulative distribution function) of T as function of m for combinatorial sets X and n introduced above. The parameter values chosen as in the previous sections 0g- if 1 < i i d/2 and 0g = A otherwise. For each sample path we generate T by simulating TS until the optimal decision played for the first time.
minft 2 x(t) x=] can be exponentially large, and this is what
Some quantiles of r indeed seem to increase exponentially as m grows and for reasonable values of m, can be very large with appreciable probability, for instance on Fig. 3 for = 14, 5 2 5.10 with probability greater than 0.1. Clearly, on sample paths where this happens, TS performs worse than random choice for the first 5. 5. time steps which is surprisingly poor behaviour, especially on such a simple problem. This also showcases the fact that those sample paths happen relatively often. Thus the regret of TS is not only due very rare occasions with high regret but also because of those poor behavior that can happen quite often.
To investigate the impact of the gap A, on Figure 4a and Figure 4b, we p the expected first time for the sets of paths X
the optimal decision is selected B(T) as a function of m for various and matchings X Once again observe exponential growth in both figures, and this growth is particularly fast for small values of ó. When the gap gets small, the exponential growth of regret is exacerbated, leading to even worse performance.
Impact of forced exploration We now investigate if forced exploration alleviates the problem in practice, and consider & forced exploration rounds. On figures 5a and 5b plot the expected first time the optimal decision is selected E(r) as a function of m for various ó = and f, for the sets of paths X As predicted by Theorem 4, EE() still seems scale exponentially in which causes exponential regret.
Theorem 4 states that if é is chosen such that < स then regret scales exponentially, On the other hand one could think that when é is chosen large enough to violate this condition then regret does not grow as rapidly. Figure 5b shows that, at least numerically, this does not appear to be the case, indeed, we choose f = m, and there are values of 5 such that the regret still seem to scale exponentially in m.
Comparison with optimistic algorithms We now compare TS with the state-of the-hhharrt frequentist algorithms ESCB and/or CUCB. These experiments are averaged over 40 sample paths due to computational limits. On figures 6a and 6b we present the regret as a function of m for the set of paths XP, 0.1, T 4. and the set of matchings X A = 0.05, T = 4. respectively. The results show that the regret of TS is larger than that of CUCB and/or ESCB by several orders of magnitude in high dimensions, predicted by our theoretical results. In fact the regret of TS is
7

---

1.0
1.0
0.8
0.8
0.6
0.6
0.2
0.2
0.0
0.0
250
500
750
1000
100000
200000
300000
Topo
Topu
m
6,
A
X'
m
14,
A
5
on A
1.0
1.0
0.8
0.8
0.4
0.4
0.2
0.2
500
1000
1500
50000 100000 150000
on X
6,
on 2m
170
m
Figure 3: C.d.f. of the first time the optimal decision is played function of m for set of paths and matchings X2,, xm
30000
0.4
5 0.150
20000
0.3
0.125
15000
= 0.2
20000
5 0.05
5 0.1
10000
10000
5000
25
50
75
100
125
6
8
10
m
(a) Set of paths X combinatorial set
(b) Set of matchings A combinatorial set
Figure 4: Expectation of the first time the optimal decision is played E(r) as a function of m and various values of A
so overwhelmingly large that, due to the scale of the figure, it looks like the regret of ESCB and/or CUCB does not increase with the dimension (this is of course not case). figures 7a and 7b we perform similar experiments but with smaller gaps, and the same behaviour arises.
Conclusion
We have shown through both theoretical analysis well as numerical experiments that TS can perform very poorly in high dimensions, both for both linear and non linear problems, and for various combinatorial structures such as sets of paths and matchings (one could consider more complex combinatorial set including multiple non disjoint paths). Introducing forced exploration does not alleviate the problem either. Therefore, this not an artifact, but rather general problem. In essence, Thompson performs poorly because it has tendency play much too greedily, and in high dimensions this sometimes leads to a complete lack of exploration and missing the optimal arm. Our work points towards a challenging open problem which is design better TS-like

---

20000
6=0.17,
==
20000
15000
6=0.02,
15000
10000
10000
5000
5000
m
m
(a) Set of paths X combinatorial set
(b) Set of matchings 2 combinatorial set 100
and L = m
Figure 5: Expectation the first time the optimal decision is played E(r) as a function of and various values of 8 and L
25000
ESCB
CUCB
30000
TS
20000
TS
15000
20000
10000
10000
8
8
10
14
(a) 5 = 0.1 and T = 4.10%, Set of paths X
(b) 5 = 0.05 and T = 10 set of matchings X
Figure Regret comparison between ESCB and for of paths X and matching n (Averaged over 40 experiences)
125000
ESCB
25000
CUCB
TS
20000
75000
15000
50000
10000
25000
8
10
5
10
15
m
(a) A and T 4.10 of paths 2
(b) A and 7 10 of matchings n
Figure 7: Regret comparison between ESCB and TS for set of paths X and matching x For fixed A (Averaged over 20 and 40 experiences)
algorithms for regret minimization that deal with high-dimensional problems, while retaining the computational efficiency of TS. Two reasonable ideas to explore would be (i) carefully designing the prior distribution (ii) enforcing forced explorations at regular intervals, possibly in adaptive manner. Also, our work concerns the Bernoulli setting but we believe that our results can be generalized to bounded distributions. is not obvious whether or not our results still hold for Gaussian distributions, and seems like an interesting open problem.

---

References
[1] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Proc. of COLT, 2017.
[2] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3) 226, 2002.
[3] Sébastien Bubeck and Che- Yu Liu. Prior-free and prior-dependent regret bounds for thompson sampling. In Proc. of IEEE CISS, 2014.
[4] O. Cappé, A. Garivier, O. Maillard, R. Munos, and G. Stoltz. Kullback-leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3):516-544 June 2013.
[5] Wei Chen, Yajun Wang, and Yang Yuan, Combinatorial multi-armed bandit: General framework and applications. In Proc. of ICML, 2013.
[6] Richard Combes, Stefan Magureanu, and Alexandre Proutiere, Minimal exploration in structured stochastic bandits. Proc. of NIPS, 2017.
[7] Richard Combes, M. Sadegh Talebi, Alexandre Proutiere, and Mare Lelarge. Combinatorial bandits revisited. In Proc. of NIPS, 2015.
[8] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. Statistically efficient, polynomial-time algorithms for combinatorial semi-bandits. Proc. ACM Meas. Anal. Comput. Syst. 5(1):09:1- 09:31, 2021.
[9] Remy Degenne and Vianney Perchet. Combinatorial semi-bandit with known covariance. In Proc. of NIPS, 2016.
[10] Aditya Gopalan, Shie Mannor, and Yishay Mansour. Thompson sampling for complex online problems. In Proc. of ICML, 2014.
[11) James A. Grant, David S. Leslie, Kevin Glazebrook, Roberto Szechtman, and Adam N. Letch- ford. Adaptive policies for perimeter surveillance problems. Eur. J. Oper. Res., 283(1))2 2020.
[12] Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. In Proc. of COLT, pages 67-79, 01 2010.
[13] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proc. of ALT, 2012.
[14] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Proc. of AISTATS, 2015.
[15] T.L.. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-2, 1985.
[16] Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. Ann, Statist., 15(1)1109111114 09 1987.
[17] Che-Yu Liu and Lihong Li. On the prior sensitivity of thompson sampling. In Proc. of ALT, 2016.
[18) Pierre Perrault, Etienne Boursier, Michal Valko, and Vianney Perchet. Statistical efficiency of thompson sampling for combinatorial semi-bandits. Proc. of NIPS, 2020.
[19] Herbert Robbins. A Remark on Stirling's Formula. The American Mathematical Monthly, 62(1):26, January 1955.
[20] William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
[21] Siwei Wang and Wei Chen. Thompson sampling for combinatorial coni-bandits. In Proc. of ICML, 2018
10


Reviews:
[{"review_id": "wxEqDBBXS5v", "reviewer": "Reviewer_nhUQ", "summary": "This work considers combinatorial semi-bandit problems, and theoretically investigates the sub-obtimality of Thompson sampling in the high-dimensional feature space and empirically shows the poor performance of Thompson sampling compared to other existing approaches such as ESCB and CUCB algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThis work provides novel lower regret bounds for Thompson sampling to show that the minimax regret of Thompson sampling scales almost linearly when high dimensional feature is considered. Also it gives interesting examples for linear and non-linear combinatorial bandits, showing that regret of Thomason sampling scales exponentially in dimension. \n\nQuality:\nTheoretical results sound well-grounded and numerical experiments seem reasonably fair and supportive to this theoretical outcome, which makes a complete piece.\n\nClarity:\nIt was hard to read this submission since theorem and proofs are not clearly separated and it does not provide enough technical details in the proof. Forced exploration part seems redundant in a complete piece of work.\n\nSignificance: \nThis submission only proves the sub-optimality of Thompson sampling approach in combinatorial bandit. Though it left a new challenging open problem “how to design better Thompson-sampling type algorithm to deal with high dimensional features”, the significance of this work is weak without suggesting TS-type algorithm with sub-linear regrets.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned in main review, this submission reports only weakness of Thompson sampling approach in combinatorial bandit in terms of both theoretical and empirical results. It can be a complete piece of work to suggest  TS-type algorithm with sub-linear regrets by handling its greedy property in high dimension. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jjKKyi-Vuq0", "reviewer": "Reviewer_qacF", "summary": "This paper analyzes Thompson Sampling in combinatorial bandits problems and proves two lower bounds that show that in these problems, Thompson Sampling can scale exponentially in the dimension of the problem. In particular, they first construct an instance on which the regret of Thompson Sampling satisfies an instance dependent lower bound that scales exponentially with the dimension. They then show that in a \"min-max\" sense that the regret of TS on this instance can scale almost linearly unlike other optimism-based methods. Furthermore, they show that this sub-optimality is not alleviated by forcing exploration. They conclude with numerical results that verify their findings.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and represents a nice contribution showing that Thompson Sampling in combinatorial bandits is suboptimal with respect to the dimension of the problem. As the authors note, regret bounds for Thompson Sampling often show that it has worse dimension-dependence in problems than optimism based methods, but this is often assumed to be an artifact of the proof. This paper shows that--- in the case of combinatorial bandits---  this is not true and in fact this suboptimal scaling is unavoidable (even if you force exploration). This is a nice and surprising finding which expands on our growing understanding of Thompson Sampling.\n\n\nDetailed Questions:\n\n1. In linear bandits, Thompson Sampling is not yet known to achieve the optimal rate (compared to e.g., optimism based methods), and generally the variance of the posterior is blown up by a constant $\\sqrt{d}$ in order to prove regret bounds (see e.g., [1], [2]). While--- to the best of my knowledge--- this factor has not been shown to be necessary, would scaling the variance similarly solve this scaling problem in combinatorial bandits? This seems to be different than forced exploration analyzed in Section 3.4. \n\n2. How much of this suboptimality comes from a bad modeling decision? In the case of the first instance with two disjoint paths, if one reduced the problem to a two-arm MAB problem and used TS, the suboptimality would disapear. It seems to me like the modeling choice is overcomplicated for this problem and that this is the source of suboptimality while optimism based methods don't have this problem since they are more `black-box'. Is this one way to interpret the  results? The results in this paper are still interesting and relevant because they show the importance of choosing good models in thompson sampling, and the algorithm itself may not be suboptimal, but extremely reliant on simple models.\n\nMinor:\n\n1. There is a broken link to the appendix on line 134.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The point of this paper is to demonstrate the limitations of a popular algorithm in contextual bandit problems. I think the authors should be careful (in e.g., the title) to highlight that they show the limitations of thompson sampling in the combinatorial bandits problems and not more generally.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "Zy9eNQvlXP2", "reviewer": "Reviewer_1SPf", "summary": "This paper shows that the Thompson Sampling (TS) is suboptimal for combinatorial semi-bandits. In particular, they give instances where the regret scales exponentially in the ambient dimension and shows that its minimax regret is nearly linear. They demonstrate this phenomenon theoretically and empirically.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think that the the theoretical and empirical results on the suboptimality of TS are original and surprising. This is significant, as the authors point out, because TS has been analyzed in several recent papers for combinatorial semi-bandits and this suggests that new algorithmic ideas are needed. \n\nThe authors provide a nice empirical study on the suboptimality of TS.\n\nIn the sketch of the proof following Theorem 1, the authors provide intuition on the large t regime at which point the law of large numbers kicks in. It would be useful to explain in addition why TS does not sample the best decision with sufficiently large probability in the small t regime.  This seems to be a gap currently in the proof sketch.\n\nI think it would be useful if they provided a regret bound for ESCB for Theorem 1 to emphasize that there exists an algorithm whose regret does not scale exponentially in the ambient dimension.\n\nIn section 3.4, the authors write that the learner would need to know the value of the gap in advance to set l. But, could one use the doubling trick, as well as perhaps a confidence bound? \n\nOne limitation of the current paper is that they do not give any positive results. It would be really nice if they could modify TS in a way that avoids this poor scaling in the dimension, even if this were just a partial result. I think that this would make the paper considerably stronger.\n\nAfter rebuttal: I found the authors' response convincing, and have increased my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not comment on the potential negative societal impact of their work. I think the paper is mainly theoretical. Algorithms for combinatorial semibandits could be used for applications with either positive societal impact or negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Q0M5FxQzdhZ", "reviewer": "Reviewer_dwfb", "summary": "This paper focusses on Thompson Sampling for stochastic combinatorial semibandits. The main contributions of the paper are to formalise conditions under which Thompson Sampling does not behave optimally for these problems. Through per-instance and minimax analyses, the authors show that when Thompson Sampling is deployed for Bernoulli combinatorial semibandits, and is initialised with a uniform (Beta(1,1)) prior there exist particular action sets and underlying parameters of the reward distribution such that the regret grows sub-optimally. In particular the regret can be shown to be lower bounded by a function that is exponential in the number of arms, or linear in the time horizon for small enough (but potentially still large) time horizons. An empirical investigation ratifies these findings and demonstrates that this issue is not encountered by optimistic algorithms such as ESCB and CUCB.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I feel there is a solid piece of theoretical analysis underpinning this work, and that the experimental work has been thoughtfully conducted, resulting in a paper which does a good job of investigating an interesting phenomenon. I believe this a useful finding, of genuine interest to the NeurIPS community. However, I do also feel that there are some issues which should be addressed to improve the paper. These are discussed in more detail below, but principally concern the dependence of the results on a particular choice of prior and construction of the action set, and the presentation of the proofs of Theorem 2 and Corollary 3.\n\nORIGINALITY: The paper presents new and interesting theoretical results. The key result underpinning these is a lower bound (in terms of a horizon T) on the probability of not selecting the optimal action within T rounds, when playing the particular combinatorial problem with action set X^p introduced in section 3. This result is as far as I am aware new, and correct. I feel that it tells us something concrete about Thompson Sampling that we, as a community, only had intuition- or simulation-based evidence for previously, and thus I am happy that this paper clears the bar for originality.\n\nQUALITY: The writing and the research is generally of a high quality. The introductory text displays a good combination of concise mathematics and a clear statement of the main ideas of the paper. The quality of the writing drops somewhat in the proofs – at points reaching a minimal level of detail. In particular in the proofs of Theorem 2 and Corollary 3 (and the results in a similar style to these) there are a couple of key points that are not as clear as they could be due to this succinct writing style. I feel the proof would be improved if the authors could add detail to clarify the following points: Q1: In line 535, in what sense is the constant C_2 universal? In that it does not depend on \\Delta? Or  T? or m? It seems that a dependence on m at least is inevitable? Seeing as the final bounds include dependence on m should this not be stated? Q2: In line 536, how does the bound on P(B_T) follow from a bound on P(B_T|\\bar{A})? This is not discussed.  Q3: Similarly to Q1, on line 539, is C_3 also a universal constant, and what is its dependence on m, via both T_0 and C_2? Further, statements such as that on line 534 would be much more user friendly if they referenced a particular equation rather than using a phrase such as “We showed previously”. \n\nI wish to praise the quality of the experimental section. I feel that the authors have chosen sensible experiments to usefully interface with the theory presented.\n\nCLARITY: As above, the clarity of the writing is generally clear, dropping somewhat in the appendices – I would react positively to a general attempt to include more detail throughout the proofs to aid the less senior reader. An issue I do have, that best falls under the heading of clarity is the context in which the results have been presented. I feel that the generality of the results is tending towards being oversold. The tone of the first few sections suggests that a general issue with Thompson Sampling as a principle which may apply widely across combinatorial bandits has been identified. I feel this is stretching the contribution somewhat and downplaying the nature of the results which to me represent the identification of pathological cases. I wish to make clear that I have no issue with the presentation of such results, and no issue with the acceptance of such results to NeurIPS. However, I think it is important to make clear(er) from the outset that these results apply to a) Thompson Sampling with the uniform prior, and b) are only verified for a particular formulation of the action set – which the informed reader may well observe could be more parsimoniously represented as a 2-armed bandit with rewards in the discrete set {0,1,…,m}, where, from what I can see, a traditional instantiation of Thompson Sampling would not inherit this suboptimal performance? I would like to see a commitment to a more transparent framing of these issues – particular the issue around the choice of prior, which I think is an important consideration. I am aware of at least one study (Grant et al, 2020 – Adaptive Policies for Perimeter Surveillance) which investigates empirically the effect of the prior on Thompson Sampling in an instance of a combinatorial bandit, and a number considering the effect of the prior in more classic multi-armed bandit settings (Bubeck and Liu, 2014 – Prior-free and Prior-dependent regret bounds for Thompson Sampling, Liu and Li, 2015 - On the Prior Sensitivity of Thompson Sampling) which may be useful references in speculating as to the effect of the prior. My particular suspicion is that a more 'optimistic' prior may alleviate the suboptimal performance.\n\nSIGNFICANCE: I think this is paper provides a set of useful observations around the performance of Thompson Sampling on combinatorial bandits, and modulo some achievable improvements to the presentation of the results certainly significant and interesting to the NeurIPS community. The authors may wish to add a more extensive history in terms of the observation of the undesirable phenomenon, noting that (Agrawal et al, 2017 – ‘Thompson Sampling for the MNL-bandit’) already propose a fix to the issue through using correlated Thompson samples to increase the probability of exploration in a very closely related problem.\n\n\nMISC: Finally, I would suggest that a thorough copy-edit be conducted prior to upload of any final version as I found a number of grammatical errors (e.g. line 110 – should be ‘performs’, line 230 should be ‘occasions’, line 267 should be ‘concerns’, Fig 1 pt 5 – should be ‘receives’, line 541 is not a sentence incorporated properly in to the text), and typos (e.g. line 134 – referencing issue, Figs 6 and 7 – should be X^p in part (a)s, line 535 – spacing between equations needed), and places where resizing of nested parentheses would aid the reading (e.g. lines 147, 185, and 204).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have considered this.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has received mixed reviews in the first round, but the author response has successfully addressed the concerns of the reviewers. After some internal discussion, the reviewers all agreed that the paper offers a strong and interesting contribution and should thus be accepted for publication at the conference.
Decision: Accept (Poster)