Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new Thompson sampling algorithm by designing proper sampling distributions for exponential family reward distributions. Three contributions: (1) new algorithm (2) showing that the standard TS enjoys a $\sqrt{\log(K)}$ minimax ratio (without inflating the posterior distribution) and (3) a simple greedy trick to achieve a constant minimax ratio.
strengths_and_weaknesses: Originality: high

Quality: high

Clarity: high

Significant: medium-high

The key contribution, to me, is the novel analysis described around Eq 4.2. In fact, proving/disproving that the standard Thompson sampling (without inflating the posterior distribution, which breaks the asymptotic optimality) has the minimax rate of $O(\sqrt{\log(K)})$ was an open problem. Note Agrawal & Goyal (2017) have shown this rate with Gaussian TS but they in fact inflate the posterior variance by a constant factor. 

On clarity, I appreciate that the authors point out specific section/formula numbers from the references; not many people do this these days.

While the sampling distribution is novel, I am not entirely convinced that it is necessary, but at least it is a nice addition to the library of variations of TS. 
questions: * L168: missing a square for (mu-mu')
* L169-170: I did not follow why we are setting V(.) = 1/4. I mean, we don't get to choose V(.); it is given from the definition of a specific exponential family distribution?
* L209-210: I would remove the word 'a regret' there since it sounds like it is about the regret lower bound rather than the lower bound on $D_i$.
  * Furthermore, looking into Lemma 5 of Jin et al., it seems that D_i = \Omega(\sqrt{KT\log(T)}) is not correct (and rather a typo). It seems we need to say K D_i = \Omega(\sqrt{KT\log(T)}) ?
* It'd be great to have a figure showing plots of PDFs for the sample distribution.
* what's the role of b_n? Anything goes wrong if we set $b_n=1$
* How does the empirical performance of ExpTS fair with TS? 
* L254: "when n is large, we will choose b_n to be close to 0" ⇒ this contradicts to b_n in Theorem 4.1?
* L276-277: to claim that ExpTS is comparable to the best known UCB, we need to define the scope. For Gaussian rewards, AdaUCB has a strictly better guarantee than ExpTS.
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the regret of Thompson sampling (TS) for exponential family reward distributed multi-armed bandits, by addressing all its theoretical properties.

After a careful summary of their work, an informative related work Section 2 and necessary preliminaries in Section 3, the authors argue in Section 4.1. that the existing finite-time regret TS analysis based on the under-estimation of the optimal arm can be improved by introducing a lower confidence bound on such under-estimation.

To that end, they present a new decomposition of the regret that allows for a new approach to algorithm analysis and design. Specifically, they propose in Section 4.2 a sampling distribution that results in a variant of TS (denoted Exp-TS), with its subsequent frequentist regret analysis provided in Section 4.3.

The analysis simultaneously yields both the finite-time regret bound and the asymptotic regret bound: they prove that Exp-TS is the first algorithm to achieve the sub-UCB criteria, asymptotic optimality, and minimax optimality simultaneously for exponential family reward distributions.

In addition, they are able to show that when the exponential reward distribution has a closed form (e.g., Gaussian and Bernoulli), the posteriors in standard Thompson sampling relate to the proposed sampling distribution and therefore, obey asymptotic and finite-time regrets as well.

Finally, they introduce in Section 5 a new sampling distribution that adds a greedy exploration step to the sampling distribution used in ExpTS to remove the extra logarithm term in the worst-case regret of ExpTS, and show that this new algorithm ExpTS$^+$ is minimax optimal. To do so, a procedure to mitigate the over-estimation of sub-optimal arms is proposed. 
strengths_and_weaknesses: This work is very relevant as it studies a rich family of bandit reward distributions, i.e., the exponential family of distributions that covers commonly used ones (Bernoulli, Gaussian, Gamma, and Exponential).

The novelty and significance of this work's contributions are:

- A proof that ExpTS is an algorithm that, for exponential family of reward distributions, achieves the sub-UCB criteria, and is simultaneously minimax optimal (up to a factor of $\sqrt{log K})$ and asymptotically optimal. In addition, they show how a greedy extension of ExpTS is actually able to remove the extra $\sqrt{log K}$ minimax optimality factor. 

- A novel proof that both TS with Gaussian rewards and Gaussian posteriors, and Bernoulli rewards with Beta posteriors, are asymptotically optimal and minimax optimal up to a factor of $\sqrt{log K}$

- A novel, yet conceptually simple set of techniques, to analyze not only the frequentist regret of existing algorithms, but to also enable the proposal and analysis of new algorithms. Specifically, a regret decomposition that is conditioned on a lower confidence bound introduced in Equation 4.2
questions: The authors claim that the proposed sampling distribution in Equation 4.3 "_seems complicated for a general exponential family reward distribution, even though they only need the sampling distribution to satisfy a nice tail bound derived from this reward distribution._" Given that they show in Section 4.4. that usual conjugate priors in Gaussian and Bernoulli distributed rewards do meet such requirements, could the authors discuss what priors (or which properties of the priors) on other exponential-family rewards would meet the necessary distribution requirements?  
limitations: Given the theoretical nature of this work, there is minimal immediate impact on society, and limitations are somehow implicit in the modeling and theoretical assumptions.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper considers stochastic sampling in the multi-armed bandit problem. This problem involves K arms and the goal of the algorithm is to draw the arm of the largest mean as many times as possible. A class of algorithms called Thompson sampling, which conducts a greedy assuming that the posterior is correct, is known to be efficient. This paper considers a version of Thompson sampling with an incorrect posterior. 

To argue the advantages of the proposed algorithm, this paper considers three criteria for good algorithms. Namely, 
* Asymptotic optimality  
* Finite-time guarantee (sub-UCB, minimax)
* anytime algorithm

The proposed algorithm ExpTS is described in Table 1, which samples from the posterior based on a distribution that is inspired by the large deviation asymptotics (4.3). ExpTS+ is a version of ExpTS that mixes greedy and ExpTS. 

Class of distributions:
This paper considers a one-parameter exponential family distribution (if I understand correctly, the setting is the same as [Cappe et al. 2013]).

[Cappe et al. 2013] "Kullback-Leibler upper confidence bounds for optimal sequential allocation" Olivier Cappe, Aurelien Garivier, Odalric-Ambrym Maillard, Remi Munos, Gilles Stoltz

The paper is well-written. In my view, there are several issues in this paper that I discuss below. In particular, some of the setup and terms are different from the ones generally used in the community (and wrong in some ways). Besides, the algorithm modifies the posterior without addressing the corresponding anti-concentration of the original TS, which does not contribute to the understanding of the Thompson sampling itself. Given these, I think the paper requires some revision.

Issues 
* Incorrect mathematical definition: I guess "finite-time" is used in a wrong way. If I understand correctly, sub-UCB (1.2) bound and O(\sqrt{KT}) regret bounds are not finite-time (Landau notation is asymptotic). Usually finite-time analysis refers to the bound where all the terms are explicitly written as functions of model parameters. Moreover, I do not think most (all?) of TS analysis does not have a sub-UCB bound in the sense of (1.2). For example, if there is a term that is 1/Delta_i^2, then it is not sub-UCB because it diverges faster than (1.2) when we fix T and takes a small Delta). 
* The tradeoff relation is not very clear: the asymptotic rate on the top of log T is different in (1.1) and (1.2), which are not in a tradeoff relation. A more natural bound is a finite-time version of (1.1). There may be a tradeoff between minimax regret and the relative-divergence bound of (1.1).
* Comparison with existing results: [23] consider TS for 1-parameter exponential family and showed its asymptotical optimality (which I think is one of the closest papers to this). They stated that "Our result is asymptotic, but the only stage where the constants are not explicitly derivable from knowledge of F, T , and θ0 is in Lemma 9." I guess this bound is from a limited understanding of the anti-concentration property of TS. Authors should mention whether this bound can be made finite-time or if there need a modification such as ExpTS that is targeted to improve the anti-concentration property.
* No simulation: The computational aspect of the proposed algorithm is not mentioned (nor simulations), which limits the utility of the proposed algorithm. The sampling method from the distribution is mentioned (L258-L266) and it looks like the simulation is doable.

