Original subtitles

1

Hello and welcome back to the course on artificial intelligence.

2

Today we're going to talk about the Belman equation.

3

It's quite a complex topic and we're going to introduce it in a step by step manner throughout this

4

whole section of the course so I'm not going to just jump straight into the most complex version of

5

the Belmont equation right away but instead we're going to introduce it slowly in order to gradually

6

understand how it works.

7

And I hope your goal with that approach if you're G.R. Let's get straight into it.

8

So we're going to have a couple of key concepts that we're going to be operating with and these concepts

9

are.

10

S stands for states so the state in which our agent is or any other possible state in which it can be

11

a represents an action that a an agent can take.

12

So an agent can have access to a certain list of actions and actions are very important when they're

13

looked at in a state combination.

14

So when you're in a swing state and then you look at actions and it starts to make sense what's going

15

to be the result of those actions because you'll look an action by itself or a state doesn't really

16

make sense because you don't know where you are and where you can possibly end up and then we have we'll

17

have our Which stands for reward and that's through ward that agent gets for entering into a certain

18

state and gamma is the discount factor.

19

And we'll talk about the discount factor in a second all make sense just now but they're just taking

20

notes.

21

Make a mental note that we are going to have this letter Gamelin that will be operating with later on.

22

So the person behind the bellman equation is Richard Ernest bellman.

23

He was a flight mathematician and came up with the concepts of dynamic programming which we're now which

24

we now call reinforcement learning or which we call the Belman equation now.

25

Well that's what we're called now.

26

And in 1953 he came up with that concept and that's when the Belmont Belman equation came to me.

27

So let's have a look at how this all works.

28

There's our lovely agent in the bottom left corner and he is in a maze and this is quite a classical

29

maze where you've got some blocks the wide blocks are blocks in which the agent can step into the gray

30

block is the one one that is just not accessible says like a wall in this maze.

31

The green is where the agent is should be aiming to end up in that's where we want the agent to go that's

32

the finish.

33

And the red is firepits or the engine falls into the fire pit.

34

He will lose the game.

35

So in the fire pit the reward which is R is minus 1.

36

So that's our way of telling the agent that's not something we want you to do.

37

Like remember in the example of when we're training dogs we want to tell them like bad dog if it's not

38

doing the right thing that wanted to do same thing here we're one tell the agent that this is not something

39

that you should be doing you shouldn't be ending up in the square so every time it doesn't happen the

40

squirrel get a minus one reward so you'll be punished with minus one reward.

41

On the other hand if it ends up in the Green Square it will get a plus one reward meaning that that

42

is what we wanted to do.

43

So those are the two rewards that the agent can't possibly get.

44

And how does it learn how to operate in this maze.

45

Just like in that example of the robot dogs that learned to walk which is going to let it know it will

46

just tell it that here the action you can do.

47

You can go up right left or down those are four possible actions that you can take and that's it.

48

Have have a play around with that see what you can come up with.

49

So the agent might go to the right then they might go two more to the right they might go back to the

50

left just randomly pressing the button and they're trying to see what happens and they go back here.

51

They go up go up go down go up go right.

52

So for now they haven't learnt anything they just so far nothing's happened.

53

They go right and then bam they end up in the Green Square.

54

So they realize wow I just got a plus one awar So as soon as I stepped into the Green Square they got

55

a plus one reward.

56

And that triggers the algorithm to say OK that's really cool.

57

I am rewarded for ending up in the square so I want to end up in the square.

58

So what does that mean for the agent.

59

That means it starts to ask the question how did I get to this square.

60

What was the preceding state I was in and what action that I take to get to square and then looks back

61

and says OK so the preceding state was this one.

62

It turns out to be valuable in that state.

63

The one that spark of the Red Arrow.

64

Because from that state you're I'm I'm just one step away from getting the maximum reward I can possibly

65

dream of of plus one like a biscuit for a dog from as soon as I know if I ever am in that state.

66

That square marked with the Red Arrow.

67

