Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

qest13a

S Akshay, N. Bertrand, Haddad S, L. Hélouet. The steady-state control problem for Markov decision processes. In 10th International Conference on Quantitative Evaluation of SysTems (QEST'13), LNCS, Volume 8054, Pages 390-304, Buenos Aires, Argentina, August 2013.

Download [help]

Download paper: Adobe portable document (pdf) pdf

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

This paper addresses a control problem for probabilistic models in the setting of Markov decision processes (MDP). We are interested in the steady-state control problem which asks, given an ergodic MDP M and a distribution \delta, whether there exists a (history-dependent randomized) policy \pi ensuring that the steady-state distribution of M under \pi is exactly \delta. 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 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

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/
Loic Hélouet http://people.irisa.fr/Loic.Helouet/

BibTex Reference

@InProceedings{qest13a,
   Author = {Akshay, S and Bertrand, N. and S, Haddad and Hélouet, L.},
   Title = {The steady-state control problem for Markov decision processes},
   BookTitle = {10th International Conference on Quantitative Evaluation of SysTems (QEST'13)},
   Volume = {8054},
   Pages = {390--304},
   Series = {LNCS},
   Address = {Buenos Aires, Argentina},
   Month = {August},
   Year = {2013}
}

EndNote Reference [help]

Get EndNote Reference (.ref)