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.