Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL

Authors: andrew  wagenmaker
kevin  huang
liyiming  ke
kevin  jamieson
abhishek  gupta
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:19:06

Abstract: In order to mitigate the sample complexity of real-world reinforcement learning, common practice is to first train a policy in a simulator where samples are cheap, and then deploy this policy in the real world, with the hope that it generalizes effectively. Such \emph{direct sim2real} transfer is not guaranteed to succeed, however, and in cases where it fails, it is unclear how to best utilize the simulator. In this work, we show that in many regimes, while direct sim2real transfer may fail, we can utilize the simulator to learn a set of \emph{exploratory} policies which enable efficient exploration in the real world. In particular, in the setting of low-rank MDPs, we show that coupling these exploratory policies with simple, practical approaches---least-squares regression oracles and naive randomized exploration---yields a polynomial sample complexity in the real world, an exponential improvement over direct sim2real transfer, or learning without access to a simulator. To the best of our knowledge, this is the first evidence that simulation transfer yields a provable gain in reinforcement learning in settings where direct sim2real transfer fails. We validate our theoretical results on several realistic robotic simulators and a real-world robotic sim2real task, demonstrating that transferring exploratory policies can yield substantial gains in practice as well.

Main paper: 
 introduction: 
 Over the last decade, reinforcement learning (RL) techniques have been deployed to solve a variety of real-world problems, with applications in robotics, the natural sciences, and beyond [27, 54, 52, 26, 46, 23] . While promising, the broad application of RL methods has been severely limited by its large sample complexity-the number of interactions with the environment required for the algorithm to learn to solve the desired task. In applications of interest, it is often the case that collecting samples is very costly, and the number of samples required by RL algorithms is prohibitively expensive.In many domains, while collecting samples in the desired deployment environment may be very costly, we have access to a simulator where the cost of samples is virtually nonexistent. As a concrete example, in robotic applications where the goal is real-world deployment, directly training in the real world typically requires an infeasibly large number of samples. However, it is often possible to obtain a simulator-derived from first principles or knowledge of the robot's actuation-which provides an approximate model of the real-world deployment environment. Given such a simulator, common practice is to first train a policy to accomplish the desired task in the simulator, and then deploy it in the real world, with the hope that the policy generalizes effectively from the simulator to the goal deployment environment. Indeed, such "sim2real" transfer has become a key piece in the Figure 1 : Left: Overview of our approach compared to standard sim2real transfer on puck pushing task. Standard sim2real transfer first trains a policy to solve the goal task in sim and then transfers this policy to real. This policy may fail to solve the task in real due to the sim2real gap, and furthermore may not provide sufficient data coverage to successfully learn a policy that does solve the goal task in real. In contrast, our approach trains a set of exploratory policies in sim which achieve high-coverage data when deployed in real, even if they are unable to solve the task 0-shot. This high-coverage data can then be used to successfully learn a policy that solves the goal task in real. Right: Quantitative results running our approach on the puck pushing task illustrated on left, compared to standard sim2real transfer. Over 6 real-world trials, our approach solves the task 6/6 times while standard sim2real transfer solves the task 0/6 times. application of RL to robotic settings, as well as many other domains of interest such as the natural sciences [12, 15] , and is a promising approach towards reducing the sample complexity of RL in real-world deployment [19, 4, 18] .Effective sim2real transfer can be challenging, however, as there is often a non-trivial mismatch between the simulated and real environments. The real world is difficult to model perfectly, and some discrepancy is inevitable. As such, directly transferring the policy trained in the simulator to the real world often fails, the mismatch between sim and real causing the policy-which may perfectly solve the task in sim-to never solve the task in real. While some attempts have been made to address this-for example, utilizing domain randomization to extend the space of environments covered by simulator [60, 49] , or finetuning the policy learned in sim in the real world [50, 73] -these approaches are not guaranteed to succeed. In settings where such methods fail, can we still utilize a simulator to speed up real-world RL?In this work we take steps towards developing principled approaches to sim2real transfer that addresses this question. Our key intuition is that it is often easier to learn to explore than to learn to solve the goal task. While solving the goal task may require very precise actions, collecting high-quality exploratory data can require significantly less precision. For example, successfully solving a complex robotic manipulation task requires a particular sequence of motions, but obtaining a policy that will interact with the object of interest in some way, providing useful exploratory data on its behavior, would require significantly less precision.Formally, we show that, in the setting of low-rank MDPs where there is a mismatch in the dynamics between the "sim" and "real" environments, even when this mismatch is such that direct sim2real transfer fails, under certain conditions we can still effectively transfer a set of exploratory policies from sim to real. In particular, we demonstrate that access to such exploratory policies, coupled with random exploration and a least-squares regression oracle-which are insufficient for efficient learning on their own, but often still favored in practice due to their simplicity-enable provably efficient learning in real. Our results therefore demonstrate that simulators, when carefully applied, can yield a provable-exponential-gain over both naive sim2real transfer and learning without a simulator, and enable algorithms commonly used in practice to learn efficiently. Furthermore, our results motivate a simple, easy-to-implement algorithmic principle: rather than training and transferring a policy that solves the task in the simulator, utilize the simulator to train a set of exploratory policies, and transfer these, coupled with random exploration, to generate high quality exploratory data in real. We show experimentally-through a realistic robotic simulator and real-world sim2real transfer problem on the Franka robot platform-that this principle of transferring exploratory policies from sim to real yields a significant practical gain in sample efficiency, often enabling efficient learning in settings where naive transfer fails completely (see Figure 1 ). 
related work: 
 Provable Transfer in RL. Perhaps the first theoretical result on transfer in RL is the "simulation lemma", which transforms a bound on the total-variation distance between the dynamics to a bound on policy value [24, 25, 6, 22] -we argue that we can do significantly better with exploration transfer. More recent work has considered transfer in the setting of block MDPs [34] , but requires relatively strong assumptions on the similarity between source and target MDPs, or the meta-RL setting [69] , but only consider tabular MDPs, and assume the target MDP is covered by the training distribution. Perhaps most relevant to this work is the work of [36] , which presents several lower bounds showing that efficient transfer in RL is not feasible in general. In relation to this work, our work can be seen as providing a set of sufficient conditions that do enable efficient transfer; the lower bounds presented in [36] do not hold in the low-rank MDP setting we consider. Several other works exist, but either consider different types of transfer than what we consider (e.g., observation space mismatch), or only learn a policy that has suboptimality bounded by the sim2real mismatch [37, 56, 58] . Another somewhat tangential line of work considers representation transfer in RL, where it is assumed the source and target tasks share a common representation [35, 10, 2] . We remark as well that the formal sim2real setting we consider is a special case of the MF-MDP setting of [53] .Simulators and Low-Rank MDPs. Several existing works show that there are provable benefits to training a policy in "simulation" due to the ability to reset on command [67, 33, 5, 68, 70, 42] . These works do not consider the transfer problem, however. The setting of linear and low-rank MDPs which we consider has seen a significant amount of attention over the last several years, and many provably efficient algorithms exist [21, 1, 62, 63, 43, 41] . These works typically assume access to powerful oracles which enable efficient learning; we only consider access to a simple regression oracle. Beyond the theory literature, recent work has also shown that low-rank MDPs can effectively model a variety of standard RL settings in practice [72] .Sim2Real Transfer in Practice. The sim2real literature is vast and we only highlight particularly relevant works here; see [74] for a full survey. To mitigate the inconsistency between the simulator and real world's physical parameters and modeling, domain randomization creates a variety of simulated environments with randomized properties to develop a robust policy [60, 49, 44, 8, 39] . Domain adaptation instead constructs encoding of deployment conditions (e.g., physical condition or past histories) and adapts to the deployment environment by matching the encoding [29, 9, 66, 55, 38, 40] . In contrast, our work assumes a fundamental sim2real mismatch where we do not expect the real system to match the simulator for any parameter settings. A related line of work shows that policies trained with robust exploration strategies generalize better to disturbed or unseen environments [13, 20] . Our work is complimentary to this work in that our goal is not to transfer a policy that solves the task in new environment, but rather explores the environment.For any reward r, computing a policy π sim ( r) maximizing r on M sim .While access to such a policy optimization oracle is unrealistic in M real , where we want to minimize the number of samples collected, given cheap access to samples in M sim , such an oracle can often be (approximately) implemented in practice 4 . Note that under Oracle 4.2 we only assume black-box access to our simulator-rather than allowing the behavior of the simulator to be queried at arbitrary states, we are simply allowed to roll out policies on M sim , and compute optimal policies. Given Oracle 4.2, as well as our least-squares regression oracle, Oracle 4.1, we propose the following algorithm. which induce covariates with lower-bounded minimum eigenvalue on M sim and relies only on Oracle 4.2 (as well as knowledge of the featurization of M sim , ϕ s ) to find such policies. Algorithm 1 then plays these exploration policies in M real , coupled with random exploration, and applies the regression oracle to the data they collect. Finally, it estimates the value of the policy learned by the regression oracle and π sim,⋆ , and returns whichever is best. We have the following. Theorem 1. If Assumptions 1 to 4 hold andf h ← arg min f ∈F (s,a,r,s ′ )∈D (f h (s, a) -r -max a ′ f h+1 (s ′ , a ′ ))EQUATIONthen as long asT ≥ c • d 2 H 16 ϵ 8 • log H|F| δ ,with probability at least 1 -δ, Algorithm 1 returns a policy π such that V real,⋆ 0 -V real, π 0 ≤ ϵ, and Oracles 4.1 and 4.2 are invoked at most poly(d, H, ϵ -1 , log 1 δ ) times. Theorem 1 shows that, as long as ϵ sim satisfies (4.1), utilizing a simulator and least-squares regression oracle, Oracles 4.1 and 4.2, allows for efficient learning in M real , achieving a complexity scaling polynomially in problem parameters. This yields an exponential improvement over learning without a simulator using naive exploration or direct sim2real transfer-which Propositions 1 and 3 show have complexity scaling exponentially in the horizon-despite utilizing the same practical computation oracles. To the best of our knowledge, this result provides the first theoretical evidence that sim2real transfer can yield provable gains in RL beyond trivial settings where direct transfer succeeds.Note that the condition in (4.1) is independent of ϵ-unlike direct sim2real transfer, which requires ϵ = O(ϵ sim ), we simply must assume ϵ sim is small enough that (4.1) holds, and Theorem 1 shows that we can efficiently learn an ϵ-optimal policy in M real for any ϵ > 0. In Appendix B.4, we also present an extended version of Theorem 1, Theorem 3, which utilizes data from M sim to reduce the dependence on log |F|. In particular, instead of scaling with log |F|, it only scales with the log-cardinality of functions that are (approximately) Bellman-consistent on M sim . To illustrate the effectiveness of Theorem 1, we return to the instance of Propositions 1 and 3, where naive exploration and direct sim2real transfer fails. We have the following. Proposition 4. In the setting of Propositions 1 and 3 and assuming that ϵ sim ≤ 1 8192 • 1 H , running Algorithm 1 will require poly(H, ϵ -1 ) • log 1 δ samples from M real in order to identify an ϵ-optimal policy in M real with probability at least 1 -δ, for any ϵ > 0.Note that the condition required by Proposition 4 is simply that ϵ sim ≲ 1/H-as long as our simulator satisfies this condition, we can efficiently transfer exploration policies to learn an ϵ-optimal policy, for any ϵ > 0, while naive methods would be limited to only obtaining an Ω(1/H)-optimal policy. Remark 4.1 (Necessity of Random Exploration). Algorithm 1 achieves efficient exploration in M real by learning policies Π h exp in M sim that span the feature space of M sim (Line 2), and then playing these policies in M real , coupled with random exploration (Line 4). This use of random exploration is critical to obtaining Theorem 1. As we show in Proposition 5, if we omit the random exploration, Assumption 1 is not sufficient to guarantee Π h exp explores effectively in M real , even when (4.1) holds. Remark 4.2 (Computational Efficiency). Algorithm 1, as well as its main subroutine LEARNEXP-POLICIES, relies only on calls to Oracle 4.1 and Oracle 4.2. Thus, assuming we can efficiently implement these oracles, which is often the case in problem settings of interest, Algorithm 1 can be run in a computationally efficient manner. 
