Skip to Main content Skip to Navigation
Book sections

Approximate Dynamic Programming

R. Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : In any complex or large scale sequential decision making problem, there is a crucial need to use function approximation to represent the relevant functions such as the value function or the policy. The Dynamic Programming (DP) and Reinforcement Learning (RL) methods introduced in previous chapters make the implicit assumption that the value function can be perfectly represented (i.e. kept in memory), for example by using a look-up table (with a finite number of entries) assigning a value to all possible states (assumed to be finite) of the system. Those methods are called exact because they provide an exact computation of the optimal solution of the considered problem (or at least, enable the computations to converge to this optimal solution). However, such methods often apply to toy problems only, since in most interesting applications, the number of possible states is so large (and possibly infinite if we consider continuous spaces) that a perfect representation of the function at all states is impossible. It becomes necessary to approximate the function by using a moderate number of coefficients (which can be stored in a computer), and therefore extend the range of DP and RL to methods using such approximate representations. These approximate methods combine DP and RL methods with function approximation tools.
Complete list of metadatas
Contributor : Philippe Preux <>
Submitted on : Friday, February 7, 2014 - 8:23:45 AM
Last modification on : Tuesday, November 24, 2020 - 2:18:20 PM


  • HAL Id : hal-00943118, version 1



R. Munos. Approximate Dynamic Programming. Olivier Sigaud and Olivier Buffet. Markov Decision Processes in Artificial Intelligence, ISTE Ltd and John Wiley & Sons Inc, pp.67--98, 2010. ⟨hal-00943118⟩



Record views