Minimal Witness Reinforcement Learning

Abstract

“Which irreducible sets of factors are sufficient to produce an outcome?” is a question that recurs across computation and science. These irreducible sets, formally defined as minimal sufficient witnesses, are what we mean by explanations, mechanisms, and reasons. A task may have several such witnesses, none containing another. When we can only ask a black-box verifier whether a proposed set is sufficient, we have to recover the entire irreducible sets from its binary reward. We formalize this question as minimal-witness identification and introduce Minimal-Witness Reinforcement Learning (MWRL). A reward that scores each proposal alone cannot tell a new witness from a success already covered by another. MWRL treats each success as certifying its supersets and rewards a proposal for the part of that certified region which the other proposals do not cover. The same relational value rewards both refinement and family recovery. It yields an exact planner on enumerable instances and a group policy gradient that scales to language models. MWRL recovers most of the minimal-witness antichain where correctness-based methods return redundant supersets or a single witness, with the largest gains when many witnesses have comparable reachability. By making witness families learnable from verifier feedback, MWRL expands the scope of reinforcement learning beyond single-solution optimization. Our code is available at github.com/TSUITUENYUE/MWRL.

CitationT.-Y. Tsui, Z. Ye, P. Cai, Y. Li, Y. Li, Z. Ai. (2026). "Minimal Witness Reinforcement Learning."