PaperlayerView exact revision on arXiv

Source-linked AI summary

VERA: Verifiable Feasibility Representations with Counterfactual Credit for Constrained Multi-Agent Control

Bo Yin, Dongbo Li, Hongkai Chen, Jie Liu, Guoliang Xing

arXiv:2609.38889v1cs.LG

TL;DR

Dynamic constraints can make rewarding actions infeasible, while decentralized actors lack access to the global quantities needed to assess feasibility. VERA trains an action-conditioned feasibility representation and counterfactual credit mechanism without using privileged information at execution. It improves reward-matched outcomes and identifies constraint geometry as a condition on when counterfactual credit works.

  • Problem

    In dynamic physical systems, contact duration, congestion, resource contention, and deadline slack change whether actions remain executable, while deployed decentralized actors lack the global quantities needed to assess feasibility.

    Source: §1 · pp. 1–2

  • Method

    VERA supervises a five-dimensional VFR with exact post-action targets and uses CGRA to score candidate representation–action pairs during training, while execution uses one local-observation actor pass.

    Source: §1 · p. 2

  • Results

    VERA reaches 55.33 ± 3.60% SR with 0.45 ± 0.81% COV, gains 8.74 SR points over the strongest reward-matched baseline, and CGRA adds 14.16–16.48 points across representations.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    Counterfactual credit succeeds when fixed-peer candidate scores preserve relevant physical-constraint ordering, but fails when locally favorable actions impose unpriced shared externalities.

    Source: §5 · p. 9

    Because the complete VERA configuration changes execution reward, the standard block alone cannot identify an architectural effect; the reward-matched protocol addresses this.

    Source: §3.3 · p. 5

Abstract

from arXiv · show

Constrained multi-agent control requires more than predicting rewarding actions: an action can cease to be executable as contact windows, shared capacity, and deadlines change. We introduce VERA, a centralized-training, decentralized-execution framework that separates feasibility estimation from credit assignment. Each actor predicts a five-dimensional verifiable feasibility representation (VFR). After an action is proposed, exact action-conditioned margins available only during training supervise that representation, while a counterfactual group-relative advantage (CGRA) ranks candidate representation-action pairs. Execution uses one actor pass and no privileged state. In a dynamic space-air-ground integrated network (SAGIN), VERA obtains 55.33% +/- 3.60% success with 0.45% +/- 0.81% coverage violation, within 1.33 percentage points of a privileged-mask reference. With rewards matched over ten paired seeds, VERA improves success over the strongest baseline by 8.74 percentage points (p=0.023) and reduces violation by 52.19 percentage points (p=5.7e-8). A ten-seed 4-by-2 factorial attributes a 14.16-16.48 percentage-point gain to CGRA across handcrafted, learned, random, and latent representations; evaluation on seven unseen topologies preserves a 24.33-30.02 percentage-point advantage over multi-agent proximal policy optimization. From 10 to 40 users, success remains 50.1-53.8%, and VFR adds only 0.026 ms to a central processing unit (CPU) actor step. Cross-domain tests further identify the governing condition: counterfactual credit succeeds when candidate scores respect shared constraints and fails under incompatible reward geometries. These results establish action-conditioned feasibility as an auditable training interface and counterfactual credit as a geometry-dependent optimization mechanism.

1 INTRODUCTION

Dynamic constraints can make a rewarding action infeasible, while deployed decentralized actors lack the global quantities needed to check feasibility. VERA trains an explicit feasibility representation and counterfactual credit mechanism, with reported gains in reward-matched and cross-topology evaluations.