preliminaries: 
 We let △ X denote the set of distributions over set X , [H] := {1, 2, . . . , H}, and ∥P -Q∥ TV the total-variation distance between distributions P and Q.Markov Decision Processes. We consider the setting of episodic Markov Decision Processes (MDPs). An MDP is denoted by a tuple M = (S, A, {P h } H h=1 , {r h } H h=1 , s 1 , H), where S denotes the set of states, A the set of actions, P h : S × A → △ S the transition function, r h : S × A → [0, 1] the reward (which we assume is deterministic and known), s 1 the initial state, and H the horizon. We assume A is finite and denote A := |A|. Interaction with an MDP starts from state s 1 , the agent takes some action a 1 , transitions to state s 2 ∼ P 1 (• | s 1 , a 1 ), and receives reward r 1 (s 1 , a 1 ). This process continues for H steps at which points the episode terminates, and the process resets.The goal of the learner is to find a policy π = {π h } H h=1 , π h : S → △ A , that achieves maximum reward. We can quantify the reward received by some policy π in terms of the value and Q-value Formally, we make the following assumption on the structure of M sim and M real . Assumption 2. Both M sim and M real satisfy Definition 3.1 with feature maps and measures (ϕ s , µ s ) and (ϕ r , µ r ), respectively. Furthermore, ϕ s is known, but all of µ s , ϕ r , and µ r are unknown.In the literature, MDPs satisfying Definition 3.1 but where ϕ is known are typically referred to as "linear" MDPs, while MDPs satisfying Definition 3.1 but with ϕ unknown are typically referred to as "low-rank" MDPs. Given this terminology, we have that M sim is a linear MDP2 , while M real is a low-rank MDP. We assume the following reachability condition on M sim . Assumption 3. There ∃λ ⋆ min > 0 with min h sup π λ min (E M sim ,π [ϕ s (s h , a h )ϕ s (s h , a h ) ⊤ ]) ≥ λ ⋆ min . Assumption 3 posits that each direction in the feature space in our simulator can be activated by some policy, and can be thought of as a measure of how easily each direction can be reached. Similar assumptions have appeared before in the literature on linear and low-rank MDPs [71, 3, 2] . Note that we only require this reachability assumption in M sim . We also assume we are given access to function classes F h : S × A → [0, H] and let F := F 1 × F 2 × . . . × F H . Since no reward is collected in the (H + 1)th step we take f H+1 = 0. For any f : S × A → R, we let π f h (s) := arg max a∈A f h (s, a). We define the Bellman operator on some function f h+1 : S × A → R as:T f h+1 (s, a) := r h (s, a) + E s ′ ∼P h (•|s,a) [max a ′ f h+1 (s ′ , a ′ )].We make the following standard assumption on F. Assumption 4 (Bellman Completeness). For all f h+1 ∈ F h+1 , we have T real f h+1 , T sim f h+1 ∈ F h , where T real and T sim denote the Bellman operators on M real and M sim , respectively. PAC Reinforcement Learning. Our goal is to find a policy π that achieves maximum reward in M real . Formally, we consider the PAC (Probably-Approximately-Correct) RL setting. Definition 3.2 (PAC Reinforcement Learning). Given some ϵ > 0 and δ > 0, with probability at least 1 -δ identify some policy π such that:V real, π 0 ≥ V real,⋆ 0 -ϵ.We will be particularly interested in solving the PAC RL problem with the aid of a simulator, using the minimum number of samples from M real possible, as we will formalize in the following. As we will see, while it is straightforward to achieve this objective using M sim if ϵ = O(ϵ sim ), naive transfer methods can fail to achieve this completely if ϵ ≪ ϵ sim . As such, our primary focus will be on developing efficient sim2real methods in this regime. 
theoretical results: 
 In this section we provide our main theoretical results. We first present two negative results: in Section 4.1 showing that "naive exploration"-utilizing only a least-squares regression oracle and random exploration approaches such as ζ-greedy3 -is provably inefficient, and in Section 4.2 showing that directly transferring the optimal policy from M sim to M real is unable to efficiently obtain a policy with suboptimality better than O(ϵ sim ) in real. Then in Section 4.3 we present our main positive result, showing that by utilizing the same oracles as in Sections 4.1 and 4.2-a least-squares regression oracle, simulator access, and the ability to take actions randomly-we can efficiently learn an ϵ-optimal policy for ϵ ≪ ϵ sim in M real by carefully utilizing the simulator to learn exploration policies.While a variety of works have developed provably efficient methods for solving PAC RL in low-rank MDPs [1, 62, 43, 41] , these works typically either rely on complex computation oracles or carefully directed exploration strategies which are rarely utilized in practice. In contrast, RL methods utilized in practice typically rely on "simple" computation oracles and exploration strategies. Before considering the sim2real setting, we first show that such "simple" strategies are insufficient for efficient PAC RL. To instantiate such strategies, we consider a least-squares regression oracle, often available in practice. Oracle 4.1 (Least-Squares Regression Oracle). We assume access to a least-squares regression oracle such that, for any h and dataset D = {(s t , a t , y t )} T t=1 , we can computearg min f ∈F h T t=1 (f (s t , a t ) -y t ) 2 .We couple this oracle with "naive exploration", which here we use to refer to any method that explores by randomly perturbing the action recommended by the current estimate of the optimal policy. While a variety of instantiations of naive exploration exist (see e.g. [11] ), we consider a particularly common formulation, ζ-greedy exploration. Protocol 4.1 (ζ-Greedy Exploration). Given access to a regression oracle, any ζ ∈ [0, 1], and time horizon T , consider the following protocol:1. Interact with M real for T episodes. At every step of episode t + 1, play π f t h (s) with probability 1 -ζ, and a ∼ unif(A) otherwise, where:f t h = arg min f ∈F h t t ′ =1 (f (s t ′ h , a t ′ h ) -r t ′ h -max a ′ f t h+1 (s t ′ h+1 , a ′ )) 2 .2. Using collected data in any way desired, propose a policy π.Protocol 4.1 forms the backbone of many algorithms used in practice. Despite its common application, as existing work [11] and the following result show, it is provably inefficient. Proposition 1. For any H > 1, ζ ∈ [0, 1], and c ≤ 1/6, there exist some M real,1 and M real,2 such that both M real,1 and M real,2 satisfy Assumptions 2 and 4, and unless T ≥ Ω(2 H/2 ), when running Protocol 4.1 we have:sup M real ∈{M real,1 ,M real,2 } E M real [V M real ,⋆ 0 -V M real , π 0 ] ≥ c/32.Proposition 1 shows that, in a minimax sense, ζ-greedy exploration is insufficient for provably efficient reinforcement learning: on one of M real,1 and M real,2 , ζ-greedy exploration will only be able to find a policy that is suboptimal by a constant factor, unless we take an exponentially large number of samples. While we focus on ζ-greedy exploration in Proposition 1, this result extends to other types of naive exploration, for example, those given in [11] . See Section 5.2 for further discussion of the construction for Proposition 1.Proposition 1 shows that in general utilizing a least-squares regression oracle with ζ-greedy exploration is insufficient for provably efficient RL. Can this be made efficient with access to a simulator M sim ? In practice, standard sim2real methodology typically trains a policy to accomplish the goal task in M sim , and then transfers this policy to M real . We refer to this methodology as direct sim2real transfer. The following canonical result, usually referred to as the "simulation lemma" [24, 25, 6, 22] , provides a sufficient guarantee for direct sim2real transfer to succeed under Assumption 1. Proposition 2 (Simulation Lemma). Let π sim,⋆ denote an optimal policy in M sim . Then under Assumption 1 we haveV real,π sim,⋆ 0 ≥ V real,⋆ 0 -2H 2 ϵ sim .Proposition 2 shows that, as long as ϵ ≥ 2H 2 ϵ sim , direct sim2real transfer succeeds in obtaining an ϵ-optimal policy in M real . While this justifies direct sim2real transfer in settings where M sim and M real are sufficiently close, we next show that given access only to π sim,⋆ and a least-squares regression oracle-even when coupled with random exploration-we cannot hope to efficiently obtain a policy with suboptimality less than O(ϵ sim ) on M real using naive exploration. To formalize this, we consider the following interaction protocol. Protocol 4.2 (Direct sim2real Transfer with Naive Exploration). Given access to π sim,⋆ , an optimal policy in M sim , any ζ ∈ [0, 1], and time horizon T , consider the following protocol:1. Interact with M real for T episodes, and at each step h and state s play π sim,⋆ h (• | s) with probability 1 -ζ, and a ∼ unif(A) with probability ζ.2. Using collected data in any way desired, propose a policy π. Protocol 4.2 is a standard instantiation of direct sim2real transfer commonly found in the literature, and couples playing the optimal policy from M sim with naive exploration. We have the following. Proposition 3. With the same choice of M real,1 and M real,2 as in Proposition 1, there exists some M sim such that both M real,1 and M real,2 satisfy Assumption 1 with M sim for ϵ sim ← c, Assumptions 2 to 4 hold, and unless T ≥ Ω(2 H ) when running Protocol 4.2, we have:sup M real ∈{M real,1 ,M real,2 } E M real [V M real ,⋆ 0 -V M real , π 0 ] ≥ ϵ sim /32.Proposition 3 shows that there exists a setting where there are two possible M real satisfying Assumption 1 with M sim , and where, using direct policy transfer, unless we interact with M real for exponentially many episodes (in H), we cannot determine a better than Ω(ϵ sim )-optimal policy for the worst-case M real . Together, Propositions 2 and 3 show that, while we can utilize direct sim2real transfer to learn a policy that is O(ϵ sim )-optimal in M real , if our goal is to learn an ϵ-optimal policy for ϵ ≪ ϵ sim , direct sim2real transfer is unable to efficiently achieve this.Does there exist some way to utilize M sim and a least-squares regression oracle to enable efficient learning in M real , even when ϵ ≪ ϵ sim ? Our key insight is that, rather than transferring the policy that optimally solves the task in M sim , we should instead transfer policies that explore effectively in M sim . While learning to solve a task may require very precise actions, we can often obtain sufficiently rich data with relatively imprecise actions-it is easier to learn to explore than learn to solve a task. In such settings, directly transferring a policy to solve the task will likely fail due to imprecision in the simulator, but it may be possible to still transfer a policy that generates exploratory data. To formalize this, we consider the following access model to M sim . Oracle 4.2 (M sim Access). We may interact with M sim by either:1. (Trajectory Sampling) For any policy π, sampling a trajectory {(s h , a h , r h , s h+1 )} H h=1 generated by playing π on M sim . 
practical algorithm and experiments: 
 We next validate the effectiveness of our proposal in practice: can a set of diverse exploration policies obtained from simulation improve the efficiency of real-world reinforcement learning? We start by showing that this holds for a simple, didactic, tabular environment in Section 5.2. From here, we consider several more realistic task domains: simulators inspired by real-world robotic manipulation tasks (sim2sim transfer, Section 5.3); and an actual real-world sim2real experiment on a Franka robotic platform (sim2real transfer, Section 5.4). Further details on all experiments, including additional baselines, can be found in Appendix E. Before stating our experimental results, we first provide a practical instantiation of Algorithm 1 that we can apply with real robotic systems and neural network function approximators.The key idea behind Algorithm 1 is quite simple: learn a set of exploratory policies in M simpolicies which provide rich data coverage in M sim -and transfer these policies to M real , coupled with random exploration, using the collected data to determine a near-optimal policy for M real . Algorithm 1 provides a particular instantiation of this principle, learning exploratory policies in M sim via the LEARNEXPPOLICIES subroutine, which aims to cover the feature space of M sim , and utilizing a least-squares regression oracle to compute an optimal policy given the data collected in M real . In practice, however, other instantiations of this principle are possible by replacing LEARNEXPPOLICIES with any procedure which generates exploratory policies in M sim , and replacing the regression oracle with any RL algorithm able to learn from off-policy data. We consider a general meta-algorithm instantiating this in Algorithm 2.Algorithm 2 Practical sim2real Exploration Policy Transfer Meta-Algorithm Draw π exp ∼ unif(Π exp ), play in M real for one episode, add data to replay buffer of A po 5:Run A po for one episode // optional if Apo learns fully offlineIn practice, A exp and A po can be instantiated with a variety of algorithms. For example, we might take A exp to be an RND [7] or bootstrapped Q-learning-style [45, 31] algorithm, or any unsupervised RL procedure [48, 14, 32, 47] , and A po to be an off-policy policy optimization algorithm such as soft actor-critic (SAC) [16] or implicit Q-learning (IQL) [28] .For the following experiments, we instantiate Algorithm 2 by setting A exp to an algorithm inspired by recent work on inducing diverse behaviors in RL [14, 30] , and A po to SAC. In particular, A exp simultaneously trains an ensemble of policies . As shown in existing work [14, 30] , this simple training objective effectively induces diverse behavior with temporally correlated exploration while remaining within the vicinity of the optimal policy, using standard optimization techniques. Note that the particular choice of algorithm is less critical here than abiding by the recipes laid out in the meta-algorithm (Algorithm 2). The particular instantiation that we run for our experiments is detailed in Algorithm 6, along with further details in Appendix E.2.Π exp = {π i exp } n i=1 and a discriminator d θ : S × [n] → R,We first consider a variant of the construction used to prove Propositions 1 and 3, itself a variant of the classic combination lock instance. We illustrate this instance in Figure 2 . Unless noted, all transitions occur with probability 1, and rewards are 0. Here, in M sim the optimal policy, π sim,⋆ , plays action a 2 for all steps h < H -1, while in M real , the optimal policy plays action a 1 at every step. Which policy is optimal is determined by the outgoing transition from s 1 at the (H -1)th step and, as such, to identify the optimal policy, any algorithm must reach s 1 at the (H -1)th step. As s 1 will only be reached at step H -1 by playing a 1 for H -1 consecutive times, any algorithm relying on naive exploration will take exponentially long to identify the optimal policy. Furthermore, playing π sim,⋆ coupled with random exploration will similarly take an exponential number of episodes, since π sim,⋆ always plays a 2 . As such, both direct sim2real policy transfer as well as Q-learning with naive exploration (Protocol 4.1) will fail to find the optimal policy in M real . However, if we transfer exploratory policies from M sim , since M sim and M real behave identically up to step H -1, these policies can efficiently traverse M real , reach s 1 at step H -1, and identify the optimal policy. We compare our approach of exploration policy transfer to these baselines methods and illustrate the performance of each in Figure 2 . As this is a simple tabular instance, we implement Algorithm 1 directly here. As Figure 2 shows, the intuition described above leads to real gains in practice-exploration policy transfer quickly identifies the optimal policy, while more naive approach fail completely over the time horizon we considered. To test the ability of our proposed method to scale to more complex problems, we next experiment on a sim2sim transfer setting with a realistic robotic simulator. We consider TychoEnv, a simulator of the 7DOF Tycho robotics platform introduced by [73] , and shown in Figure 3 . We test sim2sim transfer on a reaching task where the goal is to touch a small ball hanging in the air with the tip of the chopstick end effector. The agent perceives the ball and its own end effector pose and outputs a delta in its desired end effector pose as a command. We set M sim and M real to be two instances of TychoEnv with slightly different parameters to model real-world sim2real transfer. Precisely, we change the action bounds and control frequency from M sim to M real . We aim to compare our approach of exploration policy transfer with direct sim2real policy transfer. To this end, we first train a policy in M sim that solves the task in M sim , π sim,⋆ , and then utilize this policy in place of Π exp in Algorithm 2. We instantiate our approach of exploration policy transfer as outlined above. Our aim in this experiment is to illustrate how the quality of the data provided by direct policy transfer vs. exploration policy transfer affects learning. As such, for both approaches we simply initialize our SAC agent in M real , A po , from scratch, and set the reward in M real to be sparse: the agent only receives a non-zero reward if it successfully touches the ball. For each approach, we repeat the process of training in M sim four times, and for each of these run them for two trials in M real . We illustrate our results in Figure 4 . As this figure illustrates, direct policy transfer fails to learn completely, while exploration policy transfer successfully solves the task. Investigating the behavior of each method, we find that the policies transferred via exploration policy transfer, while failing to solve the task with perfect accuracy, when coupled with naive exploration are able to successfully make contact with the ball on occasion. This provides sufficiently rich data for SAC to ultimately learn to solve the task. In contrast, direct policy transfer fails to collect any reward when run in M real , and, given the sparse reward nature of the task, SAC is unable to locate any reward and learn.We include an additional sim2sim experiment on the Franka Emika Panda Robot Arm in Appendix E.4.Finally, we demonstrate our algorithm for actual sim2real policy transfer for a manipulation task on a real-world Franka Emika Panda robot arm [17] with a parallel gripper. Our task is to push a 75mm diameter cylindrical "puck" from the center to the edge of the surface, as shown in Figure 1 , with the arm initialized at random locations. The observed state s = [p ee , p obj ] ∈ R 4 consists of the planar Cartesian coordinate of the end effector p ee along with the center of mass of the puck p obj . Our policy outputs planar end effector position deltas a = ∆p ee ∈ R 2 , evaluated at 8 Hz, which are passed into a lower-level joint position PID controller. We use an Intel Realsense D435 depth camera to track the location of the puck. Our reward function is a sum of a success indicator (indicating when the puck has been pushed to the edge of the surface) and terms which give negative reward if the distance from the end effector to the puck, or puck to the goal, are too large (see (E.1)); in particular, a reward greater than 0 indicates success.We run the instantiation of Algorithm 2 outlined above. In particular, we train an ensemble of n = 15 exploration policies, training for 20 million steps in M sim . In addition, we train a policy that solves the task in M sim , π sim,⋆ . We use a custom simulator of the arm, where during training the friction of the table is randomized and noise is added to the observations.We observe a substantial sim2real gap between our simulator and the real robot, with policies trained in simulation failing to complete the pushing task zero shot in real, even when trained with domain randomization. We compare direct sim2real policy transfer against our method of transferring exploration policies. For direct policy transfer, we simply run SAC to finetune π sim,⋆ in the real world, using the current policy to collect data. For exploration policy transfer, we instead utilize Π exp , our ensemble of exploration policies, to collect data in the real world. We run this in tandem with an SAC agent, feeding the data from the exploration policies into the SAC agent's replay buffer. Unlike in Section 5.3, rather than initializing the SAC policy from scratch, we set the initial policy as π sim,⋆ , and fine-tune from this on the data collected from playing Π exp . See Appendix E.5 for additional details.Our results are shown on the right side of Figure 1 . Statistics are computed over 6 runs for each method. Direct policy transfer with finetuning is unable to solve the task in real in each of the 6 runs, and converges to a suboptimal solution. However, our method is able to solve the task successfully each time and achieve a substantially higher reward. 
