Minimal Witness Reinforcement Learning

Minimal Witness Reinforcement Learning. By T. Y. Tsui and five others, from the University of Pennsylvania and the Shanghai AI Laboratory. Published on the fifth of October. Its code repository is worked out: about sixty-five source files, with a readme and a licence.

A question recurs across computation and science: what are the irreducible conditions that are sufficient to produce an outcome? Its answers are minimal sufficient witnesses, and the authors point out that these are what we mean by explanations, mechanisms, and reasons. Such problems usually have more than one minimal witness, and usually the question wants all of them. Standard reinforcement learning methods fall short here. They may reveal only one solution, or return redundant ones that contain more than they need.

The authors formalize the task as minimal-witness identification and introduce Minimal-Witness Reinforcement Learning, or MWRL. The policy samples a group of proposals. Each successful proposal certifies a set, and MWRL takes the union of those sets. A proposal is then credited for the coverage that group union would lose if that proposal were taken away.

That credit rule is derived directly from the problem definition, and it does two jobs with one signal. A redundant proposal adds nothing the others do not already cover, so it earns nothing, which pushes toward minimality. A proposal that finds a witness no one else found earns the most, which pushes toward recovering alternatives. Both demands are met from a single black-box verifier bit. Under this principle the authors derive two algorithms: 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. Other methods, by contrast, return redundant supersets or a single witness. Those two failure modes are exactly the ones the problem statement set out: an answer that contains more than it needs, or an answer that stops at the first explanation it finds. The abstract reports the comparison in those qualitative terms rather than with figures. The code is available on GitHub.

What changes is the target of learning. Ordinary reinforcement learning optimizes toward one good answer. By making whole families of witnesses learnable from verifier feedback, MWRL extends reinforcement learning to problems where the answer is a set of distinct, irreducible explanations, and where finding the same one twice adds nothing. The appeal of the construction is its economy. One bit from a verifier says only whether a proposal succeeded, yet scoring each proposal by what the group would lose without it is enough to ask for answers that are both minimal and different from one another.