On-Policy First-Visit MC Control Implementation

Monte Carlo methods combine prediction and exploration to form control algorithms. Reinforcement Learning control aims to find an optimal policy, rather than merely evaluating a given policy. For Monte Carlo methods, this involves identifying the policy that maximizes the expected return based on experiences gathered from episodes.

We'll focus on an on-policy method, meaning the policy we are learning about ($\pi$) is the same policy used to generate the behavior (the episodes). Specifically, we'll detail the First-Visit MC Control algorithm. As the name suggests, it updates the value estimate for a state-action pair $(s, a)$ only based on the return following the first time that pair was visited within an episode.

The Challenge of MC Control: Estimating Action Values

To improve a policy, we generally need estimates of action values, $Q^\pi(s, a)$, rather than just state values, $V^\pi(s)$. Why? Because to decide if changing an action in a state $s$ is beneficial, we need to know the expected return of taking alternative actions $a'$ from that state $s$. Knowing $V^\pi(s)$ alone isn't sufficient.

So, our MC prediction task shifts from estimating $V^\pi(s)$ to estimating $Q^\pi(s, a)$. The core idea remains the same: average the returns observed after visiting a state-action pair. For First-Visit MC, we average the returns following the first occurrence of $(s, a)$ in each episode.

The update rule for the Q-value estimation looks very similar to the V-value estimation:

1. Initialize $Q(s, a)$ arbitrarily for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$.
2. Initialize $N(s, a) \leftarrow 0$ (a counter for the number of first visits to $(s,a)$).
3. Initialize Returns$(s, a) \leftarrow$ an empty list (to store returns).
4. Loop forever (for each episode):
   • Generate an episode following the current policy $\pi$: $S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_{T-1}, A_{T-1}, R_T$.
   • Initialize $G \leftarrow 0$.
   • Loop for each step $t = T-1, T-2, \dots, 0$:
     • $G \leftarrow \gamma G + R_{t+1}$ (Update the return).
     • Unless the pair $(S_t, A_t)$ appears in $S_0, A_0, \dots, S_{t-1}, A_{t-1}$:
       • Increment counter: $N(S_t, A_t) \leftarrow N(S_t, A_t) + 1$.
       • Update the action-value estimate by averaging:
       $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G - Q(S_t, A_t))$$
       • (Alternatively, append $G$ to Returns$(S_t, A_t)$ and recalculate $Q(S_t, A_t)$ as the average of this list).

This process gives us the policy evaluation part using MC. Now, how do we achieve policy improvement?

Policy Improvement and the Exploration Problem

Similar to Dynamic Programming, we can improve the policy by making it greedy with respect to the current action-value estimates. For a given state $s$, the improved policy would choose the action $a$ that maximizes $Q(s, a)$:

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

However, there's a significant catch if we only act greedily based on our current estimates. Monte Carlo methods learn from episodes generated by following the current policy. If the policy becomes deterministic and greedy early on, it might stop exploring certain actions altogether. If an action $a$ is never chosen in state $s$, we will never get returns for the pair $(s, a)$, and our estimate $Q(s, a)$ will never improve. We might converge to a suboptimal policy simply because we didn't explore enough to find the truly optimal actions.

Ensuring Exploration: $\epsilon$-Greedy Policies

To balance exploration (trying new actions) and exploitation (using the best-known actions), we use strategies that ensure continued exploration. A common and simple approach is the $\epsilon$-greedy policy.

An $\epsilon$-greedy policy behaves greedily most of the time but selects a random action with a small probability $\epsilon$.

• With probability $1 - \epsilon$, choose the action $a$ that currently has the highest estimated Q-value: $\underset{a}{\text{argmax}} Q(s, a)$.
• With probability $\epsilon$, choose an action randomly from all available actions in state $s$, with uniform probability.

This ensures that, eventually, every state-action pair has a non-zero probability of being visited, allowing our Q-value estimates to continue improving for all actions. The policy we learn about and the policy we use to generate episodes are both this $\epsilon$-greedy policy, hence the term "on-policy".

The On-Policy First-Visit MC Control Algorithm

Now we can combine MC estimation of Q-values with $\epsilon$-greedy policy improvement. This follows the pattern of Generalized Policy Iteration (GPI), where evaluation and improvement steps interact.

Algorithm: On-Policy First-Visit MC Control (for $\epsilon$-soft policies)

1. Initialization:
   • Initialize $Q(s, a) \in \mathbb{R}$ arbitrarily for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$.
   • Initialize $N(s, a) \leftarrow 0$ for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$.
   • Initialize an $\epsilon$-greedy policy $\pi$ based on $Q$. For any state $s$:
     • $\pi(a|s) \leftarrow \epsilon / |\mathcal{A}(s)|$ for all $a \in \mathcal{A}(s)$.
     • $a^* \leftarrow \underset{a}{\text{argmax}} Q(s, a)$ (break ties arbitrarily).
     • $\pi(a^*|s) \leftarrow \pi(a^*|s) + (1 - \epsilon)$.
2. Loop forever (for each episode):
   • (a) Generate Episode: Generate an episode $S_0, A_0, R_1, \dots, S_{T-1}, A_{T-1}, R_T$ using the current policy $\pi$.
   • (b) Initialize Return: $G \leftarrow 0$.
   • (c) Loop for each step $t = T-1, T-2, \dots, 0$:
     • Update Return: $G \leftarrow \gamma G + R_{t+1}$.
     • Check First Visit: Unless the pair $(S_t, A_t)$ appears in $S_0, A_0, \dots, S_{t-1}, A_{t-1}$:
       • Increment Counter: $N(S_t, A_t) \leftarrow N(S_t, A_t) + 1$.
       • Update Q-value Estimate (Policy Evaluation): $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G - Q(S_t, A_t))$$
       • Update Policy (Policy Improvement): Make policy $\pi$ $\epsilon$-greedy with respect to the updated $Q$ for state $S_t$:
         • Recalculate probabilities: $\pi(a|S_t) \leftarrow \epsilon / |\mathcal{A}(S_t)|$ for all $a \in \mathcal{A}(S_t)$.
         • Find best action: $a^* \leftarrow \underset{a}{\text{argmax}} Q(S_t, a)$.
         • Update probability for best action: $\pi(a^*|S_t) \leftarrow \pi(a^*|S_t) + (1 - \epsilon)$.

The interaction loop for On-Policy First-Visit MC Control. Episodes generated using the current $\epsilon$-greedy policy are used to update Q-values (evaluation), which in turn are used to update the $\epsilon$-greedy policy (improvement).

This algorithm interleaves evaluation and improvement on a step-by-step basis within each episode's processing. It guarantees that exploration continues because the policy $\pi$ remains $\epsilon$-soft (non-zero probability for all actions). As more episodes are collected, the Q-value estimates converge towards the true action values $Q^\pi(s, a)$ for the $\epsilon$-greedy policy $\pi$, and the policy itself gradually improves towards the optimal $\epsilon$-greedy policy. While not necessarily the truly optimal policy (due to the forced exploration), it's often close and significantly better than random behavior.

In practice, you might use dictionaries in Python to store $Q(s, a)$ and $N(s, a)$, where keys are state-action tuples (s, a). Episode generation involves sampling actions according to the current $\epsilon$-greedy policy probabilities stored or calculated on the fly. The subsequent practice section will provide a more concrete example.