Markov Chain Disorder Problems.
Richard L. Marcellus · Deep Blue (University of Michigan) · 1983
Various decision problems have appeared in the literature under the name "disorder problem" or "distribution problem". These problems involve the optimal control of stochastic processes which start in a "good state" and transfer to a "bad state". The decision maker must respond to the "bad state" when it occurs. He cannot, however, observe the state of the stochastic process itself. He can only make inferences as to the nature of the state by observing an "output" of the stochastic process. His response must be based on this "output". We define and study a class of such problems, which we call Markov chain disorder problems. Markov chain disorder problems are "disorder problems" where a Markov chain must be controlled. We extend the existing literature by allowing more than one "bad state". The discounted present cost for such problems is studied in the framework of partially observed Markov decision problems. Two st and ard results are given: the discounted present cost is concave, and "more informative outputs" give lower discounted present cost. The proof of the latter is easier and more direct than previous proofs. A structural property for policies is defined, the control limit property. For certain Markov chain disorder problems, sufficient conditions are given for optimal policies to satisfy this property. These results extend the list of partially observed Markov decision problems for which policy structure results are known. We develop improvements to Sondik's algorithm for calculating the n-stage discounted present cost. These improvements may be employed when the control limit property holds.