PaperlayerView exact revision on arXiv

Source-linked AI summary

Recommender regret for improving regularised RL estimation with bandits and MCTS

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

arXiv:2610.32910v1cs.LG

TL;DR

Existing bandit-based estimation frameworks evaluate sampling efficiency, although RL uses estimators to generate target policies, values, and Q-values. This paper formalises estimate generation as recommendation and defines regulariser-aware recommender regrets. Its theoretical and empirical results include achievable bounds with uniform sampling and performance that matches or exceeds prior work across several domains.

  • Problem

    Existing bandit-based estimation frameworks assess sampling efficiency rather than the quality of RL policy, value, and Q-value estimates.

    Source: §1 · p. 1

  • Method

    The paper formalises target generation as recommendation, defines regulariser-aware regret for RL targets, and extends recommendation-based improvement to tree search.

    Source: §1 · p. 1, §3 · p. 3, §4 · p. 6

  • Results

    Recommender-motivated uniform policies match or outperform prior work in synthetic trees, arcade games, and scientific discovery.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The experiments characterise the potential of regularised MCTS in scientific applications.

    Source: §5.3 · p. 9

    General upper bounds are sometimes loose in K; future work may use regulariser-specific algorithms to tighten them.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

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.

1 INTRODUCTION

RL estimators support policy, value, and Q-value targets, but existing bandit-based frameworks focus on sampling efficiency rather than estimate quality. The paper formalises estimate generation as recommendation, defines regulariser-aware recommender regret, and evaluates recommender methods theoretically and empirically.

1 INTRODUCTION

  • Existing bandit-based estimation frameworks allocate sampling budgets for efficiency, but lack a framework that maximises the quality of RL target estimates.RL methods use policy, value, and Q-value estimators during training and inference.Source: §1 · p. 1
  • The paper reframes target estimation as recommendation, prioritising the quality of produced policies, values, and Q-values over the sampling policy's cost.It draws on multi-armed sampling, whose earlier formulations evaluate how efficiently sampling matches a target distribution.Source: §1 · p. 1
  • Recommender regret extends simple sampling regret to general regularisers and policy, value, and Q-value targets, using divergences tied to the regulariser and target.The paper combines simple sampling regret with simple regret minimisation.Source: §1 · p. 1
  • The paper derives regret lower bounds, proves uniform sampling achieves the tightest analysed upper bounds, and reports faster convergence and superior performance in its evaluated domains.The evaluations span synthetic trees, arcade games, and scientific discovery.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

The background introduces multi-armed sampling and regularised MDPs, then distinguishes this paper's regret measures from prior bandit and tree-search work. Prior sampling formulations focus on matching a target distribution, while this paper addresses recommendation quality for RL targets.

2.1 MULTI-ARMED SAMPLING BANDIT PROBLEMS

  • Multi-armed sampling sequentially chooses sampling policies, observes rewards, and seeks to match a target distribution; prior formulations assess the samples needed for that match.Prior work found that exploration was barely required for sampling.Source: §2.1 · p. 2

2.2 REGULARISED MARKOV DECISION PROCESSES

  • A regularised MDP adds a strongly convex regulariser to the usual MDP tuple, penalising policies for deviating from desirable behaviour.With negative entropy, the optimal policy is more uniform, allocating probability across actions rather than only to one optimal action.Source: §2.2 · p. 2

2.3 PRIOR WORK IN RECOMMENDER REGRET

  • Unlike Xiao et al. (2019), this work bounds policy and Q-value recommender regrets using Bregman divergence and norm-based measures; uniform action selection also gives tighter upper bounds than E3W.Prior tree-search methods include MENTS, RENTS, and TENTS.Source: §2.3 · p. 3

3 RECOMMENDER REGRET OF SAMPLING BANDITS IN REGULARISED RL

The section frames regularised RL estimation as a recommendation problem and defines regret measures aligned with the regulariser and target object. It establishes lower bounds and upper-bound guarantees for sampling policies, while noting that general bounds can remain loose in action count.

3.1 NOTIONS OF RECOMMENDER REGRET

  • Recommender regret measures how closely estimated policies, values, or Q-values match their targets using divergences aligned with the regulariser.The target estimates are deterministic functions of sampling history.Source: §3 · pp. 3–4, §3.1 · p. 4

