Original subtitles

1

Hello and welcome back to the course on artificial intelligence.

2

Today we're talking about the temporal difference.

3

Now it's very important to trial because temporal difference is the heart and soul of the Q learning

4

algorithm.

5

This is actually how everything we've learned so far comes together into play inside key learning.

6

So let's have a look.

7

Remember the time when we talked about deterministic versus nondeterministic search.

8

And remember how we said in this case it's when the agent wants to go up he goes up and when.

9

In this case he wants to go up there's a 10 percent chance he'll go lower left temps and chance and

10

go right and an 80 percent chance will go right.

11

Go straight up.

12

While these numbers are of course arbitrary and can be different.

13

And this whole concept is it could be different and different problems so it doesn't have to concern

14

which way he's moving just that there's some randomness something that's out of the control of the agent

15

happening inside this environment.

16

And what effect that had is as you remember was that in the deterministic example it was very easy to

17

calculate the Wii values while not necessarily always very easy.

18

But in our case we could just simply calculate them by using the Belman equation and we we had the exact

19

values.

20

And then as you remember I very carefully mentioned that these values for the nondeterministic search

21

example are off the top of my head.

22

They are not Kalka we know.

23

Last time I said we're not we just had to calculate them because it's very complex.

24

But the computer can do it and we just went along with these values that are just values that I made

25

up.

26

But they did get the job done.

27

They helped us understand the concept.

28

Well now we're going to return to that a little bit and understand what exactly is going on here.

29

Why is it so much harder to calculate these values in the nondeterministic example or generally speaking

30

in these problems in these environments and the agent going through them.

31

Why is it.

32

Why can it be so hard to calculate these values.

33

Well when you think about it because when the agent moves for for instance from here to the right he

34

doesn't necessarily always move that way sometimes as a chance that he will go to win instead of going

35

straight so let's call these northeast southwest so is sort of going west.

36

The agent might sometimes go south and for instance from here is sort of going north.

37

He might sometimes go east.

38

So sorry.

39

So here instead of going east he might sometimes go south and he's sort of going north.

40

He might sometimes go east or west and here instead of going north he might sometimes go west or east

41

or west and so on.

42

So and therefore So in order to calculate this value you would need to know what this value is but the

43

interesting thing is that in order to calculate this value you need to know what this value is.

44

So there's a lot of recursion happening here and therefore you cannot just decide to define what these

45

values are.

46

And on top of that this recursion is not deterministic.

47

It is sometimes it happens this way sometimes it's sort of uphill to go right sometimes instead of get

48

up and go left sometimes.

49

When he want to go up.

50

He will go up.

51

So it is subject to chance and so maybe many times agent will go through this path and he'll go up up

52

up up up and you'll think that from here you always kind of goes up and the value of the state will

53

go it will be good and then all of a sudden he'll drop into the pit and this value will go down.

54

And so therefore you can see how there is some stochastic randomness to this whole calculation on these

55

values because they're all interlinked.

56

Plus on top you've got that randomness in this inherent in the environment because there's a mark of

57

decision process.

58

So that's where all this comes together and that's where we're going to introduce the concept of the

59

temporal difference which will allow the agent to calculate these values.

60

And here we were dealing with the values.

61

And since then we've already moved onto Q values so that's what we're going to be working.

62

We're going to be looking at huge values.

63

So as I recall this is our Belman equation for q values.

64

So AQ value or the value of performing a sort of action A in state s is equal to the reward that you

65

get after performing that actions immediately after performing an action plus do you get the maximum

66

you get the gamma of the sum of all the possible.

67

So you kind of get the expected value of the state that you will end up in.

68

So as you recall there was a formula for the Beldon equation and now just for simplicity say we're going

69

to rewrite it in the old fashioned way and in a way that we used to talk about the bellmen equation

70

before we knew about the sequester.

71

So remember this was our Belman equation in the sense of a deterministic search example because here

72

you don't have that expected value you don't have the same across all probabilities.

73

You just have that as if it's determined you're going to end up what state you're going to end up and

74

then you tell you Max in that one state.

75

And the reason we're rewriting it is simply the only reason is because it is just easier to write it

76

and it'll be easier to fall along with the formula.

77

So we're going to just remember that we replaced this part of this bar.

78

And also you'll find this notation in a lot of literature so it'll be easier for you to follow along

79

with other sources if you're studying those.

80

But do remember that in fact what we mean is this probabilistic approach here instead of this notation

81

is just easier for us to operate this and understand what's going on.

82

I just kind of like look at the equations so that they're not too cluttered but once again just remember

83

that in fact what we mean is this probabilistic approach here.

84

And so we're actually in the know Tom Silis have a look at what's going on.

85

So here is our blank state of the maze we don't have any q values let's see or when we may but let's

86

just keep it blank for now let's just look at one of the states or one of the cells.

87

This one specifically.

88

And here we have for answers for the action of going up.

89

We have a q value that we calculate.

90

So it's not that we don't have any q values yet we have it we do.

91

But we're just not illustrating anything.

92

We're just keeping a blank for simplicity's sake.

