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.
Introduction
In standard Markov Decision Processes (MDPs), we assume the reward for every action is precisely known. However, in real-world applications, specifying these rewards is often difficult due to noisy data or expert disagreement. Reward-Uncertain MDPs (RUMDPs) address this by defining a set of feasible reward functions. To find a robust policy in this setting, researchers typically use the minimax regret criterion.
A critical bottleneck in this process is finding the set of all nondominated policies—those that are optimal for at least one possible reward function in the feasible set. Previous state-of-the-art algorithms, such as $\pi$Witness, rely on solving numerous complex Linear Programs (LPs) to search for these policies, which becomes computationally prohibitive as the problem size grows.
Methods: The Geometric Approach
This paper introduces the Geometric Traversal (GT) algorithm, which shifts the problem from algebraic search to geometric traversal. The core insight is that the space of feasible rewards can be partitioned into convex regions (polytopes), where each region corresponds to a specific optimal policy.
The GT algorithm operates in three main steps:
- Mapping the Reward Space: The algorithm treats the reward space as a map. Using "reward optimality conditions," the authors derive linear inequalities (hyperplanes) that form the boundaries of these regions.
- Traversal: Instead of searching the entire 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 effectively turns the search into a graph traversal problem.
- Approximate Version: For extremely large problems, an "anytime" version is provided that samples policies along a straight line through the reward space, allowing for rapid, albeit incomplete, policy collection.
Experimental Results
The authors evaluated the GT algorithm against $\pi$Witness using randomly generated RUMDP instances, varying the number of states ($|S|$), actions ($|A|$), and reward dimensions ($dim(R)$).
Performance and Scalability
The most significant finding is that the GT algorithm's running time is linear in the number of nondominated policies. In contrast, previous methods exhibit polynomial or exponential growth. As shown in the experimental data, the GT algorithm maintains high efficiency even as the number of policies scales into the tens of thousands.
In a configuration with 32 states and 5 actions, the GT algorithm successfully handled over 40,000 nondominated policies—a scale where $\pi$Witness would typically time out. While $\pi$Witness might take over 1,500 seconds to find just 500 policies, the GT algorithm completes the task in a fraction of that time.
Discussion and Future Work
The GT algorithm represents a significant leap in solving RUMDPs by exploiting the connectivity of optimal reward regions. Because one can move from any optimal region to any other by crossing boundaries, a simple traversal is guaranteed to find all nondominated policies.
However, limitations remain. The current "anytime" version lacks sophisticated heuristics to prioritize regions that might reduce regret faster. Additionally, for extremely large state spaces, the number of hyperplanes ($|S||A|$) could become a bottleneck. Future work may explore "factored" reward functions to create more compact geometric representations, further extending the scalability of this geometric approach.
Summary updated