All I have to do is press right.

68

So how do I tell myself to remember that that state is valuable.

69

Well to me there's no difference actually as the agent.

70

There's no difference in whether I am in the Green Square or in the white square right in the Green

71

Square I get the reward of one.

72

So I'm going to mark for myself that the Y Square is got for me it has a value of 1 because it leads

73

exactly to reward one soon as I'm in the white square I know I'll just take one more action.

74

I'll be in the Green Square and I'll get a reward or one so that's why I'm going to say that the value

75

of this square is equal to one because it leads directly to if on any sort of subtractions as soon as

76

I mean here I know my reward will be one so I'm going to mark this square as the call to one that's

77

the value that's the perceived value of being in the state.

78

Next the agent's going to be OK.

79

So how do I get into this square.

80

And you know he might walk around again and so on.

81

And up in the square again and be like OK how did I get into this square before that.

82

And the way I got into this square was from this square.

83

Interesting.

84

OK so as soon as I get into this square I know that all I have to do is go right.

85

And then from here I already know that I'm going to win.

86

I know exactly how everything is going to unravel from here and I know the value of being in this state

87

is equal to one.

88

And since there's no nothing is stopping me from growing from here to here the value in this is going

89

to a perceived value I'm great value being in here as a vehicle to want as well because this is I mean

90

here I know.

91

Be here and I'll be here pretty quickly.

92

So I'm going to win.

93

And then how do you get into this square before that.

94

Well I got into this square from this square.

95

So the value is similar approach the value of being here is also equal to one and so on so the value

96

of being here is equal to one value of being here is equal to one because each one of them leads to

97

the next one and these to the finish line.

98

So that's all like pretty logical at this stage.

99

This is us pretty much designing the Belman equation right now.

100

So this is we could possibly think about designing an equation that helps an agent go through the maze.

101

So look at the reward then the preceding state give it a value of equal to reward the proceedings and

102

so those are kind of like creates a pathway is all great and well but the problem here is OK what happens

103

if our agent for some reason starts in this state instead of starting here and taking these actions

104

and that it actually starts in the state.

105

How does it know how does it remember which action to take should it go right or should it go down or

106

should maybe go left or should go up.

107

How does it remember which is the next continuation from here.

108

If the only values it has is these values are equal to once it kind of cannot see what's further away.

109

It can only see.

110

All right.

111

What I have here and what I have here.

112

How does it know which way to go.

113

Well at this stage it doesn't it's as pretty identical for the age and which way to go.

114

And so that's why this approach doesn't really work.

115

It's a very simplistic explanation.

116

Of course there's much more to it.

117

But in an intuitive way that's why we cannot just assign just carry on this value backwards like that.

118

Because one of the reasons is once Agent is in between these two values which where is it going to go.

119

It doesn't it can get confused like that.

120

And so how do we solve this problem what are we going to do.

121

And this is where we're going to start introducing the Belman equation in its actual form slowly step

122

by step.

123

So the Belman equation looks something like this.

124

So we've already talked about the value of being in a certain state as is your current state or any

125

given state and there is as well.

126

And as Prime is the state the following state the state that you will end up in after the state and

127

by taking concerted action.

128

But we know that there's many actions and a agent can take and that's why we've got this Max over here.

129

So by taking an action what will happen to an agent so let's say we're in state as by taking an action

130

in state assets and we take action.

131

What will happen is will instantly get a reward by getting into a new state.

132

And remember that reward can be one or plus one or minus one if it's at the end of the game or it can

133

be a zero if it's throughout the game in this case our reward throughout the game is zero.

134

So that's the reward Plus we will get into a new state which has value of s prime.

135

So that's the value of the new state and gamma.

136

We'll talk about it in a second.

137

But the point I'm trying to raise here or the point I'm raising here is that you've got many different

138

actions that we can take and that's why we've got the maximum.

139

So by taking action we get reward Plus we end up in a new state.

140

And so for every move out of the in our case before our possible actions for every one of the possible

141

