Fitting the Randomization Distribution as a Convex Problem

Robots trained in simulation often fail on real hardware because the simulator's physics (friction, damping, rope length) is wrong. The two standard fixes both have a cost. The first is to randomize the physics very widely, which makes the policy timid. The second is to search for the right physics, which is an expensive outer loop that can also get stuck. This note proposes replacing both with one small convex problem. We simulate a fixed bank of candidate physics settings once. We then ask which mixture of those settings reproduces the distribution of behavior seen in a handful of real rollouts. Because the mismatch between that mixture and reality is a convex quadratic in the mixture weights, every solution found is globally optimal. The weights themselves become the randomization distribution the policy trains on.

The second idea removes the knob that would otherwise need tuning. When the real data cannot pin down the physics, many mixtures fit equally well. We therefore select, among all best-fitting mixtures, the one with maximum entropy. This is a lexicographic "simple bilevel" problem: first fit the data, then among fits, randomize as broadly as the data allows. It is solvable with guarantees even though the fitting problem is not strictly convex. No entropy-penalty weight has to be tuned, so no policy has to be retrained just to set it. The claim is that this gives a policy that is broad where reality is uncertain and narrow where reality is known, at a tuning cost measured in solver seconds rather than policy trainings.

Core Claim

Let $P_1,\dots,P_K$ be the distributions of rollout features produced by $K$ candidate simulator settings under a fixed set of probe actions. Let $Q$ be the empirical feature distribution of $n$ real rollouts under the same probes. Let $w$ lie in the probability simplex $\Delta_K$. With a kernel $k$ on features, the squared maximum mean discrepancy between the mixture $\sum_k w_k P_k$ and $Q$ is

$$g(w) = w^\top A w - 2 w^\top b + c,$$

where $A_{jk}$ is the mean kernel value between rollouts of settings $j$ and $k$, $b_k$ is the mean kernel value between setting $k$ and real rollouts, and $c$ is a constant. The matrix $A$ is positive semidefinite, so $g$ is convex. It is typically rank-deficient exactly when different physics produce indistinguishable behavior, and this is the identifiability failure that A convex approach for Markov chain estimation from aggregate data via inverse optimal transport calls the steady-state trap. We choose the training distribution by solving

$$\min_{w \in \Delta_K} \; \sum_k w_k \log w_k \quad \text{s.t.} \quad g(w) \le \min_{\Delta_K} g + \epsilon_g,$$

where $\epsilon_g$ is set from the bootstrap variance of the empirical discrepancy rather than tuned. This is precisely the relaxed simple bilevel form solved by FC-BiO in Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem. That paper proves near-optimal rates without strong convexity. The contribution here is not a new solver. It is the observation that sim-to-real parameter identification and the choice of randomization width can be written as this single convex problem, so that what used to be hyperparameter search becomes one certified solve.

Relation to Prior Work

Three papers motivate the gap.

Auto-Tuned Sim-to-Real Transfer trains a neural "search parameter model" that predicts, one coordinate at a time, whether each simulator parameter is above or below the real value. It then iterates a binary search between policy training rounds. It showed that tuning physics from raw real video beats wide randomization. However, its search is non-convex, depends on the initial range, and handles coupled parameters poorly. We keep its setting (real clips, no rewards) but replace the directional classifier with a global convex fit over a simulated bank. We also output a distribution rather than a point.

The inverse-optimal-transport estimator of Mascherpa et al. proves joint convexity and a $t^{-1/2}$ error rate for recovering transition matrices from aggregate snapshots. It is restricted to small discrete chains, and it documents the plateau when observations sit near stationarity. We borrow its principle, which is to match aggregate distributions convexly, and apply it to continuous simulators. We treat its stalling phenomenon as a measurable quantity: the width of the near-optimal set. We do not treat it as a failure to be hidden.

Optimal Transport for Domain Adaptation aligns source and target features with entropic transport. Its regularization weights are fixed by grid search, which is the kind of hyperparameter overhead we remove.

Two lines of work supply or constrain the method.

FC-BiO supplies the solver. Its authors tested it only on least squares and logistic regression, so our use of it is also its first test on a distribution-matching lower level.

Online hyperparameter methods, Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters and Self-Tuning Networks, show that tuning inside one run beats outer-loop search. On Penn Treebank, Self-Tuning Networks reach 70.30 validation perplexity against 72.13 for Bayesian optimization. Both methods, however, operate on non-convex supervised objectives without optimality guarantees. We take the lesson that outer loops should be collapsed, but achieve it through convexity rather than hypergradients.

One caution constrains the design. The feature encoder applied to rollouts is non-convex and fixed. Our guarantee is therefore global optimality given the features, not end-to-end. The visual gap addressed by Unsupervised Pixel-Level Domain Adaptation with Generative Adversarial Networks can still corrupt the fit. We control for this by running each experiment twice, once with proprioceptive and tracked-keypoint features and once with image features.

Research Program

The program has five parts.

First, we build the simulated bank. For each task we choose up to six physical and visual parameters. We sample an initial set of candidate settings and roll out a fixed set of probe action sequences in each. This cost is paid once and reused for every real dataset and every policy.

Second, we handle grids that would be too large. Rather than a dense grid, we add candidate settings by conditional-gradient column generation, the standard method for convex optimization over measures. At each round we simulate the setting that most decreases $g$, and stop when the duality gap falls below $\epsilon_g$. This keeps global optimality over the continuous parameter space in the limit. It also makes the simulation budget adaptive rather than exponential in dimension. We are honest that beyond roughly six to eight parameters this may still be too costly, and we report where it breaks.