1 INTRODUCTION

  • Dynamic contact duration, congestion, resource contention, and deadline slack change whether actions remain executable, but deployed decentralized actors lack the global quantities needed to assess feasibility.In SAGIN, satellite visibility, shared capacity, remote load, and end-to-end latency jointly determine whether an offloading action can complete.Source: §1 · pp. 1–2
  • VERA predicts a five-dimensional VFR supervised by exact post-action targets, then uses CGRA to score candidate representation–action pairs during training; execution uses one local-observation actor pass.The five coordinates are contact margin, energy difference, reachability, target utilization, and deadline buffer.Source: §1 · p. 2
  • Reward-matched baselines, a mechanism ladder, a representation–CGRA factorial, topology and scale tests, and cross-domain stress tests separate feasibility grounding from other sources of gain.The design also includes coordinate-removal and permutation controls and ten paired seeds.Source: §1 · p. 2
  • Under identical execution rewards, VERA improves success over AB-MAPPO-R by 8.74 points and reduces coverage violation from 52.70% to 0.51% over ten paired seeds.The comparison uses reward-matched baselines; coverage violation falls by 52.19 points.Source: §1 · p. 2
  • CGRA contributes 14.16–16.48 success points across four representation types, while the interaction with representation type is not detected.The stated applicability condition is that candidate scores respect shared constraints; incompatible reward geometry can produce reproducible failure.Source: §1 · p. 2
  • VERA reaches 55.33±3.60% success with 0.45±0.81% coverage violation, stays 24.33–30.02 points above MAPPO-R across seven topologies, and adds 0.026 ms per CPU actor step.Success remains 50.1–53.8% from 10 to 40 users.Source: §1 · p. 2

2 RELATED WORK

Related work covers cooperative MARL, constrained control, interpretable representations, SAGIN resource management, and verifier-based optimization. VERA’s stated distinction is an action-conditioned feasibility interface paired with candidate-relative credit, tested across topology, scale, and reward geometry.

Cooperative MARL and counterfactual credit

  • Cooperative MARL spans centralized critics, value factorization, policy gradients, and return-conditioned sequence models; CGRA instead compares one agent’s sampled representation–action candidates under fixed peer requests.This candidate comparison does not require joint-action enumeration or an execution-time privileged critic.Source: §2 · pp. 2–3

Safe and constrained control

  • Expected-cost constrained methods regulate long-run costs, while hard masks enforce per-decision feasibility only when exact constraints are known; VFR predicts missing action-conditioned quantities and complements available safety layers.VFR makes prediction error, consistency, and signed margins measurable.Source: §2 · p. 3

Decision-relevant and interpretable representations

  • Unlike observation-attached concepts or strict information bottlenecks, VFR targets are computed from realized state–action pairs and the action head retains a backbone bypass.The representation is a supervised, auditable pathway rather than a claim that five variables suffice for optimal control.Source: §2 · p. 3

Learning for SAGIN resource management

  • Prior SAGIN resource-management work commonly evaluates task reward under a fixed simulator and reports aggregate constraints; this work focuses on explicit action-conditioned feasibility and tests across topology, scale, and reward geometry.Source: §2 · p. 3

Verifier supervision and group-relative optimization

  • VERA adapts verifier supervision to typed feasibility margins and varies one agent’s candidate while holding peer requests fixed; reward-matched factorials distinguish relative-credit benefits from representation semantics.Source: §2 · p. 3

3 VERIFIABLE FEASIBILITY AND COUNTERFACTUAL CREDIT

VERA uses decentralized actors with training-time access to exact, action-conditioned feasibility targets. It couples an inspectable feasibility representation with counterfactual candidate scoring under fixed peer requests.

3.1 CONSTRAINED DECENTRALIZED CONTROL

  • Agents choose an execution target, offloading ratio, and bandwidth request from local observations, while shared resources and reachability couple their outcomes.During training, the verifier can evaluate proposed actions using global state; at execution, actors receive only local observations.Source: §3.1 · p. 4

3.2 VERIFIABLE FEASIBILITY REPRESENTATION

  • VFR provides an inspectable, intervenable pathway alongside direct encoder features; feasibility-sign accuracy depends on prediction error and distance from constraint boundaries.Its coordinates are normalized to fixed numerical ranges, and the representation is not claimed to be sufficient for optimal control.Source: §3.2 · pp. 4–5

3.3 ACTION-CONDITIONED VERIFICATION

  • Action-conditioned verification measures action–margin contradictions, while the execution reward includes success shaping and a coverage penalty.Reward-matched baselines and a mechanism ladder hold the execution reward fixed to separate reward effects from architectural and mechanism effects.Source: §3.3 · p. 5

