Quelques majorants de la complexité d'itérations 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é : Étant donné un processus de décision Markovien (PDM) avec $n$ états et $m$ actions, nous étudions le nombre d'étapes requises par l'algorithme itérations sur les politiques (IP) pour converger vers la politique optimale $\gamma$ actualisée. Nous considérons deux variations d'IP: IP-Howard qui change les actions dans tous les états qui ont un avantage strictement positif, et IP-Simplexe qui change uniquement une action dans l'état qui a l'avantage maximal. Nous montrons que IP-Howard termine après au plus $$ n(m-1) \left \lceil \frac{1}{1-\gamma}\log \left( \frac{1}{1-\gamma} \right) \right \rceil = O \left( \frac{ n m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Hansen et al. (2013), tandis que IP-Simplexe termine après au plus $$ n^2(m-1) \left( 1 + \frac{2}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) = O \left( \frac{n^2 m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Ye (2011). Sous des hypothèses structurelles du PDM, nous considérons ensuite des majorants qui sont indépendants du facteur d'actualisation $\gamma$: étant données une mesure $\tau_t$ du temps maximal pour quitter les zones transientes et une mesure $\tau_r$ du temps maximal pour revisiter les états dans les classes récurrentes sous l'ensemble des politiques, nous montrons que IP-Simplexe termine après au plus $$ n^2 (m-1) \left(\lceil \tau_r \log (n \tau_r) \rceil +\lceil \tau_r \log (n \tau_t) \rceil \right) \left[ (m-1) \lceil n \tau_t \log (n \tau_t)\rceil + \lceil n \tau_t \log (n^2 \tau_t ) \rceil\right] =\tilde O \left( n^3 m^2 \tau_t \tau_r \right) $$ itérations. Ceci généralise un résultat récent de Post & Ye (2012) sur les PDMs déterministes dans lesquels on a $\tau_t=\tau_r=n$. Nous expliquons pourquoi des résultats analogues semblent difficiles à obtenir pour IP-Howard. Enfin, sous l'hypothèse supplémentaire (restrictive) que l'espace d'états est partitionné en deux ensembles, correspondant aux états transients (respectivement récurrents) pour toutes les politiques, nous montrons que IP-Simplexe et IP-Howard terminent après au plus $$ n(m-1) \left( \lceil \tau_t \log n \tau_t \rceil + \lceil \tau_r \log n \tau_r \rceil \right) =\tilde O(nm (\tau_t+\tau_r)) $$ itérations.
Type de document :
Communication dans un congrès
JFPDA - 8èmes Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes - 2013, Jul 2013, Lille, France. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00921287
Contributeur : Bruno Scherrer <>
Soumis le : vendredi 20 décembre 2013 - 10:44:14
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : vendredi 21 mars 2014 - 10:30:15

Fichiers

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

Identifiants

  • HAL Id : hal-00921287, version 1

Citation

Bruno Scherrer. Quelques majorants de la complexité d'itérations sur les politiques. JFPDA - 8èmes Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes - 2013, Jul 2013, Lille, France. 2013. 〈hal-00921287〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

175