Parallelizing Thompson Sampling
Authors: amin karbasi
Vahab Mirrokni
Mohammad Shadravan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Thompson Sampling
Bandit
Batch
Exploration
Exploitation

Abstract: How can we make use of information parallelism in online decision-making problems while efficiently balancing the exploration-exploitation trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision-making problems with partial feedback, namely,  stochastic multi-arm bandit and linear contextual bandit. Over a time horizon $T$,  our batch Thompson Sampling policy achieves the same  (asymptotic) regret bound of a fully sequential one while carrying out only   $O(\log T)$ batch queries.  To achieve this exponential reduction, i.e., reducing the number of interactions from $T$ to $O(\log T)$, our batch policy dynamically determines the duration of each batch in order to balance the exploration-exploitation trade-off. We also demonstrate experimentally that dynamic batch allocation outperforms natural baselines. 

Parallelizing Thompson Sampling
Amin Karbasi
Vahab Mirrokni
Mohammad Shadravan
Yale University
Google Research mirr cirrokniien mirrokni@google... com
Yale University mohammad wwaaaaaaaaaaaaaaaae.a.aaaaaaaaae edu
amin.karbas @eale.aalllele.. edu
Abstract
How can we make use of information parallelism in online decision making prob- lems while efficiently balancing the exploration-exploitaiie trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision making problems, namely, stochastic multi-arm bandit and lin- ear contextual bandit with finitely many arms. Over a time horizon T, our batch Thompson Sampling policy achieves the same (asymptotic) regret bound of fully sequential one while carrying out only Ollog 7') batch queries. To achieve this ex- ponential reduction, i.e., reducing the number of interactions from T to O(log T). our batch policy dynamically determines the duration of each batch in order to bal- ance the explorationeexlliittion trade-off. We also demonstrate experimentally that dynamic batch allocation dramatically outperforms natural basclines such as static batch allocations.
Introduction
Many problems in machine learning and artificial intelligence are sequential in nature and require making decisions over long period of time and under uncertainty. Examples include A/B testing [Graepel et al., 2010), hyppe-parameterr tuning (Kandasamy et al., 2018], adaptive experimental design [Berry and Fristedt, 1985], ad placement [Schwartz. et al., 2017], clinical trials [Villar et al., 2015], and recommender systems [Kawale et al., 2015], to name a few. Bandit problems provide simple yet expressive view of sequential decision making with uncertainty. In such problems, repeated game between a learner and the environment is played where at each round the learner selects action, called an arm, and then the environment reveals the reward. The goal of the learner to maximize the accumulated reward over a horizon T. The main challenge faced by the learner is that the environment is unknown, and thus the learner has to follow policy that identifies an efficient trade-off between the exploration (i.e., trying new actions) and exploitation (i.e., choosing among the known actions). A common way measure the performance of policy through regret, a game-theoretic notion, which is defined as the difference between the reward accumulated by the policy and that of the best fixed action in hindsight.
We say that a policy has no regret, if its regret growth-rate as a function o' sub-linear. There has been a large body of work aiming to develop no-regret policies for wide range of bandit problems (for a comprehensive overview, see [Lattimore and Szepesvári, 2020, Bubeck and Cesa Desa-Bianchi, 2012, Slivkins, 2019]). However, almost all the existing policies are fully sequential in nature, meaning that once an action is executed the reward immediately observed by the learner and can be incorporated to make the subsequent decisions. In practice however, it is often more preferable (and sometimes the only way) to explore many actions parallel, so called batch of actions, in order gain more information about the environment in timely fashion. For instance, in clinical trials, a phase of medical treatment is often carried out on a group of individuals and the results are gathered for the entire group the end of the phase. Based on the collected information, the treatment for the subsequent phases are devised [Perchet et al., 2016). Similarly, in marketing campaign, the response line of products not collected in fully sequential manner, instead, a batch of products are mailed to subset of costumers and their feedback is gathered collectively
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

