Year: 2021

Abstract:
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.

heading: 1 INTRODUCTION
text: Reinforcement Learning (RL) is concerned with sequential decision making, in which the agent interacts with the environment to maximize its cumulative rewards. This framework has achieved tremendous empirical successes in various fields such as Atari games, Go and StarCraft (Mnih et al., 2013; Silver et al., 2017; Vinyals et al., 2019). However, state-of-the-art algorithms often require a large amount of training samples to achieve such a good performance. While feasible in applications that have a good simulator such as the examples above, these methods are limited in applications where interactions with the real environment are costly and risky, such as healthcare and robotics.
One solution to this challenge is sim-to-real transfer (Floreano et al., 2008; Kober et al., 2013). The basic idea is to train an RL agent in a simulator that approximates the real world and then transfer the trained agent to the real environment. This paradigm has been widely applied, especially in robotics (Rusu et al., 2017; Peng et al., 2018; Chebotar et al., 2019) and autonomous driving (Pouyanfar et al., 2019; Niu et al., 2021). Sim-to-real transfer is appealing as it provides an essentially unlimited amount of data to the agent, and reduces the costs and risks in training.
However, sim-to-real transfer faces the fundamental challenge that the policy trained in the simulated environment may have degenerated performance in the real world due to the sim-to-real gap—the mismatch between simulated and real environments. In addition to building higher-fidelity simulators to alleviate this gap, domain randomization is another popular method (Sadeghi & Levine, 2016; Tobin et al., 2017; Peng et al., 2018; OpenAI et al., 2018). Instead of training the agent in a single simulated environment, domain randomization randomizes the dynamics of the environment, thus exposes the agent to a diverse set of environments in the training phase. Policies learned entirely in the simulated environment with domain randomization can be directly transferred to the physical world with good performance (Sadeghi & Levine, 2016; Matas et al., 2018; OpenAI et al., 2018).
In this paper, we focus on understanding sim-to-real transfer and domain randomization from a theoretical perspective. The empirical successes raise the question: can we provide guarantees for the sub-optimality gap of the policy that is trained in a simulator with domain randomization
and directly transferred to the physical world? To do so, we formulate the simulator as a set of MDPs with tunable latent variables, which corresponds to unknown parameters such as friction coefficient or wind velocity in the real physical world. We model the training process with domain randomization as finding an optimal history-dependent policy for a latent MDP, in which an MDP is randomly drawn from a set of MDPs in the simulator at the beginning of each episode.
Our contributions can be summarized as follows:
• We propose a novel formulation of sim-to-real transfer and establish the connection between domain randomization and the latent MDP model (Kwon et al., 2021). The latent MDP model illustrates the uniform sampling nature of domain randomization, and helps to analyze the sim-to-real gap for the policy obtained from domain randomization.
• We study the optimality of domain randomization in three different settings. Our results indicate that the sim-to-real gap of the policy trained in the simulation can be o(H) when the randomized simulator class is finite or satisfies certain smoothness condition, where H is the horizon of the real-world interaction. We also provide a lower bound showing that such benign conditions are necessary for efficient learning. Our theory highlights the importance of using memory (i.e., history-dependent policies) in domain randomization.
• To analyze the optimality of domain randomization, we propose a novel proof framework which reduces the problem of bounding the sim-to-real gap of domain randomization to the problem of designing efficient learning algorithms for infinite-horizon MDPs, which we believe are of independent interest.
• As a byproduct of our proof, we provide the first provably efficient model-based algorithm for learning infinite-horizon average-reward MDPs with general function approximation (Algorithm 4 in Appendix C.3). Our algorithm achieves a regret bound of Õ(D √ deT ),
where T is the total timesteps and de is a complexity measure of a certain function class F that depends on the eluder dimension (Russo & Van Roy, 2013; Osband & Van Roy, 2014).

heading: 2 RELATED WORK
text: Sim-to-Real and Domain Randomization The basic idea of sim-to-real is to first train an RL agent in simulation, and then transfer it to the real environment. This idea has been widely applied to problems such as robotics (e.g., Ng et al., 2006; Bousmalis et al., 2018; Tan et al., 2018; OpenAI et al., 2018) and autonomous driving (e.g., Pouyanfar et al., 2019; Niu et al., 2021). To alleviate the influence of reality gap, previous works have proposed different methods to help with sim-to-real transfer, including progressive networks (Rusu et al., 2017), inverse dynamics models (Christiano et al., 2016) and Bayesian methods (Cutler & How, 2015; Pautrat et al., 2018). Domain randomization is an alternative approach to making the learned policy to be more adaptive to different environments (Sadeghi & Levine, 2016; Tobin et al., 2017; Peng et al., 2018; OpenAI et al., 2018), thus greatly reducing the number of real-world interactions.
There are also theoretical works related to sim-to-real transfer. Jiang (2018) uses the number of different state-action pairs as a measure of the gap between the simulator and the real environment. Under the assumption that the number of different pairs is constant, they prove the hardness of sim-to-real transfer and propose efficient adaptation algorithms with further conditions. Feng et al. (2019) prove that an approximate simulator model can effectively reduce the sample complexity in the real environment by eliminating sub-optimal actions from the policy search space. Zhong et al. (2019) formulate a theoretical sim-to-real framework using the rich observation Markov decision processes (ROMDPs), and show that the transfer can result in a smaller real-world sample complexity. None of these results study benefits of domain randomization in sim-to-real transfer. Furthermore, all above works require real-world samples to fine-tune their policy during training, while our work and the domain randomization algorithm do not.
POMDPs and Latent MDPs Partially observable Markov decision processes (POMDPs) are a general framework for sequential decision-making problems when the state is not fully observable (Smallwood & Sondik, 1973; Kaelbling et al., 1998; Vlassis et al., 2012; Jin et al., 2020a; Xiong et al., 2021). Latent MDPs (Kwon et al., 2021), or LMDPs, are a special type of POMDPs, in which the real environment is randomly sampled from a set of MDPs at the beginning of each
episode. This model has been widely investigated with different names such as hidden-model MDPs and multi-model MDPs. There are also results studying the planning problem in LMDPs, when the true parameters of the model is given (Chades et al., 2012; Buchholz & Scheftelowitsch, 2019; Steimle et al., 2021) . Kwon et al. (2021) consider the regret minimization problem for LMDPs, and provide efficient learning algorithms under different conditions. We remark that all works mentioned above focus on the problems of finding the optimal policies for POMDPs or latent MDPs, which is perpendicular to the central problem of this paper—bounding the performance gap of transferring the optimal policies of latent MDPs from simulation to the real environment.
Infinite-horizon Average-Reward MDPs Recent theoretical progress has produced many provably sample-efficient algorithms for RL in infinite-horizon average-reward setting. Nearly matching upper bounds and lower bounds are known for the tabular setting (Jaksch et al., 2010; Fruit et al., 2018; Zhang & Ji, 2019; Wei et al., 2020). Beyond the tabular case, Wei et al. (2021) propose efficient algorithms for infinite-horizon MDPs with linear function approximation. To the best of our knowledge, our result (Algorithm 4) is the first efficient algorithm with near-optimal regret for infinite-horizon average-reward MDPs with general function approximation.

heading: 3 PRELIMINARIES

heading: 3.1 EPISODIC MDPS
text: We consider episodic RL problems where each MDP is specified byM = (S,A, P,R,H, s1). S and A are the state and the action space with cardinality S and A respectively. We assume that S and A are finite but can be extremely large. P : S × A → ∆(S) is the transition probability matrix so that P (·|s, a) gives the distribution over states if action a is taken on state s, R : S × A → [0, 1] is the reward function. H is the number of steps in one episode.
For simplicity, we assume the agent always starts from the same state in each episode, and use s1 to denote the initial state at step h = 1. It is straight-forward to extend our results to the case with random initialization. At step h ∈ [H], the agent observes the current state sh ∈ S , takes action ah ∈ A, receives reward R(sh, ah), and transits to state sh+1 with probability P (sh+1|sh, ah). The episode ends when sH+1 is reached.
We consider the history-dependent policy class Π, where π ∈ Π is a collection of mappings from the history observations to the distributions over actions. Specifically, we use trajh = {(s1, a1, s2, a2, · · · , sh) | si ∈ S, ai ∈ A, i ∈ [h]} to denote the set of all possible trajectories of history till step h. We define a policy π ∈ Π to be a collection of H policy functions {πh : trajh → ∆(A)}h∈[H]. We define V πM,h : S → R to be the value function at step h under policy π on MDP M, i.e., V πM,h(s) = EM,π[ ∑H t=hR(st, at) | sh = s]. Accordingly, we define QπM,h : S × A → R to be the Q-value function at step h: QπM,h(s, a) = EM,π[R(sh, ah) + ∑H t=h+1R(st, at) | sh = s, ah = a].
We use π∗M to denote the optimal policy for a single MDPM. It can be shown that there exists π∗M such that the policy at step h depends on only the state at step h but not any other prior history. That is, π∗M can be expressed as a collection of H policy functions mapping from S to ∆(A). We use V ∗M,h and Q ∗ M,h to denote the optimal value and Q-functions under the optimal policy π ∗ M at step h.

heading: 3.2 PRACTICAL IMPLEMENTATION OF DOMAIN RANDOMIZATION
text: In this subsection, we briefly introduce how domain randomization works in practical applications. Domain randomization is a popular technique for improving domain transfer (Tobin et al., 2017; Peng et al., 2018; Matas et al., 2018), which is often used for zero-shot transfer when the target domain is unknown or cannot be easily used for training. For example, by highly randomizing the rendering settings for their simulated training set, Sadeghi & Levine (2016) trained vision-based controllers for a quadrotor using only synthetically rendered scenes. OpenAI et al. (2018) studied the problem of dexterous in-hand manipulation. The training is performed entirely in a simulated
environment in which they randomize the physical parameters of the system like friction coefficients and vision properties such as object’s appearance.
To apply domain randomization in the simulation training, the first step before domain randomization is usually to build a simulator that is close to the real environment. The simulated model is further improved to match the physical system more closely through calibration. Though the simulation is still a rough approximation of the physical setup after these engineering efforts, these steps ensure that the randomized simulators generated by domain randomization can cover the real-world variability. During the training phase, many aspects of the simulated environment are randomized in each episode in order to help the agent learn a policy that generalizes to reality. The policy trained with domain randomization can be represented using recurrent neural network with memory such as LSTM (Yu et al., 2018; OpenAI et al., 2018; Doersch & Zisserman, 2019). Such a memory-augmented structure allows the policy to potentially identify the properties of the current environment and adapt its behavior accordingly. With sufficient data sampled using the simulator, the agent can find a near-optimal policy w.r.t. the average value function over a variety of simulation environments. This policy has shown its great adaptivity in many previous results, and can be directly applied to the physical world without any real-world fine-tuning (Sadeghi & Levine, 2016; Matas et al., 2018; OpenAI et al., 2018).

