PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Domain Randomization for Sim-to-real Transfer

Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, Liwei Wang

arXiv:2110.03239v2cs.LG

TL;DR

Real-world reinforcement learning is hindered by costly and risky data collection, while the theoretical basis of domain-randomized sim-to-real transfer remains limited. The paper models simulators as sets of parameterized MDPs, derives sim-to-real gap bounds, and shows transfer can succeed without real-world samples under finite or suitably smooth simulator classes. It also identifies history-dependent policies as important to domain-randomization guarantees.

  • Problem

    Real-world reinforcement learning requires costly and risky interactions, while the theoretical reasons for domain randomization's empirical sim-to-real success remain limited.

  • Method

    The paper models the simulator as a set of MDPs with tunable latent parameters and analyzes domain randomization through a latent MDP and infinite-horizon MDP learning.

  • Results

    Domain-randomized policies can incur only o(H) loss relative to the real-environment optimum when the simulator class is finite or satisfies a smoothness condition.

  • Takeaways & Limitations

    The theory indicates that sim-to-real transfer can succeed without real-world training samples and that memory is important for domain randomization.

  • Takeaways & Limitations

    For infinite simulator classes, domain randomization requires smoothness near the real MDP, meaning the sampling distribution must assign positive probability to a nearby MDP.

Abstract

from arXiv · show

Reinforcement learning encounters many challenges when applied directly in the real world. Sim-to-real transfer is widely used to transfer the knowledge learned from simulation to the real world. Domain randomization -- one of the most popular algorithms for sim-to-real transfer -- has been demonstrated to be effective in various tasks in robotics and autonomous driving. Despite its empirical successes, theoretical understanding on why this simple algorithm works is limited. In this paper, we propose a theoretical framework for sim-to-real transfers, in which the simulator is modeled as a set of MDPs with tunable parameters (corresponding to unknown physical parameters such as friction). We provide sharp bounds on the sim-to-real gap -- the difference between the value of policy returned by domain randomization and the value of an optimal policy for the real world. We prove that sim-to-real transfer can succeed under mild conditions without any real-world training samples. Our theory also highlights the importance of using memory (i.e., history-dependent policies) in domain randomization. Our proof is based on novel techniques that reduce the problem of bounding the sim-to-real gap to the problem of designing efficient learning algorithms for infinite-horizon MDPs, which we believe are of independent interest.

1 INTRODUCTION

Real-world reinforcement learning is costly and risky because strong algorithms often require many samples, motivating sim-to-real transfer and domain randomization. This paper develops a theoretical framework to explain when domain-randomized policies transfer successfully and why history-dependent policies matter.

  • State-of-the-art reinforcement-learning methods can require many samples, limiting their use when real-environment interactions are costly or risky.
  • Sim-to-real transfer trains an agent in an approximate simulator before deploying it in the real environment.
  • The sim-to-real gap is the performance mismatch between a policy trained in simulation and its real-world deployment.
  • Domain randomization varies simulated environment dynamics during training, exposing the agent to diverse environments before physical-world transfer.
  • The paper models the simulator as MDPs with tunable latent variables representing unknown physical parameters such as friction or wind velocity.
  • The authors establish a theoretical connection between domain randomization and latent MDPs, analyze sim-to-real optimality, and develop a proof framework based on infinite-horizon MDP learning.

2 RELATED WORK

Prior sim-to-real theory studies transfer difficulty, approximate simulators, and real-world adaptation, but does not analyze domain randomization without real-world samples. The paper connects this setting to latent MDPs and infinite-horizon average-reward reinforcement learning.

  • Earlier sim-to-real methods study gap measures, approximate simulators, or transfer procedures that reduce real-world sample complexity.
  • Existing theoretical results require real-world samples to fine-tune policies, whereas this work studies domain randomization without real-world training data.
  • Latent MDPs model an environment sampled from a set of MDPs at the beginning of each episode and form a special case of POMDPs.
  • The paper relates its analysis to sample-efficient algorithms for infinite-horizon average-reward MDPs.
  • The authors state that Algorithm 4 is the first efficient near-optimal-regret algorithm for infinite-horizon average-reward MDPs with general function approximation.

3 PRELIMINARIES

The preliminaries define finite-horizon MDP interaction, history-dependent policies, value functions, and practical domain-randomization procedures. These foundations distinguish general history-dependent policies from single-MDP optimal policies.

  • 3.1 EPISODIC MDPS: An episodic MDP specifies states, actions, transitions, rewards, horizon H, and an initial state.
  • 3.1 EPISODIC MDPS: At each step, the agent observes a state, chooses an action, receives a reward, and transitions until the episode ends.
  • 3.1 EPISODIC MDPS: A history-dependent policy maps the trajectory observed up to each step to a distribution over actions.
  • 3.1 EPISODIC MDPS: Value and Q-functions represent expected returns from states and state-action pairs under a policy.
  • 3.1 EPISODIC MDPS: For a single MDP, an optimal policy can depend only on the current state rather than prior history.
  • 3.2 PRACTICAL IMPLEMENTATION OF DOMAIN RANDOMIZATION: In practice, domain randomization varies physical parameters and visual properties across simulated training environments for zero-shot transfer.
  • 3.2 PRACTICAL IMPLEMENTATION OF DOMAIN RANDOMIZATION: Simulator calibration is used before randomization so the generated environments can cover real-world variability despite simulation imperfections.

4 FORMULATION

The formulation represents sim-to-real transfer as learning from a simulator-wide MDP set without real-world samples, and represents domain randomization as optimal control in a latent MDP. Its history-dependent policy is then analyzed through the resulting sim-to-real gap.

  • 4 FORMULATION: The paper introduces a theoretical formulation that models the simulator and supports analysis of domain-randomization optimality.
  • 4.1 SIM-TO-REAL TRANSFER: The simulator is a set U of MDPs sharing state and action spaces but differing in transition dynamics induced by latent parameters.
  • 4.1 SIM-TO-REAL TRANSFER: The real environment is represented by an MDP M* in the simulator class.
  • 4.1 SIM-TO-REAL TRANSFER: The objective is to choose a policy using U alone and measure its performance by the difference from an optimal policy in the real environment.
  • 4.1 SIM-TO-REAL TRANSFER: The framework learns policies exclusively in simulation, while real-world fine-tuning is left for future research.
  • 4.2 DOMAIN RANDOMIZATION AND LMDPS: A latent MDP samples one MDP from U according to distribution ν at the start of each episode, with the sampled environment hidden from the agent.
  • 4.2 DOMAIN RANDOMIZATION AND LMDPS: Domain randomization specifies ν, trains on the induced latent MDP, and is idealized as finding its globally optimal policy.
  • 4.2 DOMAIN RANDOMIZATION AND LMDPS: Because latent MDPs are POMDPs, the domain-randomization optimum generally depends on history, making memory and environment randomization critical to the guarantee.

5 MAIN RESULTS

The paper analyzes domain-randomization policies across finite and infinite simulator classes, showing sublinear sim-to-real gaps under communicating and, where needed, separation or smoothness conditions. The results also establish that randomization and memory are essential, while removing key assumptions can make the gap linear in H.

  • Overview: For finite simulator classes with separation, the sim-to-real gap is only O(log^3(H)), while the two other settings achieve ˜O(H^1/2), matching the best possible H-dependence.The analysis covers finite separated, finite non-separated, and infinite simulator classes in the long-horizon setting.
  • Assumptions: The analysis assumes communicating MDPs with bounded diameter D, an assumption described as natural for many robotics tasks.The paper also states that the diameter assumption is necessary under its framework.
  • Assumptions: Without the communicating-MDP assumption, a hard instance makes the domain-randomization policy ineffective, reaching the worst possible gap H.The paper notes that H is the worst possible gap for any policy.
  • Finite simulator classes with separation: In the separated finite setting, the proof constructs a policy that identifies the environment quickly and then follows the real MDP's optimal policy.The separation condition requires every pair of MDPs to differ on at least one state-action pair by at least δ.
  • Finite simulator classes without separation: For finite classes without separation, memory allows the policy to implicitly identify environments; combining memory with randomization reduces the worst-case gap from order H to order H^1/2.Without randomization, the policy is not trained on all environments; without memory, it cannot achieve sublinear worst-case loss.
  • Lower bound: The lower bound shows that any history-dependent policy can suffer a worst-case gap of at least order H^1/2 under the stated finite-class conditions.This lower bound explains why the H^1/2 dependence in the positive results is optimal in its horizon scaling.
  • Infinite simulator classes: For infinite simulator classes, smoothness near the real MDP is required; without it, the domain-randomization policy can still have an Ω(H) gap even when the MDPs have low-rank structure.Smoothness means the randomization distribution assigns positive probability to MDPs close to the real MDP.

6 PROOF OVERVIEW

The proof reduces sim-to-real gap bounds to constructing history-dependent base policies, then connects that construction to infinite-horizon average-reward learning. This yields efficient exploration approaches for finite and infinite simulator classes.

  • The central reduction bounds the domain-randomization policy through a base policy with small worst-case sim-to-real gap over the simulator class.
  • With separation conditions: For finite simulator classes with separation, the base policy identifies the real MDP by collecting informative state-action samples and eliminating inconsistent candidates.
  • Without separation conditions: Without separation, nearby MDPs may be indistinguishable, so the analysis reduces base-policy construction to regret minimization in infinite-horizon average-reward MDPs.
  • The finite- and infinite-horizon views are connected because the communicating-MDP assumption allows the agent to reach any state after the episodic horizon.
  • The authors propose two optimistic-exploration algorithms for finite and infinite simulator classes, including an efficient algorithm with near-optimal regret for general function approximation.

7 CONCLUSION

The paper models domain randomization as optimizing a latent MDP with uniform initialization and analyzes its transferred policy without real-world samples. It shows sublinear-in-horizon loss under finite or suitably smooth simulator classes.

  • Domain randomization is viewed as an oracle returning the optimal policy of a latent MDP with a uniform initialization distribution.
  • The policy learned by domain randomization can incur only o(H) loss relative to the real environment’s optimal value when the simulator class is finite or sufficiently smooth.
  • The analysis uses infinite-horizon average-reward MDPs, where policies are evaluated by long-run average gain rather than episodic returns.
  • The associated regret problem has established efficient methods, including UCRL2 for communicating MDPs with diameter-dependent regret bounds.
  • The function-class analysis characterizes transition complexity using eluder dimension and covering numbers under the L∞ norm.

B OMITTED PROOF IN SECTION 6

The omitted proofs instantiate the reduction with elimination-based exploration under separation and optimistic exploration without it. These constructions provide the base-policy guarantees used to bound domain-randomization performance.

  • After identifying the remaining MDP, the policy follows its optimal policy for the remaining interaction steps.
  • The separation-based policy repeatedly selects informative state-action pairs, gathers transition samples, and eliminates one candidate MDP at each comparison.
  • Theorem 5 bounds the sim-to-real gap of this history-dependent policy under the communicating and separation assumptions.
  • For finite simulator classes, optimistic exploration selects the candidate MDP with maximum expected gain and removes it after sufficient evidence shows it is not the real MDP.
  • The finite-class regret analysis bounds episode-wise regret using optimism, Bellman equations, and the elimination of inconsistent optimistic models.

C.3 INFINITE SIMULATOR CLASS

For infinite simulator classes, the paper develops a model-based optimistic algorithm using function-class complexity to decide when new data justify updating the optimistic model. Its regret is bounded through eluder dimension and covering-number terms.

  • The proposed method is a provably efficient model-based algorithm for infinite-horizon average-reward MDPs with general function approximation.
  • The algorithm maintains a candidate model class, selects an optimistic MDP with maximum expected gain, collects transition data, and updates the class as evidence accumulates.
  • Model and policy updates occur only when an importance score for newly collected samples exceeds a threshold, limiting unnecessary updates across episodes.
  • The regret bound depends on the 1/H-eluder dimension and the 1/H-covering number of the transition function class under the L∞ norm.

D.1 PROOF OF THEOREM 5

The proof bounds the sim-to-real gap by controlling the exploration time in stage 1 and the subsequent value difference. It shows that the true MDP remains in the candidate set and that stage 1 has bounded expected duration.

  • Candidate-set preservation: The true MDP is not eliminated from the candidate set during stage 1 with high probability.This ensures the later execution can use the optimal policy for the true MDP on the remaining steps.
  • Concentration: Concentration arguments control transition estimates and preserve the high-probability event needed for the final theorem bound.The proof invokes sub-exponential concentration, Azuma-Hoeffding’s inequality, Pinsker’s inequality, and union bounds.
  • Stage-1 exploration: E[h0] ≤ O( DM2 log2(SMH/δ) log(MH) δ4 ) bounds the expected number of stage-1 steps.The expectation is over randomness in the algorithm and environment.
  • Stage-1 exploration: The stage-1 procedure alternates policies for candidate MDPs to reach a designated state and gather information.The analysis bounds the expected travel time using the communicating property and the fact that the true MDP remains available.
  • Gap decomposition: The sim-to-real gap is bounded by a term proportional to the stage-1 duration plus an additional D-scale remainder.The proof first upper-bounds Gap(π̂, U) by O(E[h0] + D), then handles the remaining value difference through state distributions and Bellman-equation arguments.

E.2 PROOF OF THEOREM 2

The theorem proof derives the stated regret guarantee for Algorithm 3 by combining Theorem 6 with two supporting lemmas. The resulting policy is evaluated uniformly over the MDP class.

  • Theorem combination: The policy returned by Algorithm 3 has a regret bound established by Theorem 6 for any MDP in the uncertainty class.The theorem proof then combines this result with Lemmas 1 and 2 to obtain Theorem 2.
  • Theorem combination: The proof of Theorem 2 is completed by combining Theorem 6, Lemma 1, and Lemma 2.The supplied proof passage states this combination explicitly without reproducing the full bound.
  • Theorem scope: The guarantee is stated for every MDP M ∈ U rather than for a single fixed environment.This makes the theorem a class-wide result over the modeled uncertainty set.

F.1 PROOF OF THEOREM 7

The proof of Theorem 7 controls regret for a switching algorithm by combining optimism, concentration, and a bound on the number of episodes. The analysis uses the complexity of the function class to bound cumulative uncertainty.

  • Switching control: The total number of episodes is bounded, providing control over how often the algorithm switches policies.The proof introduces a switching rule and bounds its cumulative importance score.
  • Confidence sets: The true model remains in each confidence set with high probability, enabling optimistic regret decomposition.The proof uses concentration for the model class and the optimism condition to relate selected models to the true model.
  • Regret decomposition: The regret analysis separates martingale noise from the model-discrepancy term and controls the former with Azuma’s inequality.The remaining term is bounded using the construction of the confidence sets and the switching condition.
  • Complexity control: The cumulative model-discrepancy term is bounded through a function-class complexity argument involving covering numbers and eluder dimension.The proof invokes a prior lemma with G = F − F and obtains terms involving dim_E(F, 1/H) and log(H · N(F, 1/H)).
  • Theorem combination: The theorem follows by combining the regret bound for Algorithm 4 with Lemmas 1 and 2.The supplied proof identifies this combination as the final step for Theorem 4.
  • Hard instance: A hard MDP construction uses distinct optimal state-action pairs, showing how identifying the correct pair drives the lower-bound argument.The construction has 3M + 1 states and routes each initial action to an MDP-specific branch.

G.2 PROOF OF THEOREM 3

The proof establishes lower bounds by constructing hard MDP and bandit instances in which the agent must identify an unknown optimal choice. These constructions yield linear-in-horizon sim-to-real gaps in several settings.

  • Bandit lower bound: A K-armed-bandit-style construction gives a sim-to-real gap of at least Ω(·) by hiding the uniquely better arm among M = K choices.The proof maps MDP instances to bandit instances with one slightly higher-reward arm.
  • Two-state construction: Acting sub-optimally causes regret of order ε/δ per time step in the two-state construction.The sub-optimal action produces a uniform distribution over the two states, whereas the good action preserves access to the rewarding state more often.
  • MDP lower bound: Connecting O(S) copies through an A-ary tree forces identification among SA possible state-action choices.The construction transfers the identification difficulty into an infinite-horizon MDP lower bound.
  • Linear-mixture lower bound: Even linear-mixture MDPs with shared representation dimension d = O(log(M)) can have sim-to-real gap Ω(H) when M ≥ H.This proposition demonstrates that a low-dimensional shared representation alone does not prevent a horizon-scale gap.
Loading 2110.03239v2…