Understanding Domain Randomization for Sim-to-real Transfer
Authors: Xiaoyu Chen
Jiachen Hu
Chi Jin
Lihong Li
Liwei Wang
Venue: ICLR 2022 Spotlight (2022)
Keywords: domain randomization
sim-to-real transfer
learning theory

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 largely missing. 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.

Published as a conference paper at ICLR 2022
UNDERSTANDING DOMAIN RANDOMIZATION FOR SIM- TOM-TO-REAL TRANSFER
Xiaoyu Chen & JJiachen Hu"
Chi Jín
Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence, Peking University {cxy30, Ni wickh)@pku. wwt.pp.u..uu.......oomeoeee..... edu.cn
Department of Electrical and Computer Engincering, Princeton University chi jēpr iepprriinettnn.emm edu
Lihong Li
Liwei Wang
Amazon
Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence, Peking University International Center for Machine Learning Research, Peking University wang 1 wis.s. pku edu.cn
1 11h0 Amazon. com
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 ular algorithms for sim-to-real transfer has been demonstrated to be effective 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 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 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., policies) in domain randomization. Our proof is based novel techniques that reduce the problem of bounding the sim-to-real gap to the prob- lem of designing efficient learning algorithms for infinite horizon MDPs, which we believe are of independent interest.
of the most pop-
INTRODUCTION
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 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 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 to train an RL agent in a simulator that approximates the real world and then trans- fer the trained agent to the real environment. This paradigm has been widely applied, especially in roboties (Rusu al. 2017 Peng et al.) 2018 Chebotar et al., 2019) and autonomous driving (Pouyanfar et al. 2019: Niu et al.) 2021). Sim-to-real transter is appealing as it provides an essen- tially 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
'hheee authors contributed equally.

---

Published as a conference paper at ICLR 2022
mismatch between simulated and real environments. In addition to building higher-fidelity simula- tors to alleviate this gap, domain randomization is another popular method (Sadeghi & Levine 2016) Tobin et all, 2017 Peng al.) 2018: OpenAl 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 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 al., 2018 OpenAl et al. 2018).
In this paper, we focus on understanding sim-to-real transfer and domain randomization from theoretical perspective. The empirical successes raise the question: can we provide guarantees for the sub- ootbmaitillltyy 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-depencee is randomly drawn from a set of MDPs in the simulator at the beginning of each episode.
policy for latent MDP, in which an MDP
Our contributions can be summarized as follows:
We propose novel formulation of sim-to-real transfer and establish the connection be- tween domain randomization and the latent MDP model (Kwon et al. 202I). 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 satisfies certain smoothness condition, where is the horizon of the real-world interaction. We also provide a lower bound showing that such benign conditions necessary for efficient learning. Our theory highlights the importance of using memory (i.c., history-dependeen 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 anfinite-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 aafinite-horizon average-reward MDPs with general function approximation (Algorithm in Appendix (.3). Our algorithm achieves regret bound of ((DVa,T)
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).
2 RELATED WORK
Sim-to-Real and Domain Randomization The basic idea of sim-to-real is first train RL. agent in simulation, and then transfer it to the real environment. This idea has been widely applied to problems such robotics (e.g. Ng et al. 2006 Bousmalis al. [2018] Tan et al. 2018 OpenAl et al. 2018)) and autonomous driving (e.g., Pouyanfar et al. 2019 Niu et al. 2022 l). To alleviate the influence of reality gap, previous works have proposed different methods help with sim-to-real
transfer, including progressive networks (Rusu et al. 2017). inverse dynamics models (Christiano al. 2016) and Bayesian methods (Cutler & How|
et al., 2018). Domain random- ization 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 OpenAl 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 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. |eng et al. (201)) 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
2

---

Published as a conference paper at ICLR 2022
al. 2019) formulate theoretical sim-to-real framework using the rich observation Markov de- cision processes (ROMDPs), and show that the transfer can result in 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 observ- able (Smallwood & Sondik 1973; Kaelbling et al. 1998; Vlassis et al.] 2012 Jin et al. 2020a Xiong al. 2021). Latent MDPs (Kwon et al. 202 D. or LMDPs, are 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 hidden- hidden-model 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; [Bcchholz & Scheftelowitsch 2019 Steimle et al. 202T). Kwon et al. (202T) 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 gaper-bounding the performance gap of transferring the optimal policies of latent MDPs from simulation to the real environment.
infinite-horizon wverage-Reward MDPs Recent theoretical progress has produced many prov- ably sample-efficient algorithms for RL in infinite-horee horizznn average-reward setting. Nearly matching upper bounds and lower bounds are known for the tabular setting (Jaksch al., 22010; Fruit al., 2018 Zhang & Ji. 2019: Wei et al.] 20220). 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 / is the first efficient algorithm with near-optimal regret for
infinite-horizon average-reward MDPs with general function approximation.
3 PRELIMINARIES
3.1 EPISODIC MDPs
We consider episodic RL problems where each MDP is specified by M = (S, A, H,,)), 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 SSX x A + ASS) is the transition probability matrix so that P(-|s, a) gives the distribution over states action a is taken on state 8, : x A + [0 the reward function. H is the number of steps in episode.
For simplicity, we assume the agent always starts from the same state in each episode, and use $1 denote the initial state step h It is straight-forward to extend our results the case with random initialization. At step E [M]. the agent observes the current state 84 E S, takes action an E A, receives reward R(s), an), and transits to state 81+1 with probability P(sh+1|sh, az). The episode ends when sH+1 is reached.
We consider the history-dependent policy class II, where from the history observations to the distributions over actions. Specifically, we use traj,, {(s1, a1, 82, a.. .t)). |s S.a; E A. i [h] to denote the set of all possible trajec- tories of history till step h. We define a policy π E II to be a collection of H policy func- the value function at
1l a collection of mappings
tions {TT Iraja > ((A)]e(())- We define VM.
-- -RR
step h under policy on MDP M, i.e., (),(s)) = EM, (E (t) sh s]. Accord- ingly, we define QM,a. S + R to be the Q-value function at step h. @Ma(ssa)
EMM (R(s,, an) + DE R(st, a.) ) 8h. 8, a).
We use JM to denote the optimal policy for a single MDP M. It can be shown that there exists Th such that the policy step h depends only the state at step h but not any other prior history. That
is. Te can be expressed as a collection of H policy functions mapping from S to A(A). We use M. and QunA denote the optimal value and Q-functions under the optimal policy क. MM at step h.
Ve
3

---

