Abstract. In this article, we propose and analyze a class of actor-critic algorithms. These are two-time-scale algorithms in which the critic uses temporal difference learning with a linearly parameterized approximation architecture, and the actor is updated in an approximate gradient direction, based on information provided by the critic. We show that the features for the critic should ideally span a subspace prescribed by the choice of parameterization of the actor. We study actor-critic algorithms for Markov decision processes with Polish state and action spaces. We state and prove two results regarding their convergence. Key words. reinforcement learning, Markov decision processes, actor-critic algorithms, stochastic approximation AMS subject classifications. 93E35, 68T05, 62L20 DOI. 10.1137/S0363012901385691 1. Introduction. Many problems in finance, communication networks, operations research, and other fields can be formulated as dynamic programming problems. However, the dimension of the state space in these formulations is often too large for the problem to be tractable. Moreover, the underlying dynamics are seldom known and are often difficult to identify. Reinforcement learning and neuro-dynamic programming [5, 19] methods try to overcome these difficulties by combining simulationbased learning and compact representations of policies and value functions. The vast majority of these methods falls into one of the following two categories: (a) Actor-only methods work with a parameterized family of policies. The gradient of the performance, with respect to the actor parameters, is directly estimated by simulation, and the parameters are updated in a direction of improvement [8, 10, 16, 23] . A possible drawback of such methods is that the gradient estimators may have a large variance. Furthermore, as the policy changes, a new gradient is estimated independently of past estimates. Hence, there is no "learning" in the sense of accumulation and consolidation of older information. (b) Critic-only methods rely exclusively on value function approximation and aim at learning an approximate solution to the Bellman equation, which will then hopefully prescribe a near-optimal policy. Such methods are indirect in the sense that they do not try to optimize directly over a policy space. A method of this type may succeed in constructing a "good" approximation of the value function yet lack reliable guarantees in terms of near-optimality of the resulting policy. Actor-critic methods [2] aim at combining the strong points of actor-only and criticonly methods. The critic uses an approximation architecture and simulation to learn a value function, which is then used to update the actor's policy parameters in a
Konda and Tsitsiklis REF proposed an actor-critic algorithm that uses temporal difference (TD) learning with a linear approximation architecture for training a critic function.
Actor-critic algorithms
SIAM Journal on Control and Optimization
Mathematics Computer Science