You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
E-Book;
Electronic Thesis
Title:
Strategy improvement method for solving simple stochastic games ; Méthode d'amélioration de stratégie pour résoudre les jeux stochastiques simples
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Un Jeu Stochastique est joué par deux joueurs, MAX et MIN, en déplaçant un pion sur un ensemble d'états. À chaque tour, les deux joueurs choisissent simultanément une action et le pion est déplacé suivant une loi de probabilité dépendante du choix des deux joueurs. De plus, une valeur est associée à chaque état et le joueur MIN doit payer au joueur MAX cette valeur à chaque entrée dans l'état. Cela continue jusqu'à ce que le pion entre dans un puits. Dans ce cas, le jeu s'arrête. Il s'agit donc d'un jeu à somme nulle, où le but de MAX est de maximiser l'espérance de la valeur gagner durant la partie et MIN cherche à la minimiser. Ces jeux ont été introduits par Shapley en 1953, qui prouve qu'il existe des stratégies optimales pour les joueurs qui sont sans mémoire, et de ce fait, un gain moyen optimal.En 1990, Condon présente une restriction des jeux stochastiques appelés jeux stochastiques simples (SSG pour Simple Stochastic Games en anglais) dans lequel les joueurs jouent à tour de rôle. Elle prouve qu'il existe une paire de stratégies déterministe, sans mémoire et optimales pour les joueurs. Notre but est de calculer ces stratégies. Pour le moment, les algorithmes déterministes pour résoudre ce problème sont en temps exponentiel, quant aux algorithmes non déterministes ils ont un temps moyen sous-exponentiel.Dans cette thèse, on se focalise principale sur la méthode d'amélioration de stratégie pour résoudre des SSGs. On commence par reprouver certains résultats connus, mais sans utiliser la condition d'arrêt, une condition sur les SSG garantissant que la partie s'achève avec probabilité 1. Ensuite, on prouve une borne stricte sur le format des valeurs des sommets, et on présente un algorithme générique qui capture les algorithmes d'amélioration de stratégies. On l'utilise pour prouver bornes de complexités générales pour tous les algorithmes d'améliorations de stratégies. On compare également les méthodes d'améliorations de stratégies et d'itération de valeur. Dans un second temps, on introduit le concept de ...