discussion: 
 In this work, we have demonstrated that simulators can make naive exploration efficient even in settings where direct sim2real transfer fails, if they are used to train a set of exploration policies. We highlight several limitations of this work, which we believe are interesting future research questions:• Our focus is purely on dynamics shift-where the dynamics of sim and real differ, but the environments are otherwise the same. While dynamics shift is common in many scenarios, other types of shift can exist as well, for example perceptual shift. How can we best handle these types of shift?• How can we utilize a simulator in sim2real transfer if we can reset it arbitrarily, rather than just allowing for black-box access? Does the ability to reset allow us to improve sample efficiency further?• Is the reachability condition, Assumption 3, necessary for successful exploration transfer?We denote the state-visitations for some policy π as w π h (s, a):= P π [(s h , a h ) = (s, a)], w π h (Z) := P π [(s h , a h ) ∈ Z], for Z ⊆ S × A. For X ⊆ R d , we denote w π h (X ) := P π [ϕ(s h , a h ) ∈ X ],for ϕ the featurization of the environment. Lemma A.1. Consider MDPs M and M with transition kernels P and P . Assume that both M and M start in the same state s 0 and that, for each (s, a, h):∥P h (• | s, a) -P h (• | s, a)∥ TV ≤ ϵ sim . (A.1)Consider some reward function r such thatH h=1 r h (s h , a h ) ≤ R for all possible sequences {(s h , a h )} H h=1 .Then it follows that, for any π and (s, a, h),|Q M,π h (s, a) -Q M ,π h (s, a)| ≤ HR • ϵ sim .Proof. We prove this by induction. First, assume that for some h and all s, a, we have|Q M,π h+1 (s, a) - Q M ,π h+1 (s, a)| ≤ ϵ h+1. By definition we haveQ M,π h (s, a) = r h (s, a) + E M,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a]and similarly for Q M ,π h+1 (s, a). Thus:|Q M,π h (s, a) -Q M ,π h (s, a)| (a) ≤ |E M,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a] -E M ,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a]| + E M ,π [|Q M,π h+1 (s h+1 , a h+1 ) -Q M ,π h+1 (s h+1 , a h+1 )| | s h = s, a h = a] (b) ≤ |E M,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a] -E M ,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a]| + ϵ h+1where (a) follows from the triangle inequality and (b) follows from the inductive hypothesis. Under (A.1), we can bound|E M,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a]-E M ,π [Q M,π h+1 (s h+1 , a h+1 ) | s h = s, a h = a]| ≤ ϵ sim •R.It follows that for any (s, a),|Q M,π h (s, a) -Q M ,π h (s, a)| ≤ ϵ h =: ϵ sim R + ϵ h+1 .The base case follows trivially with ϵ H = 0 since for any MDP we have thatQ M,π H (s, a) = r H (s, a) = Q M ,πH (s, a). Lemma A.2. Under the same setting as Lemma A.1 and for any h, π, and Z ⊆ S × A, we have|w M,π h (Z) -w M ,π h (Z)| ≤ Hϵ sim .Proof. This is an immediate consequence of Lemma A.1 since, setting the rewardr h ′ (s, a) = I{(s, a) ∈ Z, h ′ = h}, we can set R = 1 and have V M,π 0 = w M,π h (Z).Lemma A.3 (Proposition 2). Under Assumption 1, we have thatV real,⋆ 0 -V real,π sim,⋆ 0 ≤ 2H 2 ϵ sim and V sim,⋆ 0 -V sim,π real,⋆ 0 ≤ 2H 2 ϵ sim .Proof. We prove the result for real-the result for sim follows analogously. We haveV real,⋆ 0 -V real,π sim,⋆ 0 = V real,π real,⋆ 0 -V sim,π real,⋆ 0 + V sim,π real,⋆ 0 -V sim,π sim,⋆ 0 ≤0 +V sim,π sim,⋆ 0 -V real,π sim,⋆ 0 ≤ |V real,π real,⋆ 0 -V sim,π real,⋆ 0 | + |V sim,π sim,⋆ 0 -V real,π sim,⋆ 0 |.The result then follows by applying Lemma A.1 to bound each of these terms by H 2 ϵ sim .Lemma A.4. For any f ∈ F,V ⋆ 0 -V π f 0 ≤ max π∈{π f ,π ⋆ } H-1 h=0 2 |E π [f h (s h , a h ) -T f h+1 (s h , a h )]| .Proof. We writeEQUATION+ maxa f 0 (s 0 , a) -V π f 0 (b)and then bound each of these terms separately. By Lemma 5 of [57] we have(a) ≤ H h=0 E π ⋆ [f h (s h , a h ) -r h -max a ′ f h+1 (s h+1 , a ′ )] = H-1 h=0 E π ⋆ [f h (s h , a h ) -E[r h + max a ′ f h+1 (s h+1 , a ′ ) | s h , a h ]] .Similarly, by Lemma 4 of [57] we have(b) ≤ H-1 h=0 E π f [f h (s h , a h ) -r h -max a ′ f h+1 (s h+1 , a ′ )] = H-1 h=0 E π f [f h (s h , a h ) -E[r h + max a ′ f h+1 (s h+1 , a ′ ) | s h , a h ]] .In Appendix B.1 we first provide a general result on learning in real when collecting data via a fixed set of exploration policies, given a particular coverage assumption. Then in Appendix B.2, we show that by playing a set of policies which induce full-rank covariates in sim, these policies provide sufficient coverage for learning in real. Finally in Appendices B.3 and B.4, we use these results to prove Theorems 1 and 3. Throughout the appendix we develop the supporting lemmas for our more general result, Theorem 3, which utilizes the simulator to restrict the version space (i.e. the dependence on |F|) in addition to utilizing the simulator to aid in exploration.Throughout this and the following section we assume that Assumption 4 holds. We also assume thatf h ∈ [0, V max ] instead of f h ∈ [0, H],for some V max > 0. For any f ∈ F, we denote the Bellman residual asE h (f )(s, a) := T f h+1 (s, a) -f h (s, a).Note that by assumption on F, we haveE h (f )(s, a) ∈ [-V max , V max ].For any policy π, we denote Λ s π,h:= E sim,π [ϕ s (s h , a h )ϕ s (s h , a h ) ⊤ ] and Λ r π,h := E real,π [ϕ r (s h , a h )ϕ r (s h , a h ) ⊤ ].Necessity of Random Exploration. Algorithm 1 achieves efficient exploration in M real by first learning a set of policies Π h exp in M sim that span the feature space of M sim (Line 2), achievingλ min 1 |Π h exp | π∈Π h exp E M sim ,π [ϕ s (s h , a h )ϕ s (s h , a h ) ⊤ ] ≳ λ ⋆ min , (B.1)and then playing these policies in M real , coupled with random exploration (Line 4). In particular, Algorithm 1 plays policies from Π h exp , where each π exp ∈ Π h exp is defined as the policy which plays some π exp ∈ Π h exp up to step h, and then for steps h ′ = h + 1, . . . , H chooses actions uniformly at random. This use of random exploration is critical to obtaining Theorem 1. Indeed, under our transfer model, condition (4.1) of Theorem 1 is not strong enough to ensure that policies satisfying (B.1) collect rich enough data in M real to allow for learning a near-optimal policy. While (4.1) is sufficient to guarantee that playing Π h exp on M real collects data which spans the feature space of M sim -that is, satisfying (B.1) but with the expectation over M sim replaced by an expectation of M real -this is insufficient for learning, as the following result shows. Proposition 5. For any ϵ sim ≤ 1/2, there exist some M sim , M real,1 , and M real,2 such that:1. Both M real,1 and M real,2 satisfy Assumption 1 with M sim and Assumptions 2 to 4 hold.2. There exists some policy π exp such thatλ min (E M sim ,πexp [ϕ s (s h , a h )ϕ s (s h , a h ) ⊤ ]) = 1/2, ∀h ∈ [H],and for any T ≥ 0, if we play π exp on M real for T steps, we have:inf π sup M real ∈{M real,1 ,M real,2 } E M real ,πexp [V M real ,⋆ 0 -V M real , π 0 ] ≥ ϵ sim .Proposition 5 holds because two MDPs may be "close" in the sense of Assumption 1 but admit very different feature representations. As a result, transferring a policy that covers the feature space of M sim is not necessarily sufficient for covering the feature space of M real , which ultimately means that data collected from π exp is unable to identify the optimal policy in M real . Our key technical result, Lemma B. f h ← arg min f ∈F (s,a,r,s ′ )∈D h sim (f h (s, a) -r -max a ′ f h+1 (s ′ , a ′ )) 2 f h ← arg min f ∈F (s,a,r,s ′ )∈D h (f h (s, a) -r -max a ′ f h+1 (s ′ , a ′ )) 2 s.t. 1 |D sim | (s,a)∈D h sim (f h (s, a) -f h (s, a)) 2 ≤ γ (B.2V 2 max ϵ 2 sim + 43V 2 max β 2 dH • log 8H|F h | δ + 6V 2 max β log 8H|F h | δ dH ≤ γ.Furthermore, assume that there exists some C, ϵ > 0 such that, for any π, h ∈ [H], and Z ′ ⊆ S × A, we have:w real,π h (Z ′ ) ≤ C • w real,πexp h (Z ′ ) + ϵ. (B.3)Then with probability at least 1 -2δ, the policy π f generated by Algorithm 3 satisfiesV ⋆ 0 -V π f 0 ≤ 4CH 256V 2 max log(4H| F(π sim exp )|/δ) T + 4HV max ϵ for F(π sim exp ) := {f ∈ F : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 2γ, ∀h ∈ [H]}.Proof. Let E denote the good event of Lemma B.2, which holds with probability at least 1 -2δ. By Lemma A.4 we haveV real,⋆ 0 -V real,π f 0 ≤ max π∈{π f ,π real,⋆ } H-1 h=0 2 E real,π [ f h (s h , a h ) -T real f h+1 (s h , a h )] ≤ max π H-1 h=0 2E real,π [|E real h ( f )(s h , a h )|]. Let Z h,i := {(s, a) : |E real h ( f )(s, a)| ∈ [V max • 2 -i , V max • 2 -i+1)}. Then we have, for any π,E real,π [|E real h ( f )(s h , a h )|] ≤ ∞ i=1 w real,π h (Z h,i ) • V max 2 -i+1 ≤ C • ∞ i=1 w real,πexp h (Z h,i ) • V max 2 -i+1 + 2V max ϵ ≤ 2C • E real,πexp [|E real h ( f )(s h , a h )|] + 2V max ϵwhere the second inequality follows from (B.3). On E, by Lemma B.2 and Jensen's inequality, we haveE real,πexp [|E real h ( f )(s h , a h )|] ≤ E real,πexp [E real h ( f )(s h , a h ) 2 ] ≤ 1 T • 256V 2 max log 2H| F h (π sim exp )| δ .As this holds for each h and π, we have therefore shown thatV real,⋆ 0 -V real,π f 0 ≤ 4C • H-1 h=0 1 T • 256V 2 max log 2H| F h (π sim exp )| δ + 4HV max ϵ ≤ 4CH 1 T • 256V 2 max log 2H| F(π sim exp )| δ + 4HV max ϵ.This proves the result.Lemma B.2. With probability at least 1 -2δ, for each h ∈ [H] simultaneously, as long as the conditions on γ given in Lemma B.3 hold, we haveE real,πexp [( f h (s h , a h ) -T real f h+1 (s h , a h )) 2 ] ≤ 1 T • 256V 2 max log(2H| F h (π sim exp )|/δ),andf h ∈ F h (π sim exp ) for all h ∈ [H],whereF h (π sim exp ) := {f h ∈ F h : ∃f h+1 ∈ F h+1 s.t. E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 2γ}.Proof. Let F h denote the feasible set of (B.2) at step h. By Lemma B.3, with probability at least 1 -δ, F t h ⊆ F h , and, furthermore, that T real f h+1 is feasible. The result then follows from Lemma 3 of [57] , since the constraint on the regression problem restricts the version space.Lemma B.3. Assume that data in D sim is generated as in Assumption 5 via the procedure of Lemma C.3 run with some parameter β, and γ satisfies2V 2 max ϵ 2 sim + 43V 2 max β 2 dH • log 8H|F h | δ + 6V 2 max β log 8H|F h | δ dH ≤ γ.Then with probability at least 1 -δ we have, for each h ∈ [H]:1. T real f h+1 is feasible for (B.2).2. The set of feasible f for (B.2) is a subset of{f ∈ F : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 2γ}.Proof. By Lemma C.1, we have that with probability at least 1 -δ/2H,1 T sim T sim t=1 (T real f h+1 ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ 2V 2 max ϵ 2 sim + 512V 2 max T sim • log 8H|F h | δ + V 2 max 2 log 4H|F h | δ T sim .By Lemma C.3, we have 12dH β 2 ≤ T sim , which implies1 T sim T sim t=1 (T real f h+1 ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ 2V 2 max ϵ 2 sim + 43V 2 max β 2 dH • log 8H|F h | δ + V 2 max β log 4H|F h | δ 6dH .Part 1 then follows given our assumption on γ.To bound the feasible set for (B.2) we appeal to Lemma C.2 which states that with probability at least 1 -δ/2H we have that the feasible set of (B.2) is a subset of   f h ∈ F h : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ + 18V 2 max log 8H|F h | δ T sim    .Again using that 12dH β 2 ≤ T sim , we have have that this is a subset of   f h ∈ F h : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ + 18V 2 max β log 8H|F h | δ 12dH    ⊆ f h ∈ F h : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 2γwhere the inclusion follows from our assumption on γ. The result then follows from a union bound. λ min Λ s π h exp ,h ≥ λmin , ∀h ∈ [H] (B.4)and that π h exp plays actions uniformly at random for h ′ > h. Let π exp = unif({π h exp } H h=1 ). Then, for any π, κ > 0, γ > 0, h ∈ [H], and Z ′ ⊆ S × A, we havew real,π h (Z ′ ) ≤ 4HγA k ⋆ -2 κ • w real,πexp h (Z ′ ) + 4κ,whereξ := 2 A λmin d γ + Hϵ sim and k ⋆ := ⌈ log 1/κ log 1/ξ ⌉.Proof. DenoteZ h+1 := {(s, a) : ϕ r (s, a) ⊤ (Λ r π h exp ,h+1) -1 ϕ r (s, a) > γ} for some γ > 0. We havew real,π h exp h+1 ( Z h+1 ) = E real,π h exp [I{(s h+1 , a h+1 ) ∈ Z h+1 }] (a) ≤ E real,π h exp ϕ r (s h+1 , a h+1 ) ⊤ (Λ r π h exp ,h+1 ) -1 ϕ r (s h+1 , a h+1 ) γ • I{(s h+1 , a h+1 ) ∈ Z h+1 } ≤ E real,π h exp ϕ r (s h+1 , a h+1 ) ⊤ (Λ r π h exp ,h+1 ) -1 ϕ r (s h+1 , a h+1 ) γ = 1 γ • tr E real,π h exp [ϕ r (s h+1 , a h+1 )ϕ r (s h+1 , a h+1 ) ⊤ ](Λ r π h exp ,h+1 ) -1 = d γwhere (a) follows since for all (s, a) ∈ Z h+1 , we have 1 < ϕ r (s, a) ⊤ (Λ r π h exp ,h+1 ) -1 ϕ r (s,( Z h+1 ) = E sim,π h exp   S h+1 a:(s,a)∈ Z h+1 π h exp (a | s, h + 1)dP sim h (s | s h , a h )   ≥ 1 A E sim,π h exp S h+1 dµ s h (s) ⊤ ϕ s (s h , a h ) = 1 A E sim,π h exp [P sim h ( S h+1 | s h , a h )] ≥ 1 A E sim,π h exp [P sim h ( S h+1 | s h , a h ) 2 ]where we have used the fact that π h exp (a | s, h + 1) = 1/A for all (s, a) by assumption, and defineP sim h ( S h+1 | s, a) := P sim [s h+1 ∈ S h+1 | s h = s, a h = a] = S h+1 dµ s h (s) ⊤ ϕ s (s, a), where the last equality follows from the definition of a linear MDP. Letting µ s h ( S h+1 ) := S h+1 dµ s h (s), note that:1 A E sim,π h exp [P sim h ( S h+1 | s h , a h ) 2 ] = 1 A µ s h ( S h+1 ) ⊤ E sim,π h exp [ϕ s (s h , a h )ϕ s (s h , a h ) ⊤ ]µ s h ( S h+1 ) = 1 A µ s h ( S h+1 ) ⊤ Λ s π h exp ,h µ s h ( S h+1 ) ≥ λmin A ∥µ s h ( S h+1 )∥ 2 2 ,where the last inequality follows from (B.4). Combining this with (B.5), we haved γ + Hϵ sim ≥ λmin A ∥µ s h ( S h+1 )∥ 2 2 .Now note that, for any z ∈ S × A:P sim h ( S h+1 | z) = S h+1 dP sim h (s | z) = S h+1 dµ s h (s) ⊤ ϕ s (z) ≤ ∥µ s h ( S h+1 )∥ 2and we also have thatP sim h ( S h+1 | z) ≥ P real h ( S h+1 | z) -ϵ sim under Assumption 1.Putting this together we have that for all z ∈ S × A:P real h ( S h+1 | z) ≤ A λmin d γ + Hϵ sim + ϵ sim .Note that we can always take ϵ sim ≤ 1, and will always have λmin ≤ 1. This implies that ϵ sim ≤ A λmin d γ + Hϵ sim . Thus,P real h ( S h+1 | z) ≤ 2 A λmin d γ + Hϵ sim =: ξ. Coverage of π exp in real. Let k ⋆ := ⌈ log 1/κ log 1/ξ ⌉, so that ξ k ⋆ ≤ κ. Let Zh := (S × A)\ Z h . Fix some Z ′ ⊆ (S × A), h ∈ [H],and policy π.Consider some z ∈ Zh , and some S ′ ⊆ S. Then note that 5P real h (S ′ | z) = µ r h (S ′ ) ⊤ ϕ r (z) = µ r h (S ′ ) ⊤ (Λ r π h-1 exp ,h ) 1/2 (Λ r π h-1 exp ,h ) -1/2 ϕ r (z) ≤ ∥µ r h (S ′ )∥ Λ r π h-1 exp ,h ∥ϕ r (z)∥ (Λ r π h-1 exp ,h ) -1 ≤ √ γ∥µ r h (S ′ )∥ Λ r π h-1 exp ,hwhere the last inequality follows from the definition of Zh . Note, though, that∥µ r h (S ′ )∥ 2 Λ r π h-1 exp ,h = E real,π h-1 exp [(µ r h (S ′ ) ⊤ ϕ r (z h )) 2 ] = E real,π h-1 exp [P real h (S ′ | z h ) 2 ].This implies that for all z ∈ Zh ,E real,π h-1 exp [P real h (S ′ | z h ) 2 ] ≥ 1 γ • P real h (S ′ | z) 2 .For h ′ < h, defineS h ′ ,i := {s : w real,π h (Z ′ | s h ′ = s) ∈ [2 -i+1 , 2 -i )} for w real,π h (Z | s h ′ = s) := P real,π [z h ∈ Z | s h ′ = s]. Note that we then have w real,π h (Z ′ | S h ′ ,i ) ∈ [2 -i+1 , 2 -i ). By what we have just shown, we have that forz ∈ Zh ′ E real,π h ′ -1 exp [P real h ′ (S h ′ +1,i | z h ′ ) 2 ] ≥ 1 γ • P real h ′ (S h ′ +1,i | z) 2which implies thatE real,π h ′ -1 exp [P real h ′ (S h ′ +1,i | z h ′ )] ≥ 1 γ • P real h ′ (S h ′ +1,i | z) 2 . (B.6) 5 If Λ r π h-1exp ,h is not invertible, we can repeat this argument with Λ r π h-1 exp ,h + λI and take λ → 0.Fix z ∈ Zh ′ . Note thatw real,π h (Z ′ | z h ′ = z) = E s∼P real h ′ (•|z) [w real,π h (Z ′ | s h ′ +1 = s)] = ∞ i=1 E s∼P real h ′ (•|z) [w real,π h (Z ′ | s h ′ +1 = s) • I{s ∈ S h ′ +1,i }] ≤ ∞ i=1 2 -i+1 P real h ′ (S h ′ +1,i | z) = ⌊log 4/κ⌋ i=1 2 -i+1 P real h ′ (S h ′ +1,i | z) + κ ≤ ⌊log 4/κ⌋ i=1 2 -i+1 P real h ′ (S h ′ +1,i | z) • I{P real h ′ (S h ′ +1,i | z) ≥ κ} + 3κ ≤ 2 ⌊log 4/κ⌋ i=1 E s∼λi [w real,π h (Z ′ | s h ′ +1 = s)]P real h ′ (S h ′ +1,i | z) • I{P real h ′ (S h ′ +1,i | z) ≥ κ} + 3κfor any λ i ∈ △ S h ′ +1,i . Note also that, since π h ′ -1 exp plays randomly for all h ′′ ≥ h ′ , we have:w real,π h ′ -1 exp h (Z ′ | s h ′ +1 = s) ≥ 1 A h-h ′ • w real,π h (Z ′ | s h ′ +1 = s),since with probability 1/A h-h ′ on any given episode, π h ′ -1 exp will play the same sequence of actions as π from steps h ′ to h. It follows that we can bound the above as:≤ 2A h-h ′ • ⌊log 4/κ⌋ i=1 E s∼λi [w real,π h ′ -1 exp h (Z ′ | s h ′ +1 = s)]P real h ′ (S h ′ +1,i | z) • I{P real h ′ (S h ′ +1,i | z) ≥ κ} + 3κ (a) ≤ 2A h-h ′ γ κ • ⌊log 4/κ⌋ i=1 E s∼λi [w real,π h ′ -1 exp h (Z ′ | s h ′ +1 = s)]E real,π h ′ -1 exp [P real h ′ (S h ′ +1,i | z h ′ )]I{P real h ′ (S h ′ +1,i | z) ≥ κ} + 3κ ≤ 2γA h-h ′ κ • ⌊log 4/κ⌋ i=1 E s∼λi [w real,π h ′ -1 exp h (Z ′ | s h ′ +1 = s)] • w real,π h ′ -1 exp h ′ +1 (S h ′ +1,i ) + 3κ (b) = 2γA h-h ′ κ • ⌊log 4/κ⌋ i=1 s∈S h ′ +1,i w real,π h ′ -1 exp h (Z ′ | s h ′ +1 = s)w real,π h ′ -1 exp h ′ +1 (s) + 3κ ≤ 2γA h-h ′ κ • w real,π h ′ -1 exp h (Z ′ ) + 3κwhere (a) follows from (B.6) and sinceP real h ′ (S h ′ ,i | z) ≥ κ, and (b) follows choosing λ i (s) = w real,π h ′ -1 exp h ′ +1 (s)/w real,π h ′ -1 exp h ′ +1 (S h ′ +1,i ) • I{s ∈ S h ′ +1,i }.We therefore have that, for all z ∈ Zh ′ :w real,π h (Z ′ | z h ′ = z) ≤ 2γA h-h ′ κ • w real,π h ′ -1 exp h (Z ′ ) + 3κ. (B.7)Controlling events. Consider events E := {z h ∈ Z ′ } and E h ′ := {z h ′ ∈ Zh ′ }. We then havew real,π h (Z ′ ) = P real,π [E] = P real,π [E ∩ E h-1 ] + P real,π [E ∩ E c h-1 ] = h h ′ =h-k ⋆ +1 P real,π [E ∩ E h ′ -1 ∩ h-1 i=h ′ E c i ] + P real,π [E ∩ E h-k ⋆ -1 ∩ h-1 i=h-k ⋆ E c i ] ≤ h h ′ =h-k ⋆ +1 P real,π [E ∩ E h ′ -1 ] + P real,π [E ∩ E h-k ⋆ -1 ∩ h-1 i=h-k ⋆ E c i ].We now analyze each of these terms. First, note thatP real,π [E ∩ E h ′ -1 ] = P real,π [E | E h ′ -1 ]P real,π [E h ′ -1 ] ≤ P real,π [E | E h ′ -1 ] = w real,π h (Z ′ | z h ′ -1 ∈ Zh ′ -1 ).We can then boundw real,π h (Z ′ | z h ′ -1 ∈ Zh ′ -1 ) ≤ 2γA h-h ′ -1 κ • w real,π h ′ -2 exp h (Z ′ ) + 3κwhere the inequality follows from (B.7). For the second term, we haveP real,π [E ∩ E h-k ⋆ -1 ∩ h-1 i=h-k ⋆ E c i ] ≤ P real,π [E ∩ h-1 i=h-k ⋆ E c i ] = P real,π [E | h-1 i=h-k ⋆ E c i ] • k ⋆ j=1 P real,π [E c h-j | h-j-1 i=h-k ⋆ E c i ].Note, however, thatP real,π [E | h-1 i=h-k ⋆ E c i ] ≤ ξ and P real,π [E c h-j | h-j-1 i=h-k ⋆ E c i ]≤ ξ for all j. We therefore can bound the above asξ k ⋆ +1 ≤ κ.Altogether, then, we have thatw real,π h (Z ′ ) ≤ h h ′ =h-k ⋆ +1 2γA h-h ′ -1 κ • w real,π h ′ -2 exp h (Z ′ ) + 4κ. Furthermore, since π exp = unif({π h exp } H h=1 ), we have w real,π h ′ -2 exp h (Z ′ ) ≤ Hw real,πexp h (Z ′ ), so we conclude that w real,π h (Z ′ ) ≤ 4HγA k ⋆ -2 κ • w real,πexp h (Z ′ ) + 4κ.Theorem 2. Assume that one of the two conditions is met:1. For each h, π h exp plays actions uniformly at random for h ′ > h,λ min Λ s π h exp ,h ≥ λmin , (B.8)andT ≥ c • V 4 max H 4 d 2 A 2(k ⋆ -2) log(2H|F|/δ) ϵ 4 ϵ 2 sim , for k ⋆ = ⌈ log A 64HVmax ϵ log A 1/ξ ⌉, ξ = 2 2HA λmin • ϵ sim . 2. ϵ sim ≤ ϵ/4H 2 and T ≥ 16H 2 log 4 δ ϵ 2 .Then with probability at least 1 -δ, Algorithm 1 returns a π such that V real,π real,⋆ 0 -V real, π 0 ≤ ϵ.Proof. We consider each of the conditions above.Condition 1. First, note that by our assumption on π exp and applying Lemma B.4 with κ = ϵ 64HVmax and γ = d Hϵsim , for any π and Z ′ ⊆ S × A, we havew real,π h (Z ′ ) ≤ 256dHV max A k ⋆ -2 ϵϵ sim • w real,πexp h (Z ′ ) + ϵ 16HV max for k ⋆ = ⌈ log A 64HVmax ϵ log A 1/ξ ⌉, ξ = 2 2HA λmin • ϵ sim .By Lemma B.1 we then have that, with probability at least 1 -δ6 ,V real,π real,⋆ 0 -V real, π 0 ≤ 256dHV max A k ⋆ -2 ϵϵ sim • 4H 256V 2 max log(2H|F|/δ) T + ϵ/4 ≤ ϵ/2where the last inequality follows under our condition on T .Condition 2. By Lemma A.3, we have thatV real,⋆ 0 -V real,π sim,⋆ 0 ≤ 2H 2 ϵ sim . Thus, if ϵ sim ≤ ϵ/4H 2 , we have V real,⋆ 0 -V real,π sim,⋆ 0 ≤ ϵ/2.. By what we have shown, as long as one of our conditions is met, we will have that with probability at least 1 -δ/2, there exists π ∈ {π f , π sim,⋆ } such that V real,⋆ 0 -V real,π 0 ≤ ϵ/2. Denote this policy as π.Note that V real,π 0 = E real,π [ H-1 h=0 r h ] and that H-1 h=0 r h ∈ [0, H]almost surely. Consider playing π for T /4 episodes in real and let R i denote the total return of the ith episode. LetV π 0 := 4 T T /4 i=1 R i .By Hoeffding's inequality we have that, with probability at least 1 -δ/4:| V π 0 -V real,π 0 | ≤ H 4 log 4 δ T .Thus, ifT ≥ 16H 2 log 4 δ ϵ 2 , (B.9) we have that | V π 0 -V real,π 0 | ≤ ϵ/2.Union bounding over this for both π ∈ {π f , π sim,⋆ }, we have that with probability at least 1 -δ/2:V real, π 0 ≥ V π 0 -ϵ/4 ≥ V π 0 -ϵ/4 ≥ V real, π 0 -ϵ/2.It follows thatV real,⋆ -V real, π 0 ≤ V real,⋆ -V real, π 0 + ϵ/2 ≤ ϵ.The proof follows from a union bound and our condition on T (note that (B.9) is satisfied in both cases).Proof of Theorem 1. We first assume that ζ ≤ A k ⋆ -2 ≤ A log A 64HVmax/ϵ log A 1/ξ = 64HV max ϵ 1/ log A 1/ξ .It then suffices that we show 1/ log A 1/ξ ≤ 1 ⇐⇒ 1/A ≥ ξ. However, this is clearly met by our condition on ϵ sim . Thus, as long asT ≥ c • V 6 max H 6 d 2 log(2HT |F|/δ) ϵ 6 ϵ 2 sim ,by Theorem 2 we have that π is ϵ-optimal. Now, if ϵ sim ≤ ϵ/4H 2 and T ≥ 16H 2 log 4/δ ϵ , we also have that π is ϵ-optimal, by Theorem 2. Thus, in the first case, we at most will requireT ≥ c • V 6 max H 10 d 2 log(2HT |F|/δ) ϵ 8to produce a policy that is ϵ-optimal, since otherwise we will be in the second case.It remains to justify the assumption that ζ ≤ λ ⋆ min 4d . Note that the condition of (4.1) is only required in the first case. Furthermore, if ϵ sim ≤ ϵ/4H 2 we will be in the second case. Thus, in the first case, we will haveϵ 4H 2 ≤ ϵ sim ≤ λ ⋆ min 64dHA 3 .Rearranging this we obtain that, to be in the first case, we have As we noted, in general, given that we do not assume that ϕ r is unknown, log |F| could be significantly greater than the dimension. One might hope that, given access to M sim , we can reduce this dependence somewhat. We next show that this is possible given access to the following constrained regression oracle.). We assume access to a regression oracle such that, for any h and datasets {(s t , a t , y t )} T t=1 and {( s t , a t , y t )} T t=1 , we can compute:f h = arg min f ∈F h T t=1 (f (s t , a t ) -y t ) 2 s.t. T t=1 (f ( s t , a t ) -y t ) 2 ≤ γ.While in general the oracle of Oracle B.1 cannot be reduced to the oracle of Oracle 4.1, under certain conditions on F this is possible. Given this oracle, we have the following result.Theorem 3. Assume that ϵ sim ≤ λ ⋆ min 64dHA 3 . Then if T ≥ O d 2 H 16 ϵ 8 • log H| F| δ ,with probability at least 1 -δ, Algorithm 4 returns policy π such that V real,π real,⋆ 0 -V real, π 0 ≤ ϵ, whereF := f ∈ F : sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )]) 2 ≤ α • ϵ 2 sim for α = O(AdH 3 •log 2 log |F |/δ ϵsim ). Furthermore, the computation oracles of Oracle 4.2 and Oracle B.1 are called at most poly(d, A, H, ϵ -1 , log |F | δ ) times. Theorem 3 shows that, rather than paying for the full complexity of F, we can pay only for the subset of F that is Bellman-consistent on M sim .Algorithm 4 sim-to-real transfer via simulated exploration (SIM2EXPLORE)1: input: tolerance ϵ, confidence δ, budget T , Q-value function class F 2: Π h exp ← LEARNEXPPOLICIES(M sim , δ, 4A 3 ϵ H , h) for all h ∈ [H] 3: ι ← O(log 2 VmaxAdH ϵ ) 4: for ℓ = 1, 2, . . . , ι do 5: εℓ ← 2 -ℓ , T ℓ ← T /2ι, γ ℓ ← 10V 2 max (ε ℓ ) 2 6:Run exploration procedure of Lemma C.3 withβ ℓ ← γ ℓ 20V 2 max log 8H|F | δ to obtain D ℓ sim 7: π ℓ ← EXPLOREREAL ({unif(Π h exp )} h∈[H] , T ℓ , D ℓ sim , γ ℓ ) (Algorithm 3) 8:V π ℓ 0 ← average return running π ℓ in real T ℓ /2 times 9: return π ← arg max ℓ∈[ι] V π ℓ 0 Theorem 4. Assume that one of the two conditions is met:1. For each h, π h exp plays actions uniformly at random for h ′ > h,λ min Λ s π h exp ,h ≥ λmin , (B.10)andEQUATIONF := f ∈ F : sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )]) 2 ≤ c log log 32H|F | δ V max ϵ 2 sim + 1 AdHV 2 max log 48d log 32H|F | δ V max ϵ 2 sim • ϵ 2 sim . 2. ϵ sim ≤ ϵ/16H 2 and T ≥ c • H 2 ι log 16ι δ ϵ 2 .Then with probability at least 1 -δ, Algorithm 4 returns a policy π such that V real,π real,⋆ 0 -V real, π 0 ≤ ϵ.Proof. We break the proof into two cases.Case 1: ϵ sim ≥ ϵ/16H 2 . Let l = ⌊log 2 -1 sim ⌋ and note that l ≤ ι in this case and that this is a deterministic quantity. Further, note that γ l ∈ [10V Hϵsim , for any π and Z ′ ⊆ S × A, we havew real,π h (Z ′ ) ≤ 256dHV max A k ⋆ -2 ϵϵ sim • w real,πexp h (Z ′ ) + ϵ 16HV max for k ⋆ = ⌈ log A 64HVmax ϵ log A 1/ξ ⌉, ξ = 2 2HA λmin • ϵ sim .By Lemma B.1, as long as β l and γ l satisfy2V 2 max ϵ 2 sim + 43V 2 max β 2 l dH • log 8H|F h | δ + 6V 2 max βl log 8H|F h | δ dH ≤ γ l, (B.11)we have that with probability at least 1 -2δ,V real,π real,⋆ 0 -V real, π l 0 ≤ 256dHV max A k ⋆ -2 ϵϵ sim • 4H 256V 2 max log(4H| F l|/δ) T ℓ + ϵ/4whereF l := {f ∈ F : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 2γ l, ∀h ∈ [H]}.However, since V 2 max ϵ sim ≤ 1 10 γ l, and by our choice ofβ l = γ l 20V 2 max log 8H|F | δ, we see that (B.11) is met, so the conclusion holds. Note that, by Lemma C.5, we have that with probability at least 1 -δ:F l ⊆ f ∈ F : sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )]) 2 ≤ 4 log 1 βl + 6 A • 48dH log 48d β 2 l • 2γ l + V 2 max 96dH log 48d β 2 l log 1 δ • βl ⊆ f ∈ F : sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )]) 2 ≤ c log log 8H|F | δ V max ϵ 2 sim + 1 AdHV 2 max log 48d log 8H|F | δ V max ϵ 2 sim • ϵ 2 sim =: Fwhere the second inclusion follows from our setting of βl, and bounds on γ l.Since T ℓ ← T /2ι, it follows that ifT ≥ c • d 2 H 4 V 4 max A 2(k ⋆ -2) ι log(4H| F|/δ) ϵ 4 ϵ 2 sim , then we have that V real,π real,⋆ 0 -V real, π l 0 ≤ ϵ/2.Case 2: ϵ sim ≤ ϵ/16H 2 . By Lemma B.5 and our choice of T ℓ sim , we have that with probability at least 1 -δ,V real,⋆ 0 -V real, π ι 0 ≤ 6H 2 log 20V 2 max log 8H|F | δ γ ι + 3 • 192AdH log 960dV 2 max log 8H|F | δ γ ι • γ ι + 4H 2 ϵ sim .By our choice of ι = O(log 2) and sinceγ ι = 10V 2 max (ε ι ) 2 = 10V 2 max • 2 -2ι , we can bound V real,⋆ 0 -V real, π ι 0 ≤ ϵ/2.Completing the Proof. In either case, we have that with probability at least 1 -δ, there exists somei ∈ [ι] such that V 0 -V real, π i 0 ≤ ϵ/2. Note that V real,π 0 = E real,π [ H-1 h=0 r h ] and that H-1 h=0 r h ∈ [0, H]almost surely. Consider playing π for n episodes in real and let R i denote the total return of the ith episode. LetV π 0 := 1 n n i=1 R i .By Hoeffding's inequality we have that, with probability at least 1 -δ/ι:| V π 0 -V real,π 0 | ≤ H log 2ι δ n . Thus, if n ≥ 16H 2 log 2ι δ ϵ 2 , we have that | V π 0 -V real,π 0 | ≤ ϵ/2.However, as we run each π ∈ Π ℓ T ℓ /2 = T /2ι times, and in either case we assume T ≥ cιH 2 ϵ 2 • log 4ι δ , this will be met. Union bounding over this for all π ℓ , we have that with probability at least 1 -δ:V real, π 0 ≥ V π 0 -ϵ/4 ≥ V π i 0 -ϵ/4 ≥ V real, π i 0 -ϵ/2.It follows thatV real,⋆ -V real, π 0 ≤ V real,⋆ -V real, π i 0 + ϵ/2 ≤ ϵ.The result then follows from a union bound and rescaling δ.Proof of Theorem 3. The argument follows analogously to the proof of Theorem 1, but using Theorem 4 in place of Theorem 2. The bound on the number of oracle calls follows from Lemma C.3 and our choice of β ℓ .Lemma B.5. With probability at least 1 -δ, for some ℓ, we haveV sim,⋆ 0 -V sim, π ℓ 0 ≤ 6H 2 log 20V 2 max log 8H|F | δ γ ℓ + 3 • 192AdH log 960dV 2 max log 8H|F | δ γ ℓ • γ ℓ , V real,⋆ 0 -V real, π ℓ 0 ≤ 6H 2 log 20V 2 max log 8H|F | δ γ ℓ + 3 • 192AdH log 960dV 2 max log 8H|F | δ γ ℓ • γ ℓ + 4H 2 ϵ sim .Proof. By Lemma C.4 we have, with probability at least 1 -δ,V sim,⋆ 0 -V sim, π ℓ 0 ≤ 2H 2 log 1 β ℓ + 3 • β ℓ 512V 2 max A log 8H|F| δ + 96AdH log 48d β 2 ℓ • γ ℓ + 2AV 2 max 96dH log 48d β 2 ℓ log 2 δ • β ℓ ≤ 6H 2 log 20V 2 max log 8H|F | δ γ ℓ + 3 • 192AdH log 960dV 2 max log 8H|F | δ γ ℓ • γ ℓwhere the second inequality holds by our setting of β ℓ .We haveV real,⋆ 0 -V real, π t 0 = V real,⋆ 0 -V real,π sim,⋆ 0 + V real,π sim,⋆ 0 -V sim,π sim,⋆ 0 + V sim,π sim,⋆ 0 -V sim, π t 0 + V sim, π t 0 -V real, π t 0 .By Lemma A.3, we can boundV real,⋆ 0 -V real,π sim,⋆ 0 ≤ 2H 2 ϵ simand by Lemma A.1 we can boundV real,π sim,⋆ 0 -V sim,π sim,⋆ 0 ≤ H 2 ϵ sim , V sim, π ℓ 0 -V real, π ℓ 0 ≤ H 2 ϵ sim .Combining this with our bound on V sim,⋆ 0 -V sim, π ℓ 0 gives the result.In this section we provide additional supporting lemmas for our main results and in particular, we focus on linear in sim. In Appendix C.1 we provide several technical results critical to showing that sim can be utilized to restrict the version space, as is done in Theorem 4. In order to restrict the version space using sim, sufficiently rich data must be collected from sim, and in Appendix C.2 we provide results on this data collection. Finally, in Appendix C.3 we provide a procedure to compute the exploration policies in sim which we ultimately transfer to real.In Appendices C.1 and C.2, we let hypothesis f and f be defined recursively as:f h := arg min f h ∈F h 1 T sim T sim t=1 (f h ( s t h , a t h ) -r t h -max a ′ f h+1 ( s t h+1 , a ′ )) 2 .and f h ∈ F h some hypothesis satisfying1 T sim T sim t=1 ( f h ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ γfor parameter γ > 0.In Appendix C.1 we make the following assumption on the data generating process.Assumption 5. Consider the dataset D sim = {( s t 0 , a t 0 , r t 0 , . . . , s t H-1 , a t H-1 , r t H-1 )} T sim t=1 . We assume that episode t in D sim was generated by playing an F t-1 -measurable policy π t exp , and denoteπ sim exp = unif({ π t exp } T sim t=1 ).We provide a specific instantiation of π sim exp in Appendix C.2. In Appendix C.3, we provide a procedure for learning a set of policies which induce full-rank covariates in sim, a crucial piece in obtaining good exploration performance in real.Lemma C.1. With probability at least 1 -δ:1 T sim T sim t=1 (T real f h+1 ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ 2V 2 max ϵ 2 sim + 512V 2 max T sim • log 4|F h | δ + V 2 max 2 log 2|F h | δ T sim .Proof. First, note that T real f h+1 ∈ F h by Assumption 4.By Azuma-Hoeffding and a union bound, we have that, with probability at least 1 -δ, for eachf, f ′ ∈ F h , 1 T sim T sim t=1 (f h ( s t h , a t h ) -f ′ h ( s t h , a t h )) 2 ≤ 1 T sim T sim t=1 E sim, π t exp [(f h ( s h , a h ) -f ′ h ( s h , a h )) 2 ] + V 2 max 2 log |F h |/δ T sim = E sim,π sim exp [(f h (s h , a h ) -f ′ h (s h , a h )) 2 ] + V 2 max 2 log |F h |/δ T sim .In particular, this implies that1 T sim T sim t=1 (T real f h+1 ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ E sim,π sim exp [(T real f h+1 (s h , a h ) -f h (s h , a h )) 2 ] + V 2 max 2 log |F h |/δ T sim .We can boundEQUATION.To bound (a), we note thatT real f h+1 (s h , a h ) -f h (s h , a h ) = E real [max a ′ f h+1 (s ′ , a ′ ) | s, a] -E sim [max a ′ f h+1 (s ′ , a ′ ) | s, a] = s ′ (P real h (s ′ | s, a) -P sim h (s ′ | s, a)) • max a ′ f h+1 (s ′ , a ′ ) ≤ V max • s ′ |P real h (s ′ | s, a) -P sim h (s ′ | s, a)| ≤ V max ϵ simwhere the last inequality follows under Assumption 1. This gives that (a) ≤ 2V 2 max ϵ 2 sim . To bound (b), we apply Lemma 3 of [57] , which gives that with probability at least 1 -δ,(b) ≤ 512V 2 max T sim • log 4|F h | δ .Combining these with a union bound gives the result.Lemma C.2. Consider the setF h := f h ∈ F h : 1 T sim T sim t=1 (f h ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ γ .Then with probability 1 -2δ we haveF h ⊆    f h ∈ F h : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ + 18V 2 max log 4|F h | δ T sim    .Proof. By Azuma-Hoeffding, we have that with probability at least 1 -δ, for eachf h , f ′ h ∈ F h , E sim,π sim exp [(f h (s h , a h ) -f ′ h (s h , a h )) 2 ] -V 2 max 2 log |F h |/δ T sim ≤ 1 T sim T sim t=1 (f h ( s t h , a t h ) -f ′ h ( s t h , a t h )) 2which implies in particular that, for anyf h ∈ F h , E sim,π sim exp [(f h (s h , a h ) -f h (s h , a h )) 2 ] -V 2 max 2 log |F h |/δ T sim ≤ 1 T sim T sim t=1 (f h ( s t h , a t h ) -f h ( s t h , a t h )) 2 .We can writeE sim,π sim exp [(f h (s h , a h ) -f h (s h , a h )) 2 ] = E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] + E sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] -2E sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h ))(f h (s h , a h ) -T sim f h+1 (s h , a h ))] ≥ E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] -2E sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h ))(f h (s h , a h ) -T sim f h+1 (s h , a h ))].By Lemma 3 of [57] , with probability at least 1 -δ,E sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ 256V 2 max T sim • log 2|F h | δ .We can therefore bound the final term asE sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h ))(f h (s h , a h ) -T sim f h+1 (s h , a h ))] ≤ V max • E sim,π sim exp [| f h (s h , a h ) -T sim f h+1 (s h , a h )|] ≤ V max • E sim,π sim exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ V max • 256V 2 max T sim • log 2|F h | δ .Altogether then we have shown that, for any f h ∈ F h , with probability at least 1 -2δ:1 T sim T sim t=1 (f h ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≥ E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] -18V 2 max log 2|F h |/δ T sim . Thus, if 1 T sim T sim t=1 (f h ( s t h , a t h ) -f h ( s t h , a t h )) 2 ≤ γ, then E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ + 18V 2 max log 2|F h |/δ T sim .The result follows from a union bound.Lemma C.3. Consider running the COVERTRAJ algorithm of [65] for each h ∈ [H] with parameters m ← ⌈log 2 1/β⌉ and γ i ← 2 i •β for some β ∈ [0, 1], and with REGMIN set to the policy optimization oracle of Oracle 4.2. Then this procedure collectsT sim := H • m i=1 24d 2 i • β 2 log 48d 2 i • β 2episodes, calls the policy optimization oracle at most T sim times, and produces covariates Λ h,i and sets X h,i such that, for eachi ∈ [m], sup π w sim,π h (X h,i ) ≤ 2 -i+1 and ϕ ⊤ Λ -1 h,i ϕ ≤ 2 2i • β 2 , ∀ϕ ∈ X h,i ,andsup π w sim,π h (B d \ ∪ m i=1 X h,i ) ≤ β. Furthermore, we have 12dH β 2 ≤ T sim ≤ 48dH β 2 log 48d β 2 .Proof. Instantiating REGMIN with the oracle of Oracle 4.2, we have that Definition 5.1 of [65] is met with C 1 = C 2 = 0. Therefore, we have that at each stage i we collect exactly (using the precise form for K i given in the appendix of [65] )K i = ⌈2 i • 24d γ 2 i log 48 • 2 i d γ 2 i ⌉episodes. The result then follows by Theorem 3 of [65] .Lemma C.4. Consider running the procedure of Lemma C.3 to collect data. Then with probability at 1 -2δ, we haveV sim,⋆ 0 -V sim,π f 0 ≤ 2H 2 log 1 β + 3 • β 512V 2 max A log(4H|F|/δ) + 96AdH log 48d β 2 • γ + 2AV 2 max 96dH log 48d β 2 log 1 δ • β .Proof. By Lemma A.4: 3 , and note thatV sim,⋆ 0 -V sim,π f 0 ≤ max π∈{π f ,π sim,⋆ } H-1 h=0 2 E sim,π [ f h (s h , a h ) -T sim f h+1 (s h , a h )] ≤ max π∈{π f ,π sim,⋆ } H-1 h=0 2E sim,π [| f h (s h , a h ) -T sim f h+1 (s h , a h )|]. Denote g(z h ) := | f h (s h , a h ) -T sim f h+1 (s h , a h )| and Λ h-1 = m i=1 Λ h,i + I, for Λ h,i collected as in Lemma C.E sim,π [g(z h )] = E sim,π [ g(z)dP π h (z | z h-1 )] = E sim,π [ g(z)π(a | s)dadµ s h-1 (s) ⊤ ϕ s (z h-1 )] = E sim,π [ g(z)π(a | s)dadµ s h-1 (s) ⊤ Λ 1/2 h-1 Λ -1/2 h-1 ϕ s (z h-1 )] ≤ E sim,π [∥ g(z)π(a | s)dadµ s h-1 (s)∥ Λ h-1 • ∥ϕ s (z h-1 )∥ Λ -1 h-1 ] = ∥ g(z)π(a | s)dadµ s h-1 (s)∥ Λ h-1 • E sim,π [∥ϕ s (z h-1 )∥ Λ -1 h-1].(C.1)We bound each of these terms separately. First, we haveE sim,π [∥ϕ s (z h-1 )∥ Λ -1 h-1 ] ≤ m i=1 max ϕ∈X h-1,i ∥ϕ∥ Λ -1 h-1 • sup π E sim,π [I{ϕ s (z h-1 ) ∈ X h-1,i }] + max ϕ∈B d \∪ m i=1 X h-1,i ∥ϕ∥ Λ -1 h-1 • sup π E sim,π [I{ϕ s (z h-1 ) ∈ X h-1,i }] (a) ≤ ι i=1 γ i • 2 -i+1 + β ≤ (2m + 1)βwhere (a) follows from Lemma C.3 and since ∥ϕ∥ Λ -1h-1 ≤ 1 always.We turn now to bounding the first term. Note that∥ g(z)π(a | s)dadµ s h-1 (s)∥ Λ h-1 = T sim ( g(z)π(a | s)dadµ s h-1 (s) ⊤ ϕ t h-1 ) 2 = T sim t=1 E π [g(z h ) | z t h-1 ] 2 ≤ T sim t=1 E π [g(z h ) 2 | z t h-1 ] (a) ≤ A • T sim t=1 E π h-1,t exp [g(z h ) 2 | z t h-1 ] = A • T sim t=1 E π h-1,t exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 | z t h-1 ] ≤ 2A • T sim t=1 E π h-1,t exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 | z t h-1 ] + 2A • T sim t=1 E π h-1,t exp [( f h (s h , a h ) -f h (s h , a h )) 2 | z t h-1 ] (b) ≤ 512V 2 max A log(4H|F|/δ) + 2A • T sim t=1 E π h-1,t exp [( f h (s h , a h ) -f h (s h , a h )) 2 | z t h-1 ]where (a) uses the fact that π h-1,t exp plays actions randomly at step h and (b) holds with probability at least 1 -δ by Lemma C.6. By Azuma-Hoeffding, we have with probability 1 -δ:T sim t=1 E π h-1,t exp [( f h (s h , a h ) -f h (s h , a h )) 2 | z t h-1 ] ≤ T sim t=1 ( f h (s t h , a t h ) -f h (s t h , a t h )) 2 + 2V 4 max T sim log 1/δ ≤ T sim γ + 2V 4 max T sim log 1/δwhere the last inequality follows from the definition of f h .Altogether then we have shown that, with probability at least 1 -2δ:V sim,⋆ 0 -V sim,π f 0 ≤ 2H(2m + 1)β • 512V 2 max A log(4H|F|/δ) + 2AT sim γ + 2AV 2 max 2T sim log 1/δ.Using that T sim ≤ 48dH β 2 log 48d β 2 as given in Lemma C.3, we can bound this as≤ 2H(2m + 1) β 512V 2 max A log(4H|F|/δ) + 96AdH log 48d β 2 • γ + 2AV 2 max 96dH log 48d β 2 log 1 δ • β .The result follows.Lemma C.5. Assume thatE sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ.Then this implies that, with probability at least 1 -δ,sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h a h )]) 2 ≤ 4 log 1 β + 6 A • 48d log 48d β 2 • γ + V max 96d log 48d β 2 log 1 δ • β . Therefore, {f ∈ F : E sim,π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] ≤ γ} ⊆ f ∈ F : sup π (E sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )]) 2 ≤ 4 log 1 β + 6 A • 48dH log 48d β 2 • γ + V 2 max 96dH log 48d β 2 log 1 δ • β .Proof. We follow a similar argument as the proof of Lemma C.4. Denoting g(z h ) := f h (s h , a h ) -T sim f h+1 (s h , a h ), by the same calculation as (C.1) we haveE sim,π [g(z h )] ≤ ∥ g(z)π(a | s)dadµ s h-1 (s)∥ Λ h-1 • E sim,π [∥ϕ s (z h-1 )∥ Λ -1 h-1 ]and as in the proof of Lemma C.4, we can boundE sim,π [∥ϕ s (z h-1 )∥ Λ -1 h-1 ] ≤ (2m + 1)β and ∥ g(z)π(a | s)dadµ s h-1 (s)∥ Λ h-1 ≤ A • T sim t=1 E π h-1,t exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 | z t h-1 ]By Azuma-Hoeffding, with probability at least 1 -δ we can then boundT sim t=1 E π h-1,t exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 | z t h-1 ] ≤ T sim • E π sim exp [(f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 ] + 2V 4 max T sim log 1/δ ≤ T sim γ + 2V 4 max T sim log 1/δwhere the last inequality follows by assumption, and where π sim exp = unif({π h-1,t exp } T sim t=1 ). Altogether then, for all π, we haveE sim,π [f h (s h , a h ) -T sim f h+1 (s h , a h )] ≤ (2m + 1)β • AT sim γ + AV 2 max 2T sim log 1/δ.Using that T sim ≤ 48dH β 2 log 48d β 2 as given in Lemma C.3, we can bound this as≤ (2m + 1) 48AdH log 48d β 2 • γ + (2m + 1) AV 2 max 96dH log 48d β 2 log 1 δ • β.The result follows from some algebra.Lemma C. 6 . With probability at least 1 -δ, for each h ∈ [H] simultaneously, we haveT sim t=1 E sim,π h-1,t exp [( f h (s h , a h ) -T sim f h+1 (s h , a h )) 2 | s t h-1 , a t h-1 ] ≤ 256V 2 max log(4H|F|/δ).Proof. This follows from Lemma 3 of [57] . N j ← ⌈2 j/3 ⌉ -1, K j ← ⌈2 2j/3 ⌉, T j ← (N j + 1)K j , δ j ← δ 4j 2// DynamicOED algorithm from [64] 5: Σ j , Π j ← DYNAMICOED(Φ, N j , K j , δ j , A R ) for Φ(Λ h ) ← tr((Λ h + ζ • I) -1 ) 6: if λ min (Σ j ) ≥ 12544d logWe consider running the MINEIG algorithm (Algorithm 6) of [64] in sim. For a fixed h, we instantiate the setting of Appendix C of [64] with ψ(τ) = ϕ(s h , a h )ϕ(s h , a h ) ⊤ , D = 1, and A R the policy optimization oracle of Oracle 4.2 (and so C R = 0), and set N = 1 for MINEIG. We note that this algorithm is computationally efficient, given a policy optimization oracle.Lemma C.7. For M ← M sim , Algorithm T j ⋆ , which implies that the termination criteria of Algorithm 5 will be met. By Lemma C.5 of [64] , it follows that with probability at least 1 -δ/2, we have λ min ( 1|Π j ⋆ | π∈Π j ⋆ Λ s π,h ) ≥ λ ⋆ min 8d (since T j ⋆ = |Π j ⋆ |), the desired conclusion.Assume that Algorithm 5 terminates for some j < j ⋆ . This implies thatλ ⋆ min 4d T j < 12544d log 4+64Tj δ. However, in this case, we then have thatλ min (Σ j ) ≥ 12544d log 4 + 64T j δ ≥ λ ⋆ min 4d T j .From Lemma C.5 of [64] , it then follows that with probability at least 1 -δ/2, we haveλ min ( 1 |Πj | π∈Πj Λ s π,h ) ≥ λ ⋆ min 8d. It follows that, assuming T j is large enough that (C.3) is met, and we are in the case when ζ ≤ λ ⋆ min 4d holds, then Algorithm 5 will terminate and return a set of policies satisfying (C.2), with probability at least 1 -δ. Note that T j = O(2 j ). Given that Algorithm 5 does not terminate untilj = O(log 2 ( d ζ • log 1 δ + ζ -9 • log 3/2 1 δ ) ≥ O(log 2 ( d 2 λ ⋆ min • log 1 δ + ζ -9 • log 3/2 1 δ )), we will have that T j will be large enough that (C.3) is met, if ζ ≤ λ ⋆ min 4d . The proof then follows since DYNAMICOED calls Oracle 4.2 at most T j times at round j, and the total sum of T j is bounded asO( d ζ • log 1 δ + ζ -9 • log 3/2 1 δ) by the maximum of j, and since the actions chosen by π ∈ Π for h ′ > h are irrelevant for the operation of DYNAMICOED, so they can be set to random. Construction. Consider the following variation of the combination lock. We let the action space A = {1, 2}, and assume there are states, S = {s 1 , s 2 }, and horizon H. We start in state s 1 . The sim dynamics are given as:∀h < H -1 : P sim h (s 1 | s 1 , a 1 ) = 1, P sim h (s 2 |, s 1 , a 2 ) = 1 P sim H-1 (s 1 | s 1 , a 1 ) = P sim H-1 (s 2 | s 1 , a 1 ) = P sim H-1 (s 1 | s 1 , a 2 ) = P sim H-1 (s 2 | s 1 , a 2 ) = 1/2 ∀h ∈ [H] : P sim h (s 2 | s 2 , a) = 1, a ∈ {a 1 , a 2 }.We define two real instances, M 1 := M real,1 and M 2 := M real,2 , where for both we have:∀h < H -1 : P real h (s 1 | s 1 , a 1 ) = 1, P real h (s 2 |, s 1 , a 2 ) = 1 ∀h ∈ [H] : P real h (s 2 | s 2 , a) = 1, a ∈ {a 1 , a 2 } for M 1 : P real H-1 (s 1 | s 1 , a 1 ) = 1/2 + ϵ sim , P real H-1 (s 2 | s 1 , a 1 ) = 1/2 -ϵ sim , P real H-1 (s 1 | s 1 , a 2 ) = 1/2 -ϵ sim , P real H-1 (s 2 | s 1 , a 2 ) = 1/2 + ϵ sim, and for M 2 :P real H-1 (s 1 | s 1 , a 1 ) = 1/2 -ϵ sim , P real H-1 (s 2 | s 1 , a 1 ) = 1/2 + ϵ sim , P real H-1 (s 1 | s 1 , a 2 ) = 1/2 + ϵ sim , P real H-1 (s 2 | s 1 , a 2 ) = 1/2 -ϵ sim .Note then that M 1 , M 2 , and sim only differ at step H -1 in state s 1 . Furthermore, it is easy to see that both M 1 and M 2 satisfy Assumption 1 with misspecification ϵ sim . It is easy to see that Assumption 2 holds as well with d = 4 since this is a tabular MDP, and furthermore Assumption 3 also holds with λ ⋆ min = 1/4. We define the reward function as (note that this is deterministic, and the same for all instances):∀h ∈ [H] : r h (s 1 , a 2 ) = 1/2 + ϵ sim (1/2 -h/4H) r H (s 1 , a) = 1, a ∈ {a 1 , a 2 },and all other rewards are taken to be 0.In sim, we see that the optimal policy always plays a 2 . In both M 1 and M 2 , the optimal policy plays a 1 for all h < H -1, for M 1 plays a 1 at H -1, and for M 2 plays a 2 at H -1. Note that for both M 1 and M 2 , we have V ⋆ 0 = 1/2 + ϵ sim . The most natural choice of F would be the set of all tabular Q-value functions, however, this set is infinite, and would require a covering argument to incorporate. For simplicity, consider F H the set of functions mapping to {0, 1}, and F h the set of functions mapping to a finite set containing{0, 1/2 -ϵ sim , 1/2 + ϵ sim } ∪ {1/2 + ϵ sim (1/2 -h ′ /4H)} H h ′ =0. Note that such a set satisfies Assumption 4 and we can construct it such that log |F| ≤ O(H).Lower Bound for Direct Policy Transfer (Proposition 3). We consider direct sim2real transfer with randomized exploration. In particular, as noted, the optimal policy in sim always plays a 2 , so we consider the ζ-greedy policy that at every state plays a 2 with probability 1 -ζ, and plays unif({a 1 , a 2 }) with probability ζ. Denote this policy as π. We then wish to lower bound:inf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ]after running our procedure for T episodes. Note that on M 1 , regardless of the actions π chooses in other states, we haveV M1,⋆ 0 -V M1, π 0 ≥ ϵ sim 2 (1 -π H-1 (a 1 | s 1 )),since the only way π can achieve a reward of 1/2 + ϵ sim is by playing a 1 in s 1 at step H -1, and all other sequences of actions obtain a reward at most 1/2 + ϵ sim /2. Similarly for M 2 we haveV M2,⋆ 0 -V M2, π 0 ≥ ϵ sim 2 (1 -π H-1 (a 2 | s 1 )).Using this, and replacing the max over i ∈ {1, 2} with the average of them, we obtaininf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ inf π 1 2 E M1, π [ ϵ sim 2 (1 -π H-1 (a 1 | s 1 ))] + 1 2 E M2, π [ ϵ sim 2 (1 -π H-1 (a 2 | s 1 ))] = ϵ sim 2 1 - 1 2 • sup π E M1, π [ π H-1 (a 1 | s 1 )] + E M2, π [ π H-1 (a 2 | s 1 )] . Since π H-1 (a 1 | s 1 ) = 1 -π H-1 (a 2 | s 1 ), we have E M1, π [ π H-1 (a 1 | s 1 )] + E M2, π [ π H-1 (a 2 | s 1 )] = 1 + E M1, π [ π H-1 (a 1 | s 1 )] -E M2, π [ π H-1 (a 1 | s 1 )] ≤ 1 + TV(P M1, π , P M2, π ) ≤ 1 + 1 2 KL(P M1, π ∥ P M2, π )where TV denotes the total-variation distance, KL the KL-divergence, and the last inequality follows from Pinsker's inequality. We therefore haveinf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ ϵ sim 4 1 - 1 2 KL(P M1, π ∥ P M2, π ) .Now note that, since M 1 and M 2 only differ at state s 1 and step H -1, we haveEQUATION)), where T H-1 (s 1 , a i ) denotes the total number of visits to (s 1 , a i ) at step H -1 after T episodes (see e.g. [59] ). We haveKL(P M1 H-1 (• | s 1 , a 1 ) ∥ P M2 H-1 (• | s 1 , a 1 )) = KL(P M1 H-1 (• | s 1 , a 2 ) ∥ P M2 H-1 (• | s 1 , a 2 )) = 1 4 log 1/4 3/4 + 3 4 log 3/4 1/4 ≤ 3 5where the last inequality holds as long as ϵ sim ≤ 1/6. Note that the only way for a policy to reach s 1 at step H -1 is to play action a 1 H -1 consecutive times. Since π only plays a 1 at any given step with probability ζ/2, it follows that the probability that π reaches s 1 at step H -1 on any given episode is only (ζ/2) H-1 . Thus,KL(P M1, π ∥ P M2, π ) ≤ 3 5 E M1, π [T H-1 (s 1 , a 1 )] + E M1, π [T H-1 (s 1 , a 2 )] = 3 5 E M1, π [T H-1 (s 1 )] = 3 5 ζ 2 H-1 • T.We thus have:inf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ ϵ sim 4   1 - 3 10 ζ 2 H-1 • T   and we therefore have inf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ ϵ sim /8 unless T ≥ 5 6 • 2 ζ H-1.Lower Bound for ζ-Greedy Without sim (Proposition 1). In order to quantify the performance of a ζ-greedy algorithm, we must specify how it chooses f when it has not yet observed any samples from a given (s, a, h). Following the lead of Theorem 2 [11] , to avoid an overly optimistic or pessimistic initialization, we assume that the replay buffer is initialized with a single sample from each (s, a, h). Note that the conclusion would hold with other initializations, however, e.g. initializing f h (s, a) = 0 or randomly if we have no observations from (s, a, h).Assume that the observation from (s 1 , a 1 , H -1) transitions to s 2 , which occurs with probability at least 1/4. In this case, we then have that, for each h, f 0 h (s 1 , a 2 ) ≥ f 0 h (s 1 , a 1 ). Thus, following the ζ-greedy policy, we have that π 0 h (a 1 | s 1 ) ≤ 1/2. Denote this event on E 0 . Furthermore, the only way we will have f 0 h (s 1 , a 2 ) < f 0 h (s 1 , a 1 ) is if we visit (s 1 , a 1 , H -1) again and observe a transition to s 1 . For this to occur, however, we must play action a 1 H -1 times consecutively which, in this case, will occur with probability at most max{1/2, ζ/2} H-1 ≤ 1/2 H-1 .Following the argument in the direct policy transfer case, we haveinf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ inf π sup i∈{1,2} 1 4 E Mi, π [V Mi,⋆ 0 -V Mi, π 0 | E 0 ] ≥ ϵ sim 16 1 - 3 10 E M1 [T H-1 (s 1 ) | E 0 ] where E M1 [T H-1 (s 1 ) | E 0 ]is the expected number of visitations to (s 1 , H -1) after T episodes of running the ζ-greedy policy. We can rewriteE M1 [T H-1 (s 1 ) | E 0 ] = T t=1 E M1 [I{s H-1 = s 1 } | E 0 ].Let E be the event that we have reached (s 1 , H -1) in the first T rounds. Then,E M1 [I{s H-1 = s 1 } | E 0 ] = E M1 [I{s H-1 = s 1 } | E, E 0 ]P M1 [E | E 0 ] + E M1 [I{s H-1 = s 1 } | E c , E 0 ]P M1 [E c | E 0 ] ≤ P M1 [E | E 0 ] + E M1 [I{s H-1 = s 1 } | E c , E 0 ].By what we have just argued, we haveP M1 [E | E 0 ] ≤ T • 1 2 H-1 , and E M1 [I{s H-1 = s 1 } | E c , E 0 ] ≤ 1 2 H-1 . Thus, E M1 [T H-1 (s 1 ) | E 0 ] ≤ 2T 2 2 H-1 . It follows that, inf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ ϵ sim 16 1 - 3 10 2T 2 2 H-1and we therefore haveinf π sup i∈{1,2} E Mi, π [V Mi,⋆ 0 -V Mi, π 0 ] ≥ ϵ sim /32 unless T ≥ 5 8 • 2 H-1 .Upper Bound for Exploration Policy Transfer (Proposition 4). To obtain an upper bound for Algorithm 1, we can apply Theorem 1, so long asϵ sim ≤ λ ⋆ min 64dHA 3 .Note that in our setting we have d = 4, A = 2, λ ⋆ min = 1/4, so this condition reduces to ϵ sim ≤ 1 8192H . Taking F to simply be the set of Q-functions defined above (so V max = H), Theorem 1 then gives that with probability at least 1 -δ, Algorithm 1 learns an ϵ-optimal policy as long asT ≥ c • H 17 ϵ 8 • log H δ .We define three MDPs: M sim , and two possible real MDPs, M 1 := M real,1 and M 2 := M real,2 . In all cases we have states S = {s 1 , s 2 }, actions A = {a 1 , a 2 , a 3 , a 4 }, and H = 2, and set the starting state to s 1 . We defineP sim 1 (s 1 | s 1 , a 1 ) = 1, P sim 1 (s 1 | s 1 , a) = P sim 1 (s 2 | s 1 , a) = 1/2, a ∈ {a 2 , a 3 , a 4 }.The intuition for this example is as follows. In both sim and real, the only way the agent can get reward is to either end up in state s 1 at step H, or to take action a 2 in state s 1 at any In sim, the probability of ending up in state s 1 at step H, even if the optimal sequence of actions to do this is taken, is only 1/4, due to the final transition, and thus the average reward obtained by the policy which aims to end up in s 1 is only 1/4. In contrast, if we take action a 2 in s 1 , we will always collect reward of at least 3/8 (and the earlier we take action a 2 the more reward we collect, up to 1/2). Thus, in sim the optimal thing to do in s 1 is always to play a 2 . However, if we play a 2 even once, we will transition out of s 1 and never return, so there is no chance we will reach s 1 at step H.In real, the transitions at the final step are flipped, so that now the probability of finishing in s 1 , if we take the optimal sequences of actions to do this, is 3/4, and the expected reward for this is then also 3/4. Since the reward for taking a 2 in s 1 does not change, and is bounded as 1/2, then in real the optimal policy is to seek to end up in s 1 at the final step.The challenge with ending up in s 1 at the end is that it requires playing action a 1 at every step. In this sense it is then a classic combination lock instance, and randomized exploration will fail, requiring Ω(2 H ) episodes to reach the final state (since the probability of randomly taking a 1 at every state decreases exponentially with the horizon). Similarly, if we transfer the optimal policy from sim to real, it will never take action a 1 , so will never reach s 1 at the end, and if we transfer the optimal policy from sim with some random exploration, it will fail for the same reason random exploration from scratch fails.However, note that we can transfer a policy from sim that is able to reach s 1 at the second-to-last step with probability 1, i.e. the policy that takes action a 1 at every step. Thus, if in sim we aim to learn exploration policies that can traverse the MDP, and we transfer these exploration policies, they will transfer, and will allow us to easily reach s 1 at the final step, and quickly determine that it is indeed the optimal thing in real.We provide additional experimental results on this instance in Appendix E.1. states given in yellow in Figure 2 ), and when adding additional actions we add additional low-reward actions (i.e. actions that have the same behavior as action a 2 in Figure 2 ). We observe that increasing the number of states and horizon increases the number of samples needed, while increasing the number of actions does not substantially. We emphasize, however, that this is for a particular example, and this scaling may not be the same for all examples-Theorem 1, however, gives an upper bound on all examples.The core of our work is to decouple the optimal policy training from exploration strategies in reinforcement learning fine-tuning. Specifically, we propose a framework that uses a set of diverse exploration policies to collect samples from the environment. These exploration policies are fixed while we run off policy RL updates on the collected samples to extract an optimal policy. Our theoretical derivation suggests that this decoupling can improve sample efficiency and overall learning performance. ). As can be seen, while training from scratch in M real is able to learn, it learns at a much slower rate than exploration policy transfer, and achieves a much lower final value. Furthermore, training the exploration policies to maximize a mix of the task and diversity reward yields a substantial gain over simply training them to be diverse.exploration policies in the replay buffer on episodes where they observe reward. We run vanilla SAC with UTD = 3 and target entropy of -3. We rely on the implementation of SAC from stable-baselines3 [51] .For direct policy transfer, we train a policy to convergence in M sim that solves the task (using SAC), and then transfer this single policy, otherwise following the same procedure as above.In M real , our reward is chosen to have a value of 50 if the end effector makes contact with the ball, and otherwise 0. If the robot successfully makes contact with the ball the episode terminates. To generate a realistic transfer environment, we change the control frequency (doubling it in M real ) and the action bounds.For both methods, we run the M sim training procedure 4 times, and then with each of these run it in M real twice. Error bars in our plot denote one standard error.All experiments were run on two Nvidia V100 GPUs, and 32 Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz CPUs. Additional hyperparameters in given in Table 1 .We provide results on several additional baselines for the Tycho setup in Figure 6 . We next turn to the Franka Emika Panda robot arm [17] , for which we use a realistic custom simulator built using the MuJoCo simulation engine [61] . We consider a hammering task, where the Franka arm holds a hammer, and the goal is to hammer a nail into the (see Figure 8 ). Success is obtained when the nail is fully inserted. We simulate sim2real transfer by setting M real to be a version of the simulator with nail location and stiffness significantly beyond the range seen during training in M sim .We compare exploration policy transfer with direct sim2real policy transfer. Unlike the Tycho experiment, where we trained policies from scratch in M real and simply used the policies trained in M sim to explore, here we initialize the task policy in M real to π sim,⋆ , which we then finetune on the data collected in M real by running SAC. For direct sim2real transfer, we collect data in M real by simply rolling out π sim,⋆ and feeding this data to the replay buffer of SAC. For exploration policy transfer, we train an ensemble of n = 10 exploration policies in M sim and run these policies in M real , again feeding this data to the replay buffer of SAC to finetune π sim,⋆ . During training in M sim , we utilize domain randomization for both methods, randomizing nail stiffness, location, radius, mass, board size, and damping.The results of this experiment are shown in Figure 9 . We see that, while direct policy transfer is able to learn, it learns at a significantly slower rate than our exploration policy transfer approach, and achieves a much smaller final success rate.We use Algorithm 6 to train a policy on the Franka robot with n = 15.The reward of the pushing task is given by: r(s t , a t ) = -∥p ee -p obj ∥ 2 -∥p obj -p goal ∥ 2 + I p obj -p goal ≤0.025 -I p obj offtable (E.1)where p goal is the desired position of the puck by the edge of the surface.The network architecture of the actor and critic networks are identical, consisting of a 2-layer MLP, each of size 256 and ReLU activations.We use stable-baselines3 [51] for our SAC implementation, using all of their default hyperparameters. The implemention of OS is built on top of this SAC implementation. Values of hyperparameters are shown in Table 2 . Gaussian noise with mean 0 and standard deviation 0.005 meters is added in simulation to the position of the puck. Hyperparameters are identical between exploration policy transfer and direct transfer methods.For finetuning in real, we start off by sampling exclusively from the buffer used during simulation. Then, as finetuning proceeds, we gradually start taking more samples from the real buffer, with the proportion of samples taken from sim equal to 1 -s/3000, where s is the current number of steps.After 3000 steps, all samples are taken from the real buffer.Experiments were run using a standard Nvidia RTX 4090 GPU. Training in simulation takes about 3 hours, while finetuning was ran for about 90 minutes.In Figure 7 , we provide results on this setup running the additional baseline of training a policy from scratch in real. As can be seen, this is significantly worse than either transfer method.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We are not releasing high-risk models. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We have cited the creators of the code used in this project. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.The assumption that ϕ s is known is for simplicity only-similar results could be obtained were ϕ s also unknown using more complex algorithmic tools in M sim .Throughout this paper, we use "ζ-greedy" to refer to the method more commonly known as "ϵ-greedy" in the literature, to avoid ambiguity between this ϵ and the ϵ in our definition of PAC RL, Definition 3.2.While for simplicity we assume that the truly optimal policy can be computed, our results easily extend to settings where we only have access to an oracle which can compute an approximately optimal policy.Note that, while Lemma B.1 applies to the constrained regression setting, this is equivalent to the unconstrained regression setting considered here if we choose γ large enough so that the constraint is vacuous. 
 
 Appendix:  


