Approximating Shapley Explanations in Reinforcement Learning

AI summary

Overview

Research area: Interpretability and explainability for reinforcement learning (RL), specifically the use of Shapley values from cooperative game theory to attribute agent behaviour, outcomes, and predictions to input state features.

Technical level: Advanced. The paper builds on the SVERL framework, the FastSHAP approximation technique, Markov Decision Processes, and off-policy/on-policy value learning, and includes formal proofs in appendices and complexity arguments.

Scope: The paper introduces FastSVERL, a parametric framework for approximating Shapley-based explanations of RL agents in a way that scales with states rather than exploding exponentially with features.

Note: the paper content available for this summary is truncated partway through Section 4. Details of Section 5 and the appendices are referenced but not fully reported here.

What This Paper Is About

Shapley values provide theoretically grounded explanations of a model's decisions, but computing them exactly is exponentially expensive and therefore impractical for most real problems. In reinforcement learning the problem is worse than in supervised learning because explanations must account for temporally extended trajectories, may need to be derived from data collected by a different policy, and must track a policy that is still changing. The paper's goal is to build a computationally feasible way to approximate Shapley explanations for RL agents across all three explanatory targets defined by the SVERL framework: behaviour, outcome, and prediction.

Key Contributions

1. FastSVERL, a scalable parametric approximation framework for Shapley explanations in RL. It replaces exponential computation with learned parametric models that amortise the approximation cost across states and feature subsets, and that can be continually refined as an agent's policy changes. The method applies the same architecture and training procedure across behaviour, outcome, and prediction explanations by substituting the relevant characteristic function into the loss.

2. Parametric approximations of the characteristic functions that underpin each explanation type. Behaviour and prediction characteristics share a conditional-expectation structure and are learned by minimising an expected squared error over states, actions, and feature subsets. The outcome characteristic, which requires expected returns under a modified policy, is handled by defining a single conditioned policy and a conditioned value function, with both an on-policy DQN-style loss and an off-policy Q-learning-style loss presented.

3. Theoretical guarantees for the learned approximations. The paper proves (in Appendix A) that the efficiency-corrected output of a global optimum recovers exact and unbiased Shapley values for state-action pairs with positive steady-state probability, and (in Appendix B) that the characteristic model's global optimum recovers exact and unbiased characteristic values for all relevant state-action-subset triples, given a sufficiently expressive model class.

4. Techniques for practical RL constraints. These include an importance sampling estimator for learning explanations passively from an agent's existing interaction buffer, and a training regime that jointly updates explanation models alongside a changing policy. An additional extension in Section 5 is reported to halve computational costs, improve estimation accuracy, and extend naturally to supervised learning.

Main Findings

• All three outcome components converge to low error. In Mastermind-222 (eight features, 53 states), the behaviour characteristic, outcome characteristic, and outcome Shapley models all converge to mean squared error below 0.01.

• Upstream approximation errors degrade downstream models. Shapley models trained on approximated characteristic values converge to less accurate solutions than those trained on exact characteristic values.

• Off-policy training is faster for the outcome characteristic. Off-policy training converges faster than on-policy training, attributed to reuse of the original agent's training experience rather than collecting new transitions from the conditioned policy. The paper notes off-policy learning is effective only when stored experience sufficiently covers states relevant to the conditioned policy.

• Cost scales with states, not features. In the Hypercube domain, for a fixed number of features, training updates needed to reach a target loss of 0.01 grow roughly linearly on a log-log scale, indicating approximate polynomial growth as states increase. With a fixed number of states, increasing the number of features has little effect on training cost.

• The characteristic model needs more updates than the Shapley model. This is consistent with the characteristic model predicting values for all feature subsets at each state (|S| × 2^n), while the Shapley model predicts values per feature and state (|S| × n).

• Convergence remains stable in large domains. In Mastermind-443 (24 features, at least 4.3 × 10^7 states), Mastermind-453 (30 features, at least 3.5 × 10^9 states), and Mastermind-463 (36 features, at least 2.8 × 10^11 states), both models converge reliably over 10 runs, with training updates remaining roughly consistent as states and features grow.

• Reported convergence figures (Table 1, mean ± standard error over 10 runs). Mastermind-443: characteristic (1.10 ± 0.11) × 10^6 updates to a final loss of (3.83 ± 0.02) × 10^-3; Shapley (7.31 ± 0.68) × 10^5 updates to (1.30 ± 0.04) × 10^-3. Mastermind-453: characteristic (1.29 ± 0.11) × 10^6 updates to (3.60 ± 0.02) × 10^-3; Shapley (7.84 ± 0.49) × 10^5 updates to (0.96 ± 0.03) × 10^-3. Mastermind-463: characteristic (1.18 ± 0.12) × 10^6 updates to (3.70 ± 0.01) × 10^-3; Shapley (7.12 ± 0.51) × 10^5 updates to (1.88 ± 0.04) × 10^-3.

• Learning losses are not ground-truth accuracy. The characteristic loss is designed to converge to a non-zero value because the model learns an expectation over unknown features. For the Shapley model, convergence toward zero indicates it has learned to explain the characteristic model's approximations, not necessarily the true values.

• Importance sampling helps but does not fully close the gap. Training the behaviour characteristic in Mastermind-222 with importance sampling on the agent's training buffer lowers approximation error relative to no importance sampling, but does not match the on-policy baseline using data from the final policy.

