RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits
This addresses the problem of implementing exploration in contextual bandits for practitioners, offering a practical solution, though it is incremental by building on existing regularization techniques.
The paper tackled the difficulty of applying exploration strategies like Thompson Sampling to black-box estimators in contextual bandits by proposing a pure-greedy strategy that leverages randomness from cross-validation-based regularization for exploration. The result showed theoretical equivalence to Thompson Sampling in two-armed bandits and empirical reliability in large-scale business environments compared to benchmarks.
Real-world contextual bandit problems with complex reward models are often tackled with iteratively trained models, such as boosting trees. However, it is difficult to directly apply simple and effective exploration strategies--such as Thompson Sampling or UCB--on top of those black-box estimators. Existing approaches rely on sophisticated assumptions or intractable procedures that are hard to verify and implement in practice. In this work, we explore the use of an exploration-free (pure-greedy) action selection strategy, that exploits the randomness inherent in model fitting process as an intrinsic source of exploration. More specifically, we note that the stochasticity in cross-validation based regularization process can naturally induce Thompson Sampling-like exploration. We show that this regularization-induced exploration is theoretically equivalent to Thompson Sampling in the two-armed bandit case and empirically leads to reliable exploration in large-scale business environments compared to benchmark methods such as epsilon-greedy and other state-of-the-art approaches. Overall, our work reveals how regularized estimator training itself can induce effective exploration, offering both theoretical insight and practical guidance for contextual bandit design.