PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncertainty-Aware Selection of Online Algorithms with Simulator Ensembles

Yongyi Guo, Zifan Xu, Ziping Xu, Kelly W. Zhang

arXiv:2609.32170v1cs.LGcs.AI

TL;DR

Selecting online RL algorithms is difficult because design choices can substantially change deployment performance, while real deployment may make testing many candidates infeasible. The paper uses simulator ensembles to account for uncertainty in algorithm selection, finding regret benefits in bandits and empirical benefit in deep-RL reward shaping.

  • Problem

    Online RL performance varies substantially with design choices, while costly deployment can make testing many candidate algorithms infeasible.

    Source: §1 · p. 1

  • Method

    The paper uses simulator ensembles to account for uncertainty when selecting online algorithms and characterizes Uncertainty-Aware selection as curvature-regularized Plug-In selection.

    Source: §1 · p. 2

  • Results

    In Gaussian bandits, Uncertainty-Aware selection has no larger asymptotic regret growth than Plug-In and, with nonvanishing probability, improves polynomial regret to logarithmic; deep-RL experiments show benefit.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Simulator ensembles can improve online-algorithm selection from limited offline data, even apart from their use in training robust policies.

    Source: §1 · p. 2

    The setting assumes offline data and online deployment come from the same environment; combining Uncertainty-Aware selection with distribution-shift methods remains future work.

    Source: §6 · p. 11

Abstract

from arXiv · show

The performance of online reinforcement learning depends critically on design choices, especially those that affect exploration. These choices are often selected by fitting a simulator to offline data, evaluating candidate algorithms in that simulator, and deploying the best-performing one. The simplest Plug-In selection rule simply selects the best performing algorithm on the fitted simulator, making evaluations unreliable when the offline data used to fit the simulator are limited. We investigate Uncertainty-Aware selection, which forms an ensemble of simulators---for example, obtained by bootstrap resampling---and selects the online algorithm with the best average performance across the ensemble. While ensemble-based approaches have been used to mitigate distribution shift and facilitate sim-to-real transfer, we formally show that this approach can mitigate the effects of limited data when fitting the simulator and theoretically has significant regret gains compared to Plug-In selection in multi-armed bandits. We also empirically investigate the Uncertainty-Aware selection approach in deep RL experiments on robotic control tasks that involve selecting reward-shaping hyperparameters, and show that it leads to more reliable selection and improved online performance.

1 Introduction

Online RL algorithm selection matters because design choices can substantially affect deployment performance, while real-world testing may be costly. This paper proposes Uncertainty-Aware selection and reports theoretical and empirical benefits over selecting on a single fitted simulator.

Motivation

  • The motivating challenge is that online RL performance varies with design choices, while testing many candidate algorithms in costly deployments may be infeasible.Offline data can instead inform design through a fitted simulator, but selecting on one fitted model does not convey its estimation uncertainty.Source: §1 · pp. 1–2

Contributions

  • Uncertainty-Aware selection scores each candidate algorithm by average return across an ensemble of simulators perturbed according to estimation uncertainty.The ensemble can be constructed by refitting on bootstrap resamples of the offline data.Source: §1 · p. 2
  • For UCB and Thompson Sampling in two-armed Gaussian bandits, Uncertainty-Aware selection can yield a polynomial-to-logarithmic regret improvement with nonvanishing probability.The analysis links the gain to asymmetric exploration costs: underexploration can cause polynomial regret, while overexploration preserves logarithmic regret.Source: §1 · p. 2
  • The selection criterion is a curvature-regularized version of Plug-In selection for general decision-making settings, including bandits and MDPs.The regularization depends on the objective's curvature with respect to simulator parameters.Source: §1 · p. 2
  • The paper also investigates Uncertainty-Aware selection for deep RL reward-shaping choices using physics parameters identified from offline trajectories in a MuJoCo simulator.The introduction identifies this as an empirical benefit for reward-shaping selection.Source: §1 · p. 2
  • The paper concludes that simulator ensembles can improve selection of online learning algorithms from limited offline data, beyond their use in robust policy training.The reported bandit results include reductions in both mean and variability of regret.Source: §1 · p. 2

2 Problem setup

The setup uses offline data to select an online learner for deployment in the same environment, comparing a single fitted simulator with an ensemble-based average. The related-work discussion distinguishes this selection problem from robust policy training and fixed-policy evaluation.

