Minimal Witness Reinforcement Learning

T. Y. Tsui; Zihao Ye; Pengxiang Cai; Yanchao Li; Yuqiang Li; Zhehong Ai

cs.LGOct 5, 2026

Minimal Witness Reinforcement Learning

Authors: T. Y. Tsui, Zihao Ye, Pengxiang Cai, Yanchao Li, Yuqiang Li, Zhehong Ai

Organizations: University of Pennsylvania · Shanghai AI Laboratory

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.

Figures & tables

Figure 1: From proposal-local reward to the group-certified region. (a) to (c) Terminal probability on

2^{\mathcal{E}}

for

\mathcal{E}=\{a,b,c,d\}

; the target antichain is ringed. A success-only reward spreads probability over all sufficient sets (a) and a size penalty collapses onto the smallest witness (b); MWRL credits each success for the part of the group’s certified region that only it certifies and puts its probability on the antichain (c). (d) Finite-budget recovery on enumerable MaxSAT instances: MWRL recovers most of each instance’s antichain, and methods that value each proposal in isolation recover at most a quarter of it. The size-penalized MaxEnt RL and GFlowNet bars use the best penalty of a sweep, and the dashed vertical line is the mean antichain size

|\mathcal{M}|

Symbol	Meaning	Symbol	Meaning
General notation		Problem formulation
$\mathcal{E},n$	Ground set and its size	$s_{c}(S)$	Sufficiency predicate for context $c$
$S,T,Q\subseteq\mathcal{E}$	Proposed or auxiliary subsets	$\mathcal{M}(c),L$	Minimal-witness antichain and its size
$2^{\mathcal{E}},\subseteq$	Subset lattice and inclusion order	$\minop_{\subseteq}$	Inclusion-minimal members of a family
$\|S\|$	Number of elements in $S$	$F(c)$	Set of all sufficient subsets
$\uparrow\!S,\downarrow S$	Supersets and subsets of $S$	$s_{\exists}$	Monotone closure of a raw predicate

Table 1: Notation grouped by its role in the paper. Symbols used only in derivations or diagnostics are included for reference. We omit

c

when it is fixed;

i,j

index proposals,

t

policy steps, and

k

planner steps.

Figure 2: Credit as a deletion marginal on the subset lattice (

\mathcal{E}=\{a,b,c,d\}

; height is subset size). A success certifies its up-set, the set of its supersets, and the up-set of

S_{2}=\{a,b,c\}

is smaller than that of

S_{1}=\{a,b\}

U_{K}

is the region the group certifies (

S_{1},S_{3}

minimal,

S_{2}

redundant,

S_{4}

rejected); in each

A_{i}

, grey denotes

U_{-i}

, the sets certified without

S_{i}

. The coloured region contains the sets whose certification is lost when

S_{i}

is removed; its measure gives the credit

A_{i}

with a size penalty
Method	born-min. rate $\uparrow$	antichain recall $\uparrow$	#found $\uparrow$	raw $\|S\|$
PPO / MaxRL	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.0{\scriptstyle\pm}0.0$	$12.0{\scriptstyle\pm}0.0$
GRPO / RLOO	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.0{\scriptstyle\pm}0.0$	$12.0{\scriptstyle\pm}0.0$
GFlowNet (success)	$0.01{\scriptstyle\pm}0.00$	$0.02{\scriptstyle\pm}0.02$	$0.4{\scriptstyle\pm}0.3$	$7.8{\scriptstyle\pm}0.1$
GFlowNet (up-set)	$0.01{\scriptstyle\pm}0.00$	$0.05{\scriptstyle\pm}0.02$	$0.9{\scriptstyle\pm}0.3$	$7.0{\scriptstyle\pm}0.4$
PPO	$1.00{\scriptstyle\pm}0.00$	$0.07{\scriptstyle\pm}0.01$	$1.3{\scriptstyle\pm}0.1$	$2.8{\scriptstyle\pm}0.0$

Table 2: Prime-implicant recovery with ground truth. Columns report born-minimal rate, antichain recall, the number of distinct witnesses found, and raw proposal size. Scalar VI is value iteration on a size-penalized scalar reward and returns one witness. Minimal-witness VI plans on

