# Counterfactual Strategies for Markov Decision Processes

arXiv: https://arxiv.org/abs/2505.09412 · HTML: https://mlsanity.com/paper/2505.09412/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 14 May 2025.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Counterfactual Probabilities: Computational Methods, Bounds and Applications](https://mlsanity.com/paper/1302.6784/) (2013)
- [Counterfactual Explanations in Sequential Decision Making Under Uncertainty](https://mlsanity.com/paper/2107.02776/) (2021)
- [The Music Streaming Sessions Dataset](https://mlsanity.com/paper/1901.09851/) (2018)
- [Redefining Counterfactual Explanations for Reinforcement Learning: Overview, Challenges and Opportunities](https://mlsanity.com/paper/2210.11846/) (2022)
- [Counterfactual Explanations for Predictive Business Process Monitoring](https://mlsanity.com/paper/2202.12018/) (2022)
- [Synthesis in pMDPs: A Tale of 1001 Parameters](https://mlsanity.com/paper/1803.02884/) (2018)
- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [Sequential Convex Programming for the Efficient Verification of Parametric MDPs](https://mlsanity.com/paper/1702.00063/) (2017)
- [Counterfactual Influence in Markov Decision Processes](https://mlsanity.com/paper/2402.08514/) (2024)

## Built on by (most cited first, 1 of 1)

- [Attribution-based Explanations for Markov Decision Processes](https://mlsanity.com/paper/2605.09780/) (2026)

## Abstract (arXiv)

Counterfactuals are widely used in AI to explain how minimal changes to a model's input can lead to a different output. However, established methods for computing counterfactuals typically focus on one-step decision-making, and are not directly applicable to sequential decision-making tasks. This paper fills this gap by introducing counterfactual strategies for Markov Decision Processes (MDPs). During MDP execution, a strategy decides which of the enabled actions (with known probabilistic effects) to execute next. Given an initial strategy that reaches an undesired outcome with a probability above some limit, we identify minimal changes to the initial strategy to reduce that probability below the limit. We encode such counterfactual strategies as solutions to non-linear optimization problems, and further extend our encoding to synthesize diverse counterfactual strategies. We evaluate our approach on four real-world datasets and demonstrate its practical viability in sophisticated sequential decision-making tasks.