One-Counter Markov Decision Processes
Tomǎš Brázdil, Václav Brožek, Kousha Etessami, Kucera, A., Wojtczak, Dominik, Charikar, M. · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2009
We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs are equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a stochastic model studied heavily in queueing theory and applied probability. They can thus be viewed as a natural “adversarial ” version of a classic stochastic model. Alternatively, they can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. Basic computational questions about these models include “termination ” questions and “limit ” questions, such as the following: does the controller have a “strategy ” (or “policy”) to ensure that the counter (which may for example count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (a.s.)? Or that it will have lim sup value ∞, a.s.? Or, that it will hit value 0 in selected terminal states, a.s.? Or, in case these are not satisfied a.s., compute the maximum (supremum) such probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. Specifically, we show that several quantitative and almost-sure limit problems can be answered in polynomial time, and almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is DP-hard (and hard for the Boolean Hierarchy over NP), and we provide an exponential time algorithm for this problem. Our upper bounds combine techniques from the theory of MDP reward models, the theory of random walks, and a variety of automata-theoretic methods.