Introduction

Dynamic programming in the previous article assumed that we knew the MDP's transition probabilities and reward function.

$$\mathcal{P}_{ss'}^a, \qquad \mathcal{R}_s^a$$

Given this model, we can perform a Bellman backup by taking a probability-weighted average over every possible next state.

But in a new game or a real robot, it is difficult to know in advance the probability of reaching each next state after an action. We cannot fill in the transition matrix before experiencing the environment.

Monte Carlo methods take a very straightforward approach.

If the model is unknown, run actual episodes to the end and correct the values with the returns received.

It is like rolling a die repeatedly and taking an average when we do not know the probability of each face. Instead of calculating the probabilities of every possible outcome, we collect actual samples to approximate the expectation.

This article introduces Monte Carlo prediction, which estimates the value of a fixed policy $\pi$ from experience.

First, Distinguish Prediction from Control

In reinforcement learning, prediction is the problem of evaluating how good a fixed policy is.

$$\text{Prediction: given } \pi, \text{ estimate } v_\pi$$

Control is the problem of finding a good policy itself.

$$\text{Control: find } \pi_*$$

Monte Carlo prediction does not change the policy. We run several episodes under policy $\pi$, observe the return obtained from each state, and estimate $v_\pi(s)$.

If we begin evaluation and improvement at the same time, it is easy to lose track of what each equation is changing. We therefore begin by making a report card for one fixed habit of behavior.

Replacing the Expected Value with an Empirical Average

The state value is defined as

$$v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t=s \right].$$

Calculating this expectation exactly requires the probabilities of every possible path. Monte Carlo instead collects returns actually observed from state $s$ and averages them.

$$V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G^{(i)}(s)$$

• $N(s)$: the number of times state $s$ has been used for evaluation
• $G^{(i)}(s)$: the return after state $s$ in sample $i$
• $V(s)$: the value estimated from experience

With enough samples, the empirical average $V(s)$ approaches the true expected value $v_\pi(s)$.

The Return Is Known Only After the Episode Ends

Consider the following short episode.

$$S_0 \xrightarrow{+1} S_1 \xrightarrow{-1} S_2 \xrightarrow{+5} \text{Terminal}$$

Let $\gamma=0.9$. After the episode ends, we calculate the return backward from the final state.

$$G_2=5$$ $$G_1=-1+0.9\times5=3.5$$ $$G_0=1+0.9\times3.5=4.15$$

The immediate reward at $S_0$ is $+1$, but its return is $4.15$ because it also includes the later rewards $-1$ and $+5$.

We now move the value estimate of $S_0$ toward $G_0=4.15$, and the estimate of $S_1$ toward $G_1=3.5$.

An Incremental Update Without Recalculating the Average

We do not need to sum every previous return again whenever a new one arrives. The average can be updated incrementally.

$$V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} \left[ G_t-V(S_t) \right]$$

The expression inside the brackets,

$$G_t-V(S_t),$$

is the difference between the newly observed return and the previous expectation.

For example, suppose $V(S_0)=3$, the new return is $G_0=4.15$, and the visit count is now $N(S_0)=5$. Then

$$\begin{aligned} V(S_0) &\leftarrow 3 + \frac{1}{5}(4.15-3) \\ &= 3.23. \end{aligned}$$

The old estimate of $3$ moves one fifth of the distance toward the new observation of $4.15$.

We can also use a fixed learning rate $\alpha$ instead of the visit count.

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t-V(S_t) \right]$$

A fixed $\alpha$ does not preserve every old experience with equal weight. It continues to give recent experience a constant amount of influence, which is useful in non-stationary problems where the environment changes over time.

First-Visit and Every-Visit

The same state can appear several times in one episode.

$$A \rightarrow B \rightarrow A \rightarrow C \rightarrow A \rightarrow \text{Terminal}$$

Two methods arise depending on which visit's return we use.

First-Visit Monte Carlo

Use only the return following the first occurrence of state $A$ in an episode. In the episode above, only the first $A$ produces an update.

Every-Visit Monte Carlo

Use the return after every occurrence of state $A$. Because the three occurrences of $A$ have different remaining futures, they produce three updates.

Under sufficient conditions, both methods converge to $v_\pi(s)$. When first learning the idea, it is more useful to see the names as answers to one question: “if a state repeats within an episode, which visits should count?”

Monte Carlo Does Not Bootstrap

The Monte Carlo target is the actual return $G_t$.

$$\text{MC target}=G_t$$

The target does not contain the current value estimate $V$. We say that this method does not bootstrap.

Bootstrapping replaces an unobserved part of the future with a current estimate. Monte Carlo waits to observe the entire reward sequence, so it borrows no estimate in its target.

This property has both advantages and disadvantages.

Advantages

• It does not require transition and reward models.
• Even if the current value estimate is wrong, the target does not directly reuse that error.
• Its target—the return from an actual episode—is easy to understand.

Disadvantages

• It must wait for the episode to end.
• It is difficult to apply as-is to a continuing task that never ends.
• The return can have high variance because it is affected by randomness in many actions, transitions, and rewards.

Returns Can Vary Greatly Even from the Same State

Suppose five episodes beginning from state $s$ produce the following returns.

$$10,\;-4,\;7,\;0,\;12$$

Their average is $5$.

$$V(s)=\frac{10-4+7+0+12}{5}=5$$

Yet individual samples range widely, from $-4$ to $12$. If both the policy and environment are stochastic, the randomness of the entire episode accumulates in the return.

Monte Carlo finds a value by averaging these fluctuating returns over many trials. It uses an unbiased actual return, but an individual update can be noisy.

TD, introduced next, uses only one reward and the next state's value instead of an entire episode. It observes less of the actual future, but reduces variance and can update immediately.

The Steps of Monte Carlo Prediction

In words, the algorithm proceeds as follows.

1. Initialize $V(s)$ and the visit counts $N(s)$.
2. Follow policy $\pi$ to generate one complete episode.
3. Starting from the terminal state, calculate the return $G_t$ at every time step.
4. Select visits according to either the first-visit or every-visit rule.
5. Update $V(S_t)$ toward $G_t$.
6. Repeat over many episodes.

The important point is that step 2 does not improve the policy. We are performing policy evaluation only.

Action values $Q(s,a)$ can be learned in the same way. Count visits to state-action pairs instead of states and average the return from each corresponding time step.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ G_t-Q(S_t,A_t) \right]$$

Improving a policy to be $\epsilon$-greedy with respect to these Q-values leads to Monte Carlo control. This series, however, covers control in detail through the TD methods SARSA and Q-Learning.

What to Remember

The central idea of this article is

Monte Carlo prediction estimates the value of a policy from actual returns sampled after episodes end.

More specifically:

1. A value can be learned from experience generated by a policy even when the model is unknown.
2. The expectation in $v_\pi(s)$ is approximated by the average of observed returns.
3. The target is the actual return $G_t$.
4. First-visit uses only the first visit in an episode, while every-visit uses them all.
5. Monte Carlo does not bootstrap and must wait for the episode to end.
6. It uses actual returns, but those returns can have high variance.

The next article begins with the question, “must we really wait until the episode ends?” Temporal-difference learning borrows the next state's value estimate and updates immediately after every step.

References

• David Silver, Lecture 4: Model-Free Prediction
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition