arxiv: 2605.09780 · v2 · submitted 2026-05-10 · 💻 cs.AI

Recognition: no theorem link

Attribution-based Explanations for Markov Decision Processes

Paul Kobialka , Andrea Pferscher , Francesco Leofante , Erika \'Abrah\'am , Silvia Lizeth Tapia Tarifa , Einar Broch Johnsen

Authors on Pith no claims yet

Pith reviewed 2026-05-13 05:52 UTC · model grok-4.3

classification 💻 cs.AI

keywords attributionsexplanationsMarkov Decision Processesstrategy synthesisimportance scoresinterpretabilitysequential decision-making

0 comments

The pith

Attributions for MDPs assign importance scores to states and execution paths via strategy synthesis.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends attribution techniques from single static inputs to sequential decision making under uncertainty in Markov Decision Processes. It formally defines what such attributions should capture, namely numerical scores that reflect the importance of individual states and of complete execution paths. These scores are obtained by reducing the attribution task to a strategy synthesis problem, which remains tractable even when the MDP contains non-deterministic transitions. A reader would care because the resulting explanations make the internal logic of planning agents observable and therefore more trustworthy in applications that involve repeated choices.

Core claim

Attributions in MDPs should consist of importance scores assigned both to individual states and to full execution paths; these scores can be computed efficiently by leveraging strategy synthesis techniques that handle the non-determinism inherent in the model.

What carries the argument

Strategy synthesis applied to derive importance scores for states and paths in MDPs.

If this is right

Importance scores become available for every state an agent may visit.
Complete paths receive scores that reflect their contribution to outcomes.
Non-determinism is handled without exponential blow-up in the computation.
Case-study evaluations confirm that the scores yield concrete insights into agent logic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction to synthesis could be reused for other stochastic models such as POMDPs.
High-scoring states and paths could serve as targets when debugging or refining a policy.
The method supplies a concrete baseline against which learned explanations from neural policies might be compared.

Load-bearing premise

Existing strategy synthesis algorithms can be applied to general MDPs to produce accurate attribution scores without prohibitive computational cost.

What would settle it

An MDP in which the synthesized scores do not correctly identify the states whose removal changes the agent's optimal behavior would show the characterization to be incorrect.

Figures

Figures reproduced from arXiv: 2605.09780 by Andrea Pferscher, Einar Broch Johnsen, Erika \'Abrah\'am, Francesco Leofante, Paul Kobialka, Silvia Lizeth Tapia Tarifa.

