@conference {1509746,
	title = {Exploiting Belief Bounds: Practical POMDPs for Personal Assistant Agents },
	booktitle = {International Conference on Autonomous Agents and Multiagent Systems, AAMAS},
	year = {2005},
	abstract = {Agents or agent teams deployed to assist humans often face the
challenges of monitoring the state of key processes in their environment (including the state of their human users themselves) and
making periodic decisions based on such monitoring. POMDPs appear well suited to enable agents to address these challenges, given
the uncertain environment and cost of actions, but optimal policy
generation for POMDPs is computationally expensive. This paper
introduces three key techniques to speedup POMDP policy generation that exploit the notion of progress or dynamics in personal assistant domains. Policy computation is restricted to the belief space
polytope that remains reachable given the progress structure of a
domain. We introduce new algorithms; particularly one based on
applying Lagrangian methods to compute a bounded belief space
support in polynomial time. Our techniques are complementary to
many existing exact and approximate POMDP policy generation algorithms. Indeed, we illustrate this by enhancing two of the fastest
existing algorithms for exact POMDP policy generation. The order
of magnitude speedups demonstrate the utility of our techniques in
facilitating the deployment of POMDPs within agents assisting human users.},
	author = {Varakantham, Pradeep and Rajiv T. Maheswaran and Tambe, Milind}
}
