Charles I'm going to say that you invented an algorithm just now
that we're going to call policy iteration.
It's kind of like value iteration,
except it's going to iterate a policy space.
>> I'm so smart >> Yeah,
though you invented it a little bit to late,
because it dates back to 1960 or thereabout.
>> Dijkstra?
Dijkstra always has ideas before I do.
>> Yes. Dijkstra's pretty clever, but
this is actually Ron Howard.
>> You mean the Ron Howard?
The director?
>> Oh, sorry.
No. It's the Ron Howard.
The algorithm designer.
[LAUGH] >> Oh, that one.
I always get them confused.
>> One played Opie.
>> And the other one proved contraction mappings.
>> They're very similar things.
>> So this is what I was imagining you were explaining.
Take it step by step.
So what we're going to do is we're going to start off picking an arbitrary
Q function like we often do.
We'll call that the initialization step.
Then, we're going to iterate the following.
We're going to take the t-th Q function.
And compute its greedy policy.
Call that pi sub t, then, that policy,
we're going to evaluate it to get a new Q function, Q 2 plus 1, and
then we're going to repeat, and iterate this over and over and over again.
So each time we go around this loop, we're taking our previous Q function.
>> Finding it's policy, taking that policy,
finding its value function and repeating.
>> Lather, rinse, repeat.
>> Exactly.
So unlike when I take a shower, we actually get convergence in finite time.
>> [LAUGH] >> So
in particular the sequence of Q functions that we get converges to Q*.
Which is good, that's like how policy iteration works.
But even better, convergence is exact and complete in finite time.
I guess that was kind of true of value iteration as well.
And it converges at least as fast as value iterationm in that
if at any point we sync up the Q functions, we start value iteration and
policy iteration from the same Q function.
Then each step that policy iteration takes is moving us towards
the optimal Q function, no more slowly than valued iteration does.
>> Okay.
>> So that kind of suggests that this is just way better.
>> Yeah, isn't it way better?
>> So, why is it not way better?
There's kind of some excitement going on in here that we need to take
into consideration.
There is a bit of trade-off as you like to say.
Mm-hm. What's the trade-off?
>> So where's the trade-off here?
We're getting faster convergence at the cost of greater computational expense.
So in particular this step, this policy evaluation step that says
take the policy and then work out the Q function for that policy.
You can do that by say solving a system of linear equations.
Or perhaps more commonly,
by writing something like value iteration to completion.
So in the inner loop of policy iteration is something that's
an awful lot like value iteration.
And so maybe it's not so
surprising that it goes at least as fast as value iteration.
It's doing a lot more work than value iteration.
Each iteration of policy iteration is doing pretty much all the work
of value iteration.
Yeah, well, so, it just depends upon what you're counting.
I say we just count the outer loop.
Then we win.
Or at least we don't lose.
In fact, this is kind of an interesting outstanding question.
So, we don't really know how many iterations policy iteration takes, so
an open question is what the convergence time really is.
We know a couple things about it, but it turns out to be fairly weak.
We know that there are some MDPs.
Such that the number of iterations, the policy iteration takes, is linear.
It's at least as large as the number of states in the MBP, though
I don't think anybody's actually shown like two times the number of states.
So all we know is something really, really basic which is that it
takes at least the number of states iterations, in theworst case.
And we know it can't be any worse than number of
actions raised to the number of states an exponential.
But where is it's in between we don't really know.
And so if it's closer to linear, then it's totally awesome and
it blows the doors off value iteration.
If it's more like exponential, then It's probably still better than
value iteration, but it's definitely more of a wash.