Analyse en norme $L_p$ de l'algorithme d'itérations sur les valeurs avec approximations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle Année : 2007

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

Rémi Munos
  • Fonction : Auteur
  • PersonId : 836863

Résumé

Approximate Value Iteration (AVI) is a method for solving a large Markov Decision Problem by approximating the optimal value function with a sequence of value representations Vn processed by means of the iterations $V_{n+1} = \mathcal{AT}V_n$ where $\mathcal{T}$ is the so-called Bellman operator and $\mathcal{A}$, an approximation operator, which may be implemented by a Supervised Learning (SL) algorithm. Previous results relate the asymptotic performance of AVI to the $L\infty$-norm of the approximation errors induced by the SL algorithm. Unfortunately, the SL algorithm usually perform a minimization problem in $L_p$-norms $(p \geq 1)$, rendering the $L\infty$ performance bounds inadequate. In this paper, we extend these performance bounds to weighted $L_p$-norms. This enables to relate the performance of AVI to the approximation power of the SL algorithm, which guarantees the tightness and pratical interest of these bounds. We illustrate the tightness of the bounds on an optimal replacement problem.
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} = \mathcal{AT}V_n$ où $\mathcal{T}$ est l'opérateur de Bellman et $\mathcal{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 $L\infty$ 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 $L_p (p\geq 1)$, rendant les majorations d'erreur en norme $L\infty$ inadéquates. Dans cet article, nous étendons ces résultats de majoration à des normes $L_p$ 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.
Fichier principal
Vignette du fichier
avi_RIA_final.pdf (193.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00116987 , version 1 (29-11-2006)

Identifiants

  • HAL Id : inria-00116987 , version 1

Citer

Rémi Munos. Analyse en norme $L_p$ 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, 2007, 21. ⟨inria-00116987⟩
250 Consultations
372 Téléchargements

Partager

Gmail Facebook X LinkedIn More