heading: 4 FORMULATION
text: In this section, we propose our theoretical formulation of sim-to-real and domain randomization. The corresponding models will be used to analyze the optimality of domain randomization in the next section, which can also serve as a starting point for future research on sim-to-real.

heading: 4.1 SIM-TO-REAL TRANSFER
text: In this paper, we model the simulator as a set of MDPs with tunable latent parameters. We consider an MDP set U representing the simulator model with joint state space S and joint action space A. Each MDP M = (S,A, PM, R,H, s1) in U has its own transition dynamics PM, which corresponds to an MDP with certain choice of latent parameters. Our result can be easily extended to the case where the rewards are also influenced by the latent parameters. We assume that there exists an MDPM∗ ∈ U that represents the dynamics of the real environment. We can now explain our general framework of sim-to-real. For simplicity, we assume that during the simulation phase (or training phase), we are given the entire set U that represents MDPs under different tunable latent parameter. Or equivalently, the learning agent is allowed to interact with any MDPM∈ U in arbitrary fashion, and sample arbitrary amount of trajectories. However, we do not know which MDPM ∈ U represents the real environment. The objective of sim-to-real transfer is to find a policy π purely based on U , which performs well in the real environment. In particular, we measure the performance in terms of the sim-to-real gap, which is defined as the difference between the value of learned policy π and the value of an optimal policy for the real world:
Gap(π) = V ∗M∗,1(s1)− V πM∗,1(s1). (1)
We remark that in our framework, the policy π is learned exclusively in simulation without the use of any real world samples. We study this framework because (1) our primary interests—domain randomization algorithm does not use any real-world samples for training; (2) we would like to focus on the problem of knowledge transfer from simulation to the real world. The more general learning paradigm that allows the fine-tuning of policy learned in simulation using real-world samples can be viewed as a combination of sim-to-real transfer and standard on-policy reinforcement learning, which we left as an interesting topic for future research.

heading: 4.2 DOMAIN RANDOMIZATION AND LMDPS
text: We first introduce Latent Markov decision processes (LMDPs) and then explain domain randomization in the viewpoint of LMDPs. A LMDP can be represented as (U , ν), where U is a set of MDPs with joint state space S and joint action space A, and ν is a distribution over U . Each MDP M = (S,A, PM, R,H, s1) in U has its own transition dynamics PM that may differs from other
MDPs. At the start of an episode, an MDPM∈ U is randomly chosen according to the distribution ν. The agent does not know explicitly which MDP is sampled, but she is allowed to interact with this MDPM for one entire episode. Domain randomization algorithm first specifies a distribution over tunable parameters, which equivalently gives a distribution ν over MDPs in simulator U . This induces a LMDP with distribution ν. The algorithm then samples trajectories from this LMDP, runs RL algorithms in order to find the near-optimal policy of this LMDP. We consider the ideal scenario that the domain randomization algorithm eventually find the globally optimal policy of this LMDP, which we formulate as domain randomization oracle as follows: Definition 1. (Domain Randomization Oracle) Let U be the set of MDPs generated by domain randomization and ν be the uniform distribution over U . The domain randomization oracle returns an optimal history-dependent policy π∗DR of the LMDP (U , ν):
π∗DR = arg max π∈Π EM∼νV πM,1(s1). (2)
Since LMDP is a special case of POMDPs, its optimal policy π∗DR in general will depend on history. This is in sharp contrast with the optimal policy of a MDP, which is history-independent. We emphasize that both the memory-augmented policy and the randomization of the simulated environment are critical to the optimality guarantee of domain randomization. We also note that we don’t restrict the learning algorithm used to find the policy π∗DR, which can be either in a model-based or model-free style. Also, we don’t explicitly define the behavior of π∗DR. The only thing we know about π∗DR is that it satisfies the optimality condition defined in Equation 2. In this paper, we aim to bound the sim-to-real gap of π∗DR, i.e., Gap(π ∗ DR,U) under different regimes.

heading: 5 MAIN RESULTS
text: We are ready to present the sim-to-real gap of π∗DR in this section. We study the gap in three different settings under our sim-to-real framework: finite simulator class (the cardinality |U| is finite) with the separation condition (MDPs in U are distinct), finite simulator class without the separation condition, and infinite simulator class. During our analysis, we mainly study the long-horizon setting where H is relatively large compared with other parameters. This is a challenging setting that has been widely-studied in recent years (Gupta et al., 2019; Mandlekar et al., 2020; Pirk et al., 2020). We show that the sim-to-real gap of π∗DR is only O(log
3(H)) for the finite simulator class with the separation condition, and only Õ( √ H) in the last two settings, matching the best possible lower bound in terms of H .
In our analysis, we assume that the MDPs in U are communicating MDPs with a bounded diameter. Assumption 1 (Communicating MDPs (Jaksch et al., 2010)). The diameter of any MDPM∈ U is bounded by D. That is, consider the stochastic process defined by a stationary policy π : S → A on an MDP with initial state s. Let T (s′|M, π, s) denote the random variable for the first time step in which state s′ is reached in this process, then
max s6=s′∈S min π:S→A
E [T (s′ | M, π, s)] ≤ D.
This is a natural assumption widely used in the literature (Jaksch et al., 2010; Agrawal & Jia, 2017; Fruit et al., 2020). The communicating MDP model also covers many real-world tasks in robotics. For example, transferring the position or angle of a mechanical arm only costs constant time. Moreover, the diameter assumption is necessary under our framework. Proposition 1. Without Assumption 1, there exists a hard instance U so that Gap(π∗DR) = Ω(H).
We prove Proposition 1 in Appendix G.1. Note that the worst possible gap of any policy is H , so π∗DR becomes ineffective without Assumption 1.

heading: 5.1 FINITE SIMULATOR CLASS WITH SEPARATION CONDITION
text: As a starting point, we will show the sim-to-real gap when the MDP set U is a finite set with cardinality M . Intuitively, a desired property of π∗DR is the ability to identify the environment the agent is
exploring within a few steps. This is because π∗DR is trained under uniform random environments, so we hope it can learn to tell the differences between environments. As long as π∗DR has this property, the agent is able to identify the environment dynamics quickly, and behave optimally afterwards (note that the MDP set U is known to the agent). Before presenting the general results, we first examine a simpler case where all MDPs in U are distinct. Concretely, we assume that any two MDPs in U are well-separated on at least one stateaction pair. Note that this assumption is much weaker than the separation condition in Kwon et al. (2021), which assumes strongly separated condition for each state-action pair. Assumption 2 (δ-separated MDP set). For any M1,M2 ∈ U , there exists a state-action pair (s, a) ∈ S×A, such that the L1 distance between the probability of next state of the different MDPs is at least δ, i.e.
‖(PM1 − PM2) (· | s, a)‖1 ≥ δ. (3)
The following theorem shows the sim-to-real gap of π∗DR in δ-separated MDP sets. Theorem 1. Under Assumption 1 and Assumption 2, for anyM ∈ U , the sim-to-real gap of π∗DR is at most
Gap(π∗DR) = O
( DM3 log(MH) log2(SMH/δ)
δ4
) . (4)
The proof of Theorem 1 is deferred to Appendix D. Though the dependence on M and δ may not be tight, our bound has only poly-logarithmic dependence on the horizon H .
The main difficulty to prove Theorem 1 is that we do not know what π∗DR does exactly despite knowing a simple and clean strategy in the real-world interaction with minimum sim-to-real gap. That is, to firstly visit the state-action pairs that help the agent identify the environment quickly and then follow the optimal policy in the real MDPM∗ after identifyingM∗. Therefore, we use a novel constructive argument in the proof. We construct a base policy that implements the idea mentioned above, and show that π∗DR cannot be much worse than the base policy. The proof overview can be found in Section 6.

heading: 5.2 FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION
text: Now we generalize the setting and study the sim-to-real gap of π∗DR when U is finite but not necessary a δ-separated MDP set. Surprisingly, we show that π∗DR can achieve Õ( √ H) sim-to-real gap when |U| = M . Theorem 2. Under Assumption 1, when the MDP set induced by domain randomization U is a finite set with cardinality M , the sim-to-real gap of π∗DR is upper bounded by
Gap(π∗DR) = O ( D √ M3H log(MH) ) . (5)
Theorem 2 is proved in Appendix E. This theorem implies the importance of randomization and memory in the domain randomization algorithms (Sadeghi & Levine, 2016; Tobin et al., 2017; Peng et al., 2018; OpenAI et al., 2018). With both of them, we successfully reduce the worst possible gap of π∗DR from the order of H to the order of √ H , so per step loss will be only Õ(H−1/2). Without randomization, it is not possible to reduce the worst possible gap (i.e., the sim-to-real gap) because the policy is even not trained on all environments. Without memory, the policy is not able to implicitly “identify” the environments, so it cannot achieve sublinear loss in the worst case.
We also use a constructive argument to prove Theorem 2. However, it is more difficult to construct the base policy because we do not have any idea to minimize the gap without the well-separated condition (Assumption 2). Fortunately, we observe that the base policy is also a memory-based policy, which basically can be viewed as an algorithm that seeks to minimize the sim-to-real gap in an unknown underlying MDP in U . Therefore, we connect the sim-to-real gap of the base policy with the regret bound of the algorithms in infinite-horizon average-reward MDPs (Bartlett & Tewari, 2012; Fruit et al., 2018; Zhang & Ji, 2019). The proof overview is deferred to Section 6.
To illustrate the hardness of minimizing the worst case gap, we prove the following lower bound for Gap(π,U) to show that any policy must suffer a gap at least Ω( √ H).
Theorem 3. Under Assumption 1, suppose A ≥ 10, SA ≥ M ≥ 100, D ≥ 20 logAM,H ≥ DM , for any history dependent policy π = {πh : trajh → A}Hh=1, there exists a set of M MDPs U = {Mm}Mm=1 and a choice ofM∗ ∈ U such that Gap(π) is at least Ω( √ DMH).
The proof of Theorem 3 follows the idea of the lower bound proof for tabular MDPs (Jaksch et al., 2010), which we defer to Appendix G.2. This lower bound implies that Ω( √ H) sim-to-real gap is unavoidable for the policy π∗DR when directly transferred to the real environment.

