Voiceover: Hey everyone and welcome back to this class, 2 2
artificial intelligence reinforcement learning in Python. 3 3
In this section of the course, we are going 4 4
to start looking at solutions to MDPs. 5 5
The entire last section was just 6 6
to set the problem up and define terms. 7 7
As you saw, the centrepiece 8 8
of the last section was the Bellman Equation. 9 9
In fact, the Bellman Equation can be used 10 10
directly to solve for the value function. 11 11
If you look carefully, you'll see that this is actually 12 12
a set of S equations with S unknowns. 13 13
In fact it is a linear equation which means 14 14
that it's not too hard to solve. 15 15
In addition, a lot of the matrix entries will be zero 16 16
since probably the state transitions will be sparse. 17 17
However, this is not the approach we'll take. 18 18
Instead we'll do what is called iterative policy evaluation. 19 19
What is iterative policy evaluation? 20 20
Essentially, it means we apply the Bellman Equation 21 21
again and again and eventually it will just converge. 22 22
This makes sense since at the point we found the solution, 23 23
the left hand side will equal the right hand side, 24 24
so any further iteration won't change anything. 25 25
We can write down the algorithm as follows. 26 26
The input into iterative policy evaluation is a policy pie. 27 27
The output is the value function for this policy. 28 28
We start out initialising v 29 29
of s equals to zero for all states. 30 30
Then in an infinite loop, 31 31
we initialise the variable called Delta. 32 32
Delta represents the maximum change 33 33
during the current iteration. 34 34
We use delta to determine when to quit. 35 35
When delta is small enough, 36 36
that's when we'll break out of the loop. 37 37
Then for every state in the state space, 38 38
we keep a copy of the old v of s 39 39
and then we use Bellman's Equation to update v of s. 40 40
We set delta to be the maximum change 41 41
in v of s for that iteration. 42 42
Once this converges, we return v of s. 43 43
The main point of interest in the algorithm is 44 44
of course the part that contains the Bellman Equation. 45 45
Notice how, strictly speaking, the values 46 46
at iteration k+1 depend only on the values at iteration k. 47 47
However, this need not be the case. 48 48
In fact, we can always just use our most up to date versions 49 49
of a value function for any state. 50 50
This actually ends up converging faster. 51 51
One last note is that we usually call the act 52 52
of finding the value function 53 53
for a given policy the prediction problem. 54 54
Later in this section, we'll learn an algorithm 55 55
for finding the optimal policy. 56 56
This is called the control problem. 57 57
This will be the pattern we'll follow 58 58
in all the remaining sections of the course. 59 59
We'll first look at the prediction problem 60 60
to find the value function for a given policy 61 61
and then we'll look at the control problem 62 62
to find the optimal policy.