Lecture 20 | Machine Learning (Stanford)

Lecture by Professor Andrew Ng for Machine Learning (CS 229) in the Stanford Computer Science department. Professor Ng discusses POMDPs, policy search, and Pegasus in the context of reinforcement learning.

This course provides a broad introduction to machine learning and statistical pattern recognition. Topics include supervised learning, unsupervised learning, learning theory, reinforcement learning and adaptive control. Recent applications of machine learning, such as to robotic control, data mining, autonomous navigation, bioinformatics, speech recognition, and text and web data processing are also discussed.

Complete Playlist for the Course:
http://www.youtube.com/view_play_list?p=A89DCFA6ADACE599

CS 229 Course Website:
http://www.stanford.edu/class/cs229/

Stanford University:
http://www.stanford.edu/

Stanford University Channel on YouTube:
http://www.youtube.com/stanford

This presentation is delivered by the Stanford Center for Professional

Development.

So welcome to the last lecture of this course.

What I want to do today is tell you about one final class of reinforcement

learning algorithms. I

just want to say a little bit about POMDPs, the partially observable MDPs, and then

the main technical topic for today will be policy search algorithms.

I'll talk about two specific algorithms, essentially called reinforced and called Pegasus,

and then we'll wrap up the class. So if you recall from the last lecture,

I actually started to talk about one specific example of a POMDP,

which was this sort of linear dynamical

system. This is sort of LQR, linear quadratic revelation problem,

but I changed it and said what if we only have observations

YT. And what if we couldn't observe the state of the system directly,

but had to choose an action only based on some noisy observations that maybe some function of the state?

So our strategy last time was that we said that in the fully observable case,

we could choose actions - AT equals two, that matrix LT times ST. So LT was this

matrix of parameters that [inaudible] describe the dynamic programming

algorithm for finite horizon MDPs in the LQR problem.

And so we said if only we knew what the state was, we choose actions according to some matrix LT times the state.

And then I said in the partially observable case,

we would compute these estimates.

I wrote them as S of T given T,

which were our best estimate for what the state is given all the observations. And in particular,

I'm gonna talk about a Kalman filter

which we worked out that our posterior distribution of what the state is

given all the observations up to a certain time

that was this. So this is from last time. So that

given the observations Y one through YT, our posterior distribution

of the current state ST was Gaussian

would mean ST given T sigma T given T.

So I said we use a Kalman filter to compute this thing, this ST given T,

which is going to be our best guess for what the state is currently.

And then we choose actions using

our estimate for what the state is, rather than using the true state because we

don't know the true state anymore in this POMDP.

So

it turns out that this specific strategy actually allows you to choose optimal actions,

allows you to choose actions as well as you possibly can given that this is a

POMDP, and given there are these noisy observations.

It turns out that in general finding optimal policies with POMDPs -

finding optimal policies for these sorts of partially observable MDPs is an NP-hard problem.

Just to be concrete about the formalism of the POMDP - I should just write it here -

a POMDP formally is a tuple like that

where the changes are the set Y is the set of possible observations,

and this O subscript S are the observation distributions.

And so at each step, we observe

- at each step in the POMDP, if we're

in some state ST, we observe some observation YT

drawn from the observation distribution O subscript ST, that there's an

index by what the current state is.

And

it turns out that computing the optimal policy in a POMDP is an NPhard problem.

For the specific case of linear dynamical systems with the Kalman filter

model, we have this strategy of computing the optimal policy assuming full observability

and then estimating the states from the observations,

and then plugging the two together.

That turns out to be optimal essentially for only that special case of a POMDP.

In the more general case,

that strategy of designing a controller assuming full observability

and then just estimating the state and plugging the two together,

for general POMDPs

that same strategy is often a very reasonable strategy but is not always guaranteed to be optimal.

Solving these problems in general, NP-hard.

So what I want to do today

is actually

talk about a different class of reinforcement learning algorithms. These are called

policy search algorithms. In particular, policy search algorithms

can be applied equally well to MDPs, to fully observed Markov decision processes,

or to these POMDPs,

or to these partially observable MPDs.

What I want to do now, I'll actually just describe policy search algorithms applied to MDPs, applied to the fully observable case.

And in the end, I just briefly describe how you can take policy search algorithms and apply them to POMDPs. In

the latter case, when

you apply a policy search algorithm to a POMDP, it's

going to be hard to guarantee that you get the globally optimal policy because

solving POMDPs in general is NP-hard, but nonetheless policy search algorithms - it turns out to be

I think one of the most

effective classes of reinforcement learning algorithms, as well both for MDPs and for POMDPs.

So

here's what we're going to do.

In policy search,

we're going to define of some set

which I denote capital pi of policies,

and our strategy is to search for a good policy lower pi into set capital pi.

Just by analogy, I want to say

- in the same way, back when we were talking about supervised learning,

the way we defined the set capital pi of policies in the search for policy in this

set capital pi is analogous to supervised learning

where we defined a set script H of hypotheses and search -

and would search for a good hypothesis in this policy script H.

Policy search is sometimes also called direct policy search.

To contrast this with the source of algorithms we've been talking about so

far, in all the algorithms we've been talking about so far, we would try to find V star. We would try to

find the optimal value function.

And then we'd use V star - we'd use the optimal value function to then try to compute or

try to approximate pi star.

So all the approaches we talked about previously are

strategy for finding a good policy. Once we compute the value function, then we go from that to policy.

In contrast, in policy search algorithms and something that's called direct policy search algorithms,

the idea is that we're going to quote "directly" try to approximate a good policy

without going through the intermediate stage of trying to find the value function.

Let's see.

And also

as I develop policy search - just one step that's sometimes slightly confusing.

Making an analogy to supervised learning again, when we talked about logistic regression,

I said we have input features X and some labels Y, and I sort of said

let's approximate Y using the logistic function of the inputs X. And

at least initially, the logistic function was sort of pulled out of the air.

In the same way, as I define policy search algorithms, there'll sort of be a step where I say,

"Well, let's try to compute the actions. Let's try to approximate what a good action is

using a logistic function of the state." So again, I'll sort of pull a

function out of the air. I'll say, "Let's just choose a function, and

that'll be our choice of the policy cost," and I'll say,

"Let's take this input the state, and then we'll map it through logistic function, and then hopefully, we'll approximate

what is a good function -

excuse me,

we'll approximate what is a good action using a logistic function of the state."

So there's that sort of -

the function of the choice of policy cost that's again a little bit arbitrary,

but it's arbitrary as it was when we were talking about supervised learning.

So to develop our first policy search algorithm, I'm actually gonna need the new definition.

So

our first policy search algorithm, we'll actually need to work with stochastic policies.

What I mean by stochastic policy is there's going to be a function that maps from

the space of states across actions. They're real numbers

where pi of S comma A will be

interpreted as the probability of taking this action A in sum state S.

And so we have to add sum over A - In other words, for every state

a stochastic policy specifies a probability distribution over the actions.

So concretely,

suppose you are executing some policy pi. Say I have some stochastic policy pi. I wanna execute the policy pi.

What that means is that - in this example let's say I have three actions.

What that means is that suppose I'm in some state S.

I would then compute pi of S comma A1, pi of S comma A2,

pi of S comma A3, if I have a three action MDP.

These will be three numbers that sum up to one,

and then my chance of taking action A1 will be

equal to this. My chance of taking action A2 will be equal to pi of S comma A2.

My chance of taking action A3 will be equal

to this number. So that's what it means to execute a stochastic policy.

So

as a concrete example, just let me make this

let me just go ahead and give one specific example of what a stochastic

policy may look like.

For this example, I'm gonna use the inverted pendulum

as my motivating example. It's that problem of balancing a pole. We have an

inverted

pendulum that swings freely, and you want to move the cart left and

right to keep the pole vertical.

Let's say my actions -

for today's example, I'm gonna use that angle to denote the angle of the pole

phi. I have two actions where A1 is to accelerate left

and A2 is to accelerate right. Actually, let me just write that the other way around. A1 is to accelerate right. A2 is to accelerate left.

So

let's see.

Choose a reward function that penalizes the pole falling over whatever.

And now let's come up with a stochastic policy for this problem.

To come up with a class of stochastic policies

really means coming up with some class of functions to approximate what action you

want to take as a function of the state.

So here's my somewhat arbitrary choice. I'm gonna say that

the probability of action A1, so pi of S comma A1,

I'm gonna write as - okay?

And I just chose the logistic function because it's a convenient function we've used a lot. So I'm gonna say that

my policy is parameterized by a set of parameters theta,

and for any given set of parameters theta,

that gives me a stochastic policy.

And if I'm executing that policy with parameters theta, that means

that the chance of my choosing to a set of [inaudible] is given by this number.

Because my chances of executing actions A1 or A2 must sum to one, this gives me pi of S A2. So just

[inaudible], this means that when I'm in sum state S,

I'm going to compute this number,

compute one over one plus E to the minus state of transpose S.

And then with this probability, I will execute the accelerate right action,

and with one minus this probability, I'll execute the accelerate left action.

And again, just to give you a sense of why this might be a reasonable thing to do,

let's say my state vector is - this

is [inaudible] state, and I added an extra one as an interceptor, just to give my

logistic function an extra feature.

If I choose my parameters and my policy to be say this,

then that means that at any state,

the probability of my taking action A1 - the probability of my taking the accelerate

right action is this one over one plus E to the minus state of transpose S, which taking the inner product

of theta and S, this just gives you phi,

equals one over one plus E to the minus phi.

And so if I choose my parameters theta as follows,

what that means is that

just depending on the angle phi of my inverted pendulum,

the chance of my accelerating to the

right is just this function of

the angle of my inverted pendulum. And so this means for example

that if my inverted pendulum is leaning far over to the right,

then I'm very likely to accelerate to the right to try to catch it. I

hope the physics of this inverted pendulum thing make

sense. If my pole's leaning over to the right, then I wanna accelerate to the right to catch it. And

conversely if phi is negative, it's leaning over to the left, and I'll accelerate to the left to try

to catch it.

So this is one example for one specific choice of parameters theta.

Obviously, this isn't a great policy because it ignores the rest of the features. Maybe if

the cart is further to the right, you want it to be less likely to accelerate to the

right, and you can capture that by changing

one of these coefficients to take into account the

actual position of the cart. And then depending on

the velocity of the cart and the angle of velocity,

you might want to change theta to take into account these other effects as well. Maybe

