Policy Search via the Signed Derivative
J. Zico Kolter and Andrew Y. Ng
Computer Science Department, Stanford University{kolter,ang}@cs.stanford.edu

Abstract— We consider policy search for reinforcement learning: learning policy parameters, for some fixed policy class, that
optimize performance of a system. In this paper, we propose
a novel policy gradient method based on an approximation wecall the Signed Derivative; the approximation is based on theintuition that it is often very easy to guess the direction in which
control inputs affect future state variables, even if we do nothave an accurate model of the system. The resulting algorithm
is very simple, requires no model of the environment, and weshow that it can outperform standard stochastic estimators of
the gradient; indeed we show that Signed Derivative algorithm
can in fact perform as well as the true (model-based) policy
gradient, but without knowledge of the model. We evaluate thealgorithm’s performance on both a simulated task and two realworld tasks — driving an RC car along a specified trajectory,
and jumping onto obstacles with an quadruped robot — and in
all cases achieve good performance after very little training.

I. I NTRODUCTION
In this paper we consider policy search for reinforcement
learning. In this setting, one considers a parametrized control
policy and then, by interacting with the environment, modifies
the parameters to optimize some cost function. For example,
if our control task was to drive a car along a desired trajectory,
the cost function could penalize deviations from the trajectory,
and the control policy could determine the steering and throttle
as a simple (say, linear) function of current state features; inthis domain, the policy search task would involve learning
the coefficients on the state features to obtain a low cost (i.e.,
follow the trajectory well). We focus in particular on the policy
gradient approach, where we optimize the cost function using
gradient descent with respect to the policy parameters.
While there exist many different methods for approximating
the policy gradients, in this paper we propose a new algorithm
that makes use of what we call the Signed Derivative approximation. This method allows us to compute an approximation
to the policy gradient without a model of the system. Ouralgorithm is based on the following simple insight: the only
term in the policy gradient that depends on the dynamics
model is the derivative of future state elements with respect
to the control inputs. However, while these true derivatives
are difficult to compute, we claim that often it is very easy toestimate the sign of many of these derivatives; that is, we only
want to know the general direction of how control adjustments
will affect the state. Consider again the example of the car
mentioned earlier, where for instance one of the state variables
is lateral deviation from the desired trajectory, and one of thecontrols is the steering angle. While it may be very difficult
to know the true derivative of future lateral deviations withrespect to the steering angle, the sign of the derivative is infact quite obvious: turning more to the left typically results
in a lateral deviation that is also more to the left. While such
“obvious” derivative signs clearly don’t apply to all control
tasks, we demonstrate in this paper that they do apply inmany interesting domains; in such situations, we show that
we can drastically improve the performance of policy gradientmethods by using these signed derivatives. Indeed, we showthat in many cases, the Signed Derivative method not only
outperforms standard stochastic policy gradient algorithms(such as the REINFORCE [15] family of algorithm), but
actually performs as well as the true (model-based) policy
gradient algorithm, but without any knowledge of the model,
only the ability to simulate a single trace.
The remainder of this paper is organized as follows. In
Section II we present preliminary material and describe thegeneral Signed Derivative algorithm more formally. In Section
III we present theoretical results. In Section IV we present
empirical results for the algorithm on a number of different
domains, both simulated and real-world. Finally, in Section V
we discuss related work, and conclude the paper in Section
VI.
II. T HE S IGNED D ERIVATIVE A LGORITHM
A. Preliminaries and Notation
We consider control in a Markov Decision Process (MDP),
which is a tuple M = (S, A, T, H, C), where S is a set ofstates, A is a set of actions, T is the (unknown, but temporarily
assumed to be deterministic) system dynamics T : S ×A → S,
H is a time horizon and C is a known (one-step) cost function
C : S × A → R. Since we are concerned with general,continuous state and action domains, we let S ⊆ Rn andA ⊆ Rm . We can capture time-varying dynamics and costs by
including time as a state variable, though for the remainder ofthis paper we will make any time dependence explicit. Finally,
although our algorithm is extendable to general cost functions,for the sake of concreteness we will here assume a common
quadratic form of the reward function
Ct (st , ut ) = (st − s⋆t )T Qt (st − s⋆t ) + uTt Rt ut
where s⋆t denotes the desired state of system at time t, andQt and Rt are diagonal positive semidefinite matrices thatpenalize state deviation and control respectively.
A (time-dependent) policy π : S × R → A is a mappingfrom states and times to actions. As we are focused on thepolicy-search setting in this paper, here we consider policies
parametrized by some set of parameters θ — we use thenotation u = π(s, t; θ) to denote the policy π, parametrized

by θ, evaluated at state s and time t. For example, a common
class of policies that we will consider in this paper is policies
that are linear in the state featuresu = π(s; θ) = θT φ(s, t)
where φ : S × R → Rk is a mapping from states and times
to features and θ ∈ Rm×k is a set of parameters that linearly
map these features into controls.
Given a policy, we define the multi-step cost function (alsocalled the value function, or just the cost function, as opposedto the one-step cost function defined above above) as the sumof all one-step costs over the horizon H,
J(s0 , θ) =H
X

Ct (st , ut−1 )t=1where ut = θT φ(st , t) and where st+1 = T (st , ut ). We
can now more formally define the policy gradient algorithm
as a gradient descent method that repeatedly updates theparameters according toθ ← θ − α∇θ J(s0 , θ)
where α is a step size and ∇θ J(s0 , θ) is the gradient of thecost function with respect to the policy parameters. Although,computing this gradient term can be quite complicated withouta model of the system, in the next section we describe a simple
approximation method.
B. The Signed Derivative Approximation
In this section we derive a simple approximation to thepolicy gradient, using an approximation we called the signed
derivative. We want to emphasize that the final form of thealgorithm, shown in Algorithm 1, is quite simple, even though
the derivation is somewhat involved.
To motivate the signed derivative method, we first consider
the basic question of why ones needs a model of the system
to compute the policy gradient ∇θ J(s, θ). We will derive thisresult shortly, but it turns out that the policy gradient depends
on the model only through terms of the form


∂st
∂ut′
for t > t′ . These terms are the Jacobians of future stateswith respect to previous inputs. They provide the criticalmotivation for the signed derivative approximation, so it isworth looking
at them more closely. These Jacobians
 are

