Reproduce “RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits” on OpenResearch

About this paper

Tong Li, Thiago de Queiroz Casanova, Eric M. Schwartz, Victor Kostyuk, Dehan Kong, Joseph J. Williams

RIE-Greedy introduces a contextual bandit approach that leverages the intrinsic exploration behavior from standard regularization techniques like cross-validation-based early stopping in iterative machine learning models. This method enables effective and adaptive exploration without requiring explicit exploration strategies, demonstrating performance comparable to or better than methods with added exploration, particularly in non-stationary environments.

Key insights

• Early stopping in iterative learning can be theoretically linked to a hypothesis testing procedure, where the decision to exploit or explore is proportional to the statistical evidence of an action's superiority, thus inducing exploration.
• This regularization-induced exploration behavior closely parallels the action allocation probabilities of Thompson Sampling, providing a novel theoretical connection between standard machine learning model fitting and bandit exploration.
• The intrinsic dynamics of model regularization contribute significantly to exploration, especially in complex, non-linear, and non-stationary environments, beyond just passive exploration from contextual diversity.

Summary by alphaXiv.