if the pole's leaning far to the right, but is actually on its way to swinging back, it's

specified to the angle of velocity, then you might be

less worried about having to accelerate hard to the right. And so

these are the sorts of behavior you can get by varying the parameters theta.

And so our goal is to tune the parameters theta - our goal in policy search

is to tune the parameters theta so that when we execute the policy pi subscript theta,

the pole stays up as long as possible.

In other words, our goal is to maximize as a function of theta -

our goal is to maximize the expected value of the payoff

for when we execute the policy pi theta. We

want to choose parameters theta

to maximize that. Are there questions about the problem set up,

and policy search and policy classes or anything? Yeah. In a case where we have

more than two actions, would we use a different theta for each of the distributions, or still have

the same parameters? Oh, yeah.

Right. So what if we have more than two actions. It turns out you can choose almost anything you want for the policy class, but

you have say a fixed number of discrete actions,

I would sometimes use like a softmax parameterization.

Similar to softmax regression that we saw earlier in the class,

you may

say

that - [inaudible] out of space. You may have a set of parameters theta 1

through theta D if

you have D actions and - pi equals E to the theta I transpose S over -

so that would be an example of a softmax parameterization for multiple actions.

It turns out that if you have continuous actions, you can actually make this be a

density

over the actions A

and parameterized by other things as well.

But the choice of policy class is somewhat up to you, in the same way that

the choice of whether we chose to use a linear function

or linear function with

quadratic features or whatever in supervised learning that was sort of up to us. Anything

else? Yeah. [Inaudible] stochastic?

Yes. So is it possible to [inaudible] a stochastic policy using numbers [inaudible]? I see. Given that MDP has stochastic transition

probabilities, is it possible to

use [inaudible] policies and [inaudible] the stochasticity of the state transition probabilities.

The answer is yes,

but

for the purposes of what I want to show later, that won't be useful.

But formally, it is possible.

If you already have a fixed - if you have a

fixed policy, then you'd be able to do that. Anything else?

Yeah. No, I guess even a [inaudible] class of policy can do that,

but for the derivation later, I actually need to keep it separate.

Actually, could you just - I know the concept of policy search is sometimes a little confusing. Could you just raise your hand

if this makes sense?

Okay. Thanks. So let's talk about

an algorithm. What I'm gonna talk about - the first algorithm I'm going to present

is sometimes called the reinforce algorithm. What I'm going to present it turns out

isn't exactly the reinforce algorithm as it was originally presented by the

author Ron Williams, but it sort of captures its essence. Here's the idea.

In the sequel - in what I'm about to do, I'm going to assume that S0 is

some fixed initial state.

Or

it turns out if S0 is drawn from some fixed initial state

distribution then everything else [inaudible], but let's just say S0 is some

fixed initial state.

So my goal is to maximize this expected sum

[inaudible]. Given the policy and whatever else, drop that.

So the random variables in this expectation is a sequence of states and actions:

S0, A0, S1, A1, and so on, up to ST, AT are the random variables.

So let me write out this expectation explicitly as a sum

over all possible state and action sequences of that

- so that's what an expectation is. It's the probability of the random variables times that. Let

me just expand out this probability.

So the probability of seeing this exact sequence of states and actions is

the probability of the MDP starting in that state.

If this is a deterministic initial state, then all the probability

mass would be on one state. Otherwise, there's some distribution over initial states.

Then times the probability

that

you chose action A0 from that state as zero,

and then times the probability that

the MDP's transition probabilities happen to transition you to state

S1 where you chose action A0 to state S0,

times the probability that you chose that and so on.

The last term here is that, and then times that.

So what I did was just

take this probability of seeing this sequence of states and actions, and then just

[inaudible] explicitly or expanded explicitly like this.

It turns out later on

I'm going to need to write this sum of rewards a lot, so I'm just gonna call this the payoff

from now. So whenever later in this lecture I write the word payoff, I

just mean this sum.

So

our goal is to maximize the expected payoff, so our goal is to maximize this sum.

Let me actually just skip ahead. I'm going to write down what the final answer is, and

then I'll come back and justify the

algorithm. So here's the algorithm. This is

how we're going to

update the parameters of the algorithm. We're going to

sample a state action sequence. The way you do this is you just take your

current stochastic policy,

and you execute it in the MDP. So just go ahead and start from some initial state, take

a stochastic action according to your current stochastic policy,

see where the state transition probably takes you, and so you just

do that for T times steps, and that's how you sample the state sequence. Then

you compute the payoff, and then you perform this update.

So let's go back and figure out what this algorithm is doing.

Notice that this algorithm performs stochastic updates because on

every step it updates data according to this thing on the right hand side.

This thing on the right hand side depends very much on your payoff and on

the state action sequence you saw. Your

state action sequence is random,

so what I want to do is figure out

- so on every step, I'll sort of take a step that's chosen randomly

because it depends on this random state action sequence.

So what I want to do is figure out on average how does it change the parameters theta.

In particular,

I want to know what is the expected value of the change to the parameters.

So I want to know what is the expected value of this change to my parameters theta. Our

goal is to maximize the sum [inaudible] - our goal is to maximize the value of the payoff.

So long as

the updates on expectation are on average taking us uphill

on the expected payoff,

then we're happy.

