Minimal Witness Reinforcement Learning
MWRL uses verifier feedback to recover families of minimal sufficient witnesses rather than a single redundant solution.
Minimal-Witness Reinforcement Learning treats explanation as finding multiple minimal sufficient conditions from a single black-box verifier bit. Credit for each successful proposal equals the coverage the group union would lose without it, combining minimality with recovery of alternatives. The authors derive a value-iteration planner that recovers the witness family and a policy-gradient method intended to scale to large language models. In experiments MWRL recovers most minimal witnesses while other methods return redundant supersets or a single witness.
- MWRL formalizes finding multiple minimal sufficient witnesses from verifier bits.
- Credit is assigned by coverage lost if a successful proposal is removed.
- A value-iteration planner recovers the full witness family.
- A policy-gradient variant is designed to scale to large language models.
- Baselines often return one witness or a redundant superset.
Full article198 words · extracted from huggingface.co · click to collapse
``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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://huggingface.co/papers/2610.07226