Discounted Markov Decision Process (DMDP)

Input

A stationary Markov decision process $M = (S, c, p)$ and a real number $\beta \in (0, 1)$.

Problem

Is the minimum expected cost of $$\sum_{t=0}^{\infty} c(s_t, \delta(s_t, t)) \beta^t$$ over all policies $\delta$ equal to $0$?

Definitions

See FHMDP. This problem is infinite horizon, that is, there is no time bound.

Status

$\P$-complete (Papadimitriou and Tsitsiklis [1]).

Remarks

The problem can be phrased as a linear programming problem and solved in polynomial time. The same construction as used in FHMDP can be used to show this problem is $\P$-complete.

The Infinite Horizon, Discounted, Deterministic Problem is in $\NC$ [1]. The deterministic problem requires that $p$ only has values $0$ or $1$.