# How to Find the Exact Pareto Front for Multi-Objective MDPs?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 21 Oct 2024.

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

- [Personalized Soups: Personalized Large Language Model Alignment via Post-hoc Parameter Merging](https://mlsanity.com/paper/2310.11564/) (2023)
- [Rewarded soups: towards Pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards](https://mlsanity.com/paper/2306.04488/) (2023)
- [A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation](https://mlsanity.com/paper/1908.08342/) (2019)
- [Dynamic Weights in Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1809.07803/) (2018)
- [Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1610.02707/) (2016)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [PD-MORL: Preference-Driven Multi-Objective Reinforcement Learning Algorithm](https://mlsanity.com/paper/2208.07914/) (2022)
- [A Distributional View on Multi-Objective Policy Optimization](https://mlsanity.com/paper/2005.07513/) (2020)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms](https://mlsanity.com/paper/2305.18409/) (2023)
- [Promptable Behaviors: Personalizing Multi-Objective Rewards from Human Preferences](https://mlsanity.com/paper/2312.09337/) (2023)
- [MORAL: Aligning AI with Human Norms through Multi-Objective Reinforced Active Learning](https://mlsanity.com/paper/2201.00012/) (2021)
- [Two-Stage Constrained Actor-Critic for Short Video Recommendation](https://mlsanity.com/paper/2302.01680/) (2023)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Evolutionary Preference Sampling for Pareto Set Learning](https://mlsanity.com/paper/2404.08414/) (2024)
- [Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2405.03082/) (2024)
- [Provable Multi-Objective Reinforcement Learning with Generative Models](https://mlsanity.com/paper/2011.10134/) (2020)

## Built on by (most cited first, 5 of 5)

- [A Single Deep Preference-Conditioned Policy for Learning Pareto Coverage Sets](https://mlsanity.com/paper/2605.08946/) (2026)
- [Interpretability by Design for Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2506.04022/) (2025)
- [Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes](https://mlsanity.com/paper/2604.02196/) (2026)
- [Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation](https://mlsanity.com/paper/2605.12000/) (2026)
- [MoFlow: Multi-Objective Agentic Workflow Generation](https://mlsanity.com/paper/2609.38294/) (2026)

## Abstract (arXiv)

Multi-Objective Markov Decision Processes (MO-MDPs) are receiving increasing attention, as real-world decision-making problems often involve conflicting objectives that cannot be addressed by a single-objective MDP. The Pareto front identifies the set of policies that cannot be dominated, providing a foundation for finding Pareto optimal solutions that can efficiently adapt to various preferences. However, finding the Pareto front is a highly challenging problem. Most existing methods either (i) rely on traversing the continuous preference space, which is impractical and results in approximations that are difficult to evaluate against the true Pareto front, or (ii) focus solely on deterministic Pareto optimal policies, from which there are no known techniques to characterize the full Pareto front. Moreover, finding the structure of the Pareto front itself remains unclear even in the context of dynamic programming, where the MDP is fully known in advance. In this work, we address the challenge of efficiently discovering the Pareto front. By investigating the geometric structure of the Pareto front in MO-MDPs, we uncover a key property: the Pareto front is on the boundary of a convex polytope whose vertices all correspond to deterministic policies, and neighboring vertices of the Pareto front differ by only one state-action pair of the deterministic policy, almost surely. This insight transforms the global comparison across all policies into a localized search among deterministic policies that differ by only one state-action pair, drastically reducing the complexity of searching for the exact Pareto front. We develop an efficient algorithm that identifies the vertices of the Pareto front by solving a single-objective MDP only once and then traversing the edges of the Pareto front, making it more efficient than existing methods.