Sample Efficient Path Integral Control under Uncertainty

We present a data-driven optimal control framework that can be viewed as a generalization of the path integral (PI) control approach. We find iterative feedback control laws without parameterization based on probabilistic representation of learned dynamics model. The proposed algorithm operates in a forward-backward manner which differentiate from other PI-related methods that perform forward sampling to find optimal controls. Our method uses significantly less samples to find optimal controls compared to other approaches within the PI control family that relies on extensive sampling from given dynamics models or trials on physical systems in model-free fashions. In addition, the learned controllers can be generalized to new tasks without re-sampling based on the compositionality theory for the linearly-solvable optimal control framework. We provide experimental results on three different systems and comparisons with state-of-the-art model-based methods to demonstrate the efficiency and generalizability of the proposed framework.


Introduction
Stochastic optimal control (SOC) is a general and powerful framework with applications in many areas of science and engineering. However, despite the broad applicability, solving SOC problems remains challenging for systems in high-dimensional continuous state action spaces. Various function approximation approaches to optimal control are available [1,2] but usually sensitive to model uncertainty. Over the last decade, SOC based on exponential transformation of the value function has demonstrated remarkable applicability in solving real world control and planning problems. In control theory the exponential transformation of the value function was introduced in [3,4]. In the recent decade it has been explored in terms of path integral interpretations and theoretical generalizations [5,6,7,8], discrete time formulations [9], and scalable RL/control algorithms [10,11,12,13,14]. The resulting stochastic optimal control frameworks are known as Path Integral (PI) control for continuous time, Kullback Leibler (KL) control for discrete time, or more generally Linearly Solvable Optimal Control [9,15].
One of the most attractive characteristics of PI control is that optimal control problems can be solved with forward sampling of Stochastic Differential Equations (SDEs). While the process of sampling with SDEs is more scalable than numerically solving partial differential equations, it still suffers from the curse of dimensionality when performed in a naive fashion. One way to circumvent this problem is to parameterize policies [10,11,14] and then perform optimization with sampling. However, in this case one has to impose the structure of the policy a-priori, therefore restrict the possible optimal control solutions within the assumed parameterization. In addition, the optimized policy parameters can not be generalized to new tasks. In general, model-free PI policy search approaches require a large number of samples from trials performed on real physical systems. The issue of sample inefficiency further restricts the applicability of PI control methods on physical systems with unknown or partially known dynamics.
Motivated by the aforementioned limitations, in this paper we introduce a sample efficient, modelbased approach to PI control. Different from existing PI control approaches, our method combines the benefits of PI control theory [5,6,7] and probabilistic model-based reinforcement learning methodologies [16,17]. The main characteristics of the our approach are summarized as follows • It extends the PI control theory [5,6,7] to the case of uncertain systems. The structural constraint is enforced between the control cost and uncertainty of the learned dynamics, which can be viewed as a generalization of previous work [5,6,7]. • Different from parameterized PI controllers [10,11,14,8], we find analytic control law without any policy parameterization. • Rather than keeping a fixed control cost weight [5,6,7,10,18], or ignoring the constraint between control authority and noise level [11], in this work the control cost weight is adapted based on the explicit uncertainty of the learned dynamics model. • The algorithm operates in a different manner compared to existing PI-related methods that perform forward sampling [5,6,7,10,18,11,12,14,8]. More precisely our method perform successive deterministic approximate inference and backward computation of optimal control law. • The proposed model-based approach is significantly more sample efficient than samplingbased PI control [5,6,7,18]. In RL setting our method is comparable to the state-of-the-art RL methods [17,19] in terms of sample and computational efficiency. • Thanks to the linearity of the backward Chapman-Kolmogorov PDE, the learned controllers can be generalized to new tasks without re-sampling by constructing composite controllers. In contrast, most policy search and trajectory optimization methods [10,11,14,17,19,20,21,22] find policy parameters that can not be generalized.

Problem formulation
We consider a nonlinear stochastic system described by the following differential equation with state x ∈ R n , control u ∈ R m , and standard Brownian motion noise ω ∈ R p with variance Σ ω . f (x) is the unknown drift term (passive dynamics), G(x) ∈ R n×m is the control matrix and B ∈ R n×p is the diffusion matrix. Given some previous control u old , we seek the optimal control correction term δu such that the total control u = u old + δu. The original system becomes In this work we assume the dynamics based on the previous control can be represented by Gaussian processes (GP) such that where f GP is the GP representation of the biased drift termf under the previous control. Now the original dynamical system (1) can be represented as follow where µ f , Σ f are predictive mean and covariance functions, respectively. For the GP model we use a prior of zero mean and covariance function K( ω , with σ s , σ ω , W the hyper-parameters. δ ij is the Kronecker symbol that is one iff i = j and zero otherwise. Samples over f GP can be drawn using an vector of i.i.d. Gaussian variable Ω where L f is obtained using Cholesky factorization such that Σ f = L f L T f . Note that generally Ω is an infinite dimensional vector and we can use the same sample to represent uncertainty during learning [23]. Without loss of generality we assume Ω to be the standard zero-mean Brownian motion. For the rest of the paper we use simplified notations with subscripts indicating the time step. The discrete-time representation of the system is x t+dt = x t +µ f t +G t δu t dt+L f t Ω t √ dt, and the conditional probability of x t+dt given x t and δu t is a Gaussian p x t+dt |x t , δu t = N µ t+dt , Σ t+dt , where µ t+dt = x t + µ f t + G t δu t and Σ t+dt = Σ f t . In this paper we consider a finite-horizon stochastic optimal control problem is a statedependent positive definite weight matrix. Next we show the linearized Hamilton-Jacobi-Bellman equation for this class of optimal control problems.

Linearized Hamilton-Jacobi-Bellman equation for uncertain dynamics
At each iteration the goal is to find the optimal control update δu t that minimizes the value function (5) is the Bellman equation. By approximating the integral for a small dt and applying Itô's rule we obtain the Hamilton-Jacobi-Bellman (HJB) equation (detailed derivation is skipped): To find the optimal control update, we take gradient of the above expression (inside the parentheses) with respect to δu t and set to 0. This yields Inserting this expression into the HJB equation yields the following nonlinear and second order PDE In order to solve the above PDE we use the exponential transformation of the value function The corresponding partial derivatives can be found as Inserting these terms to (6) results in Tr(∇xxΨtΣ f t ).
The quadratic terms ∇ x Ψ t will cancel out under the assumption of This constraint is different from existing works in path integral control [5,6,7,10,18,8] where the constraint is enforced between the additive noise covariance and control authority, more precisely The new constraint enables an adaptive update of control cost weight based on explicit uncertainty of the learned dynamics. In contrast, most existing works use a fixed control cost weight [5,6,7,10,18,12,14,8]. This condition also leads to more exploration (more aggressive control) under high uncertainty and less exploration with more certain dynamics. Given the aforementioned assumption, the above PDE is simplified as subject to the terminal condition Ψ T = exp(− 1 λ q T ). The resulting Chapman-Kolmogorov PDE (7) is linear. In general, solving (7) analytically is intractable for nonlinear systems and cost functions. We apply the Feynman-Kac formula which gives a probabilistic representation of the solution of the linear PDE (7) where τ t is the state trajectory from time t to T . The optimal control is obtained as Rather than computing ∇ x Ψ t and Ψ t , the optimal controlû t can be approximated based on path costs of sampled trajectories. Next we briefly review some of the existing approaches.

Related works
According to the path integral control theory [5,6,7,10,18,8], the stochastic optimal control problem becomes an approximation problem of a path integral (8). This problem can be solved by forward sampling of the uncontrolled (u = 0) SDE (1). The optimal controlû t is approximated based on path costs of sampled trajectories. Therefore the computation of optimal controls becomes a forward process. More precisely, when the control and noise act in the same subspace, the optimal control can be evaluated as the weighted average of the noiseû is defined as the path cost computed by performing forward sampling. However, these approaches require a large amount of samples from a given dynamics model, or extensive trials on physical systems when applied in model-free reinforcement learning settings. In order to improve sample efficiency, a nonparametric approach was developed by representing the desirability Ψ t in terms of linear operators in a reproducing kernel Hilbert space (RKHS) [12]. As a model-free approach, it allows sample re-use but relies on numerical methods to estimate the gradient of desirability, i.e., ∇ x Ψ t , which can be computationally expensive. On the other hand, computing the analytic expressions of the path integral embedding is intractable and requires exact knowledge of the system dynamics. Furthermore, the control approximation is based on samples from the uncontrolled dynamics, which is usually not sufficient for highly nonlinear or underactuated systems.
Another class of PI-related method is based on policy parameterization. Notable approaches include PI 2 [10], PI 2 -CMA [11], PI-REPS [14] and recently developed state-dependent PI [8]. The limitations of these methods are: 1) They do not take into account model uncertainty in the passive dynamics f (x). 2) The imposed policy parameterizations restrict optimal control solutions. 3) The optimized policy parameters can not be generalized to new tasks. A brief comparison of some of these methods can be found in Table 1. Motivated by the challenge of combining sample efficiency and generalizability, next we introduce a probabilistic model-based approach to compute the optimal control (9) analytically. PI [5,6,7]

Analytic path integral control: a forward-backward scheme
In order to derive the proposed framework, firstly we learn the function f GP (x t ) =f (x, u old )dt + Bdω from sampled data. Learning the continuous mapping from state to state transition can be viewed as an inference with the goal of inferring the state transition dx t = f GP (x t ). The kernel function has been defined in Sec.2.1, which can be interpreted as a similarity measure of random variables. More specifically, if the training input x i and x j are close to each other in the kernel space, their outputs dx i and dx j are highly correlated. Given a sequence of states {x 0 , . . . x T }, and the corresponding state transition {dx 0 , . . . , dx T }, the posterior distribution can be obtained by conditioning the joint prior distribution on the observations. In this work we make the standard assumption of independent outputs (no correlation between each output dimension).
To propagate the GP-based dynamics over a trajectory of time horizon T we employ the moment matching approach [24,17] to compute the predictive distribution. Given an input distribution over the state N (µ t , Σ t ), the predictive distribution over the state at t + dt can be approximated as a Gaussian p(x t+dt ) ≈ N (µ t+dt , Σ t+dt ) such that The above formulation is used to approximate one-step transition probabilities over the trajectory. Details regarding the moment matching method can be found in [24,17]. All mean and variance terms can be computed analytically. The hyper-parameters σ s , σ ω , W are learned by maximizing the log-likelihood of the training outputs given the inputs [25]. Given the approximation of transition probability (10), we now introduce a Bayesian nonparametric formulation of path integral control based on probabilistic representation of the dynamics. Firstly we perform approximate inference (forward propagation) to obtain the Gaussian belief (predictive mean and covariance of the state) over the trajectory. Since the exponential transformation of the state cost exp(− 1 λ q(x)dt) is an unnormalized Gaussian N (x d , 2λ dt Q −1 ). We can evaluate the following integral analytically for j = t+dt, ..., T . Thus given a boundary condition Ψ T = exp(− 1 λ q T ) and predictive distribution at the final step N (µ T , Σ T ), we can evaluate the one-step backward desirability Ψ T −dt analytically using the above expression (11). More generally we use the following recursive rule for j = t + dt, ..., T − dt. Since we use deterministic approximate inference based on (10) instead of explicitly sampling from the corresponding SDE, we approximate the conditional distribution p(x j |x j−dt ) by the Gaussian predictive distribution N (µ j , Σ j ). Therefore the path integral We evaluate the desirability Ψ t backward in time by successive computation using the above recursive expression. The optimal control lawû t (9) requires gradients of the desirability function with respect to the state, which can be computed backward in time as well. For simplicity we denote the function Φ(x j , Ψ j ) by Φ j . Thus we compute the gradient of the recursive expression (13) where j = t + dt, ..., T − dt. Given the expression in (11) we compute the gradient terms in (14) as ∇xΦj = dΦj dp(xj) dp(xj) The term ∇ x Ψ T −dt is compute similarly. The partial derivatives can be computed analytically as in [17]. We compute all gradients using this scheme without any numerical method (finite differences, etc.). Given Ψ t and ∇ x Ψ t , the optimal control takes a analytic form as in eq.(9). Since Ψ t and ∇ x Ψ t are explicit functions of x t , the resulting control law is essentially different from the feedforward control in sampling-based path integral control frameworks [5,6,7,10,18] as well as the parameterized state feedback PI control policies [14,8]. Notice that at current time step t, we update the control sequenceû t,...,T using the presented forward-backward scheme. Onlyû t is applied to the system to move to the next step, while the controlsû t+dt,...,T are used for control update at future steps. The transition sample recorded at each time step is incorporated to update the GP model of the dynamics. A summary of the proposed algorithm is shown in Algorithm 1.

