Exponential Safety Prices over the Randomization Box

Robots trained entirely in simulation are usually made robust by domain randomization: every training episode draws new physics (friction, mass, motor latency) from a box of plausible values, in the hope that the real robot falls somewhere inside. The policy is then optimized for average performance over that box. That average hides a few bad corners, such as low-friction or high-latency combinations, where the robot falls or collides. On hardware those corners are exactly where failures happen. This note proposes to give every region of the randomization box its own safety budget and its own price. Each price grows exponentially as that region spends more than its share of the budget, and the policy is trained against these prices. Online resource allocation uses the same mechanism to keep scarce capacity from being exhausted by an unknown stream of requests.

The catch is that an exponential price applied to noisy, heavy-tailed cost estimates is dangerous. One freak episode can inflate a price by orders of magnitude and freeze the policy into doing nothing. The second half of the idea therefore comes from high-probability optimization: price updates are fed with robust, clipped estimates of cost, so that a single training run, not merely an average over hypothetical runs, ends with every region inside its budget with probability $1-\delta$. The practical payoff is a safe sim-to-real method that needs no hand-tuned pessimism weight. It also makes the trade-off between average-case and worst-region safety explicit and controlled by one interpretable rate.

Core Claim

Sim-to-real safety failures arise largely because standard training enforces constraints on average over the randomization distribution. We claim that a per-region exponential dual price, with robust cost estimates inside the exponent, yields three things. It gives a single-run, high-probability bound on the worst-region constraint violation over the randomization box. Its scale behaves well, so the pessimism weight that current methods tune by hand is replaced by a budget and a rate. On hardware it matches the constraint satisfaction of the strongest existing pessimistic method while being less conservative.

Write the randomization box as $K$ regions with per-episode cost budgets $b_k$. Let $\hat C_k(t)$ be a robust estimate of the cumulative safety cost incurred in region $k$ up to training round $t$, and let $n_k(t)$ be the number of episodes sampled there. The price on region $k$ is

$$\lambda_k(t) = \lambda_0 \exp\big(\eta\,[\hat C_k(t) - n_k(t)\, b_k]\big),$$

where $\lambda_0$ is a small initial price and $\eta$ is a rate. This is the "actual minus expected consumption" rule of Single-Sample and Robust Online Resource Allocation, which proves that this exponential form achieves a $(1-\epsilon)$-approximation and survives adversarial outliers and value augmentation in abstract packing problems. Here it is transplanted to regions of physics space.

The policy maximizes reward minus $\sum_k \lambda_k\, c_k$, where $c_k$ is the safety cost of an episode drawn from region $k$. One limitation of online allocation theory turns into a strength in this setting. Those proofs need each request to be small relative to total capacity, which Optimal Posted Prices for Online Cloud Resource Allocation and A Learning-Augmented Approach to Online Allocation Problems flag as restrictive for "lumpy" cloud jobs. A single episode's cost is indeed tiny relative to a budget accumulated over millions of episodes.

Research Program

The work has three parts.

Analysis. We treat the policy optimizer as an approximate best-response oracle with bounded regret. We do not claim nonconvex policy convergence, because high-probability bounds for clipped methods still require smooth gradients (High Probability Analysis for Non-Convex Stochastic Optimization with Clipping), and contact-rich landscapes are not smooth. We then prove a high-probability bound on $\max_k$ of the average violation. With bounded costs, the exponential-weights argument underlying the price rule suggests a violation of order $\sqrt{\ln(K/\delta)/T}$ plus the oracle's regret. Under costs with only a bounded $p$-th moment, $p\in(1,2]$, we replace raw sums with clipped or median-of-means estimates. Truncated-mean concentration then adds a term of order $T^{-(p-1)/p}$. Without it, the exponent simply inherits the spike. Clipping comes from the Bernstein-martingale analysis of the clipping paper above. Median-of-means comes from the robust distance estimation in High probability guarantees for stochastic convex optimization.

Policy-side update. For the policy update itself, we use normalized policy gradients. From Gradient Clipping to Normalization for Heavy Tailed SGD shows that normalized SGD removes the clipping-threshold search and depends only logarithmically on $1/\delta$. This matters because a rising price multiplies the scale of the cost gradient. SGD Can Converge to Local Maxima warns that state-dependent noise of this kind can trap fixed-step optimizers. This step is the method's main concession to theory, and it is checked empirically rather than proven.

Implementation and composition with SPiDR. We build the method on top of SPiDR (SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer). SPiDR penalizes safety cost with an ensemble-disagreement term $\lambda\upsilon(s,a)$ and fixes $\lambda$ by hand. The two pieces address different failures. Disagreement captures the model's uncertainty about states. Regional prices capture the tail of the randomization distribution. In our method the regional prices multiply SPiDR's augmented cost, and $\lambda$ is fixed to a default. Regions are defined by a coarse grid over the two or three parameters with the largest effect on cost, found by a cheap sensitivity sweep. A learned partition is an extension, not a requirement.

Baselines

