Attribution-based Explanations for Markov Decision Processes

1 Introduction

Let us consider a loan application process, in which clients applying for a loan interact with a bank to discuss their eligibility and receive quotes on possible loans. While established techniques from Process Mining and Machine Learning can be used to automate process monitoring and decisionmaking (see, e.g., [Teinemaa et al., 2019; Leo et al., 2019; Shi et al., 2022; Montevechi et al., 2024]), the overall procedure remains inherently semi-structured. A successful application involves a sequence of interdependent steps, e.g., consultations and document submissions. Each step influences the probability of a successful outcome. Because the impact of these steps is often uncertain and state-dependent, the process can be viewed as a series of state transitions guided by both agent decisions and external variables.

Such stochastic, sequential decision-making tasks can be formally represented using Markov Decision Processes (MDPs) (e.g., [Baier and Katoen, 2008]). The application is then modeled as a system where transitions between process steps depend on the current state and specific actions, capturing the probabilistic nature of the problem. While MDPs effectively capture possible decisions, they lack native explainability mechanisms to communicate the significance of specific states (or sequences thereof) to a human observer.

Attribution-based explanations offer a potential solution to this problem by assigning importance scores to process elements based on their contribution to the final outcome. For a bank consultant or an applicant, such methods could provide intuitive answers to questions such as: "Which specific steps in this application process were most critical in securing the loan approval?". Unfortunately, existing attribution techniques are primarily designed for static, one-step prediction tasks [Bodria et al., 2023; Molnar, 2020] and fail to transfer to complex sequential decision-making settings.

Contributions. To bridge this gap, we introduce a novel framework for attribution-based explanations specifically designed for decision-making in MDPs. Unlike existing methods, our approach accounts for the long-term impact of transitions by evaluating the importance of a state relative to a specific strategy (or the set of all possible strategies) for reaching a goal state. Specifically, we define an attribution measure that quantifies state importance based on the reachability probabilities of optimal strategies, ensuring that explanations reflect the most efficient paths to reach a goal. We further extend this notion from individual states to execution paths and propose two optimization approaches to efficiently compute importance scores. Finally, we evaluate our approach on five case studies, demonstrating its feasibility on complex sequential decision-making tasks modeled by MDPs, with thousands of states and tens of thousands of transitions.

Outline. Section 2 reviews related work on attributionbased explanations and Sect. 3 presents background on MDPs, optimization and attribution-based explanations in Explainable AI. Our attribution-based explanations for MDPs are formalized in Sect. 4, and our encoding for computing them is presented in Sect. 5. We evaluate the performance and stability of our encoding in Sect. 6 and conclude in Sect. 7.

2 RelatedWork

In the context of attribution-based explanations, Shapley values [Shapley, 1953] have emerged as a dominant theoretical framework. Originally developed to determine fair contributions in cooperative games, they have been widely adapted to machine learning to quantify the impact of input features on model outputs [Lundberg and Lee, 2017]. Closer to our work, [Baier et al., 2021] leveraged Shapley values to propose a notion of attribution that captures entire paths in parametric Markov Chains and, later, extended this notion to general transition systems by transforming them into "one-shot" cooperative games [Baier et al., 2025]. Finally, [Triantafyllou et al., 2021] proposed several attribution techniques, including the Shapley value and Banzhaf index [Banzhaf, 1965], to assign blame to actors in a sequential cooperative multi-agent setting. These works, however, either do not deal with MDPs, or abstract from the MDP structure and do not leverage reasoning about strategies to determine importance scores.

This paper approaches the problem from a different angle and exploits the structure of MDPs to provide explanations for sequential decision making in MDPs. To this aim, we devise novel methods to compute attribution scores based on strategy synthesis. While strategies have been used to provide explanations for MDPs [Kobialka et al., 2025], their work targeted counterfactual explanations - not attribution-based explanations - and is as such complementary to this work.

3 Preliminaries

