Year: 2020

Abstract:
Imitation learning, followed by reinforcement learning algorithms, is a promising paradigm to solve complex control tasks sample-efficiently. However, learning from demonstrations often suffers from the covariate shift problem, which results in cascading errors of the learned policy. We introduce a notion of conservativelyextrapolated value functions, which provably lead to policies with self-correction. We design an algorithm Value Iteration with Negative Sampling (VINS) that practically learns such value functions with conservative extrapolation. We show that VINS can correct mistakes of the behavioral cloning policy on simulated robotics benchmark tasks. We also propose the algorithm of using VINS to initialize a reinforcement learning algorithm, which is shown to outperform prior works in sample efficiency.

text: Imitation learning, followed by reinforcement learning algorithms, is a promising paradigm to solve complex control tasks sample-efficiently. However, learning from demonstrations often suffers from the covariate shift problem, which results in cascading errors of the learned policy. We introduce a notion of conservativelyextrapolated value functions, which provably lead to policies with self-correction. We design an algorithm Value Iteration with Negative Sampling (VINS) that practically learns such value functions with conservative extrapolation. We show that VINS can correct mistakes of the behavioral cloning policy on simulated robotics benchmark tasks. We also propose the algorithm of using VINS to initialize a reinforcement learning algorithm, which is shown to outperform prior works in sample efficiency.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) algorithms, especially with sparse rewards, often require a large amount of trial-and-errors. Imitation learning from a small number of demonstrations followed by RL finetuning is a promising paradigm to improve the sample efficiency (Rajeswaran et al., 2017; Večerík et al., 2017; Hester et al., 2018; Nair et al., 2018; Gao et al., 2018).
The key technical challenge of learning from demonstrations is the covariate shift: the distribution of the states visited by the demonstrations often has a low-dimensional support; however, knowledge learned from this distribution may not necessarily transfer to other distributions of interests. This phenomenon applies to both learning the policy and the value function. The policy learned from behavioral cloning has compounding errors after we execute the policy for multiple steps and reach unseen states (Bagnell, 2015; Ross & Bagnell, 2010). The value function learned from the demonstrations can also extrapolate falsely to unseen states. See Figure 1a for an illustration of the false extrapolation in a toy environment.
We develop an algorithm that learns a value function that extrapolates to unseen states more conservatively, as an approach to attack the optimistic extrapolation problem (Fujimoto et al., 2018a). Consider a state s in the demonstration and its nearby state s̃ that is not in the demonstration. The key intuition is that s̃ should have a lower value than s, because otherwise s̃ likely should have been visited by the demonstrations in the first place. If a value function has this property for most of the pair (s, s̃) of this type, the corresponding policy will tend to correct its errors by driving back to the demonstration states because the demonstration states have locally higher values. We formalize the intuition in Section 4 by defining the so-called conservatively-extrapolated value function, which is guaranteed to induce a policy that stays close to the demonstrations states (Theorem 4.4).
In Section 5, we design a practical algorithm for learning the conservatively-extrapolated value function by a negative sampling technique inspired by work on learning embeddings Mikolov et al. (2013); Gutmann & Hyvärinen (2012). We also learn a dynamical model by standard supervised learning so that we compute actions by maximizing the values of the predicted next states. This algorithm does not use any additional environment interactions, and we show that it empirically helps correct errors of the behavioral cloning policy.
When additional environment interactions are available, we use the learned value function and the dynamical model to initialize an RL algorithm. This approach relieves the inefficiency in the prior work (Hester et al., 2018; Nair et al., 2018; Rajeswaran et al., 2017) that the randomly-initialized Q functions require a significant amount of time and samples to be warmed up, even though the initial policy already has a non-trivial success rate. Empirically, the proposed algorithm outperforms the prior work in the number of environment interactions needed to achieve near-optimal success rate.
In summary, our main contributions are: 1) we formalize the notion of values functions with conservative extrapolation which are proved to induce policies that stay close to demonstration states and achieve near-optimal performances, 2) we propose the algorithm Value Iteration with Negative Sampling (VINS) that outperforms behavioral cloning on three simulated robotics benchmark tasks with sparse rewards, and 3) we show that initializing an RL algorithm from VINS outperforms prior work in sample efficiency on the same set of benchmark tasks.

