Q-learning

1The values of the best behavior

The best any policy can do gives the optimal action values:

Knowing q_* is enough to act well: in each state, take the action with the largest value. On the cliff, with γ = 1, q_* counts moves. From A2, the cell above the start, moving right leaves 6 moves to the goal along the edge, so q_*(A2, right) = −6, and moving up costs two more, q_*(A2, up) = −8. From B2, a step down into the cliff costs 100, and from the start the best trip still costs 7: q_*(B2, down) = −107.

The optimal values are tied together, one step apart, by the Bellman optimality equation. The value of an action is the reward it brings plus the discounted value of acting as well as possible from the state it leads to:

Moving right from A2 leads to B2, whose moves up, right, down and left are worth −7, −5, −107 and −7. So q_*(A2, right) = −1 + max(−7, −5, −107, −7) = −6.

The agent does not know the rewards and next states in advance, so it cannot solve this equation. Like Sarsa, it keeps an estimate Q(s, a) for every pair and, after each step, moves the estimate of the pair it just tried a fraction α of the way toward a target. The methods on this page differ only in their target.

2The Q-learning update

Compare it with Sarsa's. Sarsa's target, R_t+1 + γQ(S_t+1, A_t+1), uses the value of the action the agent takes next. Q-learning's target uses the best action in the next state, whatever the agent does there.

Why this target? It is the inside of the Bellman optimality equation, with its two unknowns replaced by what the agent has:

• the expectation over rewards and next states becomes the one reward and next state it just observed;
• q_* becomes the current table Q.

Over many steps the randomness of single rewards and next states averages out, as a sample average approaches an expectation, while the table itself improves.

An example with numbers, with α = 0.5. Partway through learning, the table holds Q(A2, right) = −8, and in B2 up −7, right −5, down −60 and left −7. The agent moves right from A2 to B2 and gets −1. The target is −1 + max(−7, −5, −60, −7) = −6, and the estimate moves halfway to it:

The target is the same whatever the agent does next in B2, even if its next move is a random step down into the cliff.

The algorithm

The loop is Sarsa's, with one change: the target does not use the next action, so the agent does not have to choose it before updating. It chooses each action at the start of its step, from the table as it stands. For a step size α in (0, 1] and a small ε > 0:

1. Start with any table Q(s, a), except Q(terminal, ·) = 0.
2. At the start of each episode, observe the first state S.
3. Choose an action A in S with a policy derived from Q, such as ε-greedy.
4. Take A, and observe the reward R and the next state S′.
5. Update Q(S, A) ← Q(S, A) + α[R + γ max_a Q(S′, a) − Q(S, A)].
6. Set S ← S′, and go back to step 3 until S is terminal.

The figure runs Q-learning on the cliff with the settings of the Sarsa figure, α = 0.5, γ = 1 and ε = 0.1. Now the agent chooses each move after the last update, and the target uses the best moves of the next cell, outlined in red, whatever the agent does there.

When does it work? Q converges to q_* with probability 1 as long as:

1. every pair keeps being updated, so the policy must never stop trying every action;
2. the step sizes shrink in the usual way: their sum grows without limit while the sum of their squares stays finite.

The first condition is the least any method can ask for, since the value of an action never tried cannot be learned.

3Learning about one policy while following another

The agent behaves ε-greedily, yet its target uses max_a Q(S_t+1, a), the value of the greedy action in the next state, whatever action it actually takes there. So Q-learning learns the values of the greedy policy, while its experience comes from the ε-greedy one.

The behavior policy still matters in one way: it decides which pairs get visited, and so updated.

Sarsa is on-policy: its target uses the action it takes next, so when that action is an exploring move, the target includes what exploring costs. Sarsa learns q_π for the ε-greedy policy it follows, and Q-learning learns q_*. A backup diagram shows the difference, in what each update looks at.

On the cliff, the difference decides the route. Let both methods learn for long enough, with ε = 0.1 and shrinking step sizes. Sarsa settles one row up, as in the previous note. Q-learning's values assume the greedy move from the next step on, so it keeps to the edge, and while it keeps exploring, it sometimes falls in.

Q-learning's table describes the better policy, worth −7 per trip once exploring stops, but Sarsa does better while learning. The gap depends on ε:

• below ε ≈ 0.02, a random move down is rare enough that Sarsa keeps to the edge too;
• above ε ≈ 0.26, Sarsa moves up to the top row;
• if ε shrinks toward 0 over time, both end up with the optimal policy.

