Lecture 4 only evaluated policies (prediction). Now we use those tools to find the optimal policy (control). Without knowing the model, that is, without knowing the transitions or the rewards, we close in on the optimum from experience alone. Three things are at the heart of it: why we must learn action values rather than state values, how to mix in exploration, and whether to keep the policy we act with and the policy we learn the same or different (on-policy vs. off-policy).

Lecture slides: PDF

Where model-free control is needed

Elevator dispatch, RoboCup soccer, parallel parking, Quake, ship steering, portfolio management, bioreactors, protein folding, helicopter aerobatics, robot walking, Go. Almost all of the problems Silver lists are one of two kinds: either the MDP model is unknown but experience can be sampled from it, or the model is known but so large that it can only be handled by sampling. Either way, model-free control is the answer.

Let us also fix the distinction between on-policy and off-policy up front. On-policy is “learning on the job”: we learn the very policy $\pi$ we follow, from experience produced by that same $\pi$. Off-policy is “learning over someone’s shoulder”: we learn the policy $\pi$ we care about from experience produced by a different policy $\mu$.

Generalized policy iteration, made model-free

The skeleton of Lecture 3 was generalized policy iteration: evaluate the policy (estimate the value), improve the policy from that value (act greedily), and alternating the two converges to the optimum. The frame is the same in the model-free setting. Drop Lecture 4’s Monte Carlo into the evaluation slot. But a problem arises in the improvement slot.

Why action values rather than state values

To improve greedily with state values $V(s)$, we would have to write this:

