Monte Carlo Prediction: Estimating Vπ

Monte Carlo (MC) methods offer a way to learn from experience without needing a model of the environment's dynamics ($p(s', r | s, a)$). The first step in using MC methods is often prediction, which means estimating the value function $V^\pi(s)$ for a given policy $\pi$. The value function $V^\pi(s)$ represents the expected cumulative discounted reward starting from state $s$ and following policy $\pi$ thereafter.

The core idea behind MC prediction is remarkably simple: we want to estimate an expected value, $V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$. The law of large numbers tells us that we can approximate an expected value by taking the average of many samples. In MC methods, these samples are the actual returns ($G_t$) observed after visiting state $s$ during simulated or real interactions with the environment.

To get these samples, we need to run complete episodes following the policy $\pi$. An episode is a sequence of states, actions, and rewards starting from an initial state and ending at a terminal state: $S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$. For any time step $t$ within an episode, the return $G_t$ is the total discounted reward from that point forward:

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

Where $T$ is the time step of the terminal state and $\gamma$ is the discount factor.

MC prediction estimates $V^\pi(s)$ by averaging the returns $G_t$ observed following visits to state $s$ across multiple episodes. There are two main variants for how we handle multiple visits to the same state within a single episode.

First-Visit Monte Carlo Prediction

In the first-visit MC method, we only consider the return following the first time state $s$ is visited in each episode.

Here's the procedure:

1. Initialization:
   • Initialize the value estimate $V(s)$ to an arbitrary value (e.g., 0) for all states $s \in \mathcal{S}$.
   • Initialize an empty list, Returns(s), for each state $s$ to store the returns observed for that state.
2. Episode Loop: Repeat for many episodes:
   • Generate a full episode by following policy $\pi$. Let the sequence be $S_0, A_0, R_1, S_1, \dots, S_T$.
   • Keep track of which states have already been visited within this episode. A set or boolean array is useful here.
   • Iterate backwards through the time steps of the episode, from $t = T-1$ down to $0$.
   • Calculate the return $G_t = R_{t+1} + \gamma G_{t+1}$ (working backwards is efficient).
   • If state $S_t$ has not been visited earlier in this episode:
     • Mark $S_t$ as visited for this episode.
     • Append the calculated return $G_t$ to the list Returns(S_t).
     • Update the value estimate for state $S_t$ by averaging all returns collected so far in Returns(S_t): $$V(S_t) = \text{average}(\text{Returns}(S_t))$$

As more episodes are generated and more returns are collected for each state, the average in Returns(s) will converge to the true expected return $V^\pi(s)$.

Every-Visit Monte Carlo Prediction

The every-visit MC method is similar, but it averages the returns following every visit to state $s$ within each episode.

The procedure changes slightly in step 2:

1. Initialization: Same as First-Visit MC.
2. Episode Loop: Repeat for many episodes:
   • Generate a full episode using policy $\pi$: $S_0, A_0, R_1, S_1, \dots, S_T$.
   • Iterate backwards through the time steps, $t = T-1$ down to $0$.
   • Calculate the return $G_t = R_{t+1} + \gamma G_{t+1}$.
   • Append the calculated return $G_t$ to the list Returns(S_t).
   • Update the value estimate for state $S_t$: $$V(S_t) = \text{average}(\text{Returns}(S_t))$$

Both first-visit and every-visit MC methods converge to the true state-value function $V^\pi(s)$ as the number of visits (first visits or all visits, respectively) to each state approaches infinity. First-visit MC is often easier to analyze theoretically, while every-visit MC might be slightly easier to implement initially and has also seen successful application. For large numbers of episodes, the differences often become less significant.

Incremental Implementation

Storing all the returns for every state can become memory-intensive if we run many episodes or if the state space is large. We can compute the average incrementally without storing the whole list of returns.

Suppose we have just obtained a new return $G$ after a visit (either first or every, depending on the method) to state $s$. Let $N(s)$ be the count of returns collected for state $s$ before this new one. We want to update our current estimate $V(s)$ (which is the average of the previous $N(s)$ returns) using the new return $G$.

The new average after $N(s)+1$ returns will be:

$$V_{new}(s) = \frac{1}{N(s)+1} \sum_{i=1}^{N(s)+1} G_i = \frac{1}{N(s)+1} (G + \sum_{i=1}^{N(s)} G_i)$$

Since the old estimate was $V_{old}(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i$, we have $\sum_{i=1}^{N(s)} G_i = N(s) V_{old}(s)$. Substituting this in:

$$V_{new}(s) = \frac{1}{N(s)+1} (G + N(s) V_{old}(s))$$

Rearranging this gives the common incremental update rule:

$$V_{new}(s) = V_{old}(s) + \frac{1}{N(s)+1} (G - V_{old}(s))$$

This update rule looks like: NewEstimate = OldEstimate + StepSize * (Target - OldEstimate). Here, the return $G$ serves as the "target" value we are trying to move our estimate towards, and the step size is $\frac{1}{N(s)+1}$.

To implement this, instead of lists Returns(s), we maintain:

• $V(s)$: The current average return (value estimate) for state $s$.
• $N(s)$: The count of returns averaged so far for state $s$.

When a new return $G$ is observed for state $s$:

1. Increment the count: $N(s) \leftarrow N(s) + 1$.
2. Update the value estimate: $V(s) \leftarrow V(s) + \frac{1}{N(s)} (G - V(s))$. (Note: we use the new $N(s)$ here).

Using a Constant Step Size

Sometimes, especially in non-stationary problems where the environment or policy might change over time, a constant step-size parameter $\alpha \in (0, 1]$ is used instead of $1/N(s)$:

$$V(s) \leftarrow V(s) + \alpha (G - V(s))$$

This gives more weight to recent returns, allowing the estimate to adapt if the true value $V^\pi(s)$ is changing. However, with a constant $\alpha$, the estimate doesn't fully converge to the true value; it will fluctuate around it. For stationary problems where we want convergence to the true $V^\pi(s)$, the $1/N(s)$ step size is generally preferred as it satisfies the conditions for stochastic approximation convergence.

MC prediction provides a solid, model-free way to evaluate a given policy $\pi$. By simply running episodes and averaging returns, we can estimate how good it is to be in any particular state under that policy. This ability to evaluate policies is a building block for the next step: finding better policies, which is the goal of MC Control.