of such an algorithm is not as straightforward as normal stochastic gradient algorithms because the updates r(Xt)zt are not in the gradient direction (in expectation), although the sum of these updates over a regenerative cycle are. Marbach and Tsitsiklis (1998) provide the only convergence proof that we know of, albeit for a slightly different update of the form θt+1 = θt + γt[r(Xt, s) − ηˆ(θt)] zt, where ηˆ(θt) is a moving estimate of the expected performance, and is also updated on-line (this update was first suggested in the context of **POMDP**s by Jaakkola et al. (1995)).

Marbach and Tsitsiklis (1998) also considered the case of θ-dependent rewards (recall the discussion after (3)), as did Baird and Moore (1999) with their "**VAPS**" algorithm (Value And Policy Search). This last paper contains an interesting insight: through suitable choices of the performance function r(X0, . . . , XT , θ), one can combine policy-gradient search with approximate value function methods. The resulting algorithms can be viewed as *actor-critic* techniques in the spirit of Barto et al. (1983); the policy is the *actor* and the value function is the *critic*. The primary motivation is to reduce variance in the policy-gradient estimates. Experimental evidence for this phenomenon has been presented by a number of authors, including Barto et al. (1983), Kimura and Kobayashi (1998a), and Baird and Moore (1999). More recent work on this subject includes that of Sutton et al. (2000) and Konda and Tsitsiklis (2000). We discuss the use of **VAPS**-style updates further in Section 6.2.

So far we have not addressed the question of how the parameterized state-transition probabilities pXtXt+1(θ) arise. Of course, they could simply be generated by parameterizing the matrix of transition probabilities directly. Alternatively, in the case of MDPs or **POMDP**s, state transitions are typically generated by feeding an *observation* Ytthat depends stochastically on the state Xt into a parameterized *stochastic policy*, which selects a *control* Ut at random from a set of available controls (approximate value-function based approaches that generate controls stochastically via some form of lookahead also fall into this category). The distribution over successor states pXtXt+1(Ut) is then a fixed function of the control. If we denote the probability of control ut given parameters θ and observation yt by µut(**θ, y**t), then all of the above discussion carries through with
∇pXtXt+1 (θ)/pXtXt+1(θ) replaced by ∇µUt(θ, Yt)/µUt(**θ, Y**t). In that case, Algorithm 1.1 is precisely Williams' **REINFORCE** algorithm.

Algorithm 1.1 and the variants above have been extended to cover multiple agents (Peshkin et al., 2000), policies with internal state (Meuleau et al., 1999), and importance sampling methods
(Meuleau et al., 2000). We also refer the reader to the work of Rubinstein and Shapiro (1993) and Rubinstein and Melamed (1998) for in-depth analysis of the application of the likelihood-ratio method to Discrete-Event Systems (DES), in particular networks of queues. Also worth mentioning is the large literature on Infinitesimal Perturbation Analysis (IPA), which seeks a similar goal of estimating performance gradients, but operates under more restrictive assumptions than the likelihoodratio approach; see, for example, Ho and Cao (1991).

## 1.1.2 Biased Estimates Of The Performance Gradient

All the algorithms described in the previous section rely on an identifiable recurrent state i
∗, either to update the gradient estimate, or in the case of the on-line algorithm, to zero the eligibility trace z. This reliance on a recurrent state can be problematic for two main reasons:
1. The *variance* of the algorithms is related to the recurrence time between visits to i
∗, which will typically grow as the state space grows. Furthermore, the time between visits depends on