3.4 COUNTERFACTUAL GROUP-RELATIVE ADVANTAGE

  • CGRA scores sampled representation–action candidates for one agent while holding peers’ same-slot requests fixed, then mixes normalized relative scores with GAE.The approach does not re-simulate peer reactions or future dynamics; it is informative when fixed-peer scores preserve constraint ordering and can be biased by unpriced externalities.Source: §3.4 · p. 5
  • Training evaluates multiple candidates, but decentralized execution computes the actor once without the verifier, counterfactual evaluator, global state, or peer requests.The supplied table caption identifies separate standard S5 and reward-matched S10 protocols, with MaskMAPPO observing exact decision-time feasibility.Source: §3.4 · p. 5, Table 2 · p. 6

4 EXPERIMENTS

The experiments compare VERA under standard and reward-matched protocols, then test mechanism attribution, topology transfer, scaling, execution cost, and cross-domain behavior. The evidence reports strong SAGIN performance while showing that CGRA’s effects depend on reward geometry.

4 EXPERIMENTS

  • The standard SAGIN benchmark uses five seeds, while confirmatory matched-design studies use ten paired seeds and report paired tests and Holm correction for topology families.The standard environment has 20 agents, six satellites, and four UAV nodes.Source: §4 · p. 6

4.1 PRIMARY PERFORMANCE AND CONSTRAINT COMPLIANCE

  • 55.33 ± 3.60% SR with 0.45 ± 0.81% COV makes VERA the best non-privileged method, 1.33 points below MaskMAPPO; under matched rewards it gains 8.74 SR points and reduces COV by 52.19 points.The reward-matched comparison is over ten paired seeds; VERA improves compliance on every seed.Source: §4.1 · p. 6

4.2 MECHANISM ATTRIBUTION

  • 14.16–16.48 SR points from CGRA across four representations, with no detected difference among their SR effects, identifies CGRA as the main performance driver.Coordinate-removal, random-target, and permutation controls change SR by at most 1.74 points; supervised VFR reduces COV versus an ungrounded latent head.Source: §4.2 · pp. 6–7, Figure 2 · p. 7

4.3 TOPOLOGY TRANSFER AND FEASIBILITY CALIBRATION

  • Across seven unseen topologies, VERA’s 50.93–53.17% SR exceeds reward-matched MAPPO’s 23.03–26.59% by 24.33–30.02 points, with significant paired gaps on all seven.Calibration follows physical margins: negative-margin bins have 100% violation, positive-margin bins 0%, and the boundary bin 52.4–86.7%.Source: §4.3 · p. 7

4.4 SCALING AND EXECUTION PROFILE

  • From 10 to 40 users, VERA sustains 50.1–53.8% SR; across six scale settings COV stays below 11%, and CPU actor latency adds 0.026 ms.Without retraining, high load and link failure retain 100% of source SR, while tighter deadlines and heavier tasks retain 47.8% and 46.3%.Source: §4.4 · pp. 7–8, Figure 3 · p. 8

4.5 REWARD GEOMETRY DETERMINES CROSS-DOMAIN BEHAVIOR

  • In VMAS, Full VERA reaches 24.75 ± 4.09% goal success versus 4.86 ± 4.20% without VFR/CGRA, but resource-allocation and force/contact tests expose failures under incompatible reward geometries.Every CGRA arm violates shared capacity on 100% of resource-allocation decisions; all three CGRA-bearing force/contact arms collapse on 10/10 seeds.Source: Figure 2 · p. 7, §4.5 · p. 8

5 CONCLUSION

The conclusion presents VERA as effective for dynamic SAGIN control, with CGRA supplying the principal measured gain and VFR providing an auditable feasibility interface. It qualifies transfer by the geometry of candidate scores and describes the associated artifact and disclosure practices.

5 CONCLUSION

  • VERA reaches 55.33 ± 3.60% SR with 0.45 ± 0.81% COV, gains 8.74 SR points over the strongest reward-matched baseline, and retains a 24.33–30.02 point gap over MAPPO-R on seven layouts.It sustains 50.1–53.8% SR from 10 to 40 users and adds 0.026 ms to a CPU actor step.Source: §5 · p. 8
  • CGRA succeeds when candidate scores preserve the ordering induced by relevant physical constraints and fails when locally favorable actions impose an unpriced shared externality.The authors identify learning or pricing constraint geometry as a next step toward general-purpose verifiable multi-agent control.Source: §5 · p. 9
  • The companion artifact includes simulator and experiment code, fixed seeds, configurations, traces, checkpoints, and independent recomputation tools; all 48 trace-archive files pass SHA-256 verification.The appendix documents the physical model, objectives, protocols, statistical tests, and artifact map.Source: REPRODUCIBILITY STATEMENT · p. 9
  • Generative AI tools assisted with language editing, organization, LaTeX, reference discovery, and figure-code refinement, but not experimental data generation, execution, outcome selection, or statistical analysis.The authors state they verified the manuscript and archived claims against primary sources and artifacts.Source: AI USE STATEMENT · p. 9