Third, we fit the weights. We solve the lexicographic problem with FC-BiO and train one policy on the resulting mixture.

Fourth, we make identifiability visible. We compute the diameter of the near-optimal set $\{w : g(w) \le \min g + \epsilon_g\}$, measured by the spread of the implied parameter distribution. Among a small library of candidate probe sequences, we pick the one that minimizes this diameter in simulation before touching hardware. This is our answer to the steady-state trap: choose real-world excitation that makes physics distinguishable, and report when no probe does.

Fifth, we analyze the statistics. With $n$ real rollouts, the empirical discrepancy concentrates at rate $n^{-1/2}$, the standard kernel mean embedding rate. This gives a principled $\epsilon_g$, and it predicts how the fitted mixture's width should shrink as real data grows. We test that prediction directly.

Baselines

The naive reference is uniform domain randomization over the full parameter box, with the same box used to build our bank. Auto-Tuned Sim-to-Real Transfer reports that this reaches 0% success on both cabinet slide and rope peg-in-hole on real hardware. We expect it to be weak on precision tasks, but it anchors the conservatism argument.

The strongest existing method is the Auto-Tuned search parameter model. It reports 90% real success on cabinet slide and 40% on rope peg-in-hole, and it reaches success with less than 20% of the simulation steps of randomization. We run it with its published procedure on the same tasks, the same real clips, and the same total simulator-step budget. That budget counts our bank and column generation against our method. Beating it means matching or exceeding its success rate at equal or lower total simulation steps. On sim-to-sim tasks with hidden parameters, it additionally means lower parameter recovery error in coupled-parameter settings. We deliberately include the coupled settings because that is where coordinate-wise search is weakest.

Black-box search is the HPO-overhead competitor. BOHB from BOHB: Robust and Efficient Hyperparameter Optimization at Scale searches simulator parameters to minimize the same discrepancy $g$ on single settings, with the same simulation budget. A second variant searches the width of a Gaussian randomization distribution by training policies. We know of no reported result on Lacuna for BOHB on sim-to-real parameter identification.

Three ablations isolate the key ingredients.

The first is best single grid point: take the argmin of $g$ over bank members, a Dirac distribution. This isolates whether a mixture matters at all.

The second is entropy-penalized fitting with a grid-searched penalty weight. The weight is selected by real-world or held-out-simulator policy success, with the number of policy trainings recorded. This isolates whether the lexicographic bilevel form truly removes tuning overhead or merely hides it.

The third varies $\epsilon_g$ at 0.5×, 1× and 2× the bootstrap estimate. This checks that our remaining knob is insensitive.

Why not just…?

Why not just pick the single simulator setting with the smallest discrepancy? Over a fixed bank this is also globally optimal, and it is the sharpest threat. Where it fails is when real behavior is itself a spread, such as varying cabinets or rope stiffness across trials. It also fails when the data cannot distinguish settings, because it commits arbitrarily to one physics and yields a brittle policy. The best-single-point ablation settles this. If it matches the mixture on every task, including our deliberately heterogeneous sim-to-sim targets, then the mixture and bilevel machinery is unnecessary. In that case we would report the result as "convex identification plus exhaustive argmin" and drop the entropy component.

Why not just use Bayesian optimization or BOHB over simulator parameters? These methods are sample-efficient on smooth low-dimensional objectives and could match us for three or four parameters. They return a point, however, not a calibrated distribution. Choosing randomization width with them requires policy retraining in the loop, which is the overhead Making a Science of Model Search describes. The equal-budget BOHB comparison, together with a count of policy trainings, will show whether our advantage is real or only a matter of dimension. We expect parity at low dimension and an advantage when parameters are coupled.

Why not just widen domain randomization and let the policy become robust? The file's evidence is direct: 0% versus 90% on cabinet slide in Auto-Tuned Sim-to-Real Transfer. Our method includes wide randomization as a special case, since it is what the bilevel returns when real data is uninformative. It narrows only where the data warrants.

Proposed Experiments

The main testbed is sim-to-sim transfer on the DeepMind Control Suite tasks used by Auto-Tuned (Cheetah Run, Walker Walk, Finger Spin, Ball in Cup). No reported numbers were found on Lacuna for these, so all methods are run fresh. The "real" environment is a held-out simulator whose hidden parameters we set in three regimes: a single point, a point with strongly coupled parameters (friction and damping trading off), and a genuine mixture across episodes. The metrics are parameter-distribution error in Wasserstein distance, target return, and total simulation steps, including tuning.

If hardware is available, we repeat cabinet slide and rope peg-in-hole against the 90% and 40% Auto-Tuned figures, using identical real clips.

Four checks are decisive. First, in the coupled regime, our recovered distribution should concentrate on the true ridge, while the search parameter model's error grows with coupling strength. Second, in the mixture regime, the best-single-point ablation should lose target return and our mixture should not. If this fails, the central claim fails. Third, the entropy-penalized variant should need several policy trainings to match what our method reaches with one. Fourth, the near-optimal-set diameter should shrink at roughly $n^{-1/2}$ in the number of real rollouts. It should stay flat under probes that keep the system near steady state, and this plateau should disappear under our selected probe sequence. We also report the feature ablation (proprioceptive versus image features) to show how much of any failure comes from the non-convex encoder rather than from the convex fit.