Variational Bayesian Optimistic Sampling
  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.