heading: 5.3 INFINITE SIMULATOR CLASS
text: In real-world scenarios, the MDP class is very likely to be extensively large. For instance, many physical parameters such as surface friction coefficients and robot joint damping coefficients are sampled uniformly from a continuous interval in the Dexterous Hand Manipulation algorithms (OpenAI et al., 2018). In these cases, the induced MDP set U is large and even infinite. A natural question is whether we can extend our analysis to the infinite simulator class case, and provide a corresponding sim-to-real gap.
Intuitively, since the domain randomization approach returns the optimal policy in the average manner, the policy π∗DR can perform bad in the real worldM∗ if most MDPs in the randomized set differ much withM∗. In other words, U must be ”smooth” nearM∗ for domain randomization to return a nontrivial policy. By ”smoothness”, we mean that there is a positive probability that the uniform distribution ν returns a MDP that is close to M∗. This is because the probability that ν samples exactly M∗ in a infinite simulator class is 0, so domain randomization cannot work at all if such smoothness does not hold.
Formally, we assume there is a distance measure d(M1,M2) on U between two MDPs M1 and M2. Define the -neighborhood CM∗, of M∗ as CM∗, def = {M ∈ U : d(M,M∗) ≤ }. The smoothness condition is formally stated as follows:
Assumption 3 (Smoothness nearM∗). There exists a positive real number 0, and a Lipchitz constant L, such that for the policy π∗DR, the value function of any two MDPs in CM∗, 0 is L-Lipchitz w.r.t the distance function d, i.e.∣∣∣V π∗DRM1,1(s1)− V π∗DRM2,1(s1)∣∣∣ ≤ L · d(M1,M2),∀M1,M2 ∈ CM∗, 0 . (6) For example, we can set d(M1,M2) = I[M1 6=M2] in the finite simulator class. For complicated simulator class, we need to ensure there exists some d(·, ·) that L is not large. With Assumption 3, it is possible to compute the sim-to-real gap of π∗DR. In the finite simulator class, we have shown that the gap depends on M polynomially, which can be viewed as the complexity of U . The question is, how do we measure the complexity of U when it is infinitely large? Motivated by Ayoub et al. (2020), we consider the function class
F = {fM(s, a, λ) : S ×A× Λ→ R such that fM(s, a, λ) = PMλ(s, a) forM∈ U , λ ∈ Λ} , (7)
where Λ = {λ∗M,M ∈ U} is the optimal bias functions ofM ∈ U in the infinite-horizon averagereward setting (Bartlett & Tewari (2012); Fruit et al. (2018); Zhang & Ji (2019)). We note this function class is only used for analysis purposes to express our complexity measure; it does not affect the domain randomization algorithm. We use the the -log-covering number and the -eluder dimension of F to characterize the complexity of the simulator class U . In the setting of linear combined models (Ayoub et al., 2020), the -log-covering number and the -eluder dimension are O (d log(1/ )), where d is the dimension of the linear representation in linear combined models. For readers not familiar with eluder dimension or infinite-horizon average-reward MDPs, please see Appendix A for preliminary explanations.
Here comes our bound of sim-to-real gap for the infinite simulator class setting, which is proved in Appendix F.
Theorem 4. Under Assumption 1 and 3, the sim-to-real gap of the domain randomization policy π∗DR is at most for 0 ≤ < 0
Gap(π∗DR) = O
( D √ deH log (H · N (F , 1/H))
ν (CM∗, ) + L
) . (8)
Here ν(CM∗, ) is the probability of ν sampling a MDP in CM∗, , de = dimE(F , 1/H) is the 1/Heluder dimension F , and N (F , 1/H) is the 1/H-covering number of F w.r.t. L∞ norm.
Theorem 4 is a generalization of Theorem 2, since we can reduce Theorem 4 to Theorem 2 by setting d(M1,M2) = I[M1 6=M2] and = 0, in which case ν(CM∗, ) = 1/M and de ≤M . The proof overview can be found in Section 6. The main technique is still a reduction to the regret minimization problem in infinite-horizon average-reward setting. We construct a base policy and shows that the regret of it is only Õ( √ H). A key point to note is that our construction of the base policy also solves an open problem of designing efficient algorithms that achieve Õ( √ T ) regret in the infinite-horizon average-reward setting with general function approximation. This base policy is of independent interests.
To complement our positive results, we also provide a negative result that even if the MDPs in U have nice low-rank properties (e.g., the linear low-rank property (Jin et al., 2020b; Zhou et al., 2020)), the policy π∗DR returned by the domain randomization oracle can still have Ω(H) sim-to-real gap when the simulator class is large and the smoothness condition (Assumption 3) does not hold. This explains the necessity of our preconditions. Please refer to Proposition 2 in Appendix G.3 for details.

heading: 6 PROOF OVERVIEW
text: In this section, we will give a short overview of our novel proof techniques for the results shown in section 5. The main proof technique is based on reducing the problem of bounding the sim-to-real gap to the problem of constructing base policies. In the settings without separation conditions, we further connect the construction of the base policies to the design of efficient learning algorithms for the infinite-horizon average-reward settings.

heading: 6.1 REDUCING TO CONSTRUCTING BASE POLICIES
text: Intuitively, if there exists a base policy π̂ ∈ Π with bounded sim-to-real gap, then the gap of π∗DR will not be too large since π∗DR defined in Eqn 2 is the policy with the maximum average value. Lemma 1. Suppose there exists a policy π̂ ∈ Π such that the sim-to-real gap of π̂ for any MDP M∈ U satisfies V ∗M,1(s1)− V π̂M,1(s1) ≤ C, then we have
Gap(π∗DR) ≤MC, (9)
when U is a finite set with |U| = M . Furthermore, when U is an infinite set satisfying the smoothness condition (assumption 3), we have for any 0 < < 0,
Gap(π∗DR) ≤ C/ν (CM∗, ) + L . (10)
We defer the proof to Appendix B.1. Now with this reduction lemma, the remaining problem is defined as follows: Suppose the real MDP M∗ belongs to the MDP set U . We know the full information (transition matrix) of any MDP in the MDP set U . How to design a history-dependent policy π̂ ∈ Π with minimum sim-to-real gap maxM∈U ( V ∗M,1(s1)− V π̂M,1(s1) ) .

heading: 6.2 THE CONSTRUCTION OF THE BASE POLICIES
text: With separation conditions With the help of Lemma 1, we can bound the sim-to-real gap in the setting of finite simulator class with separation condition by constructing a history-dependent policy π̂. The formal definition of the policy π̂ can be found in Appendix C.1. The idea of the construction is based on elimination: the policy π̂ explicitly collects samples on the “informative” state-action
pairs and eliminates the MDP that is less likely to be the real MDP from the candidate set. Once the agent identifies the real MDP representing the dynamics of the physical environment, it follows the optimal policy of the real MDP until the end of the interactions.
Without separation conditions The main challenge in this setting is that, we can no longer construct a policy π̂ that “identify” the real MDP using the approaches as in the settings with separation conditions. In fact, we may not be able to even “identify” the real MDP since there can be MDPs in U that is very close to real MDP. Here, we use a different approach, which reduces the minimization of sim-to-real gap of π̂ to the regret minimization problem in the infinite-horizon average-reward MDPs.
The infinite-horizon average-reward setting has been well-studied (e.g., Jaksch et al., 2010; Agrawal & Jia, 2017; Fruit et al., 2018; Wei et al., 2020). The main difference compared with the episodic setting is that the agent interacts with the environment for infinite steps. The gain of a policy is defined in the average manner. The value of a policy π is defined as ρπ(s) = E[limT→∞ ∑T t=1R(st, π (st))/T | s1 = s]. The optimal gain is defined as ρ∗(s) def = maxs∈S maxπ ρ
π(s), which is shown to be state-independent in Agrawal & Jia (2017), so we use ρ∗ for short. The regret in the infinite-horizon setting is defined as Reg(T ) = E [ Tρ∗ − ∑T t=1R(st, at) ] , where the expectation is over the randomness of the trajectories. A more detailed explanation of infinite-horizon average-reward MDPs can be found in Appendix A.1.
For an MDPM ∈ U , we can view it as a finite-horizon MDP with horizon H; or we can view it as an infinite-horizon MDP. This is because Assumption 1 ensures that the agent can travel to any state from any state sH encountered at the H-th step (this may not be the case in the standard finitehorizon MDPs, since people often assume that the states at theH-th level are terminating state). The following lemma shows the connection between these two views.
Lemma 2. For a MDP M, let ρ∗M and V ∗M,1(s1) to be the optimal expected gain in the infinitehorizon view and the optimal value function in the episodic view respectively. We have the following inequality: Hρ∗M −D ≤ V ∗M,1(s1) ≤ Hρ∗M +D.
This lemma indicates that, if we can design an algorithm (i.e. the base policy) π̂ in the infinitehorizon setting with regret Reg(H), then the sim-to-real gap of this algorithm in episodic setting satisfies Gap(π̂) = V ∗M,1(s1) − V π̂M,1(s1) ≤ Reg(H) + D. This lemma connects the sim-to-real gap of π̂ in finite-horizon setting to the regret in the infinite-horizon setting.
With the help of Lemma 1 and 2, the remaining problem is to design an efficient exploration algorithm for infinite-horizon average-reward MDPs with the knowledge that the real MDPM∗ belongs to a known MDP set U . Therefore, we propose two optimistic-exploration algorithms (Algorithm 3 and Algorithm 4) for the setting of finite simulator class and infinite simulator class respectively. The formal definition of the algorithms are deferred to Appendix C.2 and Appendix C.3. Note that our Algorithm 4 is the first efficient algorithm with Õ( √ T ) regret in the infinite-horizon averagereward MDPs with general function approximation, which is of independent interest for efficient online exploration in reinforcement learning.

