A Tractable POMDP for a Class of Sequencing Problems
  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.