It turns out that

this algorithm is a form of stochastic gradient ascent in which -

remember when I talked about stochastic gradient descent for least squares regression, I

said that you have some parameters - maybe you're trying to minimize a quadratic function.

Then you may have parameters that will wander around randomly

until it gets close to the optimum of the [inaudible] quadratic surface.

It turns out that

the reinforce algorithm will be very much like that. It will be a

stochastic gradient ascent algorithm in which on every step -

the step we take is a little bit random. It's determined by the random state action sequence,

but on expectation this turns out to be essentially gradient ascent algorithm.

And so we'll do something like this. It'll wander around randomly, but on average take you towards the

optimum. So let me go ahead and prove that now.

Let's see.

What I'm going to do is I'm going to derive a gradient ascent update rule

for maximizing the expected payoff. Then I'll hopefully show that

by deriving a gradient ascent update rule, I'll end up with this thing on expectation.

So before I do the derivation, let me just remind you of

the chain rule - the product rule for differentiation

in which

if I have a product of functions,

then

the derivative of the product is given by

taking of the derivatives of these things one at a time. So first I differentiate

with respect to F prime, leaving the other two fixed. Then I differentiate with respect to G,

leaving the other two fixed.

Then I differentiate with respect to H, so I get H prime leaving the other two fixed. So that's the

product rule

for

derivatives.

If you refer back to this equation where

earlier we wrote out that

the expected payoff by this equation, this

sum over all the states of the probability

times the payoff.

So what I'm going to do is take the derivative of this expression

with respect to the parameters theta

because I want to do gradient ascent on this function. So I'm going to take the

derivative of this function with respect to theta, and then try to go uphill on this function.

So using the product rule, when I take the derivative of this function with respect to theta

what I get is - we'll end up with the sum of terms right there. There are a lot

of terms here that depend on theta,

and so what I'll end up with is I'll end up having a sum - having one term

that corresponds to the derivative of this keeping everything else fixed,

to have one term from the derivative of this keeping everything else fixed, and I'll

have one term

from the derivative of

that last thing keeping everything else fixed. So just apply the product rule to this. Let's

write that down. So I have that - the derivative

with respect to theta of the expected value of the payoff is -

it turns out I can actually do this entire derivation in exactly four steps,

but each of the steps requires a huge amount of writing, so

I'll just start writing and see how that goes, but this is a four step derivation.

So there's the sum over the state action sequences as we saw before. Close the

bracket,

and

then times the payoff.

So that huge amount of writing, that was just taking my previous formula and

differentiating these terms that depend on theta one at a time. This was the term with

the derivative

of the first pi of

theta S0 A0. So there's the first derivative

term. There's the second one. Then you have plus dot, dot, dot, like

in terms of [inaudible].

That's my last term.

So that was step one of four.

And so by algebra - let me just write this down

and convince us all that it's true.

This is the second of four steps

in which it

just convinced itself that if I expand out - take the sum and multiply it by

that big product in front,

then I get back that sum of terms I get. It's essentially -

for example, when I multiply out, this product on top of this ratio, of this

first fraction,

then pi subscript theta S0 A0, that would cancel out this pi subscript

theta S0 A0

and replace it with the derivative with respect to theta of pi theta S0 A0. So [inaudible] algebra was

the second. But

that term on top is just

what I worked out previously

- was the joint probability of the state action sequence,

and now I have that times that times the payoff.

And so by the definition of expectation, this is just equal to that thing times the payoff.

So

this thing inside the expectation, this is exactly

the step that we were taking in the inner group of our reinforce algorithm,

roughly the reinforce algorithm. This

proves that the expected value of our change to theta

is exactly in the direction of the gradient of our expected payoff. That's how

I started this whole derivation. I said

let's look at our expected payoff and take the derivative of that with respect to theta.

What we've proved is that on expectation,

the step direction I'll take reinforce is exactly the gradient of

the thing I'm trying to

optimize. This shows that this algorithm is

a stochastic gradient ascent

algorithm. I wrote a lot. Why don't you take a minute to look at the equations and [inaudible]

check if everything makes sense. I'll erase a couple of boards and then check if you have

questions after that. Questions?

Could you

raise your hand if this makes sense?

Great.

Some of the comments - we talked about

those value function approximation approaches where you approximate

V star, then you go from V star

to pi star. Then here was also policy search approaches, where you try to approximate the policy directly.

So let's talk briefly about when either one may be preferable.

It turns out that

policy search algorithms are especially effective

when you can choose a simple policy class pi.

So the question really is for your problem

does there exist a simple function like a linear function or a logistic function

that maps from features of the state to the action that works pretty well.

So the problem with the inverted pendulum - this is quite likely to be true.

Going through all the different choices of parameters, you can say

things like if the pole's leaning towards the right,

then accelerate towards the right to try to catch it. Thanks to the

inverted pendulum, this is probably true. For lots of what's called

low level control tasks, things like driving a car,

the low level reflexes of do you steer your car left to avoid another car, do

you steer your car left to follow the car road, flying a helicopter,

again very short time scale types of decisions - I like to think of these as

decisions like trained operator for like a trained driver or a trained

pilot. It would almost

be a reflex, these sorts of very quick instinctive things where

you map very directly from the inputs, data, and action. These are

problems for which

you can probably choose a reasonable policy class like a logistic function or something,

and it will often work well.

In contrast, if you have problems that require

long multistep reasoning, so things like a game of chess where you have to

reason carefully about if

I do this, then they'll do that, then they'll do this, then they'll do that.

Those I think of as less instinctual, very high level decision making.

For problems like that,

I would sometimes use a value function approximation approaches instead. Let

me say more about this later.

The last thing I want to do is actually tell you about -

I guess just as a side comment,

it turns out also that if you have POMDP, if you have a partially observable

MDP - I don't want to say too much about this -

it turns out that if you only have an approximation

- let's call it S hat of the true

state, and so this could be S hat equals S of T given T from Kalman filter -

then you can still use these sorts of policy search algorithms where you can say pi theta of S

hat comma A - There are various other ways you can use

policy search algorithms for POMDPs, but this is one of them

where if you only have estimates of the state, you can then

choose a policy class that only looks at your estimate of the state to choose the action.

By using the same way of estimating the states in both training and testing,

this will usually do some -

so these sorts of policy search algorithms can be applied

often reasonably effectively to

POMDPs as well. There's one more algorithm I wanna talk about, but some final

words on the reinforce algorithm. It turns out the reinforce algorithm

often works well but is often extremely slow. So it [inaudible]

works, but one thing to watch out for is that because you're taking these

gradient ascent steps that are very noisy, you're sampling a state action sequence, and then

you're sort of

taking a gradient ascent step in essentially a sort

of random direction that only on expectation is

correct. The

gradient ascent direction for reinforce can sometimes be a bit noisy,

and so it's not that uncommon to need like a million iterations of gradient ascent,

or ten million, or 100 million

iterations of gradient ascent

for reinforce [inaudible], so that's just something to watch out for.

One consequence of that is in the reinforce algorithm - I shouldn't

really call it reinforce. In what's essentially the reinforce algorithm, there's

this step where you need to sample a state action sequence.

So in

principle you could do this on your own robot. If there were a robot you were trying to

control, you can actually

physically initialize in some state, pick an action and so on, and go from there

to sample a state action sequence.

But

if you need to do this ten million times, you probably don't want to [inaudible]

your robot ten million times.

I personally have seen many more applications of reinforce in simulation.

You can easily run ten thousand simulations or ten million simulations of your robot in

simulation maybe, but you might not want to do that -

have your robot physically repeat some action ten million times.

So I personally have seen many more applications of reinforce

to learn using a simulator

than to actually do this on a physical device.

The last thing I wanted to do is tell you about one other algorithm,

one final policy search algorithm. [Inaudible] the laptop display please. It's

a policy search algorithm called Pegasus that's

actually what we use on our autonomous helicopter flight things

for many years. There are some other things we do now. So

here's the idea. There's a

reminder slide on RL formalism. There's nothing here that you don't know, but

I just want to pictorially describe the RL formalism because I'll use that later.

I'm gonna draw the reinforcement learning picture as follows. The

initialized [inaudible]

system, say a

helicopter or whatever in sum state S0,

you choose an action A0,

and then you'll say helicopter dynamics takes you to some new state S1, you choose

some other action A1,

and so on.

And then you have some reward function, which you reply to the sequence of states you summed out,

and that's your total payoff. So

this is just a picture I wanna use to summarize the RL problem.

Our goal is to maximize the expected payoff,

which is this, the expected sum of the rewards.

And our goal is to learn the policy, which I denote by a green box.

So our policy - and I'll switch back to deterministic policies for now.

So my deterministic policy will be some function mapping from the states to the actions.

As a concrete example, you imagine that in the policy search setting,

you may have a linear class of policies.

So you may imagine that the action A will be say a linear function of the states,

and your goal is to learn the parameters of the linear function.

So imagine trying to do linear progression on policies, except you're trying to optimize the reinforcement learning

objective. So just [inaudible] imagine that the action A

is state of transpose S, and you go and policy search this to come up with

good parameters theta so as

to maximize the expected payoff. That would be one setting in which this picture applies. There's the idea.

Quite often

we come up with a model or a simulator for the MDP, and as before

a model or a simulator is just a box

that takes this input

some state ST,

takes this input some action AT,

and then outputs some [inaudible] state ST plus one that you might want to take in the MDP.

This ST plus one will be a random state. It will be drawn from

the random state transition probabilities of MDP.

This is important. Very important, ST plus one

will be a random function ST and AT. In the simulator, this is [inaudible].

So for example, for autonomous helicopter flight, you [inaudible] build a simulator

using supervised learning, an algorithm like linear regression

[inaudible] to linear regression,

so we can get a nonlinear model of the dynamics of what ST

plus one is as a random function of ST and AT. Now

once you have a simulator,

given any fixed policy you can quite

straightforwardly evaluate any policy in a simulator.

Concretely, our goal is to find the policy pi mapping from states to actions, so the goal is to find the green box

like that. It works well.

So if you have any one fixed policy pi,

you can evaluate the policy pi just using the simulator

via the picture shown at the bottom of the slide.

So concretely, you can take your initial state S0,

feed it into the policy pi,

your policy pi will output some action A0, you plug it in

the simulator, the simulator outputs a random state S1, you feed

S1 into the policy and so on, and you get a sequence of states S0 through ST

