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.
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, 21
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00116987
Contributeur : Rémi Munos <>
Soumis le : mercredi 29 novembre 2006 - 11:59:51
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 15:15:18

Fichier

avi_RIA_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

184