We didn't go into enough detail about what it is we're trying to
optimize here.
I just said something vague like we want to maximize the sum of our reward.
Well, it's not so simple, in fact, here's a great story to illustrate that.
There's a great Russian comedian, Yakov Smirnoff,
you may remember him or not, but he told this joke once that I really loved.
He said, have you heard about the Soviet lottery,
it's a million rubles if you win, one ruble a year for a million years.
So the point is, and if you recall from one of our earlier lessons,
that one dollar or one ruble delivered to us a million years in the future
is really not as valuable as a dollar or ruble that we get now.
And so, for instance, if we think about a robot living forever,
it might do something just mundane to gather a dollar a year.
That's an infinite amount of money, but
in practice it doesn't really work that well.
So to consider that, and to illustrate that,
I'm going to show you a little maze problem here, and we'll think about
what the robot ought to do that would be optimal in this maze.
So here's our robot, and here's the challenge for our robot.
We have a reward here of $1 and a reward over here of $1 million.
So if the robot comes over here and gets this $1, it's special in that each
time he touches it, he gets $1 and it goes away but then it comes back.
So the robot could come here go back and
forth and get a dollar each time it moves here.
This one, once the robot tags it, it's gone.
But clearly it's worthwhile to come over here and grab it.
Now this red area is obstacle, it can't go there.
And here I wrote some rewards that the robot,
in fact negative one is a penalty.
But the penalties the robot would get as it went this way, and
zero penalty that way.
Now, if we say that what we want to optimize is the sum of all future
rewards, then it doesn't matter whether we go this way and
just get that dollar over and over and over again.
Or if we go this way, get the million dollars,
come back and get that $1 over and over and over again.
Now there's no difference because they both sum to infinity over time.
Now what if we say, okay, I want to optimize my reward over three moves.
So I've got a finite horizon.
Let's consider the rewards we get with a finite horizon of three
if we go this way versus this way.
So if we go this way, we're going to get rewards of -1,
-1, -1, and if we go this way we get zero,
$1, and then we have to move down here, and get another zero.
So clearly, starting here,
with a finite horizon of three, the best thing to do is go up there.
Now, if we extend the horizon a little bit further, say out to eight,
we would find that this is the best thing to do.
So if we go this way,
we get -1, -1, -1, until we hit the jackpot here and get $1M.
Clearly if you sum this up, it's a pretty good prize.
If we go this way and touch that $1 over and over again, we get this.
So clearly as we expand our finite horizon trivially up to say eight steps,
going this way and tagging at one million is the best thing to do.
If we carried it even further, we'd discover that then we should come back
this way and go to that dollar and tag it over and over and over again.
Let me formalize these a little bit.
With the infinite horizon what we're trying to maximize is the sum
of all rewards over all of the future.
So it's the sum of each of these rewards for i equals one to infinity.
The finite horizon is very similar, it's just we don't go to infinity.
So for optimizing over horizon of four steps, n would be four.
We're just trying to maximize the sum of the reward for the next four steps.
Now, there is yet another formulation that if you think
back to that lecture a while back about what's the value of a future dollar.
We can dig that up and
it makes a lot of sense in terms of reinforcement learning.
So remember that if it takes us say, four years to get a dollar,
that dollar is less valuable than say if it takes one year.
And the same way, if it takes, say, eight steps to make a dollar,
that dollar is less valuable than a dollar I can get just in one step.
And the way we represent that is very simple.
Just like we represented the sum of future dividends and
it looks like this, it's called discounted reward.
So instead of just summing up the r sub i is we multiply it by this factor
gamma to the i minus 1, such that our immediate reward, the very next one
we get, whatever gamma is when it gets raised to the zero power is just one.
So that means for the very next step we get r.
But for the step after it, it's gamma to the one.
So it devalues that reward a little bit.
Gamma is a value between zero and one,
the closer it is to one, the more we value rewards in the future.
The closer it is to zero, the less we value rewards in the future.
In fact, if gamma is set equal to one,
this is exactly the same as the infinite horizon.
But gamma relates very strongly to interest rates if you recall.
So, if say, gamma were 0.95 it means each step in the future is
worth about 5% less than the immediate reward if we got it right away.
This is the method that we use in q learning.
One reason is that the math turns out to be very handy, and
it provides nice conversion properties.