Reinforcement LearningLine World

Now Sina's situation changes as she moves, so where she stands is her state. At the stalls every plate paid out at once; here the reward only comes at the end — +10 for reaching the sweet shop, −10 for splashing into the puddle — and every step on the way gives 0. One trip from the start until she reaches either end is an episode.

In the lane, Sina's state is the cell she is standing inthe number of sweets she hasthe time of day, and her actions are step left or step rightbuy or do not buyjump or sit down.

Now or Later?

A reward several steps away is worth a little less than one right now — Sina might never get there, and a jalebi today beats a jalebi next week. RL captures this with the discount factor (gamma), a number from 0 to 1. A reward that arrives on step is multiplied by , and the total is called the return:

From cell 3, the sweet shop is three steps away, and the rewards on the way are 0, 0 and 10. With γ = 0.9 the return is .

So γ decides how patient Sina is. At the mela gate she can step left to a samosa stall (+4 at once) or walk four steps right to the sweet shop (+10, on step 4). The bars show what +10 is worth if it arrives on step 1, 2, 3 … — Sina picks the sweet shop only if the step-4 bar is taller than the samosa line. Complete both missions.

The Q-Table

How can Sina learn which way to step when the reward only comes at the very end? She keeps a table of numbers called Q-values: is her estimate of the return if she stands in cell , takes action , and plays well afterwards. All Q-values start at 0. In each cell, the arrow points to the action with the bigger Q-value — together, the arrows are her policy. While both values in a cell are equal, there is no arrow. The purple fill shows each cell's bigger Q-value: how much the cell is worth.

Sina explores with ε = 0.3 and learns with an update rule you will see next. Complete both missions.

After the first episode only one number changed: the move that actually reached the sweet shop or the puddle. On later trips, a cell next to a valuable cell becomes valuable too. The reward spreads backwards along the lane, one cell at a time, until every cell knows the way.

The Q Update

After every single step, Sina nudges the Q-value of the move she just made:

It has the same shape as the jalebi estimate: old value + step × (target − old value). Here is the reward she just got, and the target adds the discounted value of the best move from the cell she landed in. The learning rate sets the size of the step. Sina uses α = 0.5 and γ = 0.9.

Sina is in cell 5 and steps right into the sweet shop: r = 10, and the episode ends there, so the next cell's value counts as 0. Her new value is Q(5, →) = 0 + 0.5 × (10 + 0.9 × 0 − 0) = .

On a later trip she steps right from cell 4 into cell 5: now r = 0, and the best Q-value in cell 5 is 5. So Q(4, →) = 0 + 0.5 × (0 + 0.9 × 5 − 0) = .

Speed Round: What Is It Worth Now?

Get five right to move on.