Uniform domain randomization. The naive reference is uniform domain randomization with an unconstrained or average-cost Lagrangian. This is the standard pipeline of Sim-to-Real: Learning Agile Locomotion For Quadruped Robots and Learning Dexterous In-Hand Manipulation, and the one SPiDR reports as producing 26.1x more violations on the Unitree Go1 and 6.2x more on the RaceCar.

SPiDR. The strongest competitor is SPiDR, which reports 100% real-world constraint satisfaction on both the Go1 and the RaceCar. Because its hardware safety is saturated, beating it cannot mean fewer violations on those tasks. It must mean one of three things: equal constraint satisfaction with higher task return; equal results with no per-task tuning of $\lambda$ (we give SPiDR a $\lambda$ grid of the same size as our $\eta$ grid, with identical simulator, network, and environment-step budget); or fewer violations on held-out out-of-box dynamics in simulation, where SPiDR has no reported number.

Worst-case robust RL. We include M2TD3 as implemented in RRLS (RRLS : Robust Reinforcement Learning Suite, code at SuReLI/RRLS). It represents the opposite extreme, optimizing against the worst parameters. RRLS evaluates it over 5 million steps and 10 seeds, but no reported result was found on Lacuna for per-environment scores.

Ablations. Two ablations isolate the key ingredients. The first keeps per-region duals but updates them linearly by projected dual ascent, which tests whether the exponential shape matters. The second keeps exponential prices but feeds them raw cost sums, which tests whether the robust estimate matters.

Why not just…?

Why not just tune SPiDR's pessimism weight? On the tasks SPiDR was tuned for, this may genuinely suffice. The threat is real. Our claim survives only if tuned SPiDR is either more conservative (lower return at the same safety) or tuned per task where our default transfers. The equal-grid comparison settles this. If tuned SPiDR matches us on return, safety, and held-out dynamics, the contribution shrinks to a tuning-free variant, and we will report it as such.

Why not just use a standard Lagrangian with linear dual ascent per region? This is the most serious alternative, because a per-region linear dual already removes averaging. The online-allocation evidence favors the exponential form. Optimal Posted Prices for Online Cloud Resource Allocation proves that exponential posted prices achieve the optimal competitive ratio, $\ln(\bar p/p)+1$. The ratio's dependence on value bounds rather than an absolute cost scale is our reason to expect lower sensitivity to step size, an expectation the experiments test rather than a proven property. Still, those results concern packing problems, not policy learning. The linear-dual ablation, swept over a dual step size with the same budget, directly measures dual oscillation, peak violation during training, and sensitivity to step size. If linear duals match exponential prices, we drop the pricing claim.

Why not just train against the worst parameters? Pure worst-case training is known to produce the sluggish, over-conservative behavior noted as a domain-randomization limitation. Our rate $\eta$ interpolates between the average and the worst region. Comparing against M2TD3 on RRLS return under perturbed mass and friction will show whether that interpolation buys return at equal safety.

Why not just clip gradients with a fixed threshold, as PPO already does? Fixed thresholds bias the optimization and require knowing the problem's noise scale (From Gradient Clipping to Normalization for Heavy Tailed SGD). More importantly, gradient clipping does not protect the price, which sits in an exponent and is driven by cost estimates. The raw-sum ablation, with heavy-tailed cost injected by rare low-friction regions, tests whether runs freeze or diverge without robust estimation.

Proposed Experiments

Tabular sanity check. We first use the 5x5 windy-cell gridworld of Provably Safe Sim-to-Real Transfer. That method achieves 0% unsafe iterations against 68.5% for an unconstrained baseline, using a tabular mismatch-region analysis. We check that regional prices recover near-zero violation without explicitly identifying the mismatch regions. We also verify the predicted $\sqrt{\ln(K/\delta)/T}$ decay of worst-region violation across 50 or more seeds by reporting the $1-\delta$ quantile, not the mean.

Simulation benchmarks. We then run Safety Gym PointGoal2 and the Real-World RL suite in MJX, matching SPiDR's setup (no reported numbers found on Lacuna for SPiDR there). We also run RRLS Hopper, Walker2d, and Ant with a contact or tilt cost added. Each training box is shrunk, and evaluation uses held-out dynamics just outside the box. This tests extrapolation, where Robust Domain Randomization for Reinforcement Learning notes that domain randomization fails. Metrics are worst-region violation, the 95th-percentile violation across seeds, return, and sensitivity of both to the single hyperparameter.

Decisive hardware check. On the Unitree Go1 and the RaceCar with SPiDR's constraints, we deploy policies trained with SPiDR's tuned $\lambda$ and with our default $\eta$. We count violations against SPiDR's 100% satisfaction and compare task return, such as velocity tracking or time to target. The proposal succeeds if three conditions hold: hardware satisfaction stays at 100%; return is measurably higher or matched without retuning; and both the linear-dual and raw-sum ablations show either higher worst-region violation or frozen policies in simulation. If the linear ablation matches the full method, the result will be published as a negative finding about exponential pricing.