So in order to elaborate on all of that,
Michael, I want to ask you a simple question.
And here it is.
What makes reinforcement learning hard?
>> I'm going to say living on the streets.
>> Makes reinforcement learning hard?
>> Yeah, it sort of hardens it.
>> Let me let me ask that question slightly differently.
>> Okay.
>> From a computational point of view, from an algorithmic point of view,
what makes reinforcement learning hard?
>> So well there's a lot of things we've been talking about.
There's the notion of delayed reward is a very tricky thing.
>> I like that one, I like that one enough for me to write it down.
>> You're not going to wait?
>> No, I'm not going to wait,
I'm just going to write it down right now because it's ironic that way.
>> And a related issue well there's two pieces in that.
There's a delay and there's a reward.
The reward part is like unlike say supervised learning
reinforcement learning is trying to do its job based on very weak feedback.
That it's only told how it's doing and not necessarily what it should be doing.
>> Right which makes it very different from normal function approximation,
in the way that we think about in supervised learning.
Okay, what else?
>> If we do try to use something like supervised learning,
one thing that makes the function approximation hard is
the idea that it's kind of a moving target.
We tend to base our estimates on our current estimates,
as opposed to anything kind of legitimately valid in the world.
Right, so doing estimates based on estimates is, well,
like averaging averages.
>> Okay, I want to say bootstrapping is the issue.
>> Yeah I agree with that.
Bootstrapping is sort of a problem.
I think I would probably summarize that as the problem with the need to do
good exploration.
And that's a little different from the normal supervised
learning set up where you've got a bunch of training examples.
Here because you only have estimates in the reinforcement learning context,
you have to do a bunch of extra things to actually figure
out how to get good estimates so that you can actually do good learning.
So one more thing I think sort of worth mentioning that makes this sort of hard
and it's kind of very basic kind of computational problems, right.
You know when we describe computation complexity we talk about it in terms
of big o.
And the question is big o of what?
So what's the what here?
What's the in, in our big o that makes ROR?
>> Well there's a lot of them.
>> Like what?
>> Well I mean if we're thinking about sort of M.V.P.
style reinforcement learning then the size of the state space is a big o.
>> Mm hm.
>> The size of the temporal window in some sense,
like how how delayed is the reward.
>> Mm hm. >> There's
issues on what could be the actions as well.
There's lots of things that could scale.
But I guess what makes state super hard is that you can very easily specify
a problem that has a state space with an exponential number of states
that is still relatively simple, but algorithms that don't generalize
between states are not going to be able to learning them very effectively.
>> I think all of what you said is true.
Some of it, I think, is kind of captured not necessarily as explicitly in
the first two bullet points.
But I'd like to focus on states and actions.
The problem is that the learning that we need to do grows super linearly
in general, we aren't very, very careful and smart in the number of states and
the number of actions.
And so we really need to have kind of clever ways of thinking about
learning across multiple states and perhaps multiple actions.
And in fact when you talked about function approximation and
generalization, I would claim that at least in sort of this discussion,
we could talk about that as a way of dealing with generalizing overstates,
that you did function approximation over value functions.
Right, so here you tried one way of dealing with the problem of scale
when it comes to states.
Is well, if I learn something about one state,
I want to somehow have that teach me something about a bunch of other states.
And then I won't have to visit every single state an infinite number of
times, and take every action an infinite number of times.
And that's really good, that's really important, right, and
the trick here is I can see many, many states by just seeing a single state and
that's what function approximation over the value functions actually gives me.
Agreed? >> Yeah I don't know that I'd say it
quite that way, but that we learn about many states
when we learn about other states or something like that.
But yeah, that's absolutely the way I was thinking about function
approximation is helping us to kind of fill in the gaps for
states that we haven't visited nearly as often.
>> So in fact, I could be aggressive and ask you the question,
why did you do all those function approximation over states but
you didn't do any function approximation over actions, Michael?
>> That would be aggressive >> And
the [LAUGH] I don't have a wonderful answer to that.
I mean that it's tradition, in the sense that a lot of the MDPs that people have
been working with really do try to keep the action space relatively small and
expand in the state space but that's not really that good of an answer.
I think action, large actions bases are really important tom we just don't have
as good ways to deal with them.
For one thing the computing the max ends up being hard in q learning.
>> Right so in fact what I'm going to try to talk about in the rest of
the lesson is trying to do To generalizations of the sort of
generalization that you are talking about and
think about how we can learn about actions and how we can
abstract over actions in the same way that you are abstracting over states.
>> That seems great and a little bit meta.
>> A little bit meta.
And so that's why the lessons generalizing over generalizing and
the whole point in the end I'm going to claim other than just sort of
it's interesting in and of itself is that it's going to allow us to scale.
So all of these tricks ultimately have a kind of practical use
including function approximation of allowing us to scale.