∂st
∂st
n×m
matrices ∂u ′ ∈ R
where the i, j element of the ∂u′ttdenotes the derivative of the ith element of the state st withrespect to the jth element of ut′ , i.e.,∂st∂(st )i≡.
∂ut′ ij∂(ut′ )j∂st
)ij indicates how the ith element of st
In other words ( ∂ut′would change if we made a small adjustment to the j elementof the control at a previous time t′ (and assuming we arefollowing the policy θ).

In general, the elements of these Jacobians are quite difficult
to compute, as they depend on the true dynamics modelof the environment and the policy parameters θ. However,the signed derivative approximation is based on the insightthat often times it is fairly easy to guess the signs of thedominant entries of these matrices: this only requires knowing
the general direction of how previous control inputs will affectfuture states. Returning to the example of driving a car, it may
be very difficult to determine the derivative of a future statewith respect to the steering wheel, but the direction of thegradient seems fairly obvious: turning the wheel more to theleft will likely result in future states also more to the left.
Furthermore, there is another property of these Jacobians
that allows us to come up with a reasonable approximation:in many control settings, each state is primarily affected byonly one control input. For example, if we are driving our
car along a straight line, one state variable (for example, thedistance traveled along the line), would be primarily affectedby only one control (in this case, the gas pedal). Indeed, many
control tasks seem to be expressly designed such that this is thecase. For example, imagine trying to drive a car where boththe steering wheel and gas pedal controlled some different
combinations of both the wheel angle and the throttle; while
such a control system is technically “equivalent” to a standardcar, it would take much more work to learn. This suggests,
at least anecdotally, that humans also exploit these orthogonal
control effects, and so we can expect many control tasks to
be designed in this way. In other words, we can expect one
element in each row of the Jacobians to be larger than theothers, corresponding to the “dominant” control element, andthese are precisely those elements where we can guess theirsign.
Given this discussion, the signed derivative approximation isquite straightforward. We approximate all the Jacobian termswith a single matrix S ∈ Rn×m , called the signed derivative,
where entries in S correspond to the signs of the dominant
entries in the Jacobians (which, by our discussion above,means that S has only one non-zero entry per row). Consider
one last time the driving example, and suppose that the car
is facing primarily along the x axis. If we represent the stateof the car as its position and orientation (x, y, θ), and let u1
and u2 be the throttle and steering angle respectively. Then areasonable estimate for the signed derivative would be
1 0
S =  0 1 .
0 1
For instance, S11 = 1 means that the first state variable (x) is
primarily controlled by the first control input (throttle). This
makes sense, since the car is mostly aligned with the x axis,
so throttle will primarily affect this state. Similarly, y and θ
are primarily affected by the second control (steering), which
also makes sense, because the steering wheel can cause the
car to both turn and veer to the side.
Finally recall, from the beginning of this section, that theJacobians were the only terms in the policy gradient that

Algorithm 1 Policy Gradient w/ Signed Derivative (PGSD)
Input:S ∈ Rm×n : signed derivative matrix
H ∈ Z+ : horizon
Qt ∈ Rn×n , Rt ∈ Rm×m : diagonal cost function matrices
α ∈ R+ : learning rate
φ : Rn × R → Rk : feature vector function
θ0 ∈ Rk×m : initial policy parameters
Repeat:
1. Execute policy for H steps to obtain
u0 , s1 , . . . , uH−1 , uH .
2. Compute approximate gradients w.r.t. controls:HX
e u J(s0 , Θ) ←S T Qt′ (st′ − s⋆t′ ) + Rt ut∇t

on θt . Furthermore, using the definition of J,∇ut J(s, Θ) = ∇utHX(st′ − s⋆t′ )T Qt′ (st′ − s⋆t′ ) + uTt Rt ut

t′ =1

=

T

H
X
∂st′

t′ =t+1∂utThis gives a gradient with respect to each θi (where,as stated,

T

t′
).
the only model-dependent terms are the Jacobians ∂s∂ut
Therefore, the gradient of the cost with respect to a single θis equivalent to taking a step in the direction of all these θi ’sthen projecting onto the space where θ0 = θ1 = . . . = θH−1 .
This is accomplished by updating each θt according tot′ =t+1

3. Update parameters:

H−1

α X
e u J(s0 , Θ))Tθ←θ−
φ(st , t)(∇t
H t=0Qt′ (st′ − s⋆t′ ) + Rt ut

H−1

θt ← θt −α X∇θt′ J(s, Θ),
H ′
t =0

i.e., the policy gradient with respect to a single parameter θ
is also given by
H−1∇θ J(s, θ) =required a model. Therefore, after making such the signed
derivative approximation we can now perform (approximate)policy gradient without the need for any model of the system.
This is precisely the method that we show in Algorithm 1.
The precise form of the gradient updates is derived in thenext section, but the basic idea of the algorithm is simple:
we are just performing policy gradient, replacing the Jacobian
terms with the signed derivative approximation S. It may seem
surprising that the method would perform well, given that thesigned derivative is a very crude approximation to the true
Jacobians; but, we will show, from both a theoretical andempirical perspective, that we can expect the algorithm toperform well in many situations.
C. Formal Derivation of the Policy Gradient
Here we prove the claim made in the previous section,that the policy gradient depends only on the dynamics modelthrough the Jacobian terms, and we derive the precise form of
the gradient given in Algorithm 1. The derivation is slightly
technical, but the algorithm itself can be understood just fromthe discussion above.
To avoid certain dependencies, we have to initially consider
the gradient of the cost function with respect to H different
sets of policy parameters for each time, Θ = {θ0 , . . . , θH−1 }.
We will then take a gradient step in terms of these parameters,
projected back into the space where they are all equal. The
gradients are given by∇θt J(s, Θ) =



∂ut
∂θt

T

∇ut J(s, Θ)T= φ(st , t) (∇ut J(s, Θ)) .
using the fact that ut = θtT φ(st , t) and that st doesn’t depend

1 X∇θt J(s, Θ).
H t=0

As stated, the only terms that depend on the model in this sum
are the Jacobians. This derivation should make it apparent that
Algorithm 1 is simply approximating the policy gradient by
substituting the signed derivative for all the Jacobian terms.
III. T HEORETICAL R ESULTS
Given that the signed derivative is admittedly a rather
crude approximation to the true Jacobians, there remains somequestion as to why we might expect such an approach to work.
While the ultimate test of the algorithm’s usefulness is, ofcourse, its empirical performance, the results we present here
can give insight and intuition into why we obtain the positive
results shown in latter sections. We first describe the basic
intuition behind the analysis.
There are many possible sources of error for any policy
gradient algorithm, but here we analyze the two types oferror introduced by the signed gradient approximation itself.
First, the signed gradient allows only one control variable
to influence a given state variable; even if a state element
is primarily affected by one control, there most likely exist
smaller influences from the other controls as well. Second,
the signed gradient makes no attempt to capture the relative
magnitudes (or the magnitudes of any kind) of the entries in
the Jacobian. Formally, these approximations are representedas∂st= D(S + Et,t′ )(1)∂ut′
for the signed derivative S and matrices Et,t′ ∈ Rm×n andpositive diagonal D ∈ Rn×n . The D matrix scales the entries
in the signed derivative, accounting for the second type oferror mentioned above. As we will see more formally below,
this type of error isn’t overly costly, since it has the effectof simple scaling the entries of the cost functions. Especiallyin the extreme case where policy gradient finds a solutionthat obtains near-zero cost, the actual entries of Qt become
unimportant.
The Et,t′ terms capture other errors: they add arbitrary
constants to the entries in the signed derivative, accounting
for the effects of additional control inputs on the states andfor time-dependent variation in the relative scaling of theJacobian. In the worst case, there is little that can be done
about such errors: if the entries of Et,t′ are large, then thegradient approximation using the signed derivative can be very
far from the true gradient. However, there is a great dealof reason to believe that, in many situations Et,t′ won’t be
too large: time-varying scaling should be relatively small overshort horizons, and from the discussion in the previous section,
we expect cross-terms in the Jacobian to be relatively small
in magnitude. And as formalized below, if the Et,t′ are small,then we expect the signed derivative to perform well.
Theorem 1: Using the notation from (1), suppose
kEt,t′ k2 ≤ ǫ for all t, t′ .1 Define the modified cost functionQ̃t = DQt . Then, given additional technical assumptions(described fully in the appendix), PGSD will converge withprobability one to some solution θ̃ that is “close” to a local
minimum of the cost function JQ̃ (θ), the cost function thatuses Q̃t (but the same Rt ) as the cost matrices:k∇θ JQ̃ (θ̃)k ≤ O(ǫ).
Furthermore, if performing gradient descent with respect to thetrue gradient (of the actual cost function) results in η-optimal
policy parameters — i.e., JQ (θ⋆ ) ≤ η — then PGSD also
obtains an order η-optimal solution2
JQ (θ̃) ≤ κ(D)η + O(ǫ).
Proof: (sketch) The full proof is given in the appendix3 ,but we provide a very brief sketch. The proof proceeds in threesteps. First, we show that the gradient approximated using thesigned derivative is equivalent to the true gradient using theQ̃ costs, plus a bounded error terme θ JQ (θ) = ∇θ J (θ) + Ẽ∇Q̃

for kẼk ≤ O(ǫ). Second, we show that following thisapproximate gradient using a stochastic gradient method will
converge, with probability one, to a point that is close toa minimum of JQ̃ (θ). Finally, we show that given suitable
assumptions about the region of convergence, a policy that isclose to locally optimal for JQ̃ (θ) will also be close to locally
optimal for JQ (θ).
IV. E XPERIMENTAL R ESULTS
A. Simulated Two-Link Arm
While we will present experiments on real systems shortly,
we begin by presenting an evaluation of our proposed method
1 The k · k norm of a matrix is equivalent to its maximum singular value.
22 κ(·) denotes the condition number of a matrix.
3 Additional material, including the full appendix with this proof, is available
at http://cs.stanford.edu/∼kolter/rss09sd.

1

0.8

0.6

0.4

0.2

0

−0.2

−0.4

−0.6

−0.8

−1

−1

Fig. 1.

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Two-link pendulum trajectory following task.

on a simulated two-link arm, in order to rigorously compare to previous policy gradient approaches, and to provide a readily available implementation of our approach.
Code for the all the results in this section is available at
http://cs.stanford.edu/˜kolter/rss09sd. Weemphasize that the purpose of this section is to specificallycompare PGSD with other policy gradient approaches. The
control task itself is fairly straightforward, and many otherapproaches such as adaptive control or iterative learning control could also be applied, though this is beyond the scope of
this paper; we will discuss these related works more in Section
V.
The two-link pendulum is a well-known control task inrobotics and control. The system, shown in Figure 1 consistsof two planar links; the state consists of the joint angles
and velocities of both joints and the control specifies a
torque at each of the joints. The equations of motion can beeasily derived from Lagrangian dynamics, and we introduce
stochasticity to the system by adding Gaussian noise to thetorques before integrating the equations of motion. The task
we consider here, also shown in the figure, is to move theend effector along some desired trajectory. When the modelof the system is known, it is fairly easy to apply classicalcontrol methodologies such as inverse dynamics or LQR tofind an optimal controller, but of course we don’t provide thismodel to PGSD or other comparable algorithms. We feel that
this is a particularly demonstrative example for the Signed
Derivative algorithm, since it is well-known that there arecross terms that cause all joints to be affected by all the control
inputs — for instance, a common (more challenging) task is toswing the pendulum upright and balance by applying torques
only to the elbow — yet we claim that the Signed Derivative
approximation is still reasonable, since joints are primarily
affected by their own control.
The cost function for this domain penalizes deviations fromthe desired joint angles (we first computed the trajectory injoint space), and we use a time horizon of H = 5. Note that
this doesn’t mean that the controller only needs to follow the
trajectory for 5 steps, but rather that at each time the controller
should ideally act optimally with respect to a receding horizonof H = 5; since the cost function itself “guides” the arm
along the trajectory, such a horizon is suitable. We use a linear
control policy ut = θT φ(st , t) where φ contains 1) deviations
from desired joint angles, 2) deviations from desired joint
velocities, 3) desired joint accelerations, and 4) sin(2πt/ttotal )

1.5

8

Desired Position
Initial PD Controller

PGSD
REINFORCE (w/ resets)
REINFORCE

7

1

6
0.5

Cost

y

5

0

4
3

-0.5

2
-1

1
-1

-0.5

0
x

0.5

1

0
0

Fig. 2. (top) Trajectory from initial PD controller. (bottom) Trajectories fromcontroller learned using PGSD.

1.5

2000

4000
6000
Timestep

8000

10000

Fig. 4. Average cost versus time for different policy gradient methods. Costs
are averaged over 20 runs, and shown with 95% confidence intervals. (Bestviewed in color).

Desired Position
PGSD Policy

1

0.1

True Gradient (from model)
Optimal LQR controller
PGSD

0.5
y

0.08
0

0.06
Cost

-0.5

0.04

-1
-1

-0.5

0
x

0.5

1

Fig. 3. (top) Trajectory from initial PD controller. (bottom) Trajectories fromcontroller learned using PGSD.

0.02
0
0

where ttotal is total time for the complete trajectory (this lastterm was added to account for a visible periodic pattern inthe controls). This leads to s total of 14 parameters for thepolicy. For algorithms that require a stochastic policy, weadded Gaussian noise to the parameters: ut = (θ+ǫt )T φ(st , t),(ǫt )ij ∼ N (0, σ).
Figure 4 compares the performance versus time of PGSD,
and a well-known policy gradient RL algorithm, the REINFORCE algorithm.4 All free parameters of the learning algorithms (gradient step sizes, policy noise, number of episodes)
were hand-optimized to give that fastest convergence that
didn’t cause any divergence issues. As the figure shows, PGSD
drastically outperform the other methods, converging much
faster to a low-cost policy. This improvement is especiallynotable given that the REINFORCE algorithm is actually
given an advantage: since the task we’re considering is not
episodic (at least not at the time-scale of the horizon), episodic
algorithms don’t immediately apply, and so we instead allow
the algorithm the ability to reset to previous states observed
along the trajectory. The REINFORCE without resets in thefiture does not have such an advantage, but also performs muchworse. Figures 3 and 2 show the resulting controller learned
4 We intentionally scaled the parameters of this control task to be the sameorder of magnitude, so more advanced techniques such as natural gradients[6,11] didn’t improve performance significantly. In preliminary experiments wealso evaluated a variety of finite difference and weight perturbation methods,
but didn’t notice a substantial improvement over REINFORCE for this task.

