Search papers, labs, and topics across Lattice.
This paper characterizes the exact Pareto front for average-cost multi-objective Markov decision processes (MOMDPs), proving it to be a continuous, piecewise-linear surface on the boundary of a convex polytope. The vertices of this polytope correspond to deterministic policies differing in only one state, and edges are realized via closed-form convex combinations of endpoint policies. The approach avoids explicit MDP solving and is demonstrated on a remote state estimation problem.
Forget scalarization: the exact Pareto front for average-cost MOMDPs can be computed directly as a piecewise-linear surface, unlocking optimal multi-objective control without solving any MDPs.
Many communication and control problems are cast as multi-objective Markov decision processes (MOMDPs). The complete solution to an MOMDP is the Pareto front. Much of the literature approximates this front via scalarization into single-objective MDPs. Recent work has begun to characterize the full front in discounted or simple bi-objective settings by exploiting its geometry. In this work, we characterize the exact front in average-cost MOMDPs. We show that the front is a continuous, piecewise-linear surface lying on the boundary of a convex polytope. Each vertex corresponds to a deterministic policy, and adjacent vertices differ in exactly one state. Each edge is realized as a convex combination of the policies at its endpoints, with the mixing coefficient given in closed form. We apply these results to a remote state estimation problem, where each vertex on the front corresponds to a threshold policy. The exact Pareto front and solutions to certain non-convex MDPs can be obtained without explicitly solving any MDP.
