Concentrating on the second term in the right-hand-side of (31), observe that:

 1 T T X−1 t=0 ∇pXtXt+1(θ) pXtXt+1(θ) X∞ s=T +1 β s−t−1r(Xs)  ≤ 1 T T X−1 t=0  ∇pXtXt+1(θ) pXtXt+1(θ) X∞ s=T +1 β s−t−1|r(Xs)| T X−1 t=0 X∞ ≤ BR T s=T +1 β s−t−1 T X−1 t=0 β T −t = BR T 1 − β = BRβ 1 − β T T (1 − β) 2 → 0 as T → ∞,
where R and B are the bounds on the magnitudes of the rewards and |∇pij | pijfrom Assumptions 2 and 3. Hence,

$$\pi^{\prime}\nabla PJ_{\beta}=\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}\sum_{s=t+1}^{T}\beta^{s-t-1}r(X_{s}).\tag{32}$$

Unrolling the equation for ∆T in the MCG algorithm shows it is equal to

$${\frac{1}{T}}\sum_{t=0}^{T-1}{\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}}\sum_{s=t+1}^{T}\beta^{s-t-1}r(i_{s}),$$

hence ∆T → π
′∇P Jβ w.p.1 as required.

## 6. Estimating The Gradient In Partially Observable Markov Decision Processes

Algorithm 1 applies to any parameterized class of stochastic matrices P(θ) for which we can compute the gradients ∇pij (θ). In this section we consider the special case of P(θ) that arise from a parameterized class of randomized policies controlling a partially observable Markov decision process (**POMDP**). The 'partially observable' qualification means we assume that these policies have access to an observation process that depends on the state, but in general they may not see the state.

Specifically, assume that there are N controls U = {1**, . . . , N**} and M observations Y =
{1**, . . . , M**}. Each u ∈ U determines a stochastic matrix P(u) which does not depend on the parameters θ. For each state i ∈ S, an observation Y ∈ Y is generated independently according to a probability distribution ν(i) over observations in Y. We denote the probability of observation y by νy(i). A *randomized policy* is simply a function µ mapping observations y ∈ Y into probability distributions over the controls U. That is, for each observation y, µ(y) is a distribution over the controls in U. Denote the probability under µ of control u given observation y by µu(y).

To each randomized policy µ(·) and observation distribution ν(·) there corresponds a Markov chain in which state transitions are generated by first selecting an observation y in state i according