Generalization to unlearned tasks without sampling
In this section we describe how to generalize the learned controllers for new (unlearned) tasks without any interaction with the real system. The proposed approach is based on the compositionality theory [26] in linearly solvable optimal control (LSOC). We use superscripts to denote previously learned task indexes. Firstly we define a distance measure between the new targetx d and old targets x dk , k = 1, .., K, i.e., a Gaussian kernel where P is a diagonal matrix (kernel width). The composite terminal costq(x T ) for the new task becomesq where q k (x T ) is the terminal cost for old tasks. For conciseness we define a normalized distance measureω k = ω k K k=1 ω k , which can be interpreted as a probability weight. Based on (16) we have the composite terminal desirability for the new task which is a linear combination of Ψ k Since Ψ k t is the solution to the linear Chapman-Kolmogorov PDE (7), the linear combination of desirability (17) holds everywhere from t to T as long as it holds on the boundary (terminal time step). Therefore we obtain the composite control The composite control law in (18) is essentially different from an interpolating control law [26]. It enables sample-free controllers that constructed from learned controllers for different tasks. This scheme can not be adopted in policy search or trajectory optimization methods such as [10,11,14,17,19,20,21,22]. Alternatively, generalization can be achieved by imposing task-dependent policies [27]. However, this approach might restrict the choice of optimal controls given the assumed structure of control policy.

