Step-Size Parameters
A suitable step-size sequence must satisfy two requirements: it must be large enough initially and small enough eventually.
Why Step Size Matters
A step-size parameter controls how strongly new information influences an estimate. The central challenge is balance: the sequence must be large enough initially to support learning, yet small enough eventually to support convergence. These requirements describe two different phases of behavior rather than one fixed setting.
What do you think happens?
Suppose an algorithm keeps taking updates with a fixed step size. Should the estimate always settle permanently on the correct value?
Reveal answer
Answer: No, because a constant step size never becomes small enough
A constant step-size parameter does not satisfy the second convergence condition. The estimate can therefore continue to vary in response to the most recently received rewards.
The Two Convergence Requirements
A suitable step-size sequence must satisfy two requirements. First, it must be large enough initially. Early updates need enough influence for the method to keep learning from incoming information. Second, it must be small enough eventually. Later updates need to become sufficiently restrained for the estimate to settle toward convergence. A sequence that fails either requirement is unsuitable for complete convergence.
Tracing the 1/n Sequence
Following αₙ(a) = 1/n
Examine how the sample-average step-size sequence changes over successive steps.
First step: When n = 1, αₙ(a) = 1/n gives a step size of 1. This is large enough to have a strong initial influence.
Second step: When n = 2, the step size is 1/2. It is smaller than the first step.
Later steps: As n increases, 1/n becomes smaller. The individual updates therefore shrink over time.
Convergence conditions: The source identifies αₙ(a) = 1/n as a sequence that satisfies both convergence conditions: it is large enough initially and small enough eventually.
The sequence begins with a relatively large step and decreases as the number of steps grows, satisfying both stated convergence requirements.
The important pattern is not merely that the numbers change. The sequence combines a relatively strong beginning with progressively smaller later steps. That is precisely why the source presents αₙ(a) = 1/n as satisfying both convergence conditions.
What Constant Steps Change
A constant step size α does not provide complete convergence because it never becomes small enough. The estimate continues to vary in response to the most recently received rewards. Repeated updating alone is therefore not sufficient to guarantee that the estimate settles permanently on one value.
When Continued Adaptation Helps
| Environment goal | Useful step-size behavior | Reason |
|---|---|---|
| Complete convergence | Large enough initially and small enough eventually | The estimate needs to learn and then settle |
| Changing optimal solution | A constant step size can remain useful | The estimate must continue adapting when the situation changes |
A nonstationary environment is one in which the optimal solution changes over time. In such an environment, complete convergence is not always desirable: an estimate that stops changing cannot respond to a changed situation. This is why constant step-size parameters can be desirable even though they fail the second convergence condition. The source describes effectively nonstationary problems as the norm in reinforcement learning.
Practical Schedule Trade-Offs
Satisfying the two convergence conditions does not automatically make a step-size sequence attractive for every application. The source notes that such sequences can converge very slowly or require considerable tuning to obtain a satisfactory convergence rate. They are therefore often used in theoretical work but are seldom used in applications and empirical research.
Assuming that satisfying the convergence conditions guarantees a fast or practical method.
The convergence conditions describe suitability for convergence, not an automatic guarantee of a satisfactory convergence rate.
Fix:
Treat theoretical validity and practical performance as separate questions; practical use may require considerable tuning.Treating a constant step size as suitable for complete convergence simply because updates continue.
A constant step size never becomes small enough and does not satisfy the second convergence condition.
Fix:
Use a shrinking sequence when complete convergence is the objective, or recognize that a constant step size serves a different purpose in a changing environment.Assuming that all continued variation is undesirable.
In a nonstationary environment, an estimate that stops changing cannot respond to changed conditions.
Fix:
Judge the step-size behavior against the environment: settling may be desirable for convergence, while continued adaptation may be desirable when the optimum changes.
Check Your Understanding
Explain in your own words why αₙ(a) = 1/n is suitable for complete convergence, while a constant step size α is not. Then explain one situation in which the constant step size may nevertheless be desirable.
Hints
- Use both parts of the convergence requirement: initial size and eventual size.
- For the constant step size, focus on what never changes.
- For the final part, consider what happens when the optimal solution changes over time.
Classifying Two Schedules
Classify the sample-average sequence αₙ(a) = 1/n and a constant step size α according to the source's convergence requirements.
Sample-average sequence: The sequence starts relatively large and becomes smaller as n increases.
Convergence classification: The source states that αₙ(a) = 1/n satisfies both convergence conditions.
Constant step size: A constant α never becomes small enough.
Behavioral consequence: The estimate continues to vary in response to the most recently received rewards, so complete convergence is not provided.
Environmental qualification: If the optimal solution changes over time, this continued adaptation can be desirable.
The 1/n sequence supports the stated convergence requirements, while a constant step size does not provide complete convergence but can remain useful in nonstationary environments.
Key Takeaways
- A convergence-supporting step-size sequence must be large enough initially and small enough eventually.
- The sample-average sequence αₙ(a) = 1/n satisfies both convergence conditions.
- A constant step size never becomes small enough, so it does not provide complete convergence.
- Constant step sizes can be desirable in nonstationary environments because continued adaptation helps track a changing optimal solution.
- Theoretical validity does not guarantee practical speed; valid sequences may converge slowly or require considerable tuning.
Key Takeaways
- Step-size schedules must balance strong initial learning with sufficiently small eventual updates.
- The sequence αₙ(a) = 1/n decreases over time and satisfies both convergence requirements.
- A constant step size causes continued variation rather than complete convergence.
- That continued variation can be useful when the environment is nonstationary and its optimal solution changes.
- Convergence conditions are theoretical guarantees about behavior, not guarantees of fast or easily tuned practical performance.