Sensitivity of constrained Markov decision processes

The authors consider the optimization of finite-state, finite-action Markov decision processes under constraints. Costs and constraints are of the discounted or average type, and possibly finite-horizon. The authors investigate the sensitivity of the optimal cost and optimal policy to changes in various parameters. They relate several optimization problems to a generic linear program, through which sensitivity issues are investigated. The authors establish conditions for the continuity of the optimal value in the discounted factor. In particular, the optimal value and optimal policy for the expected average cost are obtained as limits of the discounted case, as the discount factor goes to one. This generalizes a well-known result for the unconstrained case. The authors also establish the continuity in the discount factor for certain non-stationary policies. They then discuss the sensitivity of optimal policies and optimal values to small changes in the transition matrix and in the instantaneous cost functions. The importance of the last two results is related to the performance of adaptive policies for constrained MDP under various cost criteria. Finally, the authors establish the convergence of the optimal value for the discounted constrained finite horizon problem to the optimal value of the corresponding infinite horizon problem.