def eps_greedy(q, s):
"""The eps-greedy policy of @def-eps-greedy at s, for the two actions here."""
g = int(q[s, 1] > q[s, 0])
return 1 - g if RNG.random() < EPS / 2 else g3 Temporal Difference Learning, Sarsa, and Q-learning
\[ \newcommand{\E}{\mathbb{E}} \newcommand{\R}{\mathbb{R}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\BR}{\operatorname{BR}} \newcommand{\eps}{\varepsilon} \newcommand{\given}{\,\vert\,} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\sm}{\setminus} \newcommand{\defeq}{\equiv} \]
Monte Carlo was the first model-free method. Temporal difference (TD) learning is the second, and it improves on Monte Carlo along the one axis Chapter 2 could not: it does not wait. Where MC Basic must run an episode to its end before it learns anything, TD updates after every single transition. This chapter builds that idea three times over, for state values, for action values under a fixed policy (Sarsa), and for optimal action values directly (Q-learning), and then removes the assumption that has been quietly holding since Chapter 1, that values can be stored in a table.
NoteSource:
Ben Moll’s RL lecture slides, Lecture 3.
3.1 Incremental versus episodic learning
The distinction is worth naming precisely, because it is the whole difference between this chapter and the last.
Chapter 2’s policy evaluation step was Equation 2.7, the average return over \(N\) episodes. Written as a running average in the manner of Equation 2.8, the \(j\)-th update is
\[ q_{\pi_{k}}^{j+1}(s,a)=q_{\pi_{k}}^{j}(s,a)+\frac{1}{j}\left[\sum_{t=0}^{T}\gamma^{t}r(s_{t}^{j},a_{t}^{j})-q_{\pi_{k}}^{j}(s,a)\right]. \tag{3.1}\]
The bracket contains a whole episode’s realized return, so nothing can be updated until \(t\) has run from \(0\) to \(T\). This chapter instead develops algorithms of the form
\[ q_{t+1}(s_{t},a_{t})=q_{t}(s_{t},a_{t})+\alpha_{t}\times(\text{something available at time } t), \tag{3.2}\]
where \(q_{t}\) is the time-\(t\) estimate of \(q_{\pi_{k}}\).
Definition 3.1 (Incremental and episodic learning) An algorithm is incremental if it updates in real time, at every transition, as in Equation 3.2. It is episodic (or non-incremental) if it must wait for an episode to finish, as in Equation 3.1.
WarningA terminology trap
Sutton and Barto call this same distinction online versus offline. That vocabulary is best avoided here, because “offline RL” has since come to mean something else entirely: learning from a fixed, previously collected dataset with no further interaction. Incremental and episodic are unambiguous.
The distinction outlives the tabular setting. The second half of this chapter writes updates to a parameter vector \(w\) rather than to a table, and the same question applies: does \(w\) move at every step, or only at the end of an episode? Chapter 4 will find both, with REINFORCE episodic and actor-critic incremental.
3.2 TD learning of state values
Start with the easier problem: estimate \(v_{\pi}\) for a fixed policy \(\pi\), with no improvement step. Write \(v_{t}(s)\) for the time-\(t\) estimate of \(v_{\pi}(s)\).
NoteAlgorithm: TD learning of state values
Given experience \(\{(s_{t},r_{t+1},s_{t+1})\}_{t}\) generated by following \(\pi\), at each \(t=0,1,2,\dots\)
\[ v_{t+1}(s_{t})=v_{t}(s_{t})+\alpha_{t}(s_{t})\big[\,r_{t+1}+\gamma v_{t}(s_{t+1})-v_{t}(s_{t})\,\big], \tag{3.3}\]
\[ v_{t+1}(s)=v_{t}(s)\qquad\text{for all } s\neq s_{t}. \tag{3.4}\]
Equation 3.4 says only the state just visited is touched; every other entry of the table is left alone. It is usually left implicit, but it matters: TD learning is a local update, and the fact that visiting one state teaches you nothing about any other is exactly the weakness that function approximation will fix at the end of this chapter.
Annotating Equation 3.3 names its parts:
\[ \underbrace{v_{t+1}(s_{t})}_{\text{new estimate}} =\underbrace{v_{t}(s_{t})}_{\text{current estimate}} +\alpha_{t}(s_{t})\Big[\underbrace{\overbrace{r_{t+1}+\gamma v_{t}(s_{t+1})}^{\text{TD target }\bar{v}_{t}}-v_{t}(s_{t})}_{\text{TD error }\delta_{t}}\Big]. \tag{3.5}\]
Definition 3.2 (TD target and TD error) \[ \bar{v}_{t}\defeq r_{t+1}+\gamma v_{t}(s_{t+1}), \qquad \delta_{t}\defeq \bar{v}_{t}-v_{t}(s_{t}). \]
This is Equation 1.3 from Chapter 1, now with the names attached and the learning rate allowed to depend on the state.
Why \(\bar{v}_{t}\) deserves the name “target”
Because the algorithm provably moves \(v(s_{t})\) toward it.
NoteDerivation: the update contracts the gap to the target
Rewrite Equation 3.3 in terms of \(\bar{v}_{t}\) and subtract \(\bar{v}_{t}\) from both sides: \[ \begin{aligned} v_{t+1}(s_{t})&=v_{t}(s_{t})+\alpha_{t}(s_{t})\big[\bar{v}_{t}-v_{t}(s_{t})\big]\\ \implies\quad v_{t+1}(s_{t})-\bar{v}_{t}&=v_{t}(s_{t})-\bar{v}_{t}+\alpha_{t}(s_{t})\big[\bar{v}_{t}-v_{t}(s_{t})\big]\\ \implies\quad v_{t+1}(s_{t})-\bar{v}_{t}&=\big[1-\alpha_{t}(s_{t})\big]\big[v_{t}(s_{t})-\bar{v}_{t}\big]\\ \implies\quad \big|v_{t+1}(s_{t})-\bar{v}_{t}\big|&=\big|1-\alpha_{t}(s_{t})\big|\,\big|v_{t}(s_{t})-\bar{v}_{t}\big| . \end{aligned} \] By the standing assumption \(\alpha_{t}(s_{t})\in(0,1)\) we have \(0<1-\alpha_{t}(s_{t})<1\), and therefore \[ \big|v_{t+1}(s_{t})-\bar{v}_{t}\big|\leq\big|v_{t}(s_{t})-\bar{v}_{t}\big| . \]
Each update never increases the distance to \(\bar{v}_{t}\), and strictly shrinks it whenever \(v_{t}(s_{t})\neq\bar{v}_{t}\). (The assumption \(\alpha_{t}<1\) is doing real work: at \(\alpha_{t}>2\) the factor \(|1-\alpha_{t}|\) exceeds one and the gap would grow.) The target moves, because it is built from \(v_{t}\) itself, but at every instant the estimate is being pulled toward it.
Convergence
Theorem 3.1 (Convergence of TD learning) Assume \(\gamma\in(0,1)\), that \(\mathcal{S}\) is finite, that rewards are bounded, and that \(\alpha_{t}(s)\in(0,1)\) for every \(t\) and \(s\). Then under the TD algorithm Equation 3.3, \(v_{t}(s)\) converges with probability 1 to \(v_{\pi}(s)\) for all \(s\in\mathcal{S}\) as \(t\to\infty\), provided \[ \sum_{t}\alpha_{t}(s)=\infty \qquad\text{and}\qquad \sum_{t}\alpha_{t}^{2}(s)<\infty \qquad\text{for all } s\in\mathcal{S}. \]
These are the Robbins-Monro conditions of Theorem 2.1, now required to hold state by state, and that qualifier carries the content.
Proving it needs a variant of Theorem 2.2, not a generalization of it. The variant handles many variables at once, one per state, and it trades the zero-mean noise requirement for a weaker one, that the bias be bounded by the current error; in exchange it adds the requirement \(\E[\beta_{k}]\leq\E[\alpha_{k}]\), which the Chapter 2 form does not impose. Neither theorem contains the other, and the Robbins-Monro corollary in Chapter 2 uses the Chapter 2 form. Bootstrapping guarantees the latter: the TD target is built from \(v_{t}\), so it is biased by exactly as much as \(v_{t}\) is wrong.
Theorem 3.2 (Dvoretzky, multi-variable form) Let \(\mathcal{S}\) be a finite index set. For the stochastic process \[ \Delta_{k+1}(s)=\big(1-\alpha_{k}(s)\big)\Delta_{k}(s)+\beta_{k}(s)\eta_{k}(s), \tag{3.6}\] \(\Delta_{k}(s)\) converges to zero almost surely for every \(s\in\mathcal{S}\) provided that, for every \(s\in\mathcal{S}\),
- \(\sum_{k}\alpha_{k}(s)=\infty\), \(\sum_{k}\alpha_{k}^{2}(s)<\infty\), \(\sum_{k}\beta_{k}^{2}(s)<\infty\), and \(\E[\beta_{k}(s)\given\mathcal{H}_{k}]\leq\E[\alpha_{k}(s)\given\mathcal{H}_{k}]\), uniformly almost surely;
- \(\big\|\E[\eta_{k}(s)\given\mathcal{H}_{k}]\big\|_{\infty}\leq\gamma\|\Delta_{k}\|_{\infty}\) for some \(\gamma\in(0,1)\);
- \(\operatorname{var}[\eta_{k}(s)\given\mathcal{H}_{k}]\leq C\big(1+\|\Delta_{k}\|_{\infty}\big)^{2}\) for a constant \(C\),
where \(\|x(s)\|_{\infty}\defeq\max_{s\in\mathcal{S}}|x(s)|\) is the maximum over the index set.
Tip
Condition 2 is the one that matters. Theorem 2.2 demanded unbiased noise; here the bias may be nonzero but must be a strict contraction of the current error, shrinking it by a factor \(\gamma<1\). In the proof below, \(\gamma\) turns out to be the discount factor, which is why discounting is not a modelling convenience here but the thing that makes bootstrapping converge at all.
NoteProof of the convergence of TD learning
Fix an arbitrary state \(s\in\mathcal{S}\) and define the estimation error \[ \Delta_{t}(s)\defeq v_{t}(s)-v_{\pi}(s). \]
Step 1: put the algorithm in the form Equation 3.6. When \(s=s_{t}\), subtract \(v_{\pi}(s)\) from both sides of Equation 3.3: \[ \Delta_{t+1}(s)=\big(1-\alpha_{t}(s)\big)\Delta_{t}(s)+\alpha_{t}(s)\underbrace{\big[r_{t+1}+\gamma v_{t}(s_{t+1})-v_{\pi}(s)\big]}_{\eta_{t}(s)} . \] When \(s\neq s_{t}\), Equation 3.4 gives \(\Delta_{t+1}(s)=\Delta_{t}(s)\), which is the same expression with \(\alpha_{t}(s)=0\) and \(\eta_{t}(s)=0\). So regardless of which state was visited, \[ \Delta_{t+1}(s)=\big(1-\alpha_{t}(s)\big)\Delta_{t}(s)+\alpha_{t}(s)\eta_{t}(s), \] which is Equation 3.6 with \(\beta_{t}(s)=\alpha_{t}(s)\), so the requirement \(\E[\beta_{t}]\leq\E[\alpha_{t}]\) holds with equality.
Step 2: condition 1. This is precisely the hypothesis of Theorem 3.1.
Step 3: condition 2, the contraction. Everything here stays conditional on \(\mathcal{H}_{t}\). That matters: \(\eta_{t}(s)\) contains \(v_{t}\), which is a function of the whole past trajectory and so is emphatically history-dependent. What the Markov property gives is narrower and is all we need. Conditioning on \(\mathcal{H}_{t}\) fixes both the table \(v_{t}\) and the current state \(s_{t}\), so the only randomness left in \(\eta_{t}(s)\) is the pair \((r_{t+1},s_{t+1})\), whose law depends on \(s_{t}\) alone. For \(s\neq s_{t}\) we have \(\eta_{t}(s)=0\) and the bound is trivial. For \(s=s_{t}\), \[ \E[\eta_{t}(s)\given\mathcal{H}_{t}]=\E\big[r_{t+1}+\gamma v_{t}(s_{t+1})\given\mathcal{H}_{t}\big]-v_{\pi}(s_{t}). \] Now use the Bellman equation for \(v_{\pi}\), which says \(v_{\pi}(s_{t})=\E[r_{t+1}+\gamma v_{\pi}(s_{t+1})\given s_{t}]\). Subtracting, the reward terms cancel exactly and only the value gap survives: \[ \E[\eta_{t}(s)\given\mathcal{H}_{t}]=\gamma\,\E\big[v_{t}(s_{t+1})-v_{\pi}(s_{t+1})\given\mathcal{H}_{t}\big] =\gamma\sum_{s'\in\mathcal{S}}p(s'\given s_{t})\big[v_{t}(s')-v_{\pi}(s')\big], \] where \(v_{t}\) passes outside the expectation because \(\mathcal{H}_{t}\) determines it. Bound the sum by its largest term, using that \(p(\cdot\given s_{t})\) is a probability distribution and therefore sums to one: \[ \big|\E[\eta_{t}(s)\given\mathcal{H}_{t}]\big| \leq\gamma\sum_{s'}p(s'\given s_{t})\max_{s'}\big|v_{t}(s')-v_{\pi}(s')\big| =\gamma\max_{s'}\big|v_{t}(s')-v_{\pi}(s')\big| =\gamma\|\Delta_{t}\|_{\infty}. \] This holds whether or not \(s=s_{t}\), so \(\|\E[\eta_{t}(s)\given\mathcal{H}_{t}]\|_{\infty}\leq\gamma\|\Delta_{t}\|_{\infty}\), with \(\gamma\in(0,1)\) the discount factor. Note both sides are \(\mathcal{H}_{t}\)-measurable random variables, which is exactly the form condition 2 of Theorem 3.2 asks for.
Step 4: condition 3. For \(s\neq s_{t}\), \(\operatorname{var}[\eta_{t}(s)\given\mathcal{H}_{t}]=0\). For \(s=s_{t}\), the constant \(v_{\pi}(s_{t})\) drops out of the variance, leaving \(\operatorname{var}[r_{t+1}+\gamma v_{t}(s_{t+1})\given s_{t}]\), which is bounded by a constant multiple of \((1+\|\Delta_{t}\|_{\infty})^{2}\) because the reward is bounded and \(v_{t}\) differs from the fixed \(v_{\pi}\) by at most \(\|\Delta_{t}\|_{\infty}\).
All three conditions hold, so Theorem 3.2 gives \(\Delta_{t}(s)\to0\) almost surely for every \(s\). \(\square\)
Important
The proof isolates why bootstrapping is safe. The TD target is not an unbiased estimate of \(v_{\pi}(s_{t})\): it is contaminated by the current error at the next state. But Step 3 shows that contamination enters multiplied by \(\gamma\). Each update therefore replaces the error at \(s_{t}\) with at most \(\gamma\) times the worst error anywhere, and iterating a factor \(\gamma<1\) drives it to zero. Undiscounted problems, \(\gamma=1\), lose exactly this argument.
TipWhat the two conditions demand here
Recall from Equation 3.4 that \(\alpha_{t}(s)>0\) only when \(s_{t}=s\), and \(\alpha_{t}(s)=0\) otherwise. So:
- \(\sum_{t}\alpha_{t}(s)=\infty\) for every \(s\) can only hold if every state is visited infinitely often. This is not a condition on the step size at all: it is an exploration requirement in disguise, and it is why \(\eps\)-greedy policies from Definition 2.2 reappear the moment we start improving the policy.
- \(\sum_{t}\alpha_{t}^{2}(s)<\infty\) requires \(\alpha_{t}\to0\). In practice \(\alpha\) is usually a small constant, which violates it. As Figure 2.2 showed, the estimate then does not converge to a point but fluctuates around the truth, and one settles for convergence in an expectation sense.
TD against Monte Carlo
Both are model-free; they differ in what they wait for and what they assume.
| TD / Sarsa | Monte Carlo | |
|---|---|---|
| Timing | incremental: updates immediately after each reward | episodic: waits until an episode is complete |
| Task type | handles episodic and continuing tasks | needs terminal states, so episodic tasks only |
| Bootstrapping | yes: the update uses the previous estimate of the same value, so it needs an initial guess | no: estimates values directly from returns, no initial guess needed |
| Variance | low: few random variables per update (Sarsa needs only \(r_{t+1},s_{t+1},a_{t+1}\)) | high: estimating \(q_{\pi}(s_{t},a_{t})\) requires samples of \(r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+\cdots\), and with episodes of length \(L\) there are \(|\mathcal{A}|^{L}\) possible episodes |
3.3 Sarsa: TD learning of action values
TD as stated estimates state values, and Chapter 2 established why that is not enough: turning \(v\) into a decision requires the model. To search for optimal policies we need action values. The fix is entirely mechanical.
NoteAlgorithm: Sarsa
Given experience \(\{(s_{t},a_{t},r_{t+1},s_{t+1},a_{t+1})\}_{t}\) generated by following \(\pi\),
\[ q_{t+1}(s_{t},a_{t})=q_{t}(s_{t},a_{t})+\alpha_{t}(s_{t},a_{t})\big[\,r_{t+1}+\gamma q_{t}(s_{t+1},a_{t+1})-q_{t}(s_{t},a_{t})\,\big], \tag{3.7}\]
with \(q_{t+1}(s,a)=q_{t}(s,a)\) for all \((s,a)\neq(s_{t},a_{t})\).
TipWhere the code is
There is no separate listing for Equation 3.7. Sarsa and Q-learning share one loop and part company on a single line, so the implementation is given once, with Q-learning below.
Three questions answer themselves from Equation 3.7.
Why the name? Each update consumes the quintuple \((s_{t},a_{t},r_{t+1},s_{t+1},a_{t+1})\): state, action, reward, state, action. Sarsa.
How does it relate to TD? Replace the state value \(v(s)\) in Equation 3.3 by the action value \(q(s,a)\) and you have Equation 3.7. Sarsa is the TD algorithm, in action-value form.
What does it solve, mathematically? Equation 3.7 is a stochastic approximation algorithm, in the sense of Theorem 2.1, for the equation
\[ q_{\pi}(s,a)=\E\big[R+\gamma q_{\pi}(S',A')\ \given\ s,a\big], \qquad\text{for all } s,a, \tag{3.8}\]
which is the action-value form of the policy-evaluation Bellman equation for the fixed policy \(\pi\): Equation 2.2 with the maximization over \(\pi\) removed.
The claim deserves a proof, because Equation 3.8 does not look like anything in Chapter 2. There is no sum over actions in it, and the policy \(\pi\) appears nowhere. Both are hiding inside the expectation.
NoteProof that the Sarsa fixed point is the Bellman equation
Write \(p(r\given s,a)\) for the distribution of the immediate reward and \(p(s'\given s,a)\) for the transition, both conditional on the pair \((s,a)\). Expanding the right-hand side of Equation 3.8 by the definition of expectation,
\[ \E\big[R+\gamma q_{\pi}(S',A')\given s,a\big] =\sum_{r}r\,p(r\given s,a) +\gamma\sum_{s'\in\mathcal{S}}\sum_{a'\in\mathcal{A}}q_{\pi}(s',a')\,p(s',a'\given s,a). \]
Linearity is doing the work in that split: each term is integrated against its own marginal, so nothing needs to be assumed about how \(R\) and \(S'\) are related. The first term is the expected immediate reward, which collapses to \(r(s,a)\) whenever the reward is a deterministic function of the pair, as it was in Chapters 1 and 2. The second term needs the joint law of the next state and the next action, and that is the one object here we have not met before.
Factor the joint. The chain rule is free: \[ p(s',a'\given s,a)=p(s'\given s,a)\,p(a'\given s',s,a). \] The second factor is where the policy enters. The agent produces \(a'\) by drawing from \(\pi(\cdot\given s')\), and \(\pi\) reads the current state and nothing else: not where the agent came from, not what it did to get there. So conditionally on \(s'\), the next action is independent of \((s,a)\), and \[ p(a'\given s',s,a)=p(a'\given s')=\pi(a'\given s'). \] That step is an assumption about the policy, not about the environment, and it is worth being clear about why it is legitimate. The pair \((s,a)\) certainly influences \(a'\), but only by determining which \(s'\) the agent lands in. Conditioning on \(s'\) closes that one channel, and there is no other, because a stationary Markov policy has no memory to route information through. This is the class of policies that has been in force since Definition 2.1. A history-dependent policy would break the step, and would break considerably more than the step: \(q\) would no longer be a function of \((s,a)\) alone, and there would be no table left to fill in.
Substitute and collect. Putting the factorization back and summing over \(a'\) first, \[ q_{\pi}(s,a)=\underbrace{\sum_{r}r\,p(r\given s,a)}_{\E[R\given s,a]} +\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\underbrace{\sum_{a'\in\mathcal{A}}\pi(a'\given s')\,q_{\pi}(s',a')}_{v_{\pi}(s')}, \] because the action value averaged against the policy at \(s'\) is by definition the state value there. Hence \[ q_{\pi}(s,a)=\E[R\given s,a]+\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\,v_{\pi}(s'), \] which is Equation 2.5, the model-based form of the action value.
And back to state values. Average that last display against \(\pi(a\given s)\) and use Definition 2.1: \[ v_{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(a\given s)\,q_{\pi}(s,a) =r_{\pi}(s)+\gamma\sum_{s'\in\mathcal{S}}p_{\pi}(s'\given s)\,v_{\pi}(s'), \] which is Equation 1.6, the policy-evaluation equation, written one state at a time. So Equation 3.8 and the state-value Bellman equation are one equation read at two resolutions: one entry per pair, or one entry per state. \(\square\)
Which is why the quintuple in the name is not an accident. Equation 3.8 sets \(q_{\pi}(s,a)\) equal to the mean of \(R+\gamma q_{\pi}(S',A')\), and the sample \((r_{t+1},s_{t+1},a_{t+1})\) is one draw of exactly those random variables. Sarsa averages the draws incrementally in the manner of Equation 2.8, bootstrapping the current \(q_{t}\) in for the unknown \(q_{\pi}\) inside the target.
Theorem 3.3 (Convergence of Sarsa) Under the same standing assumptions as Theorem 3.1 (\(\gamma\in(0,1)\), finite \(\mathcal{S}\) and \(\mathcal{A}\), bounded rewards, \(\alpha_{t}\in(0,1)\)), the Sarsa algorithm Equation 3.7 has \(q_{t}(s,a)\) converging with probability 1 to \(q_{\pi}(s,a)\) for all \((s,a)\) as \(t\to\infty\), provided \(\sum_{t}\alpha_{t}(s,a)=\infty\) and \(\sum_{t}\alpha_{t}^{2}(s,a)<\infty\) for all \((s,a)\).
The hypotheses read exactly as in Theorem 3.1 with one word changed: the Robbins-Monro conditions must now hold pair by pair rather than state by state. The conclusion changes in the same mechanical way, from the whole vector of state values to the whole table of action values. So does the proof, and it is worth showing precisely how rather than asserting it.
NoteProof of the convergence of Sarsa
Nothing new is needed. Sarsa is the TD algorithm with its index set enlarged from states to state-action pairs, so the proof of Theorem 3.1 carries over under a dictionary. Here are the substitutions, in the order that proof uses them.
The index set. Replace \(\mathcal{S}\) by \(\mathcal{S}\times\mathcal{A}\) everywhere. It is still finite, which is all Theorem 3.2 ever asked of it, and the norm becomes \(\|x\|_{\infty}=\max_{(s,a)}|x(s,a)|\), a maximum over pairs.
Step 1, the error process. In place of \(\Delta_{t}(s)\defeq v_{t}(s)-v_{\pi}(s)\), define \(\Delta_{t}(s,a)\defeq q_{t}(s,a)-q_{\pi}(s,a)\). Subtracting \(q_{\pi}(s,a)\) from Equation 3.7 when \((s,a)=(s_{t},a_{t})\) gives \[ \Delta_{t+1}(s,a)=\big(1-\alpha_{t}(s,a)\big)\Delta_{t}(s,a)+\alpha_{t}(s,a)\underbrace{\big[r_{t+1}+\gamma q_{t}(s_{t+1},a_{t+1})-q_{\pi}(s,a)\big]}_{\eta_{t}(s,a)}, \] and every other pair is left untouched, which is the same line with \(\alpha_{t}(s,a)=0\) and \(\eta_{t}(s,a)=0\). That is Equation 3.6 on the new index set, again with \(\beta_{t}=\alpha_{t}\).
Step 2, condition 1. The hypothesis of the theorem, now imposed on pairs.
Step 3, the contraction. This is the only step carrying any content. As before, once the pair is given, \(\eta_{t}(s,a)\) does not depend on the history, so \(\E[\eta_{t}(s,a)\given\mathcal{H}_{t}]=\E[\eta_{t}(s,a)]\), and the bound is trivial for pairs other than \((s_{t},a_{t})\). For \((s,a)=(s_{t},a_{t})\), \[ \E[\eta_{t}(s,a)]=\E\big[r_{t+1}+\gamma q_{t}(s_{t+1},a_{t+1})\given s_{t},a_{t}\big]-q_{\pi}(s_{t},a_{t}). \] The state-value proof subtracted the Bellman equation for \(v_{\pi}\) at this point. Subtract Equation 3.8 instead, which is exactly what the proof above licensed, and the reward terms cancel in the same way, leaving only the gap between estimate and truth at the next pair: \[ \E[\eta_{t}(s,a)]=\gamma\sum_{s'\in\mathcal{S}}\sum_{a'\in\mathcal{A}}p(s'\given s_{t},a_{t})\,\pi(a'\given s')\big[q_{t}(s',a')-q_{\pi}(s',a')\big]. \] The weights here are the factored joint \(p(s',a'\given s_{t},a_{t})\) from that same proof: non-negative, and summing to one over pairs. Bounding the sum by its largest term therefore works verbatim, \[ \big|\E[\eta_{t}(s,a)]\big|\leq\gamma\max_{(s',a')}\big|q_{t}(s',a')-q_{\pi}(s',a')\big|=\gamma\|\Delta_{t}\|_{\infty}, \] with \(\gamma\in(0,1)\) the discount factor once again supplying the contraction.
Step 4, the variance. Unchanged. The constant \(q_{\pi}(s,a)\) drops out of the variance, \(r_{t+1}\) is bounded, and \(q_{t}\) differs from the fixed \(q_{\pi}\) by at most \(\|\Delta_{t}\|_{\infty}\), so condition 3 holds for the same reason it did before.
All three conditions of Theorem 3.2 hold on the index set \(\mathcal{S}\times\mathcal{A}\), so \(\Delta_{t}(s,a)\to0\) almost surely for every pair. \(\square\)
WarningWhat the dictionary costs
The translation is free on the mathematics but not on the data. Since \(\alpha_{t}(s,a)>0\) only when \((s_{t},a_{t})=(s,a)\), requiring \(\sum_{t}\alpha_{t}(s,a)=\infty\) for every pair demands that every pair be visited infinitely often, and visiting every state infinitely often does not deliver that. A deterministic policy can tour all of \(\mathcal{S}\) forever while taking exactly one action in each state, leaving \(|\mathcal{S}|(|\mathcal{A}|-1)\) entries of the table with \(\alpha_{t}=0\) at every \(t\), frozen at their initial guesses. The requirement is stronger by a factor of \(|\mathcal{A}|\) in the number of things that must be sampled, and no greedy policy can meet it.
Note what this theorem does and does not deliver: it finds \(q_{\pi}\) for a given policy \(\pi\). It is a policy evaluation result. Getting an optimal policy requires pairing it with improvement.
Policy searching by Sarsa
The pairing is the Howard structure of Equation 2.3 once more, except that neither step waits for the other to finish. Evaluation takes one TD step, improvement acts on the result immediately, and the improved policy generates the next transition.
NoteAlgorithm: policy searching by Sarsa
For each episode: generate \(a_{0}\) at \(s_{0}\) following \(\pi_{0}(s_{0})\). Then for each \(t=0,1,2,\dots\) while \(s_{t}\) is not the target state:
Interact. Take \(a_{t}\), observe \(r_{t+1}\) and \(s_{t+1}\), and generate \(a_{t+1}\) following \(\pi_{t}(s_{t+1})\).
Update the \(q\)-value of \((s_{t},a_{t})\) by Equation 3.7.
Update the policy at \(s_{t}\) to be \(\eps\)-greedy with respect to the new \(q_{t+1}\), in the sense of Definition 2.2.
Set \(s_{t}\leftarrow s_{t+1}\), \(a_{t}\leftarrow a_{t+1}\).
NoteImplementation: eps-greedy action selection
Step 3 in code, for the two-action chain behind Figure 3.1. With \(|\mathcal{A}|=2\), Definition 2.2 puts \(1-\eps/2\) on the greedy action and \(\eps/2\) on the other, which is exactly what the coin flip below does; q is the table, g the index of its larger entry at s, and \(\eps=0.2\) throughout this chapter.
Tip
The \(\eps\)-greedy step is not a detail. Theorem 3.3 needs every pair \((s,a)\) visited infinitely often, and a greedy policy would starve every non-greedy action of data immediately. This is the exploration problem of Chapter 2 arriving exactly where it was promised.
3.4 Q-learning: TD learning of optimal action values
Sarsa estimates \(q_{\pi}\) for the policy currently being followed, and therefore must be combined with an improvement step. Q-learning skips the intermediary and estimates \(q^{*}\) directly.
NoteAlgorithm: Q-learning
\[ q_{t+1}(s_{t},a_{t})=q_{t}(s_{t},a_{t})+\alpha_{t}(s_{t},a_{t})\Big[\,r_{t+1}+\gamma\max_{a\in\mathcal{A}}q_{t}(s_{t+1},a)-q_{t}(s_{t},a_{t})\,\Big], \tag{3.9}\]
with \(q_{t+1}(s,a)=q_{t}(s,a)\) for all \((s,a)\neq(s_{t},a_{t})\).
NoteImplementation: Sarsa and Q-learning, one loop
Both algorithms, in the one loop that produces Figure 3.1. step(s, a) returns the next state, the realized reward, and whether the episode ended; the chain has N_DEC = 4 decision states and \(\gamma=0.9\); and use_max is where the two part company. It appears twice. First it selects the target: either the \(\max\) of Equation 3.9 or the value of the action eps_greedy actually drew, Equation 3.7. Second, at the bottom of the loop, it decides whether the action just used in the target is the one actually taken next, which is on-policy Sarsa, or is discarded in favour of a fresh draw, which is off-policy Q-learning. That second branch is where on-policy versus off-policy physically lives. Everything else, the visit-count step size \(\alpha_{t}=1/n(s,a)\) that supplies the Robbins-Monro schedule of Theorem 3.3, the uniform starting states that hold the two algorithms’ visitation equal, and the update itself, is shared verbatim. The two lines that record qs and vals at the episode counts listed in checks are bookkeeping for the figure and play no part in the algorithm.
def run(use_max, n_ep, checks):
"""One learning run; `use_max` selects the TD target of @tbl-sarsa-q.
use_max=True is Q-learning @eq-qlearning, whose target maxes over the table.
use_max=False is Sarsa @eq-sarsa, whose target uses the action a_{t+1} that the
eps-greedy behavior policy actually draws. Everything else is shared.
Episodes begin at a uniformly drawn decision state. That exploring-starts device
holds the two algorithms' visitation equal, so the difference the figure shows
cannot be an artifact of one of them wandering somewhere the other does not: the
only thing left that differs is the target. Step sizes are 1/n(s, a), the
Robbins-Monro schedule both convergence theorems ask for.
"""
q = RNG.normal(0.0, 1e-3, (N_DEC, 2)) # jitter only breaks the initial ties
n = np.zeros((N_DEC, 2)) # visit counts, so alpha = 1 / n(s, a)
wanted = set(checks.tolist())
qs, vals = [], []
for ep in range(1, n_ep + 1):
s = int(RNG.integers(N_DEC)) # uniform state starts, not exploring starts:
# the first action is still drawn eps-greedily
a = eps_greedy(q, s)
while True:
s2, r, done = step(s, a)
if done:
target = r
elif use_max:
target = r + GAMMA * q[s2].max() # Q-learning: max over the table
else:
a2 = eps_greedy(q, s2) # Sarsa: the action drawn next,
target = r + GAMMA * q[s2, a2] # read before the update
n[s, a] += 1
q[s, a] += (target - q[s, a]) / n[s, a]
if done:
break
s, a = s2, (eps_greedy(q, s2) if use_max else a2)
if ep in wanted:
qs.append(q.copy())
vals.append(policy_value(q[:, 1] > q[:, 0]))
return np.array(qs), np.array(vals)One boolean, read in two places, is the entire difference between an on-policy and an off-policy algorithm, and between converging to \(q_{\pi}\) and converging to \(q^{*}\).
Set Equation 3.9 beside Equation 3.7 and exactly one thing has changed, the TD target:
| TD target | |
|---|---|
| Sarsa | \(r_{t+1}+\gamma\,q_{t}(s_{t+1},a_{t+1})\) |
| Q-learning | \(r_{t+1}+\gamma\,\max_{a\in\mathcal{A}}q_{t}(s_{t+1},a)\) |
That single substitution changes what equation the algorithm solves. Sarsa is stochastic approximation on the Bellman equation Equation 3.8; Q-learning is stochastic approximation on the Bellman optimality equation,
\[ q(s,a)=\E\Big[R+\gamma\max_{a'\in\mathcal{A}}q(S',a')\ \given\ s,a\Big], \qquad\text{for all } s,a, \tag{3.10}\]
whose solution is \(q^{*}\). So Q-learning estimates the optimal action values directly, and needs no separate policy improvement step at all.
Calling Equation 3.10 an optimality equation is a claim worth checking, because it does not look like one. Its only maximization sits inside the expectation, over the next action; nothing is maximized over policies, and the unknown carries no \(\pi\) subscript at all.
NoteProof that the Q-learning fixed point is the Bellman optimality equation
Step 1: expand the expectation. Exactly as for Sarsa, write the right-hand side as sums against the conditional distributions of the reward and of the next state. What differs is that the next action is not random: the \(\max\) has already chosen it, so only \(r\) and \(s'\) are integrated out and no policy is needed to average over \(a'\), \[ q(s,a)=\sum_{r}r\,p(r\given s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\max_{a'\in\mathcal{A}}q(s',a'). \] The off-policy character of Q-learning is already visible: no \(\pi\) entered the derivation, because no action had to be drawn.
Step 2: maximize both sides over the first action. Both sides are functions of \(a\) and \(\mathcal{A}\) is finite, so the maximum exists and \[ \max_{a\in\mathcal{A}}q(s,a)=\max_{a\in\mathcal{A}}\Big\{\sum_{r}r\,p(r\given s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\max_{a'\in\mathcal{A}}q(s',a')\Big\}. \]
Step 3: name the maximized value. Define \[ v(s)\defeq\max_{a\in\mathcal{A}}q(s,a). \] The inner maximum on the right is that same definition evaluated at \(s'\), so it is \(v(s')\), and the left-hand side is \(v(s)\): \[ v(s)=\max_{a\in\mathcal{A}}\Big\{\sum_{r}r\,p(r\given s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\,v(s')\Big\}, \] which is Equation 1.4, in the \(\gamma\) dialect and with the expected reward written as a sum because rewards here are random.
Step 4: maximizing over actions is maximizing over policies. Chapter 2 wrote the optimality equation with the maximum taken over stochastic policies, Equation 2.1, so the two forms still have to be reconciled. Abbreviate the bracket in Step 3 as \[ f(a)\defeq\sum_{r}r\,p(r\given s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\given s,a)\,v(s'). \] For any distribution \(\pi(\cdot\given s)\) on the finite set \(\mathcal{A}\), \[ \sum_{a\in\mathcal{A}}\pi(a\given s)f(a)\leq\sum_{a\in\mathcal{A}}\pi(a\given s)\max_{b\in\mathcal{A}}f(b)=\max_{b\in\mathcal{A}}f(b), \] since a weighted average of finitely many numbers cannot exceed the largest of them, the weights summing to one. The bound is attained: finiteness of \(\mathcal{A}\) makes \(\argmax_{a}f(a)\) nonempty, and putting all the mass on one of its elements turns the average into the maximum. Hence \[ \max_{\pi}\sum_{a\in\mathcal{A}}\pi(a\given s)f(a)=\max_{a\in\mathcal{A}}f(a), \] the maximum over the simplex of distributions being attained at a vertex, that is, at a point mass. Step 3 is therefore Equation 2.1, and Equation 3.10 is the Bellman optimality equation written one state-action pair at a time. \(\square\)
Two consequences are worth stating. Randomizing never pays: the maximum over distributions is attained at a point mass, so an optimal policy may always be taken deterministic, and \(\pi(s)=\argmax_{a}q^{*}(s,a)\) reads it off the table by comparison alone, with no model and no separate improvement step. The \(\eps\)-greedy policy in the algorithm below is thus about collecting data, not about any value in randomizing. And the correspondence runs both ways: define \(q\) from a solution \(v\) of Equation 1.4 by the one-step formula of Step 1, and Step 3 gives \(\max_{a}q(s,a)=v(s)\), which substituted back shows that \(q\) solves Equation 3.10. The two fixed points determine each other, so the object Q-learning converges to is \(q^{*}\), with \(v^{*}(s)=\max_{a}q^{*}(s,a)\).
Why Q-learning is off-policy
Look at what each update consumes. Sarsa Equation 3.7 needs \(a_{t+1}\), the action the current policy will actually take next. Q-learning Equation 3.9 does not: the \(\max\) is taken over the table, not over what happens. Its update needs only \((s_{t},a_{t},r_{t+1},s_{t+1})\).
Definition 3.3 (On-policy and off-policy) An algorithm is on-policy if the data must be generated by the policy being learned. It is off-policy if the data may come from any behavior policy, while the target policy being learned is a different one.
Sarsa is on-policy: \(a_{t+1}\) ties the update to the policy in force. Q-learning is off-policy, which is why it can learn the optimal policy from data collected by an arbitrarily exploratory behavior policy, or from a log recorded long ago.
NoteAlgorithm: policy searching by Q-learning
For each episode, for each \(t=0,1,2,\dots\) while \(s_{t}\) is not the target state:
Interact. Generate \(a_{t}\) following \(\pi_{t}(s_{t})\); observe \(r_{t+1}\) and \(s_{t+1}\).
Update the \(q\)-value of \((s_{t},a_{t})\) by Equation 3.9.
Update the policy at \(s_{t}\) to be \(\eps\)-greedy with respect to \(q_{t+1}\).
Tip
Compare this with policy searching by Sarsa: there is no \(a_{t+1}\) anywhere. This version still generates its own data with an \(\eps\)-greedy behavior policy, which makes it a convenient but not a fully off-policy implementation. A fully off-policy version draws all its data from a fixed exploratory behavior policy and never updates it.
240 runs of each algorithm on the ledge chain, scored two ways
n_runs, n_ep = 240, 1200
checks = np.unique(np.round(np.logspace(0, np.log10(n_ep), 44)).astype(int))
algos = (("qlearning", True, COL["vermilion"]), ("sarsa", False, COL["sky"]))
ref = {name: reference_q(0.0 if use_max else EPS) for name, use_max, _ in algos}
err = {name: np.zeros(len(checks)) for name, _, _ in algos}
val = {name: np.zeros(len(checks)) for name, _, _ in algos}
for _ in range(n_runs):
for name, use_max, _ in algos:
qs, vs = run(use_max, n_ep, checks)
err[name] += np.sqrt(np.mean((qs - ref[name]) ** 2, axis=(1, 2)))
val[name] += vs
for name, _, _ in algos:
# as a share of the gap the run started from, so the two rates are comparable
err[name] /= n_runs * np.sqrt(np.mean(ref[name] ** 2))
val[name] /= n_runs
# The figure's two claims, checked on the runs it plots. Q-learning must end nearer the
# values its own equation defines AND imply the better greedy policy; Sarsa settles
# strictly below because it prices in the exploration it actually does.
assert err["qlearning"][-1] < err["sarsa"][-1]
assert val["qlearning"][-1] > val["sarsa"][-1] + 1.0
fig, (axL, axR) = plt.subplots(1, 2, figsize=(9.4, 3.9))
trim(axL), trim(axR)
# --- left: distance to each algorithm's own fixed point ------------------
for name, _, colour in algos:
axL.loglog(checks, err[name], color=colour, lw=2.0, zorder=4)
lo = err["qlearning"][-1]
axL.set_xlim(1, n_ep)
axL.set_ylim(lo * 0.5, 1.3) # room under the curves for the two direct labels
axL.set_xlabel("episodes")
axL.set_ylabel("share of the initial error left")
label_at(axL, 1.6, lo * 2.4, r"Sarsa $\to q_{\pi}$", color=COL["sky"], fontsize=9.5)
label_at(axL, 1.6, lo * 0.8, r"Q-learning $\to q^{*}$",
color=COL["vermilion"], fontsize=9.5)
axL.set_title("Each settles on its own fixed point, Q-learning sooner", fontsize=11)
# --- right: value of the greedy policy each one implies ------------------
# The reference lines stop at the last episode, leaving the right margin clear for
# their tags rather than running a dashed rule straight through the text.
v_star, v_safe = policy_value([False] * N_DEC), R_SAFE
for v in (v_star, v_safe):
axR.plot([0, n_ep], [v, v], color=GREY, lw=0.9, ls="--", zorder=2)
for name, _, colour in algos:
axR.plot(checks, val[name], color=colour, lw=2.0, zorder=4)
axR.set_xlim(0, n_ep * 1.42) # headroom on the right for the two reference tags
axR.set_xticks([0, 400, 800, 1200]) # the headroom carries tags, not data
axR.set_xlabel("episodes")
axR.set_ylabel(r"value at $s_{0}$ of the implied greedy policy")
label_at(axR, n_ep * 1.04, v_star, r"$v^{*}(s_{0})$: the ledge",
color=GREY, fontsize=8.5)
label_at(axR, n_ep * 1.04, v_safe, "the safe route", color=GREY, fontsize=8.5)
label_at(axR, n_ep * 0.42, 6.25, "Q-learning", color=COL["vermilion"], fontsize=9.5)
label_at(axR, n_ep * 0.42, 4.05, "Sarsa", color=COL["sky"], fontsize=9.5)
axR.set_title("Sarsa keeps the safe route it can afford to explore", fontsize=11)
fig.tight_layout()
plt.show()
3.5 TD learning with function approximation
Everything so far has stored values in a table: one entry per state, or one per state-action pair. Equation 3.4 is the clearest statement of what that costs, since visiting a state updates that state and nothing else.
Tables are intuitive and easy to analyze. They fail on two counts:
- Storage. A table has \(|\mathcal{S}|\) or \(|\mathcal{S}|\times|\mathcal{A}|\) entries. For large or continuous state spaces this is hopeless, and in economics the state space is routinely continuous.
- Generalization. Nothing learned at \(s\) transfers to a nearby \(s'\). Every state must be visited, many times, on its own account.
Values as parameterized functions
Replace the table with a function
\[ \hat{v}(s,w)\approx v_{\pi}(s), \qquad w\in\R^{m}, \tag{3.11}\]
where \(m\) can be far smaller than \(|\mathcal{S}|\). The change is in how a value is accessed and assigned: instead of reading and writing one cell, we evaluate a function and adjust its parameters, which moves the estimate at many states at once. That is generalization, purchased directly.
Example 3.1 (Fitting a line) Suppose the states \(s_{1},\dots,s_{|\mathcal{S}|}\) are one-dimensional and \(|\mathcal{S}|\) is very large. The crudest approximation is a straight line: \[ \hat{v}(s,w)=as+b=\underbrace{[\,s\ \ 1\,]}_{\phi^{\!\top}(s)}\underbrace{\begin{bmatrix}a\\ b\end{bmatrix}}_{w}=\phi^{\!\top}(s)\,w . \] Here \(w\) is the parameter vector, \(\phi(s)\) is the feature vector of \(s\), and \(\hat{v}\) is linear in \(w\). Two numbers now stand in for \(|\mathcal{S}|\) of them.
That example is deliberately crude, and it is worth seeing what a feature map actually buys before the algorithms that fit one arrive. Figure 3.2 sets a table, the line above, and a slightly richer set of features against the same value function, and then visits a single state to see what each of them does to the rest.
Fitting a 200-state value function with six numbers
# A 200-state chain on [0, 1]. The policy induces a reflecting random walk, so v_pi
# solves (I - gamma P) v = r exactly: nothing below is estimated, this is the object
# the algorithms of this chapter are chasing and the object a table has to store.
N, GAMMA = 200, 0.98
S = np.linspace(0.0, 1.0, N)
i = np.arange(N)
P = np.zeros((N, N))
np.add.at(P, (i, np.clip(i - 1, 0, N - 1)), 0.5)
np.add.at(P, (i, np.clip(i + 1, 0, N - 1)), 0.5)
R = (1.0 - GAMMA) * (8.0 * np.exp(-0.5 * ((S - 0.30) / 0.13) ** 2)
- 4.0 * np.exp(-0.5 * ((S - 0.78) / 0.15) ** 2)
+ 1.6 * S + 0.4)
V = np.linalg.solve(np.eye(N) - GAMMA * P, R)
# Two feature maps. PHI_L is @exm-linear-fa verbatim, so w is two numbers; PHI_R
# spreads six bumps across the state space, so w is six.
CENTRES, WIDTH = np.linspace(0.05, 0.95, 6), 0.13
PHI_L = np.stack([S, np.ones_like(S)], axis=-1)
PHI_R = np.exp(-0.5 * ((S[:, None] - CENTRES) / WIDTH) ** 2)
# Least squares against v_pi under a uniform state distribution is exactly the
# minimizer of @eq-fa-objective, so these are the two families at their best.
fit_l = PHI_L @ np.linalg.lstsq(PHI_L, V, rcond=None)[0]
fit_r = PHI_R @ np.linalg.lstsq(PHI_R, V, rcond=None)[0]
# One update at one visited state. w starts at zero, so the estimate starts flat and
# the error at s_t is v_pi(s_t) itself. The step size is the one that lands the
# estimate at s_t exactly on that target, which is what a table with alpha = 1 does
# too. All three therefore move by the SAME amount at s_t, and differ only elsewhere.
IT = int(np.argmin(np.abs(S - 0.32)))
ST, TARGET = S[IT], V[IT]
up_l = TARGET * (PHI_L @ PHI_L[IT]) / (PHI_L[IT] @ PHI_L[IT])
up_r = TARGET * (PHI_R @ PHI_R[IT]) / (PHI_R[IT] @ PHI_R[IT])
# The two claims the figure makes, checked on the numbers it plots. Six parameters
# track v_pi an order of magnitude better than two; and one update at s_t moves every
# state within 0.15 of it closer to the truth while leaving distant states nearly
# untouched, which the two-feature update cannot do.
near, far = np.abs(S - ST) < 0.15, np.abs(S - ST) > 0.40
assert np.sqrt(np.mean((V - fit_r) ** 2)) < 0.3 < 2.0 < np.sqrt(np.mean((V - fit_l) ** 2))
assert np.all(np.abs(V[near] - up_r[near]) < np.abs(V[near]))
assert np.max(np.abs(up_r[far])) < 0.15 * np.min(np.abs(up_l[far]))
fig, (axL, axR) = plt.subplots(1, 2, figsize=(9.4, 3.9))
trim(axL), trim(axR)
# Left: the same curve, stored three ways.
axL.plot(S, fit_l, color=COL["orange"], lw=2.0, zorder=4)
axL.plot(S, fit_r, color=COL["blue"], lw=1.8, zorder=5)
axL.plot(S, V, ls="none", marker="o", ms=2.0, color=GREY, zorder=6)
axL.set_xlim(-0.02, 1.02)
axL.set_ylim(-4.4, 11.0)
axL.set_xlabel("state $s$")
axL.set_ylabel("value")
axL.set_title("Six numbers stand in for two hundred", fontsize=11)
label_at(axL, 0.02, 10.2, r"$v_{\pi}$: 200 table entries", color=GREY, fontsize=9.5)
label_at(axL, 0.47, 8.4, "6 features: 6 numbers", color=COL["blue"], fontsize=9.5)
label_at(axL, 0.66, 2.6, r"$[\,s\ \ 1\,]$: 2 numbers", color=COL["orange"], fontsize=9.5)
# Right: one update at one state. The dots on zero are the table entries that
# @eq-td-untouched leaves alone; the arrow is the one entry the table does move.
axR.plot(S, V, ls="none", marker="o", ms=2.0, color=GREY, alpha=0.5, zorder=2)
axR.plot(S[::4], np.zeros(N)[::4], ls="none", marker="o", ms=2.6,
color=COL["vermilion"], alpha=0.75, zorder=3)
axR.plot(S, up_l, color=COL["orange"], lw=2.0, zorder=4)
axR.plot(S, up_r, color=COL["blue"], lw=1.8, zorder=5)
axR.annotate("", xy=(ST, TARGET), xytext=(ST, 0.0),
arrowprops=dict(arrowstyle="->", color=COL["vermilion"], lw=1.3))
axR.plot([ST], [TARGET], marker="o", ms=6.5, color=COL["vermilion"], zorder=7)
axR.set_xlim(-0.02, 1.02)
axR.set_ylim(-4.4, 11.0)
axR.set_xlabel("state $s$")
axR.set_ylabel("estimate after one update")
axR.set_title("One visit, and the neighbours move too", fontsize=11)
label_at(axR, 0.02, 10.3, "2 features: every state moves", color=COL["orange"], fontsize=9.5)
label_at(axR, 0.55, 6.3, "6 features: nearby states move", color=COL["blue"], fontsize=9.5)
label_at(axR, 0.02, -1.7, "a table moves this entry only", color=COL["vermilion"], fontsize=9.5)
label_at(axR, 0.345, 0.8, r"$s_{t}$", color=COL["vermilion"], fontsize=10)
label_at(axR, 0.84, -3.3, r"$v_{\pi}$", color=GREY, fontsize=9.5)
fig.tight_layout()
plt.show()
Nothing requires \(\hat{v}\) to be linear. Taking \(\hat{v}(s,w)\) to be a deep neural network, with \(w\) its weights, is what people mean by deep reinforcement learning.
Note
As Chapter 1 already insisted: RL and deep learning are orthogonal. RL says how to estimate values and policies from sampled experience; the network is one choice of approximator among many, and swapping it for Example 3.1 changes nothing about the algorithms below.
Fitting \(w\) by stochastic gradient descent
Choose \(w\) to minimize the mean squared error against the true value function,
\[ J(w)=\E\Big[\big(v_{\pi}(S)-\hat{v}(S,w)\big)^{2}\Big]. \tag{3.12}\]
This is exactly Equation 2.12, so Equation 2.13 applies. With \(f(w,s)=(v_{\pi}(s)-\hat{v}(s,w))^{2}\) the gradient is \(-2(v_{\pi}(s)-\hat{v}(s,w))\nabla_{w}\hat{v}(s,w)\), and absorbing the \(2\) into the step size gives gradient ascent on the negative error:
\[ w_{t+1}=w_{t}+\alpha_{t}\big(v_{\pi}(s_{t})-\hat{v}(s_{t},w_{t})\big)\nabla_{w}\hat{v}(s_{t},w_{t}). \tag{3.13}\]
One term in Equation 3.13 is not available: \(v_{\pi}(s_{t})\) is the thing being estimated. Every algorithm in this chapter is a different answer to what to put in its place, and each answer is one we have already met.
| Method | Substitute for \(v_{\pi}(s_{t})\) | Update |
|---|---|---|
| Monte Carlo with FA | \(g_{t}\), the realized discounted return from \(s_{t}\) | \(w_{t+1}=w_{t}+\alpha_{t}\big(g_{t}-\hat{v}(s_{t},w_{t})\big)\nabla_{w}\hat{v}(s_{t},w_{t})\) |
| TD with FA | the TD target \(r_{t+1}+\gamma\hat{v}(s_{t+1},w_{t})\) | \(w_{t+1}=w_{t}+\alpha_{t}\big[r_{t+1}+\gamma\hat{v}(s_{t+1},w_{t})-\hat{v}(s_{t},w_{t})\big]\nabla_{w}\hat{v}(s_{t},w_{t})\) |
WarningThe second row is not actually SGD
The Monte Carlo row is an honest stochastic gradient step: \(g_{t}\) does not depend on \(w\), so the increment really is an unbiased sample of the gradient of Equation 3.12.
The TD row is not. Its target \(r_{t+1}+\gamma\hat{v}(s_{t+1},w_{t})\) contains \(w_{t}\), so differentiating Equation 3.12 properly would produce a second term in \(\gamma\nabla_{w}\hat{v}(s_{t+1},w_{t})\) that the update simply drops. Dropping it is deliberate, and the result is called a semi-gradient method: it follows the gradient of the error while pretending the target is a constant.
The cost is that Theorem 2.1 no longer applies off the shelf, because the increment is not the gradient of anything. What survives is weaker and more conditional: for linear \(\hat{v}\) and on-policy sampling, with states drawn from the stationary distribution induced by \(\pi\), semi-gradient TD converges to the TD fixed point, which is not the minimizer of Equation 3.12 but is within a bounded factor of it. Combine off-policy sampling with function approximation and bootstrapping and it can diverge outright. In exchange one gets what this whole chapter is about: updates that do not wait for the episode to end.
Diverging outright deserves more than a clause, because the failure is cheap to arrange. Figure 3.3 needs no more than two states, one weight and a problem the approximator represents exactly, and it blows up on nothing worse than a change in where the data comes from.
Off-policy semi-gradient TD diverging on a two-state chain
RNG = np.random.default_rng(20260725)
# --- two states, one parameter -----------------------------------------------
# phi(s1) = 1 and phi(s2) = 2, so v(s1, w) = w and v(s2, w) = 2w: one weight moves
# both estimates, which is the whole point of function approximation. Every reward is
# mean zero, so v_pi = 0 at both states and the approximator represents the answer
# EXACTLY, at w = 0. Nothing is wrong with the function class. At s1 there are two
# actions, advance to s2 and dawdle at s1; at s2 the single action returns to s1.
GAMMA, PHI = 0.9, np.array([1.0, 2.0])
ALPHA, SIGMA = 0.01, 0.3 # step size, and the sd of the mean-zero reward
Q_TARGET, P_BEHAV = 1.0, 0.1 # P(advance | s1) under the target, and behavior, policy
W0, N_STEPS, N_RUNS = 1.0, 1600, 60
def run(p_advance, n_steps, alpha=ALPHA, rng=None):
"""Semi-gradient TD, the TD row of @tbl-fa-methods, on data from `p_advance`.
The update is w += alpha * rho * delta * phi(s). The importance ratio
rho = pi(a|s) / b(a|s) corrects the ACTION the behavior policy took, and nothing
corrects the STATE distribution its dawdling induces. Setting p_advance = Q_TARGET
makes rho equal 1 at every step, which is exactly the on-policy run.
"""
rng = RNG if rng is None else rng
w, s, out = W0, 0, np.empty(n_steps + 1)
out[0] = w
for t in range(n_steps):
if s == 0:
adv = rng.random() < p_advance
pi_a, b_a = (Q_TARGET, p_advance) if adv else (1.0 - Q_TARGET, 1.0 - p_advance)
rho, s2 = (pi_a / b_a if b_a > 0 else 0.0), (1 if adv else 0)
else:
rho, s2 = 1.0, 0 # s2 offers a single action, so no correction is needed
delta = rng.normal(0.0, SIGMA) + GAMMA * PHI[s2] * w - PHI[s] * w
w += alpha * rho * delta * PHI[s]
out[t + 1] = w
s = s2
return out
def drift(d1):
"""Coefficient in E[dw] = alpha * c(d1) * w when a share d1 of updates land at s1.
At s1 the TD error is gamma*2w - w and the gradient is phi = 1, contributing
2*gamma - 1. That is POSITIVE for gamma > 1/2: raising the estimate w at s1 raises
its own bootstrapped target 2w twice as fast, so the correction enlarges the error
it was sent to fix. Only updates at s2, worth 2*(gamma - 2), pull back.
"""
return d1 * (2 * GAMMA - 1) + (1 - d1) * 2 * (GAMMA - 2)
def rms(p_advance):
paths = np.array([run(p_advance, N_STEPS) for _ in range(N_RUNS)])
return np.sqrt((paths ** 2).mean(axis=0))
on, off = rms(Q_TARGET), rms(P_BEHAV)
steps = np.arange(N_STEPS + 1)
# The blow-up is structural, not a step size chosen to produce it: the drift
# coefficient is positive whatever alpha is, so shrinking alpha only slows the exit.
for a in (0.001, 0.003, 0.01):
ends = [abs(run(P_BEHAV, 2000, alpha=a, rng=np.random.default_rng(k))[-1])
for k in range(5)]
assert min(ends) > W0, (a, min(ends))
assert off[-1] > 100 * off[0] and on[-1] < on[0] / 10, (off[-1], on[-1])
fig, (axL, axR) = plt.subplots(1, 2, figsize=(9.4, 3.9))
trim(axL), trim(axR)
# --- left: one approximator, one update rule, two sampling distributions ------
axL.semilogy(steps, off, color=COL["vermilion"], lw=2.0, zorder=4)
axL.semilogy(steps, on, color=COL["sky"], lw=2.0, zorder=4)
axL.set_xlim(0, N_STEPS)
axL.set_ylim(on.min() * 0.45, off.max() * 8) # air above the red curve, and below the blue
axL.set_xlabel("updates")
axL.set_ylabel("root mean square weight ($w=0$ is exact)")
axL.set_title("Off-policy, the weight runs away geometrically", fontsize=11)
label_at(axL, N_STEPS * 0.30, off.max() * 2.2, "off-policy sampling",
color=COL["vermilion"], fontsize=9.5)
label_at(axL, N_STEPS * 0.42, on[-1] * 6.0, "on-policy sampling",
color=COL["sky"], fontsize=9.5)
# --- right: the sign of the drift, against where the updates land -------------
# Each tag sits just below and to the right of its own dot, on the empty side of
# the line, so neither the line nor the other tag comes near it.
d = np.linspace(0, 1, 200)
axR.plot([0, 1.02], [0, 0], color=GREY, lw=0.9, ls="--", zorder=2)
axR.plot(d, drift(d), color=INK, lw=1.6, zorder=3)
for x, colour in ((0.5, COL["sky"]), (1.0 / (1.0 + P_BEHAV), COL["vermilion"])):
axR.plot([x], [drift(x)], "o", color=colour, ms=7, zorder=5)
axR.set_xlim(0, 1.22)
axR.set_xticks([0, 0.25, 0.5, 0.75, 1.0]) # the margin past 1 gives the tag room to sit
axR.set_ylim(-2.45, 1.05)
axR.set_xlabel("share of updates made at $s_{1}$")
axR.set_ylabel(r"drift in $w$ per update, in units of $\alpha w$")
axR.set_title("The sign of the drift is set by the sampling", fontsize=11)
label_at(axR, 0.95, 0.22, "off-policy", color=COL["vermilion"], fontsize=9.5)
label_at(axR, 0.56, -1.00, "on-policy", color=COL["sky"], fontsize=9.5)
label_at(axR, 0.03, 0.30, "$w$ runs away", color=GREY, fontsize=9)
label_at(axR, 0.03, -0.36, "$w$ contracts to $0$", color=GREY, fontsize=9)
fig.tight_layout()
plt.show()
Sarsa with function approximation
State values still cannot be turned into decisions without a model, so repeat the construction for action values. Approximate \(\hat{q}(s,a,w)\approx q_{\pi}(s,a)\) and substitute it into the TD-with-FA row of Table 3.3:
\[ w_{t+1}=w_{t}+\alpha_{t}\big[\,r_{t+1}+\gamma\hat{q}(s_{t+1},a_{t+1},w_{t})-\hat{q}(s_{t},a_{t},w_{t})\,\big]\nabla_{w}\hat{q}(s_{t},a_{t},w_{t}). \tag{3.14}\]
This is tabular Sarsa Equation 3.7 with \(q\) replaced by \(\hat{q}\), and with the update applied to \(w\) rather than to a cell. Pair it with \(\eps\)-greedy improvement exactly as before and the policy search algorithm carries over unchanged.
Important
Two threads now run in parallel and should not be confused. What is estimated has gone from state values to action values to optimal action values. How it is stored has gone from a table to a parameter vector. They are independent choices: Q-learning with function approximation is the combination that, with a neural network for \(\hat{q}\), is Deep Q-learning.
Chapter 4 changes the question again. Everything here parameterizes a value and reads a policy off it. Policy gradient methods parameterize the policy directly and never form a table of values at all.