$$\pi'(s) = \arg\max_{a\in\mathcal{A}} \Big( R_s^a + P_{ss'}^a\, V(s') \Big)$$

The transition probability $P_{ss'}^a$ and the reward $R_s^a$, that is, the model, sit right inside it. Without the model, this $\arg\max$ cannot be computed. Not knowing “where taking this action leads and how much it pays,” we cannot tell from state values alone which action is good.

Learning action values $Q(s,a)$ removes this wall.

$$\pi'(s) = \arg\max_{a\in\mathcal{A}} Q(s,a)$$

Action values already hold “the value of each action” whole, so improvement is done by simply picking the largest entry in the table, no model needed. That is why model-free control learns $Q$ rather than $V$. The starting point is to put “Monte Carlo for $Q \approx q_\pi$” in the evaluation slot and “greedy with respect to $Q$” in the improvement slot.

Why we must mix in exploration: the two doors

Pure greedy improvement has a trap. Silver’s two-doors example shows it sharply.

There are two doors ahead. You open the left door and get reward $0$. $V(\text{left})=0$. You open the right door and get $+1$. $V(\text{right})=+1$. You open the right again and get $+3$, so the average rises to $+2$. You open the right once more and get $+2$, still averaging $+2$. Now, acting greedily, you keep opening only the right door, because the right looks better than the left.

But did you really pick the best door? You opened the left just once. That time it happened to come up $0$, but it might in fact have been a jackpot door averaging $+10$. If you never open the left again, you will never know the truth. Shutting a door on a single bad experience: this is the danger of pure greed. So you must keep exploring, a little, forever.

ε-greedy

The simplest way to guarantee exploration. Give all $m$ actions a nonzero probability, but choose the greedy action with probability $1-\epsilon$ and a random action with probability $\epsilon$.

$$\pi(a|s) = \begin{cases} \epsilon/m + 1 - \epsilon & a^* = \arg\max_{a} Q(s,a) \\ \epsilon/m & \text{otherwise} \end{cases}$$

Most of the time you take the action that looks best, but now and then you open a different door too. If the left door was a jackpot, it will be exposed sooner or later in one of those $\epsilon$ moments.

ε-greedy is always an improvement

You might worry that mixing in $\epsilon$ makes things worse than greedy. It does not. Silver nails this down as a theorem. For any $\epsilon$-greedy policy $\pi$, the new $\epsilon$-greedy policy $\pi'$ with respect to its $q_\pi$ is always an improvement. That is, $v_{\pi'}(s) \ge v_\pi(s)$.

The heart of the proof is to show that the value of one step under the new policy is greater than or equal to the value of the old policy.

$$q_\pi(s,\pi'(s)) = \sum_{a} \pi'(a|s)\, q_\pi(s,a) = \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\max_a q_\pi(s,a)$$

Here $\max_a q_\pi(s,a)$ is greater than or equal to any weighted average. In particular, it is greater than the weighted average formed from the old policy $\pi$’s probabilities after subtracting off $\epsilon/m$.

$$\ge \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\sum_{a} \frac{\pi(a|s) - \epsilon/m}{1-\epsilon}\, q_\pi(s,a) = \sum_{a}\pi(a|s)\, q_\pi(s,a) = v_\pi(s)$$

Putting it together, $q_\pi(s,\pi'(s)) \ge v_\pi(s)$, and by the policy improvement theorem $v_{\pi'}(s) \ge v_\pi(s)$. Improving with $\epsilon$-greedy costs nothing: with this guarantee in hand, we can mix in exploration with confidence.

GLIE

Still, if we keep acting randomly with probability $\epsilon$ forever, we never quite settle onto the optimal policy. So exploration should be infinite but tapering. This condition is GLIE (Greedy in the Limit with Infinite Exploration). It demands two things.

  • Every state-action pair is visited infinitely often: $\lim_{k\to\infty} N_k(s,a) = \infty$.
  • The policy eventually converges to greedy: $\lim_{k\to\infty} \pi_k(a|s) = \mathbf{1}(a = \arg\max_{a'} Q_k(s,a'))$.

$\epsilon$-greedy becomes GLIE if $\epsilon$ is decayed to 0. The simplest schedule is $\epsilon = 1/k$. Early on it wanders a lot (small $k$ means large $\epsilon$), and as the episodes pile up it explores less and converges to greedy. It is a delicate balance: exploring infinitely yet ultimately picking out the optimum.

GLIE Monte Carlo control

Now it assembles into a single algorithm. Sample the $k$-th episode with the current policy $\pi$. For each state $S_t$ and action $A_t$ in that episode,

$$N(S_t,A_t) \leftarrow N(S_t,A_t) + 1$$

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \frac{1}{N(S_t,A_t)}\big(G_t - Q(S_t,A_t)\big)$$

pull the action value toward the mean of the returns. Then decay $\epsilon \leftarrow 1/k$ and improve the policy with $\pi \leftarrow \epsilon\text{-greedy}(Q)$. By the theorem, this GLIE Monte Carlo control converges to the optimal action value. $Q(s,a) \to q_*(s,a)$.

Silver’s example is blackjack again. Playing countless hands for real, without knowing the dealer’s rules or the probabilities, updating $Q$ and refining the policy with $\epsilon$-greedy, a policy very close to the “basic strategy” table people have worked out on paper emerges on its own. It has learned, from experience alone, when to hit and when to stand.

On-policy TD control: Sarsa

Plugging temporal-difference learning into the control loop in place of Monte Carlo is a natural improvement. TD has lower variance than MC, is online, and learns from unfinished sequences. So the idea is to apply TD to $Q(S,A)$, improve with $\epsilon$-greedy, and update at every step.

We update with the next action $A'$ that we actually take. It is called Sarsa because it uses state, action, reward, next state, and next action.

$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma Q(S',A') - Q(S,A)\big)$$

The policy that chooses actions and the policy being learned are the same (on-policy). At every step we run evaluation (Sarsa for $Q\approx q_\pi$) and improvement ($\epsilon$-greedy) together.

For Sarsa to converge to the optimal action value, two conditions are needed. One is the GLIE sequence of policies seen above; the other is that the step sizes $\alpha_t$ satisfy the Robbins-Monro conditions. That is, $\sum_{t=1}^{\infty}\alpha_t = \infty$ and $\sum_{t=1}^{\infty}\alpha_t^2 < \infty$. The first sum being infinite means the total stride length is enough to eventually reach any value, no matter how far it lies; the second sum being finite means the noise gradually dies down so the value settles at a single point. (In practice this condition is often not observed strictly, and a small constant $\alpha$ is used instead.)

The windy gridworld

Silver’s example is the windy gridworld. You move up, down, left, and right from a start to a goal, with a reward of $-1$ at every step until you arrive (no discounting). So the aim is to reach the goal as fast as possible. The catch is that certain columns have a wind blowing upward. In those columns, after you move, the wind pushes the piece one or two extra cells upward. Sarsa learns a detour that accounts for this wind. Factoring in the direction the wind pushes, it finds a roundabout route that lands exactly on the goal.

n-step Sarsa and Sarsa(λ)

As in prediction, one step and all the way to the end are just the two extremes in control too. The n-step Q-return, looking n steps ahead, bridges the space between.

$$q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n})$$