400

800
1200
Timestep

1600

2000

Fig. 5. Average cost versus time for PGSD versus model-based methods.
Costs are averaged over 20 runs, and shown with 95% confidence intervals.

by the PGSD algorithm after 2000 time steps (4 times throughthe trajectory), along with the trajectory achieved by the initial
PD controller (used to initialize all the learning algorithms).
We also compare, in Figure 5, the performance of the
PGSD algorithm, policy gradient using the true gradient fromthe model, and an optimal LQR controller. Not surprisingly,
the LQR controller performs best: this controller is built by
linearizing around the (known) dynamics at each operating
point, then computing a series of non-stationary policies foreach point (in total, the LQR controller has 9000 parameters).
However, using only 14 parameters, the true policy gradientand PGSD algorithm are able to obtain a controller that performs relatively close to this full LQR controller. Furthermore,
the most important result is that the learning curve for PGSD
is virtually indistinguishable from the true policy gradientlearning curve; despite the rather crude approximation madeby the signed derivative, this resulting algorithm performs justas well on this task, and requires no model of the system (andtherefore also less computation time, since there is no needfor time-consuming finite difference computations).
B. Autonomous RC Driving
In this section we apply the PGSD algorithm to the taskof learning to drive an autonomous RC car along a desired

2Desired Position
PGSD Policy

