Monte Carlo prediction and control

1Averaging returns

A policy π says how the agent chooses actions, here the robot's random moves. The value of a state under π is the return to expect from it, the sum of the rewards until the episode ends at time T, discounted by γ:

An expected value can be estimated by an average of samples, and each visit to s in an episode gives one sample: the return that followed it. A state can be visited more than once in the same episode, so there are two ways to average:

In the home γ = 1 and every move gives −1, so a return is minus the number of moves left. Here are two trips:

First-visit Monte Carlo takes, from each trip, the return after a room's first visit: −3 and −7 for the kitchen, which average −5. In the second trip the robot returns to the kitchen with 5 moves left, and every-visit Monte Carlo also takes that −5: (−3 − 7 − 5)/3 is −5 too. They differ for the hallway: every-visit averages four returns, (−2 − 6 − 4 − 2)/4 = −3.5, and first-visit two, (−2 − 6)/2 = −4.

Two short trips are a poor sample: the true values are much lower, since many trips go back and forth for a while. They follow from the relations between neighboring rooms, each worth the average over its moves of −1 plus the value of the room the move leads to, 0 at the charger:

which together give −9, −8 and −5. Averaging more trips gets there: after 10,000 trips, both methods are within 0.1 of these values.

Both methods converge to v_π(s) as the number of visits grows, each for its own reason:

• For first-visit Monte Carlo this is the law of large numbers: each return is an independent sample whose expectation is v_π(s), so the average is unbiased, and its error shrinks like 1/√n after n returns.
• Every-visit Monte Carlo converges too, though its samples from the same episode are not independent.

The algorithm

Returns are easiest to compute backward from the end of the episode, since G_t = R_t+1 + γG_t+1. First-visit Monte Carlo prediction, for a policy π:

1. Start with any estimates V(s) and an empty list of returns for each state.
2. Generate an episode by following π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Set G ← 0.
3. For t = T − 1, T − 2, …, 0: set G ← γG + R_t+1. If S_t does not appear earlier in the episode, add G to the returns of S_t and set V(S_t) to their average.
4. Repeat from step 2 for each new episode. Every-visit Monte Carlo is the same without the check of step 3.

The figure runs it on a grid 3 cells wide and 3 tall, with cells named by column and row, from A1 at the bottom left to C3 at the top right, with every estimate at 0:

• an agent starts in A1 and moves up, right, down or left, each move picked at random by the policy; a move into a wall leaves the agent where it is;
• reaching the cookie in C3 gives +1 and ends the episode, and every other move gives 0, so with γ = 0.9 the return from a cell is 1 if the next move reaches the cookie, 0.9 if it comes one move later, 0.81 if two, and so on.

Each cell shows its estimate, shaded green the closer it is to 1, and not at all at 0. The pseudocode beside the grid lights the line each press plays. At first, each press is one line of the algorithm:

• during the episode, the move chosen turns yellow and the agent takes it, the cells it has left are outlined in dashed blue, and no estimate changes;
• once the agent reaches the cookie, each press is one step of the sweep back, and every estimate it updates is outlined in green.

Later, Next skips ahead to the moments where something new is learned, and the gear button after Next opens the figure's settings: the heatmap and the sound.

Averaging as you go

There is no need to keep every return. After a new return G_t, the average of the N(S_t) returns seen so far moves toward it:

For the hallway, the first return, −2, gives V = −2, and the second, −6, gives −2 + ½(−6 + 2) = −4, the same average as before. A constant step size α in place of 1/N gives constant-α Monte Carlo, V(S_t) ← V(S_t) + α[G_t − V(S_t)], which, like the bandit note's constant α, suits problems that change over time, such as learning about a policy that keeps changing.

No bootstrapping

A consequence is that estimating one state costs the same however many states there are, so a Monte Carlo method can study a few states of interest by starting many episodes from them and ignoring the rest. The price is waiting: an estimate changes only when its episode ends.

2Values of actions

State values are enough to choose actions only with a model of the world: knowing that a move from the hallway leads to the study, the robot could compare the rooms each move leads to. Without a model it needs the value of each action directly:

the return to expect after taking action a in state s and following π afterward. Monte Carlo estimates it the same way, by averaging the returns after visits to the pair (s, a), first visits or all visits. For the wandering robot, each move is worth its −1 plus the value of the room it leads to:

