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

arXiv: https://arxiv.org/abs/2609.38889 · HTML: https://mlsanity.com/paper/2609.38889/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 42 of its 54 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 30 of 42)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Concept Bottleneck Models](https://mlsanity.com/paper/2007.04612/) (2020)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Safe RLHF: Safe Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2310.12773/) (2023)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11251/) (2021)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Multi-Agent Reinforcement Learning is a Sequence Modeling Problem](https://mlsanity.com/paper/2205.14953/) (2022)
- [Safety-Gymnasium: A Unified Safe Reinforcement Learning Benchmark](https://mlsanity.com/paper/2310.12567/) (2023)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [Invariant Causal Prediction for Block MDPs](https://mlsanity.com/paper/2003.06016/) (2020)
- [Probabilistic Concept Bottleneck Models](https://mlsanity.com/paper/2306.01574/) (2023)
- [Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks](https://mlsanity.com/paper/1909.01865/) (2019)
- [OmniSafe: An Infrastructure for Accelerating Safe Reinforcement Learning Research](https://mlsanity.com/paper/2305.09304/) (2023)
- [Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation](https://mlsanity.com/paper/2202.06558/) (2022)
- [Heterogeneous-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.09870/) (2023)
- [VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning](https://mlsanity.com/paper/2207.03530/) (2022)
- [Causal Dynamics Learning for Task-Independent State Abstraction](https://mlsanity.com/paper/2206.13452/) (2022)
- [Constrained Update Projection Approach to Safe Policy Optimization](https://mlsanity.com/paper/2209.07089/) (2022)
- [Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2204.13060/) (2022)
- [Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.07505/) (2022)

## Abstract (arXiv)

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.