Real-World Sample Complexity Scales with the Dimension of the Sim-to-Real Gap

A robot trained in a physics simulator usually fails on hardware because a handful of physical quantities are wrong: friction, mass, actuator delay, slip. Each wrong quantity slightly perturbs every transition the robot can make. This proposal asks how many real-world interactions are needed to repair a policy under this kind of gap, and argues that the right answer counts the few mismatched physical knobs rather than the number of states and actions. We propose an estimator that uses the simulator for two jobs. First, it computes which directions the dynamics could plausibly move in, by perturbing each knob and differencing. Second, it pools every real transition, from any state, to estimate only those few directions. We will prove matching upper and lower bounds showing that real-world sample complexity scales with the dimension $d$ of the gap, times the usual cubic dependence on the effective planning horizon. The bounds also include an explicit penalty for the part of reality that no knob explains.

The opportunity is that theory and practice currently disagree about what "the gap" is. The one provable sim-to-real result that reduces real samples, Provably Safe Sim-to-Real Transfer, assumes the simulator is exactly right at most state-action pairs and badly wrong at a few. Practitioners instead describe gaps that are diffuse but low-dimensional, as in the friction, gravity and density scalings of HIDIL or the control-frequency and friction mismatch of Sim2Explore. Under a diffuse gap the separable-shift analysis marks every pair as mismatched and falls back to learning from scratch. The goal is a rate that stays small in exactly the regime practitioners care about.

Core Claim

The setting is a discounted Markov decision process with discount $\gamma$ and effective horizon $1/(1-\gamma)$. Let $P_{\text{sim}}$ be the simulator's transition kernel, which we can query cheaply at any state-action pair. From the simulator, compute $d$ perturbation kernels $\Delta_1,\dots,\Delta_d$, each the finite-difference change in $P_{\text{sim}}$ when one physical parameter is nudged. We model reality as

$$P_{\text{real}}(\cdot\mid s,a) = P_{\text{sim}}(\cdot\mid s,a) + \sum_{i=1}^{d} \theta_i^\star \Delta_i(\cdot\mid s,a) + R(\cdot\mid s,a),$$

where $\theta^\star \in \mathbb{R}^d$ are the unknown true parameter offsets. The residual $R$ collects everything the knobs cannot express. We measure it only where it matters for planning, as $\rho = \max_{s,a} |R V^\star(s,a)|$, the largest error it induces in a one-step expected optimal value.

Our target theorem has two halves. The upper bound says that, with $n_{\text{real}}$ real transitions spread over a well-conditioned set of pairs, an $\epsilon$-optimal policy for reality is found once

$$n_{\text{real}} \gtrsim \frac{\kappa\, d}{(1-\gamma)^3 \epsilon^2}\log(1/\delta), \qquad \text{provided } \frac{\rho}{1-\gamma} \lesssim \epsilon .$$

Here $\kappa$ is a conditioning constant measuring how distinguishable the $d$ directions are along the value function, and $\delta$ is the failure probability. The lower bound says $\Omega\big(d/((1-\gamma)^3\epsilon^2)\big)$ real samples are necessary for any algorithm. When $\rho/(1-\gamma)$ exceeds $\epsilon$, the unexplained part must be learned pair by pair, and the rate reverts toward the tabular $|S||A|/((1-\gamma)^3\epsilon^2)$ of Azar et al. on the affected pairs.

The form of the bound comes from Azar et al.'s argument with one change. In the tabular lower bound each state-action pair is an independent unknown, which produces the factor $|S||A|$. In our model all pairs share $d$ unknowns, so each real sample informs every parameter at once. The cubic horizon factor survives because it comes from the variance of the value function, which the same Bernstein-plus-variance-recursion analysis controls.

Why the Obvious Idea Fails

The natural first idea at this intersection is the file's "multi-fidelity Bellman operator". It would import the control variate of MFPG into value iteration, subtracting a simulator estimate of the next-state value from the real one to cancel variance. That trick works in MFPG because two simulators can share random seeds, so their rollouts are correlated.

