A Decision-Theoretic Model of Assistance

By Alan Fern, Sriraam Natarajan, Kshitij Judah, Prasad Tadepalli. 2007

130 citations recorded by the source corpus.

There is a growing interest in intelligent assistants for a variety of applications from sorting email to helping people with disabilities to do their daily chores. In this paper, we formulate the problem of intelligent assistance in a decision-theoretic framework, and present both theoretical and empirical results. We first introduce a class of POMDPs called hidden-goal MDPs (HGMDPs), which formalizes 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 for HGMDPs is PSPACE-complete even for deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), which are sufficient for modeling many real-world problems. We show classes of HAMDPs for which efficient algorithms are possible. More interestingly, for general HAMDPs we show that a simple myopic policy achieves a near optimal regret, compared to an oracle assistant that knows the agent's goal. We then introduce more sophisticated versions of this policy for the general case of HGMDPs that we combine with a novel approach for quickly learning about the agent being assisted. We evaluate our approach in two game-like computer environments where human subjects perform tasks, and in a real-world domain of providing assistance during folder navigation in a computer desktop environment. The results show that in all three domains the framework results in an assistant that substantially reduces user effort with only modest computation.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Cooperative Inverse Reinforcement Learning (2016, background): “Fern et al. (2014) model the human as part of the environment.”
Information gathering actions over human internal state (2016, background): “(4) Optimizing expected reward now entails reasoning about the effects that the robot actions will have on what observations the robot will get, i.e., the actions that the human will take in response, and how useful these observations will be in shattering ambiguity about ϕ.”
Sidekick agents for sequential planning problems (2013, methodology): “, who developed a decision-theoretic model of assistance that used the same basic strategy for building human models outlined here, although our formulation is somewhat more general in that we allow for a range of control strategies that attempt to reason about how to mitigate the sidekick's uncerta”
The Off-Switch Game (2016, unknown): “Fern et al. (2014) consider hidden-goal Markov decision processes.”