Batched Thompson Sampling
Authors: Cem Kalkanli
Ayfer Ozgur
Venue: NeurIPS 2021 Poster (2021)
Keywords: Thompson Sampling
Batched Multi-Armed Bandits
Stochastic Multi-Armed Bandits

Abstract: We introduce a novel anytime batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order $O(\log(T))$ and a minimax regret of order $O(\sqrt{T\log(T)})$  while the number of batches can be bounded by $O(\log(T))$ independent of the problem instance over a time horizon $T$. We also prove that in expectation the instance dependent batch complexity of our policy is of order $O(\log\log(T))$. These results indicate that Thompson sampling performs competitively with recently proposed algorithms for the batched setting, which optimize the batch structure for a given  time horizon $T$ and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. Unlike these algorithms, the batched Thompson sampling algorithm we propose is an anytime policy, i.e. it operates without the knowledge of the time horizon $T$, and  as such it is the only anytime algorithm that achieves optimal regret with $O(\log\log(T))$ expected batch complexity. This is achieved through a dynamic batching strategy, which uses the agents estimates to adaptively increase the batch duration. 


Batched Thompson Sampling
Cem Kalkanh and Ayfer Özgür Department of Electrical Engineering Stanford University {cemk, aozgur))staafoord edu
Abstract
We introduce novel anytime batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simulta- neously achieves problem dependent regret of order (Tog(T)) and minimax regret of order P(VTlog(TT) while the number of batches can be bounded by (log(T)) independent of the problem instance over a time horizon T. We also prove that in expectation the instance dependent batch complexity of our policy is order Ollog lT). These results indicate that Thompson sampling performs competitively with recently proposed algorithms for the batched setting, which optimize the batch structure for a given time horizon T and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. Unlike these algorithms, the batched Thompson sampling algorithm we propose is an anytime policy, i.e. it operates without the knowledge of the time horizon T. and such it is the only anytime algorithm that achieves optimal regret with O (log log(T")) expected batch complexity. This is achieved through dynamic batching strategy, which uses the agents estimates to adaptively increase the batch duration.
Introduction
The multi-armed bandit problem models the scenario where an agent plays repeated actions and observes rewards associated with her actions. The agent aims accumulate as much reward as possible, and consequently, she has to balance between playing arms that generated high rewards in the past, i.c. exploitation, and selecting under-explored arms that could potentially return better rewards, i.e. exploration. In the ideal scenario, the agent can adjust her policy once she receives feedback, e.g a reward, before the next action instance. However, many real-world applications limit the number of times the agent can interact with the system. For example, in medical applications (26), many patients are treated simultaneously in each trial, and the experimenter has to wait for the outcome of one trial before planing the next. In online marketing [25], there may be millions of responses per second, and as a result, it is not feasible for the advertiser to update her algorithm every time she receives feedback.
Recently, Perchet [19] proposed model this problem the batched multi-armed bandits. Here, the experiment of duration T' is split into a small number of batches and the agent does not receive any feedback regarding the rewards of its actions until the end of each batch. For the two-armed bandit problem, they proposed general class of batched algorithms called explore-then-comee policies, where the agent plays both arms the same number commits to the better performing arm in the last round unless the sample mean of one arm sufficiently dominates other in earlier batches. They show that this algorithm achieves the optimal problem- dependent regret Olog(TT) and the optimal minimax regret O O(VT), matching the performance in the classical case where the agent receives instantaneous feedback about her actions, by using only ( lo)( and Ollo log(T)) batches respectively. Their algorithm takes the time
(ETC) times until the terminal batch and
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

horizon T and divides it into fixed number of batches before the experiment where the specific batch structure tuned to the target performance criteria, i.e. problem-dependent or minimax regret. Gao et al. [10] later generalized this result to the setting where the agent had more than two arms to choose from and she could adaptively adjust the batch sizes based on the past data. Their algorithm, called BaSE, is similar to the ETC algorithm in that in each batch the agent plays each of the remaining actions in a round robin fashion, and climinates the underperforming arms at the end of cach batch. They showed that this algorithm required (llo(TT) and (log log(T)) number of batches to achiove the optimal that were again tailored to the specific objective. More recently several other batched algorithms appeared in the context of asymptotic optimality [13], stochastic and adversarial bandits [9], and linear contextual bandits [11, 22, 20, 211, where the authors provided optimal algorithms in their respective settings. We note that there are also some earlier algorithms developed in the context of the classical bandit setting or bandits with switching cost that even-though not specially developed for the batched setting can be applied in a batched fashion [4, 6].
and the optimal minimax regret respectively, with batching strategics
In this paper, we aim to study whether Thompson sampling, an algorithm that has been developed in 1933 [26] and since then successfully applicd to a broad range of online optimization problems [7. 25]. can achieve a similar performance in the batched sctting. In the Thompson sampling algorithm, the agent chooses an action randomly according to its likelihood of being optimal, and after receiving feedback, i.e. observing rewards, updates its beliefs about the optimal action. The performance of Thompson sampling has been thoroughly analyzed in the literature [16, 17, 1, 2, 23, 24] and is known to achieve the optimal understand whether Thommson sampling can be combined with an adaptive batching strategy and maintain its regret performance when allowed to update its beliefs only at the end of small number of batches. Note that the carlier algorithms developed specifically for the batched setting [19, 10] heavily prioritize exploration in the initial batches eliminate the possibility that a suboptimal arm is played in the final exponentially larger batches, while Thompson sampling inherently balances between exploration and exploitation by randomly sampling actions according to their probability of being optimal. A first result in this direction has appeared in [14], which presents batched Thompson sampling strategy called iPASE. However, [14] provides almost sure guarantees on the asymptotic regret which do not imply the guarantees on expected finite-time regret of interest in this paper and the previously mentioned literature.
depeeddd and minimax regret in the classical case. Our goal is to
Our main contribution in this paper is to show that Thompson sampling, combined with a novel adaptive batching scheme, achieves the optimal problem-dependent performance (log(T)) and at the same time a minimax regret of order ((v ((oo)))) by using (log(T)) batches independent of the problem instance. This performance is achieved simultaneously by single strategy without the need to tune the batching structure according to the target criteria, i.e. problem-dependen or minimax regret. Moreover, unlike most of the previously mentioned batched algorithms where T is used both in action selection and the optimization of the batch structure, our strategy is an anytime strategy, i.e. it operates without the knowledge of the time horizon T. We note that policies designed for minimizing the problem-dependent regret can indeed be turned into anytime algorithms while retaining their (log(T)) regret and ((lg(TT) batch complexities with the help of the so called doubling trick in [5]. but the same extension does not hold for minimax policics. This is because even with the best known doubling schemnes (exponential or geometric), the minimax policies either suffer regret significantly larger than vT or have their batch complexity increase to M(log (exponential doubling leads to the first conclusion and geometric doubling leads to the second). This implies that our anytime Thompson sampling strategy matches the batch size of (llgg(T)) needed for these anytime extensions. In addition, we develop a problem-dependent bound on the expected number of batches used by our strategy which is Ollg log( This shows that while our strategy uses Ollog(T) batches in the worst case, similar to previous algorithms, in a given instance of the problem with fixed reward distributions we only need Ollog log(T)) batches on average. To the best of our knowledge, our scheme is the only strategy that can reduce the number of doubly
batches to (log log( without the knowledge of the time horizon T.. This corresponds exponential reduction in the interaction needed with the environment as compared to the classical case. We achieve this with a two-fold adaptive batching scheme that allows the batch sizes to increase doubly exponentially as the agent becomes more confident in its decisions. The scheme consists of two layers comprising of batches and multiple cycles inside each batch: the number of cycles per batch is increased exponentially, while at the same time each cycle becomes longer as the agent learns the environment and suboptimal action is played less and less frequently. This notion of cycles is
2

---

key to allowing the batching scheme to dynamically adopt to each instance of the problem, which enables the (log (T)) guarantee on its expected problem-dependent batch complexity.
Finally, we would like to mention concurrent and independent work by Karbasi et al. [15], also accepted to NeurIPS 2021. They consider the same problem and also develop batch Thompson sampling strategy for the multi-armed bandits setting. While their results have some overlap with ours, there are also some differences. For example, they establish (T)) worst-case guarantee on the batch complexity of their algorithm as we do in our paper. however their algorithm lacks O (T)) guarantee on its expected batch complexity. contrast, they generalize their batch Thompson sampling strategy to the linear contextual setting, while we restrict our attention to multi-armed bandits.
Problem Formulation
2.1 Notations
denote the natural logarithm as log(-) while a logarithmic function of base a log (.). For and an (2,,,. if and only if b, Oa,). We also denote by Q(-) the probability of standard normal random variable X being bigger than a certain threshold æ; i.e. Q(x) = P(X 2 x)) for any x C IR Finally 1(-) is defined as the indicator function.
the non-negative sequences of } and {ba). an = ((b,) if and only if lim sup,
2.2 Batched Multi-Armed Bandit
We consider the batched multi-armed bandit setting. Here there are K arms, where each consecutive pull of the jth arm produces bounded i.i.d. rewards (Yá,t) such that
Y11 [0,
E E| = 14 E
These mean rewards { are assumed to be deterministic parameters unknown the agent, whose goal is to accumulate as much reward as possible by repeatedly pulling these arms. Therefore, each time instance t, the agent plays an arm At {1, ..., K} and receives the reward YA.,t- Since she can only causally and does not know } she can only use the past observations, H4 {A1, YA....... A,, YA.,} where Ho = U, to seleet the next action A4+1.
In this paper, we study the batched version of this multi- armed bandit problem, where the agent has to play these arms in batches and can only incorporate the feedback from the system, i.e. her rewards, into her algorithm at the end of a batch. In other words, there are batch end points () = To Ti .... and the actions the agent plays in the jth batch [ + 1, Tj] as well as the size of the batch itself, i.e. Tj T3 1. can depend only on the information present in Hr, for any j Z+ and some external randomness that is independent of the system. Note that in this setting, the agent is allowed adaptively choose the batch sizes depending on the past observations.
Finally, we let μ1 > μ4 for any 2 2. Given that the agent aims to maximize her cumulative reward, she would only play the first arm if she knew the hidden system parameters {H) This observation naturally leads to the cumulative regret term, R(T):
K
E[R(T)) = Σ ([N
(1)
where μ1 14 A, and
T N₂(T) = Σ 1(A
t=1
fo (1, .... K}.
3

---

3 Batched Thompson Sampling
In this section, we describe our Batched Thompson sampling strategy for the batched multi-armed bandit setting described in the previous section. This policy uses Gaussian priors in the spirit of [2] and each arm sampled randomly according to its likelihood of being optimal under this prior and the observations from previous batches. We combine this strategy with an batching mechanism which relies on the notion of cycles. A cycle is defined as follows. The first cycle starts in the beginning of the experiment and ends when the agent selects an action different from the previous actions, ie. it corresponds to the shortest time interval starting from the beginning of the experiment where the time
two different actions are selected. Then the jth cycle for j > 1 is defined recursively interval from the end of the j - 1hh cycle to the first time step where the agent selects an action different from the first action in the cycle. In other words, in each cycle the agent plays exactly two different actions. Consider the following example. Assume that the first seven actions played by the agent
follows: A = A2 1, A3 2, A4 1, As 3, As- 2, A7 2. Then the first cycle is [1,3] because only at the third time step the agent selected an arm different from the earlier actions. Similarly, the second cycle is [4,5] 5] where the agent played the first and the third actions. The third cycle that started on t = 6 has not ended yet because only a single action has been played so far. We use the concept of eycle adaptively decide on the batch size. At the beginning of the jth batch, the Thompson sampling agent checks the number of cycles in which each action i has been played since the beginning of the experiment, denoted (T, ) and sets upper limits Ui, - max Jo x (T for the cycle count of each action. Here a >> is a batch growth factor to be chosen. Throughout the jth batch, the agent employs Thompson sampling, and at the end of each cycle checks whether or not the number of cycles in which a certain arm has been selected since the beginning of the experiment has reached its upper limit U2, set for the current batch. The batch ends if there is one such action hitting its upper limit. After the jth batch, the agent observes the rewards of its actions and repeats the same process in the next batch. Note that as the algorithm proceeds the batch size increases due to two different reasons. First, the cycle count of each action is increased at the end of each batch. This alone leads to an exponential increase in the number of cycles per batch with base However, in addition to this, the length of each cycle becomes longer as the agent becomes more confident about its decisions and the probability of playing an optimal arm decreases. Note that the exponential increase in the number of cycles per batch is there even if the algorithm does not make progress in learning its environment, e.g. always plays arms with equal near-equal probability due to very noisy environment. However, the increase in the cycle duration is tightly coupled with the confidence of the agent and the cycle duration increases only the agent becomes more confident. Therefore, this notion of cycles allows to adopt the batch size much more dynamically to the current progress of the agent in a given instance of the problem.
We now introduce the following notation to denote the beginning and end of the htth cycle, Co,s and Ca.t respectively:
if = 1 Co,b Co,o= - 1 Cea-1+1 if > 1
and
C., = minft E I+ F A,-1 and t > Co.k? for any positive integer k. As can be seen from these definitions, the interval (Cb,e, Co describes the 1tth cycle. We also define MT) and S:(T) as follows
M.(T)
Σ t=1
1 1(A = i,t = Co,p or Ce,k for some k)
and
T
S,(T) Σ 1 1(4, -,4=itt= Co.k or Co.k for some k)Y,,
Here (T) denotes the number of cycles in which the tth action has been selected, while (T) the sum of rewards the agent received from playing the ith action at either the beginning or the end of cycle over the duration T of the experiment. Note that whether the condition {t Co,6 or Ce.k for some k} is satisfied or not can be verified by checking the actions taken until the time step t, i.c. {A,} We also define b(t) max(j Zzolt 2 T3} as the index of the

---

last batch, and (()) min E 2+ S Tj} as the batch index of the tth time step. We provide pseudo-code for our Batched Thompson Sampling policy in Algorithm 1.
Algorithm 1: Batched Thompson Sampling
Input: Batch growth factor 1, Gaussian variance o²
Initialization: t = 1, M2( = 0, S() = 0, U = 1, 1, 10 =0.
while Experiment Run do
Sample for Each Arm: 0;(1) ~ (T+M. I+M,(T,-1))
9.(Ti-1)
o²
Play an Arm: A, arg max, (t)
Update the Pull Count: Mt(t) <- Mt - 1) I(A, i, Cb. or Co. for some k))
if Ce.ffor some & & M,(1) = U2 for some then
End the Current Batch: T =
Receive the Rewards: {Y (YA..J) 1+
Update the Cumulative Rewards for Each Arm:
S,(T,) (TT)-1)) Ei 1(A -, Co, or Ce.k for some Y)Y,,
Update the Upper Limites for the Cycle Counts: U = max(1, Ja x M, (T,))
Update the Batch Index: j f- j
end
Update the Time Index: t <- & ++1
end
Note that in Algorithm the posterior distribution from which each arm is selected depends only (Tue))) S; [ that we only use the rewards from the first and last action selected in each cycle and ignore the rest of the observed rewards. This is to simplify the analysis in the following sections. However, we can also apply the algorithm by incorporating all the observed rewards, which in general can yield better performance while still maintaining the same batch structure. In that case, (1) for any / in the jth batch is drawn instead as
T--1 1(A = i)Y,
(1(1) ~ N
1+ N+T,() N+N.
4
Main Results
In this section, state the main results of our paper. We start with the regret performance of Batched Thompson sampling.
Theorem Consider the batched armei bandit setup described in Section 2. IfT and the batch growth factor a satisfies < a S so² then Batched Thompson sampling obeys the following inequalities
4
log(T)
E[N < 01
(2)
A?
for any i 2 2, which lead to
K
log (T)
B[R(T)) < 0ia02
(3)
A
1=2
and
E(R(T)) S C2Ø VKKTlog(T) log(T)
(4)
where C1, C2 2 1 are absolute constants independent of the system parameters.
We provide the proof of this theorem for the special case of K 2, a = 2, o² 1 in Section 6. and defer the proof of the general version to the supplementary materials.
Theorem states that Batched Thompson sampling achieves O(log(T) > A, problem- dependent regret and O O(KKT log(T") minimax regret, which match the asymptotic lower bound of ((log(T)) [18] and the minimax lower bound of ((VKT) [3] up /lo((T) term respectively.
5

---

We next compare our bounds with the results on classical Thompson sampling [2]. As described in the previous section, we use Gaussian priors for Thompson sampling following the work of Agrawal and Goyal [2]. This is one of the two priors considered in that work for Thompson sampling: beta priors and Gaussian priors, For Thompson sampling with Beta priors, Agrawal and Goyal [2] provides two different bounds on the expected regret:
lTg(T") d(ss, (11)
K
E[R(T)] S (1++)
A + 7
(5)
for any e E (0, 1). and
[[R(T)) S O( KT (og())))
(6)
where d(ws, 11) μ4 log( m1) M1
(1 24) log( ( In addition, they show that with Gaussian
priors the expected regret of the classical Thompson sampling is bounded by Olv llyKT (
if T 2 K. Considering that d(p;, /1) > 2 by Pinsker's inequality, (5) provides a tighter performance guarantee than (3) in terms of the dependence on the reward distributions, but we note that the minimax performance of Batched Thompson sampling, (4), matches the performance of classical Thompson sampling when the agent receives instantaneous feedback about rewards and can update its policy after each action. These results show that Batched Thompson sampling, apart from the dependence on the reward distributions in the problem dependent bound, matches the regret performance in the classical case.
We note that the regret bounds in the theorem depend on the batch growth factor a. The regret increases linearly as grows bigger; this is not surprising since bigger batch sizes mean fewer updates for Batched Thompson sampling.
We now present the batch complexity results for our algorithm.
Theorem 2. Consider the batched multi-armed bandit setup described in Section 2. IfT 2 2 and 1 < a <
5a² 4, then the batch complexity B(T) of Batched Thompson sampling satisfies the following:
T
B(T) < 1+ K + K loga (1
K
K
log
log (T)
B[B(T)) 11+ K + log, (1 + Cao 2
log, (1 + Cao
and (8)
A
log(T)
E[B(T)] S 1 2Cao²
where C an absolute constant independent of the system parameters.
Theorem 2 states three different batch complexity guarantees; the first is deterministic guarantee on the number of batches while the last two bound number of batches in expectation. we consider (7), we see that Batched Thompson sampling uses at most Ollog(T)) many batches regardless of the reward distributions. This result and Theorem 1 indicate that Batched Thompson sampling matches the regret performance and the batch complexities of optimal problem-depenndet batched algorithms developed [4. 10, 9, 15J, which also achieve O(K log(T)) problem-dependent regret with OloggTT)) batch complexity. However, compared with the other optimal algorithms, we show that we can further reduce the expected batch complexity down to O(K log lT'( in (8). This is because our batching strategy uses the information it gathers about the system (through the notion of cycles) to adaptively decide on the sizes of the batches while most prior batched algorithms use a static batch structure. We note that Algorithm of Esfandiari et al. [9] does strategy however that strategy appears to be geared towards obtaining a tighter regret bound rather than reducing the batch complexity.
adaptive batching
We note that the bounds on the number of batches in (7) and (8) diverge to infinity as a J. 1. The bound in (9) the other hand decreases with and can be relevant when a is chosen very small. We also note that if a < 1+ for fixed T, then Batched Thompson sampling will only allow one cycle per batch throughout the experiment of duration T and the notion of a batch will coincide with the

---

notion of a cycle. In this extremal case with one cycle per batch, (9) shows that Batched Thompson sampling will have (T)) batch complexity, while still satisfying the regret bounds stated in Theorem 1. The (KK log (T)) bound on the expected batch complexity in (8) is enabled by the fact that for larger a we allow for exponentially more cycles in each batch. As the algorithm proceeds and becomes more confident about the system, choosing suboptimal arm becomes less likely and as a result the cycle durations become inherently larger. At the same time, the algorithm allows for exponcntially more cycles in cach batch. This double batching strategy in our algorithm, via cycles and batches is key to obtain O(K log log(T)) guarantee in (8) with an anytime strategy. Note that the best previously available guarantee batch complexity for an anytime batching strategy is O (T)g)
The proof of these theorems are provided in Section 6. The main technical novelty in the proof comes from the fact that the notion of cycles leads to random duration for each batch without any deterministic upper bound on the number of times each arm is played in the batch. This makes it more difficult to control the regret accumulated during a given batch. We note that without the notion of cycles (e.g. when a cycle corresponds to pull of arm) the exponential increase in the number of arms per batch is relatively casy to deal with, as in this case we have a deterministic upper bound on the number of times cach arm can be played in a given batch.
Experiments
In this section, we provide some experimental results on the performance of Batched Thompson sampling where we do not skip samples, i.c. the variant mentioned al the end of Section 3, for different values a, {1.00001, 1.25, 1.5, 2). and how they perform against normal Thompson sampling under different reward distributions and action counts when time horizon I' = 5 x 10 and the sampling
variance 2² 1. We mainly consider four setups: Bernoulli rewards when K 2, Figure (a); Bernoulii rewards when K 5. Figure 1 (b); Gaussian rewards when K - 2, Figure 1 (c); Gaussian rewards when K 5, Figure (d). Finally each figure is the result of an experiment averaged over 10t repeats and the average number of batches used throughout the experiment is rounded up to the nearest integer and reported in the parenthesis to the right of the algorithm names on the figures. The figures show that our batching strategy matches the performance of classical Thompson sampling by using roughly 100 batches over a time horizon = 5 x 10
As can be seen from Figure 1, Batched Thompson sampling achieves almost the same empirical performance as the normal Thompson sampling when we set a small enough so that there only one cycle per batch, i.c. a 1.00001. We also observe that this Batched Thompson sampling version 1.00001, can have batch count as small as 15. However when a is very small, the problem independent guarantees in (7) and (8) become very loose and the number of batches can vary more with the reward distributions. This can be partly observed in the figures: for a = 1.00001, there larger variation in the average batch complexity across different reward distributions though in all cases the average numbe of batches remain very small. Increasing a leads to more stable batch complexity behavior, at the cost of a small multiplicative regret factor; we observe that the batch count almost remains constant for a = across different reward distributions. The source codes of the git.
experiment can be found in https:/ /gi thub. http///cccmm/aaacchce/oopppsssss
6 Technical Analysis
In this section we provide technical proofs for results. We start with the proof of Theorem I for special case and at the end prove Theorem 2.
6.1 Proof of Theorem 1 when K = 2, a = and 0² = -1
We first introduce (t. as the number of times the second arm is pulled if Batched Thompson sampling is employed for t many round with the past knowledge of Hr 1- In this case, N2, Ty-1)= = (T, - (T) We know that in the first T rounds, there can be no more than many batches, and each batch can not last longer than T rounds. As a result, we have the following bound
7

---

85tthed 2..00---- 28
120
80tohed
bonchest
Botthed
80tched
102
5,0023
25-
23
logoor
log20111
(a) V1,r BBem)(0775), Y2,, BBem(00225
(h) V1,+ ~>Brn(0.75) Vú, Bem((..25) S i
butches!
phai: (S000) barches)
Nontrll (10000 baaches)
The Dwwrage AT7
The Dowrsoo
40
10-
bqcom)
DESOIT
(c) Y1,: NV1,1) 1), Y2, ~ (0,
(d) YL, ~ (11, 1), Y.. ~ N(0, 1) 2 iss
Figure 1: Empirical Regret Performance of Batched and normal Thompson sampling
on N2(T):
T
(2
min(N2. T5-1), N2) j=1
Now we first analyze the expected number of times the second is pulled in the first cycle of the jth batch. is easy see the time the first arm selected in this cycle an upper bound on the number of times the second arm is picked. This observation follows from the fact that if the first action is selected in the first round, then the second is selected only once in the current cycle, if not the time the first arm is selected becomes one more than the number of times the second arm is picked. As result, conditioned on the past Hr,-,, the expected number of times the second arm is picked in single cycle is upper bounded by F(A 100y-1+11111pp J. Also note that since there are only two actions,
cach cycle will contain both of them, and in the first j batches, there will be 2 many cycles by the construction of Algorithm 1. This observation means that there are no more than 2 many identically distributed such cycles in the jth batch, and we have the following bound for any j:
(T, Tj-1)l < 20-1 -E
P(ATT- = 1 Hr,..) S C2
(10)
where > a constant independent of j. The last inequality in (10) follows from the following Lemma 3 and the fact that in the first batch IP(Ar,-1) -+1 (T,-,) P(Ai = =
Lemma 3. If K = 2, a 2, and o² = 1, then any j 2 2:
E
C,
(11)
P ((A, = H
24-4
P P(A -14 =2) s exp(
A2)
(12)
3
8

---

where C 2 2 is a constant independent of j-
In addition, we also have:
2
TP(
exp(
A3)
(13)
3
for j by the same lemma. The overall analysis shows that for any positive integer k, have:
T
E (T) & E
min min(N2,,T,
S > E
-T--)) +
(T))
T
2/-1
S 5C(2 1) +
exp(
A3)
(14)
3
Ø=
where the last step follows from (10) and (13). Let & be the smallest positive integer such that log(T) Then we have
2
8
A
T
2
T
exp(
A
S T
exp(-
-2
A
S T
exp( -2 log()))
3
3
j=b+1
1=0
==0
T 2
1=0
where the last inequality follows from the assumption that 7 This analysis bounds the last summation term in (14). To bound C(2* 1), note that k is the smallest positive integer bigger
than log2 (24 (og(T)
Since A < and 2 2, we know 24 log(T)
A N 1. This analysis shows that
k < loga (24 log ++ = log2 (48 (T) ). As a result, C(2* - 1) < 48C 48C log(T). The overall analysis A shows that E[R(T)] A₂ 12 (T)]
A3
48C log(() 2Ag by (14). This finishes the proof of (3).
A2
Finally (4) is proven by (3) if A2 proves (4).
log(T) If not, then [[[ s TA2 (Tlo'("), and this
6.2 Proof of Theorem
Let us consider the case where the agent has already employed the Batched Thompson sampling, Algorithm for 7' many steps and denote ij 21, (T)) 1} for j 21, ki} as the indices where (T,)) = Uniy. Since each batch end point T, has to satisfy the condition M((T)) = U1, for some we have
K >
B(T) - 15
(15)
By the definition of U..: know that MT,T,) 1. In addition, note that there may be batches in between 1th and 2tth ones and the agent may have picked the tth arm while the condition MT(T)) U2 is not satisfied. These observations lead to max,o.M,TT, ), MT + +1 S M,(T,,) for j 2 2. The overall analysis shows that if > 1, then k < M,TT,,) < (, due to the fact that T.,, S TB(T) which leads to k; S log. (1+ M((TB(T) 1)) for any k; 2 0. In addition, we also have the following trivial bound k; S (T.,...) S ((TTB(T)-I). a result of these incqualities and (15), we have
K
B(T) $1+K K
log, (1 + (c(TB(()11)
(16)
and
B(T) < 1+
M((Te(D-1).
(17)

---

First of all, since log()) is a concave function, Jensen's inequality and (16) lead to
B(T) K loga (1
Σ M((TB((--1)) K
(18)
Considering that each cycle has contain least two action steps, there can be no more than L many cycles in the first B()) batches. In addition, each cycle can only be recorded once by two different actions. This observation leads to Σ Mi(TB(T)-1) S T, which proves (7) by (18). To prove (8), we first nole that M1 (T < Ex= (,(TB(r)-)) because cach cycle of the first arm has to be accompanied by another arm. Since (,TTB(T--) S NT(T) for any i, we have K
K BTT) < 1 K loga (1 Σx N.) Ex= log, (1 (T)) by (16), which shows that
(T)(T)] < <Bi1 K log (1 +
(.)T)) + Σ
log. (1 + (T))
i=2
S 1 K log, (1 +
Σ
B(N((T) + log, (1 E[))
The last inequality follows from Jensen's 's inequality. This leads to (8) by the fact that (E(N.()) <
Coaa log(?) from (2). Finally, the previous analysis also implies that B(T) S 1 + Σ (T) by of
(17). This inequality and (2) prove (9).
7 Conclusion
We proposed an anytime Batched Thompson sampling algorithm and proved that it achieves the optimal wroblem-dependen and minimax regret with only (log(TT) instance-independent batch complexity, matching the state-of-the-arr anytime batched algorithms. More interestingly, we showed that in a given instance the problem our algorithm requires only Ollog log(T)) batches on average, which corresponds to doubly exponential decrease in the interaction needed with the environment as compared to the classical case. To the best our knowledge, previous anytime algorithms only satisfy worst-case (log(T)) guarantee on the batch complexity. Finally, simulations show that Batched Thompson sampling performs empirically close to classical Thompson sampling by using drastically fewer batches.
Acknowledgements
This work was supported in part by a Google Faculty Research Award, and the National Science Foundation under grants CCF1704624 and NeTS-1817205.
References
[1] Mare Abeille, Alessandro Lazaric, et al. Linear thompson sampling revisited. Electronic Journal of Statistics, 11(2):5165 5197, 2017.
[2] Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
[3] Jean-Yves Audibert, Sébastien Bubeck, et al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256, 2002.
[5] Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't 't do for multi-armed bandits. arXiv preprint arXiv: 18x::0800000777 2018.
10

---

[6] Nicolo Gesa-Bianchi Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, pages 1 1160-1168, 2013.
[7] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249 2257,, 2011.
[8] Rick Durrett. Probability: theory and examples, volume 49, Cambridge university press, 2019.
[9] Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. arXiv preprint
019994999 2019.
[10] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In Advances in Neural Information Processing Systems, pages 503-513, 2019.
[11] Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu
Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint (XXiv:200406332/1 2020.
[12] Wassily Hoeffding. Probability incqualities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409-426. Springer, 1994.
[13] Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double exploretthen-commit: Asymp- totic optimality and beyond. arXiv preprint arXiv:2002.09174, 2020.
[14] Cem Kalkanhı and Ayfer Özgür. Asymptotic performance of thompson sampling in the batched multi-armed bandits. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 539-544. IEEE, 2021.
[15] Amin Karbasi, Vahab Mirrokni, and Mohammad Shadravan. Parallelizing thompson sampling. arXiv preprint arXiv:2106. 01420, 2021.
[16] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
[17] Nathaniel Korda, Emilie Kaufmann, and Remi Munos. Thompson sampling for 1-dimensional exponential family bandits. In Advances in neural information processing systems, pages 1448 1456, 2013.
[18] Tze Leung Lai and Herbert Robbins. Asympiotically elficient adaptive allocation rules. Ad- vances in applied mathematics. 6(1):422, 1985.
[19] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg, et al. Batched bandit problems. The Annals of Statistics, 4462)6660-611, 2016.
[20] Zhimei Ren and Zhengyuan Zhou Dynamic batch learning in high- sigh-dimensional sparse linear contextual bandits. arXiv preprint arXiv:2008. 11918, 2020.
[21] Zhimei Ren, Zhengyuan Zhou, and Jayant Kalagnanam. Batched learning in generalized linear contextual bandits with general decision sets. IEEE Control Systems Letters, 2020.
[22] Yufei Ruan, Jiaqi Yang, and Yuan Zhou Linear bandits with limited adaptivity and learning distributional optimal design. arXiv preprint 20070:2007.01980, 2020.
[23] Daniel Russo and Benjamin Van Roy, Learning to optimize via posterior sampling. Mathmatics of Operations Research, 39(4): 12: 1243- 2014.
[24] Daniel Russo and Benjamin Van Roy. An cetemattion-thhoreee analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):24422447, 2016.
[25] Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
[26] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[27] Roman Vershynin. High-dimensional pwwpaiiiiliiooobiiibibib.l... 2019.
11


Reviews:
[{"review_id": "vVxqz8nMeoj", "reviewer": "Reviewer_jTWC", "summary": "The paper tackles the batched multi-armed bandit problem, where arms are played in batches and feedback is obtained by the end of each batch. The authors suggest the Batched Thompson-Sampling algorithm, an anytime TS algorithm with Gaussian priors that are updated at the end of adaptive batches. The adaptive mechanism for the batch sizes is based on a doubling trick – a batch ends once the number of switches from/to some arm is doubled (or increases geometrically). The authors prove that the batched feedback degrades the regret only by a constant factor and show that the number of batches is logarithmic a.s. and is $O(\\log\\log T)$ in expectation, for fixed gaps and large enough T.\nThe authors claim that this work is the first to achieve tight problem-dependent and independent regret bounds with a batch number that adapts to the specific instance ($\\log T$ problem independent and $\\log\\log T$ problem-dependent batch number).", "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": "Overall, I think that the paper has two interesting contributions. First, the cycle (arm-switch)-based doubling trick, which might be extended to other algorithms for adaptive batch-sizing. Second, the application of TS to the batched MAB problem. However, there are a few issues with the results that the authors did not discuss.\n\nOne main issue is the guarantees on the number of batches. First, in previous works, the $\\log T$ #batches regime was required for the problem-dependent regret bounds while $\\log\\log T$ batches were required for the problem-independent regret bounds, which are mainly relevant for smaller gaps. However, in this work, the $\\log\\log T$ batch-bounds are achieved only when the gaps are large. For example, when $\\Delta\\approx1/\\sqrt{T}$ (which is the interesting regime for problem-independent bounds), the batch number is of order $\\log T$ and not $\\log\\log T$, as in previous works. In a sense, this means that the result is not a ‘best of both worlds’ result, as might be implied from its description, but rather a compromise in the problem-independent regime and (possibly) an improvement in the problem-dependent regime.\n\nA natural follow-up issue regards the relation between the upper and lower bounds for the number of batches, a comparison that was not done in this paper. In [10], the authors proved $\\log T$ and $\\log\\log T$ lower bounds for the batch number in the problem-dependent and independent regimes, respectively. Seemingly, the problem independent performance is loose, while the problem-dependent one violates the lower bounds. This isn’t necessarily the case, as the gap-dependence in the lower bound is not entirely clear, but I expect the authors to discuss and justify it. Similarly, the authors should emphasize that some of the guarantees in this paper are weaker than ones in previous work, as they only hold in expectation and not a.s. (e.g., when comparing the a.s. $\\log\\log T$ guarantees). Namely, the gap dependence comes at the price of a weaker type of guarantee.\n\nFinally, the authors assumed that the optimal arm is unique. In many cases of TS proofs, this is a technical assumption that simplifies analysis (and coupling arguments allow removing it, e.g., Agrawal and Goyal, 2012). However, in this work, it might completely break the batch division mechanism, as there would be many short cycles with two optimal arms. In particular, I believe that both expected bounds on the number of batches would not hold in this case. If this is indeed the case, it should be clearly reflected and justified in the paper, and in my opinion, it greatly weakens the results.\n\nOther comments:\n- I didn’t find the explanation on the usage of Gaussian priors, in contrast to Beta priors, very convincing (is there no gain in using KL-UCB vs. UCB1?) - is there a better reason (possibly a technical one)?\n- Simulations: an interesting missing statistic is the maximal number of batches in each scenario. Moreover, I think the evaluated algorithm should be the one in which the bounds hold.\n- In my opinion, it would be beneficial to add a summary + discussion (e.g., on all previously mentioned issues) by the end of the paper (for example, instead of the simulations of the Gaussian case, that I think that can safely move to the appendix).\n\nMinor comments:\n- Line 62 – minimax optimal up to log-factors\n- Line 120 – an batching -> a batching\n- Line 143 – min -> inf\n- Looking at the proof of (7), isn’t there a (+1) missing inside the log?\n- Lines 218-220 – add commas.\n- Line 256 – the second -> the second arm\n- Checklist I -> we\n\n\nReferences:\n\nShipra Agrawal and Navin Goyal. 2012. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory (COLT’12)\n\n#########\n\nI thank the authors for the response. I decided to leave my score unchanged.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, the authors did not adequately discuss the limitations in this work – see all previous comments on the guarantees on the batch number.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "O1Nll2875zc", "reviewer": "Reviewer_HuxN", "summary": "This paper studies the Thompson Sampling policy for the batched multi-arm bandit problem. The policy only collects the reward at the end of each batch, while the endpoints of each batch are at the discretion of the policy. Both the adaptive and the minimax regret bounds are given, and the bound on the number of batches is also given. The proved bounds are comparable with the bounds of the successive elimination algorithms for batched multi-arm bandits, which shows Thompson Sampling is equally comparable for the batched bandit problems.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Given the batched bandit problem and the batched successive elimination policy in previous works, it is a direct association to consider how well Thompson Sampling performs under the batched setting. This paper answers this question by proving that the batched Thompson Sampling can achieve comparable regret bound as its instantaneous counterpart. The bounds are also comparable with the successive elimination policy in previous works.\n\nThe paper is clearly written and easy to read, while the proof of Theorem 1 in the supplementary is a bit difficult for me to follow. It would be helpful to provide a bit more explanation on the decomposition from Equation (74) to (79). \n\nThe technical originality is not well highlighted. Given the previous works on batched bandit problem and the fact that Thompson Sampling is well studied before, the relation between this paper and the previous ones is not very clear. This might lead to an impression that this is rigorous work yet without much technical novelty.  For example,  the analysis seems to heavily rely on the geometrical grid, which is also used in previous works like [10] Gao et al. How original is the proof technique used here given the previous work?  Another concern which I am not quite sure about is that the proposed algorithm follows [2] Agrawal and Goyal. What is the relation between this paper's analysis and [2]'s. Some clarification in terms of technical contributions aside from the algorithmic design and performance advantage would be helpful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors compare their algorithm with previous ones and show the advantages over others.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "J1ArZsuO3IW", "reviewer": "Reviewer_7wHj", "summary": "The paper addresses the problem of K-armed bandits in a batched setting. In this setting, the entire time duration is split into small batches and the feedback is received only at the end of each batch. The authors design a batched version of Thompson sampling, where the batch duration is set adaptively based on the past data. The author analyzes the proposed algorithm under Gaussian reward distribution and provides a problem-dependent O(log(T)) regret bound, as well as O(\\sqrt{T}) minimax regret bound. The number of batches used is shown to be O(log(T)) in the worst case and admits O(log log(T)) amortized problem-dependent bound.  The authors validate their theoretical results using synthetic experiments. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n - The proposed algorithm that adapts the batch size based on how many times the arms are played in the past is novel. They introduce a notion of the cycle -- a series of rounds with exactly two distinct arms. A batch ends when, for any arm, the number of cycles that arm is played in the batch is \\alpha times the number of cycles that arm is played before the batch. \n\n- The regret analysis builds on the proposed adaptive batching. It also uses the fact that the prior for arm rewards used in Thompson sampling remains unchanged during a batch. The amortized problem-dependent batching analysis is also novel.\n\n- The writing is clear although the use of notations can be a little overwhelming at times. \n\n- The paper mentions the relevant works to the best of my knowledge. \n\n\nDrawbacks and Suggestions:\n- A discussion on the tradeoffs of setting alpha close to 1 or away from 1 will be useful.  \n\n- A discussion on how the regret analysis with K=2 will be extended to K > 2 in the full proof will be insightful. With the cycle structure, the transition from K=2 to K > 2 seems non-trivial.  \n\n- The experiments are not run for long enough time, as evident from the linear regret shape. I suggest running the algorithm for enough time to obtain the log(T) shaped curve and use logscale for Y-axis. \n\n- In Theorem 1 and Theorem 2 please specify that \\alpha > 1.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is theoretical in nature, and the scope for negative societal impact seems very limited. \n\nThe authors may highlight the limitation of adaptivity in designing the batch size in practice. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "3SSqwqEtfs7", "reviewer": "Reviewer_WhRh", "summary": "This paper studies the classical stochastic multi-armed bandits with batches. While the classical problem assumes that rewards are received after each decision step, here the authors consider batches: the decision maker takes a batch of decisions and then observes the rewards at the end of the batch. The next batch of decisions is then taken based on this feedback.\n\nThe authors derive an algorithm that uses a limited number of batches ($O(\\log(T))$ of $O(\\log\\log T)$ for a problem-independent or dependent bound) while providing an order-optimal regret ($O(\\sqrt{T\\log(T)})$ or $O(\\log(T))$ for problem-independent or dependent bound). The algorithm is based on Thompson sampling and uses a careful definition of batches.\n", "questions": "", "limitations": "", "rating": 6, "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": "I liked the setting and the results presented in the paper. The motivation behind batched-feedback is clear and well explained in the paper. The references to related work seem good. I did not look at the detailed proofs but the approach seems good.\n\nI am quite impressed (and also a bit puzzled) by how the batches are constructed. This seems to be the main difficulty of the paper. If I understand correctly, the authors define batches so that they are bigger when an arm is well identified as being optimal. When multiple arms are considered equivalent by the algorithms, the cycles will be shorter which means that batches will also be smaller. What bothers me a bit in this paper is the complexity of the approach: instead of using Thompson sampling and the very complex definition of cycles, would not it be simpler to use confidence intervals to define a deterministic batch duration?\n\nAlso, the algorithm uses a sort of internal feedback because the definition of a cycle uses the sequence of actions taken. This is not a problem in a centralized setting because only the decision taken by the algorithms are requested but not the observed reward. Yet, in a distributed setting (used as a motivation in the paper), this might be problematic. Here again, a simpler definition of batch lengths might be useful.\n\nLast, the authors present two versions of their algorithm: (1) with feedback only at the end of each cycle, or (2) with feedback at every time-step. The authors analyze (1) in theory but present experimental results only for (2). I imagine that the variant (1) performs much worse in practice. This could be studied: how much worse? How many samples are \"saved\" by doing so?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The complex definition of the batches and the potential difficulty in implementing it might be worth discussing.", "review_text": "", "extra_scores": {"ethical_concerns": "NA.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose an interesting batch Thomson Sampling algorithm that achieve the optimal regret with $O(\log T)$ and $O(\log\log T)$ number of batches in instance dependent and instance independent settings. I very much like the results and propose acceptance. 

I would like to bring the authors' attention to two concurrent work on the exact same topic:

"Parallelizing Thompson Sampling", https://arxiv.org/abs/2106.01420
"Batched Thompson Sampling for Multi-Armed Bandits", https://arxiv.org/abs/2108.06812

I propose the authors discuss the abovementioned work in the final version of their paper to highlight the differences in algorithm design and the corresponding results. I believe it adds to the value of their work. 

Decision: Accept (Poster)