Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> We propose a new approach to reinforcement learning for control problems which combines value-function approximation with linear architectures and approximate policy iteration. This new approach is motivated by the least-squares temporal-difference learning algorithm (LSTD) for prediction problems, which is known for its efficient use of sample experiences compared to pure temporal-difference algorithms. Heretofore, LSTD has not had a straightforward application to control problems mainly because LSTD learns the state value function of a fixed policy which cannot be used for action selection and control without a model of the underlying process. Our new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework. LSPI is a model-free, off-policy method which can use efficiently (and reuse in each iteration) sample experiences collected in any manner. By separating the sample collection method, the choice of the linear approximation architecture, and the solution method, LSPI allows for focused attention on the distinct elements that contribute to practical reinforcement learning. LSPI is tested on the simple task of balancing an inverted pendulum and the harder task of balancing and riding a bicycle to a target location. In both cases, LSPI learns to control the pendulum or the bicycle by merely observing a relatively small number of trials where actions are selected randomly. LSPI is also compared against Q-learning (both with and without experience replay) using the same value function architecture. While LSPI achieves good performance fairly consistently on the difficult bicycle task, Q-learning variants were rarely able to balance for more than a small fraction of the time needed to reach the target location. <s> BIB001 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> We introduce two new temporal diffence (TD) algorithms based on the theory of linear least-squares function approximation. We define an algorithm we call Least-Squares TD (LS TD) for which we prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters. We then define a recursive version of this algorithm, Recursive Least-Squares TD (RLS TD). Although these new TD algorithms require more computation per time-step than do Sutton's TD(λ) algorithms, they are more efficient in a statistical sense because they extract more information from training experiences. We describe a simulation experiment showing the substantial improvement in learning rate achieved by RLS TD in an example Markov prediction problem. To quantify this improvement, we introduce theTD error variance of a Markov chain, ωTD, and experimentally conclude that the convergence rate of a TD algorithm depends linearly on ωTD. In addition to converging more rapidly, LS TD and RLS TD do not have control parameters, such as a learning rate parameter, thus eliminating the possibility of achieving poor performance by an unlucky choice of parameters. <s> BIB002 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> Approximate Policy Iteration (API) is a reinforcement learning paradigm that is able to solve high-dimensional, continuous control problems. We propose to exploit API for the closed-loop learning of mappings from images to actions. This approach requires a family of function approximators that maps visual percepts to a real-valued function. For this purpose, we use Regression Extra-Trees, a fast, yet accurate and versatile machine learning algorithm. The inputs of the Extra-Trees consist of a set of visual features that digest the informative patterns in the visual signal. We also show how to parallelize the Extra-Tree learning process to further reduce the computational expense, which is often essential in visual tasks. Experimental results on real-world images are given that indicate that the combination of API with Extra-Trees is a promising framework for the interactive learning of visual tasks. <s> BIB003 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> In this paper we consider the problem of finding a near-optimal policy in a continuous space, discounted Markovian Decision Problem (MDP) by employing value-function-based methods when only a single trajectory of a fixed policy is available as the input. We study a policy-iteration algorithm where the iterates are obtained via empirical risk minimization with a risk function that penalizes high magnitudes of the Bellman-residual. Our main result is a finite-sample, high-probability bound on the performance of the computed policy that depends on the mixing rate of the trajectory, the capacity of the function set as measured by a novel capacity concept (the VC-crossing dimension), the approximation power of the function set and the controllability properties of the MDP. Moreover, we prove that when a linear parameterization is used the new algorithm is equivalent to Least-Squares Policy Iteration. To the best of our knowledge this is the first theoretical result for off-policy control learning over continuous state-spaces using a single trajectory. <s> BIB004 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> In this paper we consider approximate policy-iteration-based reinforcement learning algorithms. In order to implement a flexible function approximation scheme we propose the use of non-parametric methods with regularization, providing a convenient way to control the complexity of the function approximator. We propose two novel regularized policy iteration algorithms by adding L2-regularization to two widely-used policy evaluation methods: Bellman residual minimization (BRM) and least-squares temporal difference learning (LSTD). We derive efficient implementation for our algorithms when the approximate value-functions belong to a reproducing kernel Hilbert space. We also provide finite-sample performance bounds for our algorithms and show that they are able to achieve optimal rates of convergence under the studied conditions. <s> BIB005 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <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> BIB006 </s> Approximate reinforcement learning: An overview <s> A. Offline policy iteration <s> In the context of large space MDPs with linear value function approximation, we introduce a new approximate version of λ-Policy Iteration (Bertsekas & Ioffe, 1996), a method that generalizes Value Iteration and Policy Iteration with a parameter λ ∈ (0,1). Our approach, called Least-Squares λ Policy Iteration, generalizes LSPI (Lagoudakis & Parr, 2003) which makes efficient use of training samples compared to classical temporal-differences methods. The motivation of our work is to exploit the λ parameter within the least-squares context, and without having to generate new samples at each iteration or to know a model of the MDP. We provide a performance bound that shows the soundness of the algorithm. We show empirically on a simple chain problem and on the Tetris game that this λ parameter acts as a bias-variance trade-off that may improve the convergence and the performance of the policy obtained. <s> BIB007
In Sec. III, it was assumed that greedy actions can be computed efficiently. This means the policy improvement step (8) of approximate policy iteration can be performed exactly and efficiently, on demand for every state where an improved action is necessary. Hence, we mainly focus on the policy evaluation problem. One class of offline policy evaluation can be obtained similarly to offline value iteration, e.g., by performing iterative updates based on the Bellman equation for Q h (3). Such a fitted policy evaluation algorithm was proposed in BIB003 . However, if a linear Q-function parametrization (10) is used, Q(x, u; θ) = φ T (x, u)θ, a more specialized class of policy evaluation algorithms can be obtained. Consider the following mapping derived from the Bellman equation (3): Classical policy evaluation aims to solve the Bellman equation , which is equivalent to (3). Projected policy evaluation algorithms instead look for a solution of the projected Bellman equation  Ch. 6] : where the mapping P w performs a weighted least-squares projection onto the space of representable Q-functions, i.e., on φ T (x, u)θ | θ ∈ R n . The weight function w : X × U → [0, 1] controls the distribution of the approximation error, and is also used as a probability distribution, so it must satisfy x,u w(x, u) = 1. To guarantee that P w (T h ) is a contraction  Another important class of policy evaluation approaches aims to minimize the Bellman error (residual), which is the difference between the two sides of the Bellman equation: , see, e.g., BIB004 , BIB005 . and (16) has a unique solution, the weight of each stateaction pair should be the steady-state probability of this pair occurring along an infinitely-long trajectory generated with h [6, Sec. 6.3]. In practice, however, (16) also has meaningful solutions for other weight functions BIB001 . By exploiting the linearity of the approximator in the parameters in combination with the linearity of the mapping T h in the Q-values, (16) can eventually be written as a linear equation in the parameter vector: Γθ h = z, where Γ ∈ R n×n and z ∈ R n can be estimated from transition samples. Consider a batch of N samples (11), so that the sampling probability of each pair (x, u) is w(x, u). The estimates of Γ and z are initialized to zeros and updated with: Least-squares temporal difference for Q-functions (LSTD-Q) BIB001 , BIB002 is a policy evaluation algorithm that processes all the samples using (17) and then solves: By combining LSTD-Q policy evaluation with exact policy improvements BIB006 , an offline algorithm for approximate policy iteration is obtained, called least-squares policy iteration BIB001 , BIB007 . An alternative to LSTD-Q is the so-called least-squares policy evaluation for Q-functions (LSPE-Q)  ,  .