A EXTENDED EXPERIMENTAL AND IMPLEMENTATION DETAILS

The appendix supplies materials intended to support auditing of the paper’s main claims and reports final higher-precision analyses where available.

A EXTENDED EXPERIMENTAL AND IMPLEMENTATION DETAILS

A.1 ENVIRONMENT AND PHYSICAL MODEL

The benchmark models a three-tier space–air–ground network where task completion depends on visibility, deadlines, and shared bandwidth. Its simulator uses analytic orbital motion and a regional ground-track abstraction.

A.1 ENVIRONMENT AND PHYSICAL MODEL

  • The benchmark has K ground users, Msat LEO satellites, and Muav UAV nodes; its standard configuration uses 20, 6, and 4, respectively.LEO and UAV altitudes are 550 km and 20 km, with a 200-slot horizon and a 10° minimum satellite elevation.Source: §A.1 · p. 13
  • The LEO orbit is approximately 95 minutes, and visibility ends when ground-projected distance exceeds the elevation-implied threshold.The simulator uses analytic orbital motion and a regional ground-track abstraction.Source: §A.1 · p. 13
  • Each agent receives a task with probability 0.8; task size ranges from 5×10^4 to 2×10^5 bits, and compute intensity from 500 to 1,500 cycles/bit.The standard deadline is 0.15 s.Source: §A.1 · p. 13
  • Remote tasks succeed only if the link remains visible for the required transmission interval, while concurrent bandwidth requests are allocated proportionally.The simulator omits explicit Doppler re-synchronization and inter-cell interference.Source: §A.1 · p. 13

A.2 FEASIBILITY-MARGIN BOUND

The feasibility-margin bound shows when prediction error preserves feasibility signs and confines sign mismatches to two exceptional events.

A.2 FEASIBILITY-MARGIN BOUND

  • If every prediction error is at most ϵ and every true margin exceeds ϵ in absolute value, no predicted margin crosses zero.Thus every feasibility sign is preserved on E∩B.Source: §A.2 · p. 13
  • Any feasibility-sign mismatch is contained in the complement of the prediction-accuracy event or the complement of the margin-separation event.The union bound then gives Eq. (3).Source: §A.2 · p. 13
  • The implementation thresholds a signed contact-time margin for binary coverage validity, so the bound applies to its pre-threshold value.Source: §A.2 · p. 13

A.3 REWARDS, PROTOCOL, AND STATISTICS

The section specifies a layered execution reward, reward-matched mechanism comparisons, and seed-level reporting with paired statistical tests.

A.3 REWARDS, PROTOCOL, AND STATISTICS

  • The complete execution reward combines nonlinear success shaping, threshold bonuses, latency and energy terms, a squared coverage penalty, and validity and consistency rewards.Source: §A.3 · p. 14
  • Reward-matched controls share the execution reward, while the mechanism ladder varies VFR supervision, conditioning, consistency, bottlenecking, and CGRA.The complete-method comparison also changes the execution reward, so it is not an architecture-only comparison.Source: §A.3 · p. 14
  • Results are summarized as mean±sample standard deviation across seeds, with matched designs using two-sided paired t tests and paired standardized effect dz.The primary set has five seeds, confirmatory studies add five, and p > 0.05 is not interpreted as equivalence.Source: §A.3 · p. 14

A.4 COMPLETE STANDARD-CONFIGURATION RESULTS

The supplied evidence reports a five-seed same-objective comparison and identifies the scope of the standard-configuration table and success figure.

