Separable Markovian Decision Problems: The Linear Programming Method in the Multichain Case (Revised).

摘要

Separable Markovian decision problems have the property that for certain pairs (i,a) of a state i and an action a: (1) the immediate reward is the sum of terms due to the current state and action (r(ia) = s(i) + t(a)), (2) the transition probability depends only on the action and not on the state from which the transition occurs. The separable model was studied already in the late sixties. For the discounted case and the unichain undiscounted case, a reduced LP formulation was given, which involves a substantially smaller number of variables than in the LP formulation of a general Markov decision problem. It was unknown whether such an efficient formulation was also possible in the multichain case. The paper solves the problem: such an efficient formulation can be obtained. Some applications of separable models are also presented.