Accession Number:

ADA456811

Title:

Generalizing Dijkstra's Algorithm and Gaussian Elimination for Solving MDPs

Descriptive Note:

Research paper

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2005-05-01

Pagination or Media Count:

25.0

Abstract:

The authors study the problem of computing the optimal value function for a Markov Decision Process MDP with positive costs. Computing this function quickly and accurately is a basic step in many schemes for deciding how to act in stochastic environments. There are efficient algorithms that compute value functions for special types of MDPs. For deterministic MDPs with S states and A actions, Dijkstras algorithm runs in time OAS log S. And, in single-action MDPs Markov chains, standard linear-algebraic algorithms find the value function in time OS sup 3, or faster by taking advantage of sparsity or good conditioning. Algorithms for solving general MDPs can take much longer the authors are not aware of any speed guarantees better than those for comparably sized linear programs. They present a family of algorithms that reduce to Dijkstras algorithm when applied to deterministic MDPs, and to standard techniques for solving linear equations when applied to Markov chains. More importantly, they demonstrate experimentally that these algorithms perform well when applied to MDPs that almost have the required special structure.

Subject Categories:

  • Numerical Mathematics
  • Statistics and Probability
  • Computer Programming and Software
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE