Policy Gradient Methods for Reinforcement Learning with ...

1 Advances in Neural Information Processing Systems 12, pp. 1057{1063, MIT Press, 2000 Policy Gradient Methods forReinforcement Learning with FunctionApproximationRichard S. Sutton, David McAllester, Satinder Singh, Yishay MansourAT&T Labs { Research, 180 Park Avenue, Florham Park, NJ 07932 AbstractFunction approximation is essential to Reinforcement Learning , butthe standard approach of approximating a value function and deter-mining a Policy from it has so far proven theoretically this paper we explore an alternative approach in which the policyis explicitly represented by its own function approximator, indepen-dent of the value function, and is updated according to the gradientof expected reward with respect to the Policy parameters.}}

2 Williams'sREINFORCE method and actor{critic Methods are examples of thisapproach. Our main new result is to show that the Gradient canbe written in a form suitable for estimation from experience aidedby an approximate action-value or advantage function. Using thisresult, we prove for the rst time that a version of Policy iterationwith arbitrary di erentiable function approximation is convergent toa locally optimal applications of Reinforcement Learning (RL) require the use of generalizing func-tion approximators such neural networks, decision-trees, or instance-based dominant approach for the last decade has been thevalue-functionapproach, inwhich all function approximation e ort goes into estimating a value function, withthe action-selection Policy represented implicitly as the \greedy" Policy with respectto the estimated values ( , as the Policy that selects in each state the action withhighest estimated value).}

3 The value-function approach has worked well in many appli-cations, but has several limitations. First, it is oriented toward nding deterministicpolicies, whereas the optimal Policy is often stochastic, selecting di erent actions withspeci c probabilities ( , see Singh, Jaakkola, and Jordan, 1994). Second, an arbi-trarily small change in the estimated value of an action can cause it to be, or not be,selected. Such discontinuous changes have been identi ed as a key obstacle to estab-lishing convergence assurances for algorithms following the value-function approach(Bertsekas and Tsitsiklis, 1996). For example, Q- Learning , Sarsa, and dynamic pro-gramming Methods have all been shown unable to converge to any Policy for simpleMDPs and simple function approximators (Gordon, 1995, 1996; Baird, 1995; Tsit-siklis and van Roy, 1996; Bertsekas and Tsitsiklis, 1996).

4 This can occur even if thebest approximation is found at each step before changing the Policy , and whether thenotion of \best" is in the mean-squared-error sense or the slightly di erent senses ofresidual- Gradient , temporal-di erence, and dynamic-programming this paper we explore an alternative approach to function approximation in RL. Rather than approximating a value function and using that to compute a determinis-tic Policy , we approximate a stochastic Policy directly using an independent functionapproximator with its own parameters. For example, the Policy might be representedby a neural network whose input is a representation of the state, whose output isaction selection probabilities, and whose weights are the Policy parameters.

5 Let denote the vector of Policy parameters and the performance of the correspondingpolicy ( , the average reward per step). Then, in thepolicy gradientapproach, thepolicy parameters are updated approximately proportional to the Gradient : @ @ ;(1)where is a positive-de nite step size. If the above can be achieved, then canusually be assured to converge to a locally optimal Policy in the performance measure . Unlike the value-function approach, here small changes in can cause only smallchanges in the Policy and in the state-visitation this paper we prove that an unbiased estimate of the Gradient (1) can be obtainedfrom experience using an approximate value function satisfying certain 's (1988, 1992) REINFORCE algorithm also nds an unbiased estimate ofthe Gradient , but without the assistance of a learned value function.

6 REINFORCE learns much more slowly than RL Methods using value functions and has receivedrelatively little attention. Learning a value function and using it to reduce the varianceof the Gradient estimate appears to be essential for rapid Learning . Jaakkola, Singhand Jordan (1995) proved a result very similar to ours for the special case of functionapproximation corresponding to tabular POMDPs. Our result strengthens theirs andgeneralizes it to arbitrary di erentiable function approximators. Konda and Tsitsiklis(in prep.) independently developed a very simialr result to ours. See also Baxter andBartlett (in prep.) and Marbach and Tsitsiklis (1998).Our result also suggests a way of proving the convergence of a wide variety of algo-rithms based on \actor-critic" or Policy -iteration architectures ( , Barto, Sutton,and Anderson, 1983; Sutton, 1984; Kimura and Kobayashi, 1998).

7 In this paper wetake the rst step in this direction by proving for the rst time that a version ofpolicy iteration with general di erentiable function approximation is convergent toa locally optimal Policy . Baird and Moore (1999) obtained a weaker but super -cially similar result for their VAPS family of Methods . Like Policy - Gradient Methods ,VAPS includes separately parameterized Policy and value functions updated by gra-dient Methods . However, VAPS Methods do not climb the Gradient of performance(expected long-term reward), but of a measure combining performance and value-function accuracy. As a result, VAPS does not converge to a locally optimal Policy ,except in the case that no weight is put upon value-function accuracy, in which caseVAPS degenerates to REINFORCE.

8 Similarly, Gordon's (1995) tted value iterationis also convergent and value-based, but does not nd a locally optimal Policy Gradient TheoremWe consider the standard Reinforcement Learning framework (see, , Sutton andBarto, 1998), in which a Learning agent interacts with a Markov decision process(MDP). The state, action, and reward at each timet2f0;1;2;:::gare denotedst2S,at2A, andrt2<respectively. The environment's dynamics are characterized bystate transition probabilities,Pass0=Prfst+1=s0jst=s;at=a g, and expected re-wardsRas=Efrt+1jst=s;at=ag,8s;s02S;a2 A. The agent's decision makingprocedure at each time is characterized by a Policy , (s;a; )=Prfat=ajst=s; g,8s2S;a2A, where 2<l, forl<<jSj, is a parameter vector.

9 We assume that is di entiable with respect to its parameter, , that@ (s;a)@ exists. We also usuallywrite just (s;a) for (s;a; ). With function approximation, two ways of formulating the agent's objective are use-ful. One is the average reward formulation, in which policies are ranked according totheir long-term expected reward per step, ( ): ( ) = limn!11nEfr1+r2+ +rnj g=Xsd (s)Xa (s;a)Ras;whered (s) = limt!1 Prfst=sjs0; gis the stationary distribution of states under , which we assume exists and is independent ofs0for all policies. In the averagereward formulation, the value of a state{action pair given a Policy is de ned asQ (s;a)=1Xt=1 Efrt ( )js0=s;a0=a; g;8s2S;a2A:The second formulation we cover is that in which there is a designated start states0, and we care only about the long-term reward obtained from it.}

10 We will give ourresults only once, but they will apply to this formulation as well under the de nitions ( )=E 1Xt=1 t 1rt s0; andQ (s;a)=E 1Xk=1 k 1rt+k st=s;at=a; :where 2[0;1] is a discount rate ( = 1 is allowed only in episodic tasks). In thisformulation, we de ned (s) as a discounted weighting of states encountered startingats0and then following :d (s)=P1t=0 tPrfst=sjs0; rst result concerns the Gradient of the performance metric with respect to thepolicy parameter:Theorem 1 ( Policy Gradient ). For any MDP, in either the average-reward orstart-state formulations,@ @ =Xsd (s)Xa@ (s;a)@ Q (s;a):(2)Proof: See the way of expressing the Gradient was rst discussed for the average-reward formu-lation by Marbach and Tsitsiklis (1998), based on a related expression in terms of thestate-value function due to Jaakkola, Singh, and Jordan (1995) and Cao and Chen(1997).