Analyse en norme Lp de l'algorithme d'itérations sur les valeurs avec approximations

Rémi 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
Résumé : L'algorithme d'itérations sur les valeurs avec approximations (IVA) permet de résoudre des problèmes de décision markoviens en grande dimension en approchant la fonction valeur optimale par une séquence de représentations V(n) calculées itérativement selon V(n+1) = A T V(n) où T est l'opérateur de Bellman et A un opérateur d'approximation, ce dernier pouvant s'implémenter selon un algorithme d'apprentissage supervisé (AS). Les résultats usuels établissent des bornes sur la performance de IVA en fonction de la norme sup des erreurs d'approximation induites par l'algorithme d'AS. Cependant, un algorithme d'AS résout généralement un problème de régression en minimisation une norme Lp (p>=1), rendant les majorations d'erreur en norme sup inadéquates. Dans cet article, nous étendons ces résultats de majoration à des normes Lp pondérées. Ceci permet d'exprimer les performances de l'algorithme IVA en fonction de la puissance d'approximation de l'algorithme d'AS, ce qui garantit la finesse et l'intérêt applicatif de ces bornes. Nous illustrons numériquement la qualité des majorations obtenues pour un problème de remplacement optimal.
Document type :
Journal articles
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00116987
Contributor : Rémi Munos <>
Submitted on : Wednesday, November 29, 2006 - 11:59:51 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, September 20, 2012 - 3:15:18 PM

File

avi_RIA_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00116987, version 1

Collections

Citation

Rémi Munos. Analyse en norme Lp de l'algorithme d'itérations sur les valeurs avec approximations. Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, 21. ⟨inria-00116987⟩

Share

Metrics

Record views

415

Files downloads

295