Decision: A simple yet clear idea (transfer exploration policies, not exploitation policies) in an important and timely setting (sim2real), backed up with both theory and real-world robotics experiments. I concur with the reviewers' consensus that this paper should be accepted, even if there is room for further improvements (various ones pointed out in the reviews).

Reviews: review: paper_summary: paper_summary: The paper shows that for transferring with a large sim-to-real gap, exploration policies have improved capabilities compared to optimally pre-trained policies, which tend to overfit the simulation up to a point where exploration is not sufficient to adapt to the changed circumstances.
strength_weakness: strength_weakness: Overall, providing further examples for the theoretical elaborations could help comprehensibility (e.g., Proposition 3). Further minor issues include: 

- Definition 3.2: PAC is not defined, what is $\delta$ used for? 
- In Proposition 1: Is the success of the transfer dependent on the horizon of M? 
- In Proposition 2: What does $\Omega$ refer to? 
- What is the difference between $\epsilon$ and $\epsilon_{sim}$?
- Why is the transition probability $P$ defined to be dependent on the horizon H? 

Also, I am missing a thorough definition of the Low-Rank MDP, which seems central to the theoretical elaboration. 

Even though the experimental setup is convincing, I am missing comparisons directly training $\pi$ in the real task as a baseline. Also, to better illustrate and link the aforementioned theoretical elaboration, providing the distance between the considered benchmark tasks would have been interesting. Furthermore, more detailed comparisons (both experimental and theoretical) to advanced pre-training approaches like APT (Liu et al., 2021) or DIAYN (Eysenbach et al., 2018) would further enhance empirical credibility.
questions: questions: What are the implications of using a low-rank MDP?

