Empirical Bayes Regret Minimization
arXiv:1904.02664
Abstract
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.
References in corpus (15)
- Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- A Simple Neural Attentive Meta-Learner
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
- The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
- Further Optimal Regret Bounds for Thompson Sampling
- Algorithms for multi-armed bandit problems
- Provably Optimal Algorithms for Generalized Linear Contextual Bandits
- BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
- Cascading Bandits for Large-Scale Recommendation Problems
- Learning to Branch
- Ensemble Sampling
- Meta-learning of Sequential Strategies