## At the end of the discussion phase:

A least agreement is that the minimax optimality is the most important part of this paper. I still think there are many concerns remain in the current version of paper, which I write in the following.

For clarification, the most relevant papers are (references are current version)
* [25] "Thompson sampling for 1-dimensional exponential family bandits." Korda et al. -> Asymptotic optimality of Thompson sampling for 1-dim exponential family
* [20] "MOTS: Minimax Optimal Thompson Sampling" Jin et al. -> Asymptotic + minimax optimality of a version of TS for Gaussian bandits
* [5] "Near-optimal regret bounds for Thompson sampling" Agrawal et al. -> TS is not minimax optimal up to $\sqrt{\log K}$

Given these results, the novelty of this paper is
* A version of TS, applicable to V-bounded 1-dim exponential family that is asymototical+minimax optimal
* Finite-time (+ sub-UCB) analysis of it.

I consider the contributions are incremental given such an asymptotical analysis is already known in [25] for TS and minimax improvement is previously done in [20] for Gaussian by "inflating" posterior just like this paper, but it is okay if it were properly presented and complemented by experimental results. 

For me, there remain concerns on the paper. Major ones of them are as follows. 

* Confusion on the analysis and performance of the algorithm: Table 1 is ill-defined if I understand each notion correctly. The authors place "Minimax Ratio" and "Sub-UCB" (even though these are defined in terms of asymptotics) inside "Finite-Time Regret". In fact, this is not even a comparison of algorithms. Finite-time or asymptotic is the property of *an analysis* (i.e., giving all constants explicitly or not), whereas all other properties are of *an algorithm*. 

