Artificial
Intelligence

controller Q-learning(S,A,γ,α)
2:           Inputs
3:                     S is a set of states
4:                     A is a set of actions
5:                     γ the discount
6:                     α is the step size
7:           Local
8:                     real array Q[S,A]
9:                     previous state s
10:                     previous action a
11:           initialize Q[S,A] arbitrarily
12:           observe current state s
13:           repeat
14:                     select and carry out an action a
15:                     observe reward r and state s'
16:                     Q[s,a] ←Q[s,a] + α(r+ γmax_a' Q[s',a'] - Q[s,a])
17:                     s ←s'
18:           until termination

Example 11.9: Consider the domain Example 11.7, shown in Figure 11.8. Here is a sequence of ⟨s,a,r,s'⟩ experiences, and the update, where γ=0.9 and α=0.2, and all of the Q-values are initialized to 0 (to two decimal points):

Notice how the reward of -100 is averaged in with the other rewards. After the experience of receiving the -100 reward, Q[s₂,up] gets the value

0.8×0.36 + 0.2×(-100+0.9×0.36) = -19.65

At the next step, the same action is carried out with a different outcome, and Q[s₂,up] gets the value

0.8×-19.65 + 0.2×(0+0.9×3.6) = -15.07

After more experiences going up from s₂ and not receiving the reward of -100, the large negative reward will eventually be averaged in with the positive rewards and eventually have less influence on the value of Q[s₂,up], until going up in state s₂ once again receives a reward of -100.

Example 11.10: Consider the domain Example 11.7, shown in Figure 11.8. Suppose that the agent has the experience

⟨s₀,right,0,s₁,upC,-1,s₃,upC,-1,s₅,left,0,s₄,left,10,s₀⟩

and repeats this sequence of actions a number of times. (Note that a real Q-learning agent would not keep repeating the same actions, particularly when some of them look bad, but we will assume this to let us understand how Q-learning works.)

---

This is a trace of Q-learning described in Example 11.10.

(a) Q-learning for a deterministic sequence of actions with a separate α_k-value for each state-action pair, α_k=1/k.

(b) Q-learning for a deterministic sequence of actions with α=1:

(c) Q-values after full exploration and convergence:

---

Figure 11.11 shows how the Q-values are updated though a repeated execution of this action sequence. In both of these tables, the Q-values are initialized to 0.

1. In the top run there is a separate α_k-value for each state-action pair. Notice how, in iteration 1, only the immediate rewards are updated. In iteration 2, there is a one-step backup from the positive rewards. Note that the -1 is not backed up because another action is available that has a Q-value of 0. In the third iteration, there is a two-step backup. Q[s₃,upC] is updated because of the reward of 10, two steps ahead; its value is the average of its experiences: (-1 + -1 + (-1+0.9×6))/3.
2. The second run is where α=1; thus, it only takes into account the current estimate. Again, the reward is backed up one step in each iteration. In the third iteration, Q[s₃,upC] is updated because of the reward of 10 two steps ahead, but with α=1, the algorithm ignores its previous estimates and uses its new experience, -1+0.9×0.9. Having α=1 converges much faster than when α_k=1/k, but α=1 only converges when the actions are deterministic because α=1 implicitly assumes that the last reward and resulting state are representative of future ones.
3. If the algorithm is run allowing the agent to explore, as is normal, some of the Q-values after convergence are shown in part (c). Note that, because there are stochastic actions, α cannot be 1 for the algorithm to converge. Note that the Q-values are larger than for the deterministic sequence of actions because these actions do not form an optimal policy.

The final policy after convergence is to do up in state s₀, upC in state s₂, up in states s₁ and s₃, and left in states s₄ and s₅.

You can run the applet for this example that is available on the book web site. Try different initializations, and try varying α.