Minimal Sufficient Explanations for Factored Markov Decision Processes

By Omar Zia Khan, Pascal Poupart, James P. Black. 2009

93 citations recorded by the source corpus.

Explaining policies of Markov Decision Processes (MDPs) is complicated due to their probabilistic and sequential nature. We present a technique to explain policies for factored MDP by populating a set of domain-independent templates. We also present a mechanism to determine a minimal set of templates that, viewed together, completely justify the policy. Our explanations can be generated automatically at run-time with no additional effort required from the MDP designer. We demonstrate our technique using the problems of advising undergraduate students in their course selection and assisting people with dementia in completing the task of handwashing. We also evaluate our explanations for course-advising through a user study involving students.

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

Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI (2019, neutral): “…2007; Freuder, Likitvivatanavong, and Wallace, 2001; Haddawy, et al., 1997; Henrion and Druzdzel, 1990a, 1990b; Herlocker, Konstan, and Riedl, 2000; Khan, Poupart, and Black, 2009; Kisa, Van den Broeck, Choi, and Darwiche, 2014; Kofod-Petersen, Cassens, and Aamodt, 2008; Lacave and Díez, 2002;…”
Improving Robot Controller Transparency Through Autonomous Policy Explanation (2017, background): “[19] introduce the notion of a minimally sufficient explanation for action selection at a given world state, using the fewest possible terms.”
Visualizing and Understanding Atari Agents (2017, background): “Their key contribution is a method of approximating the observed behavior of deep RL policies via "Semi-Aggregated" Markov Decision Processes (SAMDPs), which are used to gain insights about the deep RL policies.”
Learn to Interpret Atari Agents (2018, background): “Interpreting RL systems traditionally involves language generation via first-order logic (Dodson et al., 2011; Elizalde et al., 2008; Khan et al., 2009; Hayes & Shah, 2017).”
The Impact of POMDP-Generated Explanations on Trust and Performance in Human-Robot Teams (2016, background): “While most of this work operated on rule- and logic-based systems, there has been more recent work on generating explanations based on Markov Decision Problems (MDPs) [8, 15].”
Unsupervised Video Object Segmentation for Deep Reinforcement Learning (2018, methodology): “[14] pioneered a generic technique to explain policies for factored Markov decision processes in terms of the occupancy frequency of future states.”
Explainable Reinforcement Learning Through a Causal Lens (2019, background): “Taking the long term effect an action has, Khan, Poupart, and Black (2009) proposed generating sufﬁcient and minimal explanations for MDPs using domain independent templates.”
A Natural Language Argumentation Interface for Explanation Generation in Markov Decision Processes (2011, background): “Since stochastic planning methods are generally not well understood by our intended users, we do not restrict our explanations to cover, for example, some minimum portion of the total reward [9], and instead choose explanation primitives that, while still factual, will be most convincing to the user”
Explainable Reinforcement Learning via Reward Decomposition (2019, result): “Prior work [8] developed a similar notion to MSX.”
Explanation and Justification in Machine Learning : A Survey Or (2017, background): “, 2007] describe an explanation system that assists plant operators in executing necessary operations; [Khan et al., 2009] explore the minimal explanation sufficient for tasks such as picking the next course in a college curriculum; [Dodson et al.”