Generalizing Causal Decision-Making: Markov Equivalence, Transportability and Counterfactuals
Organizations: Seoul National University Seoul, Republic of Korea
Abstract
Structural causal bandits use causal knowledge to guide exploration when reward mechanisms are unknown. This paper extends the approach to partially known causal structure, information from other environments, and realizable counterfactual actions. First, we develop graphical criteria for minimal intervention sets under Markov equivalence and characterize possibly-optimal minimal intervention sets for maximal ancestral graphs. A search algorithm finds sets that are possibly optimal in at least one graph represented by a partial ancestral graph. Second, we derive target reward bounds from source distributions through partial transportability, accounting for non-manipulable variables. Dominance relations provide further bounds for action pruning and restricted exploration, with a regret guarantee under valid prior bounds. Third, we formulate counterfactual structural causal bandits over actions supported by specified experimental capabilities. Graphical characterizations of minimality and possible optimality yield algorithms that remove equivalent or dominated choices while preserving an optimal action. Experiments with specified structural causal models examine how these reductions and transferred bounds affect learning. Together, these results clarify how causal knowledge and experimental capabilities determine which actions merit exploration and guide learning within the retained action space.
Figures & tables
| Layer (Symbolic) | Typical Activity | Typical Question | Example | Machine Learning | |
| Observational | Seeing | What is? How would seeing change my belief in ? | What does a symptom tell us about the disease? | Supervised / Unsupervised Learning | |
| Interventional | Doing | What if? What if I do ? | If I take aspirin, will my headache be cured? | Multi-armed bandits | |
| Counterfactual | Imagining | Why? What if I had acted differently? | Was it the aspirin that stopped my headache? |
| Task | POMIS union | DMIS | BF | ||
| 1 | 5 | 50k | 5 / 11 | 7 / 17 | 16 / 81 |
| 2 | 6 | 50k | 18 / 89 | 30 / 195 | 32 / 243 |
| 3 | 10 | 50k | 8 / 54 | 120 / 1,593 | 512 / 19,683 |
| 4 | 6 | 50k | 5 / 11 | 12 / 41 | 32 / 243 |
| 5 | 8 | 50k | 16 / 81 | 32 / 189 | 128 / 2,187 |
| 6 | 8 | 50k | 37 / 211 | 70 / 627 | 128 / 2,187 |
| Task | Solver | POMIS union | DMIS | BF |
| 1 | TS | \bm{23.3}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 9.4} | 63.4\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 20.9} | 199.6\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 22.6} |
| KL-UCB | \bm{54.2}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 12.6} | 111.8\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 21.4} | 352.5\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 25.9} | |
| 2 | TS | \bm{625.3}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 43.9} | 882.9\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 39.4} | 970.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 40.0} |
| KL-UCB | \bm{1017.8}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 34.7} | 1277.4\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 39.1} | 1363.9\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 30.1} | |
| 3 | TS | \bm{31.0}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 4.5} | 770.7\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 19.2} | 4929.9\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 40.1} |
| KL-UCB | \bm{30.5}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 4.1} | 835.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 21.6} | 6222.6\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 26.8} |
| Action | Decision | |||
| 0.0000 | 1.0000 | 1.0000 | Retain | |
| 0.0000 | 0.5900 | 1.0000 | Retain | |
| 0.1675 | 1.0000 | 1.0000 | Retain | |
| 0.2965 | 0.5450 | 0.7940 | Remove | |
| 0.8325 | 1.0000 | 1.0000 | Retain | |
| 0.2935 | 0.5900 | 0.7960 | Remove |
| Action | ||||
| 0.4844 | 0.4844 | 0.4844 | 0.4844 | |
| 0.2097 | 0.4031 | 0.6783 | 0.6783 | |
| 0.2752 | 0.5969 | 0.8066 | 0.7697 |
| Local upper bound | Returned bound | ||
| 0.8066 | 0.7697 | ||
| 0.8066 | 0.7697 | ||
| 0.8070 | 0.7697 | ||
| 0.7697 | 0.7697 |
| Action | Decision | |||
| 0.5514 | 0.5514 | 0.5514 | Remove | |
| 0.2140 | 0.4553 | 1.0000 | Retain | |
| 0.4092 | 0.6110 | 1.0000 | Retain | |
| 0.0713 | 0.1990 | 0.7901 | Remove | |
| 0.2176 | 1.0000 | 1.0000 | Retain | |
| 0.0344 | 0.0344 | 0.0344 | Remove |
| Action | ||||
| 0.0883 | 0.0883 | 0.0883 | 0.0883 | |
| 0.0090 | 0.0654 | 0.1451 | 0.0960 | |
| 0.0797 | 0.0914 | 0.1004 | 0.0960 |
| Task | UCB | poUCB | trUCB | ||
| 1 | 3 | 10k | 4 / 9 | 2 / 6 | 2 / 4 |
| 2 | 4 | 10k | 2 / 3 | 2 / 3 | 2 / 3 |
| 3 | 6 | 10k | 8 / 27 | 4 / 7 | 3 / 4 |
| Policy | Task 1 | Task 2 | Task 3 |
| UCB | 247.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 19.6} | 67.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 5.9} | 248.6\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 11.3} |
| poUCB | 94.8\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 12.1} | 67.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 5.9} | 132.7\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 13.2} |
| trUCB | \bm{13.0}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 21.6} | \bm{55.4}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 60.7} | \bm{32.2}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 35.2} |
| Bernstein-POMIS | 38.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 43.5} | 63.8\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 6.7} | 74.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 63.4} |
| Pruning only | \bm{13.0}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 21.6} | 63.8\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 6.7} | \bm{32.2}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 35.2} |
| Pruning + clipping | \bm{13.0}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 21.6} | 121.7\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 128.1} | \bm{32.2}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 35.2} |
| Task | CTF-POMIS | CTF-MIS | POMIS | ||
| 1 | 4 | 10k | 2 / 8 | 8 / 21 | 2 / 6 |
| 2 | 5 | 10k | 6 / 36 | 17 / 67 | 4 / 16 |
| 3(a), 3(b) | 7 | 100k | 5 / 52 | 35 / 187 | 5 / 36 |
| Task | Solver | CTF-POMIS | CTF-MIS | POMIS |
| 1 | TS | \bm{51.4}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 25.7} | 136.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 31.7} | 666.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 3.5} |
| KL-UCB | \bm{117.7}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 20.2} | 314.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 33.6} | 685.9\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 5.5} | |
| 2 | TS | \bm{374.7}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 45.2} | 570.3\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 45.7} | 1255.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 77.4} |
| KL-UCB | \bm{706.1}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 46.9} | 901.4\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 39.7} | 1488.8\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 47.2} | |
| 3(a) | TS | \bm{1252.4}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 161.5} | 4195.1\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 256.2} | 3502.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 171.9} |
| KL-UCB | \bm{3275.9}\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 185.2} | 8924.4\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 246.9} | 5166.2\,{\scriptstyle\color[rgb]{0.5,0.5,0.5}\!\pm 187.9} |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| 0 | 0 | 0 | 1 | 2 | 1 | 1 | 2 | |||||
| 0 | 1 | 0 | 1 | 2 | 0 | 0 | 1 | |||||
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 2 | |||||
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | |||||