  Counterfactual explanations (CFEs) are sets of actions that an agent with a
negative classification could take to achieve a (desired) positive
classification, for consequential decisions such as loan applications, hiring,
admissions, etc. In this work, we consider settings where optimal CFEs
correspond to solutions of weighted set cover problems. In particular, there is
a collection of actions that agents can perform that each have their own cost
and each provide the agent with different sets of capabilities. The agent wants
to perform the cheapest subset of actions that together provide all the needed
capabilities to achieve a positive classification. Since this is an NP-hard
optimization problem, we are interested in the question: can we, from training
data (instances of agents and their optimal CFEs) learn a CFE generator that
will quickly provide optimal sets of actions for new agents?
  In this work, we provide a deep-network learning procedure that we show
experimentally is able to achieve strong performance at this task. We consider
several problem formulations, including formulations in which the underlying
"capabilities" and effects of actions are not explicitly provided, and so there
is an informational challenge in addition to the computational challenge. Our
problem can also be viewed as one of learning an optimal policy in a family of
large but deterministic Markov Decision Processes (MDPs).
