# Finite-Time Logarithmic Bayes Regret Upper Bounds

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 15 Jun 2023.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://mlsanity.com/paper/1902.10918/) (2019)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Multitask Bandit Learning Through Heterogeneous Feedback Aggregation](https://mlsanity.com/paper/2010.15390/) (2020)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory](https://mlsanity.com/paper/2304.12466/) (2023)

## Abstract (arXiv)

We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits. In a multi-armed bandit, we obtain O(c_Delta log n) and O(ch log2 n) upper bounds for an upper confidence bound algorithm, where ch and c_Delta are constants depending on the prior distribution and the gaps of bandit instances sampled from it, respectively. The latter bound asymptotically matches the lower bound of Lai (1987). Our proofs are a major technical departure from prior works, while being simple and general. To show the generality of our techniques, we apply them to linear bandits. Our results provide insights on the value of prior in the Bayesian setting, both in the objective and as a side information given to the learner. They significantly improve upon existing tildeO(√n) bounds, which have become standard in the literature despite the logarithmic lower bound of Lai (1987).