# Empirical Bayes Regret Minimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2019.

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

- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [How Patterns Dictate Learnability in Sequential Data](https://mlsanity.com/paper/2510.10744/) (2025)
- [Co-Exploration and Co-Exploitation via Shared Structure in Multi-Task Bandits](https://mlsanity.com/paper/2512.12693/) (2025)

## Abstract (arXiv)

Most bandit algorithm designs are purely theoretical. Therefore, they have strong regret guarantees, but also are often too conservative in practice. In this work, we pioneer the idea of algorithm design by minimizing the empirical Bayes regret, the average regret over problem instances sampled from a known distribution. We focus on a tractable instance of this problem, the confidence interval and posterior width tuning, and propose an efficient algorithm for solving it. The tuning algorithm is analyzed and evaluated in multi-armed, linear, and generalized linear bandits. We report several-fold reductions in Bayes regret for state-of-the-art bandit algorithms, simply by optimizing over a small sample from a distribution.