Quelques majorants de la complexité d'itérations sur les politiques

Bruno Scherrer (1)

1 MAIA - Autonomous intelligent machine

É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.

Domaines: Complexité [cs.CC]; Recherche opérationnelle [math.OC]; Optimisation et contrôle [math.OC]

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. ⟨hal-00921287⟩