[Schwartz et al., 2017]. Note that developing no-regret policy is impossible without any infor- mation exchange about the carried out actions and obtained rewards. Thus, the main challenge in developing a batch policy is to balance between how many actions run in parallel (i.e., batch size) versus how frequently to share information (i.e., number of batches), At one end of the spectrum lie the fully sequential no-regret bandit policies where the batch size is and the number of batches is T. At the other end of the spectrum lie the fully parallel policies where the batch size is 7 and all the actions are completely determined priory without any amount of information exchange (such policies clearly suffer a linear regret).
In this paper, we investigate the sweet spot between the batch size and the corresponding regret in the context of Thompson Sampling (TS). More precisely,
For the stochastic N N-armed bandit, we develop Batch Thomson Sampling (B-TS), a batch version of the vanilla Thomson Sampling policy, that achieves the problem-dependent asymptotic optimal regret with O(N log T) batches. B-TS policy with the same number of batches also achieves the problem independent regret bound of O( D(VNT)) log T" with Beta priors, and a slightly improved regret bound of O(vNTlog N) with Gaussian priors.
For the stochastic N-armed bandit, we develop Batch Minimax Optimal Thompson Sam- pling (B-MOTS), batch Thompson Sampling policy that achieves the optimal minimax problem-indepennden regret bound of O(v with O(N log T) batches. We also present B-MOTS-J, a variant of B-MOTS, designed for Gaussian rewards, which achieves both minimax and asymptotic optimality with (LN log(T")) batches.
Finally, for the linear contextual bandit with N arms, we develop Batch Thompson Sam- pling for Contextual Bandits (B-TS-C) that achieves the wroblem-independenn regret bound of ((d/2 with ONN lTg( batches.
The main idea that allows our batch policy to achieve near-optimal regret guarantees while reducing the number of sequential interactions with the environment from T to Ollog 7)) is a novel dynamic batch mechanism that determines the duration of each batch based on an offline estimation of the regret accumulated during that phase. We also observe empirically that batch Thompson Sampling methods with fixed batch size, but equal number of batches, incur higher regrets.
2 Related Work
In this paper, we mainly focus Thompson Sampling (also known as posterior sampling and prob- ability matching), the earliest principled way for managing the exploration-explotaaiie sequential decision making problems [Thompson, 1933, Russo et al., 2017]. There has been a recent surge in understanding the theoretical guarantees of Thompson Sampling due to its strong empirical evidence and simple implementation [Chapelle and Li, 2011]. In particular, for the stochastic multi- armed bandit problem, Agrawal and Goyal [2012] proved a problem-dependemt logarithmic bound on expected regret of Thompson Sampling which was then showed to be asymptotically optimal [Kaufmann et al., 2012]. Subsequently. Agrawal and Goyal [2017] provided problem -iddependent (i.e., worst-case) regret bound of O(VNT T' on the expected regret when using Beta priors. In- terestingly. the expected regret can be improved to O(VNT Tog N) by using Gaussian priors. Very recently, Jin et al. [2020] developed Minimax Optimal Thompson Sampling (MOTS), a variant of Thompson Sampling that achieves the minimax optimal regret of (VVNT). Agrawal and Goyal [2013b] also extended the analysis of multi-armed Thompson Sampling to the linear contextual set- ting and proved regret bound of ((d3/2 VT) where d is the dimension of the context vectors. In this paper, we develop the first variants of Batch Thompson Sampling that achieve the aforemen- tioned regret bounds (predlem-dependent and problem-independee independent versions) while reducing the sequential interaction with the environment from T to ONN log 7)), thus increasing the efficiency of running Thompson Sampling by exponential factor (for fixed N).
trade-off in
There has been a large body of work and numerous algorithms for regret minimization of multi- armed bandit problems, including upper confidence bound (UCB), e-greedy, seplore-thenccomeee among many others. We refer the interested readers to some recent surveys for more details [Latti- more and Szepesvári, 2020, Slivkins, 2019]. The closest line of work to our paper is the proposed batch UCB algorithm [Gao et al., 2019], for which Esfandiari et al. [2021a [0] showed an asymptoti- cally optimal regret bound with Ollog T') number of batches. Very recently, Esfandiari et al. [2021a]

---

and Ruan al. [2021] also addressed the batch linear bandits and the batch linear contextual bandits, respectively. Our work extends those results to the case of Thompson Sampling for the stochastic multi-armed bandit as well as the linear contextual bandit problems.
As we have highlighted in our proofs, our work builds on previous art, especially Agrawal and Goyal [2012, 2017, 2013b] (we believe that giving due credits to previous work is virtue and not vice). However, we build on a non-trivial way. As it is clear from their analysis (and more generally for randomized probability matching strategies), breaking the sequential nature of distribution updates is non-trivial. We show that by a careful mooe strategy, one can reduce the sequential updates from T't (log(T)). We are unaware of any previous work that obtains such result for Thompson Sampling. In contrast, UCB strategies are much more amenable to parallelization (and the analysis is simple) as one can simply the arm elimination method proposed by Esfandiari et al. [2021a] and Gu et al. [2021]. There is no clear way to use the arm elimination strategy for batch TS. Moreover, batch TS clearly outperforms the fully sequential UCB in all of our empirical results.
The benefits of batch-mode optimization has been considered in other machine learning settings, including convex optimization [Balkanski and Singer, 2018b, Chen et al., 2020], reinforcement learning [Zhang et al., 2020], submodular optimization [Chen et al., 2019, Fahrbach et al., 2019, Balkanski and Singer, 2018a]. Gaussian processes [Desautels et al., 2014, Kathuria et al., 2016, Contal et al., 2013], stochastic sequential optimization [Esfandiari et al., 2021b, Agarwal et al., 2019, Chen and Krause, 2013], and Bayesian optimization [Wang al., 2018, Rolland al., 2018), to name a few.
Finally, we would also like to mention a concurrent work by Kalkanli and Ozgur [2021] on the very same subject of our paper, also accepted to NeurIPS 2021. Clearly, there is a significant overlap between the two works. For instance, in both papers, we have the problem-dependent asymptotic optimal regret with (log batches. However, there are also a few differences. In particular, Kalkanli and Ozgur [2021] provide tighter problem dependent bound on the expected number of batches for the stochastic multi-armes bandit. In contrast, we generalize the batch Thompson Sampling strategy to the linear contextual setting.
3 Preliminaries and Problem Formulation
As stated carlier, a standrad bandit problem is a repeated sequential game between a learner and the environment where at each round t 1,2,... ... T, the learner selects an action a(t) from the set of actions A and then the environment reveals the reward ra(t) E R. Different structures on the set of actions and rewards define different bandit problems. In this paper, we mainly consider two canonical variants, namely, stochastic multi-armed bandit, and stochastic linear contextual bandit.
Stochastic Multi-Armed Bandit. In this setting, the set of actions finite, namely, A [N], and each action a E [N] is associated with nub-Gaussian distribution Pa (e.g., Bernoulli distri- bution, distributions supported on [0, 1). etc). When the player selects an action o, reward ra is sampled independently from Pa. We denote by ua Ea-P,Ir, the average reward of an action and by μ² maxag. En-P, [ra] the action with the maximum average reward. Suppose the player selects actions a,,..., ur and receives the stochastic rewards "a.1),..., (a(T)- Then the (expected) regret is defined as
R(T) = =TH² E
Σ
Ta(e)
We say that a policy achieves no-regret, if E (R))) /T - O as the horizon T tends to infinity. In order to compare the regret of algorithms, there are multiple choices in the literature. Once we fully specify the horizon T, the class of the bandit problem (e.g., multi-armed bandit with N arms) and the specific instance we encounter withing the class (e.g., MI,..., MN in the stochastic multi-armed problem), then we can consider the problem-dependen regret bounds for each specific instance. In contrast, trrblem-independent bounds (also called worst-case bounds) only depends on the horizon T and class of bandits for which the algorithm is designed (which is the number of arms N in the multi-armed stochastic bandit problem), and not the specific instance within that class!. For the
'There is related notion of regret, called Bayesian regret, considered in the Thompson Sampling literature |Russo and Van Roy, 2014, Bubeck and Liu, 2013], where known prior the environment is assumed. The
3

---

problem-dependent regret bound, it is known that UCB-like algorithms [Auer, 2002, Garivier and Cappé, 2011, Maillard et al., 2011] I] and Thomson Sampling [Agrawal and Goyal, 2013a, Kaufmann et al., 2012] achieve the asymptotic regret of (log T I'Es,>o A,²)) where A. 4 - pa 2 0. is also known that no algorithm can achieve a better asymptotic regret bound [Lai and Robbins, 1985], thus implying that UCB and TS are both asymptotically optimal. In contrast, for the stochastic multi-armed bandit, UCB achieves the minimax problem- independent regret bound of /NT [Auer, 2002] whereas TS (with Beta-priors) achieves a slightly worst regret of /NTllg T [Agrawal and Goyal, 2017]. Very recently, Jin et al. [2020] developed Minimax Optimal Thompson Sampling (MOTS) that achieves the minimax optimal regret of O(VNT).
Contextual Linear Bandit. Contextual linear bandits generalise the multi-armed setting by al- lowing the learner to make use of side information. More specifically, each arm a is associated with a feature/context vector b E IR.. At the beginning of each round &. E [7], the learner first observes the contexts bn (t) for all E A, and then she chooses an action a(t) E A. We assume that a feature vector ba affects the reward in a linear fashion, namely, ra (t) = (ba (f), js) + Mla,.- Here, the param- eter ju is unknown to the learner, and Ta, is an independent zero-mean sub-Gaussian noise given all the actions and rewards up to time t. Therefore, B(ra(() (b. (t)] = (ba (t), p)). The learner is trying to guess the correlation between j and the contexts ba (I). For the set of actions a(I)...., a(T), the regret is defined
-
R(T)
Σ (t) (t)
Σ (t)
where a a1())= = arg max. (1), (4). The context vectors at time are generally chosen by an adver- sary after observing the actions played and the rewards received up to time / f- 1. In order to obtain scale-free regret bounds, it is commonly assumed that ||a||2 I and |bb (4)ll2 S 1 for all arms a E A. By applying UCB to linear bandit, it is possible to achieve R(T) = Ö(d'T) with high probability [Auer, 2002, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010, Abbasi- Abbasi-Yadkori Yadkori et al., 2011]. In contrast, Agrawal and Goyal [2013b] showed that the regret of Thompson Sampling can be bounded by (
Batch Bandit. The focus of this paper is to parallelize the sequential decision making problem. In contrast to the fully sequential setting, where the learner selects an action and immediately receives the reward, in the batch mode setting, the learner selects batch of actions and receives the rewards of all of them simultaneously (or only after the last action is executed). More formally, let the history H2 consists of all the actions and rewards up time f, namely, (a(s))=E({<)) and respectively. We also denote the observed set of contexts up to and including time by C. = (S) Note that in the multi-armed bandit problem C. = 0. A fully sequential policy π at round E [T] maps the history and contexts to action, namely, n. H4 C. - A. In contrast, a batch policy x only interacts with the environment at rounds 0- = Lo < 11 < 12..... < 4m = T. The 4-1 contains the time units (41-1 + 1, 4-12-1
2, ......... 4 which we denote it by the shorthand (4-1, 4). To select the actions in the 1-th batch the policy is only allowed to use the history of actions/rewards observed in the previous batches, in addition to the contexts received so far. Therefore, a batch policy at time & E (ft-1, ft] is the following map: Te Hy,, X C2 + A. Moreover, batch policy with predetermined fixed batch size is called static and the one with a dynamic batch size is called dynamic.
1-th batch of duration
4 Batch Thompson Sampling for Stochastic Multi-armed Bandit
In the classic Thompson Sampling (TS), any time 1 [T], we consider prior distribution Da(() on the underlying parameters of the reward distribution for every arm a E [N]. TS works by first sampling (L) (!).), independently for each a E [N]. and then choosing the one with the highest value, namely, a₂ = argmax, N) 0g (t). Once the action is played, we receive the reward rt, based on which the the prior distributions are updated as follows. If an arm a is not selected, its distribution does not change, i.e., Da 1) (t).). However, if a ag, then we update Da + 1) given the information (a,, r2) using the Bayes rule. By instantiating TS with different
frequentist regret bounds considered in this paper immediately imply regret bound on the Bayesian regret but the opposite is not generally possible [Lattimore and Szepesvári, 2020].

---

Algorithm Batch Thompson Sampling
Algorithm 2 Batch TS for Contextual Bandits
1: Initialize: ha & 0 (Va E [ND. la t 0
1: Initialize: ka +- 0 (Va E
[N], la +
(Va [N]), batch +-
(Va E [N]), batch t- B = La P = 0g
2: for t-- = 1, ... ... do
for t 1,2....7 ... do pa(t) ~ (N(((((())))) (BB((())))))((()))
3:
(a()) Da(t) (Va E (NT)
3:
4:
a(t) == (r (t).).
4:
a(t) argmax, (1))
5:
ka(e) + ka(e) +
5:
ka(t) - ka(t) +1
6:
if' ku(t) < 2 then
6:
if (a((t) < 2/a(1) then
7:
batch + batch U {a(t)}
7:
batch t batch U {a(t))
8:
else
else
9:
(a(1) l0(0) +
9:
la(0)= = (a(1) +
Query(batch) and receive rewards Update (t) (Va E batch)
10:
Query(batch) and receive rewards
11:
11: Update P
12:
batch t-
12:
batch
13:
end if
13: end if'
14:
end for
14:
end for
prior distributions (e.g., Beta, Gaussian), for which Bayes update is simple to compute, is possible to show that one can achieve an asymptotically optimal regret [Agrawal and Goyal, 2012, 2017].
The main idea behind the Batch Thompson Sampling (B-TS), outlined in Algorithm I, is as follows. For each arm a E [NV. B-TS keeps track of (ka [N] the number of times the arm a has been selected so far. Initially, all ka 's are set to 1. For each arm and at the beginning of the batch, necessarily 2 < lig < 2 for some integer La 2 1. Now consider a new batch that starts at time t. Within this batch, B-TS samples arms according the prior distributions up to time t - 1, namely [ta(t 1)]ee(N) [N] and selects the one with the highest value. B-TS keeps selecting arms until the point that for one of the arms, say a, it reaches h₂ = 2 At this point, B-TS queries all the arms selected during this batch. Based on the received rewards, B-TS updates {Do [NN]] and starts new batch. We should note that the doubling trick used in Algorithm is reminiscent to the halving trick used in the pure exploration setting [Jun et al., 2021, Fiez et al., 2019].
Regret Bounds with Beta Priors. For the case of presentation, we first consider the Bernoulli multi-armed bandit where Ta E {0, 1} and Me. Prira = 1]. In this setting, TS with Beta priors as follows. TS assumes an independent Reta-distributed prior, with parameters (aa, over each Pa- Due to the nice congugacy property of Beta distributions, it is very easy to update the posterior distribution, given the observations. In particular, the Bayes update can be performed as follows:
instantiate
(a Pa) (ar, 3x) (a Ba) 1(t)),)r(t)) af(t)=
af +
TS initially assumes Qg BB for all arms a E [N]. which corresponds the uniform distri- bution over [0, 1]. The update rule of B-TS in Algorithm is also very similar. Let B(t) be the last time t' S of instances arm a was selected by time t - 1 and ra = 1. Similarly, let F, (t) be the number of instances arm was selected by time 1-1 and r.
that B-TS carried out batch. Moreover, for each arm a, let S. (t) be the number
We also denote by k. (t) 5a (t) Fa(t) the total number of instances arm a was selected by time & 1. Initially, B-TS starts with the uniform distribution over [0, 1), i.e., (1) = Beta(1, for all E [N). Inspired by the update rule of TS. at any time I, B-TS updates the distribution (1) by Bela(S.(B(I)) + 1, Fa((() that during a batch when arms are being selected, the distributions (DaJeetN) not change. The updates only take place once the batch is carried out and the rewards are observed.
1). Note
First we bound the number of batch queries follows. Theorem 4.1. The total number of batches carried out by B-TS is at most O(N log T).
The proof is given in Appendix A.2.
Remark 4.2. One might be tempted to show a sublinear dependency on N. However, simple em- pirical results show that the number of batches carried out by B-TS indeed scales logarithmically in T but linearly in N. Please see figs 1a and 1b for more details.
5

---

B-TS (Beta)
250
B-TS (Canssian)
200
40
queries
queries
150-
30
100
20
10
B-TS (Beta)
B-TS (Canssian)
40
80
100
2000
4000
6000
8000
10000
number of arms
(a)
(b)
Figure 1: (a) and (b) show the number of batch queries versus the number of arms and the horizon, respectively. We consider a synthetic Bernoulli setting where the horizon is set to ' = 10 and the number of arms vary from N As we clearly see in Figure la, the regret increases linearly in N which rules out the possibility that the regret of B-TS may depend sub-linearly N. For Figure 1b, we also consider the Bernoulli setting and set N 10 and vary the horizon from T = 1 to T 10 Again, our theory suggests, regret increases logarithmically T.
N 100. We report the average regret over 100 experiments.
What is more challenging is to show is that this simple batch strategy achieves the same asymptotic regret as a fully sequential one.
Theorem 4.3. Without loss of generality, let us assume that the first arm has the highest mean value, i.e., n pt. Then, the expected regret of B-TS, outlined in Algorithm with Beta priors can be bounded as follows
N
In
= (1+)==++))0
Σ 2=
Du
+0
+
d(Has H1)
2
where d(pas = Pa log Ms + - Ma) ) log
(1-pa) and Da I-k1
141 Pa-
The complete proof is given in Appendix A.2.
Remark 4.4. Even though we only provided the details for the Bernoulli setting, B-TS can be easily
extended to general reward distributions supported over [0, 1). To do so, once reward E [0, 1] is observed, we flip coin with bias ri and update the Beta distribution according the outcome of the coin. It is easy to see that Theorem 4.3 holds for this extension as well.
Remark 4.5. Gao et al. [2019] proved that for the B-batched N-armed bandit problem with time horizon 7' it is necessary have B 22 T'/ log log 7') batches achieve the problem-depencee asymptotic optimal regret. This lower bound implies that B-TS use almost the minimum number of batches needed (i.e., Ollog T') versus 22log /log log 7)) achieve the optimal regret.
Now we present the problem independent regret bound for B-TS.
Theorem 4.6. Batch Thompson Sampling, outlined in Algorithum and instantiated with Beta priors, achieves RTT) = ((VNThl with O(N log batch queries.
The proof is given in Appendix A.3.
Regret Bounds with Gaussian Priors. In order to obtain a better regret bound, we can instantiate TS with Gaussian distributions, To do so, let us define the empirical mean estimator for each arm as follows:
pa E.=1 Ta(r) L(a(T) a)
ka(t) +
where kig (t) denotes the number of instances that an arm E [N] has been selected up to time t and I[()) is the indicator function. Then, by assuming that the prior distribution of arm is

---

Algorithm 3 Batch Minimax Optimal Thompson Sampling (B-MOTS)
1: Initialize: Kn f 0 (Va E [N], la t 0 (va E [N]. batch <-
2: Initialize: Play each arm a once and initialize D!()).
3: for t= N + .... T do
4: for all arms a E [N] sample
(t) ~ (/(c
(a) ~ Da(() mln Ta)))
5:
a(t) == argmax, (a(t)
6:
ka(t) ka(t) +1
7:
if ka(t) < 2la(1) then
8:
batch t batch {a(t)}
9: else
La(s) = la(t) +1
Query(batch) and observe rewards 12: Update (4),), Va [N]
11:
13: batch <- 0
end
15:
end for
N/ (Ra(t), Ra(()+T) and that the likelihood of ro, given Ma is N N(pr 1), the posterior will also be
Gaussian distribution with parameters NV (ma + 1), (r+1))+
In B-TS, we need slightly change the way we estimate Pia (t) as the algorithm has only access to the information received by the previous batches. Recall that B(t) indicates the last time t' < t that B-TS carried out a batch query. For each arm a E [N]. we assume the prior distribution (a(1) ~ (Ba(B(I), k.(B)1)1)
We also update the empirical mean estimator follows:
B(()) Ta(r) x II(((T)= = Nio (B(
(a(t)
Note that at any time during the 1-th batch, i.e., t (4:-1, ft). the distribution (t re- mains unchanged. Once the arms {artte(te-.ta) are carried out and the rewards (re)ee(t-1s)) are observed, Pn changes and the posterior is computed accordingly, namely, Da(t; + 1) N (ia + 1), (.( As instantiate B-TS with Gaussian priors, the regret bound slightly improves.
Theorem 4.7. Batch Thompson Sampling, outlined in Algorithm 1 and instantiated with Gaussian priors, achieves E(R(T)) = O(VNTIn with ONN log T) batch queries.
The proof is given in Appendix A.4.
Batch Minimax Optimal Thompson Sampling
So far, we have considered the parallelization of the vanilla Thompson Sampling which does not achieve the optimal minimax regret. In this section, we introduce Batch Minimax Optimal Thomp- son Sampling (B-MOTS), that achieves the optimal minimax bound of O(VNT), asymptotic optimal regret bound for Gaussian rewards. In contrast to the fully sequential MOTS developed by Jin et al. [2020], B-MOTS requires only O(N log T) batches. The crucial difference between B-MOTS and B-TS is that instead of choosing Gaussian or Beta distributions, B-MOTS uses clipped Gaussian distribution.
well as the
To run B-MOTS, we need to slightly change the way Da(() updated. First, to initialize Da(1), B-MOTS plays each arm once in the beginning and sets Ka (N + 1) to 1 and (N 1) to the
7

---

observed reward of each a E [N]. To determine Da (1) for the subsequent batches, let us first
define a confidence range (-oc, (t) for each arm a E [M] as follows:
T
(1) (aa(B(()) +
(B(t)) log
(2)
Nia (B(t))
where log*(x) (2) max (o)( and the empirical mean for each arm is estimated as
(a(t) EtS
B(0) Fa(r) [((T)=
(3)
Ki (B(t) 1)
Note that the estimators in (3) and (1) slightly differ due to the initialization step of B-MOTS.
For each arm a E [n]] B-MOTS first samples (t) from a Gaussian distribution with the following parameters (t) ~ ((a(((()) ( (B()))), where E (1/2, )) is a tuning parameter. Then, the sample is clipped by the confidence range as follows:
Da(t) min (a))).
The rest is exactly as in Alg for B-TS. If you are interested in the details, you can find the outline of B-MOTS algorithm in Appendix B.
B-MOTS for SubGaussian Rewards. We state the regret bounds in the most general format, i.c., when the rewards follow sub-Gaussian distribution. To remind ourselves, we say that a random variable X is a sub-Gaussian if E[xxp(XX XE[X])] I x2p(2X2/22 for all X E R.
The following theorem shows that B-MOTS is minimax optimal.
Theorem 5.1. the reward of each arm is I-subgussian then the regret of B-MOTS is bounded by RT() = OVVNT + Ens..o Aa). Moreover, the number of batches is bounded by O(N log T).
The proof is given in Appendix B.2.
The next theorem presents the asymptotic regret bound B-MOTS for sub-Gaussian rewards. Theorem 5.2. Assume that the reward of each arm a E [N] is I-subgaussian with mean pa- For any fixed p E (1/2, 1), the regret of B-MOTS can be bounded as R(T) (Iog(T) (((T))Er. Ea:da pهa)
The proof is given in Appendix B.3
The asymptotic regret rate of B-MOTS matches the existing lower bound log(T') Ee:d, 1/Ap [Lai and Robbins, 1985] up to a multiplicative factor 1/p. Therefore, similar to the analysis of the fully sequential setting [Jin al., 2020], B-MOTS reaches the exact lower bound at cost of minimax optimality. In the next section, we show that at least in the Gaussian reward setting, minimax and asymptotic optimally cab be achieved simultaneously.
B-MOTS-J for Gaussian Rewards. this part we present a batch version of Minimax Optimal Thompson Sampling for Gaussian rewards [Jin al., 2020], called B-MOTS-J, which achieves both minimax and asymptotic optimality when the reward distribution is Gaussian. The only difference between B-MOTS-J and B-MOTS is the way (t) are sampled. In particular, B-MOTS-J samples 0, (t) according to J (1, o²) (instead of a Gaussian distribution), where the PDF is defined as
27
(x)
20 x 14 exp
Note that when x is restricted to 2 0. then J becomes a Rayleigh distribution. More precisely, to sample (t). we set the parameters of J as follows: da(t) ~ T (ia(B(t) [.((O) where iaa()) (1)) is estimated according to (3). The rest of the algorithm is run exactly like B-MOTS.
Theorem 5.3. Assume that the reward of each arm a is sampled from a Gaussian distribution N (p 1) and a > Then, the regret of B-MOTS-J can be bounded as follows:
R(T)
2
R(T) OOVKOOKTTTT. Σ
lim T T log(T)
Σ
A
8

---

The proof is given in Appendix B.4.
Batch Thompson Sampling for Contextual Bandits
In this section, we propose Batch Thompson Sampling for Contextual Bandits (B-TS-C), outlined in Algorithm 2. As in the fully sequential TS, proposed by Agrawal and Goyal [2013b], we assume Gaussian priors and Gaussian likelihood functions. However, we should highlight that the analysis of B-TS-C and the corresponding regret bound hold irrespective of whether not the reward dis- tribution matches the Gaussian priors and Gaussian likelihood functions (similar to the multi-armed bandit setting discussed in Section 4). More formally, given a context ba (t), and parameter μ4, we sume that the likelihood of the reward ra (f) is given by (ba( p,, v²), where ov (n(//())) and 8 (0, 1)2. Let us define the matrix B(t) as follows
(())= = La + Σ (aat(())tttsttt
Note that the matrix B(t) depends all the contexts observed up to time t 1. We consider the prior (BB( for js and update the the empirical mean estimator as follows:
B(() Σ (T) x (aco)(t)
adt) = B(B(tt)) 11
(5)
Note that in order estimate jit),, we only consider the rewards received up time B(t), namely, the rewards of arms pulled in the previous batches. At each time step t, B-TS-C generates a sample ji()) from N (f(((()) v² ((B(())-) and plays the arm that maximizes bl)² (a(). The posterior distribution for at time t + 1 will be ((t(B(t + 1)), BBt((B + 1))-
Theorem 6.1. The B-TS-C algorithm (Algorithm 2) achieves the total regret of
R(T) O (In(T) + //n(T)(l(((0))))
with probability Moreover, B-TS-C carries out O(N log T) batch queries.
The proof is given in Appendix C.2.
7 Experimental Results
In this section, we compare the performance of our proposed batch Thompson Sampling policies (e.g., B--SSBB-MOTS, B-MOT-J and B-TS-C) with their fully sequential counterparts. We also in- clude several baselines such as UCB and Thompson Sampling with static batch design (Static-TS). In particular, for Static-TS, Static-TS2, and Static-TS4, we set the total number of batches to that of B-TS, twice of B-TS, and four times of B-TS, respectively. However, in the static batch design, use equal sized batches.
Batch Thompson Sampling. In Figure 2a, we compare the performance of UCB against TS and its batch variants in a synthetic Bernoulli setting. We vary T from to 10 and set N = 10. We run all the experiments 1000 times. Figure 2a compares the average regret, i.c. R/T)/T. versus the horizon T. As expected, TS outperforms UCB. Moreover, TS and B-TS follow the same trajectory and have practically the same regret. Note that for the static variant of TS, namely, Static-TS, we see that in the first few hundred iterations, its performance is even worst than UCB and then it catches with TS. Figure 2b more clearly shows the trade-off between the regret obtained by different baselines versus the number of batch queries (bottom-left is the desirable location). In this figure, we set = 10x. We see that the lowest regret achieved by TS and B-TS but TS carries out many more queries. Also, we should highlight that while the static versions make fewer queries than TS, they do not achieve a similar regret. Notably, even -S-tic-TS-4, that carries out times more queries than B- B-TS, has much higher regret. This shows the importance of dynamic batch design.
If the horizon I' is unknown, can a 9d In(t/0).

---

0.6
UOB
B-TS
0.5-
T5
0.4
5 Tr
B-TS
regros
Shotle
StatETO
0.3-
rogret
S S
0.2
10P
101
109
107
10
200
100
600
500
1000
Limeo
tmm
(a)
(b)
(c)
MoTee
300
ISC B m
0.30
TSC r TSC7- tot I1 B-15Co 080, B-TSC (woik 1066 B: B-TSC 08 601
0:30
0.4
Stath-T5C
0:2
TS-C
B-TS-C
0.0
0.50
365
5250
parameter value
timse
(d)
(c)
Figure 2: (a) and (b) compare the regret of UCB against TS and its batch variants. (c) and (d) compare the batch variants of TS and MOTS. (e) shows the sensitivity of TS-C and its batch variants to the tuning parameters. (f) shows the performance TS-C and its batch variants on real data.
Batch Minimax Optimal Thompson Sampling. In Figures 2c and 2d we compare the regret of MOTS Jin et al. [2020] and its batch versions. The synthetic setting similar to Jin et al. [2020]. We set N = 50,7 T 106 and the total number of runs to 2000. The reward of each arm is sampled from an independent Gaussian distribution. More precisely, the optimal arm has the expected reward and variance while the other N arms have the expected reward 1 - and variance (we set e = 0.2). For MOTS, we set p = 0.9999 and a = as suggested by Jin et al. [2020]. As we can in Figure 2c, the batch variants of TS and MOTS achieve practically similar regret. Also, as our theory suggests, B-MOTS (along with MOTS) have the lowest regret while B-MOTS drastically reduces the number of batches w.r.t MOTS. Moreover, the static batch designs, namely Static-TS and Static-MOTS, show the highest regret while carrying out the same number of batch queries as B-TS and B-MOTS. Therefore, the dynamic batch design of B-TS and B-MOTS seems crucial for obtaining good performances. A similar trend shown in Figure 2d where we run MOTS-J (with
2) and its batch variants. Again, B-MOTS-J and MOTS-J practically indistinguishable while achieving the lowest regret.
Contextual Bandit. For the contextual bandit, perform synthetic and real-data experiment. Figure 2e shows the performance of the sequential Thompson Sampling, namely. TS-C, and the batch variants, namely, B-TS-C, as change different parameters context dimension is 5 and we set the horizon to T = 10a We run all the experiments 1000 times. As we in Figure 2e, TS-C and B-TS-C follow practically the same curves.
and from 0 to 1. Here, the
For the experiment on real data, we use the MovieLens data set where the dimension of the context each experiment 100 times. For the parameters, we set
is 20, the horizon is T 10S, and 0.61, a = 0.01, and e = 0.71 as suggested by Beygelzimer et al. [2011]. We see that Static- TS-C performs bit worst than TS-C and B-TS-C, again suggesting that it is crucial to use dynamic batch sizes.
8 Conclusion
In this paper, we revisited the classic Thompson Sampling procedure and developed the first Batch variants for the stochastic multi-armed bandit and linear contextual bandit. We proved that our proposed batch policies achieve similar regret bounds (up to constant factors) but with significantly fewer number interactions with the environment. We have also demonstrated experimentally that our batch policies achieve practically the same regret on both synthetic and real data.
10

---

Funding Transparency Statement
This research is supported by ASFCAREER Award (IIS- (IS-18)))32), ONR YIA (N00014-19-1-2406, and TATA.
References
Yasin Abbasi-Yadkond Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Arpit Agarwal, Sepehr Assadi, and Sanjeev Khanna. Stochastic submodular cover with limited adaptivity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pages 923-342. SIAM, 2019.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit prob- lem. In Conference on learning theory, pages 39-1, 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artifi- cial intelligence and statistics, pages 99-107, 2013a.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135, 2013b.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
Peter Auer. Using confidence bounds for exploitation-exploraaio trade-offs. Journal of Machine Learning Research, 3(N0v):397-422, 2002.
Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1138-1151, 2018a.
Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimization: Adaptiv- ity lower bounds for non-smooth convex minimization. arXiv preprint arXiv: 1808. 201 8bb
Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (mono- graphs on statistics and applied probability). London: Chapman and Hall, 5(71-87):7-7, 1985.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Confer- ence Proceedings, 2011.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 1204v:1204.571,, 2012.
Sébastien Bubeck and Che-Yu Liu. Prior-free and prior-dependent regret bounds for thompson sampling. In Advances in Neural Information Processing Systems, pages 638-646, 2013.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural
information processing systems, 24:2249-2255 2257, 2011.
Lin Chen, Moran Feldman, and Amin Karbasi. Unconstrained submodular maximization with con- stant adaptive complexity. In Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, pages 102-113, 2019.
Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching-coonstrinned online convex optimization: No phase transition. NeurIPS, 2020.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. (C),(()) 280160-168)8811, 2013.

---

Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, 2011.
Emile Contal, David Buffoni, Alexandre Robicquet, and Nicolas Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 225-240. Springer, 2013.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration-explootatioo tradeoffs in Gaussian process bandit optimization. Journal of Machine Learning Research, 15: 3873-3923, 2014.
Hossein Esfandiari, Amin Karbasi, Abbas Mchrabian, and Vahab Mirrokni. Regret bounds for batched bandits. AAAI, 2021a.
Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni. Adaptivity in adaptive submodularity. In COLT, 2021b.
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Submodular maximiza- tion with nearly optimal approximation, adaptivity and query complexity. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 255-273, 2019. doi: 10. 10.1137/1.00 10.1137/1.97811 3781611975482.11 URL https: / /epubs siam. org/doi/abs/ 10. 1137/1. 9781611975482.17 17.
Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32:1066: 12:10667-10677, 2019.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched In Advances in Neural Information Processing Systems, pages 503-513, 2019.
bandits problem.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376, 2011.
Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's 's bing search engine. In /CML, 2010.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits, 2021.
Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. arXiv preprint arXiv:2003.0 20000000..0........ 2020.
Kwang-Sung Jun, Lalit Jain, Houssam Nassif, and Blake Mason. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference on Machine Learning, pages 5148 5157. PMLR, 2021.
Cem Kalkanli and Ayfer Ozgur. Batched thompson sampling, 2021.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised bayesian optimisation via thompson sampling. In International Conference on Artificial Intelli- gence and Statistics, pages 133-142. PMLR, 2018.
Tarun Kathuria, Amit Deshpande, and Pushmeet Kohli. Batched Gaussian process bandit optimiza- tion via determinantal point processes. In Advances in Neural Information Processing Systems, pages 4206 4214, 2016.
12

---

Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
Jaya Kawale, Hung H Bui, Branislav Kveton, Long Tran- Tran-Thanh, and Sanjay Chawla. Efficient thompson sampling for online matrix-factorrization recommendation. Advances in neural formation processing systems, pages 1297-1305, 2015.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. A finite-time analysis of multi-armed bandits problems with kullback-leibler divergences. In Proceedings of the 24th annual Confer- ence On Learning Theory, pages 497-514, 2011.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit prob- lems. Anm. Statist., 44(2):660-611, 04 2016. doi: 10.1214/15-AOS1320 URL https:
//doi..rg//10.....////o 1214/11111111 AOS1381. Extended abstract in COLT 2015.
Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. High-dimensional bayesian optimization via additive models with overlapping groups. arXiv preprint urXiv:1802.07028, 2018.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distri- butional optimal design. arXiv preprint 20X.v2200..01900 2021.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35 2010.
Mathematics of
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Rexeurch, 3214)1221 2014.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial thompson sampling. arXiv preprint 1eXiv:170.02000 2017.
Eric M Schwartz, Eric Bradlow, and Peter Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint
2019.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale bayesian optimization high-dimensional spaces. In International Conference on Artificial Intelligence and Statistics, pages 745-754. PMLR, 2018.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-adven -aveetage decomposition. Advances in Neural Information Processing Systems, 33, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (c.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "kPFhYpeKI0i", "reviewer": "Reviewer_2bFv", "summary": "This paper introduces a batched version of the Thompson Sampling algorithm. For the multi-arm bandit problem, within O(NlogT) batches, it is able to achieve a regret (both problem-dependent and problem-independent) that is the same order as the fully online TS; when substituting TS with MOTS, the batched-learning algorithm achieves the minimax optimal regret O(\\sqrt{NT})., again within O(NlogT) batches. For the contextual-bandit problem, the batched-TS algorithm achieves the regret bound O(d^{3/2}\\sqrt{T}) (up to logarithmic factors), again within O(NlogT) batches.\n", "questions": "", "limitations": "", "rating": 5, "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": "The writing of this paper is clear and concise. One interesting point of this paper is that it proposes a batched algorithm based on dynamic grid design---note that in Gao et al., (2019), the lower bound is established w.r.t. dynamic grids but the optimal algorithm provided there in fact uses a static grid design. \n\nMy major concern here is the optimality of the results, especially the dependence of the regret on the number of batches. For example, in the MAB case, for the problem-dependent regret here is an extra N factor in the number of batches needed to achieve optimality; for the problem-independent bound, O(NlogT) batches are needed instead of the \\Omega(\\log\\logT) batches given in Gao et al., (2019). As such, I am not quite sure how to understand the advantage of the algorithm proposed (please correct me if I am wrong or misunderstood anything). \n\nIndeed, in general, it is hard to establish theoretical results for Thompson-Sampling-based algorithms, so it would help to illustrate why it is hard to establish tighter results in terms of the number of batches. On the other hand, Thompson-Sampling-based algorithms are often found to have a better performance numerically---so it may help to show more numerical evidence of the advantage of the algorithm.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A discussion on the potential negative societal impact of this work should be added. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "KSswtKfEi4H", "reviewer": "Reviewer_JP6Y", "summary": "\nThis paper considers Thompson sampling (TS) for standard and contextual bandit problems. In bandit problems, TS is known to have great performance both theoretically and empirically. Although these problems assume a fully adaptive setting where the algorithm updates itself at each time step, this may be too restrictive to run in practice. This paper considers a mini-batch setting and considers the batch Thompson sampling (B-TS) algorithm (Algorithm 1). In particular, the distribution-independent bound is not compromised by deriving exponentially large size of batches (Algorithm 1 and 2). The authors also analyzed the clipped version of TS (MOTS) for Gaussian rewards as well as contextual linear bandits (Algorithm 2). \n\n### After the discussion period\nI think the contribution is weak, but okay to publish. I will keep the current rating but not strongly oppose to acceptance. ", "questions": "", "limitations": "", "rating": 5, "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": "\nIn my view, this paper is marginally below the acceptance threshold. This paper is well-written and nice, but there is not a strong push for this paper, and given TS, Batched UCB, MOTS, and contextual Thompson sampling are well-known, the results here are somewhat incremental. Deeper results on the adaptivity, limitation on static make the paper theoretically interesting. \n\n- Remarks\n\nMotivating applications: The paper exponentially increases the batch size and would be great if there are specific scenes where the proposed algorithms shine.\n\nIs there any results on static batch (Can static batched bandit with O(log T) batch size achieve the same rate/impossibility of that?). Algorithm 1 and 2 are dynamic batching. Results/limitations on static make the paper more interesting.\n\nIs there any way to fill the gap of logT samples and logT/(loglogT) sample lower bound by [Gao et al 2019]?\n\nCan you characterize the difference between similar results on UCB with these results? \n\n- Minor remarks\np2 notation inconsistency (N log(T) and N log T)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addresses the limitations. The societal impact is not described as this paper is methodological paper. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "I_L9eu-JRq", "reviewer": "Reviewer_DzXv", "summary": "The authors consider the Thompson sampling algorithm in the canonical stochastic bandit models, namely the N-armed bandit model and the linear contextual bandit model. They consider the case when the decision agent has to make the arm choice decisions in batches, and there are at most O(N log T) batches during the T-round horizon. The authors proposed batched versions of the TS algorithm by incorporating a doubling scheduling, and show that the batched version of the TS still achieves the state-of-the-art regret bounds by combining the analysis with existing works. ", "questions": "", "limitations": "", "rating": 3, "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": "My main concern is that, given the existing research on Thompson sampling and batched stochastic bandits under the UCB algorithm, the novelty of the submission is marginal. The main difference between the author's B-TS in Algorithm 1 and the vanilla Beta Bernoulli TS lies in the doubling schedule (the \"if... else\" loop). The use of such a doubling schedule is not a new idea, for example it is covered in Exercise Questions 7.4, 7.5 in the book \"Bandit Algorithms\":\n\nhttps://tor-lattimore.com/downloads/book/book.pdf\n\nMoreover, in Appendix A in the supplementary material for the analysis of B-TS, much of the technical content appears to be a straightforward corollary of Agrawal and Goyal 2017's TS paper. Altogether, the novelty in the algorithm design and analysis is below the bar for NeurIPS in my opinion.\n\nAnother major concern is that the authors only provide a regret bound for a specific value of batch size. Nevertheless, in existing works on batched bandits under UCB, a regret bound is provided for each batch size. Therefore, in comparison to these existing works, the generality of the results appears to be lacking. \n\nLastly, in Theorem 4.6, the authors remark on the batch size used for achieving the $\\tilde{O}(\\sqrt{NT})$ bound, and they stated that their batch size is $O(N \\log T)$. There seems to be a gap from the batch size $O( \\log \\log T)$, which is known to be sufficient for achieving the $\\tilde{O}(\\sqrt{NT})$ regret bound (see Corollary in Gao et al 2019 https://arxiv.org/pdf/1904.01763.pdf for example)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author should have stated much more explicitly that, in existing research works on batched bandits under UCB, they provide a regret bound for every possible batch size $B\\in \\mathbb{N}$, whereas the authors only provide a regret bound for TS when the batch size is $O(N \\log T)$.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Dt-gbudO23T", "reviewer": "Reviewer_9U7C", "summary": "This paper studies the batched multi-armed bandit problem, where arms are pulled in a batch fashion and the rewards are only obtained at the end of the batch. The authors propose Thompson sampling based algorithms in the batch bandit setting, which enjoy logarithmic batch complexities. This improves their full sequential counterparts that have linear batch complexities. They proved that these algorithms with improved batch complexities also enjoy the same regret bounds as fully sequential algorithms. \n", "questions": "", "limitations": "", "rating": 6, "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 the algorithms are designed in a clear way. The proposed batched bandit strategy is general enough and shows its extension to different variants of Thompson sampling algorithms. The analysis seems to be solid and the results are correct based on my intuition (I did not check all the proofs and their correctness). \n\nThe main weakness of this paper is the novelty and contribution part. In particular, the core contribution of this paper is the strategy of converting Thompson sampling into a batched algorithm, which seems novel and never done in the literature before. However, the other parts of the paper such as the minimax optimal thompson sampling (MOTS), MOTS-J for Gaussian rewards, and contextual TS are more or less a showcase of applying the proposed strategy to existing algorithms. This can also be seen from the proof analysis, where the majority of the proofs for these applications are similar to that in existing papers. \n\nFor Remark 4.5, it is worth clarifying that the lower bound on the batch complexity ($\\Omega(\\log T/ \\log \\log T)$) proved in Gao et al., [2019] is for achieving the finite-time problem-dependent regret bound for multi-armed bandits. However, in order to achieve the problem-dependent asymptotic optimal regret as stated in Remark 4.5, it has been proved in [1] that constant batch complexity is sufficient for 2-armed bandits, and in [2] that a little more than $O(\\log\\log T)$ batch complexity is sufficient. \n\n[1] \"Double explore-then-commit: Asymptotic optimality and beyond.\" COLT, 2021.\n[2] \"Almost Optimal Anytime Algorithm for Batched Multi-Armed Bandits.\" ICML, 2021. \n\nFor Algorithm 2, in Line 5, you need to keep track of the number of pulls of each arm. Does this mean the proposed algorithm does not work in the setting with infinite arms? In this setting, you may select different arms at each iteration and thus the number of arms selected could go to infinity. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main weakness of this paper might be that the algorithm design and analysis techniques are not very novel in the literature. I do not see negative societal impact directly related to this work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the problems studied in this paper look to be interesting, this paper has two weaknesses: (1) the bound $O(N\log T)$ batches is too large, compared with $O(\log T)$ or $O(\log T/\log\log T)$ using UCB or successive-elimination. The author's feedback appears to be attempting to minimize the importance of $N$ but only focus on $T$.   However, $N$ is often a significant consideration and can be very large in practice.  (2) It seems to be straightforward to combine the standard doubling method with Thompson sampling. Basically, if we can guarantee that the prior of each arm does not change by much in each round (which is true if we terminate a round when the number of pulls on a particular arm doubles), then we can easily mimic the proof of Agrawal&Goyal 2017 for (standard) Thompson sampling to obtain the regret bounds in the batched model.  In this regard, the novelty of this paper is limited.

Decision: Accept (Poster)