• A sample explanation matched plausible game strategy. In a Mastermind-463 state (hidden 4-letter code drawn from a 3-letter alphabet), the highest-influence features were recent guesses, which are sufficient to deduce that the code is a permutation of (B, C, C, C), while the redundant first guess and unused guess slots received neutral influence. The paper reads this as suggesting the approximation satisfies the nullity axiom by assigning zero contribution to irrelevant features, while cautioning against over-interpretation.

Methodology in Plain English

The authors start from SVERL, which attributes what an agent does (behaviour), the return it achieves (outcome), and what it predicts that return will be (prediction) to individual features of the state. SVERL requires summing over every possible subset of features and computing an expectation over the state space at each subset, giving a cost of O(2^|F| · |S|) per explanation.

FastSVERL replaces both halves of that computation with learned neural models. One set of models learns the characteristic functions, which describe the agent's expected action probability, expected return, or predicted return when only some features are visible. Another model, the Shapley model, learns to output the Shapley attribution for every feature directly, trained against a weighted least-squares formulation borrowed from FastSHAP, with a post hoc correction that enforces the efficiency constraint (the attributions must sum to the total change from seeing all features versus none).

The hardest case is the outcome characteristic, because it depends on a modified policy that uses the behaviour characteristic only at the state being explained. Instead of solving a separate problem for every state and feature subset, the authors define one conditioned policy for the whole state space and learn a single conditioned value function for it. They offer two variants: an on-policy version that collects transitions from the conditioned policy, and an off-policy version that learns a conditioned state-action value function and reuses transitions from a buffer, with the outcome characteristic recovered by summing the conditioned Q-values weighted by the conditioned policy's action probabilities.

For settings where the agent cannot interact with the environment, the authors add an importance sampling correction that reweights samples in the buffer by the ratio between the policy being explained and the policy that generated each sample. For settings where the policy keeps changing, they propose updating the explanation models continuously from the same interaction data used to update the agent.

Experiments use a DQN agent in the Mastermind domain, chosen because its small variants are tractable for exact Shapley value computation, and in Hypercube, an n-dimensional gridworld where side length l and dimension n control the number of states (l^n) and features (n). Results are averaged over 20 runs in Figures 1–3 and over 10 runs in Table 1.

Why This Matters

The paper targets a practical bottleneck: Shapley explanations are attractive precisely because they are principled, but their cost has kept them out of reach for real RL problems. FastSVERL offers a route to keeping the theoretical guarantees while making the computation tractable, and it explicitly addresses conditions that arise in practice rather than only in simulation.

The paper's own stated motivation is deployment in safety-critical settings, where a lack of transparency limits real-world use. Domains the work plausibly applies to include:

• Safety-critical control systems, the setting the paper names explicitly, where operators need to know which observations drove a decision before trusting an agent.
• Situations with limited or costly environment interaction, where the importance sampling approach allows explanations to be learned passively from data an agent has already generated.
• Continual and online learning settings, where an agent's policy changes during training and explanations must be updated alongside it rather than recomputed from scratch.
• High-dimensional state spaces, where the number of features is large and the paper's finding that cost scales with states rather than features is most valuable.

Industry relevance: Because the method is amortised and model-based, and because the paper reports stable convergence in domains with tens of features and up to at least 2.8 × 10^11 states, it is positioned as a component that could be integrated into existing value-based RL pipelines. The authors released code at https://github.com/djeb20/fastsverl, which lowers the barrier to adoption.

Future Directions

• Characterising the Section 5 extension. The paper states that a promising extension halves computational costs, improves estimation accuracy, and extends naturally to supervised learning, but the truncated content does not report its details. Reproducing and formalising that extension is an open step.

• Closing the off-policy accuracy gap. Importance sampling reduces error relative to its absence but does not match the on-policy baseline. Whether better reweighting, coverage-aware sampling, or hybrid data collection can close that gap is unresolved.

• Validating ground-truth accuracy at scale. The paper explicitly notes that training loss is not a measure of ground-truth accuracy and that ground-truth accuracy cannot be validated in the large Mastermind domains, since exact computation is feasible only for behaviour and prediction explanations in larger domains. Methods for certification or partial verification at scale remain open.

• Broadening beyond the tested domains and agents. Experiments centre on a DQN agent in Mastermind and Hypercube, with results for all explanation types and additional domains deferred to the appendix. Whether the scaling behaviour holds for other RL algorithms, such as PPO, and for continuous or partially observable environments is not established in the available content.

Target Audience

This paper is best suited to RL researchers and interpretability researchers with prior familiarity with Shapley values, SVERL, and value-based RL methods, since it assumes working knowledge of characteristic functions, the efficiency axiom, and off-policy learning. It is also relevant to practitioners who need auditable explanations for deployed agents in safety-critical or interaction-limited environments, and to engineers looking for a concrete implementation, given the released code. Readers seeking an introductory treatment of explainable RL will find the paper's mathematical framing demanding; the empirical sections and the worked Mastermind-463 example are the most accessible entry points.

Authors’ abstract

Reinforcement learning has achieved remarkable success in complex decision-making environments, yet its lack of transparency limits its deployment in practice, especially in safety-critical settings. Shapley values from cooperative game theory provide a principled framework for explaining reinforcement learning; however, the computational cost of Shapley explanations is an obstacle to their use. We introduce FastSVERL, a scalable method for explaining reinforcement learning by approximating Shapley values. FastSVERL is designed to handle the unique challenges of reinforcement learning, including temporal dependencies across multi-step trajectories, learning from off-policy data, and adapting to evolving agent behaviours in real time. FastSVERL introduces a practical, scalable approach for principled and rigorous interpretability in reinforcement learning.