The steady-state control problem for Markov decision processes

Sundararaman Akshay 1 Nathalie Bertrand 2, 3 Serge Haddad 4, 5 Loic Helouet 2
2 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
5 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : This paper addresses a control problem for probabilistic models in the setting of Markov decision processes (\MDP). We are interested in the \emph{steady-state control problem} which asks, given an ergodic \MDP\ $\mathcal M$ and a distribution $\delta_{goal}$, whether there exists a (history-dependent randomized) policy $\pi$ ensuring that the steady-state distribution of $\mathcal M$ under $\pi$ is exactly $\delta_{goal}$. We first show that stationary randomized policies suffice to achieve a given steady-state distribution. Then we infer that the steady-state control problem is decidable for \MDP, and can be represented as a linear program which is solvable in PTIME. This decidability result extends to labeled \MDP\ (\LMDP) where the objective is a steady-state distribution on labels carried by the states, and we provide a PSPACE algorithm. We also show that a related \emph{steady-state language inclusion problem} is decidable in EXPTIME for \LMDP. Finally, we prove that if we consider \MDP\ under partial observation (\POMDP), the steady-state control problem becomes undecidable.
Type de document :
Communication dans un congrès
Joshi, Kaustubh R. and Siegle, Markus and Stoelinga, Marielle and D'Argenio, Pedro R. Qest 2013, Sep 2013, Buenos Aires, Argentina. Springer, 8054, pp.290-304, 2013, LNCS
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00879355
Contributeur : Loic Helouet <>
Soumis le : samedi 2 novembre 2013 - 22:21:32
Dernière modification le : mercredi 16 mai 2018 - 11:24:06
Document(s) archivé(s) le : lundi 3 février 2014 - 04:26:51

Fichier

Qest_paper_29.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00879355, version 1

Citation

Sundararaman Akshay, Nathalie Bertrand, Serge Haddad, Loic Helouet. The steady-state control problem for Markov decision processes. Joshi, Kaustubh R. and Siegle, Markus and Stoelinga, Marielle and D'Argenio, Pedro R. Qest 2013, Sep 2013, Buenos Aires, Argentina. Springer, 8054, pp.290-304, 2013, LNCS. 〈hal-00879355〉

Partager

Métriques

Consultations de la notice

684

Téléchargements de fichiers

129