‘Thanks R. S. Sutton and A. G. Barto for their great work in Reinforcement Learning: An Introduction.

Eligibility Traces in Prediction Problems

In the backward view of TD(λ), there is a memory variable associated with each state, its eligibility trace. The eligibility trace for state s at time t is a random variable denoted Zt(s)∈R+. On each step, the eligibility traces for all states decay by γλ, and the eligibility trace for the one state visited on the step is incremented by 1:

for all nonterminal states s, where γ is the discount rate and λ is the λ-return 1 parameter or trace-decay parameter. This kind of eligibility trace is called an accumulating trace. The global TD error signal triggers proportional updates to all recently visited states, as signaled by their nonzero traces:

where

A complete prediction algorithm for on-line TD(λ) is given as follows:

1. Initialize V(s) arbitrarily.
2. Repeat for each episode:
   
   1. Initialize Z(s)=0 for all s∈S.
   2. Repeat for each step of episode:
      
      1. A← action given by π for S.
      2. Observe reward R and the next state S′.
      3. δ←R+γV(S′)−V(S)
      4. Z(S)←Z(S)+1
      5. For all s∈S:
         
         1. V(s)←V(s)+αδZ(s)
         2. Z(s)←γλZ(s)
      6. S←S′
   3. Until S is terminal.

Sarsa(λ)

The main idea of control is simply to learn action values rather than state values. The idea in Sarsa(λ) is to apply the TD(λ) prediction method to state-action pairs. Let Zt(s,a) denote the trace for state-action pair s,a. Substitute state-action variables for state variables, i.e.

where

and

The complete Sarsa( λ) algorithm is given as follows:

1. Initialize Q(s,a) arbitrarily for all s∈S,a∈A(s)
2. Repeat for each episode:
   
   1. Z(s,a)=0 for all s∈S,a∈A(s)
   2. Repeat for each step of episode:
      
      1. Take action A, observe R, S′.
      2. Choose A′ from S′ using policy derived from Q.
      3. δ←R+γQ(S′,A′)−Q(S,A)
      4. Z(S,A)←Z(S,A)+1
      5. For all s∈S,a∈A(s):
         
         1. Q(s,a)←Q(s,a)+αδZ(s,a)
         2. Z(s,a)←γλZ(s,a)
      6. S←S′,A←A′
   3. Unitl S is terminal.

Q(λ)

There are two different methods have been proposed that combine eligibility traces and Q-Learning: the Watkins’s Q(λ) and Peng’s Q(λ). Here we focus on Watkin’s Q(λ) only and give a brief description of Peng’s Q(λ).

Unlike TD(λ) and Sarsa(λ), Watkins’s Q(λ) does not look ahead all the way to the end of the episode in its backup. It only looks ahead as far as the next exploratory action. For example, suppose the first action, At+1, is exploratory. Watkins’s Q(λ) would still do the one-step update of Qt(St,At) toward Rt+1+γmaxaQ(St+1,a). In general, if At+n is the first exploratory action, then the longest backup is toward

where we assume off-line updating.

The mechanistic or backward view of Watkins’s Q(λ) is also very simple. Eligibility traces are used just as in Sarsa(λ), except that they are set to zero whenever an exploratory action is taken. That is to say. First, the traces for all state-action pairs are either decayed by γλ or, if an exploratory action was taken, set to 0. Second, the trace corresponding to the current state and action is incremented by 1, i.e.

where Ixy is an identity indicator function, equal to 1 if x=y and 0 otherwise. The rest of the algorithm is defined by

where

The complete algorithm is given below:

1. Initialize Q(s,a) arbitrarily, for all s∈S,a∈A(s).
2. Repeat for each episode:
   
   1. Z(s,a)=0 for all s∈S,a∈A(s)
   2. Repeat for each step of episode:
      
      1. Take action A, observe R, S′
      2. Choose A′ from S′ using policy derived from Q.
      3. A∗←argmaxaQ(S′,a), ifA′ ties for the max, then A∗←A′
      4. δ←R+γQ(S′,A∗)−Q(S,A)
      5. Z(S,A)←Z(S,A)+1
      6. For all s∈S,a∈A(s):
         
         1. Q(s,a)←Q(s,a)+αδZ(s,a)
         2. If A′=A∗, then Z(s,a)←γλZ(s,a), else Z(s,a)←0.
      7. S←S′,A←A′
   3. Until S is terminal

Unfortunately, cutting off traces every time an exploratory action is taken loses much of the advantage of using eligibility traces. Peng’s Q(λ) is an alternate version of Q(λ) meant to remedy this, which can be thought of as a hybrid of Sarsa(λ) and Watkins’s Q(λ). In Peng’s Q(λ), there is no distinction between exploratory and greedy actions. Each component beckup is over many steps of actual experiences, and all but the last are capped by a final maximization over actions. For a fixed nongreedy policy, Qt converges to neither qπ nor q∗, but to some hybrid of the two. However, if the policy is gradually made more greedy, then the method may still converge to q∗.

Replacing Traces

In some cases significantly better performance can be obtained by using a slightly modified kind of trace known as replacing trace:

There are several possible ways to generalize replacing eligibility traces for use in control methods. In some cases, the state-action traces are updated by the following: