Approximate reinforcement learning: An overview <s> A. Policy gradient and actor-critic algorithms <s> It is shown how a system consisting of two neuronlike adaptive elements can solve a difficult learning control problem. The task is to balance a pole that is hinged to a movable cart by applying forces to the cart's base. It is argued that the learning problems faced by adaptive elements that are components of adaptive networks are at least as difficult as this version of the pole-balancing problem. The learning system consists of a single associative search element (ASE) and a single adaptive critic element (ACE). In the course of learning to balance the pole, the ASE constructs associations between input and output by searching under the influence of reinforcement feedback, and the ACE constructs a more informative evaluation function than reinforcement feedback alone can provide. The differences between this approach and other attempts to solve problems using neurolike elements are discussed, as is the relation of this work to classical and instrumental conditioning in animal learning studies and its possible implications for research in the neurosciences. <s> BIB001 </s> Approximate reinforcement learning: An overview <s> A. Policy gradient and actor-critic algorithms <s> It is widely accepted that the use of more compact representations than lookup tables is crucial to scaling reinforcement learning (RL) algorithms to real-world problems. Unfortunately almost all of the theory of reinforcement learning assumes lookup table representations. In this paper we address the pressing issue of combining function approximation and RL, and present 1) a function approximator based on a simple extension to state aggregation (a commonly used form of compact representation), namely soft state aggregation, 2) a theory of convergence for RL with arbitrary, but fixed, soft state aggregation, 3) a novel intuitive understanding of the effect of state aggregation on online RL, and 4) a new heuristic adaptive state aggregation algorithm that finds improved compact representations by exploiting the non-discrete nature of soft state aggregation. Preliminary empirical results are also presented. <s> BIB002 </s> Approximate reinforcement learning: An overview <s> A. Policy gradient and actor-critic algorithms <s> Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent of the value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy. <s> BIB003 </s> Approximate reinforcement learning: An overview <s> A. Policy gradient and actor-critic algorithms <s> Autonomous learning is one of the hallmarks of human and animal behavior, and understanding the principles of learning will be crucial in order to achieve true autonomy in advanced machines like humanoid robots. In this paper, we examine learning of complex motor skills with human-like limbs. While supervised learning can offer useful tools for bootstrapping behavior, e.g., by learning from demonstration, it is only reinforcement learning that offers a general approach to the final trial-and-error improvement that is needed by each individual acquiring a skill. Neither neurobiological nor machine learning studies have, so far, offered compelling results on how reinforcement learning can be scaled to the high-dimensional continuous state and action spaces of humans or humanoids. Here, we combine two recent research developments on learning motor control in order to achieve this scaling. First, we interpret the idea of modular motor control by means of motor primitives as a suitable way to generate parameterized control policies for reinforcement learning. Second, we combine motor primitives with the theory of stochastic policy gradient learning, which currently seems to be the only feasible framework for reinforcement learning for humanoids. We evaluate different policy gradient methods with a focus on their applicability to parameterized motor primitives. We compare these algorithms in the context of motor primitive learning, and show that our most modern algorithm, the Episodic Natural Actor-Critic outperforms previous algorithms by at least an order of magnitude. We demonstrate the efficiency of this reinforcement learning method in the application of learning to hit a baseball with an anthropomorphic robot arm. <s> BIB004 </s> Approximate reinforcement learning: An overview <s> A. Policy gradient and actor-critic algorithms <s> In this paper, we suggest a novel reinforcement learning architecture, the Natural Actor-Critic. The actor updates are achieved using stochastic policy gradients employing Amari's natural gradient approach, while the critic obtains both the natural policy gradient and additional parameters of a value function simultaneously by linear regression. We show that actor improvements with natural policy gradients are particularly appealing as these are independent of coordinate frame of the chosen policy representation, and can be estimated more efficiently than regular policy gradients. The critic makes use of a special basis function parameterization motivated by the policy-gradient compatible function approximation. We show that several well-known reinforcement learning methods such as the original Actor-Critic and Bradtke's Linear Quadratic Q-Learning are in fact Natural Actor-Critic algorithms. Empirical evaluations illustrate the effectiveness of our techniques in comparison to previous methods, and also demonstrate their applicability for learning control on an anthropomorphic robot arm. <s> BIB005
In policy gradient methods, the policy is represented using a differentiable parametrization, and gradient updates are performed to find parameters that lead to (locally) maximal returns BIB004 . The policy is usually stochastic, to include exploration: u ∼ h(x, u; ϑ), where ϑ ∈ R N is the policy parameter. Policy gradient methods are usually formalized under the average return criterion, different from the discounted return (1) considered in the other sections. The expected average return from x 0 under the policy parameterized by ϑ is: Under appropriate conditions, see  Ch. 4] , the average return is the same for every initial state (denote it by R ϑ ), and together with a so-called differential V-function, satisfies a variant of Bellman equation. A parameter ϑ * that (locally) maximizes R ϑ must be found. To this end, gradient ascent updates are performed: where α is the step size. The core problem is estimating ∂ R ϑ ∂ϑ . The gradient can be rewritten in a form that allows it to be estimated using simulations similar to rollouts  . An alternative is to explicitly approximate the V-function, leading to actor-critic algorithms (the original actor-critic was given in BIB001 ). The V-function can be found, e.g., by using averagereturn variants of LSTD and LSPE  Sec. 6.6] . Another class of algorithms can be obtained by expressing the gradient in terms of a Q-function. It has been shown BIB003 ,  that such a gradient estimate remains valid even if the Qfunction is linearly approximated, given that a set of so-called compatible BFs, derived from the policy parametrization, are used. Actor-critic variants that exploit such a parameterization have been given, e.g., in BIB003 ,  . The so-called 'natural' policy gradient  leads to faster convergence than the 'vanilla' policy gradient in BIB002 , besides other advantages BIB004 . Natural policy gradients were used to develop natural actor-critic algorithms in, e.g., BIB005 ,  . Policy gradient and actor-critic algorithms provably converge to a local optimum under mild conditions.