First-visit Monte Carlo methods

The Repeating Learning Cycle

On-policy first-visit Monte Carlo control learns by repeating two activities: it generates an episode using the current policy, then uses returns observed in that episode to update its action values and policy. The updated policy is used to generate later episodes, so a policy change influences the data collected in the future.

A First-Visit Trace

Consider an illustrative episode in which the same state-action pair appears more than once. The first occurrence of a pair is the one that matters for the first-visit update. A later occurrence of that same pair in the same episode does not supply another return for that first-visit update.

From Returns to Q Values

The algorithm stores returns associated with state-action pairs. To estimate Q for a pair, it averages the stored returns for that pair. Each new first-visit observation can therefore contribute another stored return, while the Q estimate reflects the average of the returns collected so far.

Turning Q into an ε-Soft Policy

After Q values have been updated, the algorithm identifies A*, the action with the maximum Q value, for every state appearing in the episode. It then updates the probabilities of all available actions according to the ε-soft rule. The best action is favored, but the policy remains ε-soft, meaning every action retains a minimum probability of being selected.

The policy update has two parts. First, compare the available actions through their Q values and identify the maximum-Q action A*. Second, assign action probabilities using the ε-soft rule. Do not interpret this as removing all probability from the other actions: the source method keeps every action selectable with at least a minimum probability.

Finding the First Divergence

When a traced result is unexpected, inspect the algorithm in its execution order. Check the generated episode first. Then check whether the first occurrence of each state-action pair was identified correctly. Next check the return attached to that occurrence, the stored-return average used for Q, and finally the policy improvement step. The first stage that differs from the intended process is the most useful place to investigate.

• Using the return after every occurrence of a repeated state-action pair in the same episode.

  First-visit control uses only the return after the first occurrence for that first-visit update.

  Fix: Locate the earliest occurrence of the pair before selecting the return.

• Treating a Q update as the end of the process.

  The method alternates between episode generation and policy improvement, and the updated policy generates later episodes.

  Fix: After updating Q, identify the maximum-Q action and update the ε-soft policy.

• Making the policy completely deterministic after finding A*.

  The resulting policy remains ε-soft, so every action has a minimum probability of being selected.

  Fix: Favor A* while retaining the minimum probability required by the ε-soft rule for every action.

Trace It Yourself

• Confirm which episode was generated by the current ε-soft policy.
• Identify the first occurrence of each state-action pair being updated.
• Confirm that the return after that first occurrence is the one stored.
• Confirm that stored returns are averaged to estimate Q.
• Confirm that the maximum-Q action is identified as A*.
• Confirm that all available actions receive probabilities according to the ε-soft rule.

Key Takeaways

1. On-policy first-visit Monte Carlo control alternates between generating episodes and improving the policy.
2. Only the return after the first occurrence of a state-action pair is used for its first-visit update in an episode.
3. Q values are estimated by averaging stored returns for each state-action pair.
4. The maximum-Q action becomes A*, but the policy remains ε-soft and keeps every action selectable with a minimum probability.
5. To debug an unexpected result, trace episode generation, first-visit selection, return handling, Q averaging, and policy improvement in order.