Abstract
Standard Hidden Markov Models (HMMs) are effective for state estimation but lack the causal structure necessary to answer counterfactual "what-if" questions. This paper addresses the problem of attribution in dynamic systems by framing the classic "Dishonest Casino" problem within a Structural Causal Model (SCM). We introduce the Expected Winnings Attributable to Cheating (EWAC) metric to quantify the portion of observed winnings directly caused by a loaded die versus simple luck. Because the underlying causal mechanism is often underdetermined by observed data, we propose a linear programming framework to derive sharp upper and lower bounds on EWAC. Our results show that while counterfactuals are partially identifiable for finite sequences, time-averaged attribution becomes fully identifiable as the sequence length grows.
Introduction: The Attribution Problem in HMMs
In the canonical "Dishonest Casino" example, an observer sees a sequence of die rolls and must infer when the casino switched from a fair die to a loaded one. Traditional HMM tools, such as the Viterbi algorithm, provide the most likely sequence of hidden states (fair vs. loaded). However, they cannot answer a deeper causal question: "Given the observed rolls, how much more did the casino win because they cheated, compared to what they would have won had they played fair the whole time?"
Standard HMMs (Figure 1) only specify marginal distributions—the behavior of the fair die and the loaded die independently. They do not specify the coupling, or the joint relationship between the factual outcome and the counterfactual alternative. Consequently, multiple causal mechanisms can produce the same observed HMM, leading to a range of possible counterfactual outcomes rather than a single point estimate. This phenomenon is known as partial identifiability.
Methodology: SCM Embedding and EWAC
To resolve this, the authors bridge probabilistic HMMs and causal inference by embedding the HMM into a Structural Causal Model (SCM). This is achieved by introducing exogenous noise variables ($U_t, V_t$) that drive state transitions and die emissions.
As shown in Figure 2, the SCM provides the necessary structure to perform counterfactual reasoning. The authors define a new metric, Expected Winnings Attributable to Cheating (EWAC), which calculates the difference between observed winnings and the expected winnings in a counterfactual world where the casino was forced to use the fair die throughout the entire sequence.
Linear Programming Bounds
Since the exact SCM is typically unknown, the joint distribution (the "copula") of the fair and loaded dice is treated as a decision variable. The authors solve Linear Programs (LPs) to find the maximum and minimum possible values of EWAC consistent with the observed HMM parameters. To narrow these bounds, they introduce several domain-specific constraints:
- Time-homogeneity: The cheating mechanism remains constant over time.
- Pathwise Monotonicity: A high roll with a fair die implies an equal or higher roll with a loaded die.
- Counterfactual Stability (CS): Outcomes are unlikely to change under intervention if they were already highly probable.
Key Insights and Results
The research yields several critical insights into the nature of causal attribution in sequences:
- Luck vs. Cheating: The model distinguishes between winnings due to the loaded die's bias and winnings due to simple good luck. If a casino rolls a 6 while cheating, but the causal mechanism dictates they would have rolled a 6 with a fair die anyway, that specific win is not "attributable to cheating."
- The Importance of Abduction: Counterfactual analysis requires an "abduction" step to infer the state of the world (noise/luck) from data. The authors demonstrate that naive estimates ignoring the specific sequence of rolls can fall outside the mathematically valid causal bounds.
- Identifiability at Infinity: A major theoretical finding is that while EWAC is partially identifiable for short sequences, the time-averaged EWAC converges to a single value as the number of rolls $T \to \infty$. This proves that long-term attribution is fully identifiable.
- Sharpness and Convergence: Numerical experiments on synthetic "lucky" and "unlucky" paths confirm that the LP-based bounds are sharp. Adding the CS constraint significantly narrows the range, providing more precise estimates for legal or regulatory applications.
Conclusion
This work provides the first framework for deriving sharp counterfactual bounds in dynamic HMM settings. By moving from probabilistic guessing to causal attribution, it offers a rigorous way to penalize dishonest behavior or evaluate interventions. Future work will extend this to Generalized HMMs and Partially Observable Markov Decision Processes (POMDPs), enabling counterfactual policy evaluation in complex environments like healthcare and marketing.
Summary updated