With $n=1$ it is $R_{t+1} + \gamma Q(S_{t+1})$, ordinary Sarsa; with $n=\infty$ it is Monte Carlo going all the way to the end of the episode. n-step Sarsa pulls $Q$ toward this n-step Q-return.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^{(n)} - Q(S_t,A_t)\big)$$

Forward-view Sarsa(λ) uses as its target the $q^\lambda$-return, which blends the Q-returns of all $n$ at once with weights $(1-\lambda)\lambda^{n-1}$.

$$q_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1} q_t^{(n)}, \qquad Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^\lambda - Q(S_t,A_t)\big)$$

The forward view has to see all of the future, so it can only be computed once the episode ends. Backward-view Sarsa(λ) does the same thing online with eligibility traces. Only now the trace is attached not per state but one per (state, action) pair.

$$E_0(s,a) = 0, \qquad E_t(s,a) = \gamma\lambda\, E_{t-1}(s,a) + \mathbf{1}(S_t = s, A_t = a)$$

And the TD error $\delta_t = R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)$ is sent out to all pairs in proportion to this trace.

$$Q(s,a) \leftarrow Q(s,a) + \alpha\,\delta_t\, E_t(s,a)$$

The intuition is this. When you happen to reach a reward, that good signal spreads along the traces all at once to the (state, action) pairs you just stepped on. The more recently you stepped on them, the darker the trace, so the larger the correction. In problems where reward is sparse, this spreading speeds learning up a great deal. In Silver’s gridworld example, one-step Sarsa(0) raises the value of only the single cell just in front of the goal, whereas Sarsa(λ) distributes credit at once along the entire path leading to the goal.

Off-policy learning

So far the policy we act with and the policy we learn have been the same. Off-policy separates the two. Following the behavior policy $\mu$, we experience $\{S_1,A_1,R_2,\dots,S_T\}\sim\mu$, and from it we learn the value $v_\pi(s)$ or $q_\pi(s,a)$ of a target policy $\pi$. Why does this matter? Silver gives four motivations.

  • Learn by observing humans or other agents. Learning by watching someone else play.
  • Reuse experience generated by old policies $\pi_1,\pi_2,\dots,\pi_{t-1}$. Not throwing it away, but using it again.
  • Learn the optimal policy while following an exploratory policy. This is the core motivation of Q-learning.
  • Learn multiple target policies at once while following a single behavior policy.

Importance sampling

The problem is how to estimate an expectation under $\pi$ from experience generated by $\mu$. The answer is importance sampling: the trick of rewriting an expectation under a different distribution $P$ in terms of the distribution $Q$ we have in hand.

$$\mathbb{E}_{X\sim P}[f(X)] = \sum_X P(X) f(X) = \sum_X Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}_{X\sim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$$

We re-weight by the ratio $P/Q$ of the two distributions.

Applying this to Monte Carlo, we correct the return $G_t$ generated by $\mu$ by multiplying it by the similarity of the two policies. The problem is that since the return runs all the way to the end of the episode, the probability ratio at every step must be multiplied throughout the episode.

$$G_t^{\pi/\mu} = \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})}\cdots\frac{\pi(A_T|S_T)}{\mu(A_T|S_T)}\, G_t$$$$V(S_t) \leftarrow V(S_t) + \alpha\big(G_t^{\pi/\mu} - V(S_t)\big)$$

It cannot be used when $\pi$ is nonzero but $\mu$ is zero (experience you never had cannot be corrected for), and above all, multiplying the probability ratio dozens of times makes the variance blow up. A single factor being very small or very large sends the whole product swinging. So MC importance sampling is almost unusable in practice.