that your helicopter flies through in simulation.

Then sum up the rewards,

and this gives you an estimate of the expected payoff of the policy.

This picture is just a fancy way of saying fly

your helicopter in simulation and see how well it does, and measure the sum of

rewards you get on average in the simulator. The

picture I've drawn here assumes that you run your policy through the

simulator just once. In general,

you would run the policy through the simulator

some number of times and then average to get an average over M

simulations to get a better estimate of the policy's expected payoff.

Now that I have a way

- given any one fixed policy,

this gives me a way to evaluate the expected payoff of that policy.

So one reasonably obvious thing you might try to do is then

just search for a policy,

in other words search for parameters theta for your policy, that

gives you high estimated payoff.

Does that make sense? So my policy has some parameters theta, so

my policy is

my actions A are equal to theta transpose S say if there's a linear policy.

For any fixed value of the parameters theta,

I can evaluate -

I can get an estimate for how good the policy is using the simulator.

One thing I might try to do is search for parameters theta to try to

maximize my estimated payoff.

It turns out you can sort of do that,

but that idea as I've just stated is hard to get to work.

Here's the

reason. The simulator allows us to evaluate

policy, so let's search for policy of high

value. The difficulty is that the simulator is random,

and so every time we evaluate a policy,

we get back a very slightly different answer. So

in the

cartoon below, I want you to imagine that the horizontal axis is the space of policies.

In other words, as I vary the

parameters in my policy, I get different points on the horizontal axis here. As I

vary the parameters theta, I get different policies,

and so I'm moving along the X axis,

and my total payoff I'm gonna plot on the vertical axis,

and the red line in this cartoon is the expected payoff of the different

policies.

My goal is to find the policy with the highest expected payoff.

You could search for a policy with high expected payoff, but every time you evaluate a policy

- say I evaluate some policy,

then I might get a point that

just by chance looked a little bit better than it should have. If

I evaluate a second policy and just by chance it looked a little bit worse. I evaluate a third

policy, fourth,

sometimes you look here - sometimes I might actually evaluate exactly the same policy

twice and get back slightly different

answers just because my simulator is random, so when I apply the same policy

twice in simulation, I might get back slightly different answers.

So as I evaluate more and more policies, these are the pictures I get.

My goal is to try to optimize the red line. I hope you appreciate this is a

hard problem, especially when all [inaudible] optimization algorithm gets to see are these

black dots, and they don't have direct access to the red line.

So when my input space is some fairly high dimensional space, if I have

ten parameters, the horizontal axis would actually be a 10-D space,

all I get are these noisy estimates of what the red line is. This is a very hard

stochastic optimization problem.

So it turns out there's one way to make this optimization problem much easier. Here's the idea.

And the method is called Pegasus, which is an acronym for something.

I'll tell you later.

So the simulator repeatedly makes calls

to a random number generator

to generate random numbers RT, which are used to simulate the stochastic dynamics.

What I mean by that is that the simulator takes this input of state

and action, and it outputs the mixed state randomly,

and if you peer into the simulator, if you open the box of the simulator and ask

how is my simulator generating these random mixed states ST plus one,

pretty much the only way to do so - pretty much the only way

to write a simulator with random outputs is

we're gonna make calls to a random number generator,

and get random numbers, these RTs,

and then you have some function that takes this input S0, A0, and

the results of your random number generator,

and it computes some mixed state as a function of the inputs and of the random

number it got from the random number

generator. This is

pretty much the only way anyone implements any random code, any code

that generates random outputs. You make a call to a random number generator,

and you compute some function of the random number and of your other

inputs. The reason that when you evaluate different policies you get

different answers

is because

every time you rerun the simulator, you get a different sequence of random

numbers from the random number generator,

and so you get a different answer every time,

even if you evaluate the same policy twice.

So here's the idea.

Let's say we fix in advance the sequence of random numbers,

choose R1, R2, up to RT minus one.

Fix the sequence of random numbers in advance,

and we'll always use the same sequence of random numbers

to evaluate different policies. Go

into your code and fix R1, R2, through RT minus one.

Choose them randomly once and then fix them forever.

If you always use the same sequence of random numbers, then

the system is no longer random, and if you evaluate the same policy twice,

you get back exactly the same answer.

And so these sequences of random numbers, [inaudible] call them scenarios, and

Pegasus is an acronym for policy evaluation of gradient and search using scenarios.

So

when you do that, this is the picture you get.

As before, the red line is your expected payoff, and by fixing the random numbers,

you've defined some estimate of the expected payoff.

And as you evaluate different policies, they're

still only approximations to their true expected payoff, but at least now you have

a

deterministic function to optimize,

and you can now apply your favorite algorithms, be it gradient ascent or

some sort

of local [inaudible] search

to try to optimize the black

curve. This gives you a much easier

optimization problem, and you

can optimize this to find hopefully a good policy. So this is

the Pegasus policy search method.

So when

I started to talk about reinforcement learning, I showed

that video of a helicopter flying upside down. That was actually done using

exactly method, using exactly this policy search algorithm. This

seems to scale well

even to fairly large problems, even to fairly high dimensional state spaces.

Typically Pegasus policy search algorithms have been using -

the optimization problem

is still - is much easier than the stochastic version, but sometimes it's

not entirely trivial, and so

you have to apply this sort of method with

maybe on the order of ten parameters or tens of parameters, so 30, 40

parameters, but

not thousands of parameters,

at least in these sorts of things with them.

So is that method different than just assuming that

you know your simulator exactly, just throwing away all the random numbers entirely? So is this different from assuming that

we have a deterministic simulator?

The answer is no. In the way you do this,

for the sake of simplicity I talked about one sequence of random numbers.

What you do is -

so imagine that the random numbers are simulating different wind gusts against your helicopter.

So what you want to do isn't really evaluate just against one pattern of wind gusts.

What you want to do is

sample some set of

different patterns of wind gusts, and evaluate against all of them in average.

So what you do is you actually

sample say 100 -

some number I made up like 100 sequences of random numbers,

and every time you want to evaluate a policy,

you evaluate it against all 100 sequences of random numbers and then average.

This is in exactly the same way that on this earlier picture

you wouldn't necessarily evaluate the policy just once. You evaluate it maybe 100

times in simulation, and then

average to get a better estimate of the expected reward.

In the same way,

you do that here

but with 100 fixed sequences of random numbers. Does that make sense? Any

other questions? If we use 100 scenarios and get an estimate for the policy, [inaudible] 100 times [inaudible] random numbers [inaudible] won't you get similar ideas [inaudible]?

Yeah. I guess you're right. So the quality - for a fixed policy,

the quality of the approximation is equally good for both cases. The

advantage of fixing the random numbers is that you end up with

an optimization problem that's much easier.

I have some search problem,

and on the horizontal axis there's a space of control policies,

and my goal is to find a control policy that

maximizes the payoff.

The problem with this earlier setting was that

when I evaluate policies I get these noisy estimates,

and then it's

just very hard to optimize the red curve if I have these points that are all over the

place. And if I evaluate the same policy twice, I don't even get back the same

answer. By fixing the random numbers,

the algorithm still doesn't get to see the red curve, but at least it's

now optimizing a deterministic function. That makes the

optimization problem much easier. Does

that make sense? Student:So every time you fix the random numbers, you get a nice curve to optimize. And then you change the random numbers to get a bunch of different curves

that are easy to optimize. And then you smush them together?

Let's see.

I have just one nice black curve that I'm trying to optimize. For each scenario.

I see. So I'm gonna average over M scenarios, so I'm gonna average over 100 scenarios.

So the black curve here is defined by averaging over

a large set of scenarios. Does that make sense?

So instead of only one - if the averaging thing doesn't make sense, imagine that there's

just one sequence of random numbers. That might be easier to think

about. Fix one sequence of random numbers, and every time I evaluate another policy,

I evaluate against the same sequence of random numbers, and that gives me

a nice deterministic function to optimize.

Any other questions?

The advantage is really

that - one way to think about it is when I evaluate the same policy twice,

at least I get back the same answer. This gives me a deterministic function

mapping from parameters in my policy

to my estimate of the expected payoff.

That's just a function that I can try to optimize using the search algorithm.

So we use this algorithm for inverted hovering,

and again policy search algorithms tend to work well when you can find

a reasonably simple policy mapping from

the states to the actions. This is sort of especially the low level control tasks,

which I think of as sort of reflexes almost.

Completely,

if you want to solve a problem like Tetris where you might plan

ahead a few steps about what's a nice configuration of the board, or

something like a game of chess,

or problems of long path plannings of go here, then go there, then go there,

then sometimes you might apply a value function method instead.

But for tasks like helicopter flight, for

low level control tasks, for the reflexes of driving or controlling

various robots, policy search algorithms were easier -

we can sometimes more easily approximate the policy directly works very well.

Some [inaudible] the state of RL today. RL algorithms are applied

to a wide range of problems,

and the key is really sequential decision making. The place where you

think about applying reinforcement learning algorithm is when you need to make a decision,

then another decision, then another decision,

and some of your actions may have long-term consequences. I think that

is the heart of RL's sequential decision making, where you make multiple decisions,

and some of your actions may have long-term consequences. I've shown you

a bunch of robotics examples. RL

is also

applied to thinks like medical decision making, where you may have a patient and you

want to choose a sequence of treatments, and you do this now for the patient, and the

patient may be in some other state, and you choose to do that later, and so on.

It turns out there's a large community of people applying these sorts of tools to queues. So

imagine you have a bank where you have people lining up, and

after they go to one cashier,

some of them have to go to the manager to deal with something else. You have

a system of multiple people standing in line in multiple queues, and so how do you route

people optimally to minimize the waiting

time. And not just people, but

objects in an assembly line and so on. It turns out there's a surprisingly large community

working on optimizing queues.

I mentioned game playing a little bit already. Things

like financial decision making, if you have a large amount of stock,

how do you sell off a large amount - how do you time the selling off of your stock

so as to not affect market prices adversely too much? There

are many operations research problems, things like factory automation. Can you design

a factory

to optimize throughput, or minimize cost, or whatever. These are all

sorts of problems that people are applying reinforcement learning algorithms to.

Let me just close with a few robotics examples because they're always fun, and we just

have these videos.

This video was a work of Ziko Coulter and Peter Abiel, which is a PhD student

here. They were working getting a robot dog to climb over difficult rugged