(F,b)

and recovers the full antichain at

b=|\mathcal{M}|

(Appendix E.4). Learned rows report mean

\pm

standard deviation over three policy seeds after averaging the eight instances (training configuration in Appendix E.3). The size-penalized MaxEnt RL and GFlowNet rows report the best setting of a sweep over the penalty strength, trained with

57{,}600

verifier calls per formula.

Figure 3: Amortized discovery of minimal reaction-condition sets on the Suzuki coupling. (a) Two held-out substrate pairs with their ground-truth antichains. Each row of chips names one minimal set of dimensions allowed to vary from the baseline (cat catalyst system, solv solvent, Pd loading, T temperature). (b) Recall on each held-out substrate within the window of 32 distinct condition sets, with the values of each policy sorted in decreasing order. The shaded gap between the conditioned and the substrate-blind policy is the recall that the substrate fingerprint adds.

Amortized MWRL
Method	born-min.	recall $\uparrow$		#found $\uparrow$
	rate $\uparrow$	seen	held-out
Per-substrate	$0.20$	$0.67$	—	$4.9$
Conditioned	$0.26{\scriptstyle\pm}0.02$	$0.50{\scriptstyle\pm}0.02$	$\mathbf{0.48{\scriptstyle\pm}0.03}$	$\mathbf{3.6{\scriptstyle\pm}0.2}$
Substrate-blind	$0.20{\scriptstyle\pm}0.01$	$0.37{\scriptstyle\pm}0.01$	$0.34{\scriptstyle\pm}0.02$	$2.6{\scriptstyle\pm}0.1$
Scalar RL	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.0{\scriptstyle\pm}0.0$

Table 3: Amortized recovery of minimal reaction-condition sets within a window of 32 distinct condition sets per substrate. We report antichain recall on substrates seen in training and on held-out substrates, and the held-out column measures amortization. The column #found counts distinct minimal witnesses per held-out context. The two amortized rows train the same MWRL objective and differ only in access to the substrate fingerprint. Amortized rows give the mean

\pm

standard deviation over three seeds that control both the substrate split and the policy. Per-substrate search retrains for each substrate to mark the ceiling, and nothing is held out from it.

Figure 4: Complete recovered circuit families for three MMLU subjects on Qwen3-1.7B, shown on the module graph (

28

layers

\times

16

heads, MLP rail below). The recovered families contain

14

10

and

8

circuits, with median sizes

55

67

and

49

, respectively. Dark rings mark the modules present in every recovered circuit:

7

of the

189

modules used in (a),

15

230

in (b), and

10

136

in (c). The remaining modules vary across circuits.

Method	KL ${}_{\text{held}}$ $\uparrow$	retention $\uparrow$	circuits $\uparrow$
Dense model	$1.00$	$1.00$	—
Random- $k$	$-0.01{\scriptstyle\pm}0.01$	$0.18{\scriptstyle\pm}0.00$	—
Magnitude	$0.02{\scriptstyle\pm}0.00$	$0.21{\scriptstyle\pm}0.00$	—
Wanda	$-0.05{\scriptstyle\pm}0.00$	$0.20{\scriptstyle\pm}0.01$	—
EAP	$0.15{\scriptstyle\pm}0.01$	$0.20{\scriptstyle\pm}0.02$	—
ACDC (greedy)	$\mathbf{0.42{\scriptstyle\pm}0.01}$	$\mathbf{0.74{\scriptstyle\pm}0.01}$	$1$

Table 4: Circuit recovery on ten MMLU subjects with Qwen3-1.7B, every mask at the subject’s matched active-component budget (ACDC at its converged size). All columns evaluate the frozen circuit with every other component given its activation on another prompt. KL

{}_{\text{held}}

is one minus the circuit’s KL divergence from the unmodified model, divided by the divergence when every component is replaced, on questions disjoint from discovery (

1

= the circuit behaves like the full model,

0

= no better than replacing every component); retention is discovery-prompt accuracy relative to the dense model; circuits is the number of distinct proposals per subject that are 1-minimal under the raw verifier. Means over ten subjects and three discovery seeds,

\pm

the across-seed standard deviation.

Figure 5: Credit estimators against the exact policy gradient on an enumerable MaxSAT instance with a frozen mid-training policy and