Applied to TD, things improve dramatically. The TD target $R + \gamma V(S')$ is just a single step, so only a single importance correction is needed.

$$V(S_t) \leftarrow V(S_t) + \alpha\left(\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\big(R_{t+1} + \gamma V(S_{t+1})\big) - V(S_t)\right)$$

Since the two policies need only be similar for a single step, the variance is far lower than for Monte Carlo.

Q-learning: no importance sampling at all

In off-policy learning of action values $Q(s,a)$, something more dramatic happens: no importance sampling is needed at all. Here is why. The action $A_{t+1}$ we actually take next is chosen by the behavior policy $\mu$, but inside the target we directly use the value of an alternative action $A'\sim\pi(\cdot|S_t)$ chosen by the target policy $\pi$.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(R_{t+1} + \gamma Q(S_{t+1},A') - Q(S_t,A_t)\big)$$

Since the target already plugs in an action chosen by $\pi$, nothing is left to correct with a probability ratio later. If we now make the target policy $\pi$ greedy with respect to $Q$, that is, set $\pi(S_{t+1}) = \arg\max_{a'} Q(S_{t+1},a')$, the target simplifies cleanly.

$$R_{t+1} + \gamma Q(S_{t+1}, \arg\max_{a'} Q(S_{t+1},a')) = R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$

Since the alternative action chosen by $\pi$ is exactly the action that maximizes $Q$, the $\arg\max$ collapses into a $\max$. This is Q-learning’s famous update.

$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma \max_{a'} Q(S',a') - Q(S,A)\big)$$

Acting is done with an exploratory policy $\mu$ such as $\epsilon$-greedy, but what is being learned is the greedy optimal policy. As the behavior policy and the target policy both improve, Q-learning converges to the optimal action value. $Q(s,a) \to q_*(s,a)$.

Cliff walking

The cliff walking example shows the difference between on-policy (Sarsa) and off-policy (Q-learning) well. The bottom edge of the grid is a cliff, and falling off it incurs a large penalty and returns you to the start. The goal is to reach the opposite end while avoiding the cliff.

Q-learning learns the shortest path running right along the edge of the cliff. Because its target policy is greedy, it immediately learns that “the optimum is the straight line beside the cliff.” The problem is that when it actually walks it moves $\epsilon$-greedily, so once in a while, in one of those $\epsilon$ moments, it stumbles off the cliff. So its actual score during learning often plunges.

Sarsa is different. Being on-policy, it learns with the next action it actually takes, that is, actions that include exploration. Factoring in “the me who will sometimes move at random,” it learns a safe detour one cell away from the cliff. It is not optimal, but with fewer accidents during exploration its actual score is better. Q-learning, which knows the optimum, and Sarsa, which is safe because it accounts for exploration: the difference in character between the two is again vivid here.

Cliff walking. The bottom edge is the cliff (−100), and you must go from S to G. Run the episodes and Q-learning learns the shortest path right along the cliff (red), while Sarsa, accounting for exploration, learns the safe path one cell away (blue). Raise ε and you can see Sarsa detour farther out.

DP and TD, at a glance

By the time we reach control, the correspondence between Lecture 3’s dynamic programming and this lecture becomes vivid. It amounts to solving the same Bellman equation with full-width backups when the model is known and with sample backups when it is not. The correspondence pairs up like this.

  • Bellman expectation equation ($v_\pi$): full-width gives iterative policy evaluation, sample gives TD learning.
  • Bellman expectation equation ($q_\pi$): full-width gives Q-policy iteration, sample gives Sarsa.
  • Bellman optimality equation ($q_*$): full-width gives Q-value iteration, sample gives Q-learning.

Placing them side by side as update rules makes the correspondence even sharper. Letting $x \xleftarrow{\alpha} y$ stand for $x \leftarrow x + \alpha(y-x)$,

$$Q(s,a) \leftarrow \mathbb{E}[R + \gamma Q(S',A') \mid s,a] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma Q(S',A')$$

The left is Q-policy iteration, sweeping the entire expectation with the model; the right is Sarsa, filling that spot with a single experienced sample. The optimality equation has the same structure.

$$Q(s,a) \leftarrow \mathbb{E}\Big[R + \gamma \max_{a'} Q(S',a') \mid s,a\Big] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma \max_{a'} Q(S',a')$$

The skeleton learned in DP repeats itself in the model-free setting, with samples in place of the expectation.

This Q-learning meets neural networks in Lecture 6 and becomes DQN. And up to here we stored each state one by one in a table (tabular). If states are very many or continuous, a table is impossible. The next lecture approximates the value function with a function.