3.2 LOWER BOUNDS ON THE RECOMMENDER REGRET

  • The value lower bound is independent of the number of actions, while Q-value recommender regret scales with √(K/T).The passage notes that larger horizons make the problem easier, whereas more actions make Q-value estimation harder.Source: §3.2 · pp. 4–5

3.3 ALGORITHMS FOR THE RECOMMENDER REGRET

  • For any strongly convex regulariser, sampling policies with nonzero probability on every action achieve near-optimal dependence on T, but K-dependence is optimal only in specified cases.The stated cases are when the dual norm is ∥·∥∞ or the target object is a value.Source: §3.3 · pp. 5–6
  • Uniform sampling maximises the minimum action probability and yields tighter regret bounds than E3W, whose bounds incur a log(T) penalty.The analysis identifies a tension: recommendation requires pure exploration, unlike sampling, which requires minimal exploration.Source: §3.3 · pp. 5–6
  • The general upper bounds are fairly tight in T but can remain loose in K; regulariser-specific algorithms are proposed as future work for tighter bounds.The bounds are designed to hold regardless of the regulariser and the resulting policy or value functions.Source: §3.3 · p. 6

4 MONTE CARLO PLANNING FOR RECOMMENDATIONS

Recommender MCTS extends bandit-based estimation to tree search, using sampled trajectories and regularised value backups to produce policy, value, and Q-value recommendations. Its analysis establishes root regret concentration and expected regret bounds, with uniform sampling yielding tighter rates than E3W.

4 MONTE CARLO PLANNING FOR RECOMMENDATIONS

  • At each simulation, MCTS samples a trajectory from the root, updates visit counts along it, and uses regularised backups rather than empirical-average backups.The final leaf value comes from a Monte Carlo rollout or a learned value estimator.Source: §4 · p. 6
  • Theorem 5 establishes concentration of simple recommender regret at the tree root, supporting policy, value, and Q-value recommendations from recommender MCTS.The result assumes deterministic transitions and non-leaf rewards, and a sampling policy assigning each action probability at least ζ > 0.Source: §4 · p. 6
  • Corollary 6 provides expected regret bounds for recommender MCTS by integrating the concentration inequalities.The bounds include norm-based and Bregman-divergence-based regrets.Source: §4 · p. 7
  • Uniform sampling achieves tighter MCTS rates in concentration and expected regret than E3W, whose exponential convergence rates include logarithmic penalties in the exponent.The resulting sample complexity scales exponentially with tree depth and polynomially with action-space size.Source: §4 · p. 7

5 EXPERIMENTS

Across synthetic trees, arcade games, and biological sequence-design tasks, the experiments evaluate recommender bandits and MCTS for convergence and downstream performance. Tree search performs strongly in scientific discovery, while uniform sampling often compares favorably with E3W.

5 EXPERIMENTS

  • The experiments compare E3W and uniform sampling in synthetic trees, then evaluate recommenders in OCTAX arcade games and biological sequence design using regularised MCTS backup operators.The scientific-discovery setup uses a TGM model as baseline and value predictor; its diversity-aware metric selects high-reward sequences separated by a task-specific Levenshtein distance.Source: §5 · p. 7, §5.1 · p. 7, §5.3 · pp. 8–9

5.1 SYNTHETIC TREE EXPERIMENTS

  • In synthetic trees, uniform sampling outperforms E3W across the presented settings, but does not always yield the lowest value-regret or norm-based policy-regret curve.The authors attribute the mismatch with theory to imperfect modelling of algorithms’ dependence on K and somewhat loose value and policy error bounds.Source: §5.1 · p. 7, Figure 1 · p. 8

5.2 ARCADE GAMES IN OCTAX

  • Regularised MCTS improves PQN performance in representative OCTAX games, especially as simulations increase; E3W often leads at low budgets, while uniform sampling performs similarly at high budgets.The reported comparison covers a representative subset; some games were excluded because they saturated quickly or did not improve with search.Source: §5.2 · p. 8, Figure 2 · p. 9

