Training Characteristic Functions with Reinforcement Learning: XAI-methods play Connect Four

Stephan Wäldchen, Sebastian Pokutta, Felix Huber

Explainable AI (XAI) aims to make complex "black-box" models, like deep neural networks, transparent and interpretable. A popular approach to achieve this is saliency attribution, which highlights the specific input features (such as pixels in an image) that were most important for a model's decision. However, evaluating these methods objectively is notoriously difficult.

This paper introduces a novel framework for evaluating XAI methods by training Reinforcement Learning (RL) agents to play Connect Four with partial information. By directly learning "characteristic functions" on-manifold, the authors create a robust proxy task that avoids the common pitfalls of off-manifold counterfactuals, allowing for a fair, game-theoretic comparison of popular saliency attribution methods.

The Problem: Off-Manifold Counterfactuals

Many XAI methods rely on "off-manifold" counterfactuals to test feature importance. This involves evaluating the model on inputs it never saw during training—for example, an image with a black square artificially placed over the subject. Because the model is forced into "unseen" territory, it can produce unreliable explanations that are easily manipulated.

Saliency methods can sometimes create "super-stimulus" features off-manifold, as seen in this bird image mask.

The authors identify a core issue: most XAI methods try to turn a standard classifier into a "characteristic function" (a game-theoretic concept that evaluates subsets of features) post-hoc. This process is ambiguous. It often leads to "super-stimulus" effects where the explanation method creates features or artifacts that weren't present in the original data, simply to maintain a classification score.

The Solution: On-Manifold Training via Connect Four

To solve the off-manifold problem, the researchers propose a different path: directly training characteristic functions using Reinforcement Learning.

  1. Connect Four as a Proxy: The authors use the game Connect Four because it is strategically complex yet has a discrete, low-dimensional input space. This makes "hiding" information straightforward without the complex contextual dependencies found in natural images.
  2. Training with Partial Information: Agents are trained using Proximal Policy Optimization (PPO). Crucially, during self-play training, the environment randomly hides a percentage of the board's color information. This forces the agent to learn to make decisions based on partial inputs. Effectively, this trains the policy network as a characteristic function $\nu(S)$ that is valid "on-manifold." Because the model is trained on missing data, a missing feature is simply a zero in the input channel—exactly as the model expects.

Evaluation: The Masker-Player Tournament

To evaluate different XAI methods fairly, the authors set up a unique game between two teams. Each team consists of a "masker" (an XAI method) and a "player" (the trained RL agent).

The Connect Four setup with maskers and players.

The masker analyzes the board and identifies the most important pieces for a winning move. It then hides the rest of the board, showing only those "salient" pieces to the player. The quality of the XAI method is measured directly by how well the player performs with this limited information.

Key Findings and Insights

The study compared their agents against standard Monte-Carlo Tree Search (MCTS) benchmarks and perfect solvers, yielding several surprising insights:

  • Competitive Agents: Agents trained on up to 50% partial information (PI-50) remained highly capable. When given full information, they won over 90% of games against a standard MCTS-1000 benchmark.
  • Heuristics Outperform Theory: In the round-robin tournament, heuristic methods like DeepShap and GuidedBackprop (along with a Frank-Wolfe based method) were the top performers. They consistently outperformed theoretically grounded methods like sampled Shapley values in this specific game setting. They were highly effective at selecting the 50% of pieces that allowed the player to still win.
  • Ground Truth Recovery: When tested against "ground truth" (the specific pieces that actually completed a winning line), DeepShap and GuidedBackprop correctly identified at least two out of three critical pieces in over 75% of cases.
  • Shapley Value Instability: The authors found that Shapley values can become unreliable when too much information is hidden. If a board state is so obscured that any move is equally likely, the policy becomes random, and the "importance" of features becomes mathematically ill-defined.

Limitations and Future Directions

While this framework provides a rigorous sandbox for XAI evaluation, the authors note some limitations. Connect Four pieces have low correlation, whereas real-world data like images are highly redundant. Hiding a few pixels in an image is easily "undone" by a vision model's internal understanding of context (inpainting), making this exact approach harder to scale directly to complex computer vision tasks.

Additionally, at high levels of missing information, the policy network's output tends toward a uniform distribution, muddying the saliency signal. The authors suggest that using a value-based approach (like Q-learning) might provide more stable importance estimates in these low-information regimes.

Ultimately, this research provides a compelling new proxy task that could serve as a standard "sanity check" for new XAI techniques, encouraging further investigation into why certain heuristic methods perform so well in practice.

Summary updated

Abstract

Characteristic functions (from cooperative game theory) are able to evaluate partial inputs and form the basis for attribution methods like Shapley values. These attribution methods allow us to mea...
BibTeX
@inproceedings{waldchen2022training,
  author = {Stephan Wäldchen and Sebastian Pokutta and Felix Huber},
  title = {{Training Characteristic Functions with Reinforcement Learning: XAI-methods play Connect Four}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=sPKogzLjD2B},
}
Figure