1.5
1
y

0.5
0
-0.5
-1
-2

Fig. 6.
2

-1

-0.5

0
x

0.5

1

1.5

2

Fig. 8.
Desired trajectory for the autonomous RC driving experiments,
with typical trajectory learned using PGSD after approximately 20 secondsof learning.

Desired Position
Initial PD Controller

1.5

0.5

1
y

-1.5

RC car used for the driving experiments.

0.5

PGSD

0.4

0

0.3
Cost

-0.5
-1

0.2
-2

-1.5

-1

-0.5

0
x

0.5

1

1.5

2

Fig. 7. Desired trajectory for the autonomous RC driving experiments, withtrajectory for initial PD controller

0.1
0
0

trajectory. Figure 6 shows the car, a Tamiya TRF415, which
is about 40cm long and 20cm wide. A pattern of LED lights
is attached to the car, and tracked by an external PhaseSpace
motion capture system for pose estimation. All processing isdone on a workstation PC, with controls transmitted to the car
at 50hz.
The simplest representation of the car’s state is as six
dimensional vector representing the 2D position x, y, theorientation θ, and the time derivatives ẋ, ẏ, θ̇. However, a morenatural representation for the signed derivative approach isto represent the car’s state relative to some desired trajectory— here the trajectory is specified as a continuous spline thatgives the desired state as a function of time. In this alternate
representation, the state consists of the longitudinal, lateral,and angular deviation (and their derivatives) from the desired
trajectory. The control is two dimensional, consisting of acommanded throttle and steering angle.
We use the same form of linear controller as in the previous
sections, but where φ(s, t) now contains 1) the full state(represented as the deviation terms), 3) the desired velocities,
relative to the car frame, 3) the deviations for a target state
0.5 seconds and 4) a constant term. Some of the θ parameters
are forced to be zero (so that, for instance, the throttle doesn’t
depend on the lateral deviation), for a total of 16 parametersin the policy. The cost function penalizes the longitudinal,
lateral, and angular deviation, any control outside a specified
valid range, and control that changes more that some amountbetween two time steps (to minimize oscillations). We used atime horizon of H = 25.

10

20

30
40
Time (seconds)

50

60

Fig. 9. Average cost versus time for the PGSD algorithm on the RC car task.
Costs are averaged over 10 runs, and shown with 95% confidence intervals.

Figures 8 and 7 show the control task we consider: driving
the car in an irregular figure-eight pattern at varying speeds(2.0 m/s along the larger loop, 1.5 m/s along the smaller loop).
The figure also shows the trajectory followed by an initial PD
controller: while the PD controller follows the overall patternof the trajectory, it clearly does not perform very well. Figure
9 shows the learning curve of the PGSD algorithm. As thefigure shows, PGSD is able to very quickly — within an
average of 20 seconds, about 3 times around the trajectory— obtain a policy that performs far better than the initial PD
controller. We show a typical trajectory from one of theselearned controllers in Figure 8. The learned policies do not
perform flawlessly — the car still sometimes veers off thedesired path — but we feel this is largely due to the limited
policy class itself; to perform better, one might need more
complex, time-varying policies, to capture the fact that the carneeds to behave differently at different points along the path.
Nonetheless, PGSD converges to a very reasonable policy —in fact, better than any we were able to hand tune in the same
policy class — in just 20 seconds of learning.
C. LittleDog Jumping
In this section we present results on applying PGSD to
the task of “jumping” the front legs of a quadruped robot toquickly climb up large steps. The “LittleDog” robot that weFig. 12.
Fig. 10.

Fig. 11.

A properly executed jump.

The LittleDog robot.

The desired task for the LittleDog: climb over three large steps.