For a finite set X, let Distr(X) be the set of all distributions over X, which are functions µ : X → [0, 1] with ∑x∈X µ(x)=1; we set supp(µ) = {x∈X | µ(x)>0}.

3.1 Markov Decision Processes

A Markov Decision Process (MDP) M is a tuple ⟨S, A, s0, δ⟩ with a finite non-empty set S of states, a finite set A of actions, an initial state s0 ∈ S, and a partial transition function δ : S × A ⇀ Distr(S). An action a ∈ A is enabled in state s ∈ S, if δ(s, a) is defined. Let A(s) be the set of enabled actions in state s; we require that A(s) ̸= ∅ for all s ∈ S. Transition probabilities δ(s, a)(s′ ) are abbreviated δ(s, a, s′ ).

Let M = ⟨S, A, s0, δ⟩ be an MDP. An infinite path is an infinite sequence τ = s0, a0, s1, . . . of alternating states si ∈ S and actions ai ∈ A(si) with δ(si, ai, si+1) > 0 for all i ≥ 0. A finite path is a non-empty finite prefix τ = s0, . . . , sn of an infinite path; τ is simple if si ̸= sj for all 0 ≤ i < j ≤ n, and its cylinder set Cyl(τ) consists of all infinite paths extending τ. Let PathsM(s) and Paths finM(s) be the sets of all infinite resp. finite paths of M starting in s ∈ S. A state t ∈ S is reachable from s ∈ S, if a finite path starts in s and ends in t; let ←- R(t) be the set of all states fromwhich t is reachable.

Strategies (or schedulers) resolve nondeterminism in MDPs by deciding which actions to take. We consider stochastic memoryless strategies σ : S → Distr(A) with supp(σ(s)) ⊆ A(s) for all s ∈ S, forming the set ΣM. We abbreviate strategy probabilities σ(s)(a) as σ(s, a), and call σ deterministic if |supp(σ(s))| = 1 for any s ∈ S. Finite memory strategies extend memoryless ones with a finite set M of memory modes, differentiating how the current state is reached. Finite memory strategies for an MDP with states S can be simulated by memoryless strategies on an MDP with state space S ×M. Therefore, we use the memoryless notation also for finite memory strategies.

1

For a strategy σ of M = ⟨S, A, s0, δ⟩, its induced Markov Chain is Mσ = ⟨S, s0, δσ ⟩, where δσ : S × S → [0, 1] with δσ (s, s′ ) = ∑a∈A σ(s)(a) · δ(s, a, s′ ) for all s, s′ ∈ S. With D = Mσ we associate the probability space (PathsD(s0), {⋃τ∈R Cyl(τ) | R ⊆ Paths fin D (s0)}, PrD(s0)), where the probability of the cylinder set of a finite path τ = s0 . . . sn is PrD(s0)(Cyl(τ )) = ∏n-1 i=0 δσ (si, si+1). For a state t, let ΣtM be the set of all strategies σ ∈ ΣM with a positive probability of reaching t inMσ .

Example 1. The MDP in Figure 1 models a loan application process. Starting in s0, the applicant decides between taking a consultation or directly submitting an application. If applying directly, the application is error-free with a chance of 95%, and the bank decides whether a consultation is needed or the application can be considered directly. If an error occurred when applying, the Error state is reached and a consultation is needed. In the consultation, the user either applies again, or they become angry and quit the application process. In the former case, the submitted application is evaluated by the bank, and may be reworked one more time before a final decision is made.

3.2 Non-linear Optimization

Mixed Integer Quadratically Constrained Quadratic Problems (MIQCQPs) [Billionnet et al., 2016] are non-linear optimization problems, where both objective function and constraints are quadratic functions over real and integer variables. Formally, MIQCQPs are defined as:

using integer-valued (VZ) and real-valued (VR) variables x = (x1, . . . , xn) (n ∈ N) in the functions fi(x) = xT Qix + cTi x with symmetric matrices Qi ∈ Rn×n and constants ci ∈ Rn for all i ∈ {0, . . . ,m} (m ∈ N). Upper bounds align with the domain of the constrained variable, i.e., uj ∈ Z for xj ∈ VZ, and uj ∈ R for xj ∈ VR. MIQCQP are generally non-convex and thus hard to solve [Billionnet et al., 2016; Garey and Johnson, 1979].

