acceptodds
Withdrawn from ICLR 2027

Certify, Refute, or Abstain: Claim-Aware Policy Auditing in Multi-Agent Reinforcement Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

High task return does not establish that a policy satisfies a declared protocol or deviation-gap claim. Claim-Aware Protocol Auditing (CAPA) distinguishes the evidence needed to certify a claim from the evidence sufficient to refute it: an upper bound supports certification, a lower bound supports refutation, and insufficient evidence requires abstention. We formulate unconditional false-decision and false-selection guarantees and show that passive rollouts cannot improve a worst-case gap bound on an indistinguishable bounded-game pair. A constructed soft leader–follower example separates return ranking from protocol-map conformity: the return-10 candidate violates the map tolerance, whereas the selected conforming candidate has return 3.956. Synthetic boundary calibration exposes undercoverage of Gaussian plug-in bounds; matched Student-t bounds require iid Gaussian gains. On fixed learned MPE candidates, a seeded neural-deviation audit reports all 45 probes with paired returns and explicit Gaussian-approximation limits. No learned candidate has an unrestricted upper-bound certificate. The resulting evaluation contract makes policy performance, evidence of a violation, and the stronger evidence needed for certification separate objects of assessment.

Primary area:
reinforcement learning
Keywords:
protocol auditing, selective prediction, abstention, multi-agent reinforcement learning, claim certification

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_fUGkOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes CAPA, a reporting contract for auditing claims about MARL policies. A claim specifies four things: a violation functional Δq\Delta_q (e.g., a unilateral-deviation gap or a distance to a declared policy map), a tolerance ϵq\epsilon_q, and two predicates. The predicates control the unconditional probabilities of false certification and false refutation.

The decision rule is:

  • Certify if a valid upper bound is at most ϵq\epsilon_q.
  • Refute if a valid lower bound exceeds ϵq\epsilon_q.
  • Abstain otherwise. A selector then returns the certified candidate with the smallest upper bound, or abstains if no candidate is certified.

The theoretical results are:

  • Thm. 4.1: two games with identical on-policy trajectory laws but gaps of 00 and HWHW. This shows passive rollouts cannot tighten the trivial bound.
  • Thm. 4.2: the resulting certify/refute/abstain tradeoff on that pair.
  • Prop. 4.3: one crossing probe refutes, via a union bound.
  • Thm. 4.4: a union bound on false selection.
  • App. A: standard contraction, Hoeffding and finite-cover bounds. The empirical part has three pieces:
  1. A hand-constructed 2×2 leader–follower game with six constructed candidates. Here, picking the highest leader return violates the declared soft map.
  2. A seeded audit of fixed IPPO, MAPPO and HAPPO checkpoints on MPE Simple Spread, using 45 REINFORCE deviation probes. Outcomes: one approximate refutation (MAPPO), two abstentions, and no certificates.
  3. Synthetic calibration of Gaussian vs. Student-t lower bounds, plus "historical exploratory" measurements that the authors state were produced with a defective reward collector and unseeded randomness.
Critical strengths

1. The conceptual distinction is correct and stated carefully. The paper keeps four things separate:

  • what a lower bound licenses (refutation) versus what an upper bound licenses (certification);
  • unconditional error control versus conditional correctness among returned candidates. It also notes explicitly that a passing theorem for valid bounds does not validate a Gaussian plug-in bound.

The arithmetic holds up. I recomputed the exact example: q0∗=1/(1+e4)q_0^* = 1/(1+e^4), q1∗=1/(1+e8)q_1^* = 1/(1+e^8), p∗≈0.0027p^* \approx 0.0027. Every return, RsR_s and RuR_u entry in Table 1 reproduces (3.956, 3.829, 10, 4.25, 1; residuals 0.06, 0.97, 0.018, 0.5, 0.997). The Gaussian and Student-t lower bounds for the MAPPO crossing (0.216, 0.086, 0.062) also reproduce, as do the 512-reset confirmation and the paired budget contrasts in Table 6.

2. The seeded audit follows good reporting practice.

  • All 45 probes are reported without best-seed filtering.
  • Positive restoration controls check the evaluation path.
  • The known-violation search control is a genuinely useful negative result. A 6.9-point profitable deviation is never recovered by REINFORCE search at 50, 200 or 800 episodes, across three seeds and three disjoint evaluation sets. This is a concrete warning that failed response search should not be read as a small gap.
Critical weaknesses

1. There is no new capability, and the paper says so.

The paper concedes most of the ground itself:

  • It does not claim novelty for approximate best responses, Bonferroni correction, residual bounds, or abstention (Sec. 2).
  • It states that "an exploitability evaluator with valid bounds and honest uncertainty/abstention can make the same decisions as CAPA" (Sec. 2).
  • It says no experiment demonstrates superiority over such an evaluator (Sec. 6).
  • It says the experiments do not show that published IPPO/MAPPO/HAPPO evaluations made the unsupported inference CAPA is meant to prevent (Sec. 1). What remains is a three-way decision rule based on confidence bounds. That is the classical interval-based three-decision / equivalence-testing setup, applied to exploitability.

The theoretical results do not add much beyond this:

  • Thm. 4.1 is an identifiability statement: a deterministic policy never visits a1a_1, so on-policy data cannot see its payoff.
  • Thm. 4.2 follows immediately from Thm. 4.1.
  • Prop. 4.3 and Thm. 4.4 are single union bounds.
  • App. A collects textbook contraction and Hoeffding arguments. None of these needs more than a few lines, and the paper itself describes them as exposing "evidence requirements rather than new … methods" (Sec. 4).

The flagship "ranking reversal" is built in by construction:

  • The two return-10 candidates require the follower to play b=1b=1 after a=1a=1, where B11=−2<B10=2B_{11} = -2 < B_{10} = 2. This is a strictly worse reply in that subgame, so no soft-response map would endorse it.
  • Since FF is constant in xx, the "map residual" is just the ℓ∞\ell_\infty distance to a precomputed target policy. That target is the logit agent-QRE of this extensive-form game, though the paper never names it.
  • The paper concedes that zero false promotions is mechanical (Sec. 6, App. C.5). The example therefore shows that optimizing one player's payoff over the joint policy ignores the other player's incentives. That is not a finding a reader needs a framework to learn.

2. The learned evaluation cannot exercise the framework, and it is padded with data the authors cannot stand behind.

(a) Certification is impossible by construction. No upper-bound backend is instantiated for any learned candidate, so every learned certification bit is zero by construction (App. C.5).

(b) Refutation depends on a search the paper shows is too weak. The audit's own known-violation control finds no learned response at any budget, while the supplied response gains 6.9. So the two "abstain" verdicts carry no information. The search also has visible weaknesses:

  • Probes are randomly initialized REINFORCE policies trained for 200 episodes (about 5,000 environment steps). Their untrained gains are already −1.8 to −4.1.
  • Warm-starting the deviator from πi\pi_i, so the gain starts near zero, and using a stronger learner are the obvious fixes.
  • REINFORCE is trained with discount 0.99 for an undiscounted 25-step objective. (c) The audited object is not the trained policy. It is a deterministic argmax with zero recurrent state, d(π)d(\pi). Its return is never compared with that of the deployed stochastic or recurrent checkpoint. A refutation of d(π)d(\pi) may therefore reflect the transformation rather than the learner.

(d) The tolerance is not chosen with the noise level in mind. ϵ=0.05\epsilon = 0.05 is unmotivated relative to the noise: the paired-gain SE is about 0.37 at n=128n = 128. In practice the test is against zero.

(e) The primary bound is one the paper itself shows undercovers. The main audit uses Gaussian plug-in bounds even though the paper's own Table 8 shows they undercover, and a Student-t bound was trivially available. The single MAPPO crossing is fragile under that bound: with Student-t the LCB is 0.062, which falls below the tolerance in 40 of 128 leave-one-out variants (App. C.1). The 512-reset confirmation does support it, and that is the paper's strongest learned finding.

(f) Known-defective, unverifiable results should not be in the submission. The paper retains "historical exploratory" results produced with a reward collector that gave zero training reward to non-final agents and with unseeded Torch randomness (Sec. 6, App. C.2–C.4). App. D states that 74 of 179 summary rows could not be recomputed and that raw deltas for some controls "were not located." Some of these records are cited in the main text (Sec. 6, "Calibration and sensitivity diagnostics").

These results should be removed rather than retained with caveats. Where they overlap with the seeded audit, they also disagree with it: the historical audit refutes IPPO, the seeded audit refutes MAPPO. That disagreement itself suggests verdicts are driven by search randomness.

(g) Presentation compounds these problems.

  • Much of the main text consists of caveats about what is not shown.
  • Revision-history language recurs throughout: "new", "retained", "repaired evaluator", "the review reconciled 179 summary rows".
  • Figures 5–7 replot Table 1, and Figure 8 plots the deterministic arithmetic 0.32/B0.32/\sqrt{B}.
Questions for authors
  1. Can CAPA certify anything nontrivial? Can you instantiate an upper-bound backend on learned candidates in a setting where it is feasible? Examples: small OpenSpiel or tabular Markov games with exact best responses, or stochastic candidates with full-support exploration that permit off-policy upper bounds. Without this, CAPA never certifies anything nontrivial in the paper.
  2. What problem does CAPA solve? Can you point to published evaluations where return rankings were used to support equilibrium or protocol claims? If not, what does CAPA prevent that standard exploitability reporting with valid confidence intervals does not?
  3. Can a stronger search recover the known violation? If the deviator is warm-started from πi\pi_i and trained with a stronger learner (e.g., PPO with a larger budget), does it recover the 6.9-point restoration control? If the search cannot find a known violation, how should a reader interpret any abstention?
  4. Does the transformation degrade the policies? What are the returns of d(π)d(\pi) (argmax, zero hidden state) compared with the original stochastic or recurrent checkpoints? Is the MAPPO refutation also present for the untransformed policy?
  5. Why the Gaussian plug-in, and why ϵ=0.05\epsilon = 0.05? Why is the Gaussian plug-in bound kept as the primary rule when your own calibration shows undercoverage and the Student-t version is available? How was ϵ=0.05\epsilon = 0.05 chosen relative to returns of −15 to −27 per agent and an SE of about 0.37?
  6. Is there a power or coverage result? Is there any positive result giving conditions under which CAPA certifies true claims and refutes false ones with high probability? This would complement the impossibility results in Thms. 4.1–4.2.
  7. Why does the selector ignore return? Algorithm 1 returns the certified candidate with the smallest upper bound, using return only to break ties. Given the paper's motivation, why not maximize return within the certified set? You note that this rule has the same guarantee.
Reviewer_jPPGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The authors explore claim-aware protocol auditing through game theoretic mechanisms.

Critical strengths

Claim-Aware Protocol Auditing is an interesting area, and I think there are some interesting ideas being explored here. However, as will be discussed in the weaknesses section below, I fundamentally believe the paper is so lacking in its presentation and explanations that it makes parsing the work almost impossible. Even if the work is parsed, I do not believe the current set of experiments or presented evidence is sufficient to provide a foundation for future work, or to move this space forward in any meaningful manner.

Critical weaknesses

I assess papers in terms of two primary considerations - how interesting are the ideas presented, and how accessible the work is. Fundamentally in my eyes it's impossible to truly assess the quality of the ideas presented because the presentation of the work is so poor. To me, I see this as a work that doesn't have a firm grip of who their audience is, or what they're trying to convey. It's not that the presentation is non-idiomatic, it's more that the work is not self sufficient enough in its explanations of its foundational concepts, in a way that makes anything downstream nigh on impenetrable. And if one was to read the abstract alone, they would wonder what the actual contribution of the work is - the abstract certainly ends with a whimper, and not a bang.

And this above statement about impenetrability is made by someone who has significantly more game theory experience than the average ICLR reviewer/author, and who has experience in MARL as well.

For example, take the concept of certifications. This is an overloaded term in the literature - however the primary community of practice using certifications as a part of their lingua franca is the certified robustness community. To some extent, this work uses language and even mathematical framing that would be familiar to that community. However, the actual mechanistic connection between the scenario and the certification is almost entirely absent.