93

But we have the age has been walking around for some time and let's say hypothetically somehow he's

94

calculated this cube value of going up or Norf from this state from this specific cell and the values.

95

Q S and A and so now what we have.

96

So he is currently with his blue arrows point and the agent is sitting in this cell.

97

And now he needs to make a choice where is he going to go.

98

And he knows the value of this action going north and that is q Senay and here I'm saying before and

99

the reason for that is because he that is before he takes Actually he hasn't taken action yet so he's

100

still in the cell and before he's taken the action the value here is q and SNH and now he actually takes

101

the action.

102

So let's say he decides is the best one.

103

He takes the action and he moves up to the cell.

104

Well now what happens is now comes after so after he's taken action we can measure what is this value

105

let's just calculate this value the value of the reward of for taking that action plus gamma times the

106

maximum of this new state that he's just gotten into as prime.

107

And so the maximum across all possible actions and aspirin.

108

And so what we have here is the value before in of that action.

109

And then we've calculated this metric afterwards.

110

But as you can recall from the previous four months if we go back very quickly from the previous formula

111

where we just calculated is indeed the value that is how Q of s.a.a is calculated.

112

So this Arite part of just calculated separately but after we've taken action.

113

So as again before we knew a Q of an S and a value something that we've calculated through our iterations

114

Preuss is something.

115

So a value that's stored in our memory.

116

So just like a number that we know and now after the action is being performed we know what reward he

117

actually got what reward the agent actually got.

118

And we can calculate this new value.

119

So in essence we're kind of recalculating this value but now with new information the new information

120

is the reward that we got.

121

And plus what stayed we ended up in and what the maximum across that state what that this new value

122

is for that specific data can.

123

So what's the value of that being in that state.

124

So basically the Cure Vanessa-Mae but given new information and now the temporal difference is defined

125

as tiddy of a and s of these two of the difference between these two.

126

So here the first element is your off-Terra value.

127

So the kind of like Q of Esson a bit calculated afterwards.

128

And the previous quvenzhan A which you had stored in your memory.

129

And so the question is are they different.

130

So ideally they should be the same.

131

Ideally this should be the same as this simply because this is the formula for calculating this.

132

But the thing is that this is not something we Kalka this is something that we have from empirical evidence

133

something that we have from just going through the maze many times and calculate.

134

So this is something we come up with so far.

135

Its not related to the current iteration.

136

Its something that we came up with previously a long long time ago but in one of our previous iterations

137

going through the maze.

138

Whereas this is something we've calculated just now and there is no guarantee that they're going to

139

be the same or because of the randomness that exists in the maze because this could have been calculated

140

and saw some CRN random events were triggered and this can be called to different random events happening

141

were triggered.

142

And so now we write down our heroes just move it up there.

143

So how do we use this.

144

The question is OK so we have this temporal difference.

145

How do we use this.

146

And why is it called the temporal difference.

147

Well the reason is called the temporal difference is because you're basically calculating the same thing

148

you're calculating Q of S and A so the Q value of that action.

149

Your Calcott here and you're calculating it here.

150

But the difference is time.

151

This is the Q of S and they previously this is yo Q of S and A.

152

Now your new cure is innate and the question is has there been a difference.

153

Have there's been a shift between them in time.

154

And how can we use this to our advantage if there is indeed has been a shift in time.

155

Well one thing we could do is we could say OK well you know our Q of s.a.a doesn't.

156

This new value doesn't equal old so we are going to get rid of the old or forget about the old and we'll

157

just use this is all a new value.

158

But that would not be smart.

159

And the reason for that is that in our environments random events can sometimes happen.

160

And what if our old QSA of s.a.a was something that consistently happens like 80 percent of the time.

161

And then like was represented by what happens 80 percent of the time.

162

And then this new one just what happened due to randomness.

163

In that case we're going to throw away the the one that is responsible for the bulk of the situation

164

and we're going to replace it with something that happens only 10 or 20 percent of the time.

165

That wouldn't be the best approach to go and that's why that's exactly why we don't want to completely

166

change Opu values.

167

We want to use like change them step by step a little bit by a little bit.

168

And that's why we're going to use this temporal difference in a specific way so we're going to say Here's

169

a formula we're going to take our cue of SNH.

170

And we're going to update it in such a way.

171

We're going to take the old value of cure Senay and we are going to add all five times the temporal

172

difference.

173

So Alpha is going to be all learning right.

174

That's a new parameter that we're introducing.

175

That's how quickly is algorithm learning.

176

So basically we're taking this difference and whatever it is we're adding it on to our previous KJo

177

snake.

178

Now this formula probably doesn't make any sense or like just by looking it doesn't make sense because

179

you got Covisint here and give us an A here.

180

It's the same thing so probably should negate each other but we had to rewrite this in a bit of a different

181

way.

182

So I'm going to show you again so I'm just adding time to these formulas.

183

So here is q t minus one the previous years.

184

Q T minus 1 the previous years.

185

Q T The New this should be a circle here in circle here as well but never mind and here get alpha temporal

186

difference.

187

