Multi-Objective MDPs with Conditional Lexicographic Reward Preferences

Kyle Hollins Wray, Shlomo Zilberstein, Abdel-Illah MouaddibAAAI 2015 · DOI

Introduction

Autonomous systems frequently encounter scenarios requiring the simultaneous optimization of multiple, often conflicting, objectives. For instance, a self-driving vehicle must balance minimizing travel time with maximizing passenger comfort and safety. Traditional approaches typically rely on scalarization, where objectives are combined into a single reward function using fixed weights. However, determining appropriate weights is often arbitrary and fails to capture the dynamic nature of real-world priorities.

This research introduces Lexicographic MDPs (LMDPs), a framework that extends standard Markov Decision Processes to handle state-dependent goal priorities and "slack"—the allowable trade-off between high- and low-priority goals. By allowing priorities to shift based on the environment (e.g., a driver's fatigue level), LMDPs offer a more expressive and flexible modeling approach than linear weighting.

Methodology

The LMDP framework introduces two primary innovations:

  1. Conditioning: The priority of objectives is not static but can change depending on the current state. For example, safety may become the absolute priority only when a driver is exhausted.
  2. Slack ($\delta$): To prevent the rigidity of strict lexicographic ordering, the authors introduce a "margin of error." This allows an agent to deviate slightly from the mathematical optimum of a primary goal if doing so yields significant improvements in a secondary objective.

To solve these models, the authors developed Lexicographic Value Iteration (LVI). This algorithm processes objectives sequentially according to their priority. For each subsequent objective, LVI restricts the action space to those that maintain the performance of higher-priority goals within their defined slack bounds. To address the computational demands of multi-objective planning, the authors implemented LVI using CUDA for GPUs, parallelizing Bellman updates for significant performance gains.

Experimental Evaluation

The researchers evaluated the LMDP framework using a semi-autonomous driving domain. They utilized real-world road network data for 10 major cities (e.g., New York City, Chicago, Boston) sourced from OpenStreetMap. The state space modeled intersection pairs, driver fatigue levels, and the availability of autonomous-capable road segments. The primary objectives were to minimize travel time and minimize driver fatigue (incurred during manual driving while tired).

Key Results and Insights

A significant theoretical contribution of this work is the proof that LMDPs can represent optimal policies that are mathematically impossible to achieve through any linear combination of weights. This establishes LMDPs as a strictly more expressive class of models. Furthermore, the authors demonstrated a formal link between LMDPs and game theory, showing that optimal policies correspond to Nash equilibria in specific multi-player games.

Qualitative Performance

In driving simulations, the LVI algorithm successfully adapted its policy based on the driver's state. As shown in Figure 4, the agent selects different routes depending on whether the driver is attentive or fatigued, prioritizing safety and autonomous-capable roads when the driver is tired.

Qualitative route selection: The top map shows a direct route for an attentive driver, while the bottom map shows a safety-prioritized route for a tired driver.

Computational Efficiency

The GPU-accelerated implementation of LVI provided substantial speedups over traditional CPU execution. As detailed in Figure 5, for the largest dataset (New York City), the GPU version achieved a ~30x speedup, reducing computation time from over 4.5 hours to under 9 minutes.

Performance comparison of CPU vs. GPU execution times across various city datasets.

Conclusion

The LMDP framework provides a robust solution for complex decision-making with shifting priorities. While the current convergence proofs rely on specific state partitions and selecting appropriate slack values requires domain expertise, the results demonstrate that LMDPs are both more expressive and computationally feasible for large-scale real-world applications. Future work will explore more complex, non-linear preference structures and broader releases of the scenario-generation tools.

Summary updated

BibTeX
@inproceedings{wray2015multi,
  author = {Kyle Hollins Wray and Shlomo Zilberstein and Abdel-Illah Mouaddib},
  title = {{Multi-Objective MDPs with Conditional Lexicographic Reward Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9647},
}
Figure