On-Policy Temporal-Difference Control
Sarsa convergence is tied to the policy's dependence on Q.
The Convergence Question
Sarsa is an on-policy temporal-difference control method, but temporal-difference control alone does not guarantee convergence. The important question is how the policy is connected to Q, the action-value function. As Q changes, the policy may change too, so convergence depends on both continued exploration and the policy's behavior in the limit.
The stated convergence guarantee requires two conditions: every state-action pair must be visited an infinite number of times, and the policy must approach the greedy policy in the limit.
How Q Shapes the Policy
A policy can depend on Q because Q influences which action is treated as preferable. When Q changes, the policy may change as well. This dependence matters because Sarsa's convergence discussion is not about an unrelated, fixed policy; it is about a policy whose behavior is connected to the action-value estimates being learned.
Two Policy Dependencies
Suppose an agent's Q-values change while it is learning. What should you expect if the policy depends on Q?
Start with current estimates: The current Q-values influence which action the policy treats as preferable.
Change Q: Learning changes the action-value estimates. Because the policy depends on Q, its action preferences may change too.
Continue learning: The agent must still visit every state-action pair an infinite number of times while the policy moves toward greedy behavior.
The policy's dependence on Q is central to the convergence discussion: Q influences the policy, and changes in the policy affect how the agent behaves while learning.
Balancing Exploration and Preference
An ε-greedy policy chooses the greedy action with probability 1 − ε and a random action with probability ε. The value of ε controls the balance between following the action currently favored by Q and allowing random action selection.
Consider a state where Q currently makes one action the greedy action. Under an ε-greedy policy, the agent usually follows that preference through the 1 − ε portion of the choice, while the ε portion preserves random action selection. The policy therefore uses Q to prefer an action without eliminating random selection entirely.
Shrinking Epsilon Over Time
An ε-greedy policy can move toward greedy behavior by setting ε = 1/t, where t denotes the time step. As t increases, 1/t becomes smaller. Consequently, the probability assigned to random action selection decreases, while the probability assigned to the greedy action, 1 − ε, moves toward 1.
Reading the Schedule
What happens to the random-action probability as t increases under ε = 1/t?
At t = 1: The exploration probability is 1/1, or 1.
At t = 2: The exploration probability is 1/2, which is smaller than at t = 1.
As t continues to grow: The value 1/t becomes smaller, so the probability of random action selection decreases.
The ε-greedy policy approaches greedy behavior because ε moves toward zero and 1 − ε moves toward one.
Checking the Guarantee
The phrase probability 1 describes the strength of the convergence result. It does not mean that every arbitrary policy produces convergence. The visitation condition and the limiting behavior of the policy are essential parts of the claim.
Assuming that temporal-difference control alone guarantees convergence.
The convergence result depends on how the policy is connected to Q, not merely on the use of temporal-difference control.
Fix:
Check both required conditions: infinite visits to every state-action pair and a policy that approaches the greedy policy.Treating probability 1 as a guarantee for every policy.
The stated result is conditional. It does not apply when the required visitation or limiting-policy condition is missing.
Fix:
Read probability 1 together with the assumptions that precede it.Checking only whether the policy eventually becomes greedy.
The policy condition is satisfied, but the infinite-visitation condition is not.
Fix:
Both conditions must hold; satisfying only one is insufficient.Checking only whether every state-action pair is visited infinitely often.
The visitation condition is satisfied, but the limiting-policy condition is not.
Fix:
Verify both continued visitation and convergence toward greedy behavior.Treating Q and the policy as unrelated.
The source identifies the policy's dependence on Q as central to the convergence discussion.
Fix:
Track how Q influences which action is treated as preferable and how policy behavior changes as Q changes.
| Setup | Condition about visits | Condition about policy | Matches the stated guarantee? |
|---|---|---|---|
| Policy becomes greedy, but some pairs are not visited infinitely often | Missing | Present | No |
| All pairs are visited infinitely often, but policy does not approach greedy behavior | Present | Missing | No |
| All pairs are visited infinitely often and policy approaches greedy behavior | Present | Present | Yes, under the stated conditions |
Test Your Understanding
A proposed Sarsa setup uses an ε-greedy policy with ε = 1/t. Explain why this schedule supports movement toward the greedy policy, then state the additional visitation condition required by the convergence guarantee.
Hints
- As t increases, what happens to 1/t?
- What happens to 1 − ε when ε becomes smaller?
- The convergence claim has two conditions. Name the one concerning state-action pairs.
Consider two hypothetical cases. Case A reaches greedy behavior but fails to visit some state-action pairs infinitely often. Case B visits every state-action pair infinitely often but does not approach the greedy policy. Which case satisfies the stated convergence guarantee, and why?
Hints
- List the two required conditions before evaluating the cases.
- Check each case against both conditions, not just one.
The On-Policy Picture
- Sarsa's convergence depends on the policy's connection to Q, not simply on the fact that Sarsa uses temporal-difference control.
- The stated convergence guarantee requires every state-action pair to be visited an infinite number of times.
- The policy must approach the greedy policy in the limit.
- An ε-greedy policy chooses the greedy action with probability 1 − ε and a random action with probability ε.
- With ε = 1/t, exploration probability decreases as time increases, so the policy moves toward greedy behavior.
Key Takeaways
- Sarsa's convergence guarantee is conditional rather than automatic.
- Every state-action pair must be visited an infinite number of times.
- The policy must approach the greedy policy in the limit.
- Because the policy depends on Q, changes in Q can change action preferences and policy behavior.
- An ε-greedy policy with ε = 1/t gradually reduces random action selection and approaches greedy behavior.