On-Policy Temporal-Difference Control
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.
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?
- 1Start with current estimates
The current Q-values influence which action the policy treats as preferable.
- 2Change Q
Learning changes the action-value estimates. Because the policy depends on Q, its action preferences may change too.
- 3Continue 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?
- 1At t = 1
The exploration probability is 1/1, or 1.
- 2At t = 2
The exploration probability is 1/2, which is smaller than at t = 1.
- 3As 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.
Common mistake Assuming that temporal-difference control alone guarantees convergence.
What it looks likeSarsa is used, so convergence is treated as automatic.
Why it failsThe convergence result depends on how the policy is connected to Q, not merely on the use of temporal-difference control.
Do this insteadCheck both required conditions: infinite visits to every state-action pair and a policy that approaches the greedy policy.
Common mistake Treating probability 1 as a guarantee for every policy.
What it looks likeAny fixed policy is assumed to receive the same convergence guarantee.
Why it failsThe stated result is conditional. It does not apply when the required visitation or limiting-policy condition is missing.
Do this insteadRead probability 1 together with the assumptions that precede it.
Common mistake Checking only whether the policy eventually becomes greedy.
What it looks likeA policy becomes greedy, but some state-action pairs stop being visited infinitely often.
Why it failsThe policy condition is satisfied, but the infinite-visitation condition is not.
Do this insteadBoth conditions must hold; satisfying only one is insufficient.
Common mistake Checking only whether every state-action pair is visited infinitely often.
What it looks likeAll pairs continue to be visited, but the policy does not converge toward the greedy policy.
Why it failsThe visitation condition is satisfied, but the limiting-policy condition is not.
Do this insteadVerify both continued visitation and convergence toward greedy behavior.
Common mistake Treating Q and the policy as unrelated.
What it looks likeChanges in Q are assumed to have no effect on action preference.
Why it failsThe source identifies the policy's dependence on Q as central to the convergence discussion.
Do this insteadTrack 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 |
Sarsa's convergence statement requires both conditions, not just one.
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
- 1Sarsa's convergence depends on the policy's connection to Q, not simply on the fact that Sarsa uses temporal-difference control.
- 2The stated convergence guarantee requires every state-action pair to be visited an infinite number of times.
- 3The policy must approach the greedy policy in the limit.
- 4An ε-greedy policy chooses the greedy action with probability 1 − ε and a random action with probability ε.
- 5With ε = 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.