To attempt to provide guidance to the authors, I present the following notes in the hope that they help you improve the quality of your future manuscripts:

  • Unless I'm mistaken, ICLR's style guide is very much to use author year citations, not numbered citations. And then to occasionally have cites like "Timbers et al.’s " without a year speaks to a degree of carelessness regarding how you present the work of your compatriots.
  • "High task return does not establish that a policy satisfies a declared protocol or deviation-gap claim". I get that the authors know what they're talking about, but I think it's important to write to your audience, which, crucially, is not just the set of authors. Even as someone who is familiar with and has worked on MARL & game theory papers (although both are not necessarily my primary area), I found this opening sentence to be nigh on impenetrable. And I would really argue that the abstract doesn't get better from this point.
  • The above carries on into the introduction. What is the difference between structured MARL and unstructured MARL? What are learners and policy classes? What is a high-return policy? Or reward-only selectors? Why are they "Our" reward-only selectors? You haven't yet established what you're doing, so making a claim of ownership is rather presumptive.
  • If you're going to be labelling something with an acronym (like MARL) then unless there's reason otherwise, it really should be treated as a proper noun, and thus the presentation should also be capitalized, so, in this case, Multi-Agent Reinforcement Learning (MARL).
  • I don't suppose you'd like to define Exploitability or NashConv. I'm familiar with these, and there are cites that they quantify unilateral improvement, but it probably would be useful to be clear about what exactly they're measuring the improvement of.
  • The works verbiage is often quite staccato. Look, for example, at the first paragraph of S2 - there's no flow between sentences, rather the paragraph is a bombard of facts without context. It reads more as checking a box for showing knowledge, rather than actually attempting to explain the foundations of the authors work, and to acknowledge the ideas they build upon. The related work section is also incredibly sparse.
  • Undefined and underdefined terms are rampant. Semantic operator? Surrogate operator?
  • Statements are made of the what, but not the why "One may set both budgets to a common \delta_q", for example. Or "Each soft choice uses its decision maker’s payoff and a Shannon-entropy bonus with temperature" - a reader is likely familiar with all of these terms, but there's nothing in the statements to tell a reader /why/ these have been used, or what they're supposed to care about from this?
  • "There is no entropy bonus, discount, or division by 25 in this audit objective" 25 is presented as a magic number, and not the size of the scale of the sum, which, well, also appears to be a magic number.
  • Inconsistent capitalization in bibliography.
  • Odd structuring - the authors were not even close to the page limit (I presume they've misread the page limit as including references rather than excluding them), and have moved key content to the appendices, and have used a numbered rather than author, year bibliography style.

I'll note that the paper does include an (incredibly brief) AI use statement, and neither of the recommended reproducibility and ethics statements.

Questions for authors
  • "One may set both budgets to a common \delta_q" - why? What would the implications of this be?
Reviewer_7DaxOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes Claim-Aware Protocol Auditing (CAPA), a reporting protocol for claims about fixed multi-agent policies, such as a bound on the unilateral deviation gap or conformity to a declared ``protocol map''. For a declared claim with tolerance ϵq\epsilon_q:

  1. a valid upper bound Uq≤ϵqU_q\le\epsilon_q certifies the claim;
  2. a valid lower bound Lq>ϵqL_q>\epsilon_q refutes it;
  3. otherwise the auditor abstains.

Error guarantees are unconditional error-event bounds (Def. 3.1). The theoretical results are:

  1. Thm. 4.1: passive rollouts cannot improve a worst-case upper bound on the deviation gap, shown with two games whose on-path behaviour is identical.
  2. Thm. 4.2: the decision probabilities of any passive rule on that pair obey pA≥1−δC−δRp_A\ge 1-\delta_C-\delta_R.
  3. Prop. 4.3 and Thm. 4.4: lower bounds give valid refutation, and a union bound gives valid selection.
  4. Appendix A: contraction, surrogate-transfer, response-oracle, paired-rollout and finite-cover ``backends''.

The experiments have three parts:

  1. Exact example. A 2×22\times2 soft leader--follower game with six hand-built candidates, where the highest-return candidate violates the map tolerance (Table 1).
  2. Neural audit} On one IPPO, MAPPO and HAPPO checkpoint each in MPE Simple Spread, 45 REINFORCE ``probes'' yield one Gaussian-approximate refutation (MAPPO) and abstention elsewhere (Table 2).
  3. Synthetic calibration. Simulations compare Gaussian plug-in and Student-tt bounds (Table 8).
Critical strengths
  1. The core point is correct. Finding an improving deviation can refute a claim but never certify one. Certification needs an upper-bound backend, and abstention is the honest default when neither bound is available. The guarantees are scoped carefully as unconditional error-event bounds, not posterior statements.
  2. The experiments are carefully run.
  • Seeds are fixed in advance, and all 45 probes are reported without filtering for the best seed.
  • The MAPPO crossing is confirmed on 512 fresh resets.
  • Positive ``restoration'' controls test the search itself.
  • The numbers are internally consistent: the soft-response values in Table 1, and the MAPPO lower bounds (0.216 at 0.05/150.05/15, 0.086 at 0.05/450.05/45).}
Critical weaknesses
  1. The paper makes no technical contribution beyond a reporting convention, and it says so itself.

a. The paper states that "an exploitability evaluator with valid bounds and honest uncertainty/abstention can make the same decisions as CAPA'' (l 75--76). It also says that its learned records "do not establish an additional statistical or computational capability over that comparator'' (l. 77--78), and that it does not claim novelty for approximate best responses, Bonferroni correction, residual bounds or abstention (l 72).

b. The formal results are textbook facts restated as theorems:

  • Thm. 4.1 is non-identifiability off the observed path.
  • Thm. 4.2 is arithmetic on three decision probabilities that are equal in both games.
  • Prop. 4.3, Thm. 4.4 and Cor. A.7 are union bounds.
  • Prop. A.2 is the standard contraction argument.
  • Prop. A.6 is Hoeffding's inequality plus a Lipschitz net.

c. That a lower bound on exploitability cannot certify a small gap is already the point of Timbers et al.(2022), which the paper cites.

d. The motivating failure is never shown to occur. The paper states that ``the experiments do not show that published IPPO, MAPPO, or HAPPO evaluations made that unsupported inference'' (l. 37--38). Neither a technical advance nor a documented problem in practice is established.

  1. The experiments never instantiate the contract with valid guarantees on a learned system, and the deviation search fails its own positive controls.

a. No certification is possible on learned policies. No upper-bound backend is implemented for them (l. 161), so no learned candidate can ever be certified.

b. Refutations are only approximate. They rest on Gaussian plug-in bounds that, by the paper's own account, do not satisfy Def.3.1 ("approximate refutation evidence, not a finite-sample guarantee'', Table 2).

c. "Abstain'' mostly measures how weak the search is. In the restoration controls, a known improving deviation gains 6.88. The learned probes have negative mean gains at every budget (−2.78-2.78, −3.76-3.76, −2.19-2.19 at 50, 200 and 800 episodes; Tables 4--5, Fig.3), so they do worse than simply keeping the candidate's own policy. The abstentions for IPPO and HAPPO therefore say little about those policies.

d. The exact example holds by construction. It is a 2×22\times2 game with six hand-designed candidates, scored against a known deterministic residual at ϵ=0.08\epsilon=0.08. The paper itself notes that "it is not an independent calibration result''.

e. The synthetic calibration restates known facts. A normal quantile with sample SD over-rejects at n=40n=40 (analytically 6.16% vs. 4.90% for Student-tt), and neither rule is valid under skewed noise.

  1. The paper is very hard to read, and much of the appendix should not be there. Some specific issues are:

a. Undefined terms. Central objects are never defined in the main text:

  • the semantic and surrogate operators Ts,Tu\mathcal T_s,\mathcal T_u, and the "declared protocol TT'';
  • the "claim-matched backend'' and the transfer bound;
  • the diagnostic tags (Surrogate-Only, Practical, Obstructed, Uncertified);
  • the difference between "unsupported'' and "false'' promotion.

b. Algorithm 1. (record the claim-matched backend, assumptions, estimates) has no computable content.

  1. Minor comments

a. Citation style. Citations are numeric (7; 8; 19), while the ICLR template requires natbib author--year citations.

b. Fig. 8. It plots a deterministic slack 0.32/B0.32/\sqrt{B} against a "synthetic budget parameter''. This has no statistical meaning and should be removed.

Questions for authors
  1. What decision can CAPA make that an exploitability evaluator with valid bounds and abstention cannot? If the answer is none (l. 75--78), what is the intended contribution?
  2. Can you instantiate any upper-bound backend, such as Prop.~A.6 on a small tabular Markov game or an exact best response, and show a certification or a correct abstention for a learned policy?
  3. Why do the probes fail the restoration control at every budget? Does a standard best-response learner, trained much longer as in Timbers et al. (2022), recover the known +6.88+6.88 deviation?
  4. Can you define Ts\mathcal T_s, Tu\mathcal T_u, the protocol TT and the diagnostic tags in the main text, and state formally what Algorithm 1 computes?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.