Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
This provides a foundational solution for exact Pareto front computation in average-cost MOMDPs, impacting communication and control problems, though it builds on prior geometric characterizations in simpler settings.
The authors characterized the exact Pareto front in average-cost multi-objective Markov decision processes, showing it is a continuous, piecewise-linear surface on a convex polytope boundary, with vertices corresponding to deterministic policies. They applied this to a remote state estimation problem, where vertices correspond to threshold policies, enabling exact Pareto front computation without solving MDPs explicitly.
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.