K=6

; the reference is the exact gradient from full enumeration of the subset lattice. (a) Per-proposal credit over shared rollout groups: the l1o deletion credit is non-negative, while l2o and group-mean centering are signed. (b) Small points are

512

-group estimates, large points show their mean across sixteen independent estimates, ellipses show

2\sigma

dispersion, and the star is the exact gradient. (c) Running relative error

\lVert\bar{g}_{N}-\nabla J\rVert/\lVert\nabla J\rVert

; the dotted guide is

1/\sqrt{N}

and the dashed line the group mean’s bias.

Figure 6: Training group size and deployment budget at

36{,}864

training verifier calls per instance; the dashed line is the antichain size

|\mathcal{M}|

. (a) Recovery at

B=256

proposals: grey paths are the three seeds after averaging six instances, filled markers their means, open rings empirical estimates. (b) Deployment sweep of the frozen policies: lines show the expected number of distinct minimal witnesses in

B

proposals, computed in closed form (Appendix B.5 ), and markers show the number found in the first

B

sampled proposals.

$N$	$\cos(\widehat{\widetilde{A}},\widetilde{A})\uparrow$	relative $\ell_{1}$ error $\downarrow$	support recall $\uparrow$	policy-grad. cosine $\uparrow$
$256$	$0.866{\scriptstyle\pm}0.138$	$0.516{\scriptstyle\pm}0.176$	$0.594{\scriptstyle\pm}0.140$	$0.888{\scriptstyle\pm}0.163$
$1{,}024$	$0.970{\scriptstyle\pm}0.027$	$0.232{\scriptstyle\pm}0.069$	$0.850{\scriptstyle\pm}0.150$	$0.972{\scriptstyle\pm}0.020$
$5{,}000$	$0.995{\scriptstyle\pm}0.004$	$0.094{\scriptstyle\pm}0.033$	$1.000{\scriptstyle\pm}0.000$	$0.995{\scriptstyle\pm}0.004$
$20{,}000$	$0.998{\scriptstyle\pm}0.001$	$0.059{\scriptstyle\pm}0.017$	$1.000{\scriptstyle\pm}0.000$	$0.999{\scriptstyle\pm}0.001$

Table 5: Shared-sample Monte Carlo fidelity against exact enumeration under the geometric measure with

p=0.7

. Credit-vector metrics average 20 sample batches for a fixed

K=48

group; the policy-gradient cosine averages 12 on-policy groups. The first two columns use the baseline-adjusted

\widetilde{A}

, support recall uses raw

A

, and

N

counts auxiliary samples from

\mu

, which do not spend verifier calls.

Figure 7: Base-measure sweep on the MaxSAT benchmark. Only the parameter

p

of the geometric measure varies; the dotted line marks

p=1/\sqrt{2}

. We report means and across-seed standard deviations over three seeds and eight instances.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

	Bench10	8B family	8B leaf
Probes	$630$	$546$	$2{,}688$
Raw violation $\downarrow$	$0.83$	$0.56$	$0.56$
Closure repair $\uparrow$	$0.70$	$0.73$	$0.68$
Residual $\downarrow$	$0.25$	$0.15$	$0.18$
1-minimal	$15/15$	$13/13$	$64/64$

Appendix

Table 6: Non-monotonicity at

\alpha=0.8

. Bench10 uses Qwen3-1.7B; the other two verifiers use Qwen3-8B. Raw violation is the fraction of sampled supersets rejected by the raw verifier; closure repair is the fraction of these violations in which the finite closure finds an accepted subset. Residual bounds the violations left after the finite closure. 1-minimal counts the returned circuits that are 1-minimal.

Figure 8: Violation of monotonicity in the circuit verifier. (a) Fraction of random supersets of a verified circuit rejected by the raw predicate, against the number of added components. A monotone predicate would reject none. (b) Mean faithfulness of the rejected supersets; the dashed line is the acceptance threshold

\alpha=0.8