We consider hierarchical objectives [Anandalingam and Friesz, 1992], such that the objective function f0(x) maps to a tuple and higher-indexed objectives are optimized under optimally-solved lower-indexed objectives, i.e., f0(x)1 is optimized with the additional constraint that f0(x)0 is optimal.

3.3 Attribution-based Explanations

An attribution-based explanation explains the outcome of an AI model by assigning a numerical score to its inputs. Intuitively, these attribution scores represent the degree to which each input influences the observed result. In Machine Learning, attribution methods such as LIME, SHAP and gradientscoring [Ribeiro et al., 2016; Lundberg and Lee, 2017; Selvaraju et al., 2017; Sundararajan and Najmi, 2020] assign a score to each input feature (e.g., pixels, words) to reflect their contribution towards an output (e.g., a classification); see also the survey [Molnar, 2020]. Although well-suited for ML, these methods are generally not applicable for MDPs because they attribute importance to static input features at a single point in time, failing to account for crucial factors in sequential decision-making, such as sequential dependencies, long-term rewards, and stochastic state transitions.

4 Attribution-based Explanations for MDPs

As a first contribution, we give a formal characterization of attributions for MDPs, establishing a quantitative basis for measuring the importance of states and paths, such that questions about their influence in reaching a target can be answered.

LTL notation. In the sequel, we will use notation from Linear Temporal Logic (LTL) [Pnueli, 1977], which we briefly recall. Based on a set of atomic propositions, e.g., a set S of state names, LTL formulae φ are inductively defined by the abstract grammar φ ::= ⊤ | s | φ ∧ φ | ¬φ | ⃝φ | φUφ with s ∈ S. The formula ⃝φ expresses that φ holds in the next state, φ1 Uφ2 that φ1 holds until φ2 gets true, and ♢φ that φ will eventually hold (i.e., ⊤Uφ). For an MDP M, a strategy σ ∈ ΣM, and an LTL formula φ, PrMσ(φ) = PrMσ{τ ∈ PathsM(s0) | τ |= φ} [Baier and Katoen, 2008].

4.1 Our formal attribution framework

As our first contribution, in order to provide a comprehensive view of importance, we formalize four attribution problems. We first address the importance of individual states (P1) and paths (P3) under a fixed strategy, capturing the realization of a specific behavior. We then generalize these notions to quantify the importance of states (P2) and paths (P4) across all strategies, revealing the global importance of these elements within the MDP. We begin with quantifying the importance of an individual state within the context of a fixed strategy.

P1 Consider an MDPM= ⟨S,A, s0, δ⟩, a target state t ∈ S, and a strategy σ ∈ ΣtM. How important is a given state s ∈ S for reaching t inMσ ?

Intuitively, a state s ∈ S is important under strategy σ for reaching state t ∈ S, if the induced Markov Chain Mσ has a high probability of visiting s before reaching t. We denote this probability by PrMσ (s0, s, t) := PrMσ (♢t ∧ (¬t U s)), to capture the probability of eventually reaching t and visiting s before reaching t. If M is loop-free and s is never reached after t on any simple path, then PMσ (s0, s, t) reduces to PMσ (♢t ∧ ♢s).

Given the above, we define the importance of a state s for reaching t in MDPMunder strategy σ as:

To ensure that our importance measure is well-defined, we require that σ ∈ ΣtM (i.e., the probability of reaching t under σ is positive). Note that imps0,t Mσ(s) ∈ [0, 1] for any s ∈ S and σ ∈ ΣtM; imps0,t Mσ(s) = 0 indicates that s is never visited before reaching t, and imps0,t Mσ(s) = 1 indicates that s is always visited before reaching t. Thus the initial state s0 and the target state t receive an importance of 1 under all strategies, as they are guaranteed to be visited. However, the importance of the other states depends on the strategy at hand.

