Empirical Bayes Regret Minimization
  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.