heading: 2 RELATED WORK
text: Imitation learning. Imitation learning is commonly adopted as a standard approach in robotics (Pomerleau, 1989; Schaal, 1997; Argall et al., 2009; Osa et al., 2017; Ye & Alterovitz, 2017; Aleotti & Caselli, 2006; Lawitzky et al., 2012; Torabi et al., 2018; Le et al., 2017; 2018) and many other areas such as playing games (Mnih et al., 2013). Behavioral cloning (Bain & Sommut, 1999) is one of the underlying central approaches. See Osa et al. (2018) for a thorough survey and more references therein. If we are allowed to access an expert policy (instead of trajectories) or an approximate value function, in the training time or in the phase of collecting demonstrations, then, stronger algorithms can be designed, such as DAgger (Ross et al., 2011), AggreVaTe (Ross & Bagnell, 2014), AggreVaTeD (Sun et al., 2017), DART (Laskey et al., 2017), THOR Sun et al. (2018a). Our setting is that we have only clean demonstrations trajectories and a sparse reward (but we still hope to learn the self-correctable policy.)
Ho & Ermon (2016); Wang et al. (2017); Schroecker et al. (2018) successfully combine generative models in the setting where a large amount of environment interaction without rewards are allowed. The sample efficiency of (Ho & Ermon, 2016) has been improved in various ways, including maximum mean discrepancy minimization (Kim & Park, 2018), a Bayesian formulation of GAIL (Jeon et al., 2018), using an off-policy RL algorithm and solving reward bias problem (Kostrikov et al., 2018), and bypassing the learning of reward function (Sasaki et al., 2018). By contrast, we would like to minimize the amount of environment interactions needed, but are allowed to access a sparse reward. The work (Schroecker & Isbell, 2017) also aims to learn policies that can stay close to the demonstration sets, but through a quite different approach of estimating the true MAP estimate of the
policy. The algorithm also requires environment interactions, whereas one of our main goals is to improve upon behavioral cloning without any environment interactions.
Inverse reinforcement learning (e.g., see (Abbeel & Ng, 2004; Ng et al., 2000; Ziebart et al., 2008; Finn et al., 2016a;b; Fu et al., 2017)) is another important and successful line of ideas for imitation learning. It relates to our approach in the sense that it aims to learn a reward function that the expert is optimizing. In contrast, we construct a model to learn the value function (of the trivial sparse reward R(s, a) = −1), rather than the reward function. Some of these works (e.g., (Finn et al., 2016a;b; Fu et al., 2017)) use techniques that are reminiscent of negative sampling or contrastive learning, although unlike our methods, they use “negative samples” that are sampled from the environments.
Leveraging demonstrations for sample-efficient reinforcement learning. Demonstrations have been widely used to improve the efficiency of RL (Kim et al., 2013; Chemali & Lazaric, 2015; Piot et al., 2014; Sasaki et al., 2018), and a common paradigm for continuous state and action space is to initialize with RL algorithms with a good policy or Q function (Rajeswaran et al., 2017; Nair et al., 2018; Večerík et al., 2017; Hester et al., 2018; Gao et al., 2018). We experimentally compare with the previous state-of-the-art algorithm in Nair et al. (2018) on the same type of tasks. Gao et al. (2018) has introduced soft version of actor-critic to tackle the false extrapolation of Q in the argument of a when the action space is discrete. In contrast, we deal with the extrapolation of the states in a continuous state and action space.
Model-based reinforcement learning. Even though we will learn a dynamical model in our algorithms, we do not use it to generate fictitious samples for planning. Instead, the learned dynamics are only used in combination with the value function to get a Q function. Therefore, we do not consider our algorithm as model-based techniques. We refer to (Kurutach et al., 2018; Clavera et al., 2018; Sun et al., 2018b; Chua et al., 2018; Sanchez-Gonzalez et al., 2018; Pascanu et al., 2017; Khansari-Zadeh & Billard, 2011; Luo et al., 2018) and the reference therein for recent work on model-based RL.
Off-policy reinforcement learning There is a large body of prior works in the domain of off-policy RL, including extensions of policy gradient (Gu et al., 2016; Degris et al., 2012; Wang et al., 2016) or Q-learning (Watkins & Dayan, 1992; Haarnoja et al., 2018; Munos et al., 2016). Fujimoto et al. (2018a) propose to solve off-policy reinforcement learning by constraining the action space, and Fujimoto et al. (2018c) use double Q-learning (Van Hasselt et al., 2016) to alleviate the optimistic extrapolation issue. In contrast, our method adjusts the erroneously extrapolated value function by explicitly penalizing the unseen states (which is customized to the particular demonstration offpolicy data). For most of the off-policy methods, their convergence are based on the assumption of visiting each state-action pair sufficiently many times. In the learning from demonstration setting, the demonstrations states are highly biased or structured; thus off-policy method may not be able to learn much from the demonstrations.

heading: 3 PROBLEM SETUP AND CHALLENGES
text: We consider a setting with a deterministic MDP with continuous state and action space, and sparse rewards. Let S = Rd be the state space andA = Rk be the action space, and letM? : Rd×Rk → Rd be the deterministic dynamics. At test time, a random initial state s0 is generated from some distribution Ds0 . We assume Ds0 has a low-dimensional bounded support because typically initial states have special structures. We aim to find a policy π such that executing π from state s0 will lead to a set of goal states G. All the goal states are terminal states, and we run the policy for at most T steps if none of the goal states is reached.
Let τ = (s0, a1, s1, . . . , ) be the trajectory obtained by executing a deterministic policy π from s0, where at = π(st), and st+1 = M?(st, at). The success rate of the policy π is defined as
succ(π) = E [1{∃t ≤ T, st ∈ G}] (3.1)
where the expectation is taken over the randomness of s0. Note that the problem comes with a natural sparse reward: R(s, a) = −1 for every s and a. This will encourage reaching the goal with as small number of steps as possible: the total payoff of a trajectory is equal to negative the number of steps if the trajectory succeeds, or −T otherwise.
Let πe be an expert policy 1 from which a set of n demonstrations are sampled. Concretely, n independent initial states {s(i)0 }ni=1 from Ds0 are generated, and the expert executes πe to collect a set of n trajectories {τ (i)}ni=1. We only have the access to the trajectories but not the expert policy itself. We will design algorithms for two different settings:
Imitation learning without environment interactions: The goal is to learn a policy π from the demonstration trajectories {τ (i)}ni=1 without having any additional interactions with the environment. Leveraging demonstrations in reinforcement learning: Here, in addition to the demonstrations, we can also interact with the environment (by sampling s0 ∼ Ds0 and executing a policy) and observe if the trajectory reaches the goal. We aim is to minimize the amount of environment interactions by efficiently leveraging the demonstrations.
Let U be the set of states that can be visited by the demonstration policy from a random state s0 with positive probability. Throughout this paper, we consider the situation where the set U is only a small subset or a low-dimensional manifold of the entire state space. This is typical for continuous state space control problems in robotics, because the expert policy may only visit a very special kind of states that are the most efficient for reaching the goal. For example, in the toy example in Figure 1, the set U only contains those entries with black edges.2
To put our theoretical motivation in Section 4 into context, next we summarize a few challenges of imitation learning that are particularly caused by that U is only a small subset of the state space. Cascading errors for behavioral cloning. As pointed out by Bagnell (2015); Ross & Bagnell (2010), the errors of the policy can compound into a long sequence of mistakes and in the worst case cascade quadratically in the number of time steps T . From a statistical point of view, the fundamental issue is that the distribution of the states that a learned policy may encounter is different from the demonstration state distribution. Concretely, the behavioral cloning πBC performs well on the states in U but not on those states far away from U . However, small errors of the learned policy can drive the state to leave U , and then the errors compound as we move further and further away from U . As shown in Section 4, our key idea is to design policies that correct themselves to stay close to the set U . Degeneracy in learning value or Q functions from only demonstrations. When U is a small subset or a low-dimensional manifold of the state space, off-policy evaluation of V πe and Qπe is fundamentally problematic in the following sense. The expert policy πe is not uniquely defined outside U because any arbitrary extension of πe outside U would not affect the performance of the expert policy (because those states outside U will never be visited by πe from s0 ∼ Ds0 ). As a result, the value function V πe and Qπe is not uniquely defined outside U . In Section 4, we will propose a conservative extrapolation of the value function that encourages the policy to stay close to U . Fitting Qπe is in fact even more problematic. We refer to Section A for detailed discussions and why our approach can alleviate the problem.
Success and challenges of initializing RL with imitation learning. A successful paradigm for sample-efficient RL is to initialize the RL policy by some coarse imitation learning algorithm such as BC (Rajeswaran et al., 2017; Večerík et al., 2017; Hester et al., 2018; Nair et al., 2018; Gao et al., 2018). However, the authors suspect that the method can still be improved, because the value function or the Q function are only randomly initialized so that many samples are burned to warm them up. As alluded before and shown in Section 4, we will propose a way to learn a value function from the demonstrations so that the following RL algorithm can be initialized by a policy, value function, and Q function (which is a composition of value and dynamical model) and thus converge faster.

