  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.
