Residual Overfit Method of Exploration

Abstract

Exploration is a crucial aspect of bandit and reinforcement learning algorithms. The uncertainty quantification necessary for exploration often comes from either closed-form expressions based on simple models or resampling and posterior approximations that are computationally intensive. We propose instead an approximate exploration methodology based on fitting only two point estimates, one tuned and one overfit. The approach, which we term the residual overfit method of exploration (ROME), drives exploration towards actions where the overfit model exhibits the most overfitting compared to the tuned model. The intuition is that overfitting occurs the most at actions and contexts with insufficient data to form accurate predictions of the reward. We justify this intuition formally from both a frequentist and a Bayesian information theoretic perspective. The result is a method that generalizes to a wide variety of models and avoids the computational overhead of resampling or posterior approximations. We compare ROME against a set of established contextual bandit methods on three datasets and find it to be one of the best performing.

arXiv comment13 pages, 16 figures

References in corpus (5)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Bayesian Active Learning for Classification and Preference Learning
• Variational Dropout and the Local Reparameterization Trick
• Scalable Bayesian Optimization Using Deep Neural Networks
• Learning from Bandit Feedback: An Overview of the State-of-the-art