Abstract
Finding the full Pareto front in Multi-Objective Markov Decision Processes (MO-MDPs) has traditionally required a trade-off between slow approximations and incomplete exact methods. This paper introduces a breakthrough geometric property: the Pareto front is the boundary of a convex polytope where neighboring vertices differ by only a single state-action pair. Leveraging this "Distance-One" property, we present an algorithm that efficiently traverses the exact Pareto front, identifying both deterministic and stochastic optimal policies far more effectively than existing methods.
1. Introduction
In real-world decision-making, agents must often balance conflicting goals, such as speed versus safety in autonomous driving. Multi-Objective MDPs (MO-MDPs) model these trade-offs, where the ultimate goal is to identify the Pareto front—the set of all policies that cannot be improved in one objective without degrading another.
Finding this front is computationally difficult due to two primary challenges: the Continuity Trap, where scalarization methods require infinite sampling of weights, and the Stochastic Gap, where exact methods often only identify deterministic policies (the "corners" of the front) while missing the stochastic mixtures that form the faces and edges between them.
2. Methodology
2.1 The Geometric Breakthrough
The researchers proved that the set of all possible returns in an MO-MDP forms a convex polytope. Crucially, they discovered the Distance-One Property: for almost all MDPs, any two neighboring vertices on the Pareto front differ by exactly one state-action pair. This transforms a global search across the entire policy space into a localized search among neighbors.
2.2 The Pareto Front Searching Algorithm
Building on this property, the proposed algorithm follows a structured traversal:
- Initialization: Solve a standard single-objective MDP to find a starting vertex on the Pareto front.
- Neighbor Search: Identify all deterministic policies that differ from the current one by only one action in one state.
- Face Extraction: Use a modified Quickhull-style approach and Linear Programming (LP) to determine which "faces" (stochastic policies) connecting these neighbors are also Pareto optimal.
- Traversal: Move to the next unexplored vertex and repeat until the entire front is mapped.
3. Results and Evaluation
The algorithm was evaluated using synthetic MO-MDPs and the classic Deep-Sea-Treasure benchmark. The results demonstrate that the algorithm successfully recovers the entire precise Pareto front, including low-dimensional edges and faces that approximation methods typically fail to reconstruct.
Key findings include:
- Exactness: Unlike scalarization, this method captures the full geometry of the front, including stochastic policies.
- Scalability: While brute-force benchmarks explode exponentially with the number of actions, this algorithm maintains a manageable runtime. It also demonstrates a flatter scaling curve compared to popular methods like Optimistic Linear Support (OLS) as state and action spaces expand.
- Efficiency: By utilizing local search, the algorithm only requires solving a full MDP once for initialization; subsequent steps are computationally inexpensive local evaluations.
4. Conclusion and Future Work
The "distance-one" property provides a powerful tool for exact planning in multi-objective environments. While the current algorithm assumes known dynamics, it sets the stage for future work in Multi-Objective Reinforcement Learning (MORL), where agents must learn these dynamics from experience while navigating the trade-offs of the Pareto front.
Summary updated