Patent ID: 9135563
Filing Date: 2015-09-15
Classification: G06N

Abstract:
1. An apparatus for determining an optimum policy by using a Markov decision process in which T subspaces each have at least one state, comprising: a processor implemented subspace identifying unit that identifies T subspaces that are part of a fixed state space, T being a natural number, the identified T subspaces being in sequence, the Markov decision process being cyclic by having the (T+1)-th subspace of the T subspaces equal to the first subspace of the T subspaces; a processor implemented election unit that selects the t-th subspace among the identified T subspaces, t being a natural number that is less than or equal to T; 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 next 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 and decrementing manner starting from the (t−1)-th subspace to the (t−2)-th subspace and so forth down to the (t+1)-th subspace, via the first subspace and the T-th subspace, wherein selection of a subspace having fewest states among the T subspaces is received as the t-th subspace.