Empirical Bayes Regret Minimization

Understand

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.