Bounding Counterfactuals in Hidden Markov Models and Beyond

Answering a counterfactual query (CQ) in a hidden Markov model (HMM) requires embedding the HMM in a so-called structural causal model (SCM). In general, however, we don't have sufficient information to fully specify the SCM and so we cannot provide an exact answer to the CQ. Nonetheless, the known structure of the given HMM implies we should only consider SCMs that have no hidden confounding. We use this observation to optimize over the space of feasible SCMs to compute upper and lower bounds on the CQ and to the best of our knowledge, we are the first to compute such bounds in a HMM. We consider two applications of our framework. The first application concerns the well-known dishonest casino HMM. In this case, the CQ is the casino’s expected winnings that are attributable to cheating (EWAC) and we show that bounds on the EWAC can be computed as the solutions to simple linear programs. Our second application concerns a patient who died from breast cancer after being denied regular screenings by her insurance company. We propose an extended HMM to model the problem dynamics and we bound the CQ - the so-called probability of necessity - by formulating and solving polynomial programs. We also show how informative bounds can still be computed even when the original polynomial programs are too difficult to solve. Finally, we disprove a recent conjecture suggesting that the Gumbel-max distribution is the unique mechanism for modeling SCMs with the so-called counterfactual stability (CS) property