hide
Free keywords:
Computer Science, Learning, cs.LG,Computer Science, Computers and Society, cs.CY,Statistics, Machine Learning, stat.ML
Abstract:
Methods to find counterfactual explanations have predominantly focused on one
step decision making processes. In this work, we initiate the development of
methods to find counterfactual explanations for decision making processes in
which multiple, dependent actions are taken sequentially over time. We start by
formally characterizing a sequence of actions and states using finite horizon
Markov decision processes and the Gumbel-Max structural causal model. Building
upon this characterization, we formally state the problem of finding
counterfactual explanations for sequential decision making processes. In our
problem formulation, the counterfactual explanation specifies an alternative
sequence of actions differing in at most k actions from the observed sequence
that could have led the observed process realization to a better outcome. Then,
we introduce a polynomial time algorithm based on dynamic programming to build
a counterfactual policy that is guaranteed to always provide the optimal
counterfactual explanation on every possible realization of the counterfactual
environment dynamics. We validate our algorithm using both synthetic and real
data from cognitive behavioral therapy and show that the counterfactual
explanations our algorithm finds can provide valuable insights to enhance
sequential decision making under uncertainty.
