size of the subdominant eigenvalue |λ2|. We showed how the algorithm could be modified to apply to partially observable Markov decision processes controlled by parameterized stochastic policies, with both discrete and continuous control, observation and state spaces (**GPOMDP**). For the finite state case, we proved convergence with probability 1 of both algorithms.

We briefly described extensions to multi-agent problems, policies with internal state, estimating higher-order derivatives, generalizations of the bias result to chains with non-distinct eigenvalues, and a new variance result. There are many avenues for further research. Continuous time results should follow as extensions of the results presented here. The MCG and **GPOMDP** algorithms can be applied to countably or uncountably infinite state spaces; convergence results are also needed in these cases.

In the companion paper (Baxter et al., 2001), we present experimental results showing rapid convergence of the estimates generated by **GPOMDP** to the true gradient ∇η. We give on-line variants of the algorithms of the present paper, and also variants of gradient ascent that make use of the estimates of ∇βη. We present experimental results showing the effectiveness of these algorithms in a variety of problems, including a three-state MDP, a nonlinear physical control problem, and a call-admission problem.

## Acknowledgements

This work was supported by the Australian Research Council, and benefited from the comments of several anonymous referees. Most of this research was performed while the authors were with the Research School of Information Sciences and Engineering, Australian National University.

## Appendix A. A Simple Example Of Policy Degradation In Value-Function Learning

Approximate value-function approaches to reinforcement work by minimizing some form of error between the approximate value function and the true value function. It has long been known that this may not necessarily lead to improved policy performance from the new value function. We include this appendix because it illustrates that this phenomenon can occur in the simplest possible system, a two-state MDP, and also provides some geometric intuition for why the phenomenon arises.

Consider the two-state Markov decision process (MDP) in Figure 1. There are two controls u1, u2 with corresponding transition probability matrices

$$P(u_{1})=\begin{bmatrix}\frac{1}{3}&\frac{2}{3}\\ \frac{1}{3}&\frac{2}{3}\end{bmatrix},\quad P(u_{2})=\begin{bmatrix}\frac{2}{3}&\frac{1}{3}\\ \frac{2}{3}&\frac{1}{3}\end{bmatrix},$$

so that u1 always takes the system to state 2 with probability 2/3, regardless of the starting state (and therefore to state 1 with probability 1/3), and u2 does the opposite. Since state 2 has a reward of 1, while state 1 has a reward of 0, the optimal policy is to always select action u1. Under this policy the stationary distribution on states is [π1, π2**] = [1**/3, 2/3], while the infinite-horizon discounted value of each state i = 1, 2 with discount value α ∈ [0, 1) is

$$J_{\alpha}(i)=\mathbf{E}\left(\sum_{t=0}^{\infty}\alpha^{t}r(X_{t})\Bigg|\,X_{0}=i\right),$$  all state sequences $X_{0},\,X_{1},\,X_{2},\,\ldots$ with $s$.  
where the expectation is over all state sequences X0, X1, X2**, . . .** with state transitions generated according to P(u1). Solving *Bellman's equations:* Jα = r + αP(u1)Jα, where Jα = [Jα(1), Jα**(2)]**′
and r = [r(1), r**(2)]**′yields Jα**(1) =** 2α 3(1−α)
and Jα**(2) = 1 +** 2α 3(1−α)
.