Variational Bayesian Optimistic Sampling
Authors: Brendan O'Donoghue
Tor Lattimore
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Bayes
Variational inference
Bandits
Decision problems
Online learning

Abstract: We consider online sequential decision problems where an agent must balance  exploration and exploitation. We derive a set of Bayesian `optimistic' policies  which, in the stochastic multi-armed bandit case, includes the Thompson sampling  policy. We provide a new analysis showing that any algorithm producing policies in the optimistic set enjoys $\tilde O(\sqrt{AT})$ Bayesian regret for a problem with $A$ actions after $T$ rounds. We extend the regret analysis for optimistic policies to bilinear saddle-point problems which include zero-sum matrix games and constrained bandits as special cases. In this case we show that Thompson sampling can produce policies outside of the optimistic set and suffer linear regret in some instances. Finding a policy inside the optimistic set amounts to solving a convex optimization problem and we call the resulting algorithm `variational Bayesian optimistic sampling' (VBOS). The procedure works for any posteriors, \ie, it does not require the posterior to have any special properties, such as log-concavity, unimodality, or smoothness. The variational view of the problem has many useful properties, including the ability to tune the exploration-exploitation tradeoff, add regularization, incorporate constraints, and linearly parameterize the policy.

Variational Bayesian Optimistic Sampling
Brendan O'Donoghue
Tor Lattimore DeepMind
Deep.Mind bodonooghue&deepminnnd com
lattimoree@deepmimddcco
Abstract
We consider online sequential decision problems where an agent must balance exploration and exploitation. We derive set of Bayesian 'optimistic" policies which, in the stochastic multi-armed bandit case, includes the Thompson sam- pling policy. We provide new analysis showing that any algorithm producing policies in the optimistic set enjoys Ó(VAT) Bayesian regret for a problem with actions after T rounds. We extend the regret analysis for optimistic policies to bilinear saddle-point problems which include zero-sum matrix games and con- strained bandits as special cases. this case we show that Thompson sampling can produce policies outside of the optimistic set and suffer linear regret in instances. Finding policy inside the optimistic set amounts to solving a convex optimization problem and call the resulting algorithm 'variational Bayesian op- timistic sampling" (VBOS). The procedure works for any posteriors, i.e., it does not require the posterior have any special properties, such as log-concavity, unimodality, or smoothness. The variational view of the problem has many useful properties, including the ability to tune the citoraatio-epllitaattioo tradeoff, add regularization, incorporate constraints, and linearly parameterize the policy.
1 Introduction
In this manuscript consider online learning, in particular the multi-armed stochastic bandit prob- lem [19] and its extension to bilinear saddle-point problems. Thompson sampling (TS) is a well- known Bayesian algorithm to tackle this problem 37 B5). At each iteration TS samples action according to the posterior probability that it is the optimal action. However, it never computes these probabilities, instead TS samples from the posterior of each and then acts greedily with respect to that sample, which is an implicit sample from the posterior probability of optimality. TS enjoys strong theoretical guarantees 31] well excellent practical performance (6]. Moreover, has an elegant information-theerrtii interpretation of an agent that is making a tradeoff between infor- mation accumulation and regret 34 That being said it does have several weaknesses. Firstly, TS requires samples from the true posterior, which may be intractable for some problems. It is known that TS with even small error in its posterior samples can suffer linear regret [32]. In many cases of interest the posterior distribution is highly intractable to sample from and running MCMC chains, one for each arm, can be wasteful and slow and still not yield precise enough samples for good per- formance, though recent work has attempted to improve this situation (22.. Moreover, TS is unable take into account other preferences, such as constraints or the presence of other agents. In partieu- lar, it was recently shown that TS can suffer linear regret in two-player zero sum games (27] and we shall demonstrate the same phenomenon this work empirically for constrained bandits. Finally, when performing TS the user never has direct access to the posterior probability of optimality, only samples from that distribution (though the distribution can be estimated by taking many samples). In some practical applications having access to the policy is desirable, for example to ensure safety constraints or to allocate budgets.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper we present 'variational Bayesian optimistic sampling' (VBOS), new Bayesian ap- proach online learning. At every step the VBOS algorithm solves convex optimization problem over the simplex. The solution to this problem is policy that satisfies a particular 'optimism' condi- tion. The problem always convex, no matter what form the posteriors take. The only requirement is the ability to compute or estimate the cumulant generating function of the posteriors. VBOS and TS can be considered as part of the same family of algorithms since, in the bandit case, they both produce policies inside the optimistic set. That being said, VBOS has several advantages over TS. First, some cases estimating or bounding the cumulant generating function may be easier than sampling from the posterior. Second, incorporating additional requirements such as constraints, opponents or tuning the exploration exploitation tradcoff is easy in VBOS just change the opti- mization problem. Finally, when using VBOS we always have direct access to the policy, rather than just implicit samples from it, as well as an explicit upper bound on the expected value of the problem, which TS does not give us. Here we list the contributions of this work.
1.1 Contributions
1. We derive a set of "optimistic" Bayesian policies for the stochastic multi- armed bandit that satisfy a particular optimism inequality and which includes the TS policy.
2. We present a new, simple proof of a Ö v AT) regret-bound for a bandit with arms after
T timesteps that covers any policy in the optimistic set (Ò ignores logarithmic factors).
3. We derive variational Bayesian optimistic sampling (VBOS), which a policy the opti- mistic set that can be computed by solving convex optimization problem.
4. We show that, unlike TS, the variational formulation easily handles more complicated prob- lems, such as bilinear saddle-point problems which include as special cases zero-sum two player games and constrained bandits.
1.2 Preliminaries
stochastic multi-armed bandit problem a sequential learning problem in which an agent interacts with an environment in order to maximize its total cumulative reward. Initially the agent does not know how the rewards are distributed and must learn about them from experience. In each round E N the agent selects an action a₂ E {1,..., A} and receives reward r. Maa + nú, where ná, E R is zero-mean noise associated with action at time t. We define F, = (a1, ri,.... (t-1))tt1) to be the sequence of actions and rewards observed by the agent prior to round f, and as shorthand we shall use the notation E' (-) B( FF).
An algorithm alg is measurable mapping that takes the entire history at time / and produces probability distribution, the policy, from which the agent samples its action. In order to assess the quality of an algorithm alg we consider the regret, or shortfall in eumulative rewards relative the optimal value,
T Regret(J, alg, T') = E, Σ
max
(1)
where Eg denotes the expectation with respect to the noise process v and any randomness in the algorithm. This quantity ( depends on the unknown expected reward μ E RA,, which is fixed at the start of play and kept the same throughout. To assess the quality of learning algorithms designed to work across some family M of problems we define
Beyesteg alg, T') = En Regret(,,, alg, T)
(2)
where á is a prior probability measure over μ E M that assigns relative importance to each problem instance and which we assume is known to the algorithm.
2 Thompson sampling and a variational approach
The algorithm that minimizes the Bayesian regret 2 is called the Bayes-optimal policy, but it is believed to be intractable to compute in most cases 10] With that mind we would like an algorithm that is computationally tractable and still guarantees good bound on the Bayesian regret.

---

TS is a Bayesian algorithm that at each time step samples possible values of each arm from their respective posteriors and acts greedily with respect those samples; see Algorithm This simple strategy provides a principled approach to the exploration-exploitaiioo tradeoff in the stochastic multi-armed bandit problem. In this section we derive a set of 'optimistic' policies, which includes the TS policy, and we shall show that any algorithm that produces policies in this set satisfies guaranteed Bayesian regret bound. For brevity we defer all proofs to the appendices.
2.1 Bounding the conditional expectation
The Bayesian regret (2 depends on the expectation of the maximum over collection of random variables. Here we shall derive an upper bound on this quantity, starting with generic upper bound on the conditional expectation.
Xx: : Ω + IRd a random variable in L (i.e, E| < oo for each = 1,....d) then we denote by Vx Rdd RRU {oo} the cumulant generating function of - EX,, i.e.,
-EX,
(3 = log E (x (x EX)).
This function is always convex, and we shall assume throughout this manuscript that it is also closed and proper for any random variables we encounter. With this definition we can present a bound on the conditional expectation.
Lemma 1. Let X Q - R be random variable on F,I)) satisfying X E L1, and let A E F be an event with P(A) > Then, for any T 2
E[X[A] < EX + xxx - P(A).
(3)
The right hand side of (3) involves the perspective of V and so convex in 4 and we can
minimize over > O to find the tightest bound, which we do next. Recall that the convex conjugate
of function f: .Rd - R is denoted f .Rd R and given by ('(()) sup, (1: y - f fxx) 44
Theorem 1. Let Ω + I be a random variable such that the interior of the domain of v x is non-empty, then under the same assumptions as Lemmal / we have
B[X]A] S EX + (Vx) log P(A)).
For example, if X ~ NNO0 then for any event A we can bound the conditional expectation as [[ < o. log P(A), no matter how X and A are related. This inequality has clear Donsker-Varadhan
connections to Kullback's 's inequality g and the Donsker- Varadhan variational representation of KL-divergence [11 Thm. 3.2]. The function T is referred to the Cramér functionn or the rate function in large deviations theory [39]. The inverse of the rate function comes up several contexts, such as queuing theory and calculating optimal insurance premiums [21]. Cramér's s theorem tells us that the probability of a large deviation of the empirical average of a collection of IID random variables decays exponentially with more data, and that the decay constant is the rate function. It is no surprise then that the regret bound we derive will depend on the inverse of the rate function, i.e., when the tails decay faster we incur less regret.
2.2 The optimistic set
Using Theorem I we next derive the maximal inequality we shall use to bound the regret.
Lemma 2. Let p Ω + RAA. E L be random variable, let i* argmax, (ties broken arbitrarily) and denote by V; = un then
E max S Σ P(i i) (Bn +
P(i i)))
Note that Lemma 2 makes no assumption of independence of each entry of μ. the bound holds even in the case of dependency.
If Vx 0. then take (vx -1 0.
3

---

In the context of online learning प. = P(i* = i) is exactly the TS policy when μr have the laws of the posterior. For ease of notation we introduce the 'optimism' map S A which for random variable μ J2 + gAa distributed according to o(- Fi) is given by
A (T) = Σ no (B' p4s ( m
(4)
where A denotes the probability simplex of dimension
and V == Wi Note that G3
concave since V is convex 4 Moreover, if the random variables are non-degenerate then g is differentiable and the gradient can be computed using Danskin's theorem
With this notation we can write E' max; μ4 S (TT)). This brings us to the 'optimistic" set of probability distributions, which corresponds to the set of policies that satisfy that same inequality.
Definition 1. Let j Ω A be random variable distributed according to 6(- Fe). then we define the optimistic set as
P = f AA E' max S (T))))
Immediately have two facts about the set Pl First, it is non-empty since n TS P and second, is convex set since the optimism map O concave.
2.3 Variational Bayesian optimistic sampling
Since the TS policy is in P it implies that we can maximize the bound and also obtain policy in Pt since
E' max 14 S (TT S max (T))
(5)
*EAA
We refer to the policy that maximizes G as the 'variational Bayesian optimistic sampling" policy (VBOS) and present the VBOS procedure as Algorithm 2
VBOS produces a policy E Pt at each round by construction. The maximum is guaranteed to exist since A is compact and G is continuous. The problem of maximizing 9 is concave maximization problem, and is thus computationally tractable long as each V readily accessible. This holds no matter what form the posterior distribution takes. This means we don't It rely on any properties like log-concavity, unimodality, smoothness of the distribution for tractability of the optimization problem.
As an example, consider the case where each μ4 ~ N/ o²) independently. In this instance we maXTEAA Ga(T) / log A. The
recover the familiar bound of E max, 14 (a( variational forn allows us to compute a bound in the case of differently distributed random variables.
Algorithm TS for bandits
Algorithm VBOS for bandits
for round = =1 1.......
T do
for round 1, ..,,....7 do compute π' = argmax g sample a₁ ~ n' end for
sample jı ~ 66. Fi)
choose 0g E argmax, ji! end for
2.4 Regret analysis
Now we shall present regret bounds for algorithms that produce policies in the optimistic set. These bounds cover both TS and VBOS.
Lemma 3. Let alg produce any sequence of policies T", = I,..., T, that satisfy # E dr then
BayesRegret(o, alg, T) < E
This bound is generic that it holds for any set posteriors any algorithm producing policies in Pl. The regret depends on the inverse rate functions of the posteriors, no matter how complicated

---

those posteriors may be, and faster concentrating posteriors, i.e. larger rate functions, will have lower regret. Loosely speaking, as more data accumulates the posteriors concentrate towards the true value (under benign conditions [38 Ch. 10.2]), implying (V(-)- - O. By carefully examining the rate of concentration of the posteriors we can derive concrete regret bounds in specific cases, such as the standard Gaussaan reward noise case, which we do next.
Theorem 2.
Let alg produce any sequence of policies x², ...... , that satisfy x² P and assume that both the prior and reward noise Haubb-Gaussian for each arm, then
BayesRegret alg, 7) /2AT A(1 log = Ō
The assumption that the prior is --sub-Gaussian is not really necessary and can be removed if, for example, we assume the algorithm pulls each arm once at the start of the procedure. Theorem 2 bounds the regret of both TS and VBOS, as well as any other algorithm producing optimistic policies. The point of this theorem is not to provide the tightest regret bound but to provide some insight into the question of how close to the true TS policy another policy has be order to achieve similar (in particular sub-linear) regret. We have provided one answer any policy in the optimistic set Pa for all I, is close enough. However, this set contracts as more data accumulates (as the posteriors concentrate) so becomes harder find good approximating policies. That being said, the VBOS policy is always sufficiently close because it is always in the optimistic set. In Figure 1 we show the progression of a single realization of the set P over time for a three-armed Gaussian bandit with Gaussian prior and where the policy being followed TS [3]. Initially, P is quite wide, but gradually as more data accrues concentrates toward the optimal arm vertex of the simplex.
Am 2
Arm
Arm
vB0s
v8os
Ar
Nm
Am
Amn
Amn
Amo
(a) L
(b) ( 32
(c) 256
Figure 1: Policy simplex for three-armed bandit. The shaded area is the optimistic set Pt. The blue dot is the TS policy and the red dot is the VBOS policy.
3 Connections and interpretations of VBOS
Expporatioon-eploitttii tradcoff. Examining the problem that solved to determine the VBOS policy we can break it into two components
g (T)
Σ
E M4
Σ n. ( (- log mT);
exploit
explore
the first term of which includes the expected reward (under the posterior) from pulling each arm and the agent's 's current understanding of the world, and the second term consists only of the uncertainty in each arm. The policy that maximizes this function is balancing this exploration and exploitation tradeoff, with a tradeoff parameter of one. a different tradeoff parameter other than one, e.g., when there are larger number of arms than the total number of rounds to play. In this case VBOS can easily be tuned be more or less exploring needed.
some practical instances may beneficial to use
5

---

Upper confidence bounds. Here we show a connection between VBOS and upper confidence bound (UCB) methods [8] 21. The Chernoff inequality tells us that the tail probability of random variable μt . + IR can be bounded as [f EE 6) S exp( (e)). for any 2 0. UCB algorithms build upper confidence intervals which contain the true value of the random variable with high-probability 2 [6]. If we want the interval to contain the true value of j with probability at least 1 - it requires setting e = (4 log 8). yielding Ep + (42)) log 6) 2 μ with high probability. UCB approaches to the stochastic multi-armed bandit typically choose the largest upper confidence bound (the 'optimism in the face of uncertainty" approach), that is, at time & they select action
ae E argmax p4 + (w"")"' ó:),,
for some schedule 6, A lot of work goes into tuning 5g for various applications. By contrast, VBOS samples from policy
EE' (E'r + (V()) (o)gr:))
01 argmax
TEA
It is clear that VBOS is building upper confidence bounds on the values of each arm that depend on the value of the policy, since we denote x* the maximizer to the above problem, then F (IE p + (V(()--(( log m < (4: I .;-- This procedure gives higher 'bonuses' to arms that end up with lower probability of being pulled, and lower bonuses to arms with high probability of being pulled, which is similar to what is done in more sophisticated UCB algorithms such as KL-UCB+ [17 [4]. This is desirable because if the mean an arm is low then there is a chance this simply because we have under-estimated it and perhaps we should pay more attention to that arm. In this light VBOS can be interpreted as a stochastic Bayesian UCB approach [[6]. One advantage is that we do not have tune a schedule &c like TS algorithm is randomized and stationary, i.e., it does not depend on how many time-steps have elapsed other than implicitly through the posteriors.
K-learning, K-learning is an algorithm originally developed for efficient reinforcement learning in MDPs where enjoys similar regret bound to TS [3 time t is given by
For bandits, the agent policy at
T log Σ exp(L' + V((/T)) of x exp(L' + ((L/T()) (6)
T = argmiin
T20
can be shown that this equivalent to VBOS when the 'temperature' parameters T; that we optimize over are constrained to be equal for each anm. Although K-learning and VBOS have essentially the same regret bound, this can make a large difference in practice. This connection also suggests that recent reinforcement learning algorithms that rely on the log-sum-cxp operator, the 'soft' max family 12
20 28 33), are also in some sense approximating the VBOS policy, although made clear in 29 these approaches do not correctly model the uncertainty and will suffer linear regret in general.
4 Bilinear saddle-point problems
In this section we extend the above analysis to constrained bilincar saddle-point problems, which include as special cases zero-sum two player games and constrained multi-armed bandits, as well as standard stochastic multi-armed bandits. Equipped with the tools from the previous sections we shall formulate a convex optimization problem that when solved yields the VBOS policy at each round, and prove that in two special cases this strategy yields a sub-linear regret bound. It is known, and we shall demonstrate empirically, that TS 3) can fail, i.e., suffer linear regret for some instances in this more general regime (27 $3.2]. Consequently, this is the first setting where the variational approach is substantially more powerful than TS.
A finite dimensional, constrained, bilinear saddle-point problem is defined by matrix R E 2 A and two non-empty convex sets II C RAA S !!'' which are the feasible sets for the maximizer and minimizer respectively. Here we shall assume that the agent is the maximizer, i.e., that II A and that the agent is uncertain about the entries of and must learn about them from experience. The saddle-poin point problem has optimal value given by
V R.A := min max X Rm max min À Rm TEAA XEA
λελ TEAA

---

where we can swap the order of the min max due to the minimax theorem [4]]. Unlike the stochastic multi-armed bandit case the maximizing policy in the bilinear saddle-point typically stochastic, and such the agent will return a policy rather than single action at each time-step. This is to allow the case, for example, an opponent who gets know the agent policy in advance of selecting their own action. We shall consider the case where at each time period the agent produces policy Te E AA over columns It from which action a; E {I....,A) } is sampled, and receives reward E IR and observation E O where either the reward, observation, or both are corrupted by noise yy. The exact reward, noise, observation, and opponent space A will depend on the problem setup. For instance, the vanilla stochastic multi-armed bandit is special case of this problem where A is singleton and the agent receives bandit feedback associated with the action sampled from its policy (i.e., 00 Ti Re, + n The information available to the agent at the start of round t is given by F. = (01, 01. ai 01-1). In this setup we define the Bayesian regret to be
T
BayesRegret(o, alg, T) = ER Enjall E(viA - ni)
Analogously to the stochastic multi-armed bandit case we can define the optimism map and the optimistic Let Rg Ω + 1 j 1,, 1,..., A, denote the random variable corresponding the jth column of R, denote by u : 1mmh - IR the cumulant generating function of Rý - E Rj. then
assuming that R₃ E LY we define the optimism map in this case be
(T)
min NEA,
T3 TT T, (A/Tg) - Tj log 1))
(8)
1=1
and the optimistic set to
Pd = ( E V S (T))
(9)
With these we can bound E'VR, using the techniques we have previously developed.
Lemma 4, Assuming that R E L we have
E'VRA S max G (T). TEAA
(10)
This lemma motivates the VBOS algorithm for bilinear saddle-points, presented as Algorithm VBOS produces policies n² P/. for all by construction. On the other hand, in some cases TS
can produce policies T² & Pi A.A. which we shall show by counter-example in the sequel.
At first glance maximizing A might seem challenging, but we can convert into a convex mini- mization problem by maximizing over ı to yield dual convex optimization problem:
minimize
V+ Σ 1==
1 Ty (xp(ss/TT)
subject to
8j 2 X E Ry + T, V (X/T)) -V - Ty. j j= 1,...,, A
(11)
A,
over variables
R RA,E R" RA, V R. The VBOS distribution be recovered using is an exponential cone program and can be solved efficiently using
क. = /T,,), Problem modern methods 25 26
IT)
36
24
Algorithm 3 TS for saddle-points
Algorithm 4 VBOS for addle-points
for round - 1, ...,, do
sample R² ~ Φ(. Fr)
..., for round / 1, ..., T.....TT.. do set n/ = argmax G (T) end for
set .' argmax min A R'T
end for xEAr xEλ
4.1 Zero-sum two-player games
Consider the problem of an agent playing a two-player zero-sum matrix game against an opponent. In this setting the agent 'column player' selects column index [I....,A) and the 'row player'
7

---

selects row index i E (1..... m) possibly with knowledge about the policy the agent is using to select the column. Note that in this case the row player makes a payment of r, = Raj + 7f, to the column player, where nig is a zero-mean noise term associated with actions i at time I, and the observation the agents receive is the reward and the actions of both players. The optimal strategies (T² :*) X*) are Nash equilibrium for the game 5). We shall assume that the agent we control the column player, and that we have no control over the actions of the opponent. It was recently shown that both K-learning and UCB variants enjoy sub-linear regret bounds in this context [27]. Here we prove a regret bound for policies in the optimistic set under nab-Gaussian assumption.
Am. These choices are revealed the players and
Theorem 3. Let alg produce any sequence of policies n', 1......., T, that satisfy n² Pt a. and 1...=1,....
let the opponent produce any policies X² -l.....,? T, adapted to Fr. Assuming that the prior over each entry of A and reward noise are
we have
BayesRegret alg, T) < /2 log A(1 = log T) - ÖVVAAT)
10020
75
VBOS
V505
Kiles
Klear
UCB
8010
EXP3
ppp1
2000
0-
10000
25030
30300
60003
15030
(a) Self-play.
(b) Against best-response opponent.
Figure 2: Regret on 50 x 50 random game.
In Figure 2 we show how five agents perform on a 50 x 50 randomly generated game in self-play and against a best-response opponent. The entries of R were sampled from prior N 1) and the noise term 1j' at each time-period was also sampled from (0, 1). In self-play the opponent has the same knowledge and is applying the same algorithm to generate the policy at each time-step. The best-response opponent knows the matrix M exactly as well as the policy that the agent produces and picks the action that minimizes the reward the agent. The matrix is the same in both cases. We compare the K- K-learming and UCB algorithms as described in (27] as well as EXP3 [3), generic adversarial bandit algorithm, VBOS Algorithm 4 and TS Algorithm 3 over 8 seeds. As can be seen VBOS is the best performing algorithm in both cases, followed closely by K-learning. Although performing moderately well in self play, response opponent since it is sometimes susceptible to exploitation, we show next.
no surprise that TS does very poorly against the best-
Consider the two-player zero-sum game counter-example presented in (77. Here A A2, and
1 with probability 1/2
R = 0 -1 r r= -1 with probability 1/2.
(12)
In this case TS will play one of two policies: - ,TS,1 [1,0] or π TS,2 11/2, each with probability 1/2. A quick calculation yields EVA, = - 1/4 and (T. = -1/2, so with probability 1/2 TS will produce a policy not in the optimistic set, since G T8.2) < EV Now, consider the case where 1 and the opponent plays the strategy [0, 1] in every round. Then every time TS produces π TS,2 will incur expected regret of 1/4. Since the value of r is never revealed the uncertainty is never resolved and so this pattern continues forever. This manifests as linear regret for TS in this instance. By contrast VBOS always produces π VBOS = [1,0] and so
suffers no regret.
In Figure 3 we show a realization of Pt 0.A over time for an agent following the VBOS policy in a randomly generated 3 3 zero-sum two-player game. Observe that the TS algorithm has produced policies outside the optimistic set, but VBOS remains inside at all times. Note that this does not prove that TS will suffer linear regret, since membership of the optimistic set only a sufficient, not necessary, condition.
8

---

Amm
Arm
Amm
VBco
MOOS
Am3
Aem
Art
Am
Ant
Am 1
(a) 1
(b) ( 32
(c) 1 = 256
Figure 3: Policy simplex for a bilinear saddle-point problem. The shaded area is the optimistic set P The blue dot is the policy generated by TS and the red dot is the policy generated by VBOS. Notice that TS has produced policies outside of the optimistic set.
4.2 Constrained bandits
In constrained bandits we want to find the policy that maximizes expected reward subject to a set of constraints. The constraints specify that the expected value of other reward functions associated with the same arms, which are also initially unknown, are larger than zero. Formally, we have the usual unknown reward vector μ4 IR we want to maximize as well as m other unknown reward vectors fm E R that define the constraints. When there is zero uncertainty we want solve the following primal-dual linear- pheear-rogramming pair
maximize
p1 m 0, i= 2,....., π E AA
minimize subject to
V
subject
DE p4d= V1 V1
X
0, 1
over primal variable π E As and dual variables V E and E RR" and where denotes the vector of all ones. We denote by (T* (²) any optimal primal-dual points.
When there is uncertainty regret is well-defined. If the support of the prior includes infeasible problems, which have optimal value -oc, then the expectation of the regret under that prior is unbounded below. However, if we make the assumption that ||**||2 S C. for some C' >> ø-almost surely, which implies that the problem is feasible almost surely, then the Bayesian regret well-defined and we can derive a regret bound that will depend on C. With this in mind define the set A {} E R" \ 1, 2 0, ||ll2 S C}. Let R E mx be the matrix with the reward vectors f11,... Mmmm stacked row-wise, then
reward vectors, then we must be careful to ensure that the Bayesian
write the Lagrangian for the above primal-dual pair as Equation (7), i.e., this problem a constrained bilinear maddle-point problem in terms of the primal-dual variables æ and X.
At each round the agent produces policy nt from which column is sampled and the agent receives observation vector o, = (Mi + Viys (22j + 12jo.... Mmmj + Thy)) where the index of the sampled column and vř is zero-mean noise for entry i, We define the reward at each time- period to be minxea A Rx We choose this reward for two reasons, firstly the regret with this reward is always non-negative, and secondly the regret zero then the corresponding policy n' optimal for the linear program since is maximizer of the saddle-pont polle- problem [4] Unlike the previous examples the agent never observes this reward since it depends on exact knowledge of R to compute, the reward is only used measure regret. Nevertheless, we have the following Bayesian regret bound for policies in the optimistic set.
Theorem 4. Let alg produce any sequence of policies n², 1,..., T, that satisfy x² P'A.A and assume that the prior over each entry of R and reward noise are Lsub-Gaussian and that ||A*1|2 I C d-almost surely, then
BayesRegret alg, T) < C (V21og (C))C((Vloo
A(1 log + +2/m VT = Ō(VmAT).
Next we present a numerical experiment with n 50 variables and m = 25 constraints. The entries of R were sampled from prior .V (-0.15, 1), and we repeatedly sampled from this distribution until

---

feasible problem was found. We chose slightly negative bias in the prior for R in order to make
the problem of finding a feasible policy more challenging. All noise was sampled from ((0, 1).
For this experiment we set C = 10; the true optimal dual variable satisfied || ~ 7. In Figure
we compare the performance of TS Algorithm 3 VBOS Algorithm 3 and K-learning [23] over seeds. We also plot how much the policy produced by each algorithm violated the constraints at each time-period, as measured by too norm. As can be seen both VBOS and K-learning enjoy sub-linear regret and have their constraint violation converging to zero, with VBOS slightly outperforming K- learning on both metrics. TS on the other hand appears to suffer from linear regret, and the constraint violation decreases up to point after which it saturates at non-zero value. It is clear that TS is unable to adequately trade off exploration and exploitation in this problem.
15
VB25
VBCS
K esmm
curck caree vwtaparr
60000
40000
8.0
20000
40000
60000
80000
100000
20000
40000
60000
80000
100000
(a) Regret.
(b) Constraint violation.
Figure 4: Performance on a random 50 x 25 constrained bandit problem.
5 Conclusion
In this manuscript we introduced variational Bayesian optimistic sampling (VBOS), which is an algorithm that produces policies by solving an optimization problem in each round of a sequential decision problem. The optimization problem that must be solved is always convex, no matter how complicated the posteriors are. We showed that VBOS enjoys low regret for several problem fam- ilies, including the well-known multi-armed bandit problem as well as more exotic problems like constrained bandits where TS can fail.
We conclude with some discussion about future directions for this work. First, in follow-up work we intend to show that VBOS is applicable in structured and multi-period problems like Markov decision processes, and again prove Bayesian regret guarantees. Second, an avenue we did not explore in this work was to parameterize the policy to be in certain family, e.g., linear in some basis. The variational formulation naturally extends this case, where the optimization problem is in terms of the basis coefficients (which maintains convexity in the linear case). Combining these two suggests using the variational formulation to find the linearly parameterized VBOS policy in an MDP, which amounts to solving a convex optimization problem that may be much smaller than solving the corresponding problem without the parameterization. We expect that a regret bound is possible in this case under certain assumptions differentiable this opens the door to using differentiable computing architectures, such as deep neural networks trained using backpropagation. We speculate that it may be possible to apply VBOS in deep reinforcement learning to tackle the challenging intoration-explitattii tradcoff in those domains.
the basis. Finally, since the VBOS objective
Acknowledgments and Disclosure of Funding
The authors would like thank Ben Van Roy, Satinder Singh, and Zheng Wen for discussions and feedback. The authors received no specific funding for this work.
10

---

References
[1] S. Agrawal and N. Goyal. Analysis of T'hompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1, 2012.
[2] Auer, N. Desa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit prob- lem. Machine learning, 47(2-3):235-222 2002.
[3] Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77) 2002.
[4] Boyd and Vandenberghe. Convex optimization. Cambridge university press, 2004.
[5] N. Besa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press,
2006.
[6] O. Chapelle and L. Li. An empirical evaluation of Thompson sampling. Advances in neural information processing systems, pages 2249-2257,201 2011.
[7] M. Danskin. The theory of max-min and application to weapons allocation problems, volume 5. Springer Science & Business Media, 2012.
[8] A. Fuchs and G. Letta. L'inégalité de Kullback. application la théorie de l'estimation. Séminaire de probabilités de Strasbourg, 4: 4:108-131, 1970.
[9] A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th ammual conference on learning theory, pages 359-376. JMLR Work- shop and Conference Proceedings, 2011.
[10] M. Ghavamzadeh, S. Mannor, Pineau, and A. Tamar. Bayesian reinforcement learning: A survey, Foundations and Trends in Machine Learning, 8(5-6):359-483, 2015.
[11] R. M. Gray. Entropy and information theory. Springer Science Business Media, 2011.
[12] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine. Reinforcement learning with deep energy- based policies. In International Conference Machine Learning, pages 1352-1361, PMLR, 2017.
[13] M. Harper. python-ternary: Temarry plots in python. 2021.
https: com/
ma marcharper/ mmrrcharpee/gytioo-teeeee
[14] J. Honda. A note KL-UCB+ policy for the stochastic bandit. arXiv:1903.07839, 2019.
arXiv preprint
[15] B. Jorgensen. The theory of dispersion models. CRC Press, 1997.
[16] E. Kaufmann, O. Cappé, and A. Garivier. On Bayesian upper confidence bounds for bandit problems. In Artificial Intelligence and Statistics, pages 592-600, 2012.
[17] T. Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, pages 1091-1114, 1987.
[18] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 6(1):4-22, 1985.
[19] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[20] Levine. Reinforcement learning and control probabilistic inference: Tutorial and review. arXiv preprint arXiv: 100..000000099 2018
[21] J. T. Lewis and R. Russell. An introduction large deviations for teletraffic engineers, 1997. [22] Mazumdar, Pacchiano, Y.-a. Ma, Bartlett, and M. Jordan. On Thompson sampling with Langevin algorithms. arXiv preprint 10000, 2020.

---

[23] B. O'Donoghue. Variational Bayesian reinforcement learning with regret bounds. arXiv preprint arXiv:1807.09644 2018.
[24] B. O'Donoguue. Operator splitting for a homogeneous embedding of the linear complemen- tarity problem. SIAM Journal on Optimization, 31(3):1999-2023 2021.
[25] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3):1422-1065 June 2016.
[26] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd. SCS: Splitting conic solver, version 2.1.0.
https://github. com/ wwwm/wxggp/seeeeeoooooe/////e/s/ scs Nov. 2017.
[27] B. O'Donoghue, T. Lattimore, and I. Osband. Stochastic matrix games with bandit feedback. arXiv preprint arXiv:2006.05145, 2020.
[28] B. O'Donoghue, R. Munos, K. Kavukcuoglu, and Mnih. Combining policy gradient and Q-learning. In International Conference on Learning Representations (ICLR), 2017.
[29] B. O'Donoghue, I. Osband, and C. Ionescu. Making sense of reinforcement learning and prob- abilistic inference. In International Conference on Learning Representations (ICLR), 2020.
[30] I. Osband, D. Russo, and B. Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[3]] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning. In Proceedings of the 34th International Conference Machine Learning (ICML), 2017.
[32] M. Phan, Y. Yadkori, and J. Domke. Thompson sampling and approximate inference. In Advances in Neural Information Processing Systems, pages 8801-8811, 2019.
[33] P. H. Richemond and B. Maginnis. A short variational proof of equivalence between policy gradients and soft Q-learning. arXiv preprint 17Xiv=1712.086550, 2017.
[34] D. Russo and B. Van Roy. An information--theortiicc analysis of Thompson sampling. The Journal of Machine Learning Research, 17(1):2442-247, 2016.
[35] D. Russo, Van Roy, A. Kazerouni, Osband, and Wen. tutorial on Thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
[36] S. A. Serrano. Algorithms for unsymmetric cone optimizution and an implementation for prob- lems with the exponential cone. PhD thesis, Stanford University, 2015.
[37] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4))285-294 1933.
[38] A. W. Van der Vaart, Asymptotic statistics, volume 3. Cambridge university press, 2000.
[39] S. S. Varadhan. Large deviations and applications. SIAM, 1984.
[40] Von Neumann and Morgenstern. Theory of games and economic behavior (commemora- live edition). Princeton university press, 2007.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This is
primarily theoretical paper with limited societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [No] We included description of the data generation process for the simulations we ran.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the appendix.
4. If you are using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "yFf93APEUEd", "reviewer": "Reviewer_2rdU", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nThe paper is well written.  In particular, the paper does a good job of relating to other algorithms and interpretation in Section 3. \n\nAs noted in the paper, the name variational TS is a bit misleading.  While a better name may be possible, the clarification is appreciated.  \n\nIn 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.\n\n\n\nMinor comments:\nLine 90.5: $\\mu$ should be $X$.\nLine 235: Should $\\Delta_A$ be replaced with $\\Delta_n$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "X2ztFsBCdWg", "reviewer": "Reviewer_TWH3", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n- 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.\n- 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.\n- 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)?\n- 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?\n- Lines 265-268: is there an intuitive explanation as to why VTS is not open to exploitation by the opponent?\n- 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "TVs6KK6-h2o", "reviewer": "Reviewer_zmC9", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1. 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?\n\n2. 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.\n\n3. 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?\n\nDespite 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).\n\nMinor comments:\n\n1. On line 61, should it be $\\mu_{a_t}$ instead of $\\mu_{i_t}$?\n2. 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "None that I can see.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5 hours"}, "extra_text": {}}, {"review_id": "INuarME9U2", "reviewer": "Reviewer_AmXN", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n- 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.\n\nQuality:\n- 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. \n\nClarity:\n- The work will benefit from significant revision in terms of clarity. \n- Specific writing feedback:\n- Split the first paragraph on Line 24; the paragraph on UCB on line 192 is too dense; several other 'walls of text'\n- 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 \n- 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. \n- 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).\n- 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. \n- label the axes in the figures\n- align the algorithm boxes \n- The authors state \"the name is misleading\" about variational thompson sampling. Please use a different word than \"misleading\" or rename the paper/framework.\n\nSignificance:\n- 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.\n\nEdit:\n- have updated the score based on the strength of the author's response. Thank you for taking the time!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)