Experiments and Analysis
We consider 3 simulated RL tasks: cart-pole (CP) swing up, double pendulum on a cart (DPC) swing up, and PUMA-560 robotic arm reaching. The CP and DPC systems consist of a cart and a single/double-link pendulum. The tasks are to swing-up the single/double-link pendulum from the initial position (point down). Both CP and DPC are under-actuated systems with only one control acting on the cart. PUMA-560 is a 3D robotic arm that has 12 state dimensions, 6 degrees of freedom with 6 actuators on the joints. The task is to steer the end-effector to the desired position and orientation.
In order to demonstrate the performance, we compare the proposed control framework with three related methods: iterative path integral control [18] with known dynamics model, PILCO [17] and PDDP [19]. Iterative path integral control is a sampling-based stochastic control method. It is based on importance sampling using controlled diffusion process rather than passive dynamics used in standard path integral control [5,6,7]. Iterative PI control is used as a baseline with a given dynamics model. PILCO is a model-based policy search method that features state-of-the-art data efficiency in terms of number of trials required to learn a task. PILCO requires an extra optimizer (such as BFGS) for policy improvement. PDDP is a Gaussian belief space trajectory optimization approach. It performs dynamic programming based on local approximation of the learned dynamics and value function. Both PILCO and PDDP are applied with unknown dynamics. In this work we do not compare our method with model-free PI-related approaches such as [10,11,12,14] since these methods would certainly cost more samples than model-based methods such as PILCO and PDDP. The reason for choosing these two methods for comparison is that our method adopts a similar model learning scheme while other state-of-the-art methods, such as [20] is based on a different model.
In experiment 1 we demonstrate the sample efficiency of our method using the CP and DPC tasks.
For both tasks we choose T = 1.2 and dt = 0.02 (60 time steps per rollout). The iterative PI [18] with a given dynamics model uses 10 3 /10 4 (CP/DPC) sample rollouts per iteration and 500 iterations at each time step. We initialize PILCO and the proposed method by collecting 2/6 sample rollouts (corresponding to 120/360 transition samples) for CP/DPC tasks respectively. At each trial (on the true dynamics model), we use 1 sample rollout for PILCO and our method. PDDP uses 4/5 rollouts (corresponding to 240/300 transition samples) for initialization as well as at each trial for the CP/DPC tasks. Fig. 1 shows the results in terms of Ψ T and computational time. For both tasks our method shows higher desirability (lower terminal state cost) at each trial, which indicates higher sample efficiency for task learning. This is mainly because our method performs online reoptimization at each time step. In contrast, the other two methods do not use this scheme. However we assume partial information of the dynamics (G matrix) is given. PILCO and PDDP perform optimization on entirely unknown dynamics. In many robotic systems G corresponds to the inverse of the inertia matrix, which can be identified based on data as well. In terms of computational efficiency, our method outperforms PILCO since we compute the optimal control update analytically, while PILCO solves large scale nonlinear optimization problems to obtain policy parameters. Our method is more computational expensive than PDDP because PDDP seeks local optimal controls that rely on linear approximations, while our method is a global optimal control approach. Despite the relatively higher computational burden than PDDP, our method offers reasonable efficiency in terms of the time required to reach the baseline performance.
In experiment 2 we demonstrate the generalizability of the learned controllers to new tasks using the composite control law (18) based on the PUMA-560 system. We use T = 2 and dt = 0.02 (100 time steps per rollout). First we learn 8 independent controllers using Algorithm 1. The target postures are shown in Fig. 2. For all tasks we initialize with 3 sample rollouts and 1 sample at each trial. Blue bars in Fig. 2b shows the desirabilities Ψ T after 3 trials. Next we use the composite law (18) to construct controllers without re-sampling using 7 other controllers learned using Algorithm 1. For instance the composite controller for task#1 is found The performance comparison of the composite controllers with controllers learned from trials is shown in Fig. 2. It can be seen that the composite controllers give close performance as independently learned controllers. The compositionality theory [26] generally does not apply to policy search methods and trajectory optimizers such as PILCO, PDDP, and other recent methods [20,21,22]. Our method benefits from the compositionality of control laws that can be applied for multi-task control without re-sampling.

Conclusion and Discussion
We presented an iterative learning control framework that can find optimal controllers under uncertain dynamics using very small number of samples. This approach is closely related to the family of path integral (PI) control algorithms. Our method is based on a forward-backward optimization scheme, which differs significantly from current PI-related approaches. Moreover, it combines the attractive characteristics of probabilistic model-based reinforcement learning and linearly solvable optimal control theory. These characteristics include sample efficiency, optimality and generalizability. By iteratively updating the control laws based on probabilistic representation of the learned dynamics, our method demonstrated encouraging performance compared to the state-ofthe-art model-based methods. In addition, our method showed promising potential in performing multi-task control based on the compositionality of learned controllers. Besides the assumed structural constraint between control cost weight and uncertainty of the passive dynamics, the major limitation is that we have not taken into account the uncertainty in the control matrix G. Future work will focus on further generalization of this framework and applications to real systems.