This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Zhang, H.

Partially Observable Markov Decision Processes: A Geometric Technique and Analysis

Marshall School of Business, University of Southern California, Los Angeles, California 90089
zhanghao{at}usc.edu

This paper presents a novel framework for studying partially observable Markov decision processes (POMDPs) with finite state, action, observation sets, and discounted rewards. The new framework is solely based on future-reward vectors associated with future policies, which is more parsimonious than the traditional framework based on belief vectors. It reveals the connection between the POMDP problem and two computational geometry problems, i.e., finding the vertices of a convex hull and finding the Minkowski sum of convex polytopes, which can help solve the POMDP problem more efficiently. The new framework can clarify some existing algorithms over both finite and infinite horizons and shed new light on them. It also facilitates the comparison of POMDPs with respect to their degree of observability, as a useful structural result.

Subject classifications: dynamic programming; Markov; analysis of algorithms; computational complexity; mathematics; combinatorics; computers/computer science; artificial intelligence.
History: Received January 2008; revision received July 2008; accepted November 2008.