Une étude comparative de quelques schémas d'approximation de type iterations sur les politiques

Bruno Scherrer 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Résumé : Nous considérons le problème du contrôle optimal actualisé à horizon infini formalisé dans le cadre des processus de décision Markoviens. Nous nous focalisons sur plusieurs variations approchées du schéma itération sur les politiques: itérations sur les politiques approché (API), itérations sur les politiques conservatif (CPI), une adaptation naturelle de l'algorithme ''Policy Search by Dynamic Programming'' au cas de l'horizon infini (PSDP), et itérations sur les politiques non-stationnaires (NSPI). Pour tous ces algorithmes, nous décrivons des bornes de performance en fonction de l'erreur $\epsilon$ à chaque itération, et faisons une comparaison en portant une attention particulière aux coefficients de concentration impliqués, au nombre d'itérations et à la mémoire requis. Notre analyse souligne plusieurs points: 1) Les garanties de performance de CPI peuvent être arbitrairement meilleures que celle d'API, mais au prix d'une augmentation---exponentielle en $\frac{1}{\epsilon}$---du nombre d'itérations. 2) PSDP combine les avantages d'API et CPI: sa garantie de performance est similaire à celle de CPI, et elle est obtenue en un nombre d'itérations identique à celui d'API. 3) Contrairement à API qui requiert une mémoire constante, la mémoire dont CPI et PSDP ont besoin est proportionnelle au nombre d'itérations, ce qui peut être problématique lorsque le facteur d'actualisation $\gamma$ est proche de 1 ou lorsque l'erreur d'approximation $\epsilon$ est proche de 0; nous montrons que l'algorithme NSPI permet de faire un compromis entre la bonne mémoire d'API et la meilleure performance de PSDP. Enfin, des simulations numériques de ces schémas algorithmiques confirment notre analyse.
Type de document :
Rapport
[Rapport de recherche] 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00989991
Contributeur : Bruno Scherrer <>
Soumis le : lundi 12 mai 2014 - 17:39:03
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : mardi 12 août 2014 - 12:10:58

Fichiers

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

Identifiants

  • HAL Id : hal-00989991, version 1

Citation

Bruno Scherrer. Une étude comparative de quelques schémas d'approximation de type iterations sur les politiques. [Rapport de recherche] 2014. 〈hal-00989991〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

228