# Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework

arXiv: https://arxiv.org/abs/2201.12955 · HTML: https://mlsanity.com/paper/2201.12955/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 25 of 25)

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [R'enyi Divergence Variational Inference](https://mlsanity.com/paper/1602.02311/) (2016)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Black-box α-divergence Minimization](https://mlsanity.com/paper/1511.03243/) (2015)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [f-Divergence Variational Inference](https://mlsanity.com/paper/2009.13093/) (2020)
- [Variational Inference with Tail-adaptive f-Divergence](https://mlsanity.com/paper/1810.11943/) (2018)
- [Deep Bayesian Bandits: Exploring in Online Personalized Recommendations](https://mlsanity.com/paper/2008.00727/) (2020)
- [A Contrastive Divergence for Combining Variational Inference and MCMC](https://mlsanity.com/paper/1905.04062/) (2019)
- [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016)
- [Fast Distributed Bandits for Online Recommendation Systems](https://mlsanity.com/paper/2007.08061/) (2020)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Thompson Sampling with Approximate Inference](https://mlsanity.com/paper/1908.04970/) (2019)
- [All in the Exponential Family: Bregman Duality in Thermodynamic Variational Inference](https://mlsanity.com/paper/2007.00642/) (2020)
- [Variational Bayesian Optimistic Sampling](https://mlsanity.com/paper/2110.15688/) (2021)
- [Mixture weights optimisation for Alpha-Divergence Variational Inference](https://mlsanity.com/paper/2106.05114/) (2021)

## Built on by (most cited first, 2 of 2)

- [Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret](https://mlsanity.com/paper/2412.20824/) (2024)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)

## Abstract (arXiv)

Bayesian bandit algorithms with approximate Bayesian inference have been widely used in real-world applications. However, there is a large discrepancy between the superior practical performance of these approaches and their theoretical justification. Previous research only indicates a negative theoretical result: Thompson sampling could have a worst-case linear regret Omega(T) with a constant threshold on the inference error measured by one α-divergence. To bridge this gap, we propose an Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that can efficiently accommodate bandit problems in the presence of approximate inference. Our theoretical analysis demonstrates that for Bernoulli multi-armed bandits, EBUCB can achieve the optimal regret order O(log T) if the inference error measured by two different α-divergences is less than a constant, regardless of how large this constant is. To our best knowledge, our study provides the first theoretical regret bound that is better than o(T) in the setting of constant approximate inference error. Furthermore, in concordance with the negative results in previous studies, we show that only one bounded α-divergence is insufficient to guarantee a sub-linear regret.