ε-soft policies
On-policy first-visit MC control alternates between episode generation and policy improvement.
The Repeating Learning Cycle
On-policy first-visit Monte Carlo control learns by repeating two activities. First, it generates an episode using the current policy. Then, it uses the returns observed in that episode to update action-value estimates and improve the policy. The improved policy is used to generate later episodes, so each policy update can affect the data collected in the next cycle.
The word on-policy matters for tracing: the policy that is updated is also the policy used to generate later episodes. Do not treat episode generation and policy improvement as unrelated processes.
Finding the First Visit
A first-visit update uses only the return after the first occurrence of a particular state-action pair in an episode. If the same state-action pair appears again later in that episode, the later occurrence does not provide the return for that first-visit update. The algorithm therefore has to inspect the episode in order, identify the first matching occurrence, and select the return from that point.
One Pair Appears Twice
An episode contains the state-action pair S1, A1 at position 1 and again at position 3. Which occurrence supplies the return for the first-visit update?
Scan the episode: Read the episode from its beginning and look for the first occurrence of S1, A1.
Select position 1: The pair first appears at position 1, so position 1 is the occurrence used for the first-visit update.
Ignore the later occurrence for this update: The appearance at position 3 is not the first occurrence in this episode, so its later return is not used for this first-visit update.
The return selected for S1, A1 is the return after its first occurrence at position 1.
From Returns to Q
For each state-action pair, the algorithm stores the returns selected from first visits. Its estimate of Q for that state-action pair is obtained by averaging the stored returns. Thus, the Q estimate depends on the returns that were actually recorded, not simply on the most recent return.
Updating an Estimate
Suppose the first-visit process has stored three returns for S1, A1: 4, 6, and 8. What does the averaging step do?
Gather the stored returns: The returns associated with S1, A1 are 4, 6, and 8.
Average them: Combine the stored returns and divide by the number of stored returns.
Interpret the result: The resulting average is the current estimate of Q for S1, A1.
The estimate is the average of 4, 6, and 8, which is 6.
When tracing an unexpected Q value, inspect the contents of the stored-return collection before inspecting the average. A correct averaging operation cannot repair a return that was selected or stored incorrectly.
Improving Without Removing Exploration
After Q values are updated, the algorithm examines each state appearing in the episode. For that state, the action with the maximum Q value becomes A*. The policy is then updated for all available actions according to the ε-soft rule. The result is an improved policy that still gives every action a minimum probability of being selected.
Choosing A* While Staying ε-soft
At a state, suppose the updated Q estimate for Action B is greater than the estimates for Action A and Action C. What is selected as A*, and what must remain true of the resulting policy?
Compare Q values: Examine the updated Q value for every available action at the state.
Select the maximum: Because Action B has the maximum Q value, Action B becomes A*.
Apply the ε-soft update: Update the probabilities for all available actions using the ε-soft rule rather than assigning probability only to Action B.
Action B becomes A*, and every available action retains a minimum probability of selection under the updated ε-soft policy.
Tracing an Unexpected Result
An unexpected result can first arise at several different stages of the cycle. The useful debugging approach is to trace the intended order: episode generation, first-visit selection, return storage, Q-value averaging, and policy improvement. Checking only the final Q value or final policy can hide the stage where the deviation began.
Using a later occurrence of a repeated state-action pair
First-visit control uses the return after the first occurrence in the episode.
Fix:
Scan the episode from the beginning and select the return associated with the first occurrence.Replacing the stored returns with only the newest return
Q values are estimated by averaging stored returns.
Fix:
Keep the selected returns that belong to the pair and average the stored collection.Treating A* as the only action the policy can select
The resulting policy remains ε-soft, so every action has a minimum probability of selection.
Fix:
Use A* to identify the preferred action, then update the probabilities of all available actions according to the ε-soft rule.Updating the policy before completing the return-based update
The intended cycle is episode generation followed by return-based updating and policy improvement.
Fix:
Trace the stages in order and verify the episode, first occurrence, stored return, average, and policy update.
When debugging, record an audit trail for one state-action pair: where it first appeared in the episode, which return was selected, which returns are stored for it, what average produces its Q value, and which action has the maximum Q value at the state. This follows the algorithm's intended order and helps identify the first stage where the result differs.
Practice the Trace
An episode contains S2, A2 twice. The first occurrence is followed by one return, and the second occurrence is followed by a different return. The stored returns for S2, A2 already contain two earlier values. Trace the update without calculating a policy probability.
Hints
- Start with the first occurrence in the episode, not the second.
- Add the selected first-visit return to the stored returns for S2, A2.
- Estimate Q from the complete stored-return collection.
- Compare the resulting Q values for all available actions at S2 to identify A*.
- The updated policy must remain ε-soft.
What do you think happens?
If an action has the maximum Q value at a state, does the ε-soft policy assign all probability to that action?
Reveal answer
Answer: No, the policy still gives every action a minimum probability.
The maximum-Q action becomes A*, but the resulting policy remains ε-soft. Therefore, all available actions retain a minimum probability of being selected.
The Complete Trace
- Generate an episode using the current ε-soft policy.
- For each state-action pair of interest, locate its first occurrence in that episode.
- Select the return after that first occurrence and store it for the pair.
- Average the stored returns to estimate Q for each state-action pair.
- For each state in the episode, identify A* as the action with the maximum Q value.
- Update the probabilities of all available actions using the ε-soft rule.
- Use the updated policy to generate later episodes and repeat the cycle.
The central tracing idea is order. Episode generation supplies the experience; first-visit selection determines which occurrence counts; stored returns support the Q estimate; the maximum Q identifies A*; and the ε-soft update improves the policy without removing every action from consideration.
Key Takeaways
- On-policy first-visit Monte Carlo control alternates between generating an episode and improving the policy.
- Only the return after the first occurrence of a state-action pair in an episode is used for that first-visit update.
- Stored returns are averaged to estimate Q values.
- The action with the maximum Q value becomes A*, while the policy remains ε-soft and gives every action a minimum probability.
- When tracing an unexpected result, inspect episode generation, first-visit selection, return storage, Q averaging, and policy improvement in that order.