1. An apparatus for determining an optimum policy by using a Markov decision process in which T subspaces each have at least one state having a cyclic structure, comprising: a processor implemented subspace identifying unit that identifies subspaces that are part of a state space; a processor implemented election unit that selects the t-th (t is a natural number, t≦T) subspace among the identified subspaces; a processor implemented probability and cost computing unit that computes a probability of, and an expected value of a cost of, reaching from one or more states in the selected t-th subspace to one or more states in the t-th subspace in a following cycle; and a processor implemented recursive computing unit that recursively computes a value and an expected value of a cost based on the computed probability and expected value of the cost, in a sequential manner starting from a (t−1)-th subspace.