Algorithmes d'itération sur les politiques pour les applications monotones contractantes

摘要: Cette thèse traite de généralisations et de raffinements de l'algorithme d'itération sur les politiques, ou algorithme de Howard, apparu à la fin des années 50 pour la résolution de problèmes de contrôle stochastique. Nous montrons que l'itération sur les politiques permet de résoudre bien d'autres problèmes de décision faisant intervenir des opérateurs de programmation dynamique monotones contractants pour la norme sup. Nous donnons un algorithme universel d'itération sur les politiques, calculant le point fixe d'une application décrite comme infimum d'un ensemble rectangulaire clos inférieurement d'applications monotones contractantes, ce qui fournit un théorème constructif de point-fixe. Pour les opérateurs de jeux déterministes ou stochastiques répétés, nous donnons un algorithme pour le calcul d'un vecteur propre non-linéaire, ou de demi-droites invariantes, permettant de calculer le taux de croissance asymptotique de la fonction valeur du jeu. Les preuves s'appuient sur des résultats de théorie spectrale des applications monotones contractantes, généralisant la théorie spectrale max-plus. Nous spécialisons enfin au cas déterministe l'algorithme classique de Howard, ce qui permet de résoudre des problèmes de théorie des graphes. Pour le calcul d'un circuit de poids moyen maximal, on obtient un algorithme dont la performance est en moyenne (expérimentalement) presque linéaire, ce qui gagne en moyenne un ordre de grandeur par rapport aux algorithmes existants, comme l'algorithme de Karp. Pour les problèmes de plus courts chemins, on obtient un nouvel algorithme de temps 0(nm), où n est le nombre de sommets, et m le nombre d'arcs, qui n'est expérimentalement pas plus rapide que les méthodes usuelles (Bellman, Ford-Bellman), mais permet cependant la détection rapide d'éventuels circuits de poids positifs.