terrain. Using a reinforcement learning algorithm,

they applied an approach that's

similar to a value function approximation approach, not quite but similar.

They allowed the robot dog to sort of plan ahead multiple steps, and

carefully choose his footsteps and traverse rugged terrain.

This is really state of the art in terms of what can you get a robotic dog to do.

Here's another fun one.

It turns out that

wheeled robots are very fuel-efficient. Cars and trucks are the

most fuel-efficient robots in the world almost.

Cars and trucks are very fuel-efficient,

but the bigger robots have the ability to traverse more rugged terrain.

So this is a robot - this is actually a small scale mockup of a larger

vehicle built by Lockheed Martin,

but can you come up with a vehicle that

has wheels and has the fuel efficiency of wheeled robots, but also

has legs so it can traverse obstacles.

Again, using a reinforcement algorithm to design a controller for this robot to make it traverse obstacles, and

somewhat complex gaits that would be very hard to design by hand,

but by choosing a reward function, tell the robot

this is a plus one reward that's top of the goal,

and a few other things, it learns these sorts of policies automatically.

Last couple fun ones - I'll show you a couple last helicopter videos.

This is the work of again PhD students here, Peter Abiel and Adam Coates

who have been working on autonomous flight. I'll just let you watch. I'll just

show you one more. [Inaudible] do this with a real helicopter [inaudible]?

Not a full-size helicopter.

Only small radio control helicopters. [Inaudible]. Full-size helicopters

are the wrong design for this. You shouldn't do this on a full-size helicopter.

Many full-size helicopters would fall apart if you tried to do this. Let's see. There's one more.

Are there any human [inaudible]? Yes,

there are very good human pilots that can.

This is just one more

maneuver. That was kind of fun. So this is the work of

Peter Abiel and Adam Coates. So that was it. That was all the technical material

I wanted to present in this class. I guess

you're all experts on machine learning now. Congratulations.

And as I hope you've got the sense through this class that this is one of the technologies

that's really having a huge impact on science in engineering and industry.

As I said in the first lecture, I think many people use machine

learning algorithms dozens of times a day without even knowing about it.

Based on the projects you've done, I hope that

most of you will be able to imagine yourself

going out after this class and applying these things to solve a variety of problems.

Hopefully, some of you will also imagine yourselves

writing research papers after this class, be it on

a novel way to do machine learning, or on some way of applying machine

learning to a problem that you care

about. In fact, looking at project milestones, I'm actually sure that a large fraction of

the projects in this class will be publishable, so I think that's great.

I guess many of you will also go industry, make new products, and make lots

of money using learning

algorithms. Remember me

if that happens. One of the things I'm excited about is through research or

industry, I'm actually completely sure that the people in this class in the

next few months

will apply machine learning algorithms to lots of problems in

industrial management, and computer science, things like optimizing computer architectures,

network security,

robotics, computer vision, to problems in computational biology,

to problems in aerospace, or understanding natural language,

and many more things like that.

So

right now I have no idea what all of you are going to do with the learning algorithms you learned about,

but

every time as I wrap up this class, I always

feel very excited, and optimistic, and hopeful about the sorts of amazing

things you'll be able to do.

One final thing, I'll just give out this handout.

One final thing is that machine learning has grown out of a larger literature on the AI

where

this desire to build systems that exhibit intelligent behavior and machine learning

is one of the tools of AI, maybe one that's had a

disproportionately large impact,

but there are many other ideas in AI that I hope you

go and continue to learn about. Fortunately, Stanford

has one of the best and broadest sets of AI classes, and I hope that

you take advantage of some of these classes, and go and learn more about AI, and more

about other fields which often apply learning algorithms to problems in vision,

problems in natural language processing in robotics, and so on.

So the handout I just gave out has a list of AI related courses. Just

running down very quickly, I guess, CS221 is an overview that I

teach. There

are a lot of robotics classes also: 223A,

225A, 225B

- many robotics class. There are so many applications

of learning algorithms to robotics today. 222

and 227 are knowledge representation and reasoning classes.

228 - of all the classes on this list, 228, which Daphne

Koller teaches, is probably closest in spirit to 229. This is one of

the classes I highly recommend

to all of my PhD students as well.

Many other problems also touch on machine learning. On the next page,

courses on computer vision, speech recognition, natural language processing,

various tools that aren't just machine learning, but often involve machine learning in many ways.

Other aspects of AI, multi-agent systems taught by [inaudible].

EE364A is convex optimization. It's a class taught by

Steve Boyd, and convex optimization came up many times in this class. If you

want to become really good at it, EE364 is a great class. If you're

interested in project courses, I also teach a project class

next quarter where we spend the whole quarter working

on research projects.

So I hope you go and take some more of those classes.

In closing,

let me just say

this class has been really fun to teach, and it's very satisfying to

me personally when we set these insanely difficult hallmarks, and

then we'd see a solution, and I'd be like, "Oh my god. They actually figured that one out." It's

actually very satisfying when I see that.

Or looking at the milestones, I often go, "Wow, that's really cool. I bet this would be publishable,"

So

I hope you take what you've learned, go forth, and

do amazing things with learning algorithms.

I know this is a heavy workload class, so thank you all very much for the hard

work you've put into this class, and the hard work you've put into learning this material,

and

thank you very much for having been students in.