In contrast to P1, no strategy is assumed in P2. Here, the importance of a state s ∈ S depends on whether s is important for reaching t globally. Intuitively, if s is never visited before reaching t under any strategy, then s is not important. In fact, visiting s might even be detrimental for reaching t, and thus receive an importance score of 0. As strategies can maximize and minimize the probability of visiting s before reaching t, we express importance for P2 as a tuple:

Obviously, importance scores between the lower and upper bound can be realized by mixing the minimizing and maximizing strategies. However, strategies optimizing imps0,t Mσ (s) might require up to one bit of memory to determine whether s was visited before reaching t. If lower and upper bounds align, the probability to visit s before t equals for all σ ∈ ΣtM.

In P1, the notion of importance normalizes the probability of visiting s before t by dividing by the total probability of reaching t. In addition, we also define absolute importance without normalization as the tuple ( minσ∈ΣtM PrMσ(s0, s, t),maxσ∈ΣtM PrMσ(s0, s, t)) of minimal and maximal probabilities of reaching t via s.

Available model checking tools apply value iteration to monotonically decrease resp. increase the probability of reaching t by local strategy modifications, adapting decisions at individual states. However, the importance of a state is defined as a fraction of two probabilities defined by the same strategy, and as such it cannot be directly computed by available tools. Intuitively, value iteration can be applied to both the nominator and the denominator in isolation, but monotonicity cannot be assured for their fraction. See the extended version [Kobialka et al., 2026] for an illustrating example.

We now extend the importance of states for reaching a state t, to the importance of paths, where several states need to be visited before reaching t.

P3 Consider an MDPM= ⟨S,A, s0, δ⟩, a target state t, a simple path τ = ⟨s0, a0, . . . , sn⟩ with si ̸= t for 0 ≤ i ≤ n and sn ∈ ←- R(t), and a strategy σ. How important is τ for reaching t under σ?

Intuitively, a path τ is important for reaching t under strategy σ, if the induced Markov Chain Mσ is likely to follow τ before reaching t.

For a path τ of the above form, we express the probability of reaching t after following τ as PrMσ(τ, t) := PrMσ (♢t ∧ (¬t U⃝(s1 ∧ (· · · ∧ (⃝sn) . . . )))), which simplifies to PrMσ (♢t ∧ ⃝(s1 ∧ (· · · ∧ (⃝sn) . . . ))).

The definition of the importance of a state in Equation (1) is extended to paths as follows. For a strategy σ of the MDP M, the importance of τ for reaching t is defined as:

Though we could allow paths visiting t or with sn ̸∈ ←- R (t), the importance score would then default to 0. Therefore, we constrain τ not to visit t and end in some sn ∈ ←- R (t).

In the absence of a fixed strategy, the importance of path τ is lower and upper bounded, expressing the global importance of τ for reaching t.

P4 Consider an MDP M = ⟨S,A, s0, δ⟩, a target state t, and a simple path τ = ⟨s0, a0, . . . , sn⟩, with si ̸= t for 0 ≤ i ≤ n and sn ∈ ←- R(t). How important is τ for reaching t?

As P4 abstracts from the given strategy in P3, we define the importance of a path as a tuple of lower and upper bounds on the importance of τ for reaching t under any strategy:

where the set ΣτM of strategies from ΣtM follows the action choices in τ, i.e., ΣτM = {σ ∈ ΣtM | σ(si) = ai for 0 ≤ i < n}. We restrict the strategies over which the importance of a path is optimized to ΣτM, as the lower bound is trivially realizable by not following τ .

We conclude this section with Example 2 to illustrate our definitions on the loan application from Example 1.

Example 2. A bank employee restructuring the loan application process from Example 1 wants to determine the importance of the consultation state for a successful application. Our attribution framework would show that the importance of Application+ is lower and upper bounded by one, as every successful application must visit that state, imps0,Granted M (Application+) = (1, 1). The importance of Angry, which is detrimental for a successful application, is lower and upper bounded by 0, imps0,Granted M (Angry) = (0, 0). The importance of the path τ = ⟨s0, Apply, Application⟩ is lower bounded by 0.9, and upper bounded by 1: imps0,Granted M (τ) = (0.9, 1).

Such importance bounds provide a formal yet interpretable measure of how specific states and paths contribute to - or hinder - the reachability of a target. In the following section, we detail our novel approach used to compute these intervals.

5 Computing Importance

After defining importance, in this section we propose a framework to compute its value. While our method is applicable to both states and paths, the following derivations focus on states, and we discuss the generalization to paths at the end of this section. We introduce three encodings: (i) QP, a nonlinear encoding optimizing importance over all strategies, (ii) QP∗ , a non-linear encoding optimizing over reachabilityoptimal strategies, and (iii) LP∗ , a linear encoding optimizing importance over reachability-optimal strategies. Theoretical results connect the encodings: Lemma 1 establishes that QP is computationally difficult and Theorem 1 proves its correctness; Lemma 3 enables the cheaper linear encoding LP∗ .

Assume an MDP M∗ = ⟨S∗ ,A, s0, δ∗ ⟩ and let ˆ s ∈ S∗ \ {s0} be the state of interest for reaching state t ∈ S∗ . Strategies optimizing imps0,t M∗ (ˆ s) require 1 bit of memory to remember whether ˆ s was visited. An initial preprocessing step introduces this memory, analogously to the memory construction in LTL model checking [Baier and Katoen, 2008].

Preprocessing. We construct the MDP M = ⟨S,A,s⊥0 ,δ⟩ with two copies s⊤ and s⊥ for each state s ∈ S∗ : S = {s⊤, s⊥ | s ∈ S∗ }. Index ⊤ indicates that ˆ s was visited and ⊥ that ˆ s was not visited. Accordingly, δ(s▷◁1 1 , a, s▷◁2 2 ) is δ∗ (s1, a, s2) if s▷◁2 2 = ˆ s⊤ or (▷◁1=▷◁2 and s2 ̸= ˆ s), and 0 otherwise, for all s1, s2 ∈ S∗ , a ∈ A, and ▷◁1, ▷◁2∈ {⊤, ⊥}.

Encoding as Quadratic Program (QP). Based on the preprocessed MDP M = ⟨S, A, s0, δ⟩, Fig. 2 shows the encoding of the lower boundminσ∈ΣtM∗ imps0,t M∗σ (ˆ s) on the importance of ˆ s as the solution to a nonlinear optimization problem. QP uses three types of variables: (1) psa ∈ [0, 1] stores the probability of choosing action a ∈ A in state s ∈ S by the computed strategy, (2) ps,t▷◁ ∈ [0, 1] stores the probability of reaching state t⊤ resp. t⊥ under the computed strategy, and (3) τs ∈ R allows to encode weight-decreasing paths to terminal states to enforce smallest fixedpoints. Note that ps⊥0 ,t⊥ +ps⊥0 ,t⊤ is the probability of reaching t from s0 in the non-preprocessed MDP, as all paths either visit or bypass ˆ s.

Eq. (2) minimizes an objective function that encodes the importance of ˆ s; maximizing corresponds to minimizing the objective multiplied by -1. Constraint 3 ensures that the computed strategy is well-defined (i.e., the probabilities sum up to 1). Constraints 4-5 encode default values for reaching state t, and Constraint 6 ensures a positive probability of reaching t for an arbitrarily small ϵ. Constraint 7 encodes the

Figure 2: Encoding QP for optimizing the importance of ˆ s ∈ S in the preprocessed MDP M as a nonlinear optimization problem.

Bellman optimality condition. Constraint 8 encodes a state ordering [Wimmer et al., 2012] to ensure that bottom strongly connected components not containing t reach t with probability 0, where the set of terminal states T ⊂ S contains all absorbing states where the only available action is a self-loop. Constraint 5 is not required for correctness but can reduce the solving time. Constraint 7 can be restricted to states reaching t⊤ or t⊥, setting ps,t▷◁ to 0 for states not reaching t▷◁ . All values in psa can be transformed into a strategy with memory on the non-preprocessed MDP, introducing ▷◁ ∈ {⊤, ⊥} as a memory mode to remember whether ˆ s was visited.

Let P denote the optimization problem defined in Fig. 2. The Bellman-optimality encoding in Constraint 7 is nonconvex, preventing polynomial-time solutions:

Lemma 1. P is in general non-convex.

Proof sketch. An optimization problem is convex, if its objective and all constraints are convex [Boyd and Vandenberghe, 2004]. As Constraint 7 is in general non-convex, see e.g. [Kobialka et al., 2025], the theorem follows.

Lemma 2. Assume a solution ν to P , which maps each variable v to value ν(v). Further, let σ be the strategy defined by σ(s, a) = ν(psa), for all s ∈ S and a ∈ A. Then, the value of the objective function equals minσ∈ΣtM∗ imps0,t M∗σ (ˆ s).

The following theorem states that the encoding facefully captures the importance of ˆ s.

Theorem 1 (Soundness and Completeness). P is feasible iff the importance of state ˆ s is well defined.

The proofs for Lemma 2 and Theorem 1 are contained in the extended version [Kobialka et al., 2026].

Importance for optimal reachability. In practice, we are typically interested in the importance of ˆ s under strategies that maximize the probability of reaching t. Then we can restrict the importance computation to strategies from Σ∗ = {σ ∈ ΣM∗ | PM∗σ(♢t) ≥ PM∗σ′ (♢t) for all σ′ ∈ ΣM∗}. This yields a constant value for the denominator in Eq. (2), and the problem reduces to minimizing ps⊥0 ,t⊤.

When only considering optimal reachability, QP can be further simplified as reachability probabilities from strongly connected components can be lower-bounded directly. We extend the problem to multi-objective optimization, minimizing the sum of reachability probabilities (under the maximizing schedulers from Σ∗ ) before optimizing for importance:

We further simplify computations by fixing the optimal reachability probability p∗ and lower-bounding the reachability of t⊤ and t⊥ over all possible actions to replace Constraint 8:

This encoding, denoted QP∗ , does not guarantee that the computed strategy is loop-free, but ensures that the assigned probability corresponds to actually realizable probabilities. The strategy can always be repaired to satisfy a state ordering.

We show that restricting strategies to reachability-optimal strategies simplifies the problem of computing importance: Lemma 3. For an MDPM, target state t, state ˆ s ∈ S and simple path τ , there exists a deterministic strategy optimizing imps0,t Mσ (ˆ s) and imps0,t Mσ(τ) over all strategies in Σ∗ .

Lemma 3 is proven in [Kobialka et al., 2026]. It follows that QP∗ can be adapted to a mixed-integer linear program, denoted as LP∗ , without quadratic components, in which the variables psa are turned into binary variables (i.e., from {0, 1}). The optimization objective only optimizes for the importance: min ps⊥0 ,t⊤. Constraints 7 and 8 are replaced by:

Constraint 9 ensures that optimal reachability is realized. Constraint 10 adapts the Bellman optimality equations to discrete actions; only for the chosen action in each state is the constraint not trivially satisfied. To realize the optimal reachability, those constraints must be satisfied with equation. Constraint 11 ensures that a weight-decreasing path exists under the computed strategy, where M is a large constant.

Remark. All the presented encodings can be extended to compute the importance of a simple path τ = ⟨s0, a0, . . . , sn⟩, with si ̸= t. The importance of τ can be expressed as the importance of sn weighted with the probability of observing τ. By partially assigning psiai = 1 to maximize the probability of following τ and then solving for the importance of sn, the importance of τ is the result multiplied with ∏ δ∗ (si, ai, si+1). The optimization problem is only well defined, and thus feasbile, for strategies reaching t with positive probability, i.e., it is ill defined if sn ̸∈ ←- R (t).