2 Problem setup

  • The selection objective is to use offline data to choose a candidate online algorithm that maximizes its deployment objective over T episodes in the data-generating environment.Candidates may vary in exploration strategy, architecture, state or reward specification, or hyperparameters.Source: §2 · p. 3
  • Plug-In selection evaluates candidates on one fitted simulator, whereas Uncertainty-Aware selection chooses the candidate with the best average performance across an ensemble of fitted simulators.The ensemble average favors candidates that perform consistently across plausible simulator realizations; the paper uses bootstrap-based ensembles, including empirical and parametric bootstrapping.Source: §2 · pp. 3–4

2.1 Related work

  • Unlike domain randomization, which targets simulator-to-deployment mismatch for a fixed policy, this setting assumes no mismatch and uses ensemble spread to represent finite-dataset sampling variability.That spread vanishes as the offline data grow; the proposed gain concerns online learners whose regret responds asymmetrically to estimation error.Source: §2.1 · p. 4
  • The ensemble is external to the candidate algorithms: unlike model-based RL ensembles that alter exploration or penalize disagreement, it changes only which black-box candidate is selected.The paper also contrasts its average criterion with robust RL's worst-case optimization over an uncertainty set.Source: §2.1 · pp. 4–5
  • The target is selection among learners that continue learning after deployment, not offline policy selection that ranks fixed policies through fitted value functions.The paper states that prior online-algorithm selection work had not analyzed how simulator estimation error propagates into the choice or shown that ensembles correct it.Source: §2.1 · p. 5

3 Plug-In vs. UA selection in multi-armed bandits

In two-armed Gaussian bandits, the section analyzes exploration tuning for UCB and Thompson Sampling and compares Plug-In with Uncertainty-Aware selection. It finds asymmetric costs of exploration errors and examines selection benefits from accounting for simulator uncertainty.

3 Plug-In vs. UA selection in multi-armed bandits

  • For both algorithms, larger θ induces more exploration; the analysis studies UCB and Thompson Sampling in a two-armed Gaussian bandit.The authors identify θ as the working reward variance for this analysis.Source: §3 · p. 5

3.1 Asymmetric costs of under- and overexploration

  • Below σ², regret grows as T^(1−θ/σ²+o(1)); at or above σ², it grows logarithmically with leading constant 2θ/(µ1−µ2).This characterizes the asymmetry for both UCB and Thompson Sampling: insufficient exploration can change regret from logarithmic to polynomial, while additional exploration above the threshold changes only the leading constant.Source: §3.1 · p. 6

3.2 Uncertainty-Aware selection favors exploration and improves regret

  • 573 vs 1137 (UCB) and 363 vs 869 (Thompson Sampling) cumulative-regret variance: Uncertainty-Aware is lower than Plug-In in both comparisons.The reported regret is also lower under Uncertainty-Aware selection, which chooses higher exploration values more often.Source: Figure 2 · p. 6, §3.2 · p. 7
  • 61.0% vs 50.6% of regret comes from selecting θ below θ∗ under Plug-In and Uncertainty-Aware selection, respectively.The authors attribute Plug-In's underperformance to the high cost of errors toward too little exploration, not simply to noisy estimates of θ.Source: §3.2 · p. 7
  • Across much of the offline-data-supported region, Uncertainty-Aware selects at least as much normalized exploration as Plug-In, with differences concentrated where uncertainty can change candidate rankings.The figure illustrates this comparison for UCB across estimated reward gaps and noise levels.Source: §3.2 · p. 7, Figure 3 · p. 8
  • The theoretical Uncertainty-Aware rule uses a parametric-bootstrap ensemble that perturbs fitted arm means according to their estimated sampling uncertainty.The offline-data analysis assumes a behavior policy that samples each arm equally often and restricts candidate θ values to a compact interval spanning σ².Source: §3.2 · p. 7
  • As Toff grows, on an event whose probability tends to 1/4, Plug-In selects below σ² while Uncertainty-Aware selects above, yielding polynomial versus logarithmic regret.The resulting asymptotic regret-growth ratio is infinite on this event.Source: §3.2 · pp. 8–9

4 Bandits and beyond: Uncertainty-Aware simulation selection as a curvature regularization

Uncertainty-Aware (UA) selection averages candidate performance across plausible simulator perturbations, producing a local, curvature-dependent adjustment to Plug-In rankings. This can lower the ranking of candidates whose high Plug-In scores are brittle to simulator uncertainty.

