Partially Observable Markov Decision Processes: A Geometric Technique and Analysis

• 成果类型: Article
• 署名作者: Zhang, Hao
• 署名单位: University of Southern California
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0697
• 发表日期: 2010
• 页码: 214-228
• 关键词: minkowski addition; infinite-horizon; quality-control; POLICY; complexity

摘要

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.