Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.
11.3.7 Assigning Credit and Blame to Paths
In Q-learning and SARSA, only the previous state-action pair has its value revised when a reward is received. Intuitively, when an agent takes a number of steps that lead to a reward, all of the steps along the way could be held responsible and so receive some of the credit or the blame for a reward. This section gives an algorithm that assigns the credit and blame for all of the steps that lead to a reward.
Consider updating the value of Q[s_{3},right] based on the reward for entering state s_{4}. From the perspective of state s_{4}, the algorithm is doing a one-step backup. From the perspective of state s_{3}, it is doing a one-step look-ahead. To make the algorithm allow the blame to be associated with more than the previous step, the reward from entering step s_{4} could do a two-step backup to update s_{2} or, equivalently, a two-step look-ahead from s_{2} and update s_{2}'s value when the reward from entering s_{4} is received. We will describe the algorithm in terms of a look-ahead but implement it using a backup.
With a two-step look-ahead, suppose the agent is in state s_{t}, does action a_{t}, ends up in state s_{t+1}, and receives reward r_{t+1}, then does action a_{t+1}, resulting in state s_{t+2} and receiving reward r_{t+2}. A two-step look-ahead at time t gives the return R_{t}^{(2)} = r_{t+1} + γr_{t+2} + γ^{2} V(s_{t+2}), thus giving the TD error
δ_{t} = r_{t+1} + γr_{t+2} + γ^{2} V(s_{t+2})-Q[s_{t},a_{t}],
where V(s_{t+2}) is an estimate of the value of s_{t+2}. The two-step update is
Q[s_{t},a_{t}] ←Q[s_{t},a_{t}]+αδ_{t}.
Unfortunately, this is not a good estimate of the optimal Q-value, Q^{*}, because action a_{t+1} may not be an optimal action. For example, if action a_{t+1} was the action that takes the agent into a position with a reward of -10, and better actions were available, the agent should not update Q[s_{0},a_{0}]. However, this multiple-step backup provides an improved estimate of the policy that the agent is actually following. If the agent is following policy π, this backup gives an improved estimate of Q^{π}. Thus multiple-step backup can be used in an on-policy method such as SARSA.
Suppose the agent is in state s_{t}, and it performs action a_{t} resulting in reward r_{t+1} and state s_{t+1}. It then does action a_{t+1}, resulting in reward r_{t+2} and state s_{t+2}, and so forth. An n-step return at time t, where n ≥ 1, written R_{r}^{(n)}, is a data point for the estimated future value of the action at time t, given by looking n steps ahead, is
R_{t}^{(n)} = r_{t+1} + γr_{t+2} + γ^{2} r_{t+3} + ...+ γ^{n-1} r_{t+n} + γ^{n} V(s_{t+n}).
This could be used to update Q[s_{t},a_{t}] using the TD error R_{t}^{(n)}-Q[s_{t},a_{t}]. However, it is difficult to know which n to use. Instead of selecting one particular n and looking forward n steps, it is possible to have an average of a number of n-step returns. One way to do this is to have a weighted average of all n-step returns, in which the returns in the future are exponentially decayed, with a decay of λ. This is the intuition behind the method called SARSA(λ); when a reward is received, the values of all of the visited states are updated. Those states farther in the past receive less of the credit or blame for the reward.
Let
R_{t}^{λ}= (1-λ) ∑_{n=1}^{∞}λ^{n-1} R_{t}^{(n)},
where (1-λ) is a normalizing constant to ensure we are getting an average. The following table gives the details of the sum:
look-ahead | Weight | Return |
1 step | 1-λ | r_{t+1} + γV(s_{t+1}) |
2 step | (1-λ) λ | r_{t+1} + γr_{t+2} + γ^{2} V(s_{t+2}) |
3 step | (1-λ) λ^{2} | r_{t+1} + γr_{t+2} + γ^{2} r_{t+3} + γ^{3} V(s_{t+3}) |
4 step | (1-λ) λ^{3} | r_{t+1} + γr_{t+2} + γ^{2} r_{t+3} + γ^{3} r_{t+4} + γ^{4} V(s_{t+3}) |
··· | ··· | ··· |
n step | (1-λ) λ^{n-1} | r_{t+1} + γr_{t+2} + γ^{2} r_{t+3} + ...+ γ^{n} V(s_{t+n}) |
··· | ··· | ··· |
total | 1 |
Collecting together the common r_{t+i} terms gives
R_{t}^{λ} = r_{t+1}+γV(s_{t+1})- λγV(s_{t+1}) + λγr_{t+2} + λγ^{2} V(s_{t+2})-λ^{2}γ^{2} V(s_{t+2}) + λ^{2}γ^{2} r_{t+3} + λ^{2}γ^{3} V(s_{t+3})-λ^{3}γ^{3} V(s_{t+3}) + λ^{3}γ^{3} r_{t+4} + λ^{3}γ^{4} V(s_{t+4})-λ^{4}γ^{4} V(s_{t+4}) +....
This will be used in a version of SARSA in which the future estimate of V(s_{t+i}) is the value of Q[s_{t+i},a_{t+i}]. The TD error - the return minus the state estimate - is
R_{t}^{λ}-Q[s_{t},a_{t}] = r_{t+1}+γQ[s_{t+1},a_{t+1}]-Q[s_{t},a_{t}] + λγ( r_{t+2} + γQ[s_{t+2},a_{t+2}]-Q[s_{t+1},a_{t+1}]) + λ^{2}γ^{2}( r_{t+3} + γQ[s_{t+3},a_{t+3}]- Q[s_{t+2},a_{t+2}]) + λ^{3}γ^{3}( r_{t+4} + γQ[s_{t+4},a_{t+4}] -Q[s_{t+3},a_{t+3}]) +....
Instead of waiting until the end, which may never occur, SARSA(λ) updates the value of Q[s_{t},a_{t}] at every time in the future. When the agent receives reward r_{t+i}, it can use the appropriate sum in the preceding equation to update Q[s_{t},a_{t}]. The preceding description refers to all times; therefore, the update r_{t+3} + γQ[s_{t+3},a_{t+3}]- Q[s_{t+2},a_{t+2}] can be used to update all previous states. An agent can do this by keeping an eligibility trace that specifies how much a state-action pair should be updated at each time step. When a state-action pair is first visited, its eligibility is set to 1. At each subsequent time step its eligibility is reduced by a factor of λγ. When the state-action pair is subsequently visited, 1 is added to its eligibility.
The eligibility trace is implemented by an array e[S,A], where S is the set of all states and A is the set of all actions. After every action is carried out, the Q-value for every state-action pair is updated.
controller SARSA(λ,S,A,γ,α) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
inputs: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
S is a set of states | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A is a set of actions | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
γ the discount | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
α is the step size | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
λ is the decay rate | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
internal state: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
real array Q[S,A] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
real array e[S,A] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
previous state s | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
previous action a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
begin | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
initialize Q[S,A] arbitrarily | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
initialize e[s,a]=0 for all s,a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
observe current state s | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
select action a using a policy based on Q | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
repeat forever: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
carry out an action a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
observe reward r and state s' | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
select action a' using a policy based on Q | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
δ←r+ γQ[s',a'] - Q[s,a] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e[s,a] ←e[s,a]+1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
for all s",a": | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Q[s",a"] ←Q[s",a"] + αδe[s",a"] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e[s",a"] ←γλe[s",a"] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
s ←s' | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
a ←a' | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
end-repeat | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
end |
The algorithm, known as SARSA(λ), is given in Figure 11.14.
Although this algorithm specifies that Q[s,a] is updated for every state s and action a whenever a new reward is received, it may be much more efficient and only slightly less accurate to only update those values with an eligibility over some threshold.