A physical robot shares no random numbers with a simulator. Given a real transition $(s,a,s'_{\text{real}})$, the simulator's expectation $P_{\text{sim}}V(s,a)$ is a known constant. Subtracting a constant leaves the variance of the real estimate unchanged, at $\mathrm{Var}_{P_{\text{real}}}(V)$. With uncoupled samples the control variate buys nothing, and neither does shrinking toward the simulator's pair-by-pair estimate. Estimating a mean known to lie within $\delta$ of a reference only helps when the target accuracy is coarser than $\delta$.

The simulator can therefore reduce real sample complexity only by supplying structure: telling us that thousands of pair-wise discrepancies are driven by a few shared causes. That observation is the basis of this proposal. It differs from the variance-reduction line of Sidford et al., whose reference-value trick we reuse inside the analysis but not as the source of savings.

Research Program

Estimator. The first piece is value-directed parameter estimation. At each round, given a current value estimate $V$, we fit $\hat\theta$ by least squares. The target for each real transition is $V(s')$, and the prediction is $P_{\text{sim}}V(s,a) + \sum_i \theta_i \Delta_i V(s,a)$. We then plan in the corrected model $P_{\text{sim}} + \sum_i \hat\theta_i \Delta_i$, which is free because the simulator is cheap.

This differs from ordinary system identification in one respect. System identification fits $\theta$ to predict next states, so it spends real samples matching directions in state space that do not affect value. Ours fits only the $d$ scalar projections that enter the Bellman update. Iterating the fit as $V$ improves, with a frozen high-accuracy reference value as in Sidford et al., is what we expect to give the cubic rather than quartic horizon dependence.

Theory. The work proceeds in three steps. The first is the well-specified upper bound ($\rho=0$), under a generative model of reality that allows resets to chosen states. We use this model because it is the setting in which minimax rates are currently tight. The second step is the misspecified extension. There we prove the $\rho/(1-\gamma)$ bias term and pair it with a residual test in the style of Provably Safe Sim-to-Real's statistical tests. The test flags pairs where fitted and observed next-state values disagree beyond sampling noise, and only those pairs are then learned tabularly. The result is a single rate that interpolates between the $d$-dimensional regime and the separable-shift regime, recovering $|B|$-scaling when the gap is sparse.

The third step is the lower bound. We build Azar-style sticky-state instances in which $d$ hidden parameters each control the stay probability of a disjoint block of states. Distinguishing $\pm\theta_i$ then costs $\Omega(1/((1-\gamma)^3\epsilon^2))$ samples per parameter.

Online extension. Real hardware cannot teleport between states, and this is the main open weakness. We treat it in a final step by pairing the estimator with simulator-trained exploration policies, as in Sim2Explore. The conditioning constant $\kappa$ then becomes a property of the states those policies reach. We will prove the online result only if the generative result is clean.

Baselines

Simulator only (do nothing). The naive reference point is the optimal policy of the uncorrected simulator, which uses zero real samples. It fixes the performance floor and shows how large the gap is on each instance.

Tabular learning from scratch. This is variance-reduced Q-value iteration from Sidford et al., which uses real samples only and attains the tabular minimax rate. It is run with the same real generative budget and represents what theory says without a simulator.

Action pruning. This is the method of How Does an Approximate Model Help in RL?. It prunes actions that look suboptimal in the simulator, then explores the survivors with real generative queries, costing about $N/((1-\gamma)^3\epsilon^2)$ real samples. It is the strongest existing provable competitor under diffuse gaps, because it does not require separability. It is run with the same total-variation budget given to it as a known constant, which is generous to it.

Hybrid-model method. This is the method of Provably Safe Sim-to-Real Transfer, the strongest method on its own benchmark. It reports 77,958 real samples to a near-optimal policy on the 5x5 windy gridworld, against 296,910 for reward-free safe RL without a simulator. We rerun it with its safety machinery disabled so that the comparison isolates sample efficiency.

Distributionally robust planning. This is robust value iteration from Near-Optimal DRRL with General $L_p$ Norms, with the uncertainty radius set just large enough to contain the true kernel. It uses zero real samples and gives the conservative floor. The REVI robust baseline of Sample Complexity of Robust RL with a Generative Model is reported for reference. For REVI there is no reported scalar result found on Lacuna for FrozenLake8x8 or the Gambler's problem.

System identification. This is maximum-likelihood fitting of the same $d$ parameters to next-state predictions, followed by planning. It is the ablation that isolates our key ingredient, value-directed fitting. It gets identical real samples, the identical perturbation basis, and the same number of refit rounds.

Continuous-control baselines. On MuJoCo we additionally run domain randomization plus fine-tuning and HIDIL. HIDIL reports 78.1% average normalized expert performance on the friction/gravity/density suite, versus 55.0% for behavioral cloning (HIDIL). We run MFPG's control-variate policy gradient with honest uncoupled "real" rollouts; there is no reported single-number result on Lacuna for it on its own suite.

What counts as winning. On tabular instances, beating the baselines means reaching the same $\epsilon$ with real samples that grow with $d$ and stay flat as $|S||A|$ grows, while action pruning and the hybrid model grow. On MuJoCo it means exceeding HIDIL's normalized performance, and fine-tuning's, at an equal real-interaction budget. Every method gets the same hyperparameter search budget, tuned on a held-out gap setting.

Why not just…?

Why not just do system identification and plan? This is the real threat. In the well-specified case, likelihood-based system identification with $d$ parameters plausibly achieves the same $d$-scaling. If experiments show that, the honest conclusion is that system identification is minimax-optimal here, and the theorem proves it for the first time. Our claimed empirical advantage is confined to two situations. The first is misspecification ($\rho>0$), where the likelihood fit trades value-relevant accuracy for accuracy in irrelevant state dimensions. The second is high-dimensional observations, where next-state likelihood is dominated by nuisance coordinates. The system-identification ablation, swept over $\rho$, settles this directly.

Why not just randomize the simulator's parameters? Domain randomization over the same $d$ knobs uses no real data. It must therefore hedge across the whole range, producing the conservatism the robust-RL results formalize. Sim2Explore reports 0/6 physical successes for sim-trained policies with fine-tuning on puck pushing, against 6/6 for its exploration-guided method. We include randomized policies as a baseline and expect a fixed optimality gap that no amount of simulation closes.

Why not just use the simulator as a control variate, as MFPG does? Without shared randomness between simulator and hardware, the correction term is a known constant and removes no variance, as argued above. We test this directly by running MFPG with uncoupled rollouts and confirming that its advantage over high-fidelity-only gradients disappears.

Why not just prune actions with the simulator? Wang et al.'s pruning is complementary. It reduces the action count but still pays per surviving pair, so under a diffuse gap its cost grows with $|S|$. We will also run pruning followed by our estimator, and the combination may be the best practical method.

Proposed Experiments

Diffuse-gap tabular instances. We build the tabular suite from benchmarks in the file, turning each into a diffuse, low-dimensional gap. FrozenLake8x8 uses slip probability as a single parameter ($d=1$), scaled up to larger grids to vary $|S|$ while holding $d$ fixed. The Gambler's problem uses the heads probability, shifted from its nominal 0.6. The 5x5 hazard gridworld of Provably Safe Sim-to-Real replaces localized windy cells with a global wind strength and direction ($d=2$). Keeping the original windy-cell version tests that we recover the separable regime.

Decisive tabular checks. Three checks decide the theory. First, real samples to reach $\epsilon$ should stay flat in $|S|$ at fixed $d$ and grow linearly in $d$ when we add independent knobs. Second, the horizon exponent is estimated by sweeping $\gamma$, with the prediction being close to 3. Third, when we inject a residual $R$ of controlled size, performance should break at $\rho/(1-\gamma)\approx\epsilon$ and the residual test should hand off to tabular learning.

Continuous control. We use the MuJoCo friction, gravity and density shifts at 0.5x, 1.5x and 2.0x from HIDIL and the MFPG/ODRL suite, with "reality" being a held-out MuJoCo configuration plus an unmodeled actuator delay as the residual. Here the estimator uses a learned value function, so the theory becomes a guide rather than a guarantee. The metric is normalized return versus number of real transitions.

Kill criterion. If the system-identification ablation matches value-directed fitting across the entire $\rho$ sweep on both tabular and MuJoCo instances, we drop the estimator as a contribution and publish the matching upper and lower bounds as a characterization of when parametric identification is optimal.