Counterfactual Strategies for Markov Decision Processes

International Joint Conference on Artificial Intelligence, pp. 412–420

Abstract

Counterfactuals are widely used in AI to explain how minimal changes to a model’s input can lead to a different output. However, established methods for computing counterfactuals typically focus on one-step decision-making, and are not directly applicable to sequential decision-making tasks. This paper fills this gap by introducing counterfactual strategies for Markov Decision Processes (MDPs). During MDP execution, a strategy decides which of the enabled actions (with known probabilistic effects) to execute next. Given an initial strategy that reaches an undesired outcome with a probability above some limit, we identify minimal changes to the initial strategy to reduce that probability below the limit. We encode such counterfactual strategies as solutions to non-linear optimization problems, and further extend our encoding to synthesize diverse counterfactual strategies. We evaluate our approach on four real-world datasets and demonstrate its practical viability in sophisticated sequential decision-making tasks.

Authors 6

1. Paul Kobialka

   University of Oslo

   Affiliation as printed

   University of Oslo

2. Lina Gerlach Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

3. Francesco Leofante

   Imperial College London

   Affiliation as printed

   Imperial College London

4. Erika Ábrahám Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

5. Silvia Lizeth Tapia Tarifa

   University of Oslo

   Affiliation as printed

   University of Oslo

6. Einar Broch Johnsen

   University of Oslo

   Affiliation as printed

   University of Oslo