use for this task, shown in Figure 10, is designed and built by
Boston Dynamics, Inc. The task we are concerned with here isshown in Figure 11: we want to quickly climb up three steps,
whose height is approximately equal to the robot’s groundclearance. Because the steps are so large, the most efficientmotion to climb up is to jump the two front legs on a step,then pull the rest of the body up.
However, jumping the front legs on the LittleDog robot is
not a trivial task. The LittleDog’s legs are not powerful enoughto force its body off the ground, so the only means of jumping
is to lean the body backwards until the virtually all the mass
rests on the hind legs, then quickly raise the front legs andpush forward before the robot falls over. Figure 12 shows aproperly executed front leg jump. However, if the weight is
not shifted properly, the robot will either plant it’s feet into
the step, or flip over backward. It’s very difficult to correctsuch failures, because usually by the time it is apparent thatthe robot has failed to jump properly, the robot does not havethe power to correct itself. Therefore, jumping is a “one-off”
maneuver: we guess an amount to shift backward, then apply
an open-loop sequence of joint commands, hoping to jumpsuccessfully. The situation is made complicated because the“correct”amount to shift the weight depends, for example, on
the state of the robot, namely the current position of the COG
relative to the back feet, and the forward velocity of the robot.
Because we want a policy that can jump regardless of theinitial conditions, we applied the PGSD algorithm to learn ajumping policy that predicts the correct amount to shift givenfeatures of the current state.

Although full state space for the LittleDog is 36 dimensional(12 joints and twelve joint velocities plus a 6D pose and6D pose velocities), we don’t need to take into accountthe complete state. Rather, the only state element that isparticularly crucial for the jumping maneuver is the pitch of
the body: if the pitch is too small, the dog won’t clear the step,
but if it is too large, the dog will flip backward. Therefore, thecost function can depend only on the pitch of the dog. The
control is a number that indicates how far back to shift theweight before pushing forward; we determine the control asa linear function of three features: 1) the current shift of thecenter of mass, 2) the forward velocity of the dog and 3) a
constant term.
There is one straightforward generalization of the PGSD
algorithm, as presented so far, that we make for this task.
Although the cost function depends only on the pitch of therobot, it is difficult to know the “optimal” pitch — unlike
previous tasks where the optimal state value was clearly
defined. Instead, the readily observable quantity is simply
whether the jump succeeded, or whether the robot either didn’t
clear the step or flipped over. Therefore, if we define the onestep cost as the ℓ1 error between the pitch and optimal pitch,then the gradient is just the sign of the direction we should
move our control in. When H = 1, the PGSD update thentakes on a very simple form: θ − αφ(s) robot didn’t clear stepθjump succeededθ←θ + αφ(s) robot flipped backwards
Despite the simplicity of this update rule, it works well inpractice. We evaluated this PGSD variant on the LittleDog
robot, attempting to climb the three steps as shown in Figure
11. After 28 failures (either flipping backwards or failingto clear the step), the robot successfully jumped all threesteps for the first time. After 59 failures, the learning process
had converged on a stable controller: the robot succeeded inclimbing all three steps for 13 out of the next 20 trials. This is
far better than any policy we had been able to code by hand.5
A video of the learning process on the dog is available at thewebsite mentioned previously.

5 While it is possible to increase the reliability of the system by adding extra
steps to ensure that the robot always enters a similar configuration before each
jump, in these experiments we wanted to test precisely how well a controller
could perform under many different circumstances.