Measure	Interface	minimal-output rate $\uparrow$	antichain recall $\uparrow$
Coverage $\mathcal{R}_{\mu}$	$S,s_{c}(S),\mu$	$0.758{\scriptstyle\pm}0.010$	$0.667{\scriptstyle\pm}0.016$
Counting	$S,s_{c}(S),\Phi(S)$	$1.000{\scriptstyle\pm}0.000$	$0.993{\scriptstyle\pm}0.007$

Appendix

Table 7: Coverage and counting measures. The interface column lists each measure’s inputs. Minimal-output rate is the fraction of delivered witnesses that are minimal: the born-minimal rate for coverage, one by construction for counting. Mean

\pm

standard deviation over three seeds and eight MaxSAT instances.

Figure 9: Deletion credit in the example of Figure 2 , with minimal witnesses

\{a,b\}

and

\{c,d\}

. Bar widths represent

\mu

-measure. The top bar shows

U_{K}

, partitioned by overlap among successful up-sets. Each bar below shows a proposal’s up-set; the solid portion contains the sets certified only by that proposal and has measure

A_{i}

. Here

S_{1}=\{a,b\}

is minimal and

S_{3}=\{c,d\}

is a second minimal witness, while the redundant

S_{2}=\{a,b,c\}

and the rejected

S_{4}=\{b,c\}

have zero credit, matching ( 14 ).

Figure 10: Per-element refinement ratio

\nu(|S|)/\nu(|S|{+}1)

of the base measure. This ratio is

1/p

for the geometric family and approaches one under polynomial reweighting as witness size grows. The band spans the two reference cases: strong refinement at

p=\tfrac{1}{2}

and no refinement preference at

p=1

. The experiments use

p=0.7

, close to

1/\sqrt{2}

, which has equal logarithmic distances to the two reference cases.

Item	Setting
Instances	$8$ formulas, $14$ variables, $10$ clauses of length $3$
Episode	add or $\mathrm{STOP}$ , horizon $H=12$
Actor	$15\!\to\!128\!\to\!128\!\to\!15$ , tanh activations
Rollout batch	$8$ groups per update, $K=48$ proposals per group
Training	$150$ updates, $57{,}600$ terminal verifier calls per formula
Optimization	Adam, learning rate $3\times 10^{-3}$ , entropy $0.02$ , gradient norm $1.0$

Appendix

Table 8: Common configuration for the MaxSAT policy-gradient comparison.

Figure 11: Deletion credit across planted antichain geometries. (a) The advantage each objective assigns inside one rollout group, under the planted verifier with

\mathcal{A}=\{\{a,b\},\{c,d\}\}

and the geometric measure at

p=0.7

; stems are scaled per row and every value is printed. GRPO and RLOO use only the verifier bit: the redundant

S_{2}

has the same advantage as the minimal witnesses

S_{1}

and

S_{3}

(dashed tie). Only the rejected proposal receives a different advantage. Raw deletion credit l1o assigns the mass certified only by each proposal:

0.147

and

0.250

for the two minimal witnesses, and zero for the redundant and rejected proposals. The l2o credit subtracts the leave-two-out baseline:

S_{3}

retains positive credit,

S_{1}

a small positive credit, and

S_{2}

the lowest credit, below that of the rejected

S_{4}

. (b) Sixteen conditions combine eight planted geometries with two group sizes. The axes vary family size

L

and the relative witness values:

|S_{i}|\equiv 4

gives

p^{4}{:}p^{4}

, while

|S_{i}|\in\{2,6\}

gives

p^{6}{:}p^{2}

. Bars report the paired antichain-recall difference between MWRL and the strongest learned baseline after

32{,}768

matched verifier calls (

5

predicates

\times

3

paired seeds). Bold edges mark

95\%

bootstrap intervals excluding zero; solid and hatched bars denote

K=2L

and

K=L/2

. Within each quadrant, bars order the low-overlap

q_{0.1},q_{0.9}

conditions followed by the high-overlap

q_{0.1},q_{0.9}

conditions.

MaxEnt RL, $\alpha$	$0.1$	$0.2$	$0.3$	$0.5$	$1$
$0.02$	3.2 (0.77)	1.1 (0.87)	–	–	–
$0.05$	0.4 (0.00)	3.8 (0.49)	0.3 (0.24)	0.0 (0.00)	0.0 (0.00)
$0.1$	0.0 (0.00)	0.4 (0.00)	4.3 (0.12)	0.4 (0.20)	0.0 (0.00)
$0.2$	0.0 (0.00)	0.0 (0.00)	0.0 (0.00)	2.0 (0.02)	0.2 (0.13)

