Generalized Bayesian Upper Confidence Bound with Approximate Inference
  for Bandit Problems
  Bayesian bandit algorithms with approximate inference have been widely used
in practice with superior performance. Yet, few studies regarding the
fundamental understanding of their performances are available. In this paper,
we propose a Bayesian bandit algorithm, which we call Generalized Bayesian
Upper Confidence Bound (GBUCB), for bandit problems in the presence of
approximate inference. Our theoretical analysis demonstrates that in Bernoulli
multi-armed bandit, GBUCB can achieve $O(\sqrt{T}(\log T)^c)$ frequentist
regret if the inference error measured by symmetrized Kullback-Leibler
divergence is controllable. This analysis relies on a novel sensitivity
analysis for quantile shifts with respect to inference errors. To our best
knowledge, our work provides the first theoretical regret bound that is better
than $o(T)$ in the setting of approximate inference. Our experimental
evaluations on multiple approximate inference settings corroborate our theory,
showing that our GBUCB is consistently superior to BUCB and Thompson sampling.