If the simulation is considered to be free, wouldn't learning $\Pi$ optimal policies improve the transfer (similar to using a pool of exploration policies)?  

Regarding the transfer described in Alg. 1, are all exploration policies updated, or only the best-performing? 

If we were to consider even larger shifts, is there a point at which exploration policies no longer provide benefits, and learning from scratch is the most sufficient approach? 

When considering the transfer from simulation to the real world, pre-training is often motivated by the need to ensure a certain level of safety for execution in the real world. How does this concern affect your approach?
limitations: limitations: Limitations have been addressed by the authors but could have been extended.
paper_summary: paper_summary: The authors propose a method where, instead of directly transferring a trained policy from a simulator to the real world, exploratory policies are learned in the simulator and transferred. This approach aims to enable efficient exploration in the real world, particularly in low-rank MDP settings.
strength_weakness: strength_weakness: 1. The approach relies on several assumptions (e.g., low-rank MDPs, specific access to simulators and oracles) that may not hold in all real-world scenarios.

2. While the method shows promise in specific settings, its generality to a wider range of RL tasks and environments remains to be demonstrated.

3. Limited comparison with other state-of-the-art methods, especially those addressing the sim-to-real gap through domain randomization or adaptation.
questions: questions: 1. How robust is the method to violations of the low-rank MDP assumption?

2. Can the approach be extended to more complex MDP settings?

3. How does the method scale with the complexity of the task and the size of the state/action spaces?
limitations: limitations: As in weaknesses.
paper_summary: paper_summary: The authors contribute a mathematical proof showing that transferring a "exploration strategy" in sim2real scenarios as opposed to transfer the learned policy result in an exponential improvement on samples needed to learn the real task.
strength_weakness: strength_weakness: - I am not sure why a new basic "sim2real" formalization was used to in this paper when it already exists. The problem explored in this paper is completely equivalent to Multi-Fidelity MDPs (described in {1}), in fact, MF-MDPs even have something not incorporated in the description provided that is the cost of sampling in each fidelity. The MF-MDP paper was not even cited so I assume this happened because the authors have not read the paper. I suggest the paper is rewritten to describe the problem as an MF-MDP for standardization (there shouldn't be any impact to the conclusions or contribution fro the paper), but even if not rewritten at the very least this paper has to be cited and incorporated to the related works:

{1} - Silva, F. L., et al. Toward multi-fidelity reinforcement learning for symbolic optimization. ALA workshop @ AAMAS, 2023.

- Another thing that made me be in the fence regarding my score to this paper is the lack of baselines for the experimental evaluation. There has been many papers exploring a similar idea in the past, so I feel like they should have been incorporated to the experimental evaluation (Cuttler {2} comes to mind immediately, but you also have other newer options)..

{2} Cutler, Mark, Thomas J. Walsh, and Jonathan P. How. "Reinforcement learning with multi-fidelity simulators." 2014 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2014.

- A limitation both in the theoretical and practical side of the paper is that it is assumed that the transfer will happen "one shot", neglecting the fact that either the simulator could be modified to get closer to the real world {3} and the learning process in the simulator repeated, or the approach could already account that the simulator and real world will be different and adapt for that (e.g. {2} and {3}). The present paradigm presented by the authors to "learn from the simulation once and never get back to it" is at least an incomplete picture of all that could be done.

{3} - Hanna, Josiah, and Peter Stone. "Grounded action transformation for robot learning in simulation." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 31. No. 1. 2017.
questions: questions: - Why is it assumed that the transfer HAS to be made one-shot (transferred completely in the beginning of the learning process in the "real environment")? Wouldn't it be better to have the exploration transfer strategy work as a "loop" where the exploration could be revised according to how the real world differs to the simulator?

- Why weren't MF-MDPs used to describe the problem?

- it is stated that the conditions for us being able to find a policy that solve the problem in the simulation is that ϵ ≥ 2H^2ϵ_sim. What is the meaning of ϵ here? Finding conditions for a direct policy transfer to work would also be an important contribution, specially if there is some way to test for those conditions with some samples from both the real world and simulator.
limitations: limitations: Basic research, no potential negative societal impact to explore.

Comments: comment: Thanks authors for addressing the concerns, I raised my score to 5.
We thank the reviewer for the time and effort spent reviewing our paper. As the discussion phase is about to end, we would like to make sure our responses have sufficiently addressed your concerns. We look forward to your feedback.
Thank you for your extensive response and clarifications and for providing additional experimental results as suggested. My concerns are fully addressed, and I hope some of the detailed elaborations are included in the final paper. I will retain my original, already positive score.
I am not sure why DIAYN was considered as the best baseline to add to the paper especially looking at its performance being way worse than just training from scratch.

Still, given the main contribution of the paper is the theoretical framework I will increase a bit my already-positive grade.