Then you the current temporal difference.

188

So you can see what we're doing we're saying.

189

OK let's take our current.

190

Q is going to be equal to all previous Q plus whatever temporal difference we found Times Alpha.

191

This formula here is the heart and soul of the cube learning algorithm.

192

This is how the cube is or update.

193

And it's good that we've already learned what q values are what gamma is what is and what all this stuff

194

is.

195

And now all we need to see is that you have a previous Q value Yes that's good.

196

And then what can happen is that when you take in when you actually do take the action when the agent

197

takes action you'll know he'll get a reward and he'll end up in a state.

198

And so based on that he can calculate Aha.

199

OK so what is what would have what should have been the Q value of that move that I made.

200

And now that is this part of the equation.

201

Subtract the old Q value gets you a temporal difference and now you need to take a Alpher time sample

202

difference and that's how you get adjust.

203

Q Got you that's what you mean.

204

I just think you go by and now just to finish off this.

205

This is kind of like this is sufficient to understand what's going on but just to clarify things even

206

more or perhaps maybe confuse things even more.

207

What do we need to do to take this temporal difference or this simple difference or here a way to plug

208

it into this format.

209

So we're going to take all of this part and plug it into this formula and end up with a huge equation.

210

So here we go.

211

There's our equation.

212

So this is the full equation with the temporal difference written out completely.

213

And the reason I wrote it out as well first of all you'll probably find this in other literature if

214

you study it.

215

And the second thing is that it makes some things a bit more complex has formulas longer but also make

216

somethings a bit clearer.

217

So for instance you can see here the role Alpha plays.

218

You can see it better because look at this.

219

Here.

220

Q T minus one and here you go.

221

Q T minus one with a negative sign.

222

So if you plug in Alpha equals to 1 if you put a 1 in here then this will negate this.

223

So they'll destroy each other and all you'll have left is this part.

224

And what that means is exactly that situation where we said All right so you've got a new value which

225

it should have been.

226

Let's update our Q value with the new value and forget about whatever we had previously.

227

And as we discussed isn't the best approach because there are random events here and we want to update

228

things step by step.

229

And on other hand if you said Alpher equal to zero what happens then is that you completely forget about

230

this whole part and you're cute t the new one or the current one is going to be always equal to the

231

previous one so you're not going to be learning anything.

232

And that means whatever is happening in the maze doesn't matter because you've decided on you Kuchi

233

value a long time ago and you're just going to keep it.

234

So that's why Alfas shouldn't be 0 or should be one it should be somewhere in between.

235

And it's going to allow you to learn slowly step by step is going to allow you to as your or the agent

236

as it goes through the maze is going to get the temporal difference.

237

And slowly but surely this value is going to get update and update ibed and what will happen eventually

238

is that at some point hopefully the algorithm will converge.

239

And what that means is that this temporal difference will start becoming closer and closer to zero and

240

eventually will be just well very close to zero or even 0 0 0 0 and what that means is that every single

241

time your your new cutesie value or your new calculated value.

242

What it should have been.

243

So not this one but what it hypothetically should be enough to take the step will be just equal to your

244

previous Q2 value.

245

And then one that's zero and that means when your temperature difference is zero means your algorithm

246

has converged and it's not really necessary to continue updating what's going on.

247

It does this search to continue updating your cube values.

248

The caveat here is that the only time probably one of the only times when you would still want to continue

249

performing this whole you know updating of queue values if the environment is constantly changing.

250

If not just it's not there it just has some randoms to Kostic events in it.

251

But the environment itself is modifying as is morphing is changing with time.

252

So you continuously need to learn because it's not possible for you to learn everything and come up

253

with the optimal policy because the optimal policies also changed with the environment all the time.

254

In that case you will need to continue CALKIN and temporal difference and calculating the Q values.

255

But other than that that's kind of like an extra complication.

256

Other than that this is how Q values update is so this is the main formula of the Q learning algorithm

257

and this is kind of like the expanded version of that and now it should all come together and make sense

258

why we have the Belman equation and not only what it represents the gewgaws but also how the agent goes

259

about updating its values and finding exactly what is going on in that environment so it can come up

260

with the optimal policy.

261

So I know quite a lot to take in but hopefully you enjoyed this tutorial and hopefully you able to take

262

away the underlying concepts and intuition behind your values and what's the whole notion of temporal

263

difference is and why it's important why it helps us slowly train our agents and get them to understand

264

their environments that they're operating in.

265

And if you'd like to learn a bit more about temporal differences then a very popular paper is learning

266

to predict by the methods of temporal differences by Richard Sutton of nineteen eighty eight.

267

We've already had a reference by Richard Sutton as well but this is as another one and actually has

268

a book so if you get into you know his writing style and his style of communication then check out his

269

book as well.

270

It's is kind of like a more expanded version of all of these things.

271

I haven't read the book but that's what I'm imagining at the same time.

272

This is going to add to the paper and you can learn a bit more about or probably a lot more about temporal

273

differences there.

274

And I hope you enjoyed it as well.

275

We'll see you next time.

276

Until then enjoy AI.