
$$(12)^{\frac{1}{2}}$$

ing both the theoretical results of the present paper on a toy problem, and practical aspects of the algorithms on a number of more realistic problems.

## 2. The Reinforcement Learning Problem

We model reinforcement learning as a Markov decision process (MDP) with a finite state space

S = {1**, . . . , n**}, and a stochastic matrix7 P = [pij ] giving the probability of transition from state
i to state j. Each state i has an associated reward8r(i). The matrix P belongs to a parameterized
class of stochastic matrices, P := {P(θ): θ ∈ R
K}. Denote the Markov chain corresponding to
P(θ) by M(θ). We assume that these Markov chains and rewards satisfy the following assumptions:
Assumption 1. *Each* P(θ) ∈ P *has a unique stationary distribution* π(θ) := [π(θ, 1), . . . , π(**θ, n**)]′
satisfying the balance equations
$$\pi^{\prime}(\theta)P(\theta)=\pi^{\prime}(\theta)$$
′(θ) (12)
(throughout π
′ *denotes the transpose of* π).
Assumption 2. The magnitudes of the rewards, |r(i)|*, are uniformly bounded by* R < ∞ *for all*
states i.
Assumption 1 ensures that the Markov chain forms a single recurrent class for all parameters θ.
Since any finite-state Markov chain always ends up in a recurrent class, and it is the properties of
this class that determine the long-term average reward, this assumption is mainly for convenience so that we do not have to include the recurrence class as a quantifier in our theorems. However, when we consider gradient-ascent algorithms Baxter et al. (2001), this assumption becomes more
restrictive since it guarantees that the recurrence class cannot change as the parameters are adjusted.
Ordinarily, a discussion of MDPs would not be complete without some mention of the actions
available in each state and the space of policies available to the learner. In particular, the parameters
θ would usually determine a policy (either directly or indirectly via a value function), which would
then determine the transition probabilities P(θ). However, for our purposes we do not care how
the dependence of P on θ arises, just that it satisfies Assumption 1 (and some differentiability
assumptions that we shall meet in the next section). Note also that it is easy to extend this setup
to the case where the rewards also depend on the parameters θ or on the transitions i → j. It is
equally straightforward to extend our algorithms and results to these cases. See Section 6.1 for an illustration.
The goal is to find a θ ∈ R
K maximizing the *average reward*:
$\eta(\theta):=\lim\limits_{T\to\infty}\mathbf{E}_{\theta}\left[\frac{1}{T}\sum\limits_{t=0}^{T-1}r(X_{t})\right]X_{0}=i\right],$  action over all sequences $X_{0},X_{1},\ldots,$ with 
where Eθ denotes the expectation over all sequences X0, X1**, . . . ,** with transitions generated according to P(θ). Under Assumption 1, η(θ) is independent of the starting state i and is equal to

$$\eta(\theta)=\sum_{i=1}^{n}\pi(\theta,i)r(i)=\pi^{\prime}(\theta)r,$$
$$(13)$$
