Multi-Objective POMDPs with Lexicographic Reward Preferences

Kyle Hollins Wray, Shlomo ZilbersteinIJCAI 2015

In real-world scenarios, autonomous agents—such as robots or self-driving cars—rarely pursue a single objective. Instead, they must balance multiple, often competing goals, such as minimizing travel time while maximizing passenger safety. Standard models like Partially Observable Markov Decision Processes (POMDPs) typically address this through "scalarization," combining all goals into a single weighted sum. However, determining the correct weights is often arbitrary and difficult.

This paper, presented at IJCAI 2015, introduces Lexicographic POMDPs (LPOMDPs), a framework that allows agents to prioritize objectives in a strict order (e.g., Goal A first, then Goal B). To make this practical in uncertain environments, the authors introduce the concept of "slack," enabling agents to make smarter, more nuanced decisions in complex city environments.

The Challenge of Lexicographic Planning

A natural way to handle multiple goals is lexicographic ordering: prioritize the most important goal and use secondary goals only to break ties. However, in the continuous "belief space" of a POMDP, exact ties are extremely rare. Without a mechanism to define when a primary goal is "close enough" to optimal, secondary objectives are effectively ignored.

Methods: Introducing Slack and Parallelism

The core innovation of the LPOMDP framework is the formal definition of slack ($\eta$). For each objective $i$, the agent is permitted to deviate from the optimal value by a small amount $\eta_i$. This deviation expands the set of acceptable actions for the current objective, providing the flexibility to optimize for the next objective $i+1$.

Visualization of value functions showing how slack $\eta_1$ allows for the selection of sub-optimal actions in the primary objective to improve the secondary objective.

The authors proposed two primary algorithms to solve these models:

  1. Lexicographic Value Iteration (LVI): An extension of exact value iteration for POMDPs.
  2. Lexicographic Point-Based Value Iteration (LPBVI): A scalable approximation that evaluates the value function at a finite set of "belief points."

To overcome the high computational cost of POMDPs (which are PSPACE-complete), the authors developed GPU-based optimizations using CUDA. By parallelizing the "Bellman update"—the most computationally intensive part of the process—the agent can evaluate thousands of potential future scenarios simultaneously.

Experimental Evaluation

The researchers evaluated the LPOMDP model using real-world road network data from OpenStreetMap (OSM) across 10 major U.S. cities. They simulated a semi-autonomous driving scenario where the agent had two objectives: minimize travel time and maximize safety (time spent in autonomous mode) when the driver is tired.

Key Results and Scalability

The implementation demonstrated massive performance gains through GPU acceleration. The GPU solver handled the largest datasets, such as Boston (over 2,200 states), which the CPU version failed to solve within a reasonable timeframe.

Performance comparison between CPU and GPU implementations across various city road networks, demonstrating up to 585x speedup.

Key findings include:

  • Massive Speedups: The GPU implementation achieved speedups between 194x and 585x compared to standard CPU implementations.
  • The Necessity of Slack: Without slack, the first objective almost always yielded a unique "best" action, leaving no room for secondary goals. Slack created a "neighborhood" of high-quality actions, allowing the car to choose a slightly longer route (e.g., a highway) that significantly increased safety by allowing for autonomous driving.
  • Theoretical Rigor: The authors proved that LVI converges to a unique fixed point and provided bounds for slack assignment in the approximate LPBVI version to ensure priority integrity.

Conclusion and Future Work

By combining lexicographic preferences with slack and GPU acceleration, the authors transformed a theoretical multi-objective model into a tool capable of handling thousands of states in real-world city networks. Future research directions include developing "state-dependent orderings"—where priorities change dynamically based on the environment (e.g., prioritizing safety only when the driver is detected as tired)—and further optimizing for real-time re-routing constraints.

Summary updated

BibTeX
@inproceedings{wray2015multi,
  author = {Kyle Hollins Wray and Shlomo Zilberstein},
  title = {{Multi-Objective POMDPs with Lexicographic Reward Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure