Learning from Complete Episodes

Dynamic Programming methods rely heavily on having a complete model of the environment. These methods require knowledge of state transition probabilities $p(s', r | s, a)$ to compute expected values and find optimal policies. However, in many practical problems, such a model isn't available or is too complex to define accurately. How can an agent learn to make good decisions without knowing the rules of the game beforehand?

Monte Carlo (MC) methods provide an answer by learning directly from experience. Instead of relying on a model, MC methods learn value functions and policies by interacting with the environment and observing the outcomes. The fundamental unit of experience for basic MC methods is the episode.

An episode is a sequence of interactions starting from an initial state and ending at a terminal state. Think of it as one complete playthrough of a task. For example:

• One game of Blackjack, from the first deal to the point where someone wins or busts.
• Navigating a maze from a starting position until reaching the exit (or a dead end defined as terminal).
• One attempt by a robot arm to grasp an object, ending in success or failure.

Each episode consists of a sequence of states, actions, and rewards: $S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$, where $T$ is the final time step and $S_T$ is the terminal state.

The core idea behind Monte Carlo methods is straightforward: they estimate value functions based on the average return observed after visiting a state (or state-action pair) over many episodes. They operate by waiting until an entire episode is completed. Only then can the actual return following each state visited during that episode be calculated.

Recall the definition of the return $G_t$, which is the total discounted reward from time step $t$ onwards:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$$

Here, $\gamma$ is the discount factor ($0 \le \gamma \le 1$), and $T$ is the terminal time step of the episode.

Because MC methods require the full sequence of rewards until the episode terminates to calculate $G_t$, they can only be applied directly to episodic tasks, that is, tasks that are guaranteed to eventually terminate.

Once an episode finishes, we have a sample sequence of $(S_t, A_t, R_{t+1})$ tuples. We can then go back and calculate the observed return $G_t$ for every time step $t$ within that episode. If we want to estimate the state-value function $V^\pi(s)$, we look at all the times state $s$ was visited across many episodes. For each visit, we calculate the return $G_t$ that followed that visit. The estimate $V^\pi(s)$ is simply the average of these observed returns. Similarly, to estimate the action-value function $Q^\pi(s, a)$, we average the returns observed after taking action $a$ in state $s$.

This process relies on the law of large numbers: as we gather more and more episodes (more samples), the average of the sample returns converges to the true expected return, which is the definition of the value function.

This approach contrasts sharply with Dynamic Programming. DP methods use the environment's model ($p(s', r | s, a)$) to bootstrap, updating value estimates based on other value estimates one step ahead. MC methods, on the other hand, do not bootstrap. They use the actual, complete return $G_t$ observed from experience. This independence from a model is a significant advantage, but it also means we must wait until the end of an episode to make any updates.

In the following sections, we will examine how this principle of learning from complete episodes is used for both predicting values (estimating $V^\pi$ or $Q^\pi$ for a given policy $\pi$) and for finding optimal policies (control).