heading: 4 THEORETICAL MOTIVATIONS
text: In this section, we formalize our key intuition that the ideal extrapolation of the value function V πe should be that the values should decrease as we get further and further from the demonstrations. Recall that we use U to denote the set of states reachable by the expert policy from any initial state s0
1In this work, we only consider deterministic expert policies. 2One may imagine that U can be a more diverse set if the demonstrations are more diverse, but an expert will
not visit entries on the top or bottom few rows, because they are not on any optimal routes to the goal state.
Goal
Figure 2: Illustration of the correction effect. A conservatively-extrapolated value function V , as shown in the figure, has lower values further away from U , and therefore the gradients of V point towards U . With such a value function, suppose we are at state s which is ε-close to U . The locallycorrectable assumption of the dynamics assumes the existence of acx that will drive us to state scx that is closer to U than s. Since scx has a relatively higher value compared to other possible future states that are further away from U (e.g., s′ shown in the figure), scx will be preferred by the optimization (4.3). In other words, if an action a leads to state s with large distance to U , the action won’t be picked by (4.3) because it cannot beat acx.
drawn with positive probability from Ds0 . 3 We use ‖ · ‖ to denote a norm in Euclidean space Rd. Let ΠU (s) be the projection of s ∈ Rd to a set U ⊂ Rd (according to the norm ‖ · ‖) 4. We introduce the notion of value functions with conservative extrapolation which matches V πe on the demonstration states U and has smaller values outside U . As formally defined in equation (4.1) and (4.2) in Alg. 1, we extrapolate V πe in a way that the value at s 6∈ U is decided by the value of its nearest neighbor in U (that is V πe(ΠU (s)), and its distance to the nearest neighbor (that is, ‖s−ΠU (s)‖). We allow a δV > 0 error because exact fitting inside or outside U would be impossible.
Algorithm 1 Self-correctable policy induced from a value function with conservative extrapolation Require: conservatively-extrapolated values V satisfying
V (s) = V πe(s)± δV , if s ∈ U (4.1) V (s) = V πe(ΠU (s))− λ‖s−ΠU (s)‖ ± δV if s 6∈ U (4.2)
and a locally approximately correct dynamics M and BC policy πBC satisfying Assumption (4.1).
Self-correctable policy π:
π(s) , argmax a:‖a−πBC(s)‖≤ζ V (M(s, a)) (4.3)
Besides a conservatively-extrapolated value function V , our Alg. 1 relies on a learned dynamical model M and a behavioral cloning policy πBC. With these, the policy returns the action with the maximum value of the predicted next state in around the action of the BC policy. In other words, the policy π attempts to re-adjust the BC policy locally by maximizing the value of the next state.
Towards analyzing Alg. 1, we will make a few assumptions. We first assume that the BC policy is correct in the set U , and the dynamical model M is locally correct around the set U and the BC actions. Note that these are significantly weaker than assuming that the BC policy is globally correct (which is impossible to ensure) and that the model M is globally correct. Assumption 4.1 (Local errors in learned dynamics and BC policy). We assume the BC policy πBC makes at most δπ error in U : for all s ∈ U , we have ‖πBC(s)− πe(s)‖ ≤ δπ. We also assume that the learned dynamics M has δM error locally around U and the BC actions in the sense that for all s that is ε-close to U , and any action that is ζ-close to πBC(s), we have ‖M(s, a)−M?(s, a)‖ ≤ δM .
We make another crucial assumption on the stability/correctability of the true dynamics. The following assumption essentially says that if we are at a state that is near the demonstration set, then there exists an action that can drive us closer to the demonstration set. This assumption rules out certain dynamics that does not allow corrections even after the policy making a small error. For example, if
3Recall that we assume that Ds0 has a low-dimensional support and thus typically U will also be a lowdimensional subset of the ambient space.
4Any tiebreaker can be used if there are multiple closest points.
a robot, unfortunately, falls off a cliff, then fundamentally it cannot recover itself — our algorithm cannot deal with such pathological situations.
Assumption 4.2 (Locally-correctable dynamics). For some γ ∈ (0, 1) and ε > 0, Lc > 0, we assume that the dynamics M? is (γ, Lc, ε)-locally-correctable w.r.t to the set U in the sense that for all ε0 ∈ (0, ε] and any tuple (s̄, ā, s̄′) satisfying s̄, s̄′ ∈ U and s̄′ = M?(s̄, ā), and any ε0-perturbation s of s̄ (that is, s ∈ Nε0(s̄)), there exists an action acx that is Lcε0 close to ā, such that it makes a correction in the sense that the resulting state s′ is γε0-close to the set U : s′ = M?(s, acx) ∈ Nγε0(U). Here Nδ(K) denotes the set of points that are δ-close to K.
Finally, we will assume the BC policy, the value function, and the dynamics are all Lipschitz in their arguments.5 We also assume the projection operator to the set U is locally Lipschitz. These are regularity conditions that provide loose local extrapolation of these functions, and they are satisfied by parameterized neural networks that are used to model these functions.
Assumption 4.3 (Lipschitz-ness of policy, value function, and dynamics). We assume that the policy πBC is Lπ-Lipschitz. That is, ‖πBC(s) − πBC(s̃)‖ ≤ Lπ‖s − s̃‖ for all s, s̃. We assume the value function V πe and the learned value function V are LV -Lipschitz, the model M? is LM,aLipschitz w.r.t to the action and LM,s-Lipschitz w.r.t to the state s. We also assume that the set U has LΠ-Lipschitz projection locally: for all s, ŝ that is ε-close to U , ‖ΠU (s)−ΠU (ŝ)‖ ≤ LΠ‖s− ŝ‖.
Under these assumptions, now we are ready to state our main theorem. It claims that 1) the induced policy π in Alg. 1 stays close to the demonstration set and performs similarly to the expert policy πe, and 2) following the induced policy π, we will arrive at a state with a near-optimal value.
Theorem 4.4. Suppose Assumption 4.1, 4.2, 4.3 hold with sufficiently small ε > 0 and errors δM , δπ,δπ > 0 so that they satisfy ζ ≥ Lcε + δπ + Lπ. Let λ be sufficiently large so that λ ≥ 2LV LΠLMζ+2δV +2LV δM
(1−γ)ε . Then, the policy π from equation (4.3) satisfies the following:
1. Starting from s0 ∈ U and executing policy π for T0 ≤ T steps, the resulting states s1, . . . , sT0 are all ε-close to the demonstrate states set U .
2. In addition, suppose the expert policy makes at least ρ improvement every step in the sense that for every s ∈ U , either V πe(M?(s, πe(s))) ≥ V πe(s) + ρ or M?(s, πe(s)) reaches the goal.6 Assume ε and δM , δV , δπ are small enough so that they satisfy ρ & ε+ δπ .
Then, the policy π will achieve a state sT with T ≤ 2|V πe(s0)|/ρ steps which is ε-close to a state s̄T with value at least V πe(sT ) & −(ε+ δπ).7
The proof is deferred to Section B. The first bullet follows inductively invoking the following lemma which states that if the current state is ε-close to U , then so is the next state. The proof of the Lemma is the most mathematically involved part of the paper and is deferred to the Section B. We demonstrate the key idea of the proof in Figure 2 and its caption.
Lemma 4.5. In the setting of Theorem 4.4, suppose s is ε-close to the demonstration states set U . Suppose U , and let a = π(s) and s′ = M?(s, a). Then, s′ is also ε-close to the set U .
We effectively represent the Q function by V (M(s, a)) in Alg. 1. We argue in Section A.1 that this helps address the degeneracy issue when there are random goal states (which is the case in our experiments.)
Discussion: can we learn conservatively-extrapolated Q-function? We remark that we do not expect a conservative-extrapolated Q-functions would be helpful. The fundamental idea here is to penalize the value of unseen states so that the policy can self-correct. However, to learn a Q function that induces self-correctable policies, we should encourage unseen actions that can correct the trajectory, instead of penalize them just because they are not seen before. Therefore, it is crucial that the penalization is done on the unseen states (or V ) but not the unseen actions (or Q).
5We note that technically when the reward function is R(s, a) = −1, the value function is not Lipschitz. This can be alleviated by considering a similar rewardR(s, a) = −α−β‖a‖2 which does not require additional information.
6ρ is 1 when the reward is always −1 before achieving the goal. 7Here & hides multiplicative constant factors depending on the Lipschitz parameters LM,a, LM,s, Lπ, LV .
Algorithm 2 Value Iteration on Demonstrations with Negative Sampling (VINS) 1: R ← demonstration trajectories . No environment interaction will be used 2: Initialize value parameters φ̄ = φ and model parameters θ randomly 3: for i = 1, . . . , T do 4: sample mini-batch B of N transitions (s, a, r, s′) fromR 5: update φ to minimize Ltd(φ;B) + Lns(φ;B) 6: update θ to minimize loss Lmodel(θ;B) 7: update target network: φ̄← φ̄+ τ(φ− φ̄) 8: 9: function POLICY(s) 10: Option 1: a = πBC(s); Option 2: a = 0 11: sample k noises ξ1, . . . , ξk from Uniform[−1, 1]m . m is the dimension of action space 12: i∗ = argmaxi Vφ(Mθ(s, a+ αξi)) . α > 0 is a hyper-parameter 13: return a+ αξi∗

