A Tractable POMDP for a Class of Sequencing Problems
This work addresses a specific computational bottleneck in POMDPs for researchers and practitioners in areas like targeted advertising, but it is incremental as it builds on existing dynamic programming techniques.
The authors tackled the intractability of POMDPs in sequencing problems by reducing the state space to enable tractable solutions using grid-based dynamic programming, and they developed an error bound for the approximation with an application to targeted advertising.
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.