Published as a conference paper at ICLR 2022
3.2 PRACTICAL IMPLEMENTATION OF DOMAIN RANDOMIZATION
In this subsection, we briefly introduce how domain randomization works in practical applications. Domain randomization
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 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. OpenAl et al. (0188) studied the problem of dexterous in-hand manipulation. The training is performed entirely in a simulated environment 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 randomiza- tion is usually build 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 simu- lation 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 policy that generalizes to reality. The policy trained with domain randomization can be represented using recurrent neural network with mem- ory such as LSTM (Yu et al., 2018 8 OpenAl et al.) 2018 Doersch & Zisserman [019). Such a memory-augment
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 simula- tion 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 OpenAl al. 2018).
4 FORMULATION
In this section, we propose our theoretical formulation of sim-to-real and domain randomization. The corresponding models will be used 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.
4.1 SIM-TO-REAL TRANSFER
In this paper, we model the simulator set of MDPs with tunable latent parameters. We consider an MDP set Z representing the simulator model with joint state space and joint action space A. Each MDP M = (S, A, PM, Rt, H1) in U has its own transition dynamics PM. which corre- sponds 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 MDP M E lí 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 la that represents MDPs under different tunable latent parameter. Or equivalently, the learning agent is allowed to interact with any MDP M E U in arbitrary fashion, and sample arbitrary amount of trajectories. However, we do not know which MDP M E l represents the real environment. The objective of sim-to-real transfer is to find a policy purely based on 24 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(TT = Vur. - VM- (s1).
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 any real-world samples for training; (2) would like 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 leamed in simulation using real-world samples can
4

---

Published as a conference paper at ICLR 2022
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.
4.2 DOMAIN RANDOMIZATION AND LMDPS
We first introduce Latent Markov decision processes (LMDPs) and then explain domain random- ization in the viewpoint of LMDPs. A LMDP can be represented as (L), where U is set of MDPs with joint state space S and joint action space A, and v is a distribution over 4. Each MDP M = (S, A, PM, R. H, 91) in 2Z has its own transition dynamics PM that may differs from other MDPs. At the start of an episode, an MDP M E U is randomly chosen according to the distribution
v. The agent does not know explicitly which MDP sampled, but she allowed to interact with this MDP M for one entire episode.
Domain randomization algorithm first specifies distribution over tunable parameters, which equiv- alently gives distribution v over MDPs in simulator U. This induces a LMDP with distribution v. The algorithm then samples trajectories from this LMDP, runs RI. 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 v be the uniform distribution over U. The domain randomization oracle returns an optimal cestory-depeneent policy ThR of the LMDP (U,
DD
arg max V MM1 (s1).
mEll
Since LMDP is special case of POMDPs, its optimal policy TDr in general will depend on his- tory. This is in sharp contrast with the optimal policy of a MDP, which is history-indeppndent, We emphasize that both the memory-augment ment are critical to the optimality guarantee of domain randomization. We also note that we don't t restrict the learning algorithm used to find the policy TDR. which can be either in a model-basee or model-free style. Also, we don't explicitly define the behavior of TDR- The only thing we know about Ti that it satisfies the optimality condition defined in Equation 2 In this paper, we aim to bound the sim-to-real gap of ToR i.e., Gap(#DR.24 2) under different regimes.
policy and the randomization of the simulated environ-
MAIN RESULTS
We are ready to present the sim-to-real gap of Dig in this section. We study the gap in three different settings under our sim-to-real framework: finite simulator class (the cardinality [2d] is finite) with the separation condition (MDPs in l/ are distinct), finite simulator class without the separation condition, and infinite simulator class. During analysis, 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 TDg is only O(log((!) for the finite simulator class with the separation condition, and only Ö(VH) 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 bounded diameter.
Assumption (Communicating MDPs (Jaksch al. 2010)). The diameter of any MDP M E U is bounded by D. That is, consider the stochastic process defined by stationary policy л S - A on an MDP with initial state s. Let T(') π. denote the random variable for the first time step in which state s' is reached in this process, then ea min E
[ (8' |M, (,,.s) 8)] < D.
This is a natural assumption widely used in the literature (Jassch 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. More- over, the diameter assumption is necessary under our framework.
Proposition 1. Without Assumption there exists a hard instance 1t that Gap(TōR) = S(H).
5

---

Published as a conference paper at ICLR 2022
We prove Proposition in Appendix G.1 Note that the worst possible gap of any policy is H, so TDe becomes ineffective without Assumption
5.1 FINITE SIMULATOR CLASS WITH SEPARATION CONDITION
As starting point, we will show the sim-to-real gap when the MDP set 2/ is a finite set with cardi- nality 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 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 // is known to the agent).
Before presenting the general results, we first examine a simpler case where all MDPs U are distinct. Concretely, we assume that any two MDPs in U are well-separated on at least one state- action 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 (6-separated MDP set), For any M, E U, there exists state-action pair (s) S A, such that the L1 distance between the probability of next state of the different MDPs is at least 8, i.e. [I(MM - PM,) (- a)llı 2 6.
The following theorem shows the sim-to-real gap of TD ò-separated MDP sets.
Theorem 1. Under Assumption and Assumption for any M U, the sim-to-real gap TDR
al most
(DM' log (H) log (SMH/0)
Gap(TTR) O
84
The proof of Theorem Tis is deferred to Appendix D Though the dependence on M and 8 may not be tight, our bound has only poly-logarithmic dependence the horizon H.
The main difficulty to prove Theorem T is that we do not know what "DR does exactly despite knowing 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 MDP M after identifying M Therefore, we use a novel constructive argument in the proof. We construct 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
5.2 FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION
Now we generalize the setting and study the sim-to-real gap of कंR when is finite but not necessary a ó-separated MDP set. Surprisingly, we show that DD can achieve Õ(VH) H) sim-to-real gap when [4|| M.
Theorem 2. Under Assumption] ? when the MDP set induced by domain u is a finite set with cardinality M, the sim-to-real gap of dia is upper bounded by
Gap(m ( (DVM&Hlog(Mi))
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 OpenAl et al. [0188. With both of them, we successfully reduce the worst possible gap of T from the order of H to the order of VH, per step loss will be only -12-1 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 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 constructive argument to prove Theorem 2 However, it is more difficult 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 memory-based

---

Published as a conference paper at ICLR 2022
policy, which basically can be viewed algorithm that seeks minimize the sim-to-real gap in an unknown underlying MDP in 24. Therefore, we connect the sim-to-real gap of the base policy with the regret bound of the algorithms in infintt- average-reward MDPs (Bartlett & Tewari 2012 Fruit et al. 2018 Zhang & Jil 2019). The proof overview is deferred to Section
To illustrate the hardness of minimizing the worst case gap, we prove the following lower bound for Gap( IT, U) to show that any policy must suffer gap at least 9 ())
Theorem 3. Under Assumption 7 suppose A 2 10, Z M > 100, D 20 M, H. 2 DM, for any history dependent policy π {Th, trajn 7 h=r there exists a set of M MDPs u = (Mm) m== and a choice of M E l such that Gap(T) is at least (M)D.
The proof of Theorem follows the idea of the lower bound proof for tabular MDPs (Jaksch al.) 2010), which we defer to Appendix G.2 This lower bound implies that (VVH) sim-to-real gap is unavoidable for the policy TDR when directly transferred to the real environment.
5.3 INFINITE SIMULATOR CLASS
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 the Dexterous Hand Manipulation algorithms (Ope- nAI al. 2018). In these cases, the induced MDP set 2/ is large and even infinite. A natural question is whether we can extend our analysis to the infinite simulator class case, and provide a correspond- ing sim-to-real gap.
Intuitively, since the domain randomization approach returns the optimal policy in the average man- ner, the policy "DR can perform bad in the real world .M if most MDPs in the randomized set differ much with M In other words, U must be "smooth" near MM for domain randomization to return nontrivial policy. By "smoothness", we mean that there is a positive probability that the uniform distribution y returns a MDP that is close to .M.. This is because the probability that v samples exactly M in infinite simulator class is O, so domain randomization cannot work at all if such smoothness does not hold.
Formally, we assume there is distance measure M2) on U between two MDPs M₁ and M2. Define the e-neighborhood CM-.. of M as CM-,ce (M E U d(M, s c). The smoothness condition is formally stated as follows:
Assumption (Smoothness near M There exists a positive real number co, and Lipchitz con- stant L,, such that for the policy TDx. the value function of any two MDPs in CMr,co is I-Liiphhiz w.r. the distance function d, i.e.
Do Mi,1 (51) (s1)
Do M, (s)) S L. (1-M(M1,,,)) VM,, Car..o
(5)
For example, we can set M2) = I[M1 * 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 it is possible to compute the sim-to-real gap of T In the finite simulator class, have shown that the gap depends M polynomially, which be viewed as the complexity of U. The question is, how do we measure the complexity of lI when it is infinitely large?
Motivated by Ayoub et al. 2020), we consider the function class
J F= U= Ax R such that fM(s, a, PMA((s for for
where A= (Xy, u) is the optimal bias functions of M E U in the infinite-horizon average- reward 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 e-log-covering number and the e-cluder dimension of F to characterize the complexity of the simulator class U. In the setting of linear combined models (Ayou et al. 2020), the e-log-covering number and the e-eluder dimension
7

---

Published as a conference paper at ICLR 2022
O (d])) 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 andd the sim-to-real gap of the domain randomization policy
DD most for 0 S <
DV D log (H -N(,11H)) + Le
Gap(
V (C)..e)
Here (c) is the probability of sampling a MDP in CM- de dim (F,1 1/H) is the 1 1/H- eluder dimension F, and (F H) is the 1/H-covering number of F. w.r.. Los norm.
Theorem a of Theorem 2 since we can reduce Theorem A Theorem setting ((MM,MM2) = M[Mi * M22] and 0, in which case v(CM- ,e) 1/M and de S 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 Ö(VH). A key point to note is that construction of the base policy also solves open problem of designing efficient algorithms that achieve (vTT) regret in the infinite-horizi 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 I have nice low-rank properties (e.g., the linear low-rank property (Jin et al.) 2020b Zhou al., 2020)). the policy TDR returned by the domain randomization oracle can still have Q (HH) sim-to-real gap when the simulator class is large and the smoothness condition (Assumption does not hold. This explains the necessity of our preconditions. Please refer to Proposition in Appendix G.3 for details.
PROOF OVERVIEW
In this section, we will give short overview of our novel proof techniques for the results shown in section The main proof technique is based on reducing the problem of bounding the sim-to-real gap to problem of constructing base policies. 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.
6.1 REDUCING TO CONSTRUCTING BASE POLICIES
Intuitively, if there exists base policy â TI with bounded sim-to-real gap, then the gap of DD will not be too large since FDR defined in Eqn 2 is the policy with the maximum average value.
Lemma Suppose there exists policy à πI such that the sim-to-real gap of â for any MDP M U satisfies Vinn(s:) (s1) I C, then we have Gap(TTR) S MC when U is finite set with [u] M. Furthermore, when U is infinite satisfying the smoothness condition (assumption 3. we have for any < < cv. Gap(TTR) I C/v (CM-..) + Le.
We defer the proof to Appendix B.I 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 history-dependent policy म E IT with minimum sim-to-real gap maxMen (Vi,) (=1))
6.2 THE CONSTRUCTION OF THE BASE POLICIES
With separation conditions With the help of Lemma we can bound the sim-to-real gap in the setting of finite simulator class with separation condition by constructing a history-dependent policy
8

---

Published as a conference paper at ICLR 2022
f. 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 con- struct 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 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 horizon average-reward setting has been well-studied (e.g., Jaksch et al. 2010 Agrawal & Jial 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 - s). The optimal gain is defined as
as p²((s = -EllimT-oo Et= R(se, n (st))/T
p (s) der
= maxses max; p² (s)), which is shown to be state-independent in Agrawal & Jia (017).
so we use p for short. The regret in the infinite-horizon setting is defined
(T)
E Tpp Et R(s;,a)) a.). 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.
For an MDP M E 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 | ensures that the agent can travel to any state from any state ни encountered at the //-th step (this may not be the case in the standard finite- horizon MDPs, since people often assume that the states at the H-th level are terminating state). The following lemma shows the connection between these two views.
Lemma 2. For MDP M. let P'M and (11) to be the optimal expected gain in the infinite- horizon view and the optimal value function in the episodic view respectively. We have the following inequality: H P D < (s1) I -
This lemma indicates that, if we can design an algorithm (i.e. the base policy) क in the infinite- horizon setting with regret Reg(H), then the sim-to-real gap of this algorithm in episodic setting satisfies Gap(#) = ($1) - (s1) S Reg(H) 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 D and 2 the remaining problem is design efficient exploration algo- rithm for infinite-horizon average-reward MDPs with the knowledge that the real MDP M belongs known MDP set U. Therefore, we propose two optimisticeexploaaiio
algorithms (Algorithm
and Algorithm 44) for the setting of finite simulator class and infinite simulator class respectively. The formal definition of the algorithms are deferred Appendix C.2 and Appendix C.3 Note that our Algorithm 4 is the first efficient algorithm with Ö(VT) regret in the mnfiitt-horiizn average- reward MDPs with general function approximation, which is of independent interest for efficient online exploration in reinforcement learning.
CONCLUSION
In this paper, we study the optimality of policies learned from domain randomization in sim-to-real transfer without real-world samples. We propose 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 TDx can suffer only of o(H) loss compared with the optimal value function of the real enviromment when the simulator class is finite or satisfies certain smoothness condition, thus this policy can perform well in the morizoo cases. We hope our formulation and analysis can provide insight to design more efficient algorithms for sim-to-real transfer in the future.

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGMENTS
Liwei Wang was supported by National Key R&D Program of China (2018YFB1402600) Ex- ploratory Research Project of Zhejiang Lab (No. 2022RC0AN02), BJNSF (L172037), Project 2020BD006 supported by PKUBaidu Fund.
REFERENCES
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint arXiv:1705.07011, 2017.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-4744 PMLR, 2020.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient Q-learnigg with low switching cost. arXiv preprint arXiv: 12849 2019.
Peter L. Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. arXiv preprint arXiv: 1205.2661, 2012.
Konstantinos Bousmalis, Alex Irpan, Paul Wohlhart, Yunfci Bai, Matthew Kelcey, Mrinal Kalakrish- nan, Laura Downs, Julian Ibarz, Peter Pastor, Kurt Konolige, et al. Using simulation and domain adaptation to improve efficiency of deep robotic grasping. In 2018 IEEE international conference on robotics and automation (ICRA), pp. 4243 4250. IEEE, 2018
Peter Buchholz and Dimitri Scheftelowitsch. Computation of weighted sums of rewards for concur- rent MDPs. Mathematical Methods of Operations Research, 89(1):1-42, 2019.
ladine Chades, Josie Carwardine, Tara Martin, Samuel Nicol, Régis Sabbadin, and Olivier Buf- fet. MOMDPs: solution for modelling adaptive management problems. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
Yevgen Chebotar, Ankur Handa, Viktor Makoviychuk, Miles Macklin, Jan Issac, Nathan Ratifff and Dieter Fox. Closing the sim-to-real loop: Adapting simulation randomization with real world experience. In 2019 International Conference on Robotics and Automation (ICRA), pp. 8973- 8979. IEEE, 2019.
Paul Christiano, Zain Shah, Igor Mordatch, Jonas Schneider, Trevor Blackwell, Joshua Tobin, Pieter Abbeel, and Wojeiech Zaremba. Transfer from simulation to real world through learning deep inverse dynamics model. arXiv preprint arXiv:1610.03518, 2016
Mark Cutler and Jonathan P How. Efficient reinforcement learning for robots using informative simulated priors. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 1660526112 IEEE, 2015.
Carl Doersch and Andrew Zisserman. Sim2real transfer learning for 3d human pose estimation: motion to the rescue. Advances in Neural Information Processing Systems, 1111199912999 2019.
Fei Feng, Wotao Yin, and Lin F Yang. How does an approximate model help in reinforcement learning? arXiv preprint 1xXiv:1912002988 2019.
Dario Floreano, Phil Husbands, and Stefano Nolfi. Evolutionary robotics. Technical report, Springer Verlag, 2008
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span- taas--saa-consstrane constrained exploration-exploiaa in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586. PMLR, 2018.
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved analysis of UCRL2 with empirical bernstein inequality. arXiv preprint arXiv:2007.0544 2020.
10

---

Published as a conference paper at ICLR 2022
Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman. Relay policy learning: Solving ong-horizon tasks via imitation and reinforcement learning. arXiv preprint arXiv:1910.11956. 2019.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 11(4), 2010.
Nan Jiang. PAC reinforcement learning with an imperfect model. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi cient? arXiv preprint arXiv: 180.00377 2018.
Chi Jin, Sham M Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. arXiv preprint 20Xiv:2006.12484. 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143.
PMLR. 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprinl arXiv:2 2021.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2):99-134, 1998.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal Robotics Research, 32(11):1238-12) 1274, 2013.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin Yang. Online sub- sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07203, 2021.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent MDPs: Regret guarantees and lower bound. arXiv preprint Stti::2002.09333 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Ajay Mandlekar, Danfei Xu, Roberto Martin-Martin, Silvio Savarese, and Li Fei-Fei. Learn- ing to generalize across long- aag-horizoon tasks from human demonstrations. arXiv preprint vrXiv:2003.0608 2020.
Jan Matas, Stephen James, and Andrew J Davison. Sim-to-real reinforcement learning for de- formable object manipulation. In Conference on Robot Learning, pp. 734-743, PMLR, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5609 2013.
Andrew Ng, Adam Coates, Mark Diel, Varun Ganapathi, Jamie Schulte, Ben Tse, Eric Berger, and Eric Liang. Autonomous inverted helicopter flight via reinforcement learning. In Experimental robotics IX, pp. 363-372. Springer, 2006.
Haoyi Niu, Jianming Hu, Zheyu Cui, and Yi Zhang. DR2L: Surfacing corner cases to robus- tify autonomous driving via domain randomization reinforcement learning. arXiv preprint arXiv:2107.17622 2021.
OpenAl, Marcin Andrychowicz, Bowen Baker, Maciek Chociej. Rafal Józefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, Jonas Schneider. Szy- mon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojciech Zaremba. Learning dexterous in-hand manipulation. CoRR, 2018. URL httptttpp//axxx..orggg////////// www..i.og....///......aaaaaaa/ /s
00177
Ian Osband and Benjamin Van Roy. Model-basee reinforcement learning and the Eluder dimension. arXiv preprint arXiv: /406. / 1853, 2014.
11

---

Published as a conference paper at ICLR 2022
Rémi Pautrat, Konstantinos Chatzilygeroudiss and Jean- Sean-Baptiste Mouret. Bayesian optimization with automatic prior selection for data-efficient direct policy search. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7571-7578, IEEE, 2018.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 20/8 IEEE international conference robotics and automation (ICRA), pp- 3803-3810 IEFE, 2018.
Sören Pirk, Karol Hausman, Alexander Toshev, and Mohi Khansari. Modeling long-horizon tasks as sequential interaction landscapes. arXiv preprint 2XXx:2006.04843 2020.
Samira Pouyanfar, Muneeb Saleem, Nikhil George, and Shu-Ching Chen. ROADS: Randomization for obstacle avoidance and driving in simulation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 0-0, 2019.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pp. 2256-2264. Citeseer, 2013.
Andrei A Rusu, Matej Večerík, Thomas Rothörl, Nicolas Heess, Razvan Pascanu, and Raia Hadsell. Sim-to-real robot learning from pixels with progressive nets. In Conference on Robot Learning, pp. 262-270. PMLR, 2017.
Fereshtch Sadeghi and Sergey Levine. Cad2rl: Real single-image flight without a single real image. arXiv preprint arXiv:1611.04200 2016.
David Silver, Julian Schrittwisser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. nature, 550(767)):354-359) 2017.
Richard D Smallwood and Edward J Sondik. The optimal control of partially observable Markov processes over a finite horizon. Operations research, 21(5):1071-1088 1973.
Lauren N Steimle, David L Kaufman, and Brian T Denton. Multi-model Markov decision processes. IISE Transactions, pp. 1-16, 2021.
Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke, Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint a8Xiv: /0332, 2018.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Oriol Vinyals, Igor Babuschkin, Wojciech Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782)350-334, 2019.
Nikos Vlassis, Michael L Littman, and David Barber. On the computational complexity of stochastic controller optimization POMDPs. ACM Transactions on Computation Theory (TOCT), 4(4): 1-8. 2012.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded Eluder dimension. arXiv preprint arXiv:2005. 10804, 2020.
Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward Markov decision processes. In International Conference Machine Learning, pp. 10170-10180 10.. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinitehhorizon average-reward MDPs with linear function approximation. In International Conference on Artifi- cial Intelligence and Statistics, pp. 3007-3015. PMLR, 2021.
Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning POMDPS. arXiv preprint arXiv:2107.033:: 2021.
Wenhao Yu, C Karen Liu, and Greg Turk. Policy transfer with strategy optimization. arXiv preprint 1810000810 2018.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. arXiv preprint 1rXiv:196.005100, 2019.
Yuren Zhong, Aniket Anand Deshmukh, and Clayton Scott. PAC reinforcement learning without real-world feedback. arXiv preprint arXiv: 1909. 10449, 2019.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture Markov decision processes. arXiv preprint arXiv:2012.08500 2020.
A ADDITIONAL PRELIMINARIES
A.1 INHNITE-HORIZON AVERAGE-REWARD MDPS
The infinite-horizon average- reward setting has been well-explored in the recent few years (e.g. Jaksch 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 policy is defined in the average manner.
Definition 2. (Definition 4 in Agrawal & Jia (017 The gain p" (s)) of a stationary policy from starting state $1 is defined as:
T Σ [=l
1² (8)
E
lim
R(s (8r)) 81
(8)
T-
T
In this setting, common assumption is that the MDP is communicating (Assumption Tb. Under this assumption, we have the following lemma.
Lemma 3. (Agrawal & Jia 2017 Lemma 2.1) 1) For a communicating MDP M with diameter D: (a) The optimal gain p" state independent and is achieved by a deterministic stationary policy The that is, there exists a deterministic policy IT" such that
max max p" (s')=p" Vs) E'ES
(9)
(b) The optimal gain p" satisfies the following equation:
p² min max [R(s.a) + PA(s,a) a) - >(s)] = max (R(s,0) -X((,,)-x(ss), AERS
- Xx)s
(10)
where P\(s,a)= = E., P(s))s, and X is the bias vector of the optimal policy The satisfying
0 D<X((ss
(11)
The regret minimization problem has been widely studied in this setting, with regret be defined as Reg(T) E TTp Σ R(s,, a:) where the expectation is over the randomness of the
trajectories. For example, Sasample,aasehee Jaksch et al. (2010) proposed an efficient algorithm called UCRL2, which achieves regret upper bound O AT). For notation convenience, we use (V,s or PX(s.a) shorthand of Exres P(s'|s, a) (s') Eves P(s'|s, (ss').
13

---

Published as a conference paper at ICLR 2022
A.2 ELUDER DIMENSION
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.] [020] Ayoub et al. 20200] Jin et al. [222]] Kong et al. 2021). In this work, we define eluder dimension to characterize the complexity of the function F:
F (-M((,,,,))) S Ax R such that SM(s, = PM))(,,) for M M
(12)
where A Mi E U) the optimal bias functions of M E U in the infinite-horizon average- reward setting (Bartlett & Tewari (2012); Fruit et al. (2018): Zhang & Ji (2019))
Definition 3. (Eluder dimension). Let e 2 0 and Z {(s, a, AO C S AxA A be a sequence of history samples.
A history sample (s.a, a, A) x A A is e-dependent on Z with respect if any f' E F satisfying If f'llz S E also satisfies [[ f(,, S e. Here I| fff-fll f
is a shorthand of y (G.A))Z f')(ss,,,))
An (s,a, c-independent of Z with respect to F if (s, a, A) is not c-dependent on Z.
The c-eluder dimension of a function class F is the length of the longest sequence of el- ements in S x A x A such that, for some e' c, every element is é'iindependent of its predecessors.
B OMITTED PROOF IN SECTION
B.1 PROOF OF LEMMA 1
Proof. We firstly study the case where LI is finite set with / = M. For मt, we have
1 Σ (V), V (s1)) s C.
(13)
M
MEN
By the optimality of =DR we know that
Σ M,1 (s1)
1 M
Σ
V (81)
(14)
M
MEU
MEll
Therefore,
Σ (Vi,
Vidaa vxiR((s)) s C.
(15)
M
MEU
Since the gap ( M. (s1) 2 0 for aor i E [M]. we have x (Virr,((1)) - V. (s1)
5
C. That is,
(irr,((s1) - ViTin VM & MC.
(16)
For the case where // an infinite set satisfying Assumption 3 by the optimality of Ton. we have
EM Vidt
2 EM (s)]
(17)
Therefore,
E M.v((Cur.)) (ir. viti < EMar Vir, (i 5 Emar (s1)
v=)(s:)]
(18)
14

---

Published as a conference paper at ICLR 2022
By Assumption 3 for any M C(M", c), have
Viit,,(ss)) - (1)) $ Le.
(19)
Therefore, we have
v (CM- (VMr,1(51)) (Mt,)(8)) TO) = Bmwo(enete) (Vr. V. (s1)
(20)
Combining Inq and Inq 20, we have
(C (Vir, VM VM (81) T6 S SC,
(21)
The lemma can be proved by reordering the above inequality.
B.2 PROOF LEMMA
Proof. For MDP M, denote Tin as the optimal policy in the infinite-horizon setting and { hepphhh=l
1H
the optimal policy in the episodic setting. By the optimality of Tep- we have V (s1) VM (51) 2 MM (s1).
By the Bellman equation the infinite- setting, we know that (ss(s + PM = R(s, (s) + PMAMM(s, (s)), S
(22)
For notation simplicity, we use da ($1, to denote the state distribution at step h after starting from state 81 at step 1 following policy æ. From the above equation, we have
(11) + HPM
Σ h=1
E, da ) R(sh, (s ( (M (23)
That is,
11
B.g -d R(sh, Ti (sn)) Hp''l = [AM(s)) - Bag indem1 MM < D,
h=1
(24)
where E Eenndn(ona Mish 7 (sW) (s1) Therefore, we have Hp² - s Vinn (81) S (si).
For the second inequality, by the Bellman equation in the infinite-horizon setting, we have
(s(ss) + HPM > Be (o Te (sw)) + E aa
(25)
That is,
E Panndda (es, R(sh, Tepa((n)) - HpM S Xii(s1) tr < D,
A=1
(26)
where ΣH Bes (a Roh, ( F
(s))
C THE CONSTRUCTION OF LEARNING ALGORITHMS
C.I FINITE SIMULATOR CLASS WITH SEPARATION CONDITION
In this subsection, we explicitly define the base policy á with sim-to-real gap guarantee under the separation condition. Note that history-dependent policy for LMDPs can also be regarded as
15

---

Published as a conference paper at ICLR 2022
Algorithm Optimistic Exploration Under Separation Condition
1: Initialize: the MDP set U, no co log" (SMH) log (M) for constant cp
5
2: Stage 1: Explore and find the real MDP M
3: while (D) N do
4: Randomly select two MDPs M1 and M2 from the MDP set D
5: Choose (8o: Qo) = arg (x.)) x (M PM,) ( 8,
6: Call Subroutine 2 with parameter (#o: 00) and no to collect history samples M.
PMe, (a' (00,0))
7:
if 3s's E H.M.Ma: PM, su: ao) = 0 or II 1 Pxc (e' 2 then
8:
Eliminate M2 from the MDP set D
9: else
Eliminate M1 from the MDP set D 11: end
10:
end while
13: b Stage 2: Run the optimal policy of M
14: Denote M as the remaining MDP in the MDP set D
15: Run the optimal policy of M for the remaining steps
Algorithm Subroutine: collecting data for (so, ag)
Input: informative state-action pair (8o, an), required visitation count no
Initialize: counter N (So. ao) = 0, history data = 0
Denote (M s') as the policy with the minimum expected travelling time (s' [,, ग, s)]
for MDP M (Defined in Assumption
T
while (5s,, 0p) S Tig do
5:
for i 1, ... .M do
Denote the current state Sinit
Run the policy JM, (Sinit, 80) for 2D steps, breaking the loop immediately once the agent enters state 80
end for
if the agent enters state so then Execute au, enter the next state s'. counter N(s. 0p) = N(s,, an) + 1, 1. 7l = H HUss
10:
end if
end while
Output: history data H
16

---

Published as a conference paper at ICLR 2022
algorithm for finite-horizon MDPs. By deriving an upper bound of the sim-to-real gap for ft,
upper bound Gap(TiR: 24) with Lemma] 1
The policy á is formally defined in Algorithm There are two stages in Algorithm D In the first stage, the agent's goal to quickly explore the environment and find the real MDP MM' from the MDP set U. This stage contains at most M parts. In each part, the agent randomly selects two MDPs M and M2 from the remaining MDP set DD Since the agent knows the transition dynamics of M and M2, it can find the most informative state-action pair (so, ag) with maximum total- variation difference between PM₁ (-180, 4n) and PM2 (M2(-100, ao). The algorithm calls Subroutine 2 collect enough samples from (Sg. ao) 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.
Subroutine designed to collect enough samples from the given state-action pair (sg, ap). The basic idea in Subroutine 2 is to quickly enter the state 80 and take action do, until the visitation counter N (s0, (o) = R4g. Denote (s, s') as the policy with the minimum expected travelling time I (T (8/ M, s]] for MDP M. Suppose the agent is currently at state 8tiit and runs the policy TM- (Sinit, 80) in the following steps. By Assumption and Markov's inequality, the agent will enter state so in 2D steps with probability at least 1/2. Therefore, in Subroutine 2 runs the policy T,M, (8init, $0) for 2D steps for i E [M] alternatively. This ensures that the agent can enter state So in 2M steps with probability at least 1/2.
Theorem 5 states an upper bound of the sim-to-real gap for Algorithm I which is proved in Ap- pendix D.I
Theorem 5. Suppose we use ă to denote the history-dependent policy represented by Algorithm Under Assumption and Assumption 2 for any M E U, the sim-to-real gap of Algorithm 7 is at most
DM log (H (DMP)o((/H))))((MMM)M) (SMHH//188)))
(8)) (8) so
(27)
84
C.2 FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION
In this subsection, we propose efficient algorithm in the infinite-horizon average-reward setting for finite simulator class. Our algorithm is described in Algorithm 3 In cpisode k, the agent exccutes the optimal policy of the optimistic MDP M³ with the maximum expected gain PM Once the agent collects enough data and realizes that the current MDP M is not M that represents the dynamics of the real environment, the agent eliminates M from the MDP set.
Algorithm Optimistic Exploration
1: Initialize: the MDP set U1 = U1 the episode counter A: = 1, ho =
2: Calculate M arg max MEU, P'M
3: for step h 1, .. do
4: Take action Oy = π (sn), obtain the reward R(sk, an), and observe the next state 8h+1 Eh (PM+ (St, 0z) - >ixx (s++2)) > D 2 - ha) log then Eliminate M from the MDP set Ug, denote the remaining set as Ug-+1 7: Calculate M arg max MEM P.M
5: if
6:
8: Set by = h + 1. and +11.
9:
end if
end for
To indicate the basic idea of the climination condition defined in Line of Algorithm 3) we briefly explain regret analysis of Algorithm Suppose the MDP M selected in episode & satisfies the
17

---

Published as a conference paper at ICLR 2022
optimistic condition P'M= Pi--, then the regret in H steps can be bounded as:
H
HPM
R(sh.an an)
(28)
1=1
K
-((+1)-1
Σ
(P'= R(sh,an))
(29)
k=1
h=T(k)
K -(b+1)-1
(9h Xmrr(s))
(30)
7((+1)1
Σ
Σ
(1 -in (5h+11)))) Σ - (++(3))
(31)
h=r(k)
K (b+1))-1
Σ
(M9n)je((snna)) (in((sh+))) + KD.
(32)
1=1 h=T(k)
Here we use K to denote the total number of episodes, and we use 7(ks to denote the first step of episode k. The first inequality is due to the optimistic condition puy² 2 PiM-. The first equality due to the Bellman equation in the finite-horizon setting (Eqn [0]. The last inequality is due to know that the regret in episode depends MM (8k, an) - Xi (9h+1)). If this term is relatively small, we continue following the policy TM= with little loss. Since (Sx41) is empirical sample of PM-X2 (sh, an), we can guarantee that M not M with high probability this term is
O S (s) S D. From the above inequality,
the summation Σ (PMr x M
relatively large.
Based on the above discussion, we can upper bound the regret of Algorithm of Theorem to Appendix F.I
We defer the proof
Theorem 6. Under Assumption
the regret of Algorithm is upper bounded by
Reg( (1) S Reg(H)
(DVMML MH Moggo (M)(
(33)
C.3 INFINITE SIMULATOR CLASS
In this subsection, we propose 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 horizon average-reward MDPs with general function approximation.
Considering the model class 2/ which covers the true MDP M" i.e. M U, we define the function space A = {AM. M E U)) and space X' = S x A x A. We define the function space
F = (S a, A) X - such that fM a, X) = PMA(s, a) for M EM,AE
(34)
Our algorithm, which described Algorithm also follows the well-known principle of optimism in the face of uncertainty. In each episode k. we calculate the optimistic MDP M with maximum expected gain Piye- We execute the optimal policy of M interact with the environment and collect more samples. Once we have collected enough samples in episode k, we update the model class Ur and compute the optimistic MDP for episode + 1.
Compared with the setting of episodic MDP with general function approximation (Ayou et al.) 2020 Wang et al.) 22000) Jin et al. 202T), the additional problem in the infinite-horizon setting is that the regret technically has linear dependence steps that we update the optimistic model and the policy. This corresponds to the last term (K D) in Inq 32 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. 202T). Taking inspiration from the recent work that studies efficient exploration with low switching cost
the number of total episodes, or the number of
18

---

Published as a conference paper at ICLR 2022
1/1-f2l1 nnw in episodic setting (Kong et al. 2021), we define the importance score, fuPf [| fall -a as a measure of the importance for new samples collected current episode, and only update the optimistic model and the policy when the importance score is greater than 1. Here [l fa f2ll is shorthand of [s,,,s'AN)E (Ji(s, f2(8, x))²
Algorithm General Optimistic Algorithm
1: Initialize: the MDP set U1 = Lt episode counter A =
2: Initialize: the history data set
0. Znew =
3: = 4D2 + 1, 3 cD2 log (H (NFF, 1/H) H)) for a constant c.
4: Compute M = arg max.Me4, PM
5: for step h 1,
H do
6: Take action On = π M (3x) in the current state Sh, and transit to state $1+1
7: Add (sh, ah Sh+1, m==) to the set Znew
1fi-f2l2 2ncw 2 1 then
8: if importance score f. Ilf1 fal
9:
Add the history data Znew to the set Z Calculate Ma41 arg min El
dn ANeE (PMAn(sh;an) - >n(on+1))
Update Ux+1 MEE: EiEE (PM Prren) An(s SB
11:
12:
Compute M g++ = arg max Metli1 P'M
13:
Episode counter k = k +1
end
15:
end for
We state the regret upper bound of Algorithm in Theorem 5 and defer the proof of the theorem to Appendix F.
Theorem 7. Under Assumption 1 the regrer of Algorithm uppder bounded by
Reg( H) s SO (D (H (/H.1/H1)).
(35)
where de is the e-eluder dimension of function class F with H. and (NF, is the म
covering number of F w.r.l Los norm.
For a O, we say the covering number M(F a)) of F w.r. the Loo norm equals m if there m functions in F such that any function in F is at most away from one of these m functions in norm ||- 1loo. The loce norm of function f is defined || |lo max (f())).
def
D OMITTED PROOF FOR FINITE SIMULATOR CLASS WITH SEPARATION CONDITION
D.1 PROOF OF THBBREM 5
The formal definition of & is given in Algorithm [ To upper bound the sim-to-real gap of म, we discuss on the following states that the true MDP M 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
benign properties of Algorithm Lemma Aomuaaando and Lemma Lemma
states that the total number of steps in stage upper bounded by Ö A/ This is where the final bound in Theorem comes from.
Lemma 4. With probability least the true MDP M will never be eliminated from the MDP set D in stage I.
The while-loop stage will last for M times. To prove Lemma the true MDP M is selected in certain loop, then II ( high probability. This is illustrated in the following lemma.
4 we need to prove that, T (v'Isa)) PM(
2 1 holds with
19

---

Published as a conference paper at ICLR 2022
Lemma 5. Suppose H { a set of no log' (6 log()4H) independent samples
from given state-action pair (8o, 4n) and MDP M for large constant Let Mi denote
another MDP satisfying [I( PM,) (-100 ao) 2 then the following inequality holds with probability at least MH
PM (s'|s0: ao) 1, PM2 (5'150,00)) ao)
Il
(36)
EEE
Proof. The proof of Lemma enough to show that
5 is inspired by the analysis in Kwon et al. (2021). To prove Inq 36 it
PM- (s']so,, ao) II
PMM (M ao) (s'(('lbuu aa) > 0.
Σ In
(37)
SEE PM2 (0'10,,a))
NEW
holds with probability at least MH.
Note that Pxe (sl)s) PMr (00000) can be unbounded since PM, (s'1so, an) can be zero for certain s'. To tackle
this issue, we define PM, for sufficiently small a S 48:
(M =a (M-a8)
(38)
(-1s, (115 We have [PMM - Pm.) (1ss s 2Sa s 5. thus (PeM. - Par)) -
2 2/4 Also, we
have In
1
S In(1/a) for any s' E S. With the above definition, we can decompose
PMy (5"1m0,00)
Inq 37
into TWO terms:
Pm (5'1 ao) PM₁ (5'1su, ao)
(Pm-(s'loo ao) PM, (6'180, ao)
Pm (5")00.
PM (8' ao) PM (s' su, ax) )
Σ In S'EH
Σ In
+
Σ In
(39)
S'EH
E'EM
Taking expectation over s' PM
(.15,a) PMM-(1ls,
for the first term, we have
(Mu-(0/100.aa) an)
PM, (5/ an) 1
)]
PM (s's0s'(s,, PM2 (s' so, ag)
ln
ΣΣ PM- (s'ls, ao) In
(40)
=no DEL (PM- PM (s'(s0,
(41)
(42)
2
where the last inequality is due Pinsker's inequality.
Lemma 6. (Lemma C.2 in Kwon el (2027) Suppose is an arbitrary discrete random variable
on finite support X. Then, In(1/P(X) is sub-exponential random variable (Vershynin) 2010
with Orcliz norm (n(1/((X)) 1/ee.
oo) are sub-exponential From the above LEmma, know that both PM, (s' (/|ss,, an) and PM- (s' (s'[so, random variables. By azuma-Hoeffing 's inequality, we have with probability at least 1 - 6p/2,
1
no
PMs, (s/]50, (o)oo..))))))))))) ..)))
In
E
In
log(1/a) h/llaa///mmn 2no log (2/5o). (43)
(5'ls,,,
S'EN
By Proposition 5.16 in Vershynin (2010), with probability at least 50/2,
Σ
In (PM (8' ao)) 2
E
In (PM (s/1su, aol)) Vno /og(2//bu)))
(44)
FE
20

---

Published as a conference paper at ICLR 2022
for certain constant >> 0. Therefore, lower bound the first term in Equ 39
PM- (Ms-(s'(s0,au)
ngd²
Σ In S'EH
log(1/a)) log(2/6o) /nolo////6))/,
(45)
PM,
2
with probability at least d0-
For the second term in Equ 39 by the definition of P.M.
PMr (s') ao) PMs (5'180, ao) 2 -2aSmo
Σ S'EH
In
(46)
Combining Inq 45 and Inq 46
we have
Σ In PM- ao) ao) s'EH
nod²
log(1/a) logg)2//6 Vno log(2/6o)/c 20.Sno
(s'
(47)
Setting
62 85
60 MH
and no
cn (SMH11 we have
(P)o((')o0, > 0
Σ
(48)
PM, (s'180, au)
EE
holds with probability at least MH
Lemma Suppose Stage
in Algorithm ends ho steps. We have Eiho] O( DMP (SM log(MH)) where the expectation is over all randomness in the algorithm and 84
the environment.
Proof. Recall that ss) is the policy with the minimum expected travelling time E E (s' (, s)] for MDP M. By Assumption I
have
E IM (M,,,((ss)),))
(49)
Given state and s', by Markov's inequality, we know that with probability least 2.
( M" TM (s, s)),) < 2D.
(50)
Consider the following stochastic process: In each episode k, the agent starts from a state s that is arbitrarily selected, and run the policy JM' (8k, sn) for 2D steps on the MDP M The process terminates once the agent enters certain state sp- By Inq 50 the probability that the process terminates within & episodes is at least 1 zz. 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 π., for each MDP M, E D alternately. By Lemma 4 the true MDP M is always contained the MDP set D. Therefore, the expected travelling time to enter state so for no times is bounded by no M 8D. In stage 1, we call Subroutine 2 for satisfies E[ho] & 8M O
times, which means that the expected steps in stage DM ( (SMHH65) ())(
21

---

Published as a conference paper at ICLR 2022
Proof. (Proof of Theorem Recall that use ho to denote the total steps in stage 1. Firstly, prove that Gap(a,,1) is upper bounded by (h[hol D).
VM (81)
(81))
(51)
hg
=BAo
EM-,Tin-
R(sh, an) hg
+ BM
VM no
(Shot1) I ho]
(52)
Ebbo
E +
Σ
R(s an) ho
+ EE, [Vir Ao ( ho]
(53)
-=1
An
<Bho
iM EM" in
R(sh and ho
Eno EM [Vr (sho+1) ho] EM a [V to ( ho]
(54)
<hhhol + Ens EM .=j--
VV No A (sho++1 hol - EM to ho]
(55)
The outer expectation is over all possible ha, while the inner expectation is over the possible trajec- tories given fixed hgg By Lemma we know that TDR after ho steps with probability least If this high-probability event happens, the second part in the above inequality equals
1
E EM [VM. Aot1 (Stg ) ho] EMM [Vi+ No+1 ( ho]
We can prove that this term is upper bounded by 2D. Given fixed ho- EMr-sia- ( ho EM Viee 1 ho is the difference of the value function in step ho + under two different distribution of 8ho+1- We use da (s, T) to denote the state distribution in step after starting from state in step ho following policy n.
V ho (8hot1)
=
Σ
Exg ddn (sho 11. R(sh, (sn))
(56)
h h
Σ
(pis- + -ann ) (8h) E E Ee (sho ) (sh+1)
k=ho+1
(57)
=(H ho) +
Aiv- (2 (8 1), (58)
where the second equality is due to the Bellman equation in infinite-horie horizon setting (Eqn 10 Note that by the communicating property, we have 0 < X (s) & for any s E S. Therefore, we have noot (shot2) hu] -EM+,# [VM- MM--bo+1 (sho+1)
EM- [VM+,oo++
ho] 2D.
(59)
the high-probabillig event defined in Lemma 4 does not hold (This happens with probability at most 1. we still have EMr,-i [V (shg+1) ho EMM+, V hoo (sho+1) | ho H, thus this does not influence the final bound. Taking expectation over all possible ho. and plugging result back to Inq 5T. we have
(51 - Vir,, (B(ho D) o [DM* log (SMHH/))
(60)
g
D.2 PROOF OF THBOREM I
Proof. The theorem can be proved by combining Theorem 5 and Lemma]
By Theorem 5] we prove that the constructed policy a satisfies
lg (SM log( MH)
(81) - V&c. 0
(61)
g
22

---

Published as a conference paper at ICLR 2022
By Lemma the sim-to-real gap of policy "DR is bounded by
Gap(# M) - 0 DM log loM (MH)
(62)
04
OMITTED PROOF FOR FINITE SIMULATOR CLASS WITHOUT SEPARATION CONDITION
E
PROOF OF THEOREM 6
Lemma 8. (Optimism) With probability at least 1 MH we have P'M 2 PM for any k [K].
Proof. For any fixed M E U, and fixed step h E [H]. by Azuma's inequality, we have with proba- bility at least NH.
Σ (8++1) PM- (ot, az)) < DV/((h ho) log (2
(63)
Taking union bounds over all possible .M and h, we know that the above event holds for all possible M and h with probability 1 MH Under the above event, the true MDP M will never be eliminated from the MDP set U4. Therefore, we have Piu 2 PiM-.
Proof. (Proof of Theorem By Lemma we know that PiMe 2 PMM- for any [K]. We use T(h) to denote the episode that step h belongs to. We can upper bound the regret in H steps as follows:
HPM Σ
R(sh, an)
(64)
h=1
S
(Pirren) - R(sh: ap))
(65)
H
(Parosdirr an) )mmen((sn)
(66)
H1
Σ (Pa-is) PM- Xx (Sh, an)
Σ
(PM- (yro an) - Xi
(67)
H
(PMTT - ) (Sn, (irra an) + PM PM--jurrn Ajurcn and) (51)
(68)
H-1
(Pae- (Sh, an) Xmrres(sa41))) (sn+1))
(69)
By Azuma's 's inequality, we know that
Σ (PM-Xiero0 Xiuras (8k+22))))1) I DV H Hog(2MHH,
(70)
holds with probability at least WH X X (81) ) < D. Therefore, we have
Since 0 < AM < D, we have PM X Marcs (8hgs ahh)
HpM Σ
R(sh, an) S
(Paro) - PMc)) Xirraa (p) + D H Hog((HH (71)
4=1
h=1
log M DV Hog.H D.
(72)
23

---

Published as a conference paper at ICLR 2022
The first term in 71 is bounded by the stopping condition (line 5 of Algorithm 3 By Lemma
have 1 (81)
HpM- D. Therefore, have 1 (81) Σn=1 R(sh an))
(DVMH MH log(MH))
with probability at least 2_ Therefore, we have M/
VTD (o1)((01) (1 50 (HVMMHOO(MHH) + MH )
= (HVMHHog(MMM
(73)
E.2 PROOF THEEOREM
Theorem 2 can proved by combining Theorem 6 Lemma T and Lemma 2 By Theorem 6 for any M E U, the policy á represented by Algorithm has regret bound H Σ R(5h, an) S
o (D MH log(M Taking expectation over {Sh, an hhE and combining the inequality
with Lemma we have for any M E u.
(s)) (sn) so (DV log(MH)
(74)
Then the theorem be proved by Lemmal T
F OMITTED PROOF FOR INFINITE SIMULATOR CLASS
F.1 PROOF OF THEOREM 7
Lemma 9, (Low Switching) The total number of episode K is bounded by
log(H))
(75)
Proof. By Lemma 5 of Kong et al. (2021). we know that
"
(fi(x.) - f2(x)))
Σ
min
sup fI.EET
.1 .13 s log (D²H) log(H) lff f2ll2, +
(76)
for some constant C>> 0.
Our idea to use this result upper bound the number of total switching steps.
Let (lk) be the first step of episode k. By the definition of the function class F, we have (f1 (2)) < 4D² for any f2 F and 2,. By the switching rule, we know that, once the agent starts new episode after step T(k 1) we have
7(--1)-1
T(K)-I
Σ (k)
(11 f2) <
Σ t=1
(fi f2) + 4D3 Vf, f2
(77)
Therefore, have
1
-(k-1
Σ
(f1 (2) 2 Σ
(fi f2) +a 4D2 Vh, f2
(78)
t=1
24

---

Published as a conference paper at ICLR 2022
Now upper bound the importance score in the switching step T(k + 1) 1.
((ti(k) -
(f((z))) ((((t)) f2(x1))2
T(+41)-1
(fi(2.)) f2(xx))
min
sup fi.f2
.1
min
Σ
sup fu.f
Ilf fall2r(0) +
Ilfi - fall2.()) +
(=T(R)
(79)
T(+11--1 Σ
2(fi (2((2))
f2(x)))2
<min
sup
l1 - f2113- - -10 + a
1
(kT(k)
f.f2
(80)
r(k+1)-1 Σ
2xf f2(x2))
<min
fa.f2 ll fall2. -10 +
sup
1
(kT(R)
(81)
+(k+1)-1 Σ
2(f1(x4)) f2(22))2
S
min
sup
J1.fa 1I/1 - f2l12, 4D2 +
(=
(82)
Suppose the number of episodes is at most K. If we set 412 + 1, we have
I f2(x))
(k)
2(f((2z) fe(xx))2
min
fu.fa
sup
llfi
f2l12,
+a
min
fi.2a I f2l13, 4D2 2a
sup
(83)
(84)
By the switching rule, we have su above inequality exactly K. Thus we have
2 1. Therefore, the LHS of the
Un-fall 7kk)
K <
H) log( H).
(85)
Lemma 10. (Optimism) With probability at least 1. H. M E Uy holds for any episode & E [K].
Proof. This lemma comes directly from Theorem 6 of Ayoub et al.
(2020). Define the Filtration
= (Fn)nzo so that FA is generated by (#1, a1, A1. ... Sh, an. An)
Then we have [[Ar (91+1)
F Pu (Sh, ax) fM- (Sh, ag Ar). Meanwhile, (
fM (Sh, Ohe Ap) is condi-
tionally - --subgaussian given Fx-1. By Theorem 6 of Ayoub al.
2020 we can directly know
that fM- E Us for any E [K] with probability least H.
25

---

Published as a conference paper at ICLR 2022
Proof. (Proof of Theorem Let r(k be the first step of episode k. Under the high probbabiyyy
event defined Lemma 10 we can decompose the regret using the same trick in previous sections.
K -(+1)--1
Σ ((T())
Hp R(sh; an)
(86)
R=1
(1++1)-1
Σ (kT(
(Piu R(sh. ah))
(87)
K ((b+))-1
Σ
(88)
k=1 k=T(K)
Σ -(b41)-1
K +(k+1)-1
Σ
(PM (M.))
Σ Σ
(1h,))((),an)) (sh)))
(89)
(k)
k= h=T(k)
K ((+1))-1
K -(++1)-2
(PMr - (n) +
Σ A=T
(PM,)n(shaah) An(s4+1)) + DK,
(k)
(90)
where the first incquality is due to optimism condition in Lemma 10
The first equality is due to the
Bellman equation 10 and ' = X for rlk) I I T(k + 1) The last inequality is due to 0 S (s) I D for any E S.
Now we bound the first two terms in Eqn 90 The second term can be regarded as a martingale difference sequence. By Azuma's inequality, with probability least 1
K -k+11)-1-1 Σ
Σ k=T(K)
- -n)
S Dv 2H (H).
(91)
Now focus the upper bound of the first term in Eqn 90 Under the high-probability event
defined in Lemma TO the true model P is always in the model class Us For episode k, from the
construction of U₁ we know that any fI, f2 e Ul satisfies f fell3_ 28. Since M M
Ur. we have
T(-11)
Σ ((PM - PM-) )e(s,, s
(92)
Moreover, by the if condition in Line 8 of Alg. have for any T(k) < h T(k:
1.
Σ ((PM - PM.. ((s s 23 D
(93)
(=)(
Summing up the above two equations, we have
(PMM - PM-) P( 488 + +
(94)
We invoke Lemma 26 of Jin et al. (-) is the dirac measure centered at x, 9t = fM - fMr, w = 1/H, B 43 + + D and
2021 by setting G F- (6.())z X} where
/4 1 {: (st, Ct, A²) then we have
26

---

Published as a conference paper at ICLR 2022
T(r)
Σ
1(MM
Ae aell so
(dims(FF1/H)88 (0VVims(VV1///
min (H, dim D
H
1
T=l S()
(95)
=0 (iddims
(96)
Plugging the results back to Eqn 90 we have
Σ Hp R(s,, an) so 50(Dv (F/.m(F..///))) (DDD)))(OO(FFF///
log (H (NFF,/H))
(97)
(A))
By Lemma
we have 1 (81) S Pps D. Therefore, we have
(81 Σ a()n s so Hdim (H -N(F.
(98)
A=1
with probability at least WH If the high-probability event doesn't holds (This happens with (51)
probability at most )), then the gap VMr.. (81) (51) still can be bounded by H. Taking expectation over the trajectory {sp hh, we have
2 H
(0 Vinn M- (81) 50 D (ddim(FF.1/1)) log (H ((F,1/H)) (H-(,,, H
(99)
0 DVV Hdiim log (H (N(F,
(100)
F.2 PROOF OF THEOREM 4
Proof. Theorem can be proved by combining Theorem Lemma 1 and Lemma 2 By Theo-
rem 7 for any M E U, the policy स represented by Algorithm 4 can obtain regret bound HpM
Σ R(Sh, 0n) s o (D log(H H (N(F,1/H)) Taking expectation over {sh, ah ]EEHH]
and combining the inequality with Lemma 2 we have for any M Eu.
(s1) - (s1) < ( (DV log(! (NFF.1HH)
(101)
Then the theorem can be proved by Lemmal I
G LOWER BOUNDS
G.1 PROOF OF PROPOSITION
Proof. Consider the following construction 4. There are 3M + 1 states. There are M actions in the initial state 8o, which is denoted as {a:) After taking action in state Sp, the agent will transit to state 5,, with probability 1. In state $1,1 for E [M]. the agent can only take action ag- and then transits to state 8;,2 with probability pi, and transits state 81,3 with probability 1 pi- State ) and J.M are all absorbing states. That is, the agent can only take one action do in these states, and transits back to the current state with probability 1. The agent can only obtain reward 1 in state $12 for i [M]. and all the other states have zero rewards. Therefore, if the agent knows the transition dynamics the MDP. should take action a, with arg max, P; in state sp-
Now define the transition dynamics of each MDP M,. For each MDP M, U. have p; and Pj = 0 for all j E [M], j * i. Therefore, the agent cannot identify M in state sy- The best policy in state sn for latent MDP L/ is to randomly take action a, In this case, the sim-to-real gap can be at least ((H) since the agent takes the wrong action in state 8o with probability 37.
27

---

Published as a conference paper at ICLR 2022
G.2 PROOF OF THEOREM 3
Proof. We first show that S v HH) holds with the hard instance for multi-armed bandit (Lattimore) & Szepesvári 2020). Consider class of K-armed bandits instances with K = M. For the bandit instance M, the expected reward of arm is _ + e, while the expected rewards of other arms are 2 Note that this is exactly the hard instance for K Kaamed 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 S2( H).
We restate the hard instance construction from Jaksch et al. (2010). This hard instance construction has also been applied prove the lower bound in episodic setting (Jin al. 2018). We firstly introduce the two-state MDP construction. In their construction, the reward does not depend on actions but states. State always has reward and state always has reward O. From state I, any action takes the agent to state O with probability 6, and to state 1 with probability 1 - 8. In state O, there is one action a" takes the agent to state with probability + e, and the other action a takes the agent to state 1 with probability 5. A standard Markov chain analysis shows that the stationary distribution the optimal policy (that is, the one that takes action a in state 0) has a probability of being in state of
8+5 25 +
1 2
for e S 6.
(102)
2 65
In contrast, acting sub-optimally (that is taking action in state 0) leads to uniform distribution over the two states. The regret per time step of pulling a sub-optimal action is of order e/8.
Consider O(S) copies of this two-state MDP where only one of the copies has such 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
SA 5 and cv TD Jaksch al. (2010) prove that the regret in the infinite-horizon setting is ((VDSAT).
Our analysis follows the same idea of Jaksch et al. (2010). For the MDP instance M₁. the opti- mal state-action pair is (s,, 04) ((s,, a,) * (s).a)). ). vi * 2). With the knowledge of the transition dynamics of each M,, the agent needs to identify the optimal state-action pair over totally M dif- ferent pairs in our setting. Therefore, we can similarly prove that the lower bound is 2(VDMH) following their analysis.
G.3 LOWER BOUND IN THE LARGE SIMULATOR CLASS
Proposition 2. Suppose All MDPs in the MDP set I are linear mixture models ZZhou et al.) 2020 sharing a common low dimensional representation with dimension d = Olog((M) M)), there exists hard instance such that the sim-to-real gap of the policy TDe returned by the domain randomization oracle can be still (HH) when M 2 H.
Proof. We can consider the following linear bandit instance as a special case. Suppose there are two actions with feature d(a1) (1, 0) and o(a2) = (1, 1). In the MDP set M, there are M MDPs with parameter 0; = ( -p:) with < p; < i E [M - 1], and one MDP with parameter On = ( }) Suppose M = 4H + 5, the optimal policy of such an LMDP with uniform initialization will never pull the action 0g which can suffer Ω H)) sim-to-real gap in the MDP with parameter
0 M..
28


Reviews:
[{"review_id": "yQoITDBrhds", "reviewer": "Reviewer_WmdZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well organized and easy to read. Most of the mathematical concepts do come with an intuitive description of their meaning and this allows the reader to get a grasp on the importance of the theoretical results. \n\nThe focus of the paper is very relevant to the ML and RL community. Domain randomization is emerging as a fundamental training procedure and theoretical guarantees on its performance are a necessary requirement for application in the real world. The submitted paper not only provides this bounds but also express them in terms of quantities (e.g. the value function gap) which are relevant for downstream real-world applications. \n\nThe main limitation of the paper is in assuming no fine-tuning with real-world samples. The concept of \"domain randomization oracle\" implicitly assumes the ability to eventually find the global optimal policy exploiting history and memory. Somehow this ability shares some commonalities with fine-tuning and therefore it seems possible to extend the author's approach to the more relevant scenario of domain-randomization with fine-tuning. \n\nAnother limitation of the paper is related to the format required by the conference. The submission is limited to 9 pages which the authors comply to. However, the proofs of all theorems are in the supplementary material which, as a reviewer, shouldn't be necessary to get most of the paper. This is in this case not really the case because I believe proofs are a necessary component to understand the quality and relevance of the paper. \n\nADDITIONAL COMMENTS\n- Page 5. \"The agent does not know explicitly which MDP is sampled, but **she** is allowed to interact with this MDP M for one entire episode.\". -> it\n\n- Page 5. \"We consider the ideal scenario that the domain randomization algorithm eventually **find** the globally optimal policy of this LMDP,\". -> finds\n\n", "summary_of_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. \n\nProvided 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. \n\nBounds 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)). \n\nBounds 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. ", "summary_of_the_review": "An important and relevant paper which addresses the problem of computing bounds for the value function of a policy trained with domain randomization and tested on one instance of the latent MDP distribution sampled during training with domain randomization. The paper doesn't have limiting assumptions besides the absence of analyzing how results extend to the fine-tuning case. \n\nAs a reviewer, checking the correctness of the paper wasn't easy because all relevant proofs are not in the main paper (9 pages) but mostly in the supplementary material (14 pages). The proof overview (section 6) isn't enough to check the paper correctness. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "mBObQw8ptFo", "reviewer": "Reviewer_SVo4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I believe that the main strength of this work is providing a theoretical analysis of sim-to-real deployment via domain randomization. Sim-to-real is of particular importance for enabling safe training in simulation. Theoretically analyzing and understanding this setting has the potential to provide safety guarantees and inform the design of new algorithms. While the analysis provided by this work is interesting, in the current stage I have three major concerns. First, its motivation and contribution seem to be detached from sim-to-real practice. Second, the assumptions (if I understood them correctly) seem to be very restrictive, and finally there is no evaluation whatsoever (e.g. to quantify a gap between the derived bounds and any realistic sim-to-real setting)\n\n# Motivation and Contribution\nIt is a very interesting approach to analyse sim-to-real transfer by interpreting simulators as a class of MDPs with different transition models. However, in the way this work is currently phrased, I am not sure if it provides any practically useful results. A theory work does not necessarily have to be at a stage that it is useful but I would have expected a clear technical discussion of the papers limitations in order to make use of such results in any real-world system. Currently, the link to practical implementations is provided to some extent in Sec 3.2. However, this section feels very detached from the rest of the work. It does introduce how domain randomization works in practice but does not discuss how the results of this work relate to it.\n\n# Assumptions\nThe initial discussion speaks of domain randomization in general. However, the assumptions seem to be very restrictive:\n\n* While I believe that assumption 1 is common, it would be interesting to see for which simulator real-world simulator it holds. In the case where the state-space is continuous with continuous support, the expectation $E(T(s'|\\mathcal{M}, \\pi, s))$ can easily become infinite for many interesting system classes?\n* There is a similar issue with assumption 2. As I understand it, it makes it very hard for the simulator instances in $\\mathcal{U}$ to be configurable in a continuous way because this assumption basically enforces to have a minimum distance between any two simulator instances. I wonder where this happens in practice.\n\nAgain, in theoretical work, it may be okay to have such restrictive assumptions. However, the authors should spell out which simulator & environment combinations currently satisfy such assumptions. And if there are none (which may be okay for an otherwise interesting theoretical work), there should be at least a discussion on what are the main limiting factors of the assumption compared to practical settings.\n\n# Evaluation\nI believe that the absence of any experiments is also problematic. Theoretical papers do not necessarily always need to have experiments (some theoretical contributions cannot be evaluated or may not require experimental evaluation). However, in the present case, the work aspires to address a practically relevant setting and seeing the performance evaluated seems quite relevant given that Domain Randomization already has an extensive empirical body of work. Even some of the pure theoretical results can be nicely illustrated with numerical experiments such as demonstrating cases in which derived bounds are particularly good or particularly bad.", "summary_of_the_paper": "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.", "summary_of_the_review": "In summary, I believe that this work addresses an interesting problem. Its main shortcomings are the lack of discussion linking the particular contribution and assumptions to particular use-cases as well as the absence of any experimental demonstrations.  Addressing these shortcomings will result in an interesting contribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kYBjpU73POs", "reviewer": "Reviewer_y2ZB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper very well written and easy to follow. Each assumption that the authors make - for instance that the MDPs are communicating or that the value functions are smooth - is justified by showing that there exist MDPs where the best case transfer performance is $O(H)$ in which case not much can be said. The bounds themselves are also intuitive and explain (to some extent) why zero-shot transfer is possible when training with domain randomization. \n\nOne suggestion that I had: the authors mention in the abstract and introduction that their results explain why policies trained with domain randomization should have memory. I think it might be worth mentioning in the body of the paper that the way in which Algorithms 1/3/4 use memory is somewhat different from parameterizing a network by an RNN. In these algorithms, memory is simply used to isolate the test time MDP, after which point the optimal policy (which is memoryless) for that MDP is used. In contrast, people in general would train a single RNN over the distribution of MDPs and then test the RNN on the test-time MDP. It's possible that the RNN internally learns to switch from using memory to becoming memoryless once enough observations have passed to internally determine the MDP, but it might be worth including some discussion of how Algorithms 1/3/4 compare to standard training schemes for applying domain randomization.\n\nCurrently, I feel that the bounds derived in the paper largely justify standard practices (e.g. parameterizing policies with memory when training with domain randomization, or why domain randomization should be used in the first place if one wants to transfer a policy trained in simulation to the real world), but don't suggest new practices. In the conclusion, the authors say they hope their analysis will lead to the design of more efficient algorithms for sim-to-real transfer, but I think the paper could benefit from more discussion of which of their results the believe could be the most applicable to improving how domain randomization is used in practical settings.", "summary_of_the_paper": "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})$).", "summary_of_the_review": "This paper formalizes the common practice of \"domain randomization\" and develops algorithms and bounds for the performance of domain randomization depending on if the set of randomized MDPs is finite (with or without separability) or infinite. The central result is that the performance gap is $\\tilde{O}(\\sqrt{H})$ in all cases. The formalization of domain randomization is accurate and the analysis of the problem setting is thorough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BvbsCwxROLN", "reviewer": "Reviewer_M8oh", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Let me start by admitting I am a sim-to-real practitioner, not a theorist. Therefore, it is likely that I am not fully aware of other related works that develop a similar theoretical framework. I have found the paper itself very inspiring, and both the theoretical formulation of the sim-to-real gap and the high-level idea behind the proof overview make very good sense to me. Still, I have a few comments, and it would be good if the authors could clarify them:\n\n1. There is another possible definition of sim-to-real gaps: the performance difference between a policy $\\pi$ (in particular, $\\pi^*_{DR}$) in the simulation environment and in the real world:\n\nGap($\\pi,\\mathcal{U}$) = $V_{\\mathcal{M}^*,1}^{\\pi}(s_1) -  \\mathbb{E} \\_{\\mathcal{M}\\sim\\nu} V_{\\mathcal{M},1}^{\\pi}(s_1)$.\n\nWhile I agree Eqn. (1) is perhaps a more interesting definition of sim-to-real gaps, Eqn. (1) is fairly difficult to measure in practice. Could the authors comment on these two definitions?\n\n2. It looks like the stepwise reward is assumed to be within 0 and 1. I guess the whole framework is also applicable to unbounded stepwise rewards, e.g., by remapping them to [0, 1] via a sigmoid function. Does this affect your main results?\n\n3. Comparing Sec. 5.1 and Sec. 5.2 seems to imply that narrowing the sim-to-real gap is more difficult for problems without separation condition, but I have a feeling that this is not always the case. Consider an extreme scenario where all $\\mathcal{M}$ in $\\mathcal{U}$ are very similar to each other (and therefore they are all similar to $\\mathcal{M}^*$. Such a $\\mathcal{U}$ is not a separated MDP set, but I would expect the sim-to-real gap to be much smaller than the gap given for the separated MDP set (Theorem 1). In particular, if $\\mathcal{U}$ simply copies $\\mathcal{M}^*$ multiple times, the sim-to-real gap would be 0. It looks like assuming only a few pairs of non-separated MDPs in $\\mathcal{U}$ may make the problem harder, but if all MDPs are non-separated, the problem seems to be much easier.\n\n4. The constructive argument for proving Theorem 1 seems interesting and smart, but I have a few questions about its technical details:\n\n* Alg. 1, line 7 (the condition in the if-statement): why not simply say “if $\\Pi P\\_{\\mathcal{M}_1}(s’|s_0,a_0)\\geq \\Pi P\\_{\\mathcal{M}_2}(s’|s_0,a_0)$”? This would also avoid the need for treating $P\\_{\\mathcal{M}_2}=0$ in Sec. D.1. Also, this if-condition does not seem to be symmetric: if there exists $P\\_{\\mathcal{M}_1}=0$ and $P\\_{\\mathcal{M}_2}=0$, it always chooses to eliminate $\\mathcal{M}_2$. Does it affect your proof? (Looks like it does not.)\n\n* Eqn. (41): are $s,a$ referring to $s_0,a_0$ specifically, or are they arbitrary states and actions? It looks like they should be $s_0,a_0$, according to the sentence immediately after Eqn. (41).\n\n* What is $\\tilde{\\mathcal{M}}$ in Eqn. (42) and Eqn. (49)? I was expecting $\\mathcal{M}_1$ there.\n\n* Eqn. (49): I do not see why $H$ appears on the right-hand side. It would make more sense to me if the right-hand side is $-2\\alpha S n_0$.\n\n* I cannot see how Eqn. (51) is derived from Eqn. (50) after trying to plug into Eqn. (50) the provided definitions of $\\alpha$, $\\delta_0$, and $n_0$. In particular, are $c$ in Eqn. (50) and $c_0$ in the definition of $n_0$ two different numbers? Also, it seems that $\\delta$ in the numerator of $n_0$ between Eqn. (50) and Eqn. (51) should be replaced with $\\delta_0$ so that it matches the definition of $n_0$ in Lemma 5.\n\nA few minor comments:\n\n1. Eqn. (1): why does Gap need to take $\\mathcal{U}$ as input if all it needs is $\\mathcal{M}^*$?\n\n2. What is $d$ in Theorem 3?\n\n3. The notation $PV$ is defined in Sec. 3.1 but does not seem to be used elsewhere in the main paper.\n\n4. How do we check if Assumption 3 is satisfied in practice?\n", "summary_of_the_paper": "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.\n\nIn 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.\n", "summary_of_the_review": "I appreciate the whole theoretical framework this paper establishes for studying domain randomization techniques for sim-to-real problems. I think defining the problem formally and properly is a good contribution.\n\nThe high-level proof overview makes good sense to me. I also manually checked the proof for finite simulator class (but not very carefully) in the appendix. The whole proof seems legit despite some minor issues, which I tend to think is relatively easy to fix.\n\nThe construction of base policies (Algorithms in the appendix) may also be interesting both for sim-to-real theorists and practitioners.\n\nOverall, I recommend strong acceptance assuming that all the equations in the main paper and in the appendix are correct or are relatively easy to fix.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript introduces a theoretical framework to analyze the sim2real transfer gap of policies learned via domain randomization algorithms. This work focusses on understanding the success of existing domain randomization algorithms through providing a theoretical analysis. The theoretical sim2real gap analysis requires two critical components: *uniform sampling* and *use of memory*

**Strengths**
All reviewers agree that this manuscript provides a strong theoretical analysis for an important problem (understanding sim2real gap)
well written manuscript, and well motivated
Intuitive understanding for theoretical analysis is provided


**Weaknesses**
analysis is limited to sim2real transfer without fine-tuning in the real world
the manuscript doesn't provide a novel experimental evaluation
lack of take-aways

**Rebuttal**
The authors acknowledge the limitation of not addressing fine-tuning, but also point out that several papers have performed sim2real transfer without fine-tuning. 
The authors address the lack of novel experimental evaluation by arguing that the theoretical analysis can be directly linked to existing algorithms for which empirical evaluations have already been performed. I agree with the authors that in that context it seems of little value to redo those experiments. However, I also believe that those links could be made even clearer in the manuscript and I would encourage the authors to do so. Furthermore, while the authors do provide intuitive take-aways for domain randomization algorithms, it would be helpful if those take-aways were more clearly linked to existing algorithms as well (given that there is no experimental evaluation of this). 

**Summary**
This manuscript provides a theoretical framework for analyzing the sim2real gap and using that framework provides bounds on the sim2real gap. All reviewers agree this is a strong theoretical analysis. Some take-aways on what makes domain randomization algorithms successful are provided by the provided sim2real-gap analysis (memory use, uniform sampling). Thus I recommend accept.
Decision: Accept (Spotlight)