Fast Value Iteration for Goal-Directed Markov Decision Processes

Nevin Lianwen Zhang, Weihong ZhangUAI 1997

TL;DR

This paper introduces several novel techniques to accelerate value iteration, a standard algorithm for solving Markov Decision Processes (MDPs), by exploiting the "goal-directed" nature of many planning problems. These methods, including Parsimonious Value Iteration (PVI) and Greedy Value Iteration (GVI), significantly reduce computation time, making MDPs more practical for complex planning tasks.

What Problem Does This Paper Address?

Markov Decision Processes (MDPs) are a powerful framework for modeling sequential decision-making problems where actions have uncertain outcomes. A key challenge in solving MDPs, especially those with a large number of states, is the computational cost of standard algorithms like value iteration. Value iteration iteratively refines an estimate of the optimal value function for each state, which can be slow, particularly when the discount factor is close to 1. Many real-world planning problems, however, have a specific structure: they are "goal-directed," meaning there's a clear objective or goal state. This paper aims to leverage this goal-directedness to develop faster value iteration algorithms.

Methods

The paper proposes several new algorithms that build upon standard value iteration:

  • Parsimonious Value Iteration (PVI): This approach recognizes that in goal-directed MDPs, states far from the goal might have values that change little in early iterations. PVI updates a state's value only if it's expected to change significantly, based on a comparison with the previous iteration's values. This "parsimonious" update strategy aims to reduce redundant computations. PVI is suggested as a preprocessing step to standard value iteration.
  • Greedy Value Iteration (GVI): GVI takes a more direct approach by focusing updates on states from which the goal is "ideally reachable" within a certain number of steps. This is determined by identifying the action that maximizes the probability of reaching a specific next state. GVI updates values in a sweep from the goal state backward.
  • Double Value Iteration (DVI): DVI combines GVI with standard value iteration. It uses GVI to get a good initial estimate of the value function and then applies standard value iteration. This is motivated by the idea that GVI provides a better starting point, leading to faster convergence of the subsequent value iteration.
  • Improved Parsimonious Value Iteration (PVI1): This is an enhancement of PVI, incorporating the idea of ordering states by their distance to the goal, similar to GVI.

Datasets

The paper evaluates its proposed algorithms on four office environment navigation problems borrowed from Cassandra et al. (1996). These problems vary in corridor layout and the total number of states. The experiments were conducted using both "standard" and "noisy" transition probabilities, where noisy probabilities represent less certain action outcomes.

Key Insights and Ideas

  • Exploiting Goal-Directedness: The core insight is that the goal-directed nature of many planning problems isn't just about reaching a specific state, but also about how values propagate backward from that goal. This structure can be exploited to avoid unnecessary computations.
  • Parsimony in Updates: The idea that not all states need updating in every iteration is powerful. PVI's selective update strategy is efficient because it avoids recomputing values for states whose values are unlikely to change significantly.
  • Order Matters: GVI and DVI highlight the benefit of processing states in an order that reflects their proximity to the goal. This backward sweep is analogous to shortest-path algorithms on directed acyclic graphs.
  • Preprocessing for Speed: Using algorithms like PVI or GVI as a preprocessing step for standard value iteration can dramatically reduce the total computation time required to reach a desired level of accuracy.

Key Results

Empirical studies showed significant speedups for the proposed algorithms compared to standard value iteration:

  • DVI and PVI consistently converged much faster than standard VI.
  • PVI1 (the improved PVI) converged even faster than DVI and PVI.
  • In the smallest problem, PVI1 converged about three times faster than VI.
  • In the largest problem, PVI1 converged six times faster than VI.
  • The performance differences between algorithms became larger as problem size increased.
  • Performances were generally slightly worse under noisy transition probabilities, and the differences between algorithms were also slightly larger in these cases.

Limitations and Future Work

  • PVI Guarantee: The paper notes that PVI does not guarantee that the returned value function is $\epsilon$-contracted (a measure of convergence for value iteration). However, it suggests that using PVI's output as an initial value function for standard VI can lead to rapid convergence.
  • GVI Quality in Cyclic MDPs: For cyclic MDPs (where it's possible to return to a previous state), GVI's returned value function might be of poor quality, potentially limiting its effectiveness as a standalone preprocessing step.
  • Future Work: The authors are investigating the application of these ideas to Partially Observable Markov Decision Processes (POMDPs), which are significantly more complex than standard MDPs due to uncertainty about the current state.

Summary updated

BibTeX
@inproceedings{zhang1997fast,
  author = {Nevin Lianwen Zhang and Weihong Zhang},
  title = {{Fast Value Iteration for Goal-Directed Markov Decision Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1997},
}
Figure