* Limited characterization of the minimax property. [5] considers a misspecified instance where the rewards are fixed rather than drawn from the anticipated distributions, so this is not a lower bound in the true sense. A bit larger bound of $O(\sqrt{KT \log T})$ derived from the process of upper-bounding the regret; the remark "L223: using Gaussian posteriors will unavoidably suffer
from the lower bound of $\Omega(\sqrt{KT \log T})$" needs a fix (this is not a lower bound).

* No simulations are provided: p2 motivates the finite-time sub-UCB bound is important in the practical value of $T$, but there is no simulation provided even though "We show that sampling from P is tractable (Line 277)". I think deriving a minimax example where this algorithm is expected to shine is easy ($\mu_1 = \sqrt{K/T}, \mu_2-\mu_K = 0$?). 

* Possibly no tradeoffs. They consider "there is a tradeoff between minimax optimal regret and sub-UCB regret" but open. If I understand correctly, if there is a tradeoff between $A$ and $B$, then $A \cap B = \emptyset$ (or show some evidence that $A \cap B$ is unlikely). If it is open then it is not a tradeoff. Regarding the boundedness of $V$, their explanation does not make sense at least for the exponential distribution. 

* Lack of comparison on the existing theoretical results: Limited discussion on connecting the results with relevant papers. Regarding whether the finite-time analysis of TS can be done for [25] (only single term is asymptotic in [25]), they commented "The idea of [25] is totally different from ours." and did not provide any discussion on the most closely related paper. During the answer A9 (optimal algorithm for 1-parameter exponential family), they did not aware of existing literature in 2015.
strengths_and_weaknesses: Strengths
* Algorithm and related analysis: Showed that sampling from a (mock-)posterior can achieve optimality as well as finite-time exponential concentration, not only Bernoulli and Gaussian but also some class of exponential family.
* Minimax optimality: Discussion on minimax regret of TS for exponential distribution bandits

Weaknesses
* Characterization needs some fix
* Limited contribution to the understanding of TS for exponential bandits, on top of related work [18,23].
* Some gap between what the community wants and what this paper has done
questions: * Does the original TS has plausible anti-concentration? Lemma 9 in [23] is essentially unremovable (which motivates the introduction of ExpTS) or not? Do ExpTS and original TS match for some limit?
* Tradeoff relation: Among the properties considered in this paper (asymptotic optimality, finite-time bounds, anytime property), which of them are in the tradeoff relations? 
* How well ExpTS perform in practice (with some synthetic/real data simulations)?

* Is there any reason that one cannot demonstrate the same rate as the asymptotic rate?
>L227: In this paper, we study the general exponential family of reward distribution, which has no closed form. Thus we cannot obtain a tight concentration bound for µˆ1s as in special cases such as Gaussian or Bernoulli rewards. 
* I think having closed form is not directly related to the tightness of the concentration inequality. (probably the author cannot derive the concentration inequality of KL-divergence rate for some hardness)
limitations: * Ethically sound.
* No simulations on the performance of the proposed method.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper contributes to the growing body of works, where new `optimistic' TS algorithms are designed with sampling distributions that are updated in a non-Bayesian fashion but yields better regret bounds. This paper presents two variations of the Thompson Sampling (TS) algorithm ExpTS and ExpTS$^+$ to solve a K-armed bandit problem. Instead of considering the Bayesian posterior as the sampling distribution, they construct a new sampling distribution that is updated using past rewards and the number of trials for each arm. The sampling distribution in ExpTS is designed to avoid the under-estimation of the optimal arm and over-estimation of the sub-optimal arms. ExpTS$^+$ is like ExpTS but with a greedy step to choose an action from ExpTS. Under the assumption that the rewards are modeled as a distribution from the exponential family of distributions with finite variance, they are able to show that the frequentist regret bound of
1. ExpTS is asymptotically optimal, sub-UCB, and minimax optimal up to a factor of  $\sqrt{\log K}$, and
2. ExpTS$^+$  is minimax optimal and asymptotically optimal. 
Moreover, the author improves upon the existing regret bounds for Beta-Bernoulli and Gaussian-Gaussian bandits with their new regret decomposition.
strengths_and_weaknesses: 1. I think the paper is well-written, and the ideas presented are novel and clearly described. In particular, the authors explain the importance of their approach and analysis in Sec. 4.1 and the second para. of Sec. 5.
2. The construction of the sampling distribution (in sec 4.2) with all the nice properties is novel and the key contribution of this paper.
3. The author improves upon the existing regret bounds for Beta-Bernoulli and Gaussian-Gaussian bandits with their new regret decomposition.
4. The proofs in the Appendix A are structured well and looks correct to me, however the authors may address some of my question to enhance clarity. (The length of the paper (including Appendices with proofs) is too long to review for a conference paper.)




questions: Major:
79 -It is not clear what is making ExpTS+ minimax optimal but not sub-UCB. Please elaborate with more clarity.

Table 1: Incorrect row 2 (refer Theorem 1.2 in [1] )

94-97: Are these lines correct? The lower bound for TS for Gaussian reward ($O(\sqrt{KT\log K})$) was already established in Theorem 1.4 in [1] (and [2]). 

135-136- The statement is confusing. One cannot have Gaussian posterior with a Bernoulli reward.

A.3: I didn't follow the second inequality in A.3. Why there is T in the denominator of the first expression? Please elaborate.

528:  I am not sure, I followed the argument here. Please elaborate 

A.7:  How the first term in the third inequality is bounded by $V/\epsilon^2$ and the second term is bounded by the second term in the 4th inequality using 3.3. Please elaborate.

571: I don't think I follow the inequality described here to prove A18.

Minor:

116: Asymptotic - > Asymptotically

130: Beta not beta

146: measure 'of' $p(\theta)$ as ..

299: :loose


Ref..
[1]. Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling. Journal of the ACM (JACM), 64(5):30, 2017.
limitations: The authors briefly address some of the limitations of their work in the conclusion.
review_title: null

Meta-review: metareview: This paper provides a good contribution on Thompson sampling for exponential families, while several concerns on the presentation and technical points are raised. After the discussions with reviewers and my own reading of the paper, I judged that the issues on the presentation is not so much serious and considering the strong results of the paper I determined to recommend acceptance. Still, I partly agree with the opinion that technical novelty is not enough or well presented, and I strongly encourage the authors to seriously address the raised concerns in the final version.  

Following is my own comment to the paper.  
- In the discussion phase the authors explained that the algorithm can also consider the exponential families other than Bernoulli or Gaussian distributions by restricting the parameter space. Though it is supported through existing work, some problems become significantly easy when we are allowed to consider a compact parameter space in my experience. Though the boundedness of the space is not explicitly used, I believe that this limitation on the model must be at least explicitly clarified (or practical examples of models without restriction other than Bernoullis or Gaussians should be given). In practice we would not know the exact space and it would make another problem of whether we can take the space conservatively. The response on the necessity of bounded $V$ is not convincing to me and at least not formally explained.  
- One of the biggest reasons of success of TS would be its easy implementation. In this viewpoints the proposed algorithm does not seem to be practical and the original motivation of using TS seems to be somewhat weakened. In particular, in the exponential families KL-based algorithms are easily implemented. Though this kind of algorithms sometimes requires to solve the inverse of KL, the instance to be solved converges rapidly and the actual number of iterations for computing the inverse becomes very small. On the other hand, the proposed algorithm requires to solve randomly sampled instance and iterations at each round seems to become considerably large. It is fine so far if the TS-based algorithm is essentially necessary to achieve bounds of the paper, but it does not seem to be explained well and I expect that the motivation of using the TS-based algorithm despite its computational burden is clarified (other than its technical interestingness).
confidence: Less certain
Decision: Accept