Research map / Reinforcement learning / MDPs and planning
How to Find the Exact Pareto Front for Multi-Objective MDPs?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the Pareto front of a discounted multi-objective MDP is on the boundary of a polytope whose vertices are deterministic policies differing by one state-action pair between neighbors, and uses this to build an exact Pareto front search algorithm that solves one single-objective MDP and then traverses Pareto edges.
Problem
Finding the exact Pareto front of multi-objective MDPs (including stochastic Pareto optimal policies) is hard; existing preference-sweeping and scalarization methods only approximate it or find only deterministic vertices.
Approach
The Pareto front lies on the boundary of a convex polytope of long-term returns whose vertices are deterministic policies; neighboring Pareto vertices differ by exactly one state-action pair almost surely. This turns global search into a local search over one-state-action-deviation policies, with local convex hulls and a linear-programming face criterion used to extract Pareto faces.
Key results
- The proposed algorithm recovers all faces of the true Pareto front in all tested small MDP cases (state sizes 5 and 8, action sizes 5 to 7, reward dimension 3).
- Runtime of the convex-hull benchmark grows exponentially with the number of actions, while the proposed method keeps controllable runtime.
- Compared with OLS for finding all Pareto vertices (reward dimension 4), OLS running time increases significantly with small expansions of state and action space while the proposed method remains more manageable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use local distance-one policy search and traverse Pareto-front edges instead of computing a convex hull over all non-dominated deterministic policies | Pareto-front discovery in MO-MDPs · MDPs with state spaces 5 and 8, action spaces 5–7, D=3 | runtime | Helped |
| use local distance-one policy search and traverse Pareto-front edges | Pareto-front discovery in MO-MDPs · MDPs with state spaces 5 and 8, action spaces 5–7, D=3 | Pareto-front identification | Helped |
| initialize with one single-objective planning step and search directly along the Pareto front | Pareto-front vertex discovery · MDPs with state spaces 5 and 8, D=4 | runtime | Helped |
Surprising findings
- Some Pareto-optimal vertices lie only on Pareto edges while all their incident faces are not Pareto optimal, so the Pareto front cannot be built from deterministic vertices alone.
Limitations
- Assumes the MDP is fully known; robustness to policy evaluation error is not studied.
- Exponential-size enumeration of deterministic policies in the benchmark limits experiments to small MDPs.
Experimental setup
Benchmarks: randomly generated small MDPs with varying state, action and reward dimension
Metrics: runtime correctness of recovered Pareto front faces and vertices
Baselines: Optimistic Linear Support (OLS) benchmark convex hull of all non-dominated deterministic policies
Builds on: Optimistic Linear Support Quickhull PPrune
Closest papers by meaning
- Pareto Front-Diverse Batch Multi-Objective Bayesian Optimization (AAAI 2024 · similarity 0.86)
- IOP: An Idempotent-Like Optimization Method on the Pareto Front of Hypernetwork (AAAI 2025 · similarity 0.86)
- Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization (NeurIPS 2025 · similarity 0.86)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.85)
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.85)
- User Preference Meets Pareto-Optimality in Multi-Objective Bayesian Optimization (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.