heading: 5 MAIN APPROACH
text: Learning value functions with negative sampling from demonstration trajectories. As motivated in Section 4 by Algorithm 1 and Theorem 4.4, we first develop a practical method that can learn a value function with conservative extrapolation, without environment interaction. Let Vφ be a value function parameterized by φ. Using the standard TD learning loss, we can ensure the value function to be accurate on the demonstration states U (i.e., to satisfy equation (4.1)). Let φ̄ be the target value function,8 the TD learning loss is defined as Ltd(φ) = E(s,a,s′)∼ρπe [( r(s, a) + Vφ̄(s ′)− Vφ(s) )2]
where r(s, a) is the (sparse) reward, φ̄ is the parameter of the target network, ρπe is the distribution of the states-action-states tuples of the demonstrations. The crux of the ideas in this paper is to use a negative sampling technique to enforce the value function to satisfy conservative extrapolation requirement (4.2). It would be infeasible to enforce condition (4.2) for every s 6∈ U . Instead, we draw random “negative samples” s̃ from the neighborhood of U , and enforce the condition (4.2). This is inspired by the negative sampling approach widely used in NLP for training word embeddings Mikolov et al. (2013); Gutmann & Hyvärinen (2012). Concretely, we draw a sample s ∼ ρπe , create a random perturbation of s to get a point s̃ 6∈ U . and construct the following loss function:9
Lns(φ) = Es∼ρπe ,s̃∼perturb(s) ( Vφ̄(s)− λ‖s− s̃‖ − Vφ(s̃) )2 ,
The rationale of the loss function can be best seen in the situation when U is assumed to be a lowdimensional manifold in a high-dimensional state space. In this case, s̃ will be outside the manifold U with probability 1. Moreover, the random direction s̃− s is likely to be almost orthogonal to the tangent space of the manifold U , and thus s is a reasonable approximation of the projection of s̃ back to the U , and ‖s− s̃‖ is an approximation of ‖ΠU s̃− s̃‖. If U is not a manifold but a small subset of the state space, these properties may still likely to hold for a good fraction of s.
We only attempt to enforce condition (4.2) for states near U . This likely suffices because the induced policy is shown to always stay close to U . Empirically, we perturb s by adding a Gaussian noise. The loss function to learn Vφ is defined as L(φ) = Ltd(φ) + µLns(φ) for some constant µ > 0. For a mini-batch B of data, we define the corresponding empirical loss by L(φ;B) (similarly we define Ltd(φ;B) and Lns(φ;B)). The concrete iterative learning algorithm is described in line 1-7 of Algorithm 2 (except line 6 is for learning the dynamical model, described below.)
Learning the dynamical model. We use standard supervised learning to train the model. We use `2 norm as the loss for model parameters θ instead of the more commonly used MSE loss, following the success of (Luo et al., 2018): Lmodel(θ) = E(s,a,s′)∼ρπe [‖Mθ(s, a)− s′‖2] . Optimization for policy. We don’t maintain an explicit policy but use an induced policy from Vφ and Mθ by optimizing equation (4.3). A natural choice would be using projected gradient ascent to
8A target value function is widely used in RL to improve the stability of the training (Lillicrap et al., 2015; Mnih et al., 2015).
9With slight abuse of notation, we use ρπe to denote both the distribution of (s, a, s′) tuple and the distribution of s of the expert trajectories.
optimize equation (4.3). It’s also possible to use cross-entropy methods in (Kalashnikov et al., 2018) to optimize it. However, we found the random shooting suffices because the action space is relatively low-dimensional in our experiments. Moreover, the randomness introduced appears to reduce the overfitting of the model and value function slightly. As shown in line 10-13 of Alg. 2, we sample k actions in the feasible set and choose the one with maximum Vφ(Mθ(s, a)).
Value iteration with environment interaction. As alluded before, when more environment interactions are allowed, we initialize an RL algorithm by the value function, dynamics learned from VINS. Given that we have V and M in hand, we alternate between fitted value iterations for updating the value function and supervised learning for updating the models. (See Algorithm 3 in Section C.) We do not use negative sampling here since the RL algorithms already collect bad trajectories automatically. We also do not hallucinate any goals as in HER (Andrychowicz et al., 2017).

heading: 6 EXPERIMENTS
text: Environments. We evaluate our algorithms in three simulated robotics environments10 designed by (Plappert et al., 2018) based on OpenAI Gym (Brockman et al., 2016) and MuJoCo (Todorov et al., 2012): Reach, Pick-And-Place, and Push. A detailed description can be found in Section D.1.
Demonstrations. For each task, we use Hindsight Experience Replay (HER) (Andrychowicz et al., 2017) to train a policy until convergence. The policy rolls out to collect 100/200 successful trajectories as demonstrations except for Reach environment where 100 successful trajectories are sufficient for most of the algorithms to achieve optimal policy. We filtered out unsuccessful trajectories during data collection.
We consider two settings: imitation learning from only demonstrations data, and leveraging demonstration in RL with a limited amount of interactions. We compare our algorithm with Behavioral Cloning and multiple variants of our algorithms in the first setting. We compare with the previous state-of-the-art by Nair et al. (2018), and GAIL Ho & Ermon (2016) in the second setting. We do not compare with (Gao et al., 2018) because it cannot be applied to the case with continuous actions.
Behavioral Cloning (Bain & Sommut, 1999). Behavioral Cloning (BC) learns a mapping from a state to an action on demonstration data using supervised learning. We use MSE loss for predicting the actions.
Nair et al.’18 (Nair et al., 2018). The previous state-of-the-art algorithm from Nair et al. (2018) combines HER (Andrychowicz et al., 2017) with BC and a few techniques: 1) an additional replay buffer filled with demonstrations, 2) an additional behavioral cloning loss for the policy, 3) a Q-filter for non-optimal demonstrations, 4) resets to states in the demonstrations to deal with long horizon tasks. We note that reseting to an arbitrary state may not be realistic for real-world applications in robotics. In contrast, our algorithm does not require resetting to a demonstration state.
GAIL (Ho & Ermon, 2016) Generative Adversarial Imitation Learning (GAIL) imitates the expert by matching the state-action distribution with a GAN-like framework.
HER (Andrychowicz et al., 2017) Hindsight Experience Replay (HER) is the one of the best techniques that deal with sparse-reward environments with multiple goals and can be combined with any off-policy RL algorithm. The key idea is that HER extends the replay buffer by changing the goals. With reasonable chosen goals, the underlying off-policy RL algorihtm can receive more signals from the generated experience, making policy optimization more complete.
DAC (Kostrikov et al., 2018) Discriminator-Actor-Critic (DAC) is a sample-efficient imitation learning algorihtm built on the top of GAIL. It addresses the reward bias problem by adapting AIRL reward function and introducing an absorbing state. Furthermore, it replaces the underlying RL algorithm in GAIL by TD3 (Fujimoto et al., 2018b) to make it more sample efficient.
VINS. As described in Section 5, in the setting without environment interaction, we use Algorithm 2; otherwise we use it to initialize an RL algorithm (see Algorithm 3). We use neural networks to parameterize the value function and the dynamics model. The granularity of the HER demonstration policy is very coarse, and we argument the data with additional linear interpolation between consecutive states. We also use only a subset of the states as inputs to the value function and the dynamics model,
10Available at https://github.com/openai/gym/tree/master/gym/envs/robotics.
which apparently helps improve the training and generalization of them. Implementation details can be found in Section D.2.
Our main results are reported in Table 1 11 for the setting with no environment interaction and Figure 3 for the setting with environment interactions. Table 1 shows that the Reach environment is too simple so that we do not need to run the RL algorithm. On the harder environments Pick-And-Place and Push, our algorithm VINS outperforms BC. We believe this is because our conservatively-extrapolated value function helps correct the mistakes in the policy. Here we use 2k trials to estimate the success rate (so that the errors in the estimation is negligible), and we run the algorithms with 10 different seeds. The error bars are for 1 standard error.
Figure 3 shows that VINS initialized RL algorithm outperforms prior state-of-the-art in sample efficiency. We believe the main reason is that due to the initialization of value and model, we pay less samples for warming up the value function. We note that our initial success rate in RL is slightly lower than the final result of VINS in Table 1. This is because in RL we implemented a slightly worse variant of the policy induced by VINS: in the policy of Algorithm 2, we use option 2 to search the action uniformly. This suffices because the additional interactions quickly allows us to learn a good model and the BC constraint is no longer needed.
Ablation studies. Towards understanding the effect of each component of VINS, we perform three ablative experiments to show the importance of negative sampling, searching in the neighborhood of Behavioral Cloned actions (option 1 in line 10 or Algorithm 2), and a good dynamics model. The results are shown in Table 2. We study three settings: (1) VINS without negative sampling (VINS w/o NS), where the loss Lns is removed; (2) VINS without BC (VINS w/o BC), where option 2 in line 10 or Algorithm 2 is used; (3) VINS with oracle model without BC (VINS w/ oracle w/o BC), where we use the true dynamics model to replace line 12 of Algorithm 2. Note that the last setting is only synthetic for ablation study because in the real-world we don’t have access to the true dynamics model. Please see the caption of Table 2 for more interpretations. We use the same set of hyperparameters for the same environment, which may not be optimal: for example, with more expert trajectories, the negative sampling loss Lns, which can be seen as a regularziation, should be assigned a smaller coefficient µ.

heading: 7 CONCLUSION
text: We devise a new algorithm, VINS, that can learn self-correctable by learning value function and dynamical model from demonstrations. The key idea is a theoretical formulation of conservativelyextrapolated value functions that provably leads to self-correction. The empirical results show a promising performance of VINS and an algorithm that initializes RL with VINS. It’s a fascinating direction to study other algorithms that may learn conservatively-extrapolated value functions in
11The standard error in the paper means the standard error of average success rate over 10 (100 for Reach 10) different random seeds by the same algorithm, that is, the standard deviation of 10 numbers over √ 10 (or 10, respectively). 12The curve for Nair et al.’s only starts after a few thousands steps because the code we use https: //github.com/jangirrishabh/Overcoming-exploration-from-demos only evaluates after the first epoch.
other real-world applications beyond the proof-of-concepts experiments in this paper. For example, the negative sampling by Gaussian perturbation technique in this paper may not make sense for high-dimensional pixel observation. The negative sampling can perhaps be done in the representation space (which might be learned by unsupervised learning algorithms) so that we can capture the geometry of the state space better.

heading: A DEGENERACY OF LEARNING Q FUNCTIONS FROM DEMONSTRATIONS AND OUR SOLUTIONS
text: Fitting Qπe from only demonstration is problematic: there exists a function Q(s, a) that does not depend on a at all, which can still match Qπe on all possible demonstration data. Consider Q(s, a) , Qπe(s, πe(s)). We can verify that for any (s, a) pair in the demonstrations satisfying a = πe(s), it holds that Q(s, a) = Qπe(s, a). However, Q(s, a) cannot be accurate for other choices of a’s because by its definition, it does not use any information from the action a.
A.1 COPING WITH THE DEGENERACY WITH LEARNED DYNAMICAL MODEL
Cautious reader may realize that the degeneracy problem about learning Q function from demonstrations with deterministic policies may also occur with learning the model M . However, we will show that when the problem has the particular structure of reaching a random but given goal state g, learning Q still suffers the degeneracy but learning the dynamics does not.
The typical way to deal with a random goal state g is to consider goal-conditioned value function V (s, g), policy π(s, g), and Q function Q(s, a, g).13 However, the dynamical model does not have to condition on the goal. Learning Q function still suffers from the degeneracy problem because Q(s, a, g) , Qπe(s, πe(s, g), g) matches Qπe on the demonstrations but does not use the information from a at all. However, learning M does not suffer from such degeneracy because given a single state s in the demonstration, there is still a variety of action a that can be applied to state s because there are multiple possible goals g. (In other words, we cannot construct a pathological M(s, a) = M?(s, πe(s)) because the policy also takes in g as an input). As a result, parameterizing Q by Q(s, a, g) = V (M(s, a), g) do not suffer from the degeneracy either.

heading: B MISSING PROOFS IN SECTION 4
text: Proof of Lemma 4.5. Let s̄ = ΠUs and ā = πe(s̄). Because s is ε-close to the set U , we have ‖s− s̄‖ ≤ ε. By the (γ, Lc, ε)-locally-correctable assumption of the dynamics, we have that there exists an action acx such that a) ‖acx − ā‖ ≤ Lcε and b) s′cx , M?(s, acx) is γε-close to the set U . Next we show that acx belongs to the constraint set {a : ‖a− πBC(s)‖ ≤ ζ} in equation (4.3). Note that ‖acx−πBC(s)‖ ≤ ‖acx− ā‖+‖ā−πBC(s̄)‖+‖πBC(s̄)−πBC(s)‖ ≤ Lcε+δπ+Lπε because of triangle inequality, the closeness of acx and ā, the assumption that πBC has δ error in the demonstration state set U , and the Lipschitzness of πBC. Since ζ is chosen to be bigger than Lcε+ δπ + Lπε, we conclude that acx belongs to the constraint set of the optimization in equation (4.3).
This suggests that the maximum value of the optimization (4.3) is bigger than the corresponding value of acx:
V (M(s, a)) ≥ V (M(s, acx)) (B.1)
Note that a belongs to the constraint set by definition and therefore ‖a−acx‖ ≤ 2ζ . By Lipschitzness of the dynamical model, and the value function V πe , we have that ‖M?(s, a) −M?(s, acx)‖ ≤ LM‖a − acx‖ ≤ 2LMζ. Let s′ = M?(s, a) and s′cx = M?(s, acx). We have ‖s′ − s′cx‖ ≤ 2LMζ. By the Lipschitz projection assumption, we have that ‖ΠUs′−ΠUs′cx‖ ≤ LΠ‖s′− s′cx‖ ≤ 2LΠLMζ , which in turns implies that |V πe(ΠUs′)− V πe(ΠUs′cx)| ≤ 2LV LΠLMζ by Lipschitzness of V πe . It follows that
V (s′) ≤ V πe(ΠUs′)− λ‖s′ −ΠUs′‖+ δV (by assumption (4.1)) ≤ V πe(ΠUs′cx) + |V πe(ΠUs′cx)− V πe(ΠUs′)| − λ‖s′ −ΠUs′‖+ δV
(by triangle inequality)
≤ V πe(ΠUs′cx) + 2LV LΠLMζ − λ‖s′ −ΠUs′‖+ δV (by equations in paragraph above) ≤ V (s′cx) + λ‖s′cx −Πs′cx‖+ 2LV LΠLMζ − λ‖s′ −ΠUs′‖+ 2δV (by assumption (4.2))
Note that by the Lipschitzness of the value function and the assumption on the error of the dynamical model,
|V (s′)− V (M(s, a))| = |V (M?(s, a))− V (M(s, a))| ≤ Lv‖M?(s, a)−M(s, a)‖ ≤ LV δM (B.2)
Simlarly
|V (s′cx)− V (M(s, acx))| = |V (M?(s, acx))− V (M(s, acx))| ≤ Lv‖MT ?(s, acx)−M(s, acx)‖ ≤ LV δM (B.3)
13This is equivalent to viewing the random goal g as part of an extended state s̆ = (s, g). Here the second part of the extended state is randomly chosen during sampling the initial state, but never changed by the dynamics. Thus all of our previous work does apply to this situation via this reduction.
Combining the three equations above, we obtain that
λ‖s′cx −Πs′cx‖+ 2LV LΠLMζ − λ‖s′ −ΠUs′‖+ 2δV ≥ V (s′)− V (s′cx) ≥ V (M(s, a))− V (M(s, acx))− 2LV δM (by equation (B.2) and (B.3)) ≥ −2LV δM (by equation (B.1))
Let κ = 2LV LΠLMζ + 2δV + 2LV δM and use the assumption that s′cx is γε-close to the set U (which implies that ‖s′cx −Πs′cx‖ ≤ γε), we obtain that
λ‖s′ −ΠUs′‖ ≤ λ‖s′cx −Πs′cx‖+ κ ≤ λγε+ κ (B.4)
Note that λ ≥ κ(1−γ)ε , we have that ‖s ′ −ΠUs′‖ ≤ ε.
Proof of Theorem 4.4. To prove bullet 1, we apply Lemma 4.5 inductively for T steps. To prove bullet 2, we will prove that as long as si is ε-close to U , then we can improve the value function by at least ρ−? in one step. Consider s̄i = ΠU (si). We triangle inequality, we have that ‖π(si)− πe(s̄i)‖ ≤ ‖π(si) − πBC(si)‖ + ‖πBC(si) − πBC(s̄i)‖ + ‖πBC(s̄i) − πe(s̄i)‖. These three terms can be bounded respectively by ζ, Lπ‖si − s̄i‖ ≤ Lπε, and δπ, using the definition of π, the Lipschitzness of πBC, and the error assumption of πBC on the demonstration state set U , respectively. It follows that ‖M?(si, π(si)) −M?(s̄i, πe(s̄i))‖ ≤ LM,s‖si − s̄i‖ + LM,a‖π(si) − πe(s̄i)‖ ≤ LM,sε+ LM,a(ζ + Lπε+ δπ). It follows by the Lipschitzness of the projection that
‖s̄i+1 −ΠUM?(s̄i, πe(s̄i))‖ = ‖ΠUM?(si, π(si))−ΠUM?(s̄i, πe(s̄i))‖ (B.5) = |ΠUM?(si, π(si))−M?(s̄i, πe(s̄i)) (B.6) ≤ LΠ(LM,sε+ LM,a(ζ + Lπε+ δπ)) (B.7)
This implies that
|V πe(s̄i+1)− V πe(ΠUM?(s̄i, πe(s̄i))| ≤ LV LΠ(LM,sε+ LM,a(ζ + Lπε+ δπ)) (B.8)
Note that we assumed that V (M?(s̄i, πe(s̄i)) ≥ V (s̄i) + ρ or M?(s̄i, πe(s̄i)) reaches the goal. If the former, it follows that V πe(s̄i+1) ≥ V πe(s̄i) + ρ − LV LΠ(LM,sε + LM,a(ζ + Lπε + δπ)) ≥ V πe(s̄i) + ρ/2. Otherwise, or si+1 is ε-close to s̄i+1 whose value is at most −LV LΠ(LM,sε + LM,a(ζ + Lπε+ δπ)) = −O(ε+ δπ)

heading: C ALGORITHMS VINS+RL
text: A pseudo-code our algorithm VINS+RL can be found in Algorithm 3
Algorithm 3 Value Iteration with Environment Interactions Initialized by VINS (VINS+RL) Require: Initialize parameters φ, θ from the result of VINS (Algorithm 2)
1: R ← demonstration trajectories; 2: for stage t = 1, . . . do 3: collect n1 samples using the induced policy π in Algorithm 2 (with Option 2 in Line 10) and
add them toR 4: for i = 1, . . . , ninner do 5: sample mini-batch B of N transitions (s, a, r, s′) fromR 6: update φ to minimize Ltd(φ;B) 7: update target value network: φ̄← φ̄+ τ(φ− φ̄) 8: update θ to minimize loss Lmodel(θ;B)
D IMPLEMENTATION DETAILS
D.1 SETUP
In the three environments, a 7-DoF robotics arm is manipulated for different goals. In Reach, the task is to reach a randomly sampled target location; In Pick-And-Place, the goal is to grasp a box in a table and reach a target location, and in Push, the goal is to push a box to a target location.
The reward function is 0 if the goal is reached; otherwise -1. Intuitively, an optimal agent should complete the task in a shortest possible path. The environment will stop once the agent achieves the goal or max step number have been reached. Reaching max step will be regarded as failure.
For more details, we refer the readers to (Plappert et al., 2018).
D.2 HYPERPARAMETERS
Behavioral Cloning We use a feed-forward neural network with 3 hidden layers, each containinig 256 hidden units, and ReLU activation functions. We train the network until the test success rate plateaus.
Nair et al.’18 (Nair et al., 2018) We use the implementation from https://github.com/ jangirrishabh/Overcoming-exploration-from-demos. We don’t change the default hyperparameters, except that we’re using 17 CPUs.
GAIL (Ho & Ermon, 2016) We use the implementation from OpenAI Baselines (Dhariwal et al., 2017). We don’t change the default hyperparameters.
HER (Andrychowicz et al., 2017) We also use the code from OpenAI Baselines and keep the default hyperparameters.
Discriminator-Actor-Critic (Kostrikov et al., 2018) We use the implementation from the official implementation https://github.com/google-research/google-research/ tree/master/dac.
VINS
• Architecture: We use feed-forward neural networks as function approximators for values and dynamical models. For the Vφ, the network has one hidden layer which has 256 hidden units and a layer normalization layer (Lei Ba et al., 2016). The dynamics model is a feed-forward neural network with two hidden layers and ReLU activation function. Each hidden layer has 500 units. The model uses the reduced states and actions to predict the next reduced states.
• Value augmentation: We augment the dataset by a linear interpolation between two consecutive states, i.e., for a transition (s, a, r, s′) in the demonstration, it’s augmented to (s+ λ(s′ − s), a, λr, s′) for a random real λ ∼ Uniform[0, 1]. To minimize the losses, we use the Adam optimizer Kingma & Ba (2014) with learning rate 3 × 10−4. We remove some less relevant coordinates from the state space to make the dimension smaller. (But we maintain the full state space for BC. BC will perform worse with reduce state space.) Specifically, the states of our algorithm for different environment are a) Reach: the position of the arm, b) Pick: the position of the block, the gripper, and the arm, and c) Push: the position of the block and the arm.
• States representation and perturbation: Both our model M and value function V are trained on the space of reduced states. The perturb function is also designed separately for each task. For Reach and Push, we perturb the arm only; For Pick-And-Place, we perturb the arm or the gripper. In the implementation, we perturb the state s by adding Gaussian noise from a distribution N (0, ρΣ), where Σ is a diagonal matrix that contains the variances of each coordinate of the states from the demonstration trajectories. Here ρ > 0 is a hyper-parameter to tune.

heading: E ADDITIONAL EXPERIMENTS
text: We have some additional experiments to evaluate VINS, which are (a) BC with data augmentation (b) VINS with oracle without negative sampling, which are explained below. The results are summarized in Table 3.
BC w/ data augmentation. As VINS augments the data to train the value function, it might be interesting to see the performance of BC w/ data augmentation to make the comparison more fair. The way we augment the data is similar to what we have done for the value function: Given two consecutive state-action pairs (s, a) and (s′, a′), where s′ = M(s, a), we sample t ∼ Uniform[0, 1] and construct a new pair (ts+ (1− t)s′, ta+ (1− t)a′). The new pair is used for behavior cloning. However, we found out that this kind of data augmentation hurts. We hypothesize that the augmented data provide incorrect information, as the actions between two consecutive states might be very non-linear, while value is more linear. We suspect that the biases/errors introduced by the data augmentation is particularly harmful for BC, because it lacks a mechanism of self-correction that VINS has.
VINSw/ oracle w/o negative sampling. Another way to isolatethe effect of negative sampling is comparing VINS w/ oracle w/o NS to VINS w/ oracle. The results are shown at Table 3. We can see that VINS w/ oracle achieves a significantly higher success rate than VINS w/ oracle w/o negative sampling, which shows that negative sampling is essential to the success of VINS.
VINS with fewer demonstrations. To evaluate whether VINS works with few demonstrations, we also conduct our experiments wih only 40 expert trajectories. The result is shown in Table 4. The performance of BC is worse than that with 100 expert trajectories, VINS can still correct some actions via learned value function and model and achieves a higher success rate.
VINS with stochatic dynamics model. As this paper mainly studies deterministic dynamics model, we’d like to note that our theory can be generalized to stochastic dynamics model easily. We also conduct proof-of-concept experiments to show the performance of VINS in this case. The stochastic environment we used in the experiments is based on Push, and the modification is that the dynamics model adds noises to the received actions, i.e., s′ ∼M(s, a+ ζ) where ζ ∼ N (0, σ2I), M here is the original deterministic dynamics model. One intuitive interpretation is that the actuator on the robot might not be good enough to produce the exact forces. For simplicity we don’t train a stochastic dynamics model but learn a deterministic one to approximate it. The result is summarized in Table 4, in which we can find even with a determinisic dynamics model, VINS performs better than BC.

Review summaries:
This paper tackles an issue imitation learning approaches face. More specifically, policies learned in this manner can often fail when they encounter new states not seen in demonstrations. The paper proposes a method for learning value functions that are more conservative on unseen states, which encourages the learned policies to stay within the distribution of training states. Theoretical results are derived to provide some support for the approach. A practical algorithm is also presented and experiments on continuous control tasks display the effectiveness of the method, with particularly good results on imitation learning followed by reinforcement learning.

This work presents the value iteration with negative sampling (VINS) algorithm, a method for accelerating reinforcement learning using expert demonstrations.  In addition to learning an expert policy through behavioral cloning, VINS learns an initial value function which is biased to assign smaller expected values to states not encountered during demonstrations.  This is done by augmenting the demonstration data with states that have been randomly perturbed, and penalizing the value targets for these states by a factor proportional to their Euclidean distance to the original state.  In addition to the policy and value function, VINS also learns a one-step dynamics model used to select actions against the learned value function.  As the value function learned in VINS is only defined with respect to the current state, action values are estimated by sampling future states using the learned model, and computing the value of these sampled states.