Stability estimates in the problem of average optimal switching of a Markov chain

We consider a switching model for a Markov chain x t with a transition probability p(x|B). The goal of a controller is to maximize the average gain by selecting a sequence of stopping times, in which the controller gets rewards and pays costs (depending on x t ) in an alternating order. We suppose that the exact transition probability function of the original “real” chain x t is not available to the controller, and he/she is forced to rely on a given approximation $\widetildep$ to the unknown p. The controller finds a switching policy $\widetilde\pi$ optimal for the Markov chain with the transition probability $\widetildep$ , with a view to apply $\widetilde\pi$ to the original Markov chain x t . Under certain restrictions on p we give an upper bound for the difference between the maximal gain attainable in switching of x t , and the gain made under the policy in the original model. The bound is expressed in terms of the total variation distance ${{\sup } \over x}{\kern 1pt} {\kern 1pt} {\kern 1pt} Var\left( {p\left( {x\left| \cdot \right.} \right),\widetildep\left( {x\left| \cdot \right.} \right)} \right)$ . Copyright Springer-Verlag Berlin Heidelberg 2003