4 Bandits and beyond: Uncertainty-Aware simulation selection as a curvature regularization

  • The local characterization applies beyond bandits whenever candidate procedures are evaluated in a simulator fitted from offline data.The simulator may be an explicit dynamics-and-reward model or a learned latent world model, and the evaluation criterion may be application-specific.Source: §4 · p. 9
  • Proposition 4 gives this characterization when candidate value is twice continuously differentiable in simulator parameters and its Hessian is Lipschitz.The ensemble perturbations have conditional mean zero and covariance Σ, with finite third moment.Source: §4 · p. 9
  • Averaging across simulator perturbations makes UA selection locally curvature-adjusted, lowering candidates whose high Plug-In scores are sensitive to uncertainty in the fitted simulator.The correction depends on candidate-value curvature in uncertain simulator directions; it does not uniformly penalize exploration or any particular hyperparameter value.Source: §4 · p. 9

5 Deep RL experiments

In MuJoCo control tasks, UA selection of PPO reward-shaping weights achieved higher mean success scores than Plug-In selection in every task and offline-data-size cell. The experiments fit simulator parameters from offline trajectories and evaluate the selected weights on the true environment.

5 Deep RL experiments

  • The experiments tune three PPO reward-shaping weights on Hopper and Walker2d, using grids of 25 and 30 candidate weight vectors, respectively.The weights cover a survival bonus, forward-progress term, and control-cost penalty; a larger forward-progress-to-control-cost ratio is termed more aggressive.Source: §5 · p. 10
  • Success score is evaluated after 3 × 10^5 environment steps and estimated from 50 evaluation episodes per reported value.The score is zero above an actuation bound and otherwise rises linearly with distance between two thresholds.Source: §5 · p. 10
  • The simulator varies robot mass, friction, and joint damping, which are estimated from offline trajectories; the offline sets contain 20, 80, or 320 episodes.The UA rule uses an empirical bootstrap over episodes with 12 ensemble members; both rules receive 12 training runs per candidate and are assessed over 300 replications.Source: §5 · p. 10
  • UA selection's mean success score exceeded Plug-In's by 0.005 to 0.023 in every cell, with significant differences in three of six cells.Its 10th-percentile score was higher in four cells and equal in the other two.Source: §5 · pp. 10–11

6 Discussion

The discussion distinguishes selection under finite-data simulator uncertainty from robustness to deployment shift, and contrasts UA selection with related approaches that evaluate policies or modify learners. The accompanying bandit details specify the environment, candidate grid, and simulation-based objective surface used for the figures.

6 Discussion

  • The paper isolates finite-data simulator uncertainty by assuming offline data and deployment come from the same environment, and identifies combining UA selection with distribution-shift methods as future work.It also names extensions beyond bandits and richer algorithm-design choices, and notes the need for reliable uncertainty quantification in complex simulators.Source: §6 · p. 11

A Related work

  • Prior offline algorithm-selection work commonly scores candidates in one fitted simulator; existing policy-selection methods assume Markovian candidates, unlike history-dependent online learners.The paper's related-work summary frames its focus as how simulator estimation uncertainty affects selection and regret.Source: A Related work · pp. 17, 19
  • Domain randomization addresses simulator-to-deployment mismatch for fixed policies, while this paper studies same-environment selection among online learners; other RL ensembles often alter learner actions, and robust methods use worst-case objectives.UA instead averages over the ensemble for selection.Source: A Related work · p. 18

B Simulation details for the two-armed bandit figures

B.1 Environments and candidate sets

  • Candidate exploration levels are normalized by noise variance, and the candidate grids are chosen to include each environment's best candidate.For the base setup, σ = 3; the true environment has margin 1 and noise level 3.Source: §B.1 · p. 19

B.2 The objective surface

  • The objective surface measures each candidate over a 40 × 49 grid of bandit margin and noise pairs, averaging 32,000 simulation runs per cell.The grid is offset from zero margin, and its nearest cell to the true environment is M_{0.975,3}.Source: §B.2 · p. 19

B.3 Offline data, the Plug-In simulator and the ensemble

The appendix describes the offline-data fitting and simulator-selection procedure, then reports an exploration-regret asymmetry across environments and details the figure construction and simulation budgets.

B.3 Offline data, the Plug-In simulator and the ensemble

  • The Plug-In simulator pools arm means and reward variance from the offline data, while bootstrap ensemble members are refitted on fresh datasets drawn from that fitted simulator.The two selection objectives are read from the measured surface by interpolation, without fresh rollout simulation at selection time.Source: §B.3 · p. 20

B.5 Asymmetry across environment configurations

  • Across all sixteen configurations, halving exploration cost 1.1 to 4.7 times as much excess regret as doubling it, for both UCB and Thompson Sampling.The median ratios were 1.7 for UCB and 1.9 for Thompson Sampling.Source: §B.5 · p. 21