6 Experimental Evaluation

We now show that our approach is able to compute importance scores efficiently across five case-studies. GrepS records a programming skill evaluation service where customers (1) sign-up, (2) solve programming tasks, and (3) release their test results [Kobialka et al., 2024]. BPIC12 [van Dongen, 2012] and BPIC17 [van Dongen, 2017] are datasets for loan applications released by the IEEE Task Force on Process Mining. 1 MSSD is the Music Streaming Sessions Dataset [Brost et al., 2019] released by Spotify (Mini version with 10000 listening sessions). Epidemic [Kazemi et al., 2025] is a synthetic benchmark on vaccination strategies.

We used passive automata learning [Mao et al., 2016; Muskardin et al., 2022] to learn MDPs from the traces, after applying standard preprocessing techniques. For MSSD, we construct models that vary in the number of traces; e.g., MSSD10 includes 10% of the traces. For Epidemic, we vary the maximal population size; e.g., E6 considers a maximum population size of 6. The number of states is significantly larger in the MSSD models than in the other models: MSSD10 contains on average 36 times more states than BPIC12 or BPIC17, and has a 70 times higher maximum of outgoing transitions. Epidemic has a similar number of states as MSSD, but the number of transitions is 6 times greater than that of MSSD. However, the models are less connected, the largest Epidemic model has a maximum of 48 outgoing transitions, and MSSD100 of over 5 600. Each model contains a unique target state t that represents success. For example, in BPIC12 and BPIC17, the loan is granted to the user in t.

For Greps, BPIC12, and BPIC17, we compute the importance of every state in the model. For the MSSD models, we sample 10 states per model. For the Epidemic models, we use the initial state proposed by [Kazemi et al., 2025] to compute the importance of the number of available vaccinations for reaching a state without unvaccinated individuals.

All experiments were performed on a workstation with 128GB memory and a 64-core AMD EPYC processor. Our implementation and results are online. 2 Python 3.10.12 is used to interface with the Gurobi 3 (v. 11.0.3) solver. Each run of the solver is restricted to 4GB of memory and 1 hour, in all experiments we set M = 1016 and ϵ = 10-4 .

Numerical results. We compute strategies optimizing the importance of states from all models, demonstrating that attribution-based explanations can be computed for models with up to 10000 of states and transitions. Additionally, we highlight differences between the three presented encodings.

Table 1 compares the averaged computation times and results for Greps, BPIC12, and BPIC17. For each model, we compute the lower and upper bounded importance for every state using all three encodings. Encoding (Enc.) denotes the used encoding: QP denotes the quadratic program optimizing over ΣM, QP∗ the quadratic encoding optimizing over reachability optimal strategies Σ∗M, and LP∗ the linear program. Opt. denotes the number of problems solved optimally, T.O.

1 https://www.tf-pm.org/competitions-awards/bpi-challenge

2 https://github.com/explainableMDPs/mdp attributive

3 https://www.gurobi.com/

denotes the timeouts, and Σ the absolute number of problems. The remaining columns describe the mean, standard deviation, minimum, and maximum over all solution times in seconds. While QP∗ and LP∗ can solve all inputs without timeout, LP∗ solves all instances within one second.

Table 2 shows runtimes for Epidemic with population sizes up to 19. For population sizes larger than 19, the transition probabilities can become very small, i.e., they require more than 10 digits of precision to avoid rounding to 0. Based on the results from BPIC12 and BPIC17, we omitted encoding QP as the Epidemic models are significantly larger. Until E8, encoding QP∗ can be solved within the one-hour timeout, encoding LP∗ can be solved within fractions of a second for all models. Comparing E7 with E8 reveals the growing complexity induced by the population size, the number of states increase from 962 to 1379, and transitions from 5644 to 9029. All timed-out instances involved states with sufficient vaccinations for reaching t, and were well connected in the MDP.