**Figure 2.** Figure 2: Encoding QP for optimizing the importance of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 4.** Figure 4: Gridworld example, where the agent has to reach the green [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 5.** Figure 5: Example for Non-monotone Sequence of Improvements. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

read the original abstract

Attribution techniques explain the outcome of an AI model by assigning a numerical score to its inputs. So far, these techniques have mainly focused on attributing importance to static input features at a single point in time, and thus fail to generalize to sequential decision-making settings. This paper fills this gap by introducing techniques to generate attribution-based explanations for Markov Decision Processes (MDPs). We give a formal characterization of what attributions should represent in MDPs, focusing on explanations that assign importance scores to both individual states and execution paths. We show how importance scores can be computed by leveraging techniques for strategy synthesis, enabling the efficient computation of these scores despite the non-determinism inherent in an MDP. We evaluate our approach on five case-studies, demonstrating its utility in providing interpretable insights into the logic of sequential decision-making agents.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper formalizes state and path attributions in MDPs by reducing them to strategy synthesis, which is a clean extension but the efficiency claim has no scaling support.

read the letter

The main takeaway is that this work defines what attributions should mean in an MDP—importance scores on individual states and on full execution paths—and shows how to compute them by calling existing strategy synthesis routines. That reduction is the central technical move and it looks coherent on paper. Prior attribution techniques were stuck on single-step inputs, so handling sequences and nondeterminism this way is genuinely new. The five case studies then demonstrate that the scores can surface interpretable reasons for an agent's choices in small examples, which is useful for anyone who needs to debug or explain sequential policies. The formal part avoids obvious circularity and builds on established synthesis methods rather than inventing new primitives from scratch. The soft spot is the efficiency story. The abstract promises efficient computation despite nondeterminism, yet the case studies stay small and there are no complexity bounds, no runtime plots, and no comparison against the known hardness of many MDP synthesis problems. If synthesis calls blow up on realistic state spaces, the practical payoff disappears even if the characterization stays correct. This is aimed at people working on explainable RL and formal methods for planning. A reader who wants a structured way to assign blame across trajectories will get something concrete from it. It deserves a serious referee because the formal reduction is fresh and the idea is internally consistent, even though reviewers will need to press on whether the computational claims survive beyond the toy cases.

Referee Report

1 major / 0 minor

Summary. The paper introduces attribution-based explanations for Markov Decision Processes (MDPs), providing a formal characterization of what attributions should represent by assigning importance scores to both individual states and execution paths. It shows how these scores can be computed by reducing the attribution problem to strategy synthesis techniques, which handles the non-determinism in MDPs, and demonstrates the approach via five case studies that yield interpretable insights into sequential decision-making agents.

Significance. If the formal characterization and reduction hold, the work would be significant for extending attribution methods beyond static inputs to sequential settings in reinforcement learning and planning. The explicit use of strategy synthesis as a computational engine is a strength, as it leverages existing algorithms rather than inventing new ones from scratch, and the five case studies provide concrete demonstrations of utility in explaining agent logic.

major comments (1)

[Evaluation] Evaluation section (five case studies): The manuscript claims 'efficient computation' of importance scores via strategy synthesis despite MDP non-determinism, but the case studies provide only existence proofs on small instances with no complexity bounds, no runtime scaling plots, and no direct comparison against the PSPACE-hardness of many MDP synthesis problems. This is load-bearing for the central computational claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive review and for highlighting the need to strengthen the computational claims in the evaluation. We address the major comment below and describe the revisions we will make to the manuscript.

read point-by-point responses

Referee: [Evaluation] Evaluation section (five case studies): The manuscript claims 'efficient computation' of importance scores via strategy synthesis despite MDP non-determinism, but the case studies provide only existence proofs on small instances with no complexity bounds, no runtime scaling plots, and no direct comparison against the PSPACE-hardness of many MDP synthesis problems. This is load-bearing for the central computational claim.

Authors: We agree that the current case studies serve primarily as existence proofs on small MDPs and do not include runtime scaling experiments, explicit complexity bounds, or direct comparisons to the PSPACE-completeness of MDP strategy synthesis. The manuscript's claim of 'efficient computation' rests on the reduction to existing synthesis algorithms rather than on new empirical scaling data. We will revise the evaluation section to add: (1) a discussion of the complexity inherited from the synthesis problem (noting that while worst-case PSPACE-hard, practical solvers often scale to instances of interest in verification and planning), (2) runtime measurements for the five case studies, and (3) a brief comparison to known hardness results. These changes will clarify that the approach leverages mature synthesis tools without claiming new asymptotic improvements. We do not plan to add large-scale synthetic benchmarks in this revision, as the core contribution is the formal characterization and reduction. revision: partial

Circularity Check

0 steps flagged

No circularity: attributions defined formally and reduced to external strategy synthesis

full rationale

The paper's core contribution is a formal characterization of attributions in MDPs (importance scores for states and paths) followed by a reduction to existing strategy synthesis algorithms for computation. This reduction relies on external, independently developed techniques for MDPs rather than any self-definition, fitted parameters renamed as predictions, or self-citation chains. No equations or claims in the provided text equate the output attributions to the inputs by construction, and the five case studies serve as empirical demonstrations rather than load-bearing proofs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard MDP definitions and existing strategy synthesis methods; no new free parameters, axioms, or invented entities are introduced in the abstract.

axioms (1)

domain assumption MDPs are appropriate models for sequential decision-making under uncertainty
Invoked as the setting for the attribution techniques.

pith-pipeline@v0.9.0 · 5453 in / 947 out tokens · 22653 ms · 2026-05-13T05:52:43.096140+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[1]

Hierarchical optimization: An introduc- tion.Annals of operations research, 34(1):1–11,

[Anandalingam and Friesz, 1992] Gnana Anandalingam and Terry L Friesz. Hierarchical optimization: An introduc- tion.Annals of operations research, 34(1):1–11,

work page 1992
[2]

MIT press,

[Baier and Katoen, 2008] Christel Baier and Joost-Pieter Katoen.Principles of Model Checking. MIT press,

work page 2008
[3]

Responsibility attribution in parameterized Markovian models

[Baieret al., 2021 ] Christel Baier, Florian Funke, and Ru- pak Majumdar. Responsibility attribution in parameterized Markovian models. InProceedings of the AAAI Confer- ence on Artificial Intelligence, pages 11734–11743. AAAI Press,

work page 2021
[4]

Responsibility in actor-based sys- tems

[Baieret al., 2025 ] Christel Baier, Sascha Kl ¨uppelholz, and Johannes Lehmann. Responsibility in actor-based sys- tems. InRebeca for Actor Analysis in Action: Essays Dedicated to Marjan Sirjani on the Occasion of Her 60th Birthday, pages 44–69. Springer,

work page 2025
[5]

[Banzhaf, 1965] J.F. Banzhaf. Weighted voting doesn’t work: A mathematical analysis.Rutgers Law Review, 19(2):317–343,

work page 1965
[6]

Exact quadratic convex reformula- tions of mixed-integer quadratically constrained problems

[Billionnetet al., 2016 ] Alain Billionnet, Sourour Elloumi, and Am´elie Lambert. Exact quadratic convex reformula- tions of mixed-integer quadratically constrained problems. Mathematical Programming, 158(1):235–266,

work page 2016
[7]

Benchmarking and survey of expla- nation methods for black box models.Data Mining and Knowledge Discovery, 37(5):1719–1778,

[Bodriaet al., 2023 ] Francesco Bodria, Fosca Giannotti, Riccardo Guidotti, Francesca Naretto, Dino Pedreschi, and Salvatore Rinzivillo. Benchmarking and survey of expla- nation methods for black box models.Data Mining and Knowledge Discovery, 37(5):1719–1778,

work page 2023
[8]

Cambridge univer- sity press,

[Boyd and Vandenberghe, 2004] Stephen Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge univer- sity press,

work page 2004
[9]

The music streaming sessions dataset

[Brostet al., 2019 ] Brian Brost, Rishabh Mehrotra, and Tris- tan Jehan. The music streaming sessions dataset. InThe World Wide Web Conference, pages 2594–2600,

work page 2019
[10]

[Forejtet al., 2011 ] V ojtˇech Forejt, Marta Kwiatkowska, Gethin Norman, and David Parker. Automated verifica- tion techniques for probabilistic systems.Formal Methods for Eternal Networked Software Systems: 11th Interna- tional School on Formal Methods for the Design of Com- puter, Communication and Software Systems, SFM 2011, Bertinoro, Italy, June 13-18,

work page 2011
[11]

[Garey and Johnson, 1979] Michael R Garey and David S Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman,

work page 1979
[12]

Counterfactual influence in Markov decision processes

[Kazemiet al., 2025 ] Milad Kazemi, Jessica Lally, Ekate- rina Tishchenko, Hana Chockler, and Nicola Paoletti. Counterfactual influence in Markov decision processes. In Causal Learning and Reasoning, pages 792–817. PMLR,

work page 2025
[13]

User jour- ney games: Automating user-centric analysis.Software and Systems Modeling, 23(3):605–624,

[Kobialkaet al., 2024 ] Paul Kobialka, S Lizeth Tapia Tarifa, Gunnar R Bergersen, and Einar Broch Johnsen. User jour- ney games: Automating user-centric analysis.Software and Systems Modeling, 23(3):605–624,

work page 2024
[14]

Counterfactual strategies for Markov decision processes

[Kobialkaet al., 2025 ] Paul Kobialka, Lina Gerlach, Francesco Leofante, Erika ´Abrah´am, Silvia Lizeth Tapia Tarifa, and Einar Broch Johnsen. Counterfactual strategies for Markov decision processes. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 412–420...

work page 2025
[15]

Machine learning in bank- ing risk management: A literature review.Risks, 7(1):29,

[Leoet al., 2019 ] Martin Leo, Suneel Sharma, and Koilakuntla Maddulety. Machine learning in bank- ing risk management: A literature review.Risks, 7(1):29,

work page 2019
[16]

Lundberg and Su-In Lee

[Lundberg and Lee, 2017] Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. InAdvances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Sys- tems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4765–4774,

work page 2017
[17]

Learning deterministic probabilistic automata from a model checking perspective.Machine Learning, 105(2):255–299,

[Maoet al., 2016 ] Hua Mao, Yingke Chen, Manfred Jaeger, Thomas D Nielsen, Kim G Larsen, and Brian Nielsen. Learning deterministic probabilistic automata from a model checking perspective.Machine Learning, 105(2):255–299,

work page 2016
[18]

[Molnar, 2020] Christoph Molnar.Interpretable Machine Learning. Lulu. com,

work page 2020
[19]

Advancing credit risk modelling with machine learning: A comprehensive review of the state-of-the-art.Engineering Applications of Artificial In- telligence, 137:109082,

[Montevechiet al., 2024 ] Andr´e Aoun Montevechi, Rafael de Carvalho Miranda, Andr´e Luiz Medeiros, and Jos´e Ar- naldo Barra Montevechi. Advancing credit risk modelling with machine learning: A comprehensive review of the state-of-the-art.Engineering Applications of Artificial In- telligence, 137:109082,

work page 2024
[20]

Aich- ernig, Ingo Pill, Andrea Pferscher, and Martin Tappler

[Muskardinet al., 2022 ] Edi Muskardin, Bernhard K. Aich- ernig, Ingo Pill, Andrea Pferscher, and Martin Tappler. AALpy: An active automata learning library.Innov. Syst. Softw. Eng., 18(3):417–426,

work page 2022
[21]

The temporal logic of programs

[Pnueli, 1977] Amir Pnueli. The temporal logic of programs. In18th annual symposium on foundations of computer sci- ence (sfcs 1977), pages 46–57. ieee,

work page 1977
[22]

Why should I trust you?

[Ribeiroet al., 2016 ] Marco T ´ulio Ribeiro, Sameer Singh, and Carlos Guestrin. “Why should I trust you?”: Ex- plaining the predictions of any classifier. InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1135–1144. ACM,

work page 2016
[23]

Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra

[Selvarajuet al., 2017 ] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 618–626. IEEE Computer Society,

work page 2017
[24]

[Shapley, 1953] L.S. Shapley. A value for n-person games

work page 1953
[25]

Machine learning-driven credit risk: a systemic review.Neural Computing and Ap- plications, 34(17):14327–14339,

[Shiet al., 2022 ] Si Shi, Rita Tse, Wuman Luo, Stefano D’Addona, and Giovanni Pau. Machine learning-driven credit risk: a systemic review.Neural Computing and Ap- plications, 34(17):14327–14339,

work page 2022
[26]

The many Shapley values for model expla- nation

[Sundararajan and Najmi, 2020] Mukund Sundararajan and Amir Najmi. The many Shapley values for model expla- nation. InInternational conference on machine learning, pages 9269–9278. PMLR,

work page 2020
[27]

Outcome- oriented predictive process monitoring: Review and benchmark.ACM Transactions on Knowledge Discovery from Data (TKDD), 13(2):1–57,

[Teinemaaet al., 2019 ] Irene Teinemaa, Marlon Dumas, Marcello La Rosa, and Fabrizio Maria Maggi. Outcome- oriented predictive process monitoring: Review and benchmark.ACM Transactions on Knowledge Discovery from Data (TKDD), 13(2):1–57,

work page 2019
[28]

On blame attribution for accountable multi-agent sequential decision making

[Triantafyllouet al., 2021 ] Stelios Triantafyllou, Adish Singla, and Goran Radanovic. On blame attribution for accountable multi-agent sequential decision making. Advances in Neural Information Processing Systems, 34:15774–15786,

work page 2021
[29]

BPI Challenge,

[van Dongen, 2012] Boudewijn van Dongen. BPI Challenge,

work page 2012
[30]

BPI Challenge,

[van Dongen, 2017] Boudewijn van Dongen. BPI Challenge,

work page 2017
[31]

Min- imal critical subsystems for discrete-time Markov models

[Wimmeret al., 2012 ] Ralf Wimmer, Nils Jansen, Erika ´Abrah´am, Bernd Becker, and Joost-Pieter Katoen. Min- imal critical subsystems for discrete-time Markov models. InInternational Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 299–314. Springer,

work page 2012
[32]

Figure 5: Example for Non-monotone Sequence of Improvements. A Proofs for Theoretical Properties A.1 Monotonicity Lemma 4.Optimizing the importanceimp s0,t Mσ(s)is mono- tonic in the reachability probabilityPr Mσ(s), but is not monotonic inPr Mσ(s′)for alls ′ ∈S\ {s}. Proof.The monotonicity ofimp s0,t Mσ(s)inPr Mσ(s)fors∈ S\ {s}follows from the monotonici...

work page 2011
[33]

Lemma 6.The importance of stateˆsis well defined iff Σt M ̸=∅

The following lemma connects the feasibility of the encod- ing to the reachability of the target statet. Lemma 6.The importance of stateˆsis well defined iff Σt M ̸=∅. Proof.If there exists no strategy under whichtis reached, thusΣ t M =∅, then the importance ofˆs,imp s0,t Mσ(ˆs), is not well defined for anyσ∈Σ M; the denominator always de- faults to0. Ho...

work page 2008
[34]

Proof.Lemma 8 follows from unfoldingPr Mσ(s0, s, t)fol- lowing LTL definitions [Pnueli, 1977 ]:Pr Mσ(s0, s0, t) = PMσ(♢t∧(¬tUs 0)) =P Mσ(♢t), holds ass 0 is the initial state ofM, and consequently,imp s0,t Mσ(s0) =

work page 1977