the parameters of the policy, and states that are frequently visited for the initial value of the parameters may become very rare as performance improves.

2. In situations of *partial observability* it may be difficult to estimate the underlying states, and therefore to determine when the gradient estimate should be updated, or the eligibility trace zeroed.
If the system is available only through simulation, it seems difficult (if not impossible) to obtain unbiased estimates of the gradient direction without access to a recurrent state. Thus, to solve 1 and 2, we must look to *biased* estimates. Two principle techniques for introducing bias have been proposed, both of which may be viewed as artificial truncations of the eligibility trace z. The first method takes as a starting point the formula5for the eligibility trace at time t:

$$z_{t}=\sum_{s=0}^{t-1}{\frac{\nabla p_{X_{s}X_{s+1}}(\theta)}{p_{X_{s}X_{s+1}}(\theta)}}$$

and simply truncates it at some (fixed, not random) number of terms n looking backwards (Glynn, 1990; Rubinstein, 1991, 1992; Cao & Wan, 1998):

$$z_{t}(n):=\sum_{s=t-n}^{t-1}\frac{\nabla p_{X_{s}X_{s+1}}(\theta)}{p_{X_{s}X_{s+1}}(\theta)}.$$
$${\mathrm{sition~}}X_{t}\to X_{t+1}{\mathrm{~by~}}$$

The eligibility trace zt(n) is then updated after each transition Xt → Xt+1 by

$$z_{t+1}(n)=z_{t}(n)+{\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}}-{\frac{\nabla p_{X_{t-n}X_{t-n+1}}(\theta)}{p_{X_{t-n}X_{t-n+1}}(\theta)}},$$

and in the case of state-based rewards r(Xt), the estimated gradient direction after T steps is

$$\hat{\nabla}_{n}\eta(\theta):=\frac{1}{T-n+1}\sum_{t=n}^{T}z_{t}(n)r(X_{t}).$$
$$\mathbf{\Phi}(7)$$
$$(8)$$
$$(9)$$

Unless n exceeds the maximum recurrence time (which is infinite in an ergodic Markov chain),
∇ˆnη(θ) is a biased estimate of the gradient direction, although as n → ∞, the bias approaches zero.

However the *variance* of ∇ˆnη(θ) diverges in the limit of large n. This illustrates a natural trade-off in the selection of the parameter n: it should be large enough to ensure the bias is acceptable (the expectation of ∇ˆnη(θ) should at least be within 90◦ of the true gradient direction), but not so large that the variance is prohibitive. Experimental results by Cao and Wan (1998) illustrate nicely this bias/variance trade-off.

One potential difficulty with this method is that the likelihood ratios ∇pXsXs+1(θ)/pXsXs+1(θ)
must be remembered for the previous n time steps, requiring storage of Kn parameters. Thus, to obtain small bias, the memory may have to grow without bound. An alternative approach that requires a fixed amount of memory is to *discount* the eligibility trace, rather than truncating it:

$$z_{t+1}(\beta):=\beta z_{t}(\beta)+\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)},\tag{10}$$
