A Tractable POMDP for a Class of Sequencing Problems
Paat Rusmevichientong, Benjamin van Roy
We consider a partially observable Markov decision problem (POMDP) that models a class of sequencing problems. Although POMDPs are typically intractable, our formulation admits tractable solution. Instead of maintaining a value function over a high-dimensional set of belief states, we reduce the state space to one of smaller dimension, in which grid-based dynamic programming techniques are effective. We develop an error bound for the resulting approximation, and discuss an application of the model to a problem in targeted advertising.
PDF Link: /papers/01/p480-rusmevichientong.pdf
AUTHOR = "Paat Rusmevichientong
and Benjamin van Roy",
TITLE = "A Tractable POMDP for a Class of Sequencing Problems",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "480--487"