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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00989991
Contributor : Bruno Scherrer <>
Submitted on : Monday, May 12, 2014 - 5:39:03 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Tuesday, August 12, 2014 - 12:10:58 PM

Files

scherrer.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

285

Files downloads

234