Appendix

Table 9: Size-penalty sweeps for MaxEnt RL and GFlowNet on the eight MaxSAT formulas, each run with

57{,}600

verifier calls per formula. MaxEnt entries give the number of distinct minimal witnesses found and, in parentheses, the born-minimal rate. The GFlowNet penalties

\lambda=0

and

\lambda=0.36=\log(1/0.7)

are the success and up-set rewards. Entries are means over three policy seeds after averaging the formulas; bold entries are reported in Table 2 , and dashes mark settings not run.

Figure 12: Logarithmic distances to the strong-refinement reference (

p=\tfrac{1}{2}

) and the limit of no refinement preference (

p=1

). The distances sum to

\log 2

and are equal at

p=1/\sqrt{2}

; the experiments use

p=0.7

. The dashed diagonal marks equal distances, and the open circle marks the unattainable ideal point.

Centering	Rescale	born-min. rate $\uparrow$	antichain recall $\uparrow$	# found $\uparrow$
Group mean	Mean abs.	$0.879$	$0.622$	$11.25$
Group mean	Std. dev.	$0.821$	$0.615$	$11.13$
l2o	Mean abs.	$0.819$	$0.675$	$12.25$
l2o	Std. dev.	$0.757$	$0.687$	$12.50$

Appendix

Table 10: Credit-rescaling sensitivity for coverage MWRL on the eight MaxSAT formulas. All rows use policy seed

0

Item	Setting
Tasks	1,024 substrate pairs; 205 held out per seed
Dimensions	catalyst system (6), base (6), solvent (6), water fraction (3), temperature (3), and binary time, catalyst loading, base equivalents, boron equivalents, concentration, ligand-to-palladium ratio, cosolvent, additive, and atmosphere
Panel per task	baseline, 28 singleton, 346 pairwise, and 2,504 triple deviations
Success	yield at least 75 percent; one global threshold
Antichain	2 to 35 minimal witnesses per task, mean 8.6; 201 distinct minimal witnesses, 986 distinct antichains
Popularity audit	held-out recall of the 16 most frequent minimal witnesses $0.42$ (release criterion $\leq 0.45$ ); $0.15$ , $0.25$ , $0.63$ at budgets 4, 8, 32

Appendix

Table 11: The released augmented Suzuki environment. Parentheses give the number of candidate values per dimension, including the baseline. The popularity audit row reports the substrate-blind frequency baseline used in the benchmark release criterion.

Item	Setting
Fingerprint	33 substrate descriptors from SMILES
Actor	hidden width 256, tanh; add, remove, or stop; full-set start; horizon 14
Group return	coverage measure with geometric $\mu$ , $p=0.7$ , l2o baseline, mean-absolute scaling
Amortized training	$K=32$ , 8 task groups per update, 4,800 updates
Per-substrate training	$K=32$ , 400 updates per task
Optimization	Adam, learning rate $5\times 10^{-4}$ , entropy $0.02$ , gradient norm $1.0$

Appendix

Table 12: Configuration for the Suzuki comparison.

Amortized MWRL
Method	born-min.	recall $\uparrow$		#found $\uparrow$
	rate $\uparrow$	seen	held-out
Per-substrate	$0.58{\scriptstyle\pm}0.01$	$0.88{\scriptstyle\pm}0.00$	—	$6.4{\scriptstyle\pm}0.0$
Conditioned	$0.58{\scriptstyle\pm}0.03$	$0.86{\scriptstyle\pm}0.01$	$0.83{\scriptstyle\pm}0.04$	$6.1{\scriptstyle\pm}0.3$
Substrate-blind	$0.11{\scriptstyle\pm}0.05$	$0.41{\scriptstyle\pm}0.10$	$0.38{\scriptstyle\pm}0.08$	$2.7{\scriptstyle\pm}0.5$
Scalar RL	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.00{\scriptstyle\pm}0.00$	$0.0{\scriptstyle\pm}0.0$

Appendix

Table 13: Amortized recovery on the fully synthetic 172-substrate library, mean and standard deviation over three seeds that control the substrate split and the policy. Per-substrate search retrains for each substrate and marks the recovery ceiling, so it has no held-out entry.

Figure 13: Hierarchical sparse circuits on Qwen3-8B. (a) The recovered portion of the taxonomy. Node area scales with circuit size; labels give distributional faithfulness and the median size of the recovered 1-minimal circuits. Dashed nodes denote tasks for which no circuit was recovered among the evaluation proposals. (b–d) Three leaf supports over the full component graph. Each support is the union of the successful canonical circuits in the 24 evaluation proposals for that leaf, covering

63

81

, and

36

of the

1{,}188

modules. Colored marks denote retained attention heads and MLP blocks; grey marks denote components given counterfactual activations.

Figure 14: Task-indexed transfer of the Qwen3-8B leaf supports. (a) First-token correct-versus-foil accuracy of each recovered support, activated alone with every other component given its counterfactual activation, on every evaluation leaf. Columns group the leaves into the four task families, blank cells are zero, and boxes mark the support’s own leaf. (b) The highest accuracy any recovered support reaches on each leaf, against the dense model on the same leaf. Recovered supports match the dense model on most arithmetic leaves, but not addition; knowledge and temporal coverage is partial, and the search recovered no grammar support. (c) Each support’s mean accuracy on its own leaf, on the remaining leaves of its family, and on the leaves of the other families. Accuracy on a support’s own leaf averages

0.86

and accuracy outside its family averages

0.08

Item	Setting
Model	Qwen3-1.7B, bfloat16, eager attention, frozen weights
Components	448 query heads and 28 MLP blocks
Verifier	raw verifier $s_{0}$ , $\alpha=0.8$
Actor	$953\!\to\!512\!\to\!512\!\to\!953$ , tanh activations
Episode	add, remove, or stop; full-set start; horizon 476
Group return	coverage measure with geometric $\mu$ , l2o baseline, mean-absolute scaling

Appendix

Table 14: Configuration for the Qwen3-1.7B Bench10 circuit-discovery experiment.

Item	Setting
Model	Qwen3-8B, bfloat16, eager attention, frozen weights
Components	1,152 query heads and 36 MLP blocks
Verifier	raw verifier $s_{0}$ , $\alpha=0.8$
Actor	$2377\!\to\!512\!\to\!512\!\to\!2377$ , tanh activations
Episode	add, remove, or stop; parent-support start; horizon 1,188
Group return	coverage measure with geometric $\mu$ , $p=0.7$ , l2o, mean-absolute scaling

Appendix

Table 15: Configuration for the three Qwen3-8B hierarchical passes.

Family	Subtask	Leaves
Knowledge	Geography	country capital; country continent
	Culture	country language; country currency
	Chemistry	element symbol; element state
Arithmetic	Basic	addition; subtraction
	Comparison	larger number; smaller number
	Sequence	next number; previous number

Appendix

Table 16: The complete Qwen3-8B behavior taxonomy used for hierarchical search.

Setting	ground set $\mathcal{E}$	verifier bit $s(S)=1$	base measure $\mu$
Instantiated in this paper
MaxSAT witnesses	Boolean variables	setting the variables in $S$ to true satisfies every clause	geometric, $p=0.7$
Reaction conditions	condition dimensions opened from a baseline	a tabulated assignment inside the opened set reaches the yield threshold	geometric, $p=0.7$
Sparse circuits	attention heads and MLP blocks	with every other component given its counterfactual activation, faithfulness stays at least $\alpha$	geometric, $p=0.7$
Further settings admitted by the conditions
Coherent systems	components	the system fails	component failure law

Appendix

Table 17: Instantiations of minimal-witness identification. Each row names the ground set over which proposals are formed, the event that the verifier bit indicates, and the information a domain supplies for choosing the base measure of Appendix D .

Explore similar work

Sep 14, 2026cs.LG

MInTRL: Off-policy Intervention can boost On-policy RL