B.6 Figures 3 and 6

  • Figures 3 and 6 show Plug-In and UA selected exploration levels, plus their difference, over bins of offline-data fits; contour lines mark 50%, 90%, and 99% of fitted-parameter mass.Clipping affects more than 5% of ensemble members only in a high-margin, high-noise corner containing almost none of the contour mass.Source: §B.6 · p. 21

B.7 Budgets

  • Each objective-surface cell averages 32,000 runs, and selection uses 10^6 offline datasets with ensemble members scored by interpolation rather than fresh simulation.The 50%, 90%, and 99% contour bins contain about 2,200, 470, and 69 datasets, respectively.Source: §B.7 · p. 21

C Deep reinforcement learning experiments

The appendix records definitions and settings behind Section 5, along with results not shown there.

C Deep reinforcement learning experiments

C.1 Tasks, reward and success criterion

The experiments evaluate reward-weight choices for Hopper and Walker2d using true-environment success scores, with policies trained under a fixed PPO configuration.

C.1 Tasks, reward and success criterion

  • Hopper-v5 and Walker2d-v5 episodes last at most 250 steps and end earlier if the robot leaves the healthy region.The reward combines a per-step survival bonus, forward velocity, and squared actuation; success thresholds are calibrated from true-environment runs at default weights.Source: §C.1 · pp. 21–22, Table 2 · p. 22

C.2 Candidate set and true success scores

  • 0.991 on Hopper and 0.689 on Walker2d are the true-environment success scores of the optimal weight vectors.The candidate sets contain 25 Hopper and 30 Walker2d weight vectors; the Walker2d forward-weight range is shifted downward so its optimum is interior.Source: §C.2 · p. 22

C.3 Learner

  • PPO uses a two-hidden-layer, width-64 tanh MLP for 300,000 environment steps, with reward weights, physics parameters, and seed as the varying settings.Evaluation uses deterministic policies over 50 episodes; reward normalization makes training invariant to reward-weight scale, so the survival weight is fixed at 1.Source: §C.3 · p. 22

C.4 True environment, offline data and sensor

The experiments identify MuJoCo physics parameters from noisy offline trajectories, form a bootstrap ensemble of fitted simulators, and compare selection rules using simulated scores.

C.4 True environment, offline data and sensor

  • The true MuJoCo environment uses physics factors λ∗ = (1.5, 0.7, 1.4), while independent Gaussian sensor noise makes parameter identification statistical.Noise with relative standard deviation 0.05 is applied to logged states and policy observations; the same noise settings are used across the true environment and simulators.Source: §C.4 · pp. 22–23

C.5 Identification

  • SIMEX reduces naive damping bias from +0.58 to +0.93 to +0.13 to +0.46 across every offline-data size on both robots, at larger spread.The estimate extrapolates a quadratic fit across added-noise levels to the value at ω = −1.Source: §C.5 · p. 24

C.6 UA ensemble

  • Each of 12 ensemble members bootstraps offline episodes with replacement and uses their SIMEX physics estimate to set its simulator parameters.The fitted ensemble members are evaluated on a lattice over friction and damping, with mass held at its estimated mean.Source: §C.6 · p. 24, §C.7 · p. 24, Table 5 · p. 25

C.7 Selection protocol

  • Plug-In and UA each use 12 simulated runs per candidate, while UA allocates one run per candidate to each of 12 members and averages scores across members.Across 300 replications, offline datasets and seed draws are paired between rules; only paired score contrasts are treated as evidence because replications are not independent.Source: §C.7 · pp. 24–25

C.8 Results

Across the reported cells, the mean UA variant scores highest among UA variants, while its adjustment of reward-weight ratios commonly moves selections toward the true optimum.

C.8 Results

  • The mean UA variant has the highest score of the three UA variants in every cell; the 10th-percentile variant is significantly worse than Plug-In on Walker2d at Toff = 20.The Borda variant is never significantly different from Plug-In.Source: §C.8 · p. 25
  • Given a Plug-In selection above the optimal θfwd/θctrl ratio, UA selects a smaller ratio in 55–95% of datasets; given a smaller ratio, it selects a larger one in 74–100%.Above-optimal ratios account for 74–98% of the Plug-In score shortfall below the optimum.Source: §C.8 · p. 25

D Theoretical analysis of the UCB algorithm

This section analyzes UCB(θ) selection in a two-armed Gaussian bandit, defining Plug-In and Uncertainty-Aware choices through regret minimization. It also makes explicit that deployment regret depends on the offline data.

D Theoretical analysis of the UCB algorithm

D.1 Main results and proofs

This section develops the main theoretical results and supporting arguments for the Plug-In and Uncertainty-Aware objectives, UCB regret regimes, and differences between the selection rules. It also gives asymptotic arguments for Gaussian-perturbed minimizers and introduces the Thompson Sampling setup analyzed next.

