On the Suboptimality of Thompson Sampling in High Dimensions
Year: 2022

Abstract:
In this paper we consider Thompson Sampling (TS) for combinatorial semi-bandits. 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 a fixed amount of 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.

heading: 1 Introduction
text: We consider the problem of combinatorial bandits with semi-bandit feedback. At time t = 1, , ..., T a learner selects a decision x(t) ∈ X where X ⊂ {0, 1}d is the set of available decisions. The environment then draws a random vector Z(t) ∈ Rd. The learner then observes Y (t) = x(t) Z(t), where denotes the Hadamard (elementwise) product. This setting is called semi bandit feedback. We assume that (Z(t))t≥1 are i.i.d., and that Z1(t), ..., Zd(t) are independent and distributed as Zi(t) ∼ Bernoulli(θi) for all t,i. Then the learner receives a reward f(x(t), Z(t)) where f is a known function.
The goal is to minimize the regret:
R(T, θ) = T max x∈X
{ Ef(x, Z(t)) } − T∑ t=1 Ef(x(t), Z(t)).
Initially θ 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 ∈ X , define the reward gap
∆x = max x∈X {Ef(x, Z(t))} − Ef(x, Z(t)),
which is the amount of regret incurred by choosing x instead of an optimal decision
x? ∈ arg max x∈X
{ Ef(x, Z(t)) } ,
and ∆min = minx∈X :∆x>0 ∆x the minimal gap. We define m , maxx∈X ∑d i=1 |xi| the size of the maximal decision.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
For this problem, an algorithm which has attracted a lot of interest is Thompson Sampling (TS), which at time t selects the decision maximizing x 7→ f(x, V (t)) where V (t) is a random variable distributed as the posterior distribution of θ knowing the information available at time t, which is Y (1), ..., Y (t− 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 semi-bandits where f(x, θ) = θ>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 in the dimension d (in fact in some cases it may scale even faster than exponentially in the dimension). In some cases, we show that one must wait for an amount of time greater than Ω(dd) for TS to perform at least as well as random choice where one simply chooses x(t) 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 of TS scales at least as Ω(T 1− 1 d ) so that it is not minimax optimal, as there exists algorithms such as CUCB and ESCB with minimax regret O(poly(d) √ T (lnT )). 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, we 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 it 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 a 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, 13]. Other algorithms include the celebrated UCB1 [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 UCB1 to the combinatorial setting. ESCB [7, 9] is an 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 1 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 ∆min, while the latter hold for any value of ∆min.
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 ≥ 0 such that the regret of TS is upper bounded by
R(T ) ≤ C [ d(lnm)2 ln(|X |T )/∆min + dm3/∆2min +m((m2 + 1)/∆min)2+4m) ] .
This is a general bound for all combinatorial sets of interest. The bound has a super exponential term (that does not depend on T ) : m((m2 + 1)/∆min)2+4m). Regret bounds for CUCB and ESCB do
not feature this exponential dependency in the dimension. However, since TS tends to perform very well in all of the numerical experiments presented in the literature, a natural intuition would be that all known upper bounds are 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 TS 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, it 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 of the prior on numerical performance. We believe that this is an interesting open problem.

heading: 2 Model

heading: 2.1 Problem Dependent Regret and Minimax Regret
text: 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 we study in this paper. The first is the problem-dependent regret which is R(T, θ) when θ ∈ [0, 1]d is fixed. The second is the minimax regret which is the worse case over θ for T fixed: maxθ∈[0,1]d R(T, θ).

heading: 2.2 TS
text: The basic TS algorithm works as follows. For i = 1, ..., d, define Ai(t) = ∑t−1 s=1 Zi(s)xi(s) and
Bi(t) = ∑t−1 s=1(1 − Zi(s))xi(s) which represent the number of successes and failures observed
when getting a sample to estimate θi. We define Ni(t) = Ai(t) +Bi(t) = ∑t−1 s=1 xi(s) the number of samples available at time t to estimate θi, and
θ̂i(t) = Ai(t)
max(Ni(t), 1) ,
the corresponding estimate of θi which is simply the empirical mean.
The TS algorithm selects decision
x(t) ∈ arg max x∈X f(x, V (t)) where Vi(t) ∼ Beta(Ai(t) + 1, Bi(t) + 1),
and V1(t), ..., Vd(t) are independent. Vector V (t) is called the Thompson sample at time t. TS is based on a Bayesian argument, V (t) is drawn according to the posterior distribution of θ knowing the information available at time t, where the prior distribution for θ is uniform over [0, 1]d. Choosing decision x(t) as done above should ensure that one explores just enough to find the optimal decision. In the linear case, the decision can be computed by linear maximization over X :
x(t) ∈ arg max x∈X {V (t)>x}.
This explains the practical appeal of TS, since whenever linear maximization over X can be implemented efficiently, the algorithm has low computational complexity.

heading: 2.3 TS with Forced Exploration
text: A natural extension of TS is to add ` forced exploration rounds, where ` is a fixed number, in order to avoid some artifacts that could possibly occur due to the prior distribution. The algorithm operates as follows. At time 1 ≤ t ≤ `, one selects x(t) ∈ X such that xi(t)(t) = 1 with
i(t) ∈ min i=1,...,d Ni(t).
Otherwise for t ≥ `+ 1 one selects x(t) ∈ arg max
x∈X f(x, V (t)),
with V (t) the Thompson sample defined above. Namely, one first performs a forced exploration during ` rounds then apply TS. This guarantees that Ni(t) ≥ b`/dc samples are available to estimate θi for all i = 1, ..., d, then one subsequently applies TS. We call this variant TS with ` forced exploration rounds.

heading: 3 Main Results
text: We now state our main theoretical results. All proofs are found in the appendix.

heading: 3.1 Some Combinatorial Sets of Interest
text: We will provide several examples of combinatorial sets where the regret of TS indeed scales exponentially 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 p 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, ..., 0, 1, ..., 1) of equal size m = d2 . We define X
m the set of matchings of the bipartite graph depicted in figure 2. This graph has d vertices and d edges.
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 TS here.

heading: 3.2 Linear Combinatorial Bandits
text: We focus on linear bandits, where the expected reward function is linear i.e. f(x, θ) = x>θ. For the non linear case see Appendix C. There, we consider non linear problems inspired by [21][Theorem 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 it 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 1 we consider a linear problem over the combinatorial set X p 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-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 p and parameter θi = 1 if 1 ≤ i ≤ d/2 and θi = 1− ∆m otherwise. Assume that ∆ m + 1√ m < 12 .
Then the regret of TS is lower bounded by
R(T, θ) ≥ ∆ 4p∆ (1− (1− p∆)T−1), with p∆ = exp
{ −2m
9
( 1
2 − ( ∆ m + 1√ m )
)2} .
Theorem 1 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 t such that at times 1, ..., t only the suboptimal decision has been selected. The probability of selecting the optimal decision is P (∑m i=1 Vi(t) ≥ ∑d i=m+1 Vi(t)|A(t), B(t) ) where V1(t), ..., Vd(t) are independent,
distributed in [0, 1], and their respective expectations are
E ( Vi(t)|A(t), B(t) ) = { 1 2 , if 1 ≤ i ≤ m, Ai(t)+1 t+2 , if m+ 1 ≤ i ≤ d.
Furthermore, from the law of large numbers, when t is large, ∑d i=m+1Ai(t) ≈ (1− ∆ m )t since we
have sampled the sub-optimal decision t times. Therefore ∑m i=1 E(Vi(t)|A(t), B(t)) = m 2 and again
because t is large, ∑d i=m+1 E(Vi(t)|A(t), B(t)) ≈ m−∆. Since V1(t), ..., Vd(t) are independent and distributed in [0, 1], their sums must concentrate around their expectation, and from Hoeffding’s inequality:
P ( m∑ i=1 Vi(t) ≥ d∑ i=m+1 Vi(t)|A(t), B(t) ) ≤ O ( e−um(( 1 2− ∆ m )) 2 ) ,
where u > 0 is some positive exponent related to how concentrated the Thompson samples are. This implies that, for large t, the probability of selecting the optimal decision is exponentially small if it has never been selected previously.
Also, we see that this phenomenon of lack of exploration by TS is a 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 ∆ and still have exponential regret. This is unexpected, since the difficulty of a bandit problem is usually a decreasing function of the gap ∆. Furthermore another version of Theorem 1 which exhibits exponential behavior can be shown with parameters θi = u if 1 ≤ i ≤ d/2 and θi = u − ∆m otherwise, under the condition ∆ m + 1√ m < u − 12 where u ∈] 1 2 , 1]. We chose the parameters of Theorem 1 for the sake of clarity and being at the edge of the parameter space is not a necessary condition to have exponential regret.

heading: 3.3 Linear Combinatorial Bandits: Small Gap Regime
text: Theorem 2 is another regret bound for TS which is more accurate in the regime where ∆ is small, it allows to deduce a lower bound for the minimax regret as well. The proof is a more intricate version of the proof of Theorem 1 highlighted above. Corollary 3 states that the minimax regret of TS scales as O(T ) for T ≤ m!, and at least as Ω(T 1− 2d ) for T ≥ 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(d1/4 √ T lnT ).
Theorem 2. Consider a linear combinatorial bandit problem over combinatorial set X p and parameter θi = 1 if 1 ≤ i ≤ d/2 and θi = 1− ∆m otherwise.
Then there exists universal constants C2, C3 such that for all T ≥ T0(m) ≡ C2m2 lnm, and ∆ ≤ 1/6 and m ≥ 5, the regret of TS is lower bounded by
R(T, θ) ≥ ∆ 4p∆
(1− (1− p∆)T0−1) + C3∆ (1− g∆)T0 − (1− g∆)T−T0+1
g∆
with
g∆ = (2∆)
m
m! and p∆ = exp
{ −2m
9
[ 1 2 − ( ∆ m + 1√ m )]2} Corollary 3. Consider a linear combinatorial bandit problem over combinatorial setX p withm ≥ 5. If T > 2mm! then the minimax regret of TS is lower bounded by
max θ∈[0,1]d
R(T, θ) ≥ C4mT 1− 2 d
Otherwise it is lower bounded by
max θ∈[0,1]d
R(T, θ) ≥ C ′4T
with C4, C ′4 > 0 universal constants.
The minimax regret of ESCB for this set X p is upper bounded by:
max θ∈[0,1]d
R(T, θ) ≤ C5d 1 4 √ T lnT .
with C5 ≥ 0 a universal constant. Therefore TS is not minimax optimal.

heading: 3.4 Linear Combinatorial Bandits with Forced Exploration
text: We finally extend our results to show that, even when forced exploration is added, TS still provably incurs a regret growing exponentially with the dimension, as stated by Theorem 4 and Theorem 5. In particular, if the number of forced exploration rounds ` satisfies
ln
( 1
1− ∆m
) ≤ 2 ( 1 ` 2 +2 − ( ∆m + 1√ m ) )2
( `2 + 3) 2 ` 2
then Theorem 4 implies that the regret of TS still increases exponentially in m, in spite of the forced exploration added to the algorithm. In fact it is impossible to set ` to prevent exponential regret from happening, unless the learner knows the value of the gap ∆ in advance. Indeed, for any fixed `, the above inequality always holds providing that ∆ is small enough. Theorem 4. Consider a linear combinatorial bandit problem over combinatorial set X p and parameter θi = 1 if 1 ≤ i ≤ d/2 and θi = 1− ∆m otherwise.
Then if ∆m + 1√ m < 1` 2 +2 the regret of TS with ` forced exploration rounds is lower bounded by
R(T, θ) ≥ (1− ∆ m ) m` 2 ∆ 4p`∆ (1− (1− p`∆)T−1), with
p`∆ = exp { − 2m ( 1 ` 2 + 2 − ( ∆ m + 1√ m ) )2 /( ` 2 + 3)2 } .
Theorem 5. Consider a linear combinatorial bandit problem over combinatorial set X p with m ≥ 5 and parameter θi = 1 if 1 ≤ i ≤ d/2 and θi = 1− ∆m otherwise.
Then if T > 4mm! and T > T0(m, l) ≡ C6m2(lnm)` 1 1 4 − 1 m the minimax regret of TS with ` forced exploration rounds is lower bounded by
max θ∈[0,1]d
R(T, θ) ≥ C7C(`,m) m
` T 1− 1 m .
Otherwise it is bounded by
max θ∈[0,1]d
R(T, θ) ≥ C ′7C(`,m) T
` .
with C6, C7, C ′7 > 0 universal constants and C such that ∀` ∈ N, limm→∞ C(`,m) = 1

heading: 4 Numerical Experiments
text: 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 τ = min{t ≥ 1 : x(t) = x?} can be exponentially large, and this is what causes exponential regret. On Figure 3, we present the c.d.f. (cumulative distribution function) of τ as a function of m for combinatorial sets X p and Xm introduced above. The parameter values are chosen as in the previous sections θi = 1 if 1 ≤ i ≤ d/2 and θi = ∆m otherwise. For each sample path we generate τ by simulating TS until the optimal decision is played for the first time.
Some quantiles of τ 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 m = 14, τ ≥ 5.104 with probability greater than 0.1. Clearly, on sample paths where this happens, TS performs worse than random choice for the first 5.104 time steps which is a 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 to 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 ∆, on Figure 4a and Figure 4b, we plot the expected first time the optimal decision is selected E(τ) as a function of m for various δ = ∆m , for the sets of paths X p and matchings Xm. Once again we observe an 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 an 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 we plot the expected first time the optimal decision is selected E(τ) as a function of m for various δ = ∆m and `, for the sets of paths X p. As predicted by Theorem 4, E(τ) still seems to scale exponentially in m which causes exponential regret.
Theorem 4 states that if ` is chosen such that ∆m < 2 `+1 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 ` = m, and there are values of δ such that the regret still seem to scale exponentially in m.
Comparison with optimistic algorithms We now compare TS with the state-of-the-art 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 X p, ∆m = 0.1, T = 4.10 4 and the set of matchings Xm, ∆m = 0.05, T = 4.10 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, as predicted by our theoretical results. In fact the regret of TS is
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 the case). On figures 7a and 7b we perform similar experiments but with smaller gaps, ∆m = 1 m and the same behaviour arises.

heading: 5 Conclusion
text: We have shown through both theoretical analysis as 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 is not an artifact, but rather a general problem. In essence, Thompson performs poorly because it has a tendency to 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 new challenging open problem which is to design better TS-like
algorithms for regret minimization that can 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 an adaptive manner. Also, our work concerns the Bernoulli setting but we believe that our results can be generalized to bounded distributions. It is not obvious whether or not our results still hold for Gaussian distributions, and seems like an interesting open problem.

Review summaries:
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.

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.  

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.