Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)
Pascal Poupart, Craig Boutilier
We examine the problem of generating state-space compressions of POMDPs in a way that minimally impacts decision quality. We analyze the impact of compres- sions on decision quality, observing that compressions that allow accurate policy evaluation (prediction of expected future reward) will not affect decision qual- ity. We derive a set of sufﬁcient conditions that ensure accurate prediction in this respect, illustrate interesting mathematical properties these confer on lossless lin- ear compressions, and use these to derive an iterative procedure for ﬁnding good linear lossy compressions. We also elaborate on how structured representations of a POMDP can be used to ﬁnd such compressions.