Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Dans cette thèse, nous développons des algorithmes accélérés pour les processus de décision Markoviens (MDP) et plus généralement pour les jeux stochastiques à somme nulle (SG). Nous abordons également les problèmes de meilleure approximation qui se posent en géométrie tropicale.La programmation dynamique est l'une des principales approches utilisées pour résoudre les problèmes MDP et SG. Elle permet de transformer un jeu en un problème de point fixe faisant intervenir un opérateur appelé opérateur de Shapley (ou opérateur de Bellman dans le cas de MDP). L'itération sur les valeurs (VI) et l'itération sur les politiques (PI) sont les deux principaux algorithmes permettant de résoudre ces problèmes de point fixe. Cependant, dans le cas d'instances à grande échelle, ou lorsque l'on veut résoudre un problème à paiement moyen (où il n'y a pas de facteur d'escompte pour les paiements reçus dans le futur), les méthodes classiques deviennent lentes.Dans la première partie de cette thèse, nous développons deux raffinements des algorithmes classiques d'itération sur les valeurs ou sur les politiques. Nous proposons d'abord une version accélérée de l'itération sur les valeurs (AVI) permettant de résoudre des problèmes de point fixe affines avec des matrices non auto-adjointes, ainsi qu'une version accélérée de l'itération sur les politiques (API) pour MDP, basée sur AVI. Cette accélération étend l'algorithme de gradient accéléré de Nesterov à une classe de problèmes de point fixe qui ne peuvent pas être interprétés en termes de programmation convexe. Nous caractérisons les spectres des matrices pour lesquelles cet algorithme converge avec un taux de convergence traduisant une accélération. Nous introduisons également un algorithme accéléré de degré d, et montrons qu'il donne un taux de convergence multi-accéléré sous des conditions plus exigeantes sur le spectre des matrices. Une autre contribution est une version déflatée de l'itération sur les valeurs (DVI) pour résoudre la version à paiement moyen des jeux ...