Proof. Recalling equation (17) and the discussion preceeding it, we have11

$$\nabla\eta=\pi^{\prime}\nabla P\sum_{t=0}^{\infty}\left[P^{t}-e\pi^{\prime}\right]r.$$

But ∇P e = ∇(P e) = ∇**(1) = 0** since P is a stochastic matrix, so (23) can be rewritten as

$$\nabla\eta=\pi^{\prime}\left[\sum_{t=0}^{\infty}\nabla P P^{t}\right]r.$$
$$(23)$$
$$(24)$$
$$(25)$$
r. (24)
Now let β ∈ [0, 1] be a discount factor and consider the expression

$$f(\beta):=\pi^{\prime}\left[\sum_{t=0}^{\infty}\nabla P(\beta P)^{t}\right]r$$

Clearly ∇η **= lim**β→1 f(β). To complete the proof we just need to show that f(β) = ∇βη.

Since (βP)
t = β tP
t → β teπ′ → 0, we can invoke the observation before (16) to write

$$\sum_{t=0}^{\infty}(\beta P)^{t}=\left[I-\beta P\right]^{-1}.$$

In particular, P∞
t=0(βP)
tconverges, so we can take ∇P back out of the sum in the right-hand-side of (25) and write12

$$f(\beta)=\pi^{\prime}\nabla P\left[\sum_{t=0}^{\infty}\beta^{t}P^{t}\right]r.$$  $f(\beta)=\pi^{\prime}\nabla P\,I_{t}=\nabla\gamma_{t}$
$$(26)$$
$$\blacksquare$$
But $\left[\sum_{t=0}^{\infty}\beta^t P^t\right]r=J_\beta.$ Thus $f(\beta)=\pi^\prime\nabla PJ_\beta=\nabla_\beta\eta.$
Theorem 2 shows that ∇βη is a good approximation to the gradient as β approaches 1, but it turns out that values of β very close to 1 lead to large variance in the estimates of ∇βη that we describe in the next section. However, the following theorem shows that 1 − β need not be too small, provided the transition probability matrix P(θ) has distinct eigenvalues, and the Markov chain has a short *mixing time*. From any initial state, the distribution over states of a Markov chain converges to the stationary distribution, provided the assumption (Assumption 1) about the existence and uniqueness of the stationary distribution is satisfied (see, for example, Lancaster & Tismenetsky, 1985, Theorem 15.8.1, p. 552). The spectral resolution theorem (Lancaster & Tismenetsky, 1985, Theorem 9.5.1, p. 314) implies that the distribution converges to stationarity at an exponential rate, and the time constant in this convergence rate (the mixing time) depends on the eigenvalues of the transition probability matrix. The existence of a unique stationary distribution implies that the