The paper considers the H-horizon, stationary Markov decision problem. For the discounted case, it gives an •-approximation algorithm whose time is proportional to log(1/•), log(H) and 1/(1-α), where α is the discount factor. Under an additional stability assumption, the paper gives an exact algorithm whose time is proportional to log(H) and 1/(1-α). For problems where α is bounded away from 1, it obtains, respectively, a fully polynomial approximation scheme and a polynomial-time algorithm. For the undiscounted case, by refining a weighted maximum norm contraction result of Hoffman, the paper derives analogous results under the assumption that all stationary policies are proper.
