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

arXiv: https://arxiv.org/abs/2604.02196 · HTML: https://mlsanity.com/paper/2604.02196/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 2 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Semantics-Empowered Communication for Networked Intelligent Systems](https://mlsanity.com/paper/2007.11579/) (2020)
- [Wireless Network Design for Control Systems: A Survey](https://mlsanity.com/paper/1708.07353/) (2017)
- [Semantic-Aware Remote Estimation of Multiple Markov Sources Under Constraints](https://mlsanity.com/paper/2403.16855/) (2024)
- [How to Find the Exact Pareto Front for Multi-Objective MDPs?](https://mlsanity.com/paper/2410.15557/) (2024)
- [Sensor Scheduling in Variance Based Event Triggered Estimation with Packet Drops](https://mlsanity.com/paper/1511.04792/) (2015)
- [On the Cost of Consecutive Estimation Error: Significance-Aware Non-linear Aging](https://mlsanity.com/paper/2410.03637/) (2024)
- [Remote State Estimation over a Wearing Channel: Information Freshness vs. Channel Aging](https://mlsanity.com/paper/2501.17473/) (2025)
- [Value of Communication in Goal-Oriented Semantic Communications: A Pareto Analysis](https://mlsanity.com/paper/2512.01454/) (2025)

## Abstract (arXiv)

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.