Approximation of lorenz-optimal solutions in multiobjective markov decision processes

We consider the problem of finding small representative sets of Lorenz-optimal policies for MOMDPs (Multiobjective Markov Decision Processes). MDPs model planning under uncertainty; MOMDPs are MDPs with multiple reward functions. Most work on MOMDPs finds sets of Paretooptimal policies, i.e., policies whose expected discounted total reward vectors cannot be improved on one objective without being downgraded on another objective. Unfortunately, if we allow randomized policies, the Pareto set of policies may be infinite; even if we restrict to deterministic policies, there are families of MOMDPs where the sizes of the Pareto sets grow exponentially in the number of MDP states (Ogryczak, Pemy, and Weng 2011). Earlier work looks at polynomial-sized representative samples of the Pareto set (Papadimitriou and Yannakakis 2000; Chatterjee, Majumdar, and Henzinger 2006). Here, we seek a stronger notion than Pareto optimality. It is based on Lorenz dominance, a partial preference order refining Pareto dominance while including an idea of fairness in preferences. It is used for the measurement of inequalities in mathematical economics (Shorrocks 1983), for example to compare income distributions over a population. In our context, it can be used to compare reward vectors by inspecting how they distribute rewards over objectives. We describe algorithms for finding small, representative subsets of the Lorenz-optimal policies for MOMDPs.