Monte Carlo Methods

Chapter 5 estimates value functions and improves policies from complete sampled episodes, without requiring an environment model.

Exercise 5.1

Why the big jump in the last two rows at the rear (player sums 20–21)?

At sums of 20 and 21, the policy is to stick. The bust risk is gone, and we are already very close to 21, so the probability of winning is very high.

Before 20, the policy is to hit. Therefore, the bust risk is high, and the probability of winning is low.

Why does the far-left column of that back row drop (dealer showing Ace)?

When the dealer shows an Ace, the probability of the dealer's sum reaching 21 is a bit higher than if the dealer shows some other card. Therefore, our probability of winning is a bit lower.

Why are the frontmost values higher in the upper plots than the lower?

With a usable ace, we have more flexibility in moving to a strong hand since it can be used as a 1 or an 11. The expected value is therefore uniformly higher in the frontmost rows of the upper plots than the lower plots.

Exercise 5.2

In blackjack, a given state (defined by player sum, dealer's card, usable ace flag) usually appears at most once per episode. This is because upon each action, the player's sum either increases or the episode ends.

Because there are almost no repeated state visits within the same episode, first-visit and every-visit MC give the same results.

Exercise 5.3

For MC prediction of $q_\pi$, the backup is a full-episode backup: from the state-action pair $(s_t, a_t)$, you follow the policy $\pi$ all the way to termination, then backup the total return $G_t$ to $(s_t, a_t)$ (no bootstrapping).

Exercise 5.4

Instead of keeping all returns, we can keep

• $N(s, a)$: a count of how many times action $a$ was taken in state $s$

• $Q(s, a)$: the running average of returns

Then, when we see a new return $G_t$, we update incrementally:

Exercise 5.5

The first-visit MC return is 10, whereas the every-visit MC return is the average of the returns from each visit:

Exercise 5.6

Firstly, we only include the time steps where action $a$ was taken in state $s$. Secondly, since the first action is restricted, we start our ratios from $t+1$ instead of $t$.

Exercise 5.7

Weighted importance sampling is biased but the bias vanishes asymptotically as the number of episodes grows.

Early on, the denominator (sum of weights) is small and unstable, which can cause the ratio to fluctuate and push the estimate away from the true value. This explains the initial increase in mean square error (MSE). As more data accumulates, the denominator stabilizes, the bias shrinks, and the error decreases.

Ordinary importance sampling, on the other hand, is unbiased at every sample size but has high variance. Its MSE starts high due to this variance but decreases steadily with more episodes.

Exercise 5.8

For every-visit MC, the second moment of the importance sampling ratio is:

This is equal to:

This can be written as:

Since the summation on the right follows a geometric series, we can rewrite it as:

So the expression becomes:

The first term diverges while the second term converges. But since the first term diverges at a greater rate, the overall expression diverges.

Since the second moment of the importance sampling ratio is infinite, the variance of the every-visit MC estimator is also infinite.

Exercise 5.9

Instead of appending $G$ to $Returns(S_t)$, we keep a running total of the returns for each state.

• $N(s_t) \leftarrow N(s_t) + 1$
• $V(s_t) \leftarrow V(s_t) + \frac{1}{N(s_t)} \Big(G_t - V(s_t)\Big)$

Everything else remains the same.

Exercise 5.10

Let $C_n = \sum_{i=1}^{n} W_i$

Then, we can rewrite the equation as:

Exercise 5.11

This is because in off-policy control, the target policy $\pi$ is kept deterministic and greedy.

If $A_t \neq \pi(S_t)$ then $\pi(A_t \mid S_t) = 0$ and we stop since the importance-sampling ratio beyond this point will be $0$.

Otherwise, $\pi(A_t \mid S_t) = 1$ and so the importance-sampling ratio will be

Exercise 5.12

To solve this problem, I used an Off-policy Monte Carlo agent with an epsilon-greedy behavior policy and an initial value of -500 for each state. Additionally, I used exploring starts for the first half of the episodes to ensure that the agent explores the entire state space.

The value function for the first track is:

Sample trajectories for the first track:

The value function for the second track is:

Sample trajectories for the second track:

Exercise 5.13

The expectation in $\rho_{t:T-1} R_{t+1}$ can be written as:

We know that $R_{t+1}$ is the reward for taking action $A_t$ in state $S_t$ and following policy $\pi$ from that point onwards. This means that the reward $R_{t+1}$ and the actions taken after $t+1$ are independent.

Therefore, we can rewrite the expectation as:

And since we know that

The expectation will then become:

Exercise 5.14

The discounting-aware weighted importance-sampling estimator for action-value function is:

(Skipped for now)