V. R ELATED W ORK
As mentioned in the introduction, there is a great deal ofwork on policy gradient methods for reinforcement learning.
If a model of the system is known, then we can compute thegradient using simple finite difference methods — this holds
even in stochastic domains if we are allowed to fix the random
seeds which lead to this stochasticity, an approach known as
the PEGASUS algorithm [10]. These model-based methods
have been applied to many robotics domains. However, sucha model might not always be available, or might be difficult tolearn from data. Additionally, as we have shown, our PGSD
method can sometimes perform as well as the model-based
methods without any model other than the signed derivative
approximation.
In situations where we have no model, we can still apply
finite difference methods or weight perturbation, so long as
the step sizes are large enough to overcome noise. Such an
approach was successfully applied to the task of learning aquadruped trotting gait in [8]. Recently, [13] investigated theeffect of sampling distributions on the signal-to-noise ratio ofthese and similar gradient updates.
A related but different approach uses a likelihood ratio
trick to obtain an estimate of the gradient using a numberof episodes run under the system and policy of interest: the
REINFORCE [15] algorithm was the first of such methods,
but many extensions and generalization have been proposed[4, 5, 11, 7]. There has also been work on estimating andusing the natural gradient, a gradient that is invariant toreparameterizations of the policy [6, 3, 12]. However, mostof these algorithms require running multiple episodes in orderto obtain a reasonable estimate of the gradient (or natural
gradient), which is difficult for non-episodic tasks such as
those we consider. In these domains, PGSD has the strong
advantage of only requiring a single episode to obtain an
estimate of the gradient.
Our work also shares a strong connection to [1]. This
paper proposes a method for using inaccurate simulation
models by using only the local gradient information impliedby these models. This is quite similar in spirit to our approach,except we discard any need for even an inaccurate simulator,and encode all necessary information directly in the signed
gradient: the approximation may be rougher, but unlike thispast approach PGSD does not require performing any local
policy search in a simulator.
Finally, we want to note the connection between the algorithm we propose here and the field of adaptive control[14, 2] — in particular the subtopics of Model Reference
Adaptive Control (MRAC) and Self-Tuning Regulators — andIterative Learning Control (ILC) [9]. The general philosophyof these approaches is similar to PGSD: they use an error
signal (i.e., between the actual and desired state) to directly
adapt the parameters. However, typical formulations of MRAC
or ILC use hand-crafted update rules to modify the controller,
with the focus on analyzing stability properties of the resulting
controllers. In contrast, PGSD uses a general update rule thatderives completely from the Reinforcement Learning setting oflong time horizons and general cost functions, plus the Signed
Derivative approximation of the model derivatives. derivatives.
Generally speaking however, PGSD could be viewed somewhat as an instance of MRAC or ILC, with a very particularform for the update rule.
VI. C ONCLUSION
In this paper, we proposed the Signed Derivative method, amethod for approximating policy gradients, using the insightthat often times it is very easy to guess the direction inwhich control inputs will affect future states. We show that
this algorithm, Policy Gradient with the Signed Derivative(PGSD) can perform very well compared to stochastic gradientestimators, and in fact can perform as well as the true gradient,even though it has no knowledge of the true environment’s
model. We further evaluated our algorithm on two real-worldcontrol tasks — driving an RC car and jumping with aquadruped robot — and demonstrated very good performanceon both domains. While we stress that the PGSD approachis not suitable for all situations (for instance, if the effects ofcontrols on the system is entirely unknown), we feel that inmany situations the approach applies quite easily, and offers
very substantial performance benefits.
R EFERENCES[1] Pieter Abbeel, Morgan Quigley, and Andrew Y. Ng. Using innaccurate
models in reinforcement learning. In Proceedings of the International
Conference on Machine Learning, 2006.
[2] Karl Johan Astrom and Bjorn Wittenmark. Adaptive Control. Prentice
Hall, 1994.
[3] J. Andrew Bagnell and Jeff Schneider. Covariant policy search. In Proceedings of the International Joint Conference on Artificial Intelligence,
2003.
[4] Jonathan Baxter and Peter L. Bartlett. Infinite-horizon gradient-based
policy search. Journal of Artificial Intelligence Research, 15:319–350,
2001.
[5] Evan Greensmith, Peter L. Bartlett, and Jonathan Baxter. Variancereduction techniques for gradient estimates in reinforcement learning.
Journal of Machine Learning Research, 5:1471–1530, 2004.
[6] Sham Kakade. A natural policy gradient. In Neural Information
Processing Systems 14, 2001.
[7] Jens Kober and Jan Peters. Policy search for motor primitives in robotics.
In Neural Information Processing Systems 21, 2009.
[8] Nate Kohl and Peter Stone. Machine learning for fast quadrupedal
locomotion. In Proceedings of the AAAI, pages 611–616, July 2004.
[9] Kevin L. Moore. Iterative learning control: an expository overview.
Applied and Computational Controls, Signal Processing, and Circuits,
1(1):151–214, 1999.
[10] Andrew Y. Ng and Michael Jordan. Pegasus: A policy search method
for large mdps and pomdps. In Proceedings of the Conference on
Uncertainty in Artificial Intelligence, 2000.
[11] Jan Peters and Stefan Schaal. Policy gradient methods for robotics. In
Proceedings of the IEEE Conference on Intelligent Robotics Systems,
2006.
[12] Jan Peters, Sethu Vijayakumar, and Stefan Schaal. Natural actor-critic.
In Proceedings of the European Conference on Machine Learning, 2005.
[13] John W. Roberts and Russ Tedrake. Signal-to-noise ratio analysis ofpolicy gradient algorithms. In Neural Information Processing Systems
21, 2009.
[14] Shankar Sastry and Marc Bodson. Adaptive Control: Stability, Convergence, and Robustness. Prentice-Hall, 1994.
[15] Ronald J. Williams. Simple statistical gradient-following algorithms forconnectionist reinforcement learning. Machine Learning, 8:229–256,
1992.