Temporal-Difference Learning and Q-Learning
Temporal-difference learning updates estimates from sampled rewards and discounted next-state estimates. Q-learning uses a maximum over next actions in its target. It is off-policy, but convergence requires conditions, and function approximation can cause instability.
What a learner can do afterwards
- Perform a temporal-difference update by hand and say which estimate moved and why
- Explain off-policy learning, distinguish the behavior action from Q-learning's maximum target, and state a convergence requirement
- Give one failure mode of bootstrapping with a function approximator
1 · Read
An MDP defines rewards and return. TD(0) learns expected discounted return under a policy from sampled transitions. Write V(s) for the current value estimate, r for the reward and s' for the next state. The target is r + gamma * V(s'), where gamma is the discount. Bootstrapping means using an estimate inside this target. At an episode's terminal state, the remaining return is zero, so the target is just r.
In tabular TD(0), update V(s) to V(s) + alpha * (target - V(s)), where 0 < alpha <= 1 is the learning rate. Only that table entry changes. Read all target values before updating, including on a self-transition. The target minus the old value is the TD error. The next estimate need not be more accurate than the current one. Targets can contain estimation error and random noise, so one update need not improve accuracy.
Suppose the old value is 4, reward is 2, gamma is 0.5 and the nonterminal next value is 12. The target is 2 + 0.5 * 12 = 8. With alpha 0.25, the change is 0.25 * (8 - 4) = 1. Add the change to the old value: the new estimate is 5.
Q(s,a) estimates return for a state-action pair. Tabular Q-learning uses target = r + gamma * max_b Q(s',b), then Q(s,a) = Q(s,a) + alpha * (target - Q(s,a)). At a terminal next state, use target = r. Read all target values before updating. The behavior policy collects data. The target uses a maximum over next actions, not the next behavior action. This difference makes Q-learning off-policy.
Start with Q(s,a) = 3, alpha 0.5 and gamma 0.5. A reward 2 leads to next action values 6 and 2. The target is 2 + 0.5 * 6 = 5, even if behavior next chooses the action valued 2. Update to 3 + 0.5 * (5 - 3) = 4. Later, update the same pair from a terminal transition with reward 10. Its target is 10, so the new value is 4 + 0.5 * (10 - 4) = 7.
For a finite, stationary MDP with bounded rewards and 0 <= gamma < 1, tabular Q-learning converges to optimal action values under standard sampling and step-size conditions. Every state-action pair must be sampled infinitely often. For each pair, step sizes must have an infinite sum but a finite sum of squares. Exploration helps supply these visits. A max target alone is not a convergence guarantee.
With a function approximator, shared weights can make one update change predictions for several states or actions. Combining off-policy learning, bootstrapping and function approximation can amplify errors and cause divergence. Divergence is possible, not automatic. Growing estimates do not identify the cause by themselves. Check step sizes, reward scale, sampling and the update implementation.
TD targets reward plus discounted next value. Q-learning uses a maximum next value. Update from the old estimate; use reward alone at a terminal state. Convergence and stability need conditions.
Lesson, questions and flashcards written for this dataset.
2 · Watch
به انگلیسیTake it off screen
Where it sits
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.