With a purely greedy behavior, ε = 0, the two methods almost coincide: both act greedily, and their targets are equal, since the action Sarsa takes next is the greedy one. The one difference is timing. Sarsa chooses its next action before updating the table, and Q-learning after, so when the next state is the same state, the update can change which action Q-learning then takes. In the Sarsa figure, choosing first cost the agent a second fall from the start.

Many off-policy methods must correct for the difference between the two policies. One-step Q-learning needs no such correction: given the pair it updates, the reward and the next state do not depend on either policy, and the target uses a maximum instead of the action the behavior takes next.

4Expected Sarsa

Where Sarsa's target uses the one next action the policy happens to pick and Q-learning's the best one, Expected Sarsa's target averages the values of all next actions, each weighted by how likely π is to take it. This average, written V(S_t+1), is the value of the next state that the table implies under π. It is also what Sarsa's target is worth on average, so Expected Sarsa moves every time the way Sarsa moves on average, without the randomness that the choice of A_t+1 adds. The price is a sum over the actions at every step.

The table takes section 2's step from A2 to B2, now with B2's values at q_* and ε = 0.1; the Sarsa rows give the probability of each case. The last column starts from Q(A2, right) = −6, with α = 0.5:

Sarsa's possible targets average 0.925(−6) + 0.05(−8) + 0.025(−108) = −8.65, Expected Sarsa's target. But Sarsa's new value depends on the move that happens to come next, while Expected Sarsa's is always the same. With less noise in its updates, Expected Sarsa tolerates a larger step size. On the cliff the moves themselves are certain and all the randomness comes from the policy, so Expected Sarsa can even use α = 1 and replace each estimate by its target, while Sarsa needs a small α to average its random targets.

Expected Sarsa can also learn off-policy, and it includes Q-learning as a special case:

1. the weights π can come from a target policy other than the behavior;
2. if π is greedy, the average puts all its weight on the best action, and the target is Q-learning's.

5Maximization bias and double learning

Q-learning's target takes the largest of several estimates.

Take a state with six actions that are all worth exactly 0: each pays +1 or −1 with equal chance. Estimate each action by the average of three payments, so an estimate is 1, 1/3, −1/3 or −1. Each estimate is right on average, but the largest of the six is 1 with probability 0.55, 1/3 with probability 0.43, and below 0 less than 2% of the time. On average it is +0.69.

A Q-learning target that ends in such a state gets this optimism added in, and the states that lead there look better than they are. The agent is drawn toward states whose actions are uncertain, for no good reason.

The bias comes from using the same samples twice: to pick the action that looks best, and to say how good it is. Double learning separates the two jobs. It keeps two independent estimates, Q₁ and Q₂, each learned from its own half of the experience:

• one picks the action, A^* = argmax_a Q₁(a);
• the other says what it is worth, Q₂(A^*).

The samples behind Q₂ played no part in the choice, so E[Q₂(A^*)] = q(A^*), with no bias. In the example, A^* is whichever action happened to look best, but its value comes from three fresh payments, which average 0.

Double Q-learning applies this to Q-learning. At each step a coin flip decides which table learns. On heads,

and on tails the same update with Q₁ and Q₂ swapped, so that Q₂ learns. The two tables play symmetric roles. The behavior can use both, for example ε-greedy with respect to Q₁ + Q₂. Double learning doubles the memory, but not the work per step, since each step updates only one table. The same idea gives double versions of Sarsa and Expected Sarsa.

6Afterstates

Sometimes the immediate effect of an action is known, and only what follows is uncertain. In a board game you know the position your move leaves, but not your opponent's reply. Then it pays to learn the values of afterstates instead of the values of state–action pairs.

In Nim, two players take turns removing any number of sticks from one pile, and whoever takes the last stick wins. From piles of 3 and 2, taking one stick from the first pile leaves piles of 2 and 2. From piles of 2 and 3, taking one from the second pile leaves the same position.

Piles of 2 and 2 happen to be a winning position to leave: whatever your opponent takes from one pile, you take the same from the other, and you take the last stick.

The learning methods stay the same; only what the table is about changes. Afterstates appear outside games too, whenever an action is defined by its immediate effect, such as loading a parcel onto a particular truck: the loaded truck is known, the traffic on its route is not.

7Summary

The key ideas next to their NumPy equivalents. The table q is indexed by state and action, and g holds a return or a target, which is a guess at the return.