Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes

ArXi:2604.02196v1 Announce Type: cross Many communication and control problems are cast as multi-objective Marko 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.