  Bayesian bandit algorithms with approximate Bayesian inference have been
widely used in real-world applications. Nevertheless, their theoretical
justification is less investigated in the literature, especially for contextual
bandit problems. To fill this gap, we propose a general theoretical framework
to analyze stochastic linear bandits in the presence of approximate inference
and conduct regret analysis on two Bayesian bandit algorithms, Linear Thompson
sampling (LinTS) and the extension of Bayesian Upper Confidence Bound, namely
Linear Bayesian Upper Confidence Bound (LinBUCB). We demonstrate that both
LinTS and LinBUCB can preserve their original rates of regret upper bound but
with a sacrifice of larger constant terms when applied with approximate
inference. These results hold for general Bayesian inference approaches, under
the assumption that the inference error measured by two different
$\alpha$-divergences is bounded. Additionally, by introducing a new definition
of well-behaved distributions, we show that LinBUCB improves the regret rate of
LinTS from $\tilde{O}(d^{3/2}\sqrt{T})$ to $\tilde{O}(d\sqrt{T})$, matching the
minimax optimal rate. To our knowledge, this work provides the first regret
bounds in the setting of stochastic linear bandits with bounded approximate
inference errors.
