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.
Type de document :
Chapitre d'ouvrage
Olivier Sigaud and Olivier Buffet. Markov Decision Processes in Artificial Intelligence, ISTE Ltd and John Wiley & Sons Inc, pp.67--98, 2010
Liste complète des métadonnées

https://hal.inria.fr/hal-00943118
Contributeur : Philippe Preux <>
Soumis le : vendredi 7 février 2014 - 08:23:45
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : hal-00943118, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

186