
## 5. Estimating The Gradient In Parameterized Markov Chains

Algorithm 1 introduces MCG (Markov Chain Gradient), an algorithm for estimating the approximate gradient ∇βη from a single on-line sample path X0, X1**, . . .** from the Markov chain M(θ).

MCG requires only 2K reals to be stored, where K is the dimension of the parameter space: K
parameters for the eligibility trace zt, and K parameters for the gradient estimate ∆t. Note that after T time steps ∆T is the average so far of r(Xt)zt,

$$\Delta_{T}={\frac{1}{T}}\sum_{t=0}^{T-1}z_{t}r(X_{t}).$$

## Algorithm 1 The Mcg (Markov Chain Gradient) Algorithm

1: **Given:**
- Parameter θ ∈ R
K.

- Parameterized class of stochastic matrices P = {P(θ): θ ∈ R
K} satisfying Assumptions 3 and 1.

- β ∈ [0, 1).

- Arbitrary starting state X0.

- State sequence X0, X1**, . . .** generated by M(θ) (i.e. the Markov chain with transition probabilities P(θ)).

- Reward sequence r(X0), r(X1)**, . . .** satisfying Assumption 2.
2: Set z0 = 0 and ∆0 = 0 (z0, ∆0 ∈ R
K).

3: for each state Xt+1 visited do 4: zt+1 = βzt +
∇pXtXt+1 (θ)
pXtXt+1(θ)
5: ∆t+1 = ∆t +1 t+1 [r(Xt+1)zt+1 − ∆t]
6: **end for**
Theorem 4. *Under Assumptions 1, 2 and 3, the* MCG *algorithm starting from any initial state* X0 will generate a sequence ∆0, ∆1, . . . , ∆t**, . . .** *satisfying*

$$\operatorname*{lim}_{t\to\infty}\Delta_{t}=\nabla_{\beta}\eta\quad\mathrm{w.p.1}.$$

∆t = ∇βη w.p.1. (29)
Proof. Let {Xt} = {X0, X1**, . . .** } denote the random process corresponding to M(θ). If X0 ∼ π then the entire process is stationary. The proof can easily be generalized to arbitrary initial distributions using the fact that under Assumption 1, {Xt} is asymptotically stationary. When {Xt} is

$$(29)$$
