Dominance-constrained Markov decision processes

We are interested in risk constraints for discrete time Markov decision processes (MDPs). Starting with the average reward case, we argue that stochastic dominance constraints are natural risk constraints for MDPs. Specifically, we constrain the empirical distribution of reward to dominate a benchmark distribution in the increasing concave stochastic order. We argue that the optimal policy for the dominance-constrained MDP is a stationary randomized policy. Further, the optimal policy can be computed from a linear program in the space of occupation measures, where the dominance constraint is represented by linear inequalities. The dual of this linear program is computed and is shown to be close to the usual linear programming form of the average dynamic programming optimality equations. In our case, a pricing term appears in the dual corresponding to the dominance constraints. We carry out a parallel development for the discounted reward case with stochastic dominance constraints. We also extend this development to cover multivariate stochastic dominance.