Residual Overfit Method of Exploration
This addresses the problem of efficient exploration for researchers and practitioners in bandit and reinforcement learning, offering a novel approach that is computationally lighter than existing methods.
The paper tackles the computational challenge of exploration in bandit and reinforcement learning by proposing the residual overfit method of exploration (ROME), which uses two point estimates to drive exploration without intensive resampling, achieving top performance on three datasets.
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.