nips nips2010 nips2010-4 nips2010-4-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alan Fern, Prasad Tadepalli
Abstract: We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We first introduce a class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in finite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant’s action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution. 1
[1] Xinlong Bao, Jonathan L. Herlocker, and Thomas G. Dietterich. Fewer clicks and less frustration: reducing the cost of reaching the right folder. In IUI, pages 178–185, 2006.
[2] J. Boger, P. Poupart, J. Hoey, C. Boutilier, G. Fernie, and A. Mihailidis. A decision-theoretic approach to task assistance for persons with dementia. In IJCAI, 2005.
[3] Anton N. Dragunov, Thomas G. Dietterich, Kevin Johnsrude, Matt McLaughlin, Lida Li, and Jon L. Herlocker. Tasktracer: A desktop environment to support multi-tasking knowledge workers. In Proceedings of IUI, 2005.
[4] Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82(3):231–246, September 1989.
[5] A. Fern, S. Natarajan, K. Judah, and P. Tadepalli. A decision-theoretic model of assistance. In Proceedings of the International Joint Conference in AI, 2007.
[6] Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101:99–134, 1998.
[7] Tessa A. Lau, Steven A. Wolfman, Pedro Domingos, and Daniel S. Weld. Programming by demonstration using version space algebra. Machine Learning, 53(1-2):111–156, 2003.
[8] H. Lieberman. User interface goals, AI opportunities. AI Magazine, 30(2), 2009.
[9] M. L . Littman. Algorithms for Sequential Decision Making. PhD thesis, Brown University, Providence, RI, 1996.
[10] Martin Mundhenk. The complexity of planning with partially-observable Markov Decision Processes. PhD thesis, Friedrich-Schiller-Universitdt, 2001.
[11] K. Myers, P. Berry, J. Blythe, K. Conley, M. Gervasio, D. McGuinness, D. Morley, A. Pfeffer, M. Pollack, and M. Tambe. An intelligent personal assistant for task and time management. AI Magazine, 28(2):47– 61, 2007.
[12] C. Papadimitriou and J. Tsitsiklis. The complexity of Markov Decision Processes. Mathematics of Operations Research, 12(3):441–450, 1987.
[13] M. Tambe. Electric Elves: What went wrong and why. AI Magazine, 29(2), 2008. 9