Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces Variational Thompson Sampling, where rather than sampling from the posterior, which can be infeasible, a computationally tractable upper bound is optimized.  In the stochastic multi-armed bandit setting with subgaussian noise, they provide a general analysis for any algorithm that plays a "stochastically optimistic" policy, which includes vanilla TS and the new method.  The VTS algorithm is shown to have sublinear regret for the more challenging bilinear saddle point problems where it can be shown that TS fails.
main_review: The paper seems technically sound.  The introduction of stochastically optimistic policy set is a useful abstraction that provides a nice joint analysis of TS and VTS and is useful for understanding.

The algorithm and analysis seem novel, but from a theoretical standpoint, it does not seem to improve over existing algorithms.  Experimentally, it seem marginally better than the similar K-learning algorithm.  The fact that the VTS objective is differentiable and could be incorporated as a NN layer is an interesting idea.

The paper is well written.  In particular, the paper does a good job of relating to other algorithms and interpretation in Section 3. 

As noted in the paper, the name variational TS is a bit misleading.  While a better name may be possible, the clarification is appreciated.  

In Section 4 it is noted that TS can suffer linear regret in the zero-sum game setting because it is open to exploittation without revealing information about the reward matrix. Some high level intuition on how VTS avoids this would be useful here.



Minor comments:
Line 90.5: $\mu$ should be $X$.
Line 235: Should $\Delta_A$ be replaced with $\Delta_n$?
limitations_and_societal_impact:
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work develops an analog to Thompson sampling by upper-bounding the expected regret in sequential decision-making problems. The two terms in the upper bound loosely resemble the evidence lower bound of variational inference: the first term encourages selecting arms with high expected reward; the second term depends on the inverse of the rate function and penalizes heavy tails and encourages exploration. The resulting variational Thompson sampling algorithm is evaluated on a random game and a constrained bandit problem.
main_review: Originality:
- I read this work in the spirit of Wainwright and Jordan (2008; https://people.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf) where variational inference is connected to marginal polytopes. While theoretical, I appreciate the connections the authors make between bounds dependent on inverse rate functions to concave sets of policy distributions, with Thompson sampling as a special case.

Quality:
- I did not evaluate proofs of the theorems; they seem sound at first glance. The empirical evaluation results in a favorable comparison to Thompson sampling. 

Clarity:
- The work will benefit from significant revision in terms of clarity. 
- Specific writing feedback:
- Split the first paragraph on Line 24; the paragraph on UCB on line 192 is too dense; several other 'walls of text'
- Put the noun/main character/subject of a sentence more front-and-center. I circled several things that made the writing confusing: "in this paper"; "at every step"; "this problem"; "the problem"; "the only requirement"; "in many cases"; "with that in mind"; "this simple strategy"; "have the laws of the posterior"; "with this notation"; "this brings us to"; "examining the problem that is solved"; "we conclude with some discussion"; "in this manuscript". The key point here is ctrl/cmd+F and searching for words like "it", "this", "that" and seeing if they can be replaced or the phrases can be cut. This lightens the cognitive load on a reader to figure out what "this" and other vague referents are, throughout the paper. Ditto for 
- Consider giving $\mathcal{G}_\mu$ a name - it will make it easier on readers. For example, it may be the 'regret map', mapping natural parameters of the mean reward $\mu$ to their upper bound on regret. Wainwright and Jordan (2008) may give inspiration for names in terms of the marginal polytope, natural parameters, etc. 
- Further, a visual aid of $\mathcal{G}_\mu$ would go a long way. It represents a concave set of probability distributions, and may be visualized using a diagram, perhaps as in Wainwright and Jordan (08).
- The abstract states "it permits the use of TS in a differential computation framework, such as a layer in a neural network". This was very unclear to me; and an analytical example or empirical evaluation of this is necessary; otherwise it should be cut. 
- label the axes in the figures
- align the algorithm boxes 
- The authors state "the name is misleading" about variational thompson sampling. Please use a different word than "misleading" or rename the paper/framework.

Significance:
- as above, I like the theoretical perspective this paper presents, and think if it is made more accessible through the use of visual aids, diagrams, and more experiments, it will result in practical impact as well.

Edit:
- have updated the score based on the strength of the author's response. Thank you for taking the time!
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel class of policies for online learning, named variational Thompson sampling (VTS). VTS is derived from a family of stochastically optimistic policies, which includes standard TS as a special case. VTS is amenable to some interesting interpretations when compared with difference existing policies such as UCB and K-learning, and is shown to outperform TS consistently in two classes of problems, i.e., zero-sum two player games and constrained bandits.
main_review: I find the derivation process of the VTS algorithm elegant and interesting. In particular, the paper starts from the definition of Bayesian regret and derives a related general inequality about conditional expectation, which naturally gives rise to a family of stochastically optimistic algorithms encompassing TS as a special case; VTS is then derived from this family of policies. Figure 1 and Figure 2 give nice illustrations to show that the VTS policy is closely related to yet different from TS. The connections of VTS to other existing policies in Section 3 also provide interesting insights. Section 4 gives two special cases where VTS has clear advantage over TS, supported by empirical simulations. Below are some questions/suggestions I have for the paper.

- I think the name "variational TS" may be misleading. Even after reading the abstract, I still get the feeling that the paper is in fact about proposing a variational inference algorithm to approximate standard TS. This has also been discussed in the paragraph from line 140 onwards, and I would suggest considering a less ambiguous name for the proposed method.
- Section 2.3: I wonder whether VTS is advantageous compared with standard TS for general multi-armed bandit problems (not considering the two special cases in Section 4)? It has been mentioned (lines 40-42) that solving for the VTS policy is easier than the sampling required by TS, but I think some illustrating examples would help a lot.
- Lines 214-222: the discussion here seems to suggest that VTS may actually be more related to K-learning than to TS. Moreover, in the simulation results in Section 4 (Figures 3 and 4), K-learning is very competitive with VTS. Therefore, I wonder will it be more natural for the paper to introduce VTS as a generalization of K-learning from the beginning, instead of deriving VTS in the way as in the current paper (Sections 2.1-2.3)?
- Line 263, Theorem 3: in this setting of zero-sum game between two players, does K-learning also have the same Bayesian regret as VTS?
- Lines 265-268: is there an intuitive explanation as to why VTS is not open to exploitation by the opponent?
- Figure 4: is there an explanation on the unsatisfactory performance of TS in this setting? Does the same explanation from section 4.1 (lines 228-230) also apply here?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents and establishes regret bounds for a new heuristic, inspired by Thompson sampling, for selecting actions in stochastic multi-arm bandit and bilinear saddle-point problems. As in Thompson sampling, a belief state is maintained over the values of each arm. However, instead of selecting an action according to its probability of optimality, one instead computes a policy (distribution over actions) that maximizes a novel objective. The objective can be understood as combining a "pure exploitation" term (the expected reward of the policy, under the current belief distribution), and an "exploration" term that depends only on the relative concentrations (and not the expected values) of the posteriors for each arm.
main_review: Overall, this seems like a very nice paper. I appreciated the clear logical progression, from the definition of the stochastically optimistic set, to the presentation of VTS, to the bilinear saddle-point problem extension. I also appreciated the intuition provided by Section 3 and by the examples depicted in the figures. The motivations for VTS (applicability to games while maintaining sub-linear regret, differentiability) seem plausible to me, and although this paper does not present especially compelling empirical evidence of VTS's applicability in practice, it is a nice, self-contained theory paper. I do have a couple questions / concerns:

1. One motivation offered in the introduction to look beyond TS is that it may require samples from intractable posteriors over the values for each arm. Could you say a bit more about when VTS is tractable, but sampling from these posteriors is not? It seems you do need to know or estimate the expectation of each posterior (for the "exploit" term in the objective), and you also need to compute convex conjugates of inverse cumulant generating functions. Is this really "far easier than sampling [in many cases]" (L41)? What cases?

2. The name "Variational Thompson Sampling" is misleading, as you acknowledge in L142. (To my ear, the name suggests an algorithm that uses variational inference to approximate the per-arm posterior distributions.) At multiple points in the paper you describe the VTS distribution as a "variational approximation" (in Fig. 1, an approximation "to the posterior probability of optimality"), but is there any sense in which it is a variational approximation to that distribution? It doesn't seem like it, other than that in this particular example bandit problem, the distributions happen to be somewhat close. The connection to the ELBO (L188) also seemed very tenuous, though perhaps I'm missing something.

3. In Section 3, you write that K-learning's Eq (5) is equivalent to VTS. In your experiments, what accounts for the minor discrepancy between K-learning and VTS? Do you let the temperature parameter vary by arm?

Despite these questions, this was an interesting paper that I enjoyed reading, and everything seems technically sound—so I am inclined to accept. I am, however, marking my confidence rather low (I think I've followed your presentation, but I feel less equipped to evaluate originality (particularly e.g. w.r.t K-learning) or significance).

Minor comments:

1. On line 61, should it be $\mu_{a_t}$ instead of $\mu_{i_t}$?
2. The notation $\eta_{a_t}$ suggests an action-dependent noise that does not vary with time (since the $t$ subscripts the $a$, not $\eta$). But presumably there is independent noise at each time step?
limitations_and_societal_impact: Limitations of the proposed method are not clearly discussed, as far as I can see. I would be interested to see a more complete discussion of the conditions under which VTS can be applied (i.e., the conditions under which the VTS objective, or its derivative / maximum, can be efficiently computed or estimated).
review_title: null

Meta-review: This paper introduces a family of stochastically optimistic policies that achieve favourable regret. All of the reviewers were enthusiastic about this paper, noting that the contribution was "technically sound" and "elegant".  I agree it is a valuable contribution, and will therefore recommend acceptance. I want to note two concerns that the authors should make sure to address in the camera ready:
* Please de-emphasize the argument that sampling from the posterior is harder than computing integrals w.r.t. the posterior. Unless I've misunderstood, I'm not sure I agree with this argument.
* Multiple reviewers recommended that the name of the method be changed. While I cannot enforce this, I also believe it is in the best interest of the authors to pick a name that the community finds appropriate.
Decision: Accept (Spotlight)