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.
Figures & tables
Figure 1. Allocation probability comparison between simplified two-step boosting Tree with early stopping (left) and Thompson Sampling (right), with N1=100 , N2=100 , and reward means 0.6 and 0.5 .
Figure 2. Cumulative Regret — Stationary Two-Armed Bandit. Bernoulli arms with true means 0.55 and 0.45 . Thompson Sampling uses a Beta (0.1,0.1) prior to avoid giving it an informational advantage over the regularized greedy, whose prior mean would otherwise coincide with the true arm means under a uniform prior.
Figure 3. We train a gradient boosting tree under early-stopping (see Procedure 1 ) to 1,000 burn-in samples with contextual feature vectors drawn from the email promotion dataset. By repeatedly running the algorithm, the resulting boosting model stops at different iterations due to stochasticity in the early-stopping process. To illustrate its behavior and performance metrics, we show: (a) the selected actions (indicated by color) when the boosting tree is stopped at different iterations; (b) the distribution of stopping iterations observed during cross-validation early stopping; and (c) the mean squared error (MSE) and regret associated with estimation and action selection at each iteration, evaluated using the ground-truth reward function.
Figure 4. Regret performance in a simple stationary setting with only 5 action features (18 combinations) and 2 contextual features. We compare estimators trained using standard regularization approach (early stopping via cross validation, stops after 15-25 iterations) with estimators trained with fixed 30 iterations. And we combine additional exploration strategies upon them. The parameters for Falcon variant and EXP are optimized using a grid search.
Figure 5. Reward performance in the stationary setting. All algorithms perform similarly, suggesting that little explicit exploration is needed, as the diversity of contextual features already induces sufficient implicit exploration across actions.
Figure 6. Reward performance in the non-stationary setting. The early-stopping–based oracle adapts more quickly to changes in the reward distribution, whereas additional explicit exploration provides limited or no improvement.
Figure 7. Average stopping iteration of the early-stopping oracle across different epochs. The dashed vertical lines indicate the start and end of the reward distribution change.