4 actions we're going to have a equation like this.

142

So this is going to have a value for they will have a different value for every one of four actions

143

and we're going to look at only the maximum because of course the agent wants to take the optimal state.

144

So if he's in state s he's going to look at these values he's going to find the maximum based on the

145

action and going to take that action that needs the maximum of these values.

146

So hopefully that makes sense why we're taking the maximum here.

147

Then once we got the reward and the value that said why do we have this Gabaa parameter here.

148

Well it's there exactly to solve that problem of where the agent doesn't know which way to go because

149

it cannot.

150

It's comparing the values of two states on both sides and they're the same.

151

That's why the gamblers called the discounting factor so we're going to have a look at that and it better

152

understand.

153

So let's take a formula I'll put it here on the top right.

154

And now we will analyze what the values of the different states are.

155

And every state here is a square.

156

No.

157

So one of these any one of these white squares is a state I mean we're going to calculate the value

158

of being in that state.

159

So let's start with the square.

160

What is the value of being in this state.

161

Well we need to take the maximum of this value across all actions.

162

And we know that this value represents is maximized as we get closer to the finish line and that's how

163

it is constructed and by just by looking at you can see because here's got the reward and here's got

164

a discounting factor multiplied by the value of the next state.

165

And it just makes sense that that's how we would construct that equation so it makes sense that from

166

here the maximum of this value will be if we move to the right.

167

So that's how we calculate the values that this value of this state is he calls the maximum or equals

168

to this value.

169

If we move to the right if we take an action of moving to the right.

170

So what will this value be.

171

Well the reward of moving to the right is equal to 1.

172

And regardless what color gamma is we don't have a value in the state because we are already in the

173

best state possible.

174

So this is the final stage.

175

It won't have a value we just get a reward here and that's the end of the game.

176

So the value will be of this maximum will be equal to 1.

177

And that's why value of state as here is equal to 1.

178

Now things get interesting when we move to the left when we move backwards a bit.

179

So now is calculate the value of this of being in this state and for that we're going to need Gabaa.

180

So let's say our discounting factor is a zero point nine and it makes sense what a discounting factor

181

is once we calculate that.

182

So from here just based on our intuition and based because we know how this is working how this works.

183

We know that the best possible action is go to the right because from here we go here.

184

So that means the maximum will be achieved in this state you go to the right.

185

And so let's see what happens if we plug it in here.

186

So if you go from here to here you don't get in your reward will be zero.

187

But then you'll get camis who get zero point nine times the value of the new state which is one.

188

So in this case the value the whole result of this is 1 times a 0.9 times one equals 2.9.

189

So that's all values per.

190

So if we calculate this now you'll see that from here.

191

We know just by looking at the maze we know because we as humans because we're understanding how this

192

equation works of course an AI agent would have to experiment with these things.

193

But because we have like a crystal ball we can see this whole maze.

194

We have like the bird's eye view right now.

195

We know that the best action go to go to the right.

196

So if we plug it all in here it'll be zero no reward Plus the report nine times the value in the state

197

0.9 is zero point eighty one and so on.

198

So here it'll be 0.23 and he'll be 0.66.

199

So you can see that the way the discounted factor works is it discounts the value of the state as you

200

are further away.

201

So if you are familiar with finance theory then it's something similar to time value of money like what

202

would you think about it this way What would you prefer to have $5 today or $5 in 10 days from now.

203

Just if somebody was to give you a choice I will give you five dollars today all you $5 10 days from

204

all.

205

Of course you would choose $5 today.

206

Why is that.

207

Well because you can take that $5 and you can invest them at a certain interest rate which is very similar

208

to gamma.

209

And your $5 in 10 days will actually grow into maybe 5 dollars and 73 cents or something like that.

210

And that's how time value of money works.

211

And very similar concept here.

212

And the important thing to understand here this is just a theory a way that reinforcement learning.

213

So Richard Belman came up with this equation.

214

And from then now that's how we use it.

215

So you could go ahead and come up with a different equation.

