Reinforcement learning in robotics: A survey <s> Function approximation <s> Abstract : Many reinforcement learning systems, such as Q-learning (Watkins, 1989), or advantage updating (Baird, 1993), require that a function f(x,u) be learned, and that the value of argmax f(x,u) be calculated quickly for any given x. The function f could be learned by a function approximation system such as a multilayer preceptron, but the maximum of f for a given x cannot found analytically and is difficult to approximate numerically for high-dimensional u vectors. A new method is proposed, wire fitting, in which a function approximation system is used to learn a set of functions called control wires, and the function f is found by fitting a surface to the control wires. Wire fitting has the following four properties: (1) any continuous f function can represented to any desired accuracy given sufficient parameters; (2) the function f(x,u) can be evaluated quickly; (3) argmax f(x,u) can found exactly in constant time after evaluating f(x,U); (4) wire fitting can incorporate any general function approximation system. These four properties are discussed and it is shown how wire fitting can be combined with a memory-based learning system and Q-learning to control an inverted-pendulum system <s> BIB001 </s> Reinforcement learning in robotics: A survey <s> Function approximation <s> We describe the Fourier basis, a linear value function approximation scheme based on the Fourier series. We empirically demonstrate that it performs well compared to radial basis functions and the polynomial basis, the two most popular fixed bases for linear value function approximation, and is competitive with learned proto-value functions. <s> BIB002 </s> Reinforcement learning in robotics: A survey <s> Function approximation <s> We consider the task of reinforcement learning with linear value function approximation. Temporal difference algorithms, and in particular the Least-Squares Temporal Difference (LSTD) algorithm, provide a method for learning the parameters of the value function, but when the number of features is large this algorithm can over-fit to the data and is computationally expensive. In this paper, we propose a regularization framework for the LSTD algorithm that overcomes these difficulties. In particular, we focus on the case of l1 regularization, which is robust to irrelevant features and also serves as a method for feature selection. Although the l1 regularized LSTD solution cannot be expressed as a convex optimization problem, we present an algorithm similar to the Least Angle Regression (LARS) algorithm that can efficiently compute the optimal solution. Finally, we demonstrate the performance of the algorithm experimentally. <s> BIB003
Function approximation  ) is a family of mathematical and statistical techniques used to represent a function of interest when it is computationally or information-theoretically intractable to represent the function exactly or explicitly (e.g. in tabular form). Typically, in reinforcement learning the function approximation is based on sample data collected during interaction with the environment. Function approximation is critical in nearly every reinforcement learning problem, and becomes inevitable in continuous state ones. In large discrete spaces it is also often impractical to visit or even represent all states and actions, and function approximation in this setting can be used as a means to generalize to neighboring states and actions. Function approximation can be employed to represent policies, value functions, and forward models. Broadly speaking, there are two kinds of function approximation methods: parametric and non-parametric. A parametric function approximator uses a finite set of parameters or arguments with the goal is to find parameters that make this approximation fit the observed data as closely as possible. Examples include linear basis functions and neural networks. In contrast, non-parametric methods expand representational power in relation to collected data and, hence, are not limited by the representation power of a chosen parametrization  . A prominent example that has found much use within reinforcement learning is Gaussian process regression (GPR)  . A fundamental problem with using supervised learning methods developed in the literature for function approximation is that most such methods are designed for independently and identically distributed sample data. However, the data generated by the reinforcement learning process is usually neither independent nor identically distributed. Usually, the function approximator itself plays some role in the data collection process (for instance, by serving to define a policy that we execute on a robot). Linear basis function approximators form one of the most widely used approximate value-function techniques in continuous (and discrete) state-spaces. This is largely due to the simplicity of their representation as well as a convergence theory, albeit limited, for the approximation of value functions based on samples  . Let us briefly take a closer look at a radial basis function network to illustrate this approach. The value-function maps states to a scalar value. The state-space can be covered by a grid of points, each of which correspond to the center of a Gaussian-shaped basis function. The value of the approximated function is the weighted sum of the values of all basis functions at the query point. As the influence of the Gaussian basis functions drops rapidly, the value of the query points will be predominantly influenced by the neighboring basis functions. The weights are set in a way to minimize the error between the observed samples and the reconstruction. For the mean squared error, these weights can be determined by linear regression. BIB003 discussed the benefits of regularization of such linear function approximators to avoid over-fitting. Other possible function approximators for value functions include wire fitting, which BIB001 suggested as an approach that makes continuous action selection feasible. The Fourier basis had been suggested by BIB002 . Even discretizing the statespace can be seen as a form of function approximation where coarse values serve as estimates for a smooth continuous function. One example is tile coding  , where the space is subdivided into (potentially irregularly shaped) regions, called tiling. The number of different tilings determines the resolution of the final approximation. For more examples, please refer to Sections 4.1 and 4.2. Policy search also benefits from a compact representation of the policy as discussed in Section 4.3. Models of the system dynamics can be represented using a wide variety of techniques. In this case, it is often important to model the uncertainty in the model (e.g. by a stochastic model or Bayesian estimates of model parameters) to ensure that the learning algorithm does not exploit model inaccuracies. See Section 6 for a more detailed discussion.