D.1 Main results and proofs

  • For almost every offline dataset, both the finite-horizon Plug-In and UA argmin sets are nonempty and compact.This follows from continuity of the objectives and compactness of Θ.Source: §D.1 · pp. 27–28

D.1.2 Asymmetric regret of UCB

  • For UCB, expected regret grows polynomially in T when θ < σ² and logarithmically when θ ≥ σ².The threshold θ = σ² separates the two asymptotic regimes.Source: §D.1.2 · p. 28

D.1.3 Plug-In and UA selection for UCB

  • On A_T^off, c_plug(D_off) < σ² < c_UA(D_off), and P(A_T^off) → 1/4 as T_off → ∞.Thus the selected limits fall on opposite sides of σ² on this event.Source: §D.1.3 · p. 30

D.2 Auxiliary lemmas

  • The auxiliary lemmas provide UCB regret and pull-count controls, and the Plug-In minimizer converges to the projection of the optimal-arm variance onto Θ.The minimizer result assumes distinct arm means, positive variances, and that the optimal-arm variance is not an endpoint of Θ.Source: §D.2 · pp. 30, 32, 33, 34
  • The auxiliary proof rules out UA minimizer limits below c = ΠΘ(σ̄²) by comparing objective exponents with those of a comparator.For θ < σ̄², it uses an event of positive conditional probability where the arm with variance σ̄² is optimal and has a gap in a bounded positive interval.Source: §D.2 · p. 36

E Theoretical analysis of the Thompson Sampling algorithm

  • The theoretical analysis specifies standard Gaussian Thompson Sampling with an improper flat prior and calls the algorithm TS(θ), where θ is its working reward variance.It defines Plug-In and Uncertainty-Aware selection analogously using TS regret; this part introduces the analysis but supplies no TS performance findings.Source: E Theoretical analysis of the Thompson… · pp. 36–37

E.1 Main results and proofs

This section develops the analysis of Plug-In and Uncertainty-Aware tuning and their regret, including existence and characterization of tuning choices and selected parameters. It also provides auxiliary results on regret minimizers, fixed-environment regret, Gaussian tails, and posterior sampling.

E.1 Main results and proofs

  • For T_off ≥ 4, both Thompson Sampling selection rules have nonempty, compact argmin sets for almost every offline dataset.The result is stated for every finite horizon T.Source: §E.1 · pp. 37–38

E.1.2 Asymmetric regret of Thompson Sampling

  • At θ = σ2, Thompson Sampling’s expected regret switches from polynomial growth for θ < σ2 to logarithmic growth for θ ≥ σ2.Theorem 12 characterizes this asymmetric regret in the two-armed Gaussian environment with µ1 > µ2.Source: §E.1.2 · pp. 38–39

E.1.3 Plug-In and UA selection for Thompson Sampling

  • On A_T, cplug(Doff) < σ2 < cUA(Doff), G(Doff) = ∞, and P(A_T) tends to 1/4 as T_off grows.When cplug(Doff) > σ2, the analysis instead gives G(Doff) = 1.Source: §E.1.3 · p. 40

E.2 Auxiliary lemmas

  • The auxiliary lemmas give fixed-environment TS regret and pull-count bounds over compact tuning intervals, using Gaussian tail estimates and coupled events.The stated lemma considers θ in a compact interval K; its proof uses Gaussian tail bounds and a coupling argument.Source: §E.2 · pp. 40, 43, 44
  • The Plug-In regret minimizer converges to the projection onto Θ of the optimal arm’s variance.The result is shown for fixed two-armed Gaussian environments with distinct means and positive variances.Source: §E.2 · pp. 48–49
  • For Gaussian-perturbed minimizers, every sequence converges to the projection onto Θ of the largest offline arm variance.The result applies when both offline variance estimates are positive.Source: §E.2 · pp. 49–50
  • For λ in the compact positive interval Λ=[λ−,λ+], the result asserts C′ depending only on Λ when λ+<1, and Cη depending only on η and Λ for every η>0.Source: §E.2 · p. 50
  • Lemma 18 bounds cumulative rounds associated with posterior-sample events by summing over arm-o pull counts, using sample independence and splitting at Rk = T.It defines the conditional probability that arm o’s posterior sample exceeds b after k pulls.Source: §E.2 · pp. 52–53

F Ensembles induce a curvature correction

Proposition 4 frames simulator ensembles as inducing a curvature correction under smoothness assumptions on the objective.

F Ensembles induce a curvature correction

Related papers

Loading 2609.32170v1…