A Geometric Traversal Algorithm for Reward-Uncertain MDPs

Eunsoo Oh, Kee-Eung Kim

TL;DR

This paper introduces a Geometric Traversal (GT) algorithm that dramatically speeds up solving Markov Decision Processes (MDPs) when the reward function is uncertain. By treating the space of possible rewards as a geometric map partitioned into regions, the algorithm "hops" between adjacent optimal policies, achieving a performance boost of several orders of magnitude over previous state-of-the-art methods.

What Problem Does This Paper Address?

In a standard Markov Decision Process (MDP), we assume we know exactly what the "rewards" are for every action. In reality, specifying these rewards is hard—experts might disagree, or data might be noisy. Reward-Uncertain MDPs (RUMDPs) handle this by defining a set of feasible reward functions rather than just one.

To find a robust policy in this setting, researchers often use the minimax regret criterion. A crucial, yet computationally expensive, step in this process is finding the set of all nondominated policies—policies that could be optimal for at least one possible reward function in the feasible set.

The previous leading algorithm, $\pi$Witness, is slow because it relies on solving many complex Linear Programs (LPs) to search for these policies. As the number of possible policies grows, $\pi$Witness becomes a massive bottleneck.

Methods

The authors propose a shift from algebraic search to geometric traversal.

  1. The Reward Space as a Map: They observe that the space of feasible rewards can be partitioned into convex regions (polytopes). Inside each region, one specific policy is optimal.
  2. Boundary Conditions: Using the "reward optimality condition," the authors derive the linear inequalities (hyperplanes) that form the boundaries of these regions.
  3. The Traversal Algorithm (GT): Instead of searching the whole space blindly, the GT algorithm starts with one optimal policy, identifies the "walls" (hyperplanes) of its reward region, and then "jumps" over those walls into adjacent regions to find the next nondominated policies. This turns the problem into a graph traversal where nodes are policies and edges are shared boundaries.
  4. Approximate Version: For massive problems where finding every policy is impossible, they provide an "anytime" version that shoots a straight line through the reward space and collects the policies it hits along the way.

Datasets

The authors evaluated their algorithm using randomly generated RUMDP instances. They varied the number of states ($|S|$), actions ($|A|$), and the dimension of the reward function ($dim(R)$). This setup follows the experimental standards established in prior landmark papers (like Regan and Boutilier 2010) to ensure a fair "apples-to-apples" comparison.

Key Insights and Ideas

  • Linear Complexity: The most significant insight is that the running time of the GT algorithm is linear in the number of nondominated policies. Previous methods were polynomial or worse, making them stall as the problem complexity increased.
  • Connectivity: The algorithm relies on the fact that the regions of the reward space are connected. Because you can move from any optimal region to any other by crossing boundaries, a simple breadth-first or depth-first search is guaranteed to find all nondominated policies.
  • LP Independence: While the algorithm still uses LPs to find adjacent regions, the number of LPs required per policy is small and independent of the total number of policies in the system.

Key Results

  • Speedup: In experiments with 32 states and 5 actions, the GT algorithm was orders of magnitude faster than $\pi$Witness. For example, where $\pi$Witness might take over 1,500 seconds to find 500 policies, the GT algorithm finished in a fraction of that time (often under 100 seconds for even larger sets).
  • Scalability: The GT algorithm successfully handled sets of over 40,000 nondominated policies, a scale where previous algorithms would likely have timed out or crashed.
  • Anytime Performance: The approximate version of GT outperformed the anytime version of $\pi$Witness, reaching lower regret levels much faster, although it tended to generate more policies to reach that same level of accuracy.

Limitations and Future Work

  • Prioritization Heuristics: Currently, the "anytime" version of the algorithm traverses the space along random lines. The authors admit they lack a heuristic to prioritize "important" regions that might reduce regret faster.
  • Factored Domains: The current approach requires constructing $|S||A|$ hyperplanes, which is difficult for very large state spaces. The authors suggest that "factored" reward functions (where rewards depend on fewer variables) could allow for a more compact geometric representation.
  • High-Dimensional Boundaries: While the algorithm is efficient, the number of boundaries to check grows with the number of state-action pairs, which could eventually become a bottleneck in extremely large environments.

Summary updated

Abstract

Markov decision processes (MDPs) are widely used in modeling decision making problems in stochastic environments. However, precise specification of the reward functions in MDPs is often very difficult. Recent approaches have focused on computing an optimal policy based on the minimax regret criterion for obtaining a robust policy under uncertainty in the reward function. One of the core tasks in computing the minimax regret policy is to obtain the set of all policies that can be optimal for some candidate reward function. In this paper, we propose an efficient algorithm that exploits the geometric properties of the reward function associated with the policies. We also present an approximate version of the method for further speed up. We experimentally demonstrate that our algorithm improves the performance by orders of magnitude.
BibTeX
@inproceedings{oh2011geometric,
  author = {Eunsoo Oh and Kee-Eung Kim},
  title = {{A Geometric Traversal Algorithm for Reward-Uncertain MDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=FeT-uA3nQEM},
}

Loading related content...

Figure