Recommender regret for improving regularised RL estimation with bandits and MCTS

Danilo Vucetic; Alexandre Larouche; Mohammad Pedramfar; Audrey Durand; Gauthier Gidel

cs.LGOct 23, 2026

Recommender regret for improving regularised RL estimation with bandits and MCTS

Authors: Danilo Vucetic, Alexandre Larouche, Mohammad Pedramfar, Audrey Durand, Gauthier Gidel

Organizations: Université de Montréal · Mila - Québec AI Institute · Université Laval · McGill University ·

Abstract

Regularised reinforcement learning (RL) algorithms rely on estimators, like Monte Carlo tree search or one-step look-ahead, to provide policy, value, or Q-value estimates in training and inference. However, existing bandit-based estimation frameworks evaluate sampling efficiency, not the quality of estimates. We address this by formalising estimate generation as a recommendation process, treating bandit-based sampling as an improvement operator. To evaluate the quality of a recommendation (estimate), we define regulariser-aware recommender regrets, analysing their lower bounds, and proving that simple algorithms like uniform sampling can achieve these bounds. Finally, we unify bandit- and search-based target improvement under recommender MCTS. Across synthetic trees, arcade games, and scientific discovery tasks, recommenders often yield faster target convergence and superior downstream performance. Our experiments characterise for the first time the potential of regularised MCTS in scientific applications.

Figures & tables

Name	Regulariser $\Omega(\pi)$	Value $\Omega^{*}(Q^{\star}_{\Omega}(s))$	Policy $\nabla\Omega^{*}(Q^{\star}_{\Omega}(s))$
Negative Entropy	$\sum_{a}\pi(a\|s)\log\pi(a\|s)$	$\frac{1}{\omega}\text{LSE}\left(\omega Q^{\star}_{\Omega}(s)\right)$	$\text{softmax}(\omega Q^{\star}_{\Omega}(s))$
Relative Entropy	$\text{KL}(\pi(s)\|\|\pi_{\text{ref}}(s))$	$\frac{1}{\omega}\log\sum_{a}\pi_{\text{ref}}(a\|s)e^{\omega Q^{\star}_{\Omega}(s,a)}$	$\dfrac{\pi_{\text{ref}}(a\|s)e^{\omega Q^{\star}_{\Omega}(s,a)}}{\sum_{b}\pi_{\text{ref}}(b\|s)e^{\omega Q^{\star}_{\Omega}(s,b)}}$
Soft Mellowmax	$\text{KL}(\pi(s)\|\|\pi^{\alpha}_{Q}(s))$	$\frac{1}{\omega}\log\sum_{a}\pi^{\alpha}_{Q}(a\|s)e^{\omega Q^{\star}_{\Omega}(s,a)}$	$\text{softmax}((\alpha+\omega)Q^{\star}_{\Omega}(s))$
Tsallis Entropy	$\frac{1}{2}\sum_{a}\pi(a\|s)^{2}$	$\frac{1}{\omega}\text{sparsemax-val}\left(\omega Q^{\star}_{\Omega}(s)\right)$	$\text{sparsemax}\left(\omega Q^{\star}_{\Omega}(s)\right)$

Table 1: Optimality equations for various regularisers.

Figure 1: Q-value estimation error in recommender MCTS over 15k simulations and trees of varying depth

d

, and action space size

k

, with 100 random tree search seeds, for each of the five

\mu

seeds.

Figure 2: Episodic returns in select OCTAX tasks showing improved performance with increased MCTS simulations. The error bars represent the standard error, with 100 random seeds per setting.

Figure 3: Top-100 diverse reward plots for the three scientific discovery tasks, with the TGM model as baseline, and as the value predictor in the MCTS tree. Tree search is competitive with, or beats, the mean performance of the baseline. Uniform sampling outperforms E3W for almost all algorithms.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Bounded Term	Uniform	E3W
$\left\lVert\hat{Q}_{t}-Q^{\star}\right\rVert_{\star}$	$2K^{3/2}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}\sqrt{\frac{\sigma^{2}\ln(4Kt/\delta)}{t}}$	$4K^{3/2}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}\sqrt{\frac{\sigma^{2}\ln(2+t)\ln(4Kt/\delta)}{t}}$
$\left\lVert\hat{\pi}-\pi^{\star}\right\rVert$	$\frac{1}{\beta}2K^{3/2}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}\sqrt{\frac{\sigma^{2}\ln(4Kt/\delta)}{t}}$	$\frac{1}{\beta}4K^{3/2}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}\sqrt{\frac{\sigma^{2}\ln(2+t)\ln(4Kt/\delta)}{t}}$
$D_{\Omega}(\hat{\pi},\pi^{\star})$	$\frac{1}{\beta}K^{3}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}^{2}\frac{\sigma^{2}\ln(4Kt/\delta)}{t}$	$\frac{2}{\beta}K^{3}\left\lVert\mathbf{e}_{1}\right\rVert_{\star}^{2}\frac{\sigma^{2}\ln(2+t)\ln(4Kt/\delta)}{t}$
$\left\|\hat{V}-V^{\star}\right\|$	$2\sigma\sqrt{\frac{K\ln(4Kt/\delta)}{t}}$	$4\sigma\sqrt{\frac{K\ln(2+t)\ln(4Kt/\delta)}{t}}$

Appendix

Table 2: Regret bounds comparing Uniform and E3W sampling policies.

Figure 4: Q-value mean squared error plots in synthetic trees.

Figure 5: Value mean squared error plots in synthetic trees.

Figure 6: L2 norm-based policy error plots in synthetic trees.

Figure 7: Theoretical norm-based policy error plots in synthetic trees.

Figure 8: KL divergence-based error plots in synthetic trees.

Figure 9: Theoretical Bregman divergence-based value error plots in synthetic trees.

Figure 10: Q-error graphs per seed (5 seeds one per row)

Figure 11: Value error graphs per seed (5 seeds one per row)

Figure 12: Norm-based policy error graphs per seed (5 seeds one per row)

Figure 13: Bregman-based policy error graphs per seed (5 seeds one per row)

Figure 14: Execution times increase quickly with sims per step.

Figure 15: Episode lengths stay relatively similar with increased sims per step.

Figure 16: Episodic returns for all OCTAX tasks.

Figure 17: Episode lengths for all OCTAX tasks.

Figure 18: Execution times for all OCTAX tasks.

Method	AMP	UTR	GFP
Baseline (no search)	10.17 $\pm$ 1.76	4.13 $\pm$ 0.02	1.61 $\pm$ 0.02
SMM (E3W)	6.63 $\pm$ 0.23	3.47 $\pm$ 0.02	1.53 $\pm$ 0.01
SMM (Uniform)	7.69 $\pm$ 0.74	3.66 $\pm$ 0.01	1.53 $\pm$ 0.01
MENTS (E3W)	8.56 $\pm$ 0.48	3.65 $\pm$ 0.01	1.53 $\pm$ 0.01
MENTS (Uniform)	9.13 $\pm$ 0.98	3.65 $\pm$ 0.01	1.53 $\pm$ 0.01
RENTS (E3W)	7.57 $\pm$ 0.10 †	4.12 $\pm$ 0.01	1.58 $\pm$ 0.01

Appendix

Table 3: Top-100 diverse mean reward (mean

\pm

std across seeds) for each search algorithm and action-selection rule, at each task’s highest-performance simulation budget: AMP/UTR: 1024 simulations for most methods, other than UCT; GFP: 32 simulations for all methods. Bold marks a configuration whose mean exceeds the no-search baseline for that task.

\dagger

: fewer than 5 seeds had completed; mean and std are over the seeds available.

Figure 19: Performance of tree search in the AMP and UTR tasks, with increasing MCTS simulations per environment step. The top-100 diverse mean reward consistently increases for all tasks, with uniform sampling (dotted lines) often outperforming E3W. UCT did not finish at the 1024 simulation budget. The mean and standard deviation are computed over 5 random seeds of the generation process, sweeping inverse temperatures between

0.025

40

. GFP is not presented on this figure because it takes too long to run with higher simulation budgets.

Figure 20: Performance of tree search across all scientific discovery tasks at different top

-k

levels, with increasing simulation budgets.

Regularized RL

See all 24 papers

RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits
Mar 11, 2026Tong Li, Thiago de Queiroz Casanova, Eric M. Schwartz +3Contextual Bandits Exploration-Exploitation Tradeoff
University of Toronto Canada · Braze United States · University of Michigan United States
Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
Mar 2, 2026Kaixuan Ji, Qingyue Zhao, Heyang Zhao +2Multi-Armed Bandits KL-Regularized RL
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
Sep 11, 2026Zichen Wang, Haoyang Hong, Huazheng WangContextual Bandits
Department of ECE and CSL, University of Illinois Urbana-Champaign · School of Electrical Engineering and Computer Science, Oregon State University

Mar 11, 2026J/K move · Enter open · S save

RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits

Tong Li, Thiago de Queiroz Casanova, Eric M. Schwartz, Victor Kostyuk+2

University of Toronto Canada · Braze United States · University of Michigan United States

Contextual Bandits Exploration-Exploitation Tradeoff RL Exploration Thompson Sampling

Open paper AskPDF arXiv

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.

Abstract

Regularized RL

Explore similar work

RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits

Near-Optimal Regret for KL-Regularized Multi-Armed Bandits

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence