Jeux stochastiques concurrentiels avec des objectifs à remise d'état et de parité : Complexité et Algorithmes

Nous étudions les jeux stochastiques concurrentiels à somme nulle à deux joueurs avec un espace d'état et d'action finis, joués pour un nombre infini d'étapes. À chaque étape, les deux joueurs choisissent simultanément et indépendamment une action. Étant donné l'état actuel et les actions choisies, le prochain état est obtenu selon une fonction de transition stochastique. Un objectif est une fonction mesurable sur les jeux (ou trajectoires infinies) du jeu, et la valeur d'un objectif est l'attente maximale que le joueur peut garantir contre le joueur adverse. Nous considérons : (a) des objectifs à remise d'état, qui sont similaires aux objectifs à somme remise classiques, mais les états sont associés à différents facteurs de remise plutôt qu'à un seul facteur de remise ; et (b) des objectifs de parité, qui sont une représentation canonique pour des objectifs -réguliers. Pour les objectifs à remise d'état, étant donné un ordre des facteurs de remise, la valeur limite est la limite de la valeur des objectifs à remise d'état, à mesure que les facteurs de remise approchent de zéro selon l'ordre donné. Le problème computationnel que nous considérons est l'approximation de la valeur dans une erreur additive arbitraire. Le problème ci-dessus est connu pour être dans EXPSPACE pour la valeur limite des objectifs à remise d'état et dans PSPACE pour les objectifs de parité. Les meilleurs algorithmes connus pour les deux problèmes ci-dessus prennent au moins un temps exponentiel, avec une dépendance exponentielle au nombre d'états et d'actions. Nos principaux résultats pour le problème d'approximation de la valeur de la valeur limite des objectifs à remise d'état et des objectifs de parité sont les suivants : (a) nous établissons la complexité TFNPNP ; et (b) nous présentons des algorithmes qui améliorent la dépendance au nombre d'actions dans l'exposant d'une linéaire à logarithmique. En particulier, si le nombre d'états est constant, nos algorithmes s'exécutent en temps polynomial.