
## Algorithm 1.1: Policy-Gradient Algorithm For Regenerative Processes.

1. Set j = 0, r0 = 0, z0 = 0, and ∆0 = 0 (z0, ∆0 ∈ R
K).

2. For each state transition Xt → Xt+1:

- If the episode is finished (that is, Xt+1 = i
that is, $X_{t+1}=i^*$), set. 
$\mathbf{u}$ : $\mathbf{d}$

∆j+1 = ∆j + rtzt,
$j+1=2j+r_{1}x_{t}$, $j=j+1$, $z_{t+1}=0$, $r_{t+1}=0$. * Otherwise, set $z_{t+1}=z_{t}+\frac{\nabla p_{X_{t}}X_{t+1}(\theta)}{p_{X_{t}}X_{t+1}(\theta)}$, $r_{t+1}=\phi(r_{t},X_{t+1})$.  
. If $j=N$ n. 
3. If j = N return ∆N /N, otherwise goto 2.

Examples of recursive performance functions include the sum of a scalar reward over a cycle, r(X0, . . . , XT ) = PT
t=0 r(Xt) where r(i) is a scalar reward associated with state i (this corresponds to η(θ) being the *average reward* multiplied by the expected recurrence time Eθ [T]); the negative length of the cycle (which can be implemented by assigning a reward of −1 to each state, and is used when the task is to mimimize time taken to get to a goal state, since η(θ) in this case is just −Eθ [T]); the *discounted reward* from the start state, r(X0, . . . , XT ) = PT
t=0 α tr(Xt), where α ∈ [0, 1) is the discount factor, and so on.

As Williams (1992) pointed out, a further simplification is possible in the case that rT =
r(X0**, . . . , X**T ) is a sum of scalar rewards r(Xt, t) depending on the state and possibly the time t since the starting state (such as r(Xt, t) = r(Xt), or r(Xt, t) = α tr(Xt) as above). In that case, the update ∆ from a single regenerative cycle may be written as

$$\Delta=\sum_{t=0}^{T-1}\frac{\nabla p_{X_{t}X_{t+1}}(\theta)}{p_{X_{t}X_{t+1}}(\theta)}\left[\sum_{s=0}^{t}r(X_{s},s)+\sum_{s=t+1}^{T}r(X_{s},s)\right].$$
$$(6)$$

Because changes in pXtXt+1(θ) have no influence on the rewards r(Xs, s) associated with earlier states (s ≤ t), we should be able to drop the first term in the parentheses on the right-hand-side and write

$$\Delta=\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}r(X_{s},s).$$
r(Xs, s). (6)
Although the proof is not entirely trivial, this intuition can indeed be shown to be correct.

Equation (6) allows an even simpler recursive formula for estimating the performance gradient. Set z0 = ∆0 = 0, and introduce a new variable s = 0. As before, set zt+1 = zt +
∇pXtXt+1 (θ)/pXtXt+1(θ) and s = s + 1 if Xt+1 6= i
∗, or s = 0 and zt+1 = 0 otherwise. But now, on *each iteration*, set ∆t+1 = r(Xt, s)zt + ∆t. Then ∆t/t is our estimate of ∇η(θ). Since ∆t is updated on every iteration, this suggests that we can do away with ∆t altogether and simply update θ directly: θt+1 = θt+γtr(Xt, s)zt, where the γt are suitable step-sizes4. Proving convergence