Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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

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.

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

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

Last, 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?

limitations_and_societal_impact: The complex definition of the batches and the potential difficulty in implementing it might be worth discussing.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

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

The 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.
limitations_and_societal_impact: The authors compare their algorithm with previous ones and show the advantages over others.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
The 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).
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.

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

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

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

Other comments:
- 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)?
- 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.
- 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).

Minor comments:
- Line 62 – minimax optimal up to log-factors
- Line 120 – an batching -> a batching
- Line 143 – min -> inf
- Looking at the proof of (7), isn’t there a (+1) missing inside the log?
- Lines 218-220 – add commas.
- Line 256 – the second -> the second arm
- Checklist I -> we


References:

Shipra 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)

#########

I thank the authors for the response. I decided to leave my score unchanged.

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_title: null

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

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

- The writing is clear although the use of notations can be a little overwhelming at times. 

- The paper mentions the relevant works to the best of my knowledge. 


Drawbacks and Suggestions:
- A discussion on the tradeoffs of setting alpha close to 1 or away from 1 will be useful.  

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

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

- In Theorem 1 and Theorem 2 please specify that \alpha > 1.

limitations_and_societal_impact: The paper is theoretical in nature, and the scope for negative societal impact seems very limited. 

The authors may highlight the limitation of adaptivity in designing the batch size in practice.
review_title: null

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)