216

It doesn't have to have Gamla it might have some other factor might not you know have a factor.

217

But this approach works and that's why we're using and this is what it looks like so the further away

218

you are the less value of it being in the state and in terms of time and money.

219

If I could say to you where would you rather be would you rather be here.

220

Would you rather be here.

221

You'd say I would rather be here.

222

So we're creating that that same phenomenon as time value of money we're artificially creating it through

223

gamma so that in order to incentivize agents or inspire agents to be closer to the finish line.

224

So if an agent were to be asked would you rather be here or here because of the way this equation works

225

it would choose to be here.

226

There's nothing more to that nothing less.

227

It's not something that the world works this way.

228

No it's just something that we're artificially creating in order for our agents to understand that this

229

is this is good this is good this is good old good but this one is better than this one and this one

230

is better than this one and this one has been in this one.

231

And that way you can see all the agent can see in which direction needs to go.

232

So it can see that if I'm standing here remember that problem that we had or was he standing here so

233

if you standing here do I go down or if I'm suddenly here to go up or do I go down.

234

Well now there's not a problem anymore because he can see that it's actually better to go up because

235

the values are here.

236

And then from here he's got to go right because the value is bigger here than here.

237

And then from here is Bertschi go right because the value here is bigger than you know.

238

And from here he already knows that he needs to go right because he'll get a reward here of one.

239

So that's how this whole approach works.

240

Now let's have a quick look at the rest of the square.

241

So how do we calculate the value in this square.

242

Well here is where things get tricky.

243

So from here you might not actually go left right you might actually go right so we can just keep going

244

like that because it might actually be shorter to go this way.

245

So what we're going to do is we're going to calculate the value in the square first.

246

And because obviously from here the best ways to go is up.

247

Again that's because we see the crew we have the crystal ball we can see things and you'll see further

248

down in the section you'll see how the agent actually explores this understands this on their likes

249

through experimentation.

250

But for us we know that it's better to go this way so we're going to calculate value here and that's

251

why we're going to calculate the value in this square first.

252

So here we have three possible actions.

253

In reality we actually have four we can also go left.

254

The agent could hypothetically press left and bump into the wall and stay here.

255

But for simplicity set which is going to show the actions that we knowing what we know and having the

256

crystal ball we know which actions are the ones actually lead to something other than the same state

257

again.

258

And so here from here we know that again just because we have a crystal ball we know that the best way

259

to go is this way an agent of course would have to experiment and find the best way and you'll see how

260

that happens.

261

Further down in the section you'll see actually how an agent walks around and how you would experiment

262

trying to find these values.

263

But for us we know it's that way.

264

So here if we plug everything in one so the maximum the best output is when you go up.

265

And here is a report 9:0 So you put that in.

266

You get zero point nine.

267

OK so it Kalika that one that calculate this one.

268

Same approach.

269

This is you have three ways you can go.

270

Actually four for the agent but for us we can see it's only three.

271

So zero point eighty one from here you have ZERO point seventy three.

272

And it actually ties in nicely with this value because in you if you discount again you put 66 and here

273

you have 0.23 because this is the optimal route.

274

So there you go.

275

That is the values all of these states.

276

And now you can see that because we've created this equation or we've created synthetically this whole

277

concept of the closer you are to the finish line the more valuable that state is not because we're afraid

278

that now it's pretty obvious for the agent which way it should go.

279

And we'll talk more about that in the coming.

280

I hope you enjoyed today's session and I know it's a bit it might sound a bit very basic at this stage

281

but as we go through this section we will add a bit more complexity to it.

282

At the same time if you cannot wait if you want to jump into it then there is a paper which you can

283

look at and it is the original paper by Richard Belman.

284

It's called the theory of dynamic programming from 1954.

285

And you can find it at this link.

286

And there you go so you can jump straight into it and read from the author of the Belman equation.

287

But just bear in mind that this is quite a mathematically heavy paper.

288

And on that note I'll look for your next.

289

And until then enjoy AI.