5.3 SCIENTIFIC DISCOVERY

  • In all three scientific discovery tasks, tree-search policies—particularly TENTS—match or exceed the baseline’s top-100 mean, and uniform sampling beats E3W for almost all search algorithms and tasks.The comparison uses a TGM baseline and evaluates diversity-aware top-100 rewards.Source: Figure 3 · p. 9, §5.3 · p. 9

6 CONCLUSION

The paper introduces recommender bandits for regularised RL estimation and establishes theoretical and empirical results for them. It concludes that uniform sampling can match or outperform prior approaches across the evaluated domains.

6 CONCLUSION

  • The paper presents recommender bandits as a new class of bandit-based estimators for regularised RL, built on multi-armed sampling.The conclusion states that recommender regret has non-trivial lower bounds achievable with uniform policies, unlike the greedier policies required by multi-armed sampling.Source: §6 · p. 10
  • Uniform-sampling recommenders match or outperform prior work in synthetic trees, arcade games, and scientific discovery.The authors identify tightening upper bounds with regulariser-specific algorithms as future work.Source: §6 · p. 10

A PROOF OF THE LOWER BOUNDS

The lower-bound proofs use pairs of least-played arms to establish bounds for recommender regret across values, Q-values, and policies. The appendix also proves a regulariser-related inequality used in the analysis.

A PROOF OF THE LOWER BOUNDS

  • For any algorithm, a least-played pair of arms exists; the proof uses such pairs to obtain lower bounds over sub-Gaussian bandit instances.The setup considers Gaussian instances, which the passage states yield a valid lower bound for the sub-Gaussian class.Source: A PROOF OF THE LOWER BOUNDS · p. 13

A.1 VALUES RECOMMENDER REGRET (FIRST HALF OF THEOREM 1)

  • The value-regret proof applies a norm-based lower-bound lemma to the absolute difference between the recommended and target values.The passage identifies the resulting statement as a lower bound on value recommender regret.Source: §A.1 · p. 16

A.2 Q-VALUES RECOMMENDER REGRET (SECOND HALF OF THEOREM 1)

  • The Q-value proof uses the guaranteed least-played pair to establish a lower bound on Q-value recommender regret.The provided passages do not state the bound’s complete expression.Source: §A.2 · p. 16

A.3 NORM-BASED POLICY RECOMMENDER REGRET (FIRST HALF OF THEOREM 3)

  • For norm-based policy regret, the proof gives a lower-bound lemma under an L-smooth, β-strongly convex regulariser, then combines it with the general norm lemma.The argument uses the least-played pair of arms.Source: §A.3 · p. 17

A.4 BREGMAN DIVERGENCE POLICY RECOMMENDER REGRET (SECOND HALF OF THEOREM 3)

  • For Bregman-divergence policy regret, the proof relates its gap to the squared norm-based gap and combines that relation with the preceding lower-bound lemma.The passage states that squaring is monotone on the nonnegative range.Source: §A.4 · pp. 17–18

B PROOF OF PROPOSITION 2

  • The proposition proof establishes an inequality relating regularised policy outputs for two Q-vectors, assuming a curvature bound on the regulariser over the relevant policy hull.The stated condition bounds the regulariser’s Hessian quadratic form by L times the squared norm.Source: B PROOF OF PROPOSITION 2 · p. 18

C SUPPORTING THEORETICAL RESULTS

Under a strongly convex regulariser, Q-value error bounds also control policy and value error. The proof obtains high-probability Q-value bounds by controlling action counts and reward estimation.

C SUPPORTING THEORETICAL RESULTS

  • Strong convexity of the regulariser lets Q-value error bound policy and value error.The policy and value estimates are primal-dual pairs; the Q-values need not be unique.Source: C SUPPORTING THEORETICAL RESULTS · pp. 18–19
  • Action-count concentration and reward-error bounds combine into an event holding with probability at least 1 − δ.The proof uses martingale differences for action counts and a union bound over actions and time.Source: C SUPPORTING THEORETICAL RESULTS · pp. 19–20
  • When the dual norm is ℓ∞, the proof can use the Q-error bound directly without converting norms.For other dual norms, the proof decomposes the error vector coordinate-wise.Source: C SUPPORTING THEORETICAL RESULTS · pp. 20–21

D PROOF OF THEOREM 4

