Reinforcement learning uncovers all minimal explanations for outcomes
Minimal Witness Reinforcement Learning
Machine LearningArtificial IntelligenceComputation and LanguageLogic in Computer Science
Summary
Sometimes we want to know the smallest set of conditions that caused something to happen. The paper introduces a way for AI systems to find all these minimal reasons, not just one. The authors create a new reinforcement learning method that learns from a simple yes-or-no checker to find all unique minimal sets. Their approach works better than previous ones which often find only one answer or many redundant ones. This helps AI better explain its decisions by showing all the minimal causes.
What this means in practice
- •For automated debugging teams: Identify all minimal root cause sets for software faults using minimal-witness reinforcement learning.
- •For security analysts: Discover all minimal sets of conditions triggering security alerts to improve incident explanations.
Authors
T. Y. Tsui, Zihao Ye, Pengxiang Cai, Yanchao Li, Yuqiang Li, Zhehong Ai
Abstract
``What are the irreducible conditions that are sufficient to produce an outcome?'' is one of the most common questions that recur across computation and science. Its answers, the minimal sufficient witnesses, are what we mean by explanations, mechanisms and reasons. These problems usually ask for multiple minimal witnesses, yet standard RL methods may reveal only one solution or redundant ones. We formalize this problem as minimal-witness identification and introduce Minimal-Witness Reinforcement Learning (MWRL). MWRL takes the union of the sets certified by successful proposals sampled from the policy and credits each proposal for the coverage the group union would lose without that proposal. This credit assignment, derived directly from the problem definition, unifies the demands for minimality and recovery of alternatives from a single black-box verifier bit. Under this principle, we derive a value iteration planner that recovers the entire family of witnesses and a policy gradient method that can scale to large language models. Across different experimental settings, MWRL recovers most minimal witnesses, while other methods return redundant supersets or a single witness. By making witness families learnable from verifier feedback, MWRL expands the scope of reinforcement learning beyond single-solution optimization. Our code is available at https://github.com/TSUITUENYUE/MWRL.