Markov Decision Processes (MDPs) are a class of models used by intelligent agents to reason about their environment.  MDPs describe the environment and the (stochastic) effects of the agent's actions.  Given an MDP, an intelligent agent can determine it optimal course of actions (aka, policy) in order to reach their goal with minimal cost / maximal reward.

The AI may propose actions that appear illogical to a human user in the current state.  The irrationality of such decisions might an error in the MDP, a bug in the AI, or a superb strategy that the user did not anticipate (such as taking a back step to take a better jump).  To distinguish between these scenarios, the AI needs to provide explanations that justify or illuminate the decisions.

There is no single definition of what an explanation is.  In this work, we are interested in `contrastive explanations' that answer the question

`What is the minimal change to the MDP that would modify the optimal policy?'

These answers allow the human user to better understand what aspects of the environment affect the decision.

Internship

During this internship, you will develop methods for contrastive explanations of MDPs.  You will determine how queries from users about policies can be formalised: develop algorithms to solve these problems; and propose heuristics to tame the computational complexity of these problems. We expect that a Branch \& Bound procedure will be required and that clever evaluation procedures will be necessary to avoid exponential search spaces.

In practice, the internship will be split in several subtasks as follows:

• Review the existing scientific literature on explanations for MDPs.
• Formalise (= translate in mathematical language) natural queries that a user might want being answered.
• Build benchmarks for testing the algorithms.
• Propose algorithms and test their scalability.