After confirming that computing strategies to minimize, respectively maximize, importance takes comparably long, we restricted the MSSD experiments to minimization. Figure 3 presents the averaged runtime results for the MSSD models on the left-hand y-axis and the number of time-outs on the right-hand y-axis. Most strategies were computed within a one-hour time constraint; the 4GB memory constraint was reached in three MSSD10 problems. While MSSD10-40 reported few timeouts, fromMSSD50, up to 23 runs timed out. Interpretability of our scores. Attribution-based explanations can support end-users in gaining insights into the decision process by highlighting the most crucial steps. However, to be useful, attribution scores need to be understandable. Indeed, we observe that our technique is most informative when bounds on attribution scores are tight. In such cases, our attribution-based explanations lend themselves to a textual representation that summarizes the most important states, respectively paths, with high lower bounds, and most detrimental states, respectively paths, with low upper bounds. An excerpt of a textual representation of the most influential and detrimental states for receiving a loan in BPIC12 is:

States indispensable for a loan application include: A_CreateApplication, O_Accepted, and A_Pending. States detrimental for a loan application include: SUPER LONG calls regarding incomplete information.

Additionally, process representations where states and paths are colored with heat maps according to their importance can communicate attribution-based explanations well, as demonstrated in Example 3 on a gridworld example.

Example 3. Figure 4a shows a deterministic gridworld where the agent (red triangle) has to pick up a key, required to cross a river of deadly lava to reach the green target state. This gridworld can be modeled as an MDP where each state corresponds to an agent position, the target state is the state encoding the agent at the green tile position, and touching the lava leads to unsuccessful end states. The actions correspond to moving the agent in the 4-neighborhood, and picking up the key. The key is required to pass through the door, but no "open" action is needed. Without having the key, it is not possible to move on the door-field.

Our importance scores enable answering questions such as: how important is visiting state s for reaching the target? (P2), or, how important is following path τ for reaching the target? (P4). The importance of any state is depicted in Fig. 4b via a heat map overlay. There exists a strategy that leads the agent via any non-lava state to the target state, and there exists no strategy that leads the agent via any lava state to the green state. However, there exists no successful strategy where the state across the lava receives an importance with a lower bound of less than 1.

• (a) Gridworld Example.

(b) Gridworld Heat Map Overlay.

Figure 4: Gridworld example, where the agent has to reach the green tile, while avoiding the lava tiles. The heat map on the right visualizes the importance from the corresponding MDP and highlights that most states are optional. The three white colored transfer-states are indispensable, and the six red states should be avoided.

Threats to validity. The main threat to validity in our experiments is numerical instability, related to the chosen constants for M and ϵ. Due to its size, M can introduce numerical inaccuracies as MDPs' transition probabilities might become very small, spanning a large range of values in the model. However, the differences between the LP∗ and QP∗ encodings are small: on average, results differ by less than 4 · 10-4 . A table showing the differences is included in [Kobialka et al., 2026]. In summary, attributive explanations can be computed efficiently for complex MDPs. Notably, attributions are possible for strategies with optimal reachability in MDPs with up to 10 000 states and transitions.

7 Conclusion

This paper introduces attribution-based explanations for Markov Decision Processes to address the limitations of static feature importance in sequential decision-making. We provide a formal characterization for attribution-based explanations in this context, including the assignment of importance scores to individual states as well as execution paths in the model. We also propose an optimization approach for computing these scores and demonstrate its scalability across a wide range of sequential decision-making problems.

Our work opens several interesting directions for future work. First, we plan to investigate extensions of our framework towards computing importance of subpaths as opposed to full paths (from initial to goal states) considered here. To this aim, we will investigate a formal grammar capable of identifying semantically interesting segments within an execution. Second, we intend to explore the application of our techniques to Deep Reinforcement Learning. This will require novel abstraction methods to map latent representations learned by neural networks onto our formal attribution framework, bridging the gap between symbolic reasoning and neural decision-making. Finally, we believe it would be important to conduct user studies to evaluate the interpretability of our attribution scheme and assess how effectively these explanations help end users understand system behavior.