Title: Solving H-horizon, stationary Markov decision problems in time proportional to log(H)
Abstract: We consider the H-horizon, stationary Markov decision problem. For the discounted case, we give an ε-approximation algorithm whose time is proportional to log(1/ε), log(H) and 1(1 − α). For problems where α is bounded away from 1, we obtain, 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, we derive analogous results under the assumption that all stationary policies are proper.