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 eeale.aallllle.. 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 explorationeeploiittion 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-then-comeee 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,,..., ar 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) + M/a,.- 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
- Σ (t)
R(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(((((())))) (B(((())))))((()))
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:
(a())= = (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(()),)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,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 RT)) = ((/NThl 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(t)) 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)), 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((L0))))
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 TT
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 If B-15Co 080, B-TSC (wiik 1066 B: B-TSC 08 601
0:30
0.4
Stath-T5C
0:2
TS-C
B-TS-C
0.0
0.50
365
5200
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-factoriization 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 -aveettge 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": "UkWJrsL4B8", "reviewer": "Reviewer_tYDL", "summary": "The paper \"Parallelizing Thompson Sampling\" presents a batch-version of the traditional sequential Thompson Sampling which uses maximum $O(\\textrm{Number-of-Arms} \\times \\log(T))$ batches to interact with the environment. \n\nThe paper shows that this is only $O(\\textrm{Number-of-Arms} \\log\\log T)$ worse than the minimum possible number of batches, but it achieves the same regret as traditional Thompson Sampling, which can be thought of as using $O(T)$ batches of size 1. The key idea in the algorithm is that the batch sizes are randomized. A new batch is started as soon as we approximately double the number of queried examples since the last batch. \n\nThis paper is a natural expansion of the recent line of work on Batch-UCB to Thompson Sampling and I believe it will be interesting to audience of NEURIPS.\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": "**Originality**: Batch version of classic bandit problems have emerged fairly recently, with most of the work done on UCB style approaches. This paper presents novel Thompson Sampling algorithms for batch multi-armed bandit, and batch linear contextual bandit.\n\n**Quality and Clarity**\n\nI found this paper to be well written and self-contained. Specially the Related Work section which nicely laid out the existing results in this area. I spent quite some time with Appendix A.2 which proves the main theorem of the paper and I think the proof is correct and fairly well - presented. I really liked the clear definitions in Appendix A.1 as well. That said here are some corrections and small suggestions for improvement.\n\n1. The statement of Thm 4.3 can be made to match the traditional $\\displaystyle\\sum\\frac{1}{\\Delta}$ regret bound by using the pinsker inequality.\n\nLet the equation between eq(6) and eq(7) be (6.5)\n\n2. Please use $\\mathbb{I}$ consistently in equation (6.5c) and (6.5d)\n\n3. The inequality sign should actually be equal sign in (6.5d)\n\n4. Eq(7) should use $p_{a, \\tau_k + 1}$ instead of $p_{a, \\tau_k} + 1$ in denominator. Same for Lemma A.11\n\n5. The summation in the first inequality in Eq(7) should be from $0$ to $L_a(T)$ not from $0$ to $T-1$\n\n\n**Significance** Although I doubt that the paper will have much of a practical impact on practitioners, but I think it will be well-received by theory researchers. I will like to propose some additional experiments to clarify the importance of the empirical results.\n\n1. Figure 2(b) compares the performance of the proposed algorithm to a \"naive\" batch-TS algorithm with a fixed batch-size. This comparison is helpful, but I will also a comparison to a scheme with exponentially increasing batch-sizes on a fixed schedule. Something like the epoch greedy schedule that partitions the time-steps into exponentially bigger intervals like {1, 2, 4, 8, 16, 32, 64, 128, ...}. This will use only $\\log(T)$ batches and spend more time exploring in the beginning and should have much better regret than the naive baseline presented in the paper. \n\n2. I will also like to see the empirical histogram of batch-sizes and the number of batches across various runs of this algorithm. Having tight control -- concentration -- over the batch sizes and number of batches may be necessary for practical deployment.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The discussion was adequate.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "UbbsrUPRUFE", "reviewer": "Reviewer_Qcd6", "summary": "This paper investigates dynamic-batch Thompson sampling. The proposed methods enjoys enjoy theoretically preferable regret bounds. Particular, in the stochastic multi-armed bandit setting, \n\n* B-TS achieves the problem-dependent asymptotic optimal regret;\n* B-MOTS achieves the optimal minimax problem-independent regret bound;\n* B-MOTS-J, designed for Gaussian rewards, achieves both minimax and asymptotic optimality.\n\nMoreover, a method named B-TS-C is also proposed applicable in the linear contextual bandit setting.\n\nFinally, the proposed methods are compared with their fully sequential counterparts via experiements on synthetic and small real data.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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**\n\nThis extends existing batch UCB algorithms to the case of Thompson Sampling for the stochastic multi-armed bandit as well as the linear contextual bandit problems. \n\n**Clarity**\n\nThis paper is clearly presented and readable. Although I am not very familiar with this research area, I could keep up with the storyline without much effort.\n\n**Significance**\n\nAs pointed out in the Summary section, in the stochastic multi-armed bandit setting,\n\n* B-TS achieves the problem-dependent asymptotic optimal regret;\n* B-MOTS achieves the optimal minimax problem-independent regret bound;\n* B-MOTS-J, designed for Gaussian rewards, achieves both minimax and asymptotic optimality.\n\n**Limitations**\n\nB-TS-C seems (I am not sure and the paper does not claim explicitly) to be the first dynamic-batch Thompson sampling method for the linear contextual bandit setting. However, while most of the papes of the paper are about the stochastic multi-armed bandit, it is suggested to add more discussion about B-TS-C, such as the adventages, limitations and future work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Rz1K5MqMHY", "reviewer": "Reviewer_2HGA", "summary": "Paper introduces a batch Thompson Sampling framework, and studies it for stochastic multi-arm bandit and linear contextual bandit with finitely many arms. They show that it achieves the same minimax and asymptotic regrets as the standard sequential algorithms.", "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": "Two major paper strengths are that the paper is well written, and its strong theoretical and empirical results.\n\nThe paper's contribution is incremental. The proofs closely follow proofs of other papers, with minor changes to accommodate batches. The reason dynamic batching is not affecting regret guarantees seem to stem from the doubling trick (see https://arxiv.org/pdf/1603.06560.pdf). \n\nIn fact, bandits leveraging the doubling trick, like for transductive reasoning, also achieve similar batching. Albeit in their use-case, batching is a by-product, and not necessarily the objective. See:\n- http://proceedings.mlr.press/v139/jun21a/jun21a.pdf (ICML'21)\n- https://arxiv.org/abs/1906.08399 (NeurIPS'19)\n\nOn the practical side, it is unclear to me what actual use-cases would want such a dynamic batching for the sake of batching. My experience has been that people batch because they are forced to, due to delays and system issues (like production system updates once a day). Possible a reflection of that, and a discussion of the reasons the doubling trick achieves the desired result, could enrich the paper. \n\nFinally, the parallelizing claim is a little misleading. although I get the author's points, still typically one thinks of parallelizing as parallelizing batch trainings. The authors refer to basic sequential batching, on one machine, as parallelizing.\n\nOverall, the paper still has merits, in the sense that it states batch-related theorems that others could leverage, cite or build on, all in one paper. It is likely though that similar theorems existed implicitly in other papers, like the ones I reference above.\n\nMinor:\nThrm 5.1. Delta_a not previously defined in paper. \nSince the appearance of Delta (gap) in a minimax theorem may sound counter-intuitive, you may want to remove it from the main theorem's formulation, and explain it in the appendix.\nFor instance, you can include similar language to Jin et al 2020, in their paragraph immediately below equation (5) of their paper.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GA_-H3Am2n_", "reviewer": "Reviewer_E33d", "summary": "This paper introduces a batch framework of Thompson Sampling for the stochastic multi-armed bandit and linear contextual bandit, which achieves the same regret bound of a fully sequential one while carrying out only O(log T) batch queries.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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 idea of the proposed batch framework has already been developed and analyzed for finite horizon MDP, named by stage-based update framework in Zhang et al., 2020. Same as Algorithm 1, the sample rule of stage-based update remains unchanged until some state action pair is visited (1+1/H)^k times, which is shown can achieve low switching cost. \nThe finite horizon MDP class contains the stochastic multi-armed bandit as a special case by taking the state space size S = 1 and horizon H = 1. Although Zhang et al. consider the UCB update rule, different from Thompson Sampling herein, this makes little difference about the nature of batch policies can achieve similar regret bounds but with fewer number of interactions with the environment. Hence, I think the novelty of this paper is not enough. In addition, given the results about UCB update for finite horizon MDP (including bandit), the importance of this paper is also insufficient.\nI would raise my score if the significance and difficulties of this extension from UCB update for finite horizon MDP to Thompson Sampling for bandit can be explained well. \n\nZhang, Z., Zhou, Y., and Ji, X. (2020). Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes several _batched_ Thompson sampling (TS) algorithms for stochastic and linear contextual bandit problems. In this setting, the bandit may take multiple actions before updating. For instance, if the bandit were optimizing a recommender system, it could serve recommendations to multiple users before collecting feedback and updating. Importantly, the bandit gets to decide how many actions it takes in each batch. Its goal is to minimize its regret _as well as the number of batches_. The proposed algorithms all achieve the optimal $\tilde{O}(\sqrt{T})$ (sublinear) regret using only $\tilde{O}(\log T)$ batches. Experiments show that the batched TS algorithms perform as well as fully sequential TS and better than UCB.

The paper is clear, well written and easy to follow. The theoretical results are strong in the sense that they achieve optimal rates. The empirical results are thorough and convincing. It's a nice paper that will be of interest to the NeurIPS community.

The reviews raise the following concerns.

(1) The work is closely related to recent work by Zhang et al. (NeurIPS, 2020) which proposed a batch UCB-style algorithm for tabular MDPs. The asymptotic rates for batched TS are no better than those for batched UCB. For this reason, one reviewer argued that the current work is incremental and not worth accepting. During discussion, the following points (paraphrased) were made by another reviewer:

* Zhang et al.'s work only applies to tabular MDPs with discrete states; hence, it doesn't apply to contextual bandits.
* Since Zhang et al.'s work studies MDPs, it can be thought of operating in a stochastic reward setting instead of adversarial. The current paper accommodates an adversarial setting.
* The fact that the proposed TS algorithms cannot guarantee better asymptotic rates is not a reason to reject. Aggarwal et al.'s seminal papers analyzing TS did not show better rates than UCB; just that TS performed close to optimal, off by a log factor. TS and UCB operate differently and as such their analyses are different, and historically advancements in either algorithms have merited publication.

Based on these points, I do not think Zhang et al.'s work subsumes the current work, and I do not see this issue as grounds for rejection.

(2) The analysis techniques are well known -- in particular, the "doubling trick" has been used in the past (see Review 2HGA), albeit not with batching in mind -- which detracts from the paper's contributions. Nonetheless, the combination and application of these techniques is compelling. And, as Reviewer 2HGA points out, it's nice to have all of these batching theorems compiled in a single paper, for reference by others.

(3) The practicality of the proposed algorithm is questionable, due to the assumption that the algorithm gets to decide how much to batch. In a typical bandit application (e.g., a recommender system or ad placement system), batching is used out of necessity, due to external factors like latency or limited computing resources.

I am recommending Weak Accept, because it is a nice paper, and I believe this paper will be of value to the NeurIPS community (perhaps mainly theoreticians), but the practicality of the proposed algorithms is questionable.
Decision: Accept (Poster)