Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the arm sampling behavior of UCB and Thompson sampling algorithms. For the two-arm case, the asymptotic behavior of arm sampling is characterized for different regimes (small, large, and medium) of suboptimality gap. Using this characterization, the minimax regret of UCB is shown to O(n\logn), where n is the time horizon. They highlight the incomplete learning phenomenon in Thomson sampling where sample-split could be arbitrarily imbalanced along a sample path even when both the arms have the same mean.
main_review: The paper highlights the important aspect of arm sampling distribution in the Multi-armed setting. The author nicely built the imbalances in arm sampling through examples for both UCB and Thompson sampling. The insights from the analysis highlight the 'incomplete learning' learning aspect in Thompson sampling.

I have the following question for the authors: 

Theorem 1: The result holds aysmptotically and $\Delta$ (problem instance) is changing with $n$. After $n$ rounds (sufficiently large), we expect UCB to have played the optimal arm exponentially more time than the sub-optimal arm. But the asymptotic result suggests that this need not be the case if $\Delta \rightarrow 0$ as $n \rightarrow$. Can anything be said about the arm-sampling distribution for a fixed instance $\Delta$. The asymptotic result is good, but since we also know finite time behavior, it is nice to connect.

Theorem 2: What does the symbol $\implies$ denote (convergence?). The statement assumes $n\rightarrow \infty$, but the Proof Sketch says for any $n \in \mathcal{N}$, which one is correct.

Theorem 3: Does the result hold with weaker condition $\Delta \rightarrow 0$ Instead of thanking $\Delta \sim \sqrt{\frac{\theta \log n}{n}}$.

Overall nice paper. Good insights. If authors could highlight the practical implications of their results, it could be nice. For example, is incomplete learning of Thompson Sampling good or bad. When should UCB be preferred over Thompson sampling and vice versa?
Does the incomplete learning aspect explain why Thompson sampling often performs better empirically in practice?

I would be happy to revise the scores post rebuttal. 
-----

Post rebuttal:

Thanks for clarifying some of my points. I have increased the score to 7.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the asymptotic behavior of arm-sampling distributions under the UCB and the Thompson sampling. They provide an asymptotic characterization of the distributions, and show the arm sampling rates asymptotically deterministic regardless of the hardness of instances. With this characterization, focused on canonical UCB algorithm, they provides the first algorithm-specific worst case bound and the first diffusion-limit performance.

main_review: 
Originality:
To the best of my knowledge, this is the first work to provide algorithm-specific result (Theorem 3). Also, it is interesting that they provide another view of proving the worst-case performance of UCB using a diffusion scaling approach (Theorem 4). Although the paper is not the first work introducing the diffusion scaling to bandit problems, it can deal with more standard bandit algorithms. As for the originality of proof of Theorem 4, proof techniques seem to be similar to that of [25]. Is there any difficulty to apply a diffusion scaling technique to more standard bandit algorithms?

Quality:
The proposed theorems seem to be technically sound. The authors honestly discuss about the strengths and weaknesses.

Clarity:
The paper is well-written and provides appropriate examples. I can easily follow the motivation. Since the diffusion scaling is a key technique of the main contribution, more descriptions about it helps us to understand the details of the contributions.

Significance:
As written in the originality, the provided results are the first works, which is the significant point of the paper. Since the works include some limitations that deals with two-armed bandit settings, it is an important first step to explore other bandit algorithms and settings .

limitations_and_societal_impact: A limitation of that paper is to deal with two-armed bandit settings, but as described in the concluding remarks in the paper, it may be generalized K-armed bandit. So, I think the contributions outweigh this drawback.

I found the following researches that also consider the asymptotic regime using a diffusion approximation. It would be better to add some if possible.

References:

[i] Keisuke Hirano and Jack R Porter. Asymptotic representations for sequential experiments. Cowles Foundation Conference on Econometrics, 2021

[ii] Fan, Lin, and Peter W. Glynn. "Diffusion Approximations for Thompson Sampling." arXiv preprint arXiv:2105.09232 (2021).

[iii] Araman, Victor F., and Rene Caldentey. "Diffusion Approximations for a Class of Sequential Testing Problems." arXiv preprint arXiv:2102.07030 (2021).
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper studies the asymptotical behaviors (with respect to the suboptimality gap $\Delta$) of key statistics in the standard upper confidence bound (UCB) algorithm in standard multi-armed bandits (MAB). The contributions are as follows.

1. The paper proves that the **asymptotical arm-sampling rate** converges to a constant, and gives its **analytical form** (Eq. 2). In particular, the paper discovers a non-trivial "**moderate gap**" regime for UCB. 
2. The paper proves an asymptotic regret lower bound for UCB **up to $(1 + o(1))$**  in two-armed bandits. 
3. The paper proves that the **asymptotical empirical sum** converges to a Brownian motion for UCB in two-armed bandits.
4. The paper proves the asymptotical arm-sampling rate for Bernoulli Thompson sampling in two-armed *deterministic* bandits. 
5. The authors extend their results to MAB.
main_review: 
While asymptotical analyses are common in statisics and EE (e.g. mean-field asymptotics), it is not common in CS and rare in bandits literature. Asympotical analyses are important because it could help both researchers and practitioners better understand the algorithmic behaviors, because non-asymptotic analyses are usually not as exact and precise as their asymptotical counterparts. 

This paper studies two-armed bandits, the classical and fundamental task in bandits literature, and analyzes UCB, the classical and fundamental algorithm in bandits literature. The most important statistics maintained by the UCB algorithm are the number of times of each arm being pulled and the empirical sum of each arm. For these two statistics, the paper provides exact asymptotical characterization under the simplest two-armed bandits case, which clearly distinguishes this paper from previous papers. The results are significant and set up seminal directions in bandits literature, and could benefit subsequent researchers, including myself. I believe the related works are cited adequately. 


The paper is very well-written. The maths are easy to read and can be clearly verified in a step-by-step manner. I went through Appendices E and F (which contains main technical proofs) and did not find apparent errors. The authors are honest about their weakness about their results in the final section. 

The paper almost completely depicts how standard UCB works in two-armed bandits. The results on other tasks such as multi-armed bandits and other algorithms such as Thompson sampling are, however, still premature. Further will be discussed in the limitations section. Nonetheless, given the novelty, quality, and clarity of this submission, I vote for a strong accept.
limitations_and_societal_impact: 
### Limitations

1. The authors' notations confuse me, in that it's not clear that *which limiting regime* the authors are discussing. It seems to me that Theorem 1 is stated for a sequence of two-armed bandits instances, i.e. for each $n$, there's an instance with parameters $(\mu_{1, n}, \mu_{2, n})$ such that $\Delta_n = \mu_{1, n} - \mu_{2, n}$ satisfies $\Delta_n \asymp 1/\sqrt{n}$, and that the $N_{i^*}(n) / n$ term in the result of Theorem 1 refers to the $N_{i^*}(n) / n$ in the $n$-th instance. The confusions exist at least for Theorem 1, 3, 4. Since asymptotical style results are not common in bandits literature, I recommend the authors to point out the asymptotical regime more clearly. 
2. The paper includes numerical experiments, so I think the section 3 in the checklist (Line 436) shall not be completed by "N/A", and the authors are encouraged to publish their codes, (though numerical experiments might be very simple).
3. The paper fails to fully extend the results (Theorems 1, 3, 4) to the MAB case. The two-armed case is limited from both theoretical and practical perspective. In particular, in the two-armed case, the arm pulling rates satisfy $N_1(n) = n - N_2(n)$, which makes it possible to fully characterize the bandits by only analyzing one statistics $N_1(n)$. However, in the multi-armed case, at least two statistics need be studied. The paper did not prove the most intriguing "moderate gap" part in the multi-armed case.  
4. The paper's results on Thompson sampling are quite limited, in that it only studies the deterministic case where rewards are constantly $0$ or $1$ for each arm. Although the authors somehow suggest that the results should extend to the stochastic setting by doing experiments (Fig. 1), I am still concerned about the results.  

### Other Comments

* Line 128: "diffuion-limit" should be "diffusion-limit"
* Line 144-145: The sentence almost repeats the same sentence at Line 137-138, same thing at Line 149-150; the authors need not repeat the claim of first characeterization three times in the same paragraph

### Societal Impact

The paper is mainly theoretical, and I don't see any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Classical bandit algorithms such as UCB and Thompson Sampling are well-understood in terms of their performance—for example, an upper bound on their regret—but, until recently, little attention has been given to their actual behavior—for example, the rates at which specific arms are sampled. This work seeks to address these questions by analyzing the arm sampling distribution achieved by both UCB and Thompson Sampling. They provide results characterizing these distributions asymptotically and, in addition, characterize the distribution of the rewards obtained by running UCB.
main_review: While the regret incurred by UCB and Thompson Sampling (TS) is well-understood, this work seeks to understand the actual behavior of these algorithms. It makes several contributions in this direction, all in the two-armed bandit problem (though some of the results extend to K arms). In particular, they characterize the:
- Asymptotic distribution of N_{I*}(n)/n achieved by UCB, where N_{I*}(n) is the number of pulls of the optimal arm up to time n, for various regimes of the gap.
- Asymptotic distribution of N_{I*}(n)/n achieved by TS but in a restricted regime where the rewards are deterministic.
- Precise regret incurred by UCB asymptotically, establishing that R_n -> c(\theta)*\sqrt{n log n} for some problem-dependent constant c(\theta).
- Distribution of the random process of the UCB’s reward and regret.

All results are asymptotic in nature (i.e. the number of samples n -> infinity). In addition, the authors provide several numerical examples illustrating that in practice UCB and TS can exhibit surprising behavior, and show that they are able to explain this behavior with their theoretical results.

Pros:
- This is a timely work. In the last few years, a significant amount of attention has been given to understanding the asymptotically optimal regret of bandit problems (e.g. [4]), as well as properties of UCB (for example, the bias in the estimates of the arm means maintained by UCB [1]). Very recently [5] studied the asymptotic sampling distribution of Thompson Sampling but, to my knowledge, no other works on this exist, though open questions still remain.
- The results are extensive and provide a full characterization of the behavior of the UCB algorithm, greatly deepening our understanding of its properties. The motivating examples help make clear that there are unusual and little-understood effects that occur when running UCB and TS.

Cons:
- The main results only hold for a two-armed bandit model, though they are partially extended in the appendix to K armed models (the restriction to two-armed bandits has precedence in the literature though, for instance [4]). 
- The results on Thompson Sampling only holds for deterministic bandits. Furthermore, [5] studies the asymptotic distributions of the arm pulls of Thompson Sampling and should be cited and compared against. 
- There’s a line of recent work ([1]-[3]) which aims to understand the bias of optimistic bandit algorithms. While not directly comparable to this work, it is related to the theme of understanding the behavior of bandit algorithms, and should be cited.
- Some discussion on the applications of these results would be interesting. For example, do these results motivate any improvements to UCB or other algorithms?

Overall, this is a thorough study of the performance of bandit algorithms, greatly deepens our understanding of both UCB, and warrants an accept. 

----------------------------

Update after rebuttal: I would like to maintain my score after reading the rebuttal. I believe this work makes fundamental, novel contributions to our understanding of bandits and deserves an accept.


[1] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. "Are sample means in multi-armed bandits positively or negatively biased?." arXiv preprint arXiv:1905.11397 (2019).
[2] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. "On the bias, risk and consistency of sample means in multi-armed bandits." arXiv preprint arXiv:1902.00746 (2019).
[3] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. "On conditional versus marginal bias in multi-armed bandits." International Conference on Machine Learning. PMLR, 2020.
[4] Kaufmann, Emilie, Olivier Cappé, and Aurélien Garivier. "On the complexity of best-arm identification in multi-armed bandit models." The Journal of Machine Learning Research 17.1 (2016): 1-42.
[5] Kalkanli, Cem, and Ayfer Ozgur. "Asymptotic Convergence of Thompson Sampling." arXiv preprint arXiv:2011.03917 (2020).
limitations_and_societal_impact: The authors do not discuss potential societal impact. However, the work is primarily theoretical so it is difficult to determine what negative societal impacts it may have. Limitations are discussed.
review_title: null

Meta-review: This is strong paper that I would like to see accepted as a spotlight. There is a minor criticism concerning the restriction to two arms but the reviewers feel that this is not a major concern. There are some suggestions by the reviewers of how to improve the paper further and it would be good if the authors could incorporate these.  
Decision: Accept (Spotlight)