Istituto di Studi sui Sistemi Intelligenti per l'Automazione     
Cervellera C., Muselli M. Efficient sampling in approximate dynamic programming algorithms. In: Computational Optimization and Applications, vol. 38 (3) pp. 417 - 443. Springer, 2007.
Dynamic Programming (DP) is known to be a standard optimization tool for solving Stochastic Optimal Control (SOC) problems, either over a finite or an infinite horizon of stages. Under very general assumptions, commonly employed numerical algorithms are based on approximations of the cost-to-go functions, by means of suitable parametric models built from a set of sampling points in the d-dimensional state space. Here the problem of sample complexity, i.e., how "fast" the number of points must grow with the input dimension in order to have an accurate estimate of the cost-to-go functions in typical DP approaches such as value iteration and policy iteration, is discussed. It is shown that a choice of the sampling based on low-discrepancy sequences, commonly used for efficient numerical integration, permits to achieve, under suitable hypotheses, an almost linear sample complexity, thus contributing to mitigate the curse of dimensionality of the approximate DP procedure.
DOI: 10.1007/s10589-007-9054-8
Subject stochastic optimal control problem
dynamic programming
sample complexity
deterministic learning
low-discrepancy sequences

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional