
## 7.3 Higher-Order Derivatives

GPOMDP can be generalized to compute estimates of second and higher-order derivatives of the average reward (assuming they exist), still from a single sample path of the underlying **POMDP**.

To see this for second-order derivatives, observe that if η(θ) = Rq(**θ, x**)r(x) dx for some twicedifferentiable density q(**θ, x**) and performance measure r(x), then

$$\nabla^{2}\eta(\theta)=\int r(x){\frac{\nabla^{2}q(\theta,x)}{q(\theta,x)}}q(\theta,x)\,d x$$

where ∇2 denotes the matrix of second derivatives (Hessian). It can be verified that

$$\frac{\nabla^{2}q(\theta,x)}{q(\theta,x)}=\nabla^{2}\log q(\theta,x)+\left[\nabla\log q(\theta,x)\right]^{2}\tag{40}$$

where the second term on the right-hand-side is the *outer product* between ∇ log q(**θ, x**) and itself
(that is, the matrix with entries ∂/∂θilog q(θ, x)∂/∂θj log q(**θ, x**)). Taking x to be a sequence of states X0, X1**, . . . , X**T between visits to a recurrent state i
∗in a parameterized Markov chain (recall Section 1.1.1), we have q(θ, X**) = Π**T −1 t=0 pXtXt+1(θ), which combined with (40) yields

$${\frac{\nabla^{2}q(\theta,X)}{q(\theta,X)}}=\sum_{t=0}^{T-1}{\frac{\nabla^{2}p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}}-\sum_{t=0}^{T-1}\left[{\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}}\right]^{2}+\left[\sum_{t=0}^{T-1}{\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}}\right]^{2}$$

(the squared terms in this expression are also outer products). From this expression we can derive a **GPOMDP**-like algorithm for computing a biased estimate of the Hessian ∇2η(θ), which involves maintaining—in addition to the usual eligibility trace zt—a second *matrix* trace updated as follows:

$$Z_{t+1}=\beta Z_{t}+\frac{\nabla^{2}p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}-\left[\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}\right]^{2}.$$

```
After T time steps the algorithm returns the average so far of r(Xt)-Zt + z
                                                                      2
                                                                      t
                                                                       where the second term

```

is again an outer product. Computation of higher-order derivatives could be used in second-order gradient methods for optimization of policy parameters.

## 7.4 Bias And Variance Bounds

Theorem 3 provides a bound on the *bias* of ∇βη(θ) relative to ∇η(θ) that applies when the underlying Markov chain has distinct eigenvalues. We have extended this result to arbitrary Markov chains
(Bartlett & Baxter, 2001). However, the extra generality comes at a price, since the latter bound involves the number of states in the chain, whereas Theorem 3 does not. The same paper also supplies a proof that the variance of **GPOMDP** scales as 1/(1 − β)
2, providing a formal justification for the interpretation of β in terms of bias/variance trade-off.

## 8. Conclusion

We have presented a general algorithm (MCG) for computing arbitrarily accurate approximations to the gradient of the average reward in a parameterized Markov chain. When the chain's transition matrix has distinct eigenvalues, the accuracy of the approximation was shown to be controlled by the