The complication is that many pairs may never be visited. A robot that always went from the study straight to the charger would never see a return for going back to the hallway, and could never learn whether that move is better or worse. To compare actions, every pair has to keep being tried.

One way to guarantee it is exploring starts: each episode starts from a state–action pair chosen at random, every pair with some chance. That is easy in a simulation and usually impossible in the real world, where episodes start wherever they start.

3Improving the policy

With action values, a better policy is easy to find: in each state, take the action with the largest value. A policy that does that with respect to q is greedy:

The greedy policy is at least as good as π everywhere. The argument has two parts:

1. Following it for one step and π afterward is worth max_a q_π(s, a), which is at least v_π(s), the value of following π all along.
2. By the policy improvement theorem, following it every step is at least as good too.

In the home, the greedy policy takes the better move of the diagram above in each room, to the study from the hallway (−6 beats −10) and to the charger from the study (−1 beats −9), and that is the best policy:

Here one improvement step was enough to reach the best policy; in general, evaluation and improvement have to alternate.

Evaluation need not be complete: Monte Carlo methods alternate after every episode, updating the values of the pairs visited and then the policy at those states.

The algorithm

Monte Carlo with Exploring Starts, Monte Carlo ES:

1. Start with any Q(s, a), an empty list of returns for each pair, and any policy π.
2. Choose S₀ and A₀ at random, every pair with some chance, and generate an episode from them by following π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Set G ← 0.
3. For t = T − 1, T − 2, …, 0: set G ← γG + R_t+1. If the pair S_t, A_t does not appear earlier in the episode, add G to its returns, set Q(S_t, A_t) to their average, and make π greedy in S_t: π(S_t) ← argmax_a Q(S_t, a).
4. Repeat from step 2 for each new episode.

It cannot settle on a policy that is not optimal: the values would converge to that policy's values, and the greedy step would then change it. That it always converges to the optimum is widely believed but has not been formally proved.

4Control without exploring starts

Without exploring starts, the only way to keep trying every action is for the policy itself to keep choosing them. There are two ways to do that, and this section is about an on-policy method:

The policy is kept soft, with π(a|s) > 0 for every action. An ε-soft policy gives every action at least ε/|𝒜(s)|, where |𝒜(s)| is the number of actions in s.

The closest of them to greedy is ε-greedy:

On-policy first-visit Monte Carlo control is Monte Carlo ES with one change: episodes start however they start, and the improvement step makes the policy ε-greedy with respect to Q instead of greedy.

The algorithm

On-policy first-visit Monte Carlo control, for a small ε > 0:

1. Start with any Q(s, a), an empty list of returns for each pair, and π ε-greedy with respect to Q.
2. Generate an episode by following π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Set G ← 0.
3. For t = T − 1, T − 2, …, 0: set G ← γG + R_t+1. If the pair S_t, A_t does not appear earlier in the episode, add G to its returns, set Q(S_t, A_t) to their average, and make π ε-greedy in S_t with respect to Q.
4. Repeat from step 2 for each new episode.

The figure runs it on the cookie grid of section 1, with ε = 0.1 and every value starting at 0, and its presses work as there, with moves in place of cells:

• each cell is split into four triangles, one per move, each with that move's value, blank while the move is untried;
• when one move is worth more than the others, its value is in bold, and of the four small triangles at the middle of the cell, faint blue, the one that points toward it turns solid blue;
• the moves of an episode are outlined in dashed blue, and the values its sweep updates in green;
• and the heatmap shades each move's triangle, or, if chosen in the settings, each cell by its best value.

The ε-greedy step still improves the policy. For any ε-soft π, the ε-greedy policy π′ with respect to q_π satisfies, in every state,

because π′ puts its extra weight on the largest q_π(s, a), and a weighted average never exceeds its largest term. By the policy improvement theorem, π′ is at least as good as π. In the study, with ε = 0.2 and two actions, π′ goes to the charger with probability 0.9: 0.9(−1) + 0.1(−9) = −1.8, well above the wandering robot's −5.

Where does it end? The process stops improving only at the best ε-soft policy, which is not the best policy: it keeps exploring forever, and exploring costs something. In the home, around the best moves:

Letting ε shrink over time closes that gap.

5Summary

The key ideas next to their NumPy equivalents. r[t+1] holds R_t+1, s the states of an episode, and v, q and n the estimates and the visit counts.