A.4 COMPLETE STANDARD-CONFIGURATION RESULTS

  • Table 3 reports standard-configuration metrics over the final 500-episode window and five seeds; latency averages successful tasks and must be read with success rate.Source: Table 3 · p. 14
  • Figure 4 compares standard-configuration success across methods; MaskMAPPO is a privileged-mask reference, while the constrained baseline is the tuned Table 2 configuration.Source: Figure 4 · p. 15
  • +2.58 success points (p = 0.218) and −10.31 violation points (p = 0.060) distinguish Full from w/o-VFR, but the five-seed tests do not support a strong mean claim.The authors treat these coarse tests as motivation for larger reward-matched and factorial studies.Source: §A.4 · p. 15

A.5 SAME-OBJECTIVE ABLATION AND ZERO-SHOT SHIFTS

The section tests VERA’s reward-matched performance, mechanism, transfer, calibration, failure cases, and deployment behavior. Results show a strong matched-seed advantage, while cross-domain tests expose conditions where counterfactual credit can undermine compliance.

A.5 SAME-OBJECTIVE ABLATION AND ZERO-SHOT SHIFTS

  • VERA retains 100% of source success under high load and link failure, but 47.8% and 46.3% under tighter-deadline and heavier-task shifts.Table 4 isolates VFR conditioning, the coverage coordinate, and verification reward under the VERA execution objective.Source: §A.5 · pp. 15–16, Table 4 · p. 15

A.6 TEN-SEED REWARD MATCHING AND CONSTRAINED-BASELINE TUNING

  • +8.74 success points and −52.19 violation points for VERA versus the reward-matched baseline over ten paired seeds.VERA improves success on 8/10 seeds and compliance on 10/10.Source: Table 5 · p. 16, §A.6 · p. 16

A.7 MECHANISM LADDER, SEMANTIC CONTROLS, AND S10 FACTORIAL

  • Full versus w/o CGRA adds +14.45 success points and cuts violation by −59.89 points; the representation interaction was not detected (p = 0.323).Random targets nearly match handcrafted targets when CGRA is active, while the latent head has substantially worse compliance; grounding supplies the auditable feasibility interface.Source: §A.7 · pp. 16–18, Table 9 · p. 17

A.8 HIGH-PRECISION TOPOLOGY EVALUATION

  • Across seven topologies, VERA exceeds MAPPO by 24.33–30.02 points, significantly after Holm correction on all seven.VERA–AB-MAPPO-R differences are directionally positive on all seven topologies but none is Holm-significant.Source: Table 10 · p. 18, §A.8 · p. 18

A.9 CROSS-TOPOLOGY SIGNED-MARGIN CALIBRATION

  • Across four shifted topologies, negative-margin bins had 100% violation, the boundary bin 52.4–86.7%, and positive bins 0%.VFR error is largest in the most negative region and decreases overall toward positive margins, though not at every adjacent bin.Source: Table 11 · p. 18, §A.9 · p. 18, Figure 8 · p. 19

A.10 VMAS TRANSFER AND NORMALIZED OOD AUDIT

  • 19.88 points separate Full from the no-VFR/no-CGRA backbone in VMAS; Latent-5D has the highest goal rate but also the highest collision rate in the OOD audit.The OOD audit reuses trained checkpoints and covers five new seeds, so it is separate from S10 training claims.Source: Table 12 · p. 19, §A.10 · pp. 19–20, Table 13 · p. 20

A.11 RESOURCE-ALLOCATION AND FORCE/CONTACT FAILURES

  • In resource allocation, CGRA adds +13.74–+14.20 success points but also +94.30–+98.57 violation points, with no detected representation interaction.All tested stabilizers passed SAGIN gates but failed in resource allocation and force/contact; five collapses also occurred among 20 CGRA-absent traces.Source: Table 14 · p. 20, §A.11 · p. 20

A.12 INFERENCE DIAGNOSTICS, SCALE, AND DEPLOYMENT COST; A.13 ARCHIVE DEPTH AND EXPERIMENT MAP

  • From 10 to 40 users, VERA success is 53.6/53.8/50.1%, versus 37.6/34.9/26.8% for AB-MAPPO and 34.0/32.1/35.7% for MAPPO.CPU actor steps cost 0.939 ± 0.106 ms for VERA versus 0.913 ± 0.086 ms for MAPPO; the inference-pathway test is diagnostic, not a retrained bottleneck comparison. The archive records 48 manifest-listed files passing SHA-256 verification.Source: §A.12 · p. 22, §A.13 · pp. 22–23
Loading 2609.38889v1…