Monte Carlo Control: Estimating Qπ

In the previous section, we saw how Monte Carlo (MC) methods can estimate the state-value function $V^\pi(s)$ for a given policy $\pi$ by averaging the returns observed after visiting state $s$. This process, called MC prediction or evaluation, tells us how good it is to be in a particular state under the current policy. However, our ultimate aim in Reinforcement Learning is usually control finding the optimal policy $\pi^*$ that maximizes the expected return from all states.

To achieve control using MC methods, especially when we don't have a model of the environment (i.e., we don't know the transition probabilities $p(s', r | s, a)$), estimating the state-value function $V^\pi$ is often not sufficient. Why? Because improving the policy requires knowing the value of choosing different actions in a given state. If we only know $V^\pi(s)$, we can't easily determine which action $a$ leads to the best outcome without knowing the environment's dynamics. We'd need the model to compute $\sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]$.

This is where the action-value function $Q^\pi(s, a)$ becomes essential. Recall that $Q^\pi(s, a)$ represents the expected return starting from state $s$, taking action $a$, and subsequently following policy $\pi$. If we have an accurate estimate of $Q^\pi(s, a)$ for all actions $a$ available in state $s$, choosing the best action is straightforward: we simply select the action with the highest estimated $Q$-value.

$\pi'(s) = \underset{a}{\text{argmax}} Q(s, a)$

Therefore, for model-free control using MC methods, we shift our focus from estimating $V^\pi(s)$ to estimating $Q^\pi(s, a)$.

Estimating Action-Values ($Q^\pi$) with Monte Carlo

The core idea remains the same as MC prediction: we learn from complete episodes of experience and average the observed returns. However, instead of averaging returns for each state visited, we average returns for each state-action pair $(s, a)$ visited.

Let's consider the first-visit MC method applied to estimating $Q^\pi$. We run multiple episodes following policy $\pi$. For each episode, we look at every state-action pair $(S_t, A_t)$ that occurred. If it's the first time this specific pair $(S_t, A_t)$ was visited during this episode, we calculate the total return $G_t$ from that point until the end of the episode:

$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 terminal time step of the episode.

We maintain an estimate $Q(s, a)$ for every state-action pair. Similar to MC prediction for $V^\pi$, we can update our estimate $Q(S_t, A_t)$ by averaging all the returns $G_t$ observed after first visits to $(S_t, A_t)$ across all episodes.

A practical way to implement this is using an incremental update rule. We keep track of the number of times each state-action pair $(s, a)$ has been visited for the first time across episodes, let's call this count $N(s, a)$. After generating an episode and calculating the return $G_t$ following the first visit to $(S_t, A_t)$, we update our estimate $Q(S_t, A_t)$ as follows:

1. Increment the count: $N(S_t, A_t) \leftarrow N(S_t, A_t) + 1$
2. Update the estimate: $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G_t - Q(S_t, A_t))$

This formula adjusts the current estimate $Q(S_t, A_t)$ in the direction of the newly observed return $G_t$. The step size $\frac{1}{N(S_t, A_t)}$ ensures that we are essentially calculating a running average; early returns have a larger impact, while later returns cause smaller adjustments as our estimate becomes more confident. Often, a constant step size $\alpha$ is used instead of $\frac{1}{N(s, a)}$ for non-stationary problems (where the environment or policy might change):

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (G_t - Q(S_t, A_t))$

where $0 < \alpha \le 1$ is a learning rate parameter.

The Challenge of Exploration

Now we have a way to estimate $Q^\pi(s, a)$, the action-values for a given policy $\pi$. But how do we use this to find the optimal policy $\pi^*$?

The natural inclination is to follow the pattern of Generalized Policy Iteration (GPI), which involves alternating between policy evaluation (estimating the value function for the current policy) and policy improvement (making the policy greedy with respect to the current value function estimates).

With MC methods, this would look like:

1. Policy Evaluation: Use MC to estimate $Q^\pi(s, a)$ by running many episodes under policy $\pi$ and averaging returns for state-action pairs.
2. Policy Improvement: Update the policy $\pi$ to be greedy with respect to the estimated $Q$-values: $\pi(s) \leftarrow \underset{a}{\text{argmax}} Q(s, a)$ for all $s$.
3. Repeat until the policy and value function stabilize.

However, there's a significant complication: exploration. If the policy $\pi$ becomes deterministic and greedy early on (e.g., it always chooses action $a_1$ from state $s$), then we will only ever observe returns for the pair $(s, a_1)$. We will never gather experience (and thus never update the $Q$-value estimates) for other potentially better actions (like $a_2, a_3, \dots$) from state $s$. The agent might get stuck in a suboptimal loop because it never explores alternatives.

To guarantee that MC methods converge to the optimal policy, we need to ensure that all state-action pairs continue to be visited. This is known as maintaining exploration.

One theoretical approach is the assumption of exploring starts. This assumes that every episode starts in a randomly chosen state-action pair $(s, a)$, and only then follows the policy $\pi$. This ensures that every pair has a non-zero probability of being selected as the starting point, guaranteeing eventual exploration of all pairs. While useful for theoretical proofs, exploring starts are often not feasible in real-world applications (e.g., you might not be able to arbitrarily set the initial state and action of a robot).

Therefore, practical MC control algorithms need mechanisms to ensure ongoing exploration even without relying on exploring starts. This often involves using policies that are not fully deterministic or greedy, such as $\epsilon$-greedy policies, which usually act greedily but sometimes (with a small probability $\epsilon$) choose a random action. We will discuss these specific algorithms and the distinction between on-policy and off-policy learning, which relate directly to how exploration is handled, in the following sections.