Theorem 4 bounds simple recommender regret for sampling policies that assign positive probability to every action. The bounds are near-optimal in T, with optimal K dependence only in specified cases.

D PROOF OF THEOREM 4

  • Theorem 4 gives high-probability upper bounds for simple recommender regrets under sampling policies with positive probability on every action.The proof conditions the bounds on a high-probability event and handles sub-Gaussian reward errors.Source: D PROOF OF THEOREM 4 · pp. 21–22
  • The bounds have near-optimal dependence on T, but optimal dependence on K only for the ℓ∞ dual norm or when the target is a value.The theorem covers norm-based and Bregman divergence-based regrets.Source: D PROOF OF THEOREM 4 · p. 21
  • For the ℓ∞ dual norm, the bounds are tighter than for general dual norms.The proof identifies the constants in the bounds as depending on K and the regret type.Source: D PROOF OF THEOREM 4 · pp. 21–22

E PROOF OF THEOREM 5

The proof establishes concentration for recommender regret at a search-tree root by conditioning on valid visit allocations across depths. It then derives uniform-sampling bounds for simple regret, MCTS regret, and expected regret.

E PROOF OF THEOREM 5

  • Conditioning on valid visit allocations at each depth yields a rigorous concentration bound of O(T H exp(−CT)).The resulting exponential relations mean the tree must be well explored before concentration occurs; maximizing ζ reduces the upper bound.Source: E PROOF OF THEOREM 5 · p. 28
  • The prior history-based argument yields only an Ω(1) probability bound, which does not establish concentration.The proof identifies this issue in the argument inherited from Xiao et al. (2019, Theorem 3).Source: E PROOF OF THEOREM 5 · pp. 28–29

F.1 PROOF OF COROLLARY 13

  • Among full-support sampling policies, uniform sampling minimizes the simple recommender regret upper bounds across all regret notions.The bounds in Table 2 are instance bounds and translate directly to expectation.Source: §F.1 · p. 29, Table 2 · p. 29

F.2 PROOF OF COROLLARY 14

  • Uniform sampling maximizes ζ∗ at 1/K, minimizing both C2/ζ^H and the required search horizon.This is the optimal regret-bound choice under Theorem 5’s hypotheses.Source: §F.2 · p. 30

F.3 PROOF OF COROLLARY 6

  • As T grows, the first expected-regret bound term dominates; the second scales as ˜O((T ln T)^−1/2), and the final term decays exponentially.The proof obtains the bound by integrating across error intervals.Source: §F.3 · pp. 30–31

G ADDITIONAL DETAILS AND PLOTS FOR SYNTHETIC TREE EXPERIMENTS

These appendices provide additional synthetic-tree error plots and OCTAX experiment details. They explain how the plotted errors depend on norm choice and how the experiments handle unvisited actions and simulation settings.

G ADDITIONAL DETAILS AND PLOTS FOR SYNTHETIC TREE EXPERIMENTS

  • “Theoretical” plots use norms associated with each regulariser; entropy uses the L1 norm and Tsallis entropy the L2 norm.The corresponding dual norms are L-infinity for entropy-regularised Q-values and L2 for Tsallis.Source: G ADDITIONAL DETAILS AND PLOTS FOR… · p. 33
  • Tsallis entropy and UCT can have substantially different errors in theoretical plots: KL divergence is unbounded while L2 policy error is bounded.For Q-value errors, the stated difference reflects L2 error being significantly higher than L-infinity error.Source: G ADDITIONAL DETAILS AND PLOTS FOR… · p. 33
  • Unvisited actions are assigned zero Q-values, causing constant regret on those arms; UCT may not visit all arms until roughly 4500–5000 simulations.Even greedier E3W sampling can incur this issue by repeatedly sampling high-performing arms.Source: G ADDITIONAL DETAILS AND PLOTS FOR… · p. 33
  • The synthetic-tree appendix includes Q-value MSE, value MSE, L2 policy-error, theoretical norm-based policy-error, KL-divergence, and Bregman-divergence plots.Per-seed plots show errors across five seeds; each seed represents a random environment with 100 random tree searches.Source: G ADDITIONAL DETAILS AND PLOTS FOR… · p. 33

H DETAILS OF THE OCTAX EXPERIMENTS

  • The OCTAX setup uses a PQN-style Q-network, and the authors report that wider inverse-temperature sweeps did not substantially change performance.Tree search depth is capped at 10; the tested settings were within one standard deviation of one another.Source: H DETAILS OF THE OCTAX EXPERIMENTS · p. 40
  • Some OCTAX tasks were filtered before the 512-simulation runs because those experiments took many days.The appendix also includes execution-time and episode-length plots for the large-simulation task set.Source: H DETAILS OF THE OCTAX EXPERIMENTS · p. 40

I ADDITIONAL PLOTS FOR OCTAX EXPERIMENTS

The additional OCTAX plots cover execution time, episode length, and episodic returns across tasks at different simulation budgets. The scientific-discovery details describe diversity-aware evaluation and explain the compute limits on GFP search.

I ADDITIONAL PLOTS FOR OCTAX EXPERIMENTS

J DETAILS OF THE SCIENTIFIC DISCOVERY EXPERIMENTS

  • The scientific-discovery evaluation ranks sequences by reward and adds a sequence only when it meets a task-specific Levenshtein-distance threshold from those already selected.The resulting diversity-aware top-k reward measures coverage of distinct reward-landscape modes rather than only the best sample.Source: J DETAILS OF THE SCIENTIFIC DISCOVERY… · p. 45
  • The authors report lower proxy-reward-model and TGM scores than in Jiralerspong et al. (2025), possibly due to implementation, seed, or proxy-model differences.The listed explanations are presented as possibilities.Source: J DETAILS OF THE SCIENTIFIC DISCOVERY… · p. 45
  • The scientific-discovery tree-search experiments sweep 17 inverse temperatures and repeat configurations across five seeds for regularised algorithms and their baselines.The sweep is used to assess both peak reward and sensitivity to the hyperparameter.Source: J DETAILS OF THE SCIENTIFIC DISCOVERY… · p. 45
  • GFP tree search runs every tenth token and is limited to 32 simulations because full per-token search is prohibitively expensive.At 32 simulations per token, searching all 237 tokens took roughly 20–30 minutes for one inverse temperature.Source: J DETAILS OF THE SCIENTIFIC DISCOVERY… · p. 45

K ADDITIONAL RESULTS FOR THE SCIENTIFIC DISCOVERY EXPERIMENTS

Across the scientific-discovery tasks, uniform sampling generally outperforms E3W, and TENTS with uniform sampling is particularly performant. Higher simulation budgets improve AMP and UTR performance, while top-50 and top-100 results show gains for regularised MCTS with important task- and baseline-specific qualifications.

K ADDITIONAL RESULTS FOR THE SCIENTIFIC DISCOVERY EXPERIMENTS

  • Uniform sampling outperforms E3W for almost all search methods in almost all tasks, with uniform-sampling TENTS particularly performant.Table 3 reports top-100 diverse mean reward at each task’s highest-performance simulation budget; GFP uses 32 simulations and AMP/UTR generally use 1024.Source: K ADDITIONAL RESULTS FOR THE… · p. 45, Table 3 · p. 46
  • As simulations increase from 32 to 1024, performance improves on AMP and UTR, but UCT does not finish at 1024 for either task.Figure 19 reports means and standard deviations over five generation seeds and sweeps inverse temperatures from 0.025 to 40; GFP is omitted because higher budgets take too long.Source: Figure 19 · p. 46, K ADDITIONAL RESULTS FOR THE… · p. 46
  • For top-50 and top-100 mean rewards, regularised MCTS can exceed the baseline, especially at higher simulation counts; the baseline is virtually unbeaten at top-1, top-10, and top-20.These Figure 20 plots use a single seed; AMP is the only task where no search method clears the maximum average reward, although TENTS and RENTS are competitive or higher at 1024 simulations.Source: K ADDITIONAL RESULTS FOR THE… · p. 46, Figure 20 · p. 47
  • Uniform sampling often outperforms E3W in UTR but not AMP, except at 1024 simulations; the authors report no explanation for this pattern.Source: K ADDITIONAL RESULTS FOR THE… · p. 46

Related papers

Loading 2610.32910v1…