heading: 7 CONCLUSION
text: In this paper, we study the optimality of policies learned from domain randomization in sim-to-real transfer without real-world samples. We propose a novel formulation of sim-to-real transfer and view domain randomization as an oracle that returns the optimal policy of an LMDP with uniform initialization distribution. Following this idea, we show that the policy π∗DR can suffer only o(H) loss compared with the optimal value function of the real environment when the simulator class is finite or satisfies certain smoothness condition, thus this policy can perform well in the long-horizon cases. We hope our formulation and analysis can provide insight to design more efficient algorithms for sim-to-real transfer in the future.

heading: A ADDITIONAL PRELIMINARIES
text: A.1 INFINITE-HORIZON AVERAGE-REWARD MDPS
The infinite-horizon average-reward setting has been well-explored in the recent few years (e.g. Jaksch et al. (2010); Agrawal & Jia (2017); Fruit et al. (2018); Wei et al. (2020)). The main difference compared with the episodic setting is that the agent interacts with the environment for infinite steps instead of restarting every H steps. The gain of a policy is defined in the average manner. Definition 2. (Definition 4 in Agrawal & Jia (2017)) The gain ρπ(s) of a stationary policy π from starting state s1 = s is defined as:
ρπ(s) = E [ lim T→∞ 1 T T∑ t=1 R(st, π (st)) | s1 = s ] (11)
In this setting, a common assumption is that the MDP is communicating (Assumption 1). Under this assumption, we have the following lemma. Lemma 3. (Agrawal & Jia, 2017, Lemma 2.1) For a communicating MDPM with diameterD: (a) The optimal gain ρ∗ is state-independent and is achieved by a deterministic stationary policy π∗DR; that is, there exists a deterministic policy π∗ such that
ρ∗ := max s′∈S max π ρπ (s′) = ρπ ∗ (s),∀s ∈ S (12)
(b) The optimal gain ρ∗ satisfies the following equation:
ρ∗ = min λ∈RS max s,a [R(s, a) + Pλ(s, a)− λ(s)] = max a [R(s, a) + Pλ∗(s, a)− λ∗(s)] ,∀s (13)
where Pλ(s, a) = ∑ s′ P (s ′|s, a)λ(s′), and λ∗ is the bias vector of the optimal policy π∗DR satisfying
0 ≤ λ∗(s) ≤ D. (14)
The regret minimization problem has been widely studied in this setting, with regret to be defined as Reg(T ) = E [ Tρ∗ − ∑T t=1R(st, at) ] , where the expectation is over the randomness of the trajectories. For example, Jaksch et al. (2010) proposed an efficient algorithm called UCRL2, which achieves regret upper bound Õ(DS √ AT ). For notation convenience, we use PV (s, a) or Pλ(s, a)
as a shorthand of ∑ s′∈S P (s ′|s, a)V (s′) or ∑ s′∈S P (s ′|s, a)λ(s′).

heading: A.2 ELUDER DIMENSION
text: Proposed by Russo & Van Roy (2013), eluder dimension has become a widely-used concept to characterize the complexity of different function classes in bandits and RL (Wang et al., 2020; Ayoub et al., 2020; Jin et al., 2021; Kong et al., 2021). In this work, we define eluder dimension to characterize the complexity of the function F :
F = {fM(s, a, λ) : S ×A× Λ→ R such that fM(s, a, λ) = PMλ(s, a) forM∈ U , λ ∈ Λ} , (15)
where Λ = {λ∗M,M ∈ U} is the optimal bias functions ofM ∈ U in the infinite-horizon averagereward setting (Bartlett & Tewari (2012); Fruit et al. (2018); Zhang & Ji (2019)).
Definition 3. (Eluder dimension). Let ≥ 0 and Z = {(si, ai, λi)}ni=1 ⊂ S×A×Λ be a sequence of history samples.
• A history sample (s, a, λ) ∈ S × A × Λ is -dependent on Z with respect to F if any f, f ′ ∈ F satisfying ‖f−f ′‖Z ≤ also satisfies ‖f(s, a)−f ′(s, a)‖ ≤ . Here ‖f−f ′‖Z is a shorthand of √∑ (s,a,λ)∈Z(f − f ′)2(s, a, λ).
• An (s, a, λ) is -independent of Z with respect to F if (s, a, λ) is not -dependent on Z .
• The -eluder dimension of a function class F is the length of the longest sequence of elements in S × A × Λ such that, for some ′ ≥ , every element is ′-independent of its predecessors.

heading: B OMITTED PROOF IN SECTION 6

heading: B.1 PROOF OF LEMMA 1
text: Proof. We firstly study the case where U is a finite set with |U| = M . For π̂, we have 1
M ∑ M∈U ( V ∗M,1(s1)− V π̂M,1(s1) ) ≤ C. (16)
By the optimality of π∗DR, we know that
1
M ∑ M∈U V π∗DR M,1 (s1) ≥ 1 M ∑ M∈U V π̂M,1 (s1) . (17)
Therefore, 1
M ∑ M∈U ( V ∗M,1(s1)− V π∗DR M,1(s1) ) ≤ C. (18)
Since the gap V ∗M,1(s1)−V π∗DR M,1(s1) ≥ 0 for any i ∈ [M ], we have 1 M ( V ∗M∗,1(s1)− V π∗DR M∗,1(s1) ) ≤ C. That is, ( V ∗M∗,1(s1)− V π∗DR M∗,1(s1) ) ≤MC. (19)
For the case where U is an infinite set satisfying Assumption 3, by the optimality of π∗DR, we have EM∼ν [ V π∗DR M,1(s1) ] ≥ EM∼ν [ V π̂M,1(s1) ] . (20)
Therefore, EM∼ν(CM∗, ) [ V ∗M∗,1(s1)− V π∗DR M,1(s1) ] ≤ EM∼ν [ V ∗M∗,1(s1)− V π∗DR M,1(s1) ] ≤ EM∼ν [ V ∗M∗,1(s1)− V π̂M,1(s1) ] .
(21)
By Assumption 3, for anyM∈ C(M∗, ), we have∣∣∣V π∗DRM∗,1(s1)− V π∗DRM,1(s1)∣∣∣ ≤ L . (22) Therefore, we have
ν (CM∗, ) ( V ∗M∗,1(s1)− V π∗DR M∗,1(s1)− L ) ≤ EM∼ν(CM∗, ) [ V ∗M∗,1(s1)− V π∗DR M,1(s1) ] (23)
Combining Inq 21 and Inq 23, we have ν (CM∗, ) ( V ∗M∗,1(s1)− V π∗DR M∗,1(s1)− L ) ≤ C, (24)
The lemma can be proved by reordering the above inequality.

heading: B.2 PROOF OF LEMMA 2
text: Proof. For MDPM, denote π∗in as the optimal policy in the infinite-horizon setting and {π∗ep,h}Hh=1 as the optimal policy in the episodic setting. By the optimality of π∗ep, we have V ∗ M,1(s1) = V π∗ep M,1(s1) ≥ V π∗in M,1(s1).
By the Bellman equation in the infinite-horizon setting, we know that
λ∗M(s) + ρ ∗ M = R(s, π ∗ in(s)) + PMλ ∗ M(s, π ∗ in(s)),∀s ∈ S (25)
For notation simplicity, we use dh(s1, π) to denote the state distribution at step h after starting from state s1 at step 1 following policy π. From the above equation, we have
λ∗M(s1) +Hρ ∗ M = H∑ h=1 Esh∼dh(s1,π∗in)R(sh, , π ∗ in(sh)) + EsH+1∼dH+1(s1,π∗in))λ ∗ M(sH+1). (26)
That is, | H∑ h=1 Esh∼dh(s1,π∗in)R(sh, , π ∗ in(sh))−Hρ∗M| = |λ∗M(s1)− EsH+1∼dH+1(s1,π∗in)λ ∗ M(sH+1)| ≤ D,
(27)
where ∑H h=1 Esh∼dh(s1,π∗in)R(sh, , π ∗ in(sh)) = V π∗in M,1(s1). Therefore, we have Hρ ∗ M − D ≤ V π∗in M,1(s1) ≤ V ∗M,1(s1).
For the second inequality, by the Bellman equation in the infinite-horizon setting, we have
λ∗M(s1) +Hρ ∗ M ≥ H∑ h=1 Esh∼dh(s1,π∗ep)R(sh, , π ∗ ep,h(sh)) + EsH+1∼dH+1(s1,π∗ep)λ ∗ M(sH+1).
(28)
That is, H∑ h=1 Esh∼dh(s1,π∗ep)R(sh, , π ∗ ep,h(sh))−Hρ∗M ≤ λ∗M(s1)− EsH+1∼dH+1(s1,π∗ep)λ ∗ M(sH+1) ≤ D,
(29) where ∑H h=1 Esh∼dh(s1,π∗ep)R(sh, , π ∗ ep,h(sh)) = V ∗ M,1(s1).

heading: C THE CONSTRUCTION OF LEARNING ALGORITHMS

heading: C.1 FINITE SIMULATOR CLASS WITH SEPARATION CONDITION
text: In this subsection, we explicitly define the base policy π̂ with sim-to-real gap guarantee under the separation condition. Note that a history-dependent policy for LMDPs can also be regarded as an algorithm for finite-horizon MDPs. By deriving an upper bound of the sim-to-real gap for π̂, we can upper bound Gap(π∗DR,U) with Lemma 1. The policy π̂ is formally defined in Algorithm 1. There are two stages in Algorithm 1. In the first stage, the agent’s goal is to quickly explore the environment and find the real MDPM∗ from the MDP set U . This stage contains at most M − 1 parts. In each part, the agent randomly selects two MDPsM1 andM2 from the remaining MDP set D. Since the agent knows the transition dynamics of M1 and M2, it can find the most informative state-action pair (s0, a0) with maximum totalvariation difference between PM1(·|s0, a0) and PM2(·|s0, a0). The algorithm calls Subroutine 2 to collect enough samples from (s0, a0) pairs, and then eliminates the MDP with less likelihood. At the end of the first stage, the MDP set D is ensured to contain only one MDP M∗ with high probability. Therefore, the agent can directly execute the optimal policy for the real MDP till step H + 1 in the second stage.
Algorithm 1 Optimistic Exploration Under Separation Condition
1: Initialize: the MDP set D = U , n0 = c0 log 2(SMH) log(MH)
δ4 for a constant c0 2: . Stage 1: Explore and find the real MDPM∗ 3: while |D| ≥ 1 do 4: Randomly select two MDPsM1 andM2 from the MDP set D 5: Choose (s0, a0) = arg max(s,a)∈S×A ‖(PM1 − PM2) (· | s, a)‖1 6: Call Subroutine 2 with parameter (s0, a0) and n0 to collect history samplesHM1,M2 7: if ∃s′ ∈ HM1,M2 , PM2(s′|s0, a0) = 0 or ∏ s′∈HM1,M2 PM1 (s ′|s0,a0) PM2 (s ′|s0,a0) ≥ 1 then 8: EliminateM2 from the MDP set D 9: else
10: EliminateM1 from the MDP set D 11: end if 12: end while 13: . Stage 2: Run the optimal policy ofM∗ 14: Denote M̂ as the remaining MDP in the MDP set D 15: Run the optimal policy of M̂ for the remaining steps
Algorithm 2 Subroutine: collecting data for (s0, a0) Input: informative state-action pair (s0, a0), required visitation count n0 Initialize: counter N(s0, a0) = 0, history dataH = ∅ Denote πM(s, s′) as the policy with the minimum expected travelling time E [T (s′ | M, π, s)] for MDPM (Defined in Assumption 1) while N(s0, a0) ≤ n0 do
5: for i = 1, · · · ,M do Denote the current state as sinit Run the policy πMi(sinit, s0) for 2D steps, breaking the loop immediately once the
agent enters state s0 end for if the agent enters state s0 then
10: Execute a0, enter the next state s′. counter N(s0, a0) = N(s0, a0) + 1,H = H ⋃ {s′}
end if end while Output: history dataH
Subroutine 2 is designed to collect enough samples from the given state-action pair (s0, a0). The basic idea in Subroutine 2 is to quickly enter the state s0 and take action a0, until the visitation counter N(s0, a0) = n0. Denote πM(s, s′) as the policy with the minimum expected travelling time E [T (s′ | M, π, s)] for MDP M. Suppose the agent is currently at state sinit and runs the policy πM∗(sinit, s0) in the following steps. By Assumption 1 and Markov’s inequality, the agent will enter state s0 in 2D steps with probability at least 1/2. Therefore, in Subroutine 2, we runs the policy πMi(sinit, s0) for 2D steps for i ∈ [M ] alternatively. This ensures that the agent can enter state s0 in 2MD steps with probability at least 1/2.
Theorem 5 states an upper bound of the sim-to-real gap for Algorithm 1, which is proved in Appendix D.1. Theorem 5. Suppose we use π̂ to denote the history-dependent policy represented by Algorithm 1. Under Assumption 1 and Assumption 2, for anyM ∈ U , the sim-to-real gap of Algorithm 1 is at most
V ∗M,1(s1)− V π̂M,1(s1) ≤ O ( DM2 log(MH) log2(SMH/δ)
δ4
) . (30)

heading: C.2 FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION
text: In this subsection, we propose an efficient algorithm in the infinite-horizon average-reward setting for finite simulator class. Our algorithm is described in Algorithm 3. In episode k, the agent executes the optimal policy of the optimistic MDP Mk with the maximum expected gain ρ∗Mk . Once the agent collects enough data and realizes that the current MDP Mk is not M∗ that represents the dynamics of the real environment, the agent eliminatesMk from the MDP set.
Algorithm 3 Optimistic Exploration 1: Initialize: the MDP set U1 = U , the episode counter k = 1, h0 = 1 2: CalculateM1 = arg maxM∈U1 ρ ∗ M
3: for step h = 1, · · · , H do 4: Take action ah = π∗Mk(sh), obtain the reward R(sh, ah), and observe the next state sh+1 5: if ∣∣∣∑ht=h0 (PMkλ∗Mk (st, at)− λ∗Mk (st+1))∣∣∣ > D√2(h− h0) log(2HM) then 6: EliminateMk from the MDP set Uk, denote the remaining set as Uk+1 7: CalculateMk+1 = arg maxM∈Uk+1 ρ ∗ M 8: Set h0 = h+ 1, and k = k + 1. 9: end if
10: end for
To indicate the basic idea of the elimination condition defined in Line 5 of Algorithm 3, we briefly explain our regret analysis of Algorithm 3. Suppose the MDPMk selected in episode k satisfies the optimistic condition ρ∗Mk ≥ ρ ∗ M∗ , then the regret in H steps can be bounded as:
Hρ∗M∗ − H∑ h=1 R(sh, ah) (31)
≤ K∑ k=1 τ(k+1)−1∑ h=τ(k) (ρ∗Mk −R(sh, ah)) (32)
= K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMkλ ∗ Mk(sh, ah)− λ ∗ Mk(sh)) (33)
= K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMkλ ∗ Mk(sh, ah)− λ ∗ Mk(sh+1)) + K∑ k=1 ( λ∗Mk(sτ(k+1))− λ ∗ Mk(sτ(k)) ) (34) ≤ K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMkλ ∗ Mk(sh, ah)− λ ∗ Mk(sh+1)) +KD. (35)
Here we use K to denote the total number of episodes, and we use τ(k) to denote the first step of episode k. The first inequality is due to the optimistic condition ρ∗Mk ≥ ρ ∗ M∗ . The first equality is due to the Bellman equation in the finite-horizon setting (Eqn 13). The last inequality is due to 0 ≤ λ∗M(s) ≤ D. From the above inequality, we know that the regret in episode k depends on the summation ∑τ(k+1)−1 h=τ(k) ( PMkλ ∗ Mk(sh, ah)− λ ∗ Mk(sh+1) ) . If this term is relatively small, we can continue following the policy π∗Mk with little loss. Since λ ∗ Mk(sh+1) is an empirical sample of PM∗λ∗Mk(sh, ah), we can guarantee that M k is not M∗ with high probability if this term is relatively large.
Based on the above discussion, we can upper bound the regret of Algorithm 3. We defer the proof of Theorem 6 to Appendix E.1.
Theorem 6. Under Assumption 1, the regret of Algorithm 3 is upper bounded by Reg(H) ≤ O ( D √ MH log(MH) ) . (36)
C.3 INFINITE SIMULATOR CLASS
In this subsection, we propose a provably efficient model-based algorithm solving infinite-horizon average-reward MDPs with general function approximation. To the best of our knowledge, our result is the first efficient algorithm with near-optimal regret for infinite-horizon average-reward MDPs with general function approximation.
Considering the model class U which covers the true MDPM∗, i.e.M∗ ∈ U , we define the function space Λ = {λ∗M,M∈ U}, and space X = S ×A× Λ. We define the function space
F = {fM(s, a, λ) : X → R such that fM(s, a, λ) = PMλ(s, a) forM∈ U , λ ∈ Λ} . (37)
Our algorithm, which is described in Algorithm 4, also follows the well-known principle of optimism in the face of uncertainty. In each episode k, we calculate the optimistic MDPMk with maximum expected gain ρ∗Mk . We execute the optimal policy of M
∗ to interact with the environment and collect more samples. Once we have collected enough samples in episode k, we update the model class Uk and compute the optimistic MDP for episode k + 1. Compared with the setting of episodic MDP with general function approximation (Ayoub et al., 2020; Wang et al., 2020; Jin et al., 2021), the additional problem in the infinite-horizon setting is that the regret technically has linear dependence on the number of total episodes, or the number of steps that we update the optimistic model and the policy. This corresponds to the last term (KD) in Inq 35. Therefore, to design efficient algorithm with near-optimal regret in the infinite-horizon setting, the algorithm should maintain low-switching property (Bai et al., 2019; Kong et al., 2021). Taking inspiration from the recent work that studies efficient exploration with low switching cost in episodic setting (Kong et al., 2021), we define the importance score, supf1,f2∈F ‖f1−f2‖2Znew ‖f1−f2‖2Z+α
, as a measure of the importance for new samples collected in current episode, and only update the optimistic model and the policy when the importance score is greater than 1. Here ‖f1 − f2‖2Z is a shorthand of ∑ (s,a,s′,λ)∈Z (f1(s, a, λ)− f2(s, a, λ)) 2.
We state the regret upper bound of Algorithm 4 in Theorem 5, and defer the proof of the theorem to Appendix F.1.
Theorem 7. Under Assumption 1, the regret of Algorithm 4 is uppder bounded by Reg(H) ≤ O ( D √ deH log (H · N (F , 1/H)) ) , (38)
where de is the -eluder dimension of function class F with = 1H , and N (F , 1/H) is the 1 H - covering number of F w.r.t L∞ norm.
For α > 0, we say the covering number N (F , α) of F w.r.t the L∞ norm equals m if there is m functions in F such that any function in F is at most α away from one of these m functions in norm ‖ · ‖∞. The ‖ · ‖∞ norm of function f is defined as ‖f‖∞ def = maxx∈X |f(x)|.
Algorithm 4 General Optimistic Algorithm 1: Initialize: the MDP set U1 = U , episode counter k = 1 2: Initialize: the history data set Z = ∅, Znew = ∅ 3: α = 4D2 + 1, β = cD2 log (H · N (F , 1/H)) for a constant c. 4: ComputeM1 = arg maxM∈U1 ρ ? M
5: for step h = 1, · · · , H do 6: Take action ah = π∗Mk(sh) in the current state sh, and transit to state sh+1 7: Add (sh, ah, sh+1, λ∗Mk) to the set Znew 8: if importance score supf1,f2∈F ‖f1−f2‖2Znew ‖f1−f2‖2Z+α
≥ 1 then 9: Add the history data Znew to the set Z
10: Calculate M̂k+1 = arg minM∈U ∑ (sh,ah,sh+1,λh)∈Z (PMλh(sh, ah)− λh(sh+1)) 2
11: Update Uk+1 = { M∈ U : ∑ (sh,ah,sh+1,λh)∈Z (( PM − PM̂k+1 ) λh(sh, ah) )2 ≤ β } 12: ComputeMk+1 = arg maxM∈Uk+1 ρ ? M 13: Episode counter k = k + 1 14: end if 15: end for

heading: D OMITTED PROOF FOR FINITE SIMULATOR CLASS WITH SEPARATION CONDITION

heading: D.1 PROOF OF THEOREM 5
text: The formal definition of π̂ is given in Algorithm 1. To upper bound the sim-to-real gap of π̂, we discuss on the following two benign properties of Algorithm 1 in Lemma 4 and Lemma 7. Lemma 4 states that the true MDPM∗ will never be eliminated from the MDP set D. Therefore, in stage 2, the agent will execute the optimal policy in the remaining steps with high probability. Lemma 7 states that the total number of steps in stage 1 is upper bounded by Õ(M 2
δ4 ). This is where the final bound in Theorem 5 comes from. Lemma 4. With probability at least 1 − 1H , the true MDPM
∗ will never be eliminated from the

heading: MDP set D in stage 1.
text: The while-loop in stage 1 will last for M − 1 times. To prove Lemma 4, we need to prove that, if the true MDPM∗ is selected in a certain loop, then ∏ (s,a,s′)∈HM1,M2 PM∗ (s ′|s,a)
PM(s′|s,a) ≥ 1 holds with high probability. This is illustrated in the following lemma.
Lemma 5. Suppose H = {s′i} n0 i=1 is a set of n0 =
c0 log 2(SMH/δ) log(MH)
δ4 independent samples from a given state-action pair (s0, a0) and MDP M∗ for a large constant c0. Let M1 denote another MDP satisfying ‖(PM∗ − PM1)(·|s0, a0)‖1 ≥ δ, then the following inequality holds with probability at least 1− 1MH : ∏
s′∈H
PM∗(s ′|s0, a0) PM1(s ′|s0, a0) > 1, (39)
Proof. The proof of Lemma 5 is inspired by the analysis in Kwon et al. (2021). To prove Inq 39, it is enough to show that
ln (∏ s′∈H PM∗(s ′|s0, a0) PM1(s ′|s0, a0) ) = ∑ s′∈H ln ( PM∗(s ′|s0, a0) PM1(s ′|s0, a0) ) > 0. (40)
holds with probability at least 1− 1MH .
Note that PM∗ (s ′|s0,a0)
PM1 (s ′|s0,a0) can be unbounded since PM1(s ′|s0, a0) can be zero for certain s′. To tackle this issue, we define P̃M1 for a sufficiently small α ≤ δ4S :
P̃M1(s ′|s, a) = α+ (1− αS)PM1(s′|s, a). (41)
We have ∥∥∥(P̃M1 − PM1) (·|s, a)∥∥∥ ≤ 2Sα ≤ δ2 , thus ∥∥∥(P̃M1 − PM∗) (·|s, a)∥∥∥ ≥ δ2 . Also, we
have ln (
1 P̃M1 (s ′|s0,a0)
) ≤ ln(1/α) for any s′ ∈ S. With the above definition, we can decompose
Inq 40 into two terms:∑ s′∈H ln ( PM∗(s ′|s0, a0) PM1(s ′|s0, a0) ) = ∑ s′∈H ln ( PM∗(s ′|s0, a0) P̃M1(s ′|s0, a0) ) + ∑ s′∈H ln ( P̃M1(s ′|s0, a0) PM1(s ′|s0, a0) ) . (42)
Taking expectation over s′ ∼ PM∗(·|s, a) for the first term, we have
E [ n0∑ i=1 ln ( PM∗(s ′ i|s0, a0) P̃M1(s ′ i|s0, a0) )] = n0∑ i=1 ∑ s′ PM∗(s ′|s0, a0) ln ( PM∗(s ′|s0, a0) P̃M1(s ′|s0, a0) ) (43)
=n0DKL ( PM∗(s ′|s0, a0)|P̃M1(s′|s0, a0) )
(44)
≥n0δ 2
2 , (45)
where the last inequality is due to Pinsker’s inequality.
Lemma 6. (Lemma C.2 in Kwon et al. (2021)) Suppose X is an arbitrary discrete random variable on a finite support X . Then, ln(1/P (X)) is a sub-exponential random variable (Vershynin, 2010) with Orcliz norm ln(1/P (X))φ1 = 1/e.
From the above Lemma, we know that both P̃M1(s ′|s0, a0) and PM∗(s′|s0, a0) are sub-exponential random variables. By Azuma-Hoeffing’s inequality, we have with probability at least 1− δ0/2,∑ s′∈H ln ( 1 P̃M1(s ′|s0, a0) ) ≥ E [ n0∑ i=1 ln ( 1 P̃M1(s ′ i|s0, a0) )] − log(1/α) √ 2n0 log(2/δ0). (46)
By Proposition 5.16 in Vershynin (2010), with probability at least 1− δ0/2,∑ s′∈H ln (PM∗(s ′|s0, a0)) ≥ E [ n0∑ i=1 ln (PM∗(s ′ i|s0, a0)) ] − √ n0 log(2/δ0)/c, (47)
for a certain constant c > 0. Therefore, we can lower bound the first term in Eqn 42,∑ s′∈H ln ( PM∗(s ′|s0, a0) P̃M1(s ′|s0, a0) ) ≥ n0δ 2 2 − log(1/α) √ 2n0 log(2/δ0)− √ n0 log(2/δ0)/c, (48)
with probability at least 1− δ0.
For the second term in Eqn 42, by the definition of P̃M1 ,∑ s′∈H ln ( P̃M1(s ′|s0, a0) PM1(s ′|s0, a0) ) ≥ −2αSn0 (49)
Combining Inq 48 and Inq 49, we have∑ s′∈H ln ( PM∗(s ′|s0, a0) PM1(s ′|s0, a0) ) ≥ n0δ 2 2 − log(1/α) √ 2n0 log(2/δ0)− √ n0 log(2/δ0)/c− 2αSn0
(50)
Setting α = δ 2
8S , δ0 = 1 MH , and n0 = c0 log 2(SMH/δ) log(MH) δ4 , we have∑
s′∈H ln
( PM∗(s
′|s0, a0) PM1(s ′|s0, a0)
) > 0 (51)
holds with probability at least 1− 1MH .
Lemma 7. Suppose Stage 1 in Algorithm 1 ends in h0 steps. We have E[h0] ≤ O(DM
2 log2(SMH/δ) log(MH) δ4 ), where the expectation is over all randomness in the algorithm and
the environment.
Proof. Recall that πM(s, s′) is the policy with the minimum expected travelling time E [T (s′ | M, π, s)] for MDPM. By Assumption 1, we have
E [T (s′ | M∗, πM(s, s′), s)] ≤ D. (52) Given state s and s′, by Markov’s inequality, we know that with probability at least 12 , T (s′ | M∗, πM∗(s, s′), s) ≤ 2D. (53) Consider the following stochastic process: In each episode k, the agent starts from a state sk that is arbitrarily selected, and run the policy πM∗(sk, s0) for 2D steps on the MDPM∗. The process terminates once the agent enters a certain state s0. By Inq 53, the probability that the process terminates within k episodes is at least 1 − 1
2k . By the basic algebraic calculation, the expected
stopping episode can be bounded by a constant 4.
Now we return to the proof of Lemma 7. In Subroutine 2, we run policy πMi for each MDP Mi ∈ D alternately. By Lemma 4, the true MDP M∗ is always contained in the MDP set D. Therefore, the expected travelling time to enter state s0 for n0 times is bounded by n0 ·M · 8D. In stage 1, we call Subroutine 2 for M − 1 times, which means that the expected steps in stage 1 satisfies E[h0] ≤ 8M2n0d = O(DM 2 log2(SMH/δ) log(MH) δ4 ).
Proof. (Proof of Theorem 5) Recall that we use h0 to denote the total steps in stage 1. Firstly, we prove that Gap(π̂,U) is upper bounded by O (E[h0] +D). V ∗M∗,1(s1)− V π̂M∗,1(s1) (54)
=Eh0 [ EM∗,π∗M∗ [ h0∑ h=1 R(sh, ah) | h0 ] + EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ]] (55)
− Eh0 [ EM∗,π̂ [ h0∑ h=1 R(sh, ah) | h0 ] + EM∗,π̂ [ V π̂M∗,h0+1(sh0+1) | h0 ]] (56)
≤Eh0 [ EM∗,π∗M∗ [ h0∑ h=1 R(sh, ah) | h0 ]] + Eh0 [ EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] − EM∗,π̂ [ V π̂M∗,h0+1(sh0+1) | h0 ]] (57)
≤E[h0] + Eh0 [ EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] − EM∗,π̂ [ V π̂M∗,h0+1(sh0+1) | h0 ]] (58)
The outer expectation is over all possible h0, while the inner expectation is over the possible trajectories given fixed h0. By Lemma 4, we know that π̂ = π∗DR after h0 steps with probability at least 1− 1H . If this high-probability event happens, the second part in the above inequality equals to
E [ EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] − EM∗,π̂ [ V ∗M∗,h0+1(sh0+1) | h0 ]] .
We can prove that this term is upper bounded by 2D. Given fixed h0, EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] − EM∗,π̂ [ V ∗M∗,h0+1(sh0+1) | h0 ] is the difference of the value function in step h0 + 1 under two different distribution of sh0+1. We use dh(s, π) to denote the state distribution in step h after starting from state s in step h0 + 1 following policy π.
V ∗M∗,h0+1(sh0+1) = H∑ h=h0+1 Esh∼dh(sh0+1,π∗M∗ )R(sh, π ∗ DR(sh)) (59)
= ∑
h=h0+1
( ρ∗M∗ + Esh∼dh(sh0+1,π∗M∗ )λ ∗ M∗(sh)− Esh+1∼dh+1(sh0+1,π∗M∗ )λ ∗ M∗(sh+1) ) (60)
=(H − h0)ρ∗M∗ + λ∗M∗(sh0+1)− EsH+1∼dH+1(sh0+1,π∗M∗ )λ ∗ M∗(sH+1), (61)
where the second equality is due to the Bellman equation in infinite-horizon setting (Eqn 13). Note that by the communicating property, we have 0 ≤ λ∗M∗(s) ≤ D for any s ∈ S. Therefore, we have
EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] − EM∗,π̂ [ V ∗M∗,h0+1(sh0+1) | h0 ] ≤ 2D. (62)
If the high-probability event defined in Lemma 4 does not hold (This happens with probability at most 1H ), we still have EM∗,π∗M∗ [ V ∗M∗,h0+1(sh0+1) | h0 ] −EM∗,π̂ [ V π̂M∗,h0+1(sh0+1) | h0 ] ≤ H , thus this does not influence the final bound. Taking expectation over all possible h0, and plugging the result back to Inq 54, we have
V ∗M∗,1(s1)− V π̂M∗,1(s1) ≤ O (E[h0] +D) = O ( DM2 log2(SMH/δ) log(MH)
δ4
) . (63)

heading: D.2 PROOF OF THEOREM 1
text: Proof. The theorem can be proved by combining Theorem 5 and Lemma 1.
By Theorem 5, we prove that the constructed policy π̂ satisfies
V ∗M∗,1(s1)− V π̂M∗,1(s1) ≤ O ( DM2 log2(SMH) log(MH)
δ4
) . (64)
By Lemma 1, the sim-to-real gap of policy π∗DR is bounded by
Gap(π∗DR,U) ≤ O ( DM3 log2(SMH) log(MH)
δ4
) . (65)

heading: E OMITTED PROOF FOR FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION

heading: E.1 PROOF OF THEOREM 6
text: Lemma 8. (Optimism) With probability at least 1− 1MH , we have ρ ∗ Mk ≥ ρ ∗ M∗ for any k ∈ [K].
Proof. For any fixedM ∈ U , and fixed step h ∈ [H], by Azuma’s inequality, we have with probability at least 1− 1M2H2 ,∣∣∣∣∣ h∑ t=h0 (λ∗M (st+1)− PM∗λ∗M (st, at))
∣∣∣∣∣ ≤ D√2(h− h0) log(2HM). (66) Taking union bounds over all possibleM and h, we know that the above event holds for all possible M and h with probability 1 − 1MH . Under the above event, the true MDP M
∗ will never be eliminated from the MDP set Uk. Therefore, we have ρ∗Mk ≥ ρ ∗ M∗ .
Proof. (Proof of Theorem 6) By Lemma 8, we know that ρ∗Mk ≥ ρ ∗ M∗ for any k ∈ [K]. We use τ(h) to denote the episode that step h belongs to. We can upper bound the regret in H steps as
follows:
Hρ∗M∗ − H∑ h=1 R(sh, ah) (67)
≤ H∑ h=1 ( ρ∗Mτ(h) −R(sh, ah) ) (68)
= H∑ h=1 ( PMτ(h)λ ∗ Mτ(h)(sh, ah)− λ ∗ Mτ(h)(sh) ) (69)
= H∑ h=1 (PMτ(h) − PM∗)λ∗Mτ(h)(sh, ah) + H∑ h=1 ( PM∗λ ∗ Mτ(h)(sh, ah)− λ ∗ Mτ(h)(sh) ) (70)
= H∑ h=1 (PMτ(h) − PM∗)λ∗Mτ(h)(sh, ah) + PM∗λ ∗ Mτ(h)(sh0 , ah0)− λ ∗ Mτ(h)(s1) (71)
+ H−1∑ h=1 ( PM∗λ ∗ Mτ(h)(sh, ah)− λ ∗ Mτ(h)(sh+1) ) (72)
By Azuma’s inequality, we know that
H−1∑ h=1 ( PM∗λ ∗ Mτ(h)(sh, ah)− λ ∗ Mτ(h)(sh+1) ) ≤ D √ H log(2MH), (73)
holds with probability at least 1 − 1MH . Since 0 ≤ λ ∗ M ≤ D, we have PM∗λ∗Mτ(h)(sh0 , ah0) − λ∗Mτ(h)(s1) ≤ D. Therefore, we have
Hρ∗M∗ − H∑ h=1 R(sh, ah) ≤ H∑ h=1 (PMτ(h) − PM∗)λ∗Mτ(h)(sh, ah) +D √ H log(2HM) +D (74)
≤D √ 2MH log(2MH) +M +D √ H log(2HM) +D. (75)
The first term in (74) is bounded by the stopping condition (line 5 of Algorithm 3). By Lemma 2, we have V ∗M∗,1(s1) ≤ Hρ∗M∗ + D. Therefore, we have V ∗M∗,1(s1) − ∑H h=1R(sh, ah) ≤
O ( D √ MH log(MH) ) with probability at least 1− 2MH . Therefore, we have
V ∗M∗,1(s1)− V π∗DR M∗,1(s1) ≤ O ( D √ MH log(MH) +H · 2
MH )
) = O ( D √ MH log(MH) ) .
(76)

heading: E.2 PROOF OF THEOREM 2
text: Theorem 2 can be proved by combining Theorem 6 , Lemma 1 and Lemma 2. By Theorem 6, for anyM∈ U , the policy π̂ represented by Algorithm 3 has regret bound Hρ∗M− ∑H h=1R(sh, ah) ≤
O ( D √ MH log(MH) ) . Taking expectation over {sh, ah}h∈[H] and combining the inequality
with Lemma 2, we have for anyM∈ U . V ∗M,1(s1)− V π̂M,1(s1) ≤ O ( D √ MH log(MH) ) . (77)
Then the theorem can be proved by Lemma 1.

heading: F OMITTED PROOF FOR INFINITE SIMULATOR CLASS

heading: F.1 PROOF OF THEOREM 7
text: Lemma 9. (Low Switching) The total number of episode K is bounded by
K ≤ O(dimE(F , 1/H) log(D2H) log(H)) (78)
Proof. By Lemma 5 of Kong et al. (2021), we know that
H∑ t=1 min
{ sup
f1,f2∈F
(f1(xt)− f2(xt))2
‖f1 − f2‖2Zt + 1 , 1
} ≤ CdimE(F , 1/H) log(D2H) log(H) (79)
for some constant C > 0.
Our idea is to use this result to upper bound the number of total switching steps.
Let τ(k) be the first step of episode k. By the definition of the function class F , we have (f1 − f2)
2(xt) ≤ 4D2 for any f1, f2 ∈ F and xt. By the switching rule, we know that, once the agent starts a new episode after step τ(k + 1)− 1, we have
τ(k+1)−1∑ t=τ(k) (f1 − f2)2(xt) ≤ τ(k)−1∑ t=1 (f1 − f2)2(xt) + α+ 4D2,∀f1, f2, xt (80)
Therefore, we have τ(k+1)−1∑
t=1 (f1 − f2)2(xt) ≤ 2 τ(k)−1∑ t=1 (f1 − f2)2(xt) + α+ 4D2,∀f1, f2, xt (81)
Now we upper bound the importance score in the switching step τ(k + 1)− 1.
min  supf1,f2 ∑τ(k+1)−1 t=τ(k) (f1(xt)− f2(xt)) 2 ‖f1 − f2‖2Zτ(k) + α , 1  ≤min  τ(k+1)−1∑ t=τ(k) sup f1,f2 (f1(xt)− f2(xt))2 ‖f1 − f2‖2Zτ(k) + α , 1  (82)
≤min  τ(k+1)−1∑ t=τ(k) sup f1,f2
2(f1(xt)− f2(xt))2
‖f1 − f2‖2Zτ(k+1) − 4D 2 + α
, 1  (83)
≤min  τ(k+1)−1∑ t=τ(k) sup f1,f2 2(f1(xt)− f2(xt))2 ‖f1 − f2‖2Zt − 4D2 + α , 1  (84) ≤ τ(k+1)−1∑ t=τ(k) min { sup f1,f2 2(f1(xt)− f2(xt))2 ‖f1 − f2‖2Zt − 4D2 + α , 1 } (85)
Suppose the number of episodes is at most K. If we set α = 4D2 + 1, we have
K∑ k=1 min  supf1,f2 ∑τ(k+1)−1 t=τ(k) (f1(xt)− f2(xt)) 2 ‖f1 − f2‖2Zτ(k) + α , 1  ≤ H∑ t=1 min { sup f1,f2 2(f1(xt)− f2(xt))2 ‖f1 − f2‖2Zt − 4D2 + 2α , 1 } (86)
≤CdimE(F , 1/H) log(D2H) log(H) (87)
By the switching rule, we have supf1,f2
∑τ(k+1)−1 t=τ(k) (f1(xt)−f2(xt))2
‖f1−f2‖2Zτ(k)+α ≥ 1. Therefore, the LHS of the
above inequality is exactly K. Thus we have K ≤ CdimE(F , 1/H) log(D2H) log(H). (88)
Lemma 10. (Optimism) With probability at least 1− 1H ,M ∗ ∈ Uk holds for any episode k ∈ [K].
Proof. This lemma comes directly from Theorem 6 of Ayoub et al. (2020). Define the Filtration F = (Fh)h>0 so that Fh−1 is generated by (s1, a1, λ1, · · · , sh, ah, λh). Then we have E[λh(sh+1) | Fh−1] = PM∗λh(sh, ah) = fM∗(sh, ah, λh). Meanwhile, λh(sh+1) − fM∗(sh, ah, λh) is conditionally D2 -subgaussian given Fh−1. By Theorem 6 of Ayoub et al. (2020), we can directly know that fM∗ ∈ Uk for any k ∈ [K] with probability at least 1− 1H .
Proof. (Proof of Theorem 7) Let τ(k) be the first step of episode k. Under the high-probability event defined in Lemma 10, we can decompose the regret using the same trick in previous sections.
K∑ k=1 τ(k+1)−1∑ h=τ(k) Hρ?M∗ −R(sh, ah) (89)
≤ K∑ k=1 τ(k+1)−1∑ h=τ(k) (ρ?Mk −R(sh, ah)) (90)
= K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMkλh(sh, ah)− λh(sh)) (91)
= K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMk − PM∗)λh(sh, ah) + K∑ k=1 τ(k+1)−1∑ h=τ(k) (PM∗λh(sh, ah)− λh(sh)) (92) ≤ K∑ k=1 τ(k+1)−1∑ h=τ(k) (PMk − PM∗)λh(sh, ah) + K∑ k=1 τ(k+1)−2∑ h=τ(k) (PM∗λh(sh, ah)− λh(sh+1)) +DK,
(93) where the first inequality is due to optimism condition in Lemma 10. The first equality is due to the Bellman equation 13 and λh = λ∗Mk for τ(k) ≤ h ≤ τ(k + 1) − 1. The last inequality is due to 0 ≤ λh(s) ≤ D for any s ∈ S. Now we bound the first two terms in Eqn 93. The second term can be regarded as a martingale difference sequence. By Azuma’s inequality, with probability at least 1− 1H ,
K∑ k=1 τ(k+1)−1−1∑ h=τ(k) (PM∗λh(sh, ah)− λh(sh+1)) ≤ D √ 2H log(H). (94)
Now we focus on the upper bound of the first term in Eqn 93. Under the high-probability event defined in Lemma 10, the true model P is always in the model class Uk. For episode k, from the construction of Uk we know that any f1, f2 ∈ Uk satisfies ‖f1 − f2‖2Zτ(k) ≤ 2β. SinceM
k,M∗ ∈ Uk, we have
T (k−1)∑ t=1 ((PMk − PM∗)λt(st, at)) 2 ≤ 2β (95)
Moreover, by the if condition in Line 8 of Alg. 4, we have for any τ(k) ≤ h ≤ τ(k + 1)− 1, h∑
t=τ(k)
((PMk − PM∗)λt(st, at)) 2 ≤ 2β + α+D2. (96)
Summing up the above two equations, we have
h∑ t=1 ((PMk − PM∗)λt(st, at)) 2 ≤ 4β + α+D2. (97)
We invoke Lemma 26 of Jin et al. (2021) by setting G = F − F , Π = {δx(·)|x ∈ X} where δx(·) is the dirac measure centered at x, gt = fMk − fM∗ , ω = 1/H , β = 4β + α + D2 and µt = 1 {· = (st, at, λt)}, then we have
K∑ τ=1 T (τ)∑ t=S(τ) |(PMτ − PM∗)λt(st, at)| ≤O (√ dimE(F , 1/H)βH + min (H, dimE(F , 1/H))D +H · 1 H ) (98)
=O (√ dimE(F , 1/H)βH )
(99)
Plugging the results back to Eqn 93, we have
K∑ k=1 τ(k+1)−1∑ h=τ(k) Hρ? −R(sh, ah) ≤ O ( D √ HdimE(F , 1/H) log (H · N (F , 1/H)) ) (100)
By Lemma 2, we have V ∗M∗,1(s1) ≤ Hρ∗M∗ +D. Therefore, we have
V ∗M∗,1(s1)− H∑ h=1 R(sh, ah) ≤ O ( D √ HdimE(F , 1/H) log (H · N (F , 1/H)) ) , (101)
with probability at least 1 − 2MH . If the high-probability event doesn’t holds (This happens with probability at most 2H ), then the gap V ∗ M∗,1(s1) − V π∗DR M∗,1(s1) still can be bounded by H . Taking expectation over the trajectory {sh}h, we have
V ∗M∗,1(s1)− V π∗DR M∗,1(s1) ≤O ( D √ HdimE(F , 1/H) log (H · N (F , 1/H)) +H · 2
H )
) (102)
= O ( D √ HdimE(F , 1/H) log (H · N (F , 1/H)) ) . (103)

heading: F.2 PROOF OF THEOREM 4
text: Proof. Theorem 4 can be proved by combining Theorem 7 , Lemma 1 and Lemma 2. By Theorem 7, for anyM ∈ U , the policy π̂ represented by Algorithm 4 can obtain regret bound Hρ∗M −∑H h=1R(sh, ah) ≤ O ( D √ deH log(H · N (F , 1/H)) ) . Taking expectation over {sh, ah}h∈[H] and combining the inequality with Lemma 2, we have for anyM∈ U .
V ∗M,1(s1)− V π̂M,1(s1) ≤ O ( D √ deH log(H · N (F , 1/H)) ) . (104)
Then the theorem can be proved by Lemma 1.

heading: G LOWER BOUNDS

heading: G.1 PROOF OF PROPOSITION 1
text: Proof. Consider the following construction of U . There are 3M + 1 states. There are M actions in the initial state s0, which is denoted as {ai}Mi=1. After taking action ai in state s0, the agent will
transit to state si,1 with probability 1. In state si,1 for i ∈ [M ], the agent can only take action a0, and then transits to state si,2 with probability pi, and transits to state si,3 with probability 1 − pi. State {si,2}Mi=1 and {si,3}Mi=1 are all absorbing states. That is, the agent can only take one action a0 in these states, and transits back to the current state with probability 1. The agent can only obtain reward 1 in state si,2 for i ∈ [M ], and all the other states have zero rewards. Therefore, if the agent knows the transition dynamics of the MDP, it should take action ai with i = arg maxi pi in state s0.
Now we define the transition dynamics of each MDPMi. For each MDPMi ∈ U , we have pi = 1 and pj = 0 for all j ∈ [M ], j 6= i. Therefore, the agent cannot identifyM∗ in state s0. The best policy in state s0 for latent MDP U is to randomly take an action ai. In this case, the sim-to-real gap can be at least Ω(H) since the agent takes the wrong action in state s0 with probability 1− 1M .

heading: G.2 PROOF OF THEOREM 3
text: Proof. We first show that Ω( √ MH) holds with the hard instance for multi-armed bandit (Lattimore & Szepesvári, 2020). Consider a class of K-armed bandits instances with K = M . For the bandit instanceMi, the expected reward of arm i is 12 + , while the expected rewards of other arms are 1 2 . Note that this is exactly the hard instance forK-armed bandits. Following the proof idea of the lower bound for multi-armed bandits, we know that the regret (sim-to-real gap) is at least Ω( √ MH).
We restate the hard instance construction from Jaksch et al. (2010). This hard instance construction has also been applied to prove the lower bound in episodic setting (Jin et al., 2018). We firstly introduce the two-state MDP construction. In their construction, the reward does not depend on actions but states. State 1 always has reward 1 and state 0 always has reward 0. From state 1, any action takes the agent to state 0 with probability δ, and to state 1 with probability 1 − δ. In state 0, there is one action a∗ takes the agent to state 1 with probability δ + , and the other action a takes the agent to state 1 with probability δ. A standard Markov chain analysis shows that the stationary distribution of the optimal policy (that is, the one that takes action a∗ in state 0) has a probability of being in state 1 of
1 δ
1 δ + 1 δ+ε
= δ + ε 2δ + ε ≥ 1 2 + ε 6δ for ε ≤ δ. (105)
In contrast, acting sub-optimally (that is taking action a in state 0) leads to a uniform distribution over the two states. The regret per time step of pulling a sub-optimal action is of order /δ.
Consider O(S) copies of this two-state MDP where only one of the copies has such a good action a∗. These copies are connected into a single MDP with an A-ary tree structure. In this construction, the agent needs to identify the optimal state-action pair over totally SA different choices. Setting
δ = 1D and = c √ SA TD , Jaksch et al. (2010) prove that the regret in the infinite-horizon setting is Ω( √ DSAT ).
Our analysis follows the same idea of Jaksch et al. (2010). For the MDP instance Mi, the optimal state-action pair is (si, ai) ((si, ai) 6= (sj , aj),∀i 6= j). With the knowledge of the transition dynamics of eachMi, the agent needs to identify the optimal state-action pair over totally M different pairs in our setting. Therefore, we can similarly prove that the lower bound is Ω( √ DMH) following their analysis.

heading: G.3 LOWER BOUND IN THE LARGE SIMULATOR CLASS
text: Proposition 2. Suppose All MDPs in the MDP set U are linear mixture models (Zhou et al., 2020) sharing a common low dimensional representation with dimension d = O(log(M)), there exists a hard instance such that the sim-to-real gap of the policy π∗DR returned by the domain randomization oracle can be still Ω(H) when M ≥ H .
Proof. We can consider the following linear bandit instance as a special case. Suppose there are two actions with feature φ(a1) = (1, 0) and φ(a2) = (1, 1). In the MDP setM, there are M − 1 MDPs with parameter θi = ( 12 ,−pi) with 1 4 < pi < 1 2 , i ∈ [M − 1], and one MDP with parameter θM =
( 12 , 1 2 ). Suppose M = 4H + 5, the optimal policy of such an LMDP with uniform initialization will never pull the action a2, which can suffer Ω(H) sim-to-real gap in the MDP with parameter θM .

Review summaries:
This paper presents a theoretical framework for reasoning and analyzing domain-randomization techniques. Its approach models a simulator instance as a Markov Decision Process for which the parameters of the MDP correspond to tunable simulator parameters. In this designed setting, the work proves sharp bounds on the gap between an optimal policy's value in the domain-randomized and the real-world setting. The work also analyzes the conditions under which sim-to-real transfer can be successful in the considered theoretical setting.

This paper presents a theoretical framework for analyzing the sim-to-real gap in the context of domain randomization. The paper defines formally the sim-to-real gap and the domain randomization method. Next, it analyzes the upper bound of sim-to-real gap in three different scenarios: finite simulation classes with and without separation conditions and infinite simulation classes. The paper provides constructive arguments to prove the upper bounds.  In my opinion, this paper has made multiple contributions. I am most impressed by its theoretical framework that formally defines the sim-to-real problem and its proof of the upper bound of the sim-to-real gap based on the constructive arguments described in the paper. 

The paper is a theoretical analysis of domain randomization in the context of latent MDPs. The paper provides bounds on a definition of the sim-to-real gap, defined as the difference between the optimal value function and a "domain randomization oracle" value function. In this context the oracle is defined as a history dependent policy which uses the first steps in the environment to improve its belief on the latent variable and then optimally behaves according to this belief.   Provided bounds can be applied in three different contexts: finite domain randomization (i.e. domain randomization on a finite number of domains) satisfying a separation conditions (i.e. a requirement on the existence of a state-action pair which leads to sufficiently different next states), finite domain randomization without the separation condition and infinite domain randomization.   Bounds are expressed in terms of D (i.e. a bound on number of time steps required to reach any other state in the state space) and of H (i.e. the number of steps in an episode). In the case of finite simulators with separation the domain gap is O(D log^3(H)). In the case of finite simulators without separation the domain gap is O(D H^(1/2) log^(1/2)(H)). In the case of infinite domain randomization the gap is approximatively O(D H^(1/2) log^(1/2)(H)).   Bounds are provided with assumptions and most of these assumptions are justified by proving that removing these assumptions opens the possibility to counterexamples which do not meet the provided bounds. 

The goal of this paper is formalize and analyze the technique of domain randomization in robotics. The authors frame domain randomization as training over a set of "plausible MDPs", only one of which is the MDP that will be used at test time. The authors then analyze the best possible performance of models for this problem under 3 different settings: when the set of plausible MDPs is finite with and without a separation condition, and when the set of plausible MDPs is infinite. The authors find algorithms that achieve a performance gap that beats the worst case performance gap of $O(H)$ in all three settings ($O(log^3H)$ and $O(\sqrt{H})$).