Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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, 

* B-TS achieves the problem-dependent asymptotic optimal regret;
* B-MOTS achieves the optimal minimax problem-independent regret bound;
* B-MOTS-J, designed for Gaussian rewards, achieves both minimax and asymptotic optimality.

Moreover, a method named B-TS-C is also proposed applicable in the linear contextual bandit setting.

Finally, the proposed methods are compared with their fully sequential counterparts via experiements on synthetic and small real data.
main_review: **Originality**

This 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. 

**Clarity**

This 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.

**Significance**

As pointed out in the Summary section, in the stochastic multi-armed bandit setting,

* B-TS achieves the problem-dependent asymptotic optimal regret;
* B-MOTS achieves the optimal minimax problem-independent regret bound;
* B-MOTS-J, designed for Gaussian rewards, achieves both minimax and asymptotic optimality.

**Limitations**

B-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.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Two major paper strengths are that the paper is well written, and its strong theoretical and empirical results.

The 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). 

In 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:
- http://proceedings.mlr.press/v139/jun21a/jun21a.pdf (ICML'21)
- https://arxiv.org/abs/1906.08399 (NeurIPS'19)

On 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. 

Finally, 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.

Overall, 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.

Minor:
Thrm 5.1. Delta_a not previously defined in paper. 
Since 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.
For instance, you can include similar language to Jin et al 2020, in their paragraph immediately below equation (5) of their paper.



limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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. 
The 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.
I 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. 

Zhang, Z., Zhou, Y., and Ji, X. (2020). Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 

The 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. 

This 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.

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.

**Quality and Clarity**

I 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.

1. 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.

Let the equation between eq(6) and eq(7) be (6.5)

2. Please use $\mathbb{I}$ consistently in equation (6.5c) and (6.5d)

3. The inequality sign should actually be equal sign in (6.5d)

4. Eq(7) should use $p_{a, \tau_k + 1}$ instead of $p_{a, \tau_k} + 1$ in denominator. Same for Lemma A.11

5. The summation in the first inequality in Eq(7) should be from $0$ to $L_a(T)$ not from $0$ to $T-1$


**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.

1. 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. 

2. 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.
limitations_and_societal_impact: Yes. The discussion was adequate.
review_title: null

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)