Reinforcement learning with verifiable rewards is typically performed on-policy, keeping training data close to the current policy but limiting learning to trajectories that the policy can discover itself. Off-policy methods such as supervised fine-tuning, on the other hand, can leverage external knowledge beyond the base model's capabilities, but may suffer from large distribution shift. The key challenge is thus to expand exploration without sacrificing learnability. In this work, we introduce Minimal Intervention Reinforcement Learning (MInTRL), which expands the exploration frontier through sparse, local interventions in otherwise on-policy rollouts. During generation, a judge-intervention policy periodically reviews the current policy's output, replaces erroneous suffixes with short corrections, and immediately returns control to the policy. During training, MInTRL adopts a sequence-level advantage-regression objective that eliminates the need for importance sampling. We show that sparse, local interventions can substantially improve coverage beyond finite-budget on-policy sampling while preserving the overall on-policy nature of the resulting trajectories. Across math and code benchmarks, MInTRL consistently outperforms standard on-policy and off-policy baselines. Ablations show that MInTRL remains effective with self-intervention and across different judge policies, while performance peaks at moderate intervention intensity, highlighting the importance of intervening minimally. These results establish minimal intervention as an effective paradigm for enhancing on-policy RL.

Mingyu Chen, Yefan Tao, Gerald Friedland +2

Amazon Web Services · Boston University

Off-Policy Learning

Ask PDF

May 29, 2026cs.LG

Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach

Inverse reinforcement learning (IRL) typically assumes demonstrations from a single optimal demonstrator, but in many applications data come from multiple imperfect demonstrators with heterogeneous suboptimality levels. We study reward learning in this setting through a feasible-reward-set framework: for each demonstrator, we encode its declared suboptimality level as a linear constraint and intersect the resulting feasible sets across demonstrators. Our theoretical analysis shows that the joint feasible set shrinks monotonically as data are added, and we give an exact characterization of when a new demonstrator strictly tightens it. We further establish two recovery guarantees for the feasible reward set of the ground-truth optimal demonstrator: one bound depends on closeness to the optimal occupancy, while the other requires only sufficient coverage and no near-optimal demonstrator. On the practical side, we introduce strategies to address the inherent reward ambiguity in the obtained reward set and provide an offline algorithm with function approximation for high-dimensional environments. Experiments in tabular grid-world and large language model (LLM) fine-tuning settings are consistent with the theoretical predictions and demonstrate the effectiveness of the proposed framework over baselines.

Kihyun Kim, Shripad Deshmukh, Nikos Vlassis +1

MIT LIDS · University of Massachusetts, Amherst · Adobe Research +1

Offline Reinforcement Learning Inverse Design Ground Truth

Ask PDF

May 27, 2026cs.CL

Soft-SVeRL: Self-Verified Reinforcement Learning with Soft Rewards

Reinforcement Learning from Verifiable Rewards (RLVR) has improved language models in domains such as mathematics and code, where correctness can be checked automatically. However, many important tasks are only partially verifiable: prompts contain multiple requirements, responses may satisfy some but not all of them, or no single reference answer might exist. We introduce Soft-RLVR, a framework for reinforcement learning from decomposed, learned verification signals. Soft-RLVR converts each prompt into a checklist of atomic requirements, scores candidate responses item by item with an LLM verifier, and trains on the resulting soft reward. Checklist-based rewards turn sparse pass/fail supervision into a denser partial-credit signal, but they also introduce a tradeoff: averaging item-level judgments can reduce verifier noise, while partial credit can reward incomplete responses. We formalize this tradeoff and identify conditions under which checklist-based verification gives a more reliable RL training signal than holistic verification. We further introduce Soft-SVeRL, a self-verifying variant of Soft-RLVR in which the policy also acts as the verifier. We show that self-verification is prone to reward inflation from overly permissive self-judgments, and that explicit stabilization is needed to prevent this collapse. In a controlled instruction-following setting with rule-based ground-truth evaluation, checklist-based Soft-RLVR improves IFEval by up to 11.1 points using only learned verifier rewards. Our experiments further show that verifier quality and checklist quality both affect downstream RL outcomes, and that explicit stabilization is essential for effective self-verification.

Saurabh Dash, Pierre Clavier, John Dang +4

Cohere Labs · Cohere · Adaption Labs +1

Reinforcement Learning With Verifiable Reward Verifiable Rewards

Ask PDF