So we talked a little bit about value iteration.
And we said, that eventually, it identifies an optimal policy and
polynomial time, in 1 over 1 minus gamma.
And I pointed out that, 1 over 1 minus gamma isn't really
a polynomial in the number of bits that it takes to write down gamma.
because you can, with every few bits, specify a number that's very,
very close to 1, causing this value to explode.
So, in fact, value iteration doesn't give us a polynomial time algorithm for
solving MDPs.
There is only one way that we know to solve MDPs in polynomial time and
that is, [SOUND], Linear Programming.
>> Okay.
>> Do you know what Linear Programming is?
>> I'm going to say yes.
>> All right.
So it's optimization framework, in which,
you can give linear constraint in a linear objective function.
And in polynomial time, as long as the number of variables and
constraints is polynomial, get a solution.
>> That's exactly what I was going to say.
>> Yeah, well, this is why I was going to say it for you.
>> Thank you. >> So if we're going to use this idea
to solve Markov decision processes, we need a way of
encoding a Markov decision process solution as a linear program.
So we need to encode our MDP as a linear program.
So linear constraints and a linear objective function.
So how do we know how to solve a MDP?
>> We just have to solve the Bellman equation.
>> Bellman Equation.
Right.
I can write the Bellman equation in terms of the value function as a set of
equations where the variables are the value function that we're interested in.
So for each state s, we have a variable v sub s.
And we relate the v sub s' through this equation to the v sub s primes which
are themselves just v sub s', just ordered in a different way.
And that seems really good, right?
We have a set of constraints.
And if we could just solve this set of constraints, we'll be good to go.
So are we done?
Do we have a way of doing this with linear programming directly from this
expression?
>> Not if max, unless max has become linear since I last looked, no.
>> Right, which they're not so much.
Yeah, so since the max over actions in not a linear operator,
this isn't translatable directly to a set of linear equations and
a linear objective function.
We have a system of non-linear equations, but that's not so good.
So, the cool thing about max is that we can actually think about max as
being specifiable in terms of a set of linear constraints,
and a linear objective function.
Let's think of it this way.
Let's say, that we're trying to compute a max, and
this is just as a simple little concrete example.
Here's a thing that we're trying to compute the max of.
And the max is going to be some value x.
What is the relationship between x and all these values?
So what's the relationship between x and -3?
>> X is greater than -3.
>> Greater than -3, or in general, we could say greater than or equal to.
>> Mm-hm, I knew that's what you were going to say.
>> Yeah, you know, it's always nicer to have or equal to's,
it's more inclusive that way.
>> Mm-hm.
>> And we can say the same thing about 7, right?
X is going to be greater than or equal to 7.
And x is going to be greater than or equal to 2.
And x is going to be greater than or equal to 5.
And how do we know this?
Because it's the max of those.
So it has to be at least as big as any one of them, right?
>> Right.
By the way, your bottom thing says equals.
>> Greater than or equal to.
>> Mm-hm.
>> It could be equal to 5, if I get rid of the 7.
>> Yes.
[LAUGH] >> All right, so
this is a set of constraints, of inequality constraints.
Right?
So is it true that now,
the solution to this set of inequality constraints is exactly the max?
>> No.
>> And why is that?
>> Because 9 is also greater than or equal to all of those things.
>> It is!
And 9 is the max of these things.
>> No.
No, that's not quite true.
>> No.
So what do we have to say?
We have to say that, it's bigger than equal to all these things.
And of all the things that are bigger than equal to all these things,
we want the smallest such x.
We want the x that is the smallest possible while still satisfying all of
these constraints.
In this case, that's going to have to be 7.
>> Right.
>> Right, because 7 is bigger than all the other ones, and
you can't get any smaller without getting smaller than 7.
>> Right, and of course, min is a linear operator so we're good.
>> No, no, no, min is an objective function.
This is a linear objective function.
This is okay.
>> Good, good, good.
>> That's what we are going to do.
We are going to generalize this idea to the equations in the Bellman
equation in a very similar way.
>> I look forward to it.