7.2Learning-based Spatial Reasoning

Relational Aggregation over Latent Objects. The most direct approach treats a set of feature vectors as latent “objects” and learns to aggregate their interactions. Relation Networks (RN) [1349] score every pair: given objects $O=\{o_{1},\dots,o_{n}\}$ (e.g., , feature vectors from spatial regions of a CNN map) and an optional query $q$,

where $g_{\theta}$ produces a query-conditioned relation embedding for each pair and $f_{\phi}$ maps the sum to the task output. Considering all pairs forces the network to learn pairwise spatial and semantic relations, at $O(n^{2})$ cost in the number of objects. Graph neural networks and latent scene graphs generalize this from a complete graph to a learned, sparser topology, with proposals or feature regions as nodes and learned edges as spatial dependencies; iterative message passing for scene-graph generation [798] alternates between refining node features and updating relation embeddings, learning the topology end-to-end. Such models are the clearest semi-explicit case in this subsection: the graph is inspectable and often trained with relation annotations (e.g., , from Visual Genome), yet the intermediate relational representation is learned rather than specified by a program, and its quality is bounded by the upstream proposal stage.

Spatial Attention and Multi-Scale Feature Fusion. A second family controls where and how strongly the model attends across the spatial layout, and fuses evidence across scales, rather than scoring all pairs. CNN spatial attention weights locations in a feature grid, from the hard and soft attention of Xu et al. [1350] for captioning and grounded VQA [1351] to SCA-CNN’s joint spatial and channel attention [1352]; vision transformers make relating image parts intrinsic through self-attention over patches [142], with locality-aware variants (Swin [469], PVT [1353], Twins [1354]) trading global receptive field for cost; and Feature Pyramid Networks [597] add a top-down pathway so that a relation coupling a fine object with a coarse region (a car “on” a street) can be read from one map. These designs are representation backbones that preserve and aggregate spatial information for the reasoning built on top of them, not reasoning modules in themselves.

Conditional Feature Modulation. A third family conditions one representation on another rather than aggregating or attending. In FiLM (Feature-wise Linear Modulation) [1355], a conditioning vector (e.g., , an encoded query or global context) predicts affine parameters $(\gamma,\beta)$ that are applied feature-wise to a target map, so the same backbone can be steered per task. For a query like “What is to the left of the green cube?”, a FiLM layer can learn to amplify features to the left of regions identified as the green cube, making reasoning adaptive and context-dependent.

Geometry-Aware Inductive Biases. A fourth family bakes geometric regularities into the architecture, trading data-driven flexibility for sample efficiency where the relevant geometry is known. Capsule Networks [1356] replace scalar activations with vector-valued capsules whose orientation encodes instantiation parameters (pose, deformation) and whose magnitude encodes presence; dynamic routing decides how lower-level capsules compose into higher-level ones by agreement in predicted pose, a stronger part-whole bias than translation-only convolution, though capsules have been hard to scale beyond small digit and shape datasets. Equivariant and steerable convolutions [1357], which commute with a chosen transformation group, are the subject of §7.2.3; both share the cost that the symmetry must be chosen in advance.

Structured Recurrent Reasoning Architectures. This family imposes a step-wise reasoning structure in the architecture itself, so the model is fully differentiable and trained end-to-end from input–output pairs while still exposing a step-by-step trace. The Memory, Attention, and Composition (MAC) network [1360] chains $p$ recurrent cells, each of which attends to the question to choose the operation for the current step (control unit), extracts the relevant visual information by spatial attention guided by that control signal (read unit), and integrates it into a reasoning state passed to the next cell (write unit); the attention maps of successive read units provide a transparent trace of where the model is looking, without a rigid symbolic program. MAC is thus a boundary case: explicit at the level of reasoning dynamics, implicit at the level of spatial representation, since the operations run over dense feature maps rather than named objects or relations. Because the spatial logic stays in the learned weights, it is prone to statistical shortcuts (if “red spheres” co-occur with “cubes” in training, the model may learn that correlation rather than “left of”), and soft attention maps are often diffuse, so “to the left” bleeds into irrelevant regions in cluttered scenes.

Structured Scene Representations. A related line strengthens the structural prior on the reasoning substrate. Where MAC reasons over a soft grid of features, the Neural State Machine (NSM) [1361] reasons over a discrete semantic scene graph and simulates a finite automaton over it: a concept-detection module (Mask R-CNN) identifies entities, each node $v_{i}$ is initialized with semantic properties over a learned concept vocabulary, each edge $e_{ij}$ carries a distribution over spatial and semantic relation types (left of, behind, on top of, holding), and the query is answered by sequentially traversing nodes along valid transitions. More broadly, scene graphs act as a generic structured substrate: a downstream reasoner can traverse the graph as a hard environment (the NSM stance), attend over it as a soft relational prior, or search it for graph-based question answering, in each case obtaining an inspectable cut-point between perception and reasoning. The price is that reasoning quality becomes tightly coupled to object detection, attribute grounding, and relation prediction, a dependency we return to in the challenges.

Modular and Program-Based Reasoning. A third family translates the query itself into an executable program, and its members differ mainly in the nature of the executor. The Neural Module Network (NMN) [1362] is the canonical neural-executor instance: an external semantic parser converts a question such as “What color is the llama?” into a layout, e.g., , classify[color](attend[llama]), whose slots are instantiated by distinct learnable modules (attention, re-attention, classification, combination, measurement) trained jointly to maximize the likelihood of the gold answer. Because NMN relies on an off-the-shelf parser, IEP [1363] replaces it with a sequence-to-sequence program generator that emits the program as a sequence of functions, trained jointly with the execution modules via REINFORCE [1367] or by maximizing answer likelihood over a distribution of programs. Moving further toward symbols, Neuro-Symbolic VQA (NS-VQA) [1364] adopts a symbolic executor: a scene parser turns the image into a symbolic table, after which the program reduces to deterministic functional operators, yielding fully interpretable execution at the cost of a near-perfect-perception assumption. The Neuro-Symbolic Concept Learner (NS-CL) [347] occupies the middle ground with a quasi-symbolic executor: a neural perception module produces object-centric representations and a semantic parser emits symbolic programs, but the executor relaxes discrete operations such as filtering and relating into differentiable ones, so the whole system trains end-to-end from answers alone.

LLM-Generated Visual Programs. The most active recent extension lets a large language model emit the program directly, replacing the seq2seq parser of IEP or the hand-crafted parser of NMN with a tool-based executor. ViperGPT [1131] and VisProg [1365] pair a frozen LLM with a Python-style API of vision tools (detectors, captioners, attribute classifiers) that the generated code invokes, making the approach compositional and zero-shot without per-task training. Code-as-Policies [1366] pushes the same program-synthesis paradigm into embodied control, treating the LLM-emitted program as a closed-loop policy over perception and actuation primitives; it is included here as an embodied extension of the paradigm rather than as a VQA method. The interpretability gain is real, since the emitted code is human-readable, but these systems re-inherit the brittleness of the underlying LLM (hallucinated API calls, ungrounded tool routing) as a failure mode the earlier hand-coded DSLs were designed to avoid.

Unifying View: Parser, Representation, Executor, and Supervision. The four families are points in a shared design space with four axes. The parser that maps a query to structure may be hand-built (NMN), learned end-to-end (IEP, NS-CL), or a frozen LLM (ViperGPT, VisProg); the representation over which reasoning runs may be a dense feature map (MAC), an object-centric scene graph (NSM, and the scene-graph-generation literature [798] supervised at scale by Visual Genome [796]), or a symbolic scene table (NS-VQA); the executor may be neural, symbolic, quasi-symbolic, or a code interpreter; and the supervision may be answer-only, program-supervised, or, in tool-based systems, augmented with execution traces and tool feedback. The inspectable structure between perception and answer is the common thread: it provides a natural cut-point at which symbolic and learned components can be swapped without retraining the rest of the stack, and the same four axes reappear in the foundation-model reasoners of §7.3.

Beyond VQA: 3D, Temporal, and Embodied Extensions. The same design pattern extends beyond static images: referring-expression grounding has been lifted from 2D images to 3D scenes [374], where object-centric and spatial-relation graphs supply the substrate for reasoning about support, containment, proximity, and navigability, and in video and embodied settings the intermediate structure becomes a temporal scene graph or a task plan that links perception to action (§7.3, Part IV). These extensions also expose the central limitation of current explicit methods: most available program primitives and graph predicates are still designed for static 2D relations, whereas viewpoint change, object permanence, physical interaction, and multi-step navigation need 3D, temporal, and causal operators.

Invariance by Pooling and Augmentation. The baseline strategies work without changing the architecture. Augmenting the training set with rotated, flipped, or scaled copies pushes a standard CNN toward assigning the same label to all variants, but buys only an approximate invariance and requires examples of every transformation to be tolerated; global average pooling [1371] at the end of a feature extractor discards the “where” of each feature and keeps only its presence, which is the main reason classification CNNs are robust to translation. Neither guarantees invariance to anything beyond translation.

Active Alignment with Spatial Transformer Networks. Rather than ignoring transformations, a Spatial Transformer Network (STN) [1368] learns to undo them: a small localization network regresses the parameters of an affine transformation that it predicts will bring the object into a canonical pose, a grid generator turns these parameters into a sampling grid, and a differentiable sampler produces the rectified feature map, so the localization network is trained by backpropagation from the task loss alone. The module can be inserted at any point in a network and acts as learned attentional alignment, normalizing a region of interest for the layers downstream; the invariance it provides is learned, not guaranteed.

Permutation Invariance over Point Sets. A separate symmetry arises when the input is an unordered set rather than a grid: the model must be invariant to the ordering of its elements. DeepSets [1372] shows that any permutation-invariant function over a set can be written as $f(X)=\phi\!\left(\sum_{x\in X}\psi(x)\right)$ for suitable $\phi$ and $\psi$, encode each element independently, sum, then decode, which turns set-level invariance from an ad-hoc choice into a constructive recipe and makes explicit which aggregators preserve invariance and which silently break it; the same framework yields permutation-equivariant layers for per-element outputs (per-point labels, per-atom properties). PointNet [132] is the canonical instance on raw point clouds, a shared multilayer perceptron per point followed by symmetric max pooling, and PointNet++ [270] adds locality by repeatedly grouping points within a metric ball and applying the same shared-MLP-plus-pool pattern at multiple scales. Permutation invariance comes for free in this family; rigid-motion invariance does not, which is the gap the equivariant methods below address.

From Translation to Group Equivariance. A standard convolution is translation-equivariant (shifting the image shifts the feature map) but not rotation-equivariant: rotating the input changes the feature map unpredictably. Group equivariant convolutions (G-CNNs) [1357] generalize the operation to a larger discrete group such as the four planar rotations: a single filter is rotated into a set of transformed copies, all are correlated with the input, and the feature map gains an orientation dimension, so a feature that reads “edge at $45^{\circ}$” becomes “edge at $135^{\circ}$” at the corresponding location when the input rotates by $90^{\circ}$. Equivariance is therefore not learned but imposed, layer by layer.

Steerable Filters and Equivariance in Every Layer. Steerable CNNs [1369] replace the group-indexed filter copies by filters expressed in a steerable basis, so that the response at a transformed orientation follows by linear combination of basis responses rather than by explicit rotation; the general E(2) framework [1373] extends this to continuous rotations and reflections with circular-harmonic bases under one configurable interface, and library efforts such as e3nn [1374] do the same for E(3) / SE(3). Full equivariance also requires that pooling, nonlinearities, and normalization respect the group: a standard ReLU applied to the components of a geometric vector breaks it (activations are therefore applied to invariant quantities such as the vector norm), and channel-wise batch normalization breaks the coupling between channels, which motivates equivariant normalization [1375]. The guarantee is only as strong as its weakest layer; one non-equivariant operation anywhere in the stack silently undoes the symmetry the rest preserve.

Equivariant Attention and Continuous SE(3) Symmetries. A more recent line lifts the treatment from convolutions to attention, with queries, keys, and values that transform predictably under a chosen Lie group. The SE(3)-Transformer [379] is the canonical instance, building each attention layer from tensor-field representations so that rotating the input scene rotates the whole stack of outputs consistently; Tensor Field Networks [1370] use the same machinery without an attention head and have been especially influential in molecular modeling, where SE(3) equivariance is a problem constraint rather than an optional bias. Both parameterize the kernel as a combination of spherical-harmonic basis functions, which is computationally heavy, so a parallel line pursues lighter equivariance: E($n$)-equivariant graph networks (EGNN) [1376] achieve E($n$)-equivariant message passing from relative distances and coordinate updates alone, and Vector Neurons [380] lift scalar point-cloud features to 3D vectors, obtaining SO(3) equivariance as a drop-in primitive, each trading representational richness for scalability. With the libraries above, trying equivariance on a new task now costs about as much engineering as a convolutional baseline; the choice of group still has to be made by the designer.

QP and Convex Optimization Layers. Amos and Kolter [1384] introduced OptNet, which treats the solution of a quadratic program as a layer: the forward pass solves

subject to affine constraints whose matrices can depend on previous network outputs, and the backward pass differentiates the KKT optimality conditions exactly, with a custom GPU interior-point solver that handles many small QPs in parallel and reuses its factorization for the backward pass. OptNet learned to solve Sudoku from data where conventional architectures could not, which showed that implicit layers can handle discrete or constrained reasoning problems. Agrawal et al. [1387] generalized the idea to any disciplined convex program: CVXPY Layers [1388] canonicalize the problem into conic form, solve it, and differentiate through the cone program’s optimality conditions, so a constrained least-squares, a constrained logistic regression, or a robot-motion-limit constraint can be inserted as a layer without deriving gradients by hand.

Implicit Differentiation. All of these layers share one mechanism. Rather than unrolling an iterative solver, one differentiates the closed-form optimality (KKT) conditions, which for a convex program comprise primal feasibility, dual feasibility, complementarity, and stationarity [1392]; differentiating this system and solving one linear system yields $\frac{\partial z^{\star}}{\partial\theta}$ exactly, without back-propagating through solver iterations. Where OptNet hand-codes this backward pass, Deep Declarative Networks [1389] apply automatic differentiation to the KKT system itself. The same principle extends to root-finding, fixed-point, and equilibrium layers via the implicit function theorem; deep equilibrium models [1393] treat an entire weight-tied network as a single fixed-point layer differentiated this way, and differentiable physics engines and planners propagate gradients through the equilibrium or optimum conditions of a physical system.

Differentiable Geometry Solvers. A subclass is tailored to geometric problems that are themselves argmin problems, typically minimizing a reprojection error: camera pose from 2D–3D correspondences, bundle adjustment, inverse kinematics. Campbell et al. [1390] introduced a differentiable blind PnP solver that estimates 3D pose as a layer; Teed and Deng [95] built a differentiable bundle-adjustment module into a SLAM system, solving for camera poses and 3D points by iterative optimization while letting gradients flow; EPro-PnP [744] recasts PnP as a probabilistic layer with a learnable distribution over poses; and Theseus [1394] provides a reusable library for differentiable nonlinear least squares (Gauss–Newton, Levenberg–Marquardt) that underlies bundle adjustment, pose-graph optimization, and inverse kinematics. These layers keep the domain-specific optimizer but make it differentiable, so the whole vision or robotics system trains end-to-end while the geometry stays correct and constrained, for instance so that estimated object poses agree across views; Gould et al. [1389] refer to such constructs as declarative nodes and demonstrate them on visual Sudoku and robust geometry estimation.

Differentiable Logic Layers. Beyond continuous optimization, the same construction extends to symbolic reasoning. SATNet [1385] integrates a differentiable satisfiability solver as a layer: the forward pass solves a relaxed SAT problem (a quadratic unconstrained binary optimization) to produce assignments consistent with logical constraints, and the backward pass differentiates implicitly through the solver’s fixed-point conditions; Shindo et al. [1391] extend differentiable logic programs to abstract visual reasoning benchmarks such as Raven’s Progressive Matrices. These layers belong to the same class of constraint-based implicit modules as the QP and convex layers, specialized to combinatorial and relational dependencies.

Value-Based RL. Value-based methods learn a value function that estimates the expected cumulative return of acting under a policy $\pi$. The optimal state-action value function is

where $\gamma\in(0,1)$ is the discount factor, and it satisfies the Bellman equation: if the optimal values $Q^{*}(s^{\prime},a^{\prime})$ of the next state are known for every action $a^{\prime}$, the best action now is the one that maximizes $r+\gamma Q^{*}(s^{\prime},a^{\prime})$,

Iterating this identity as an update, $Q_{i+1}(s,a)=\mathbb{E}_{s^{\prime}\sim\mathcal{E}}[r+\gamma\;\max_{a^{\prime}}\;Q_{i}(s^{\prime},a^{\prime})|s,a]$, converges to $Q^{*}$, but a table of values indexed by every state is useless in high-dimensional observation spaces, so a function approximator $Q(s,a;\theta)\approx Q^{*}(s,a)$ is learned instead, a neural network in the deep-RL setting (a Q-network). Training minimizes a sequence of regression losses whose target is the bootstrapped Bellman estimate,

with $y_{i}=\mathbb{E}_{s^{\prime}\sim\mathcal{E}}[r+\gamma\;\max_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta_{i-1})|s,a]$ computed from the previous parameters $\theta_{i-1}$, held fixed, and $\rho(s,a)$ the distribution of visited state–action pairs; the greedy policy $\pi(s;\theta)=\arg\max_{a}Q(s,a;\theta)$ then follows from the learned values.

Deep Q-networks (DQN) [1395] made this scale to high-dimensional observations with experience replay and a slowly updated target network; their convergence is analyzed theoretically by Fan et al. [1396], and Figure 7.14 shows the resulting workflow. Beyond control, value-based RL drives active visual perception: Caicedo and Lazebnik [1397] cast object localization as a sequential decision process in which a Q-network iteratively transforms an attention window until it tightly bounds the target, turning detection into a learned spatial search policy, a formulation since applied to active detection, visual search, and region selection for fine-grained recognition, where the agent learns where to look rather than scanning exhaustively. In spatial domains the limitation of vanilla DQN is that any planning behavior must be learned implicitly from data, which generalizes poorly to novel layouts, so several works embed planning structure in the value estimate itself. Value Iteration Networks (VIN) [1398] unroll Bellman updates as convolutions over a spatial grid, a differentiable approximation of value iteration; Gated Path Planning Networks (GPPN) [1399] replace the recurrence with gated units to improve optimization stability and long-range dependencies; and under partial observability QMDP-Net [1400] integrates belief updates and approximate POMDP planning (QMDP) [1401] into one differentiable network. In each case the learned value function is constrained to follow spatially structured dynamic programming rather than arbitrary function approximation.

Policy-Based RL. Policy-based methods [1367, 1402] parameterize a policy $\pi_{\theta}(a|s)$ directly and maximize expected return,

by gradient ascent on

where $R_{t}=\sum_{k=t}^{\infty}\gamma^{\,k-t}r_{k}$ is the return from time-step $t$ (Figure 7.15). Optimizing action distributions directly suits spatial decision problems in which exploration and long-horizon credit assignment are central [1403], and policy gradients train embodied agents to actively gather visual evidence: Embodied Question Answering [1404] optimizes a navigation policy so that the agent moves to vantage points from which it can answer questions about a 3D scene. The spatial competence, however, comes from the architecture rather than the objective; policy-gradient agents generalize across layouts when the policy carries a learned map [1405], a grounded spatial representation [1406], memory, or a relational encoder [1407].

Actor-Critic RL. Actor–critic methods [1408] combine the two by jointly learning a policy $\pi_{\theta}(a|s)$ (the actor, which controls behavior) and a value function $V_{\phi}(s)$ (the critic, which scores the actions taken), as in Figure 7.16. The critic provides a low-variance estimate of the advantage,

or, when a Q-function is learned as well, $A_{\phi}(s_{t},a_{t})=Q_{\phi}(s_{t},a_{t})-V_{\phi}(s_{t})$, and the advantage replaces the raw return $R_{t}$ in the policy-gradient update. The asynchronous advantage actor-critic (A3C) [1409] made this stable and scalable and became a standard backbone for embodied navigation and spatial control: target-driven visual navigation [1410] conditions an A3C agent on an image of the goal and reaches semantically specified targets in unseen indoor scenes, and Neural SLAM [1411] gives an A3C agent a differentiable map memory. The separation between actor and critic matches the structure of spatial tasks, with the actor responsible for geometry-aware decisions and the critic supplying global, long-horizon value signals, which is why actor–critic methods dominate navigation benchmarks that require memory, planning, and partial observability [1412].

PPO-Style Policy Optimization. Proximal Policy Optimization (PPO) [1413] is an actor–critic algorithm that stabilizes training by constraining each policy update through a clipped surrogate objective,

where $r_{t}(\theta)$ is the probability ratio between the new and old policies (Figure 7.17). Its robustness and sample efficiency made PPO the de facto backbone for training agents in large-scale photorealistic 3D simulators such as Gibson [93] and Matterport3D [340], and in manipulation suites such as panda-gym¹. Scaled to 2.5 billion frames with DD-PPO [1414], it essentially solves PointGoal navigation on Habitat (99.7% success and 0.97 SPL on Gibson validation), and the same backbone underpins vision-and-language navigation [1415], object-goal navigation [1416], audio-visual navigation [46], and planning over uncertain topological maps [1417].

Preference-Based Policy Optimization (DPO). Preference-based learning replaces the reward signal with comparisons. Direct Preference Optimization (DPO) [1418] learns a policy from preference pairs without an explicit reward model or online rollouts (Figure 7.18): for two completions $(y_{1},y_{2})$ of an input $x$, a labeler marks the preferred one, $y_{w}\succ y_{l}\mid x$, and by expressing the implied reward of a Bradley–Terry preference model [1419] through the optimal policy itself, DPO collapses the reward-learning-then-RL pipeline into a single maximum-likelihood objective on $\pi_{\theta}$:

where $\pi_{\text{ref}}$ is a fixed reference policy and $\beta$ controls the deviation from it. Developed for language-model alignment, DPO applies to spatial reasoning whenever supervision takes the form of trajectory preferences, plan rankings, or human judgments of spatial behavior [1420, 1421, 1422], which arise naturally in navigation, manipulation, and interactive tasks where dense rewards are hard to specify.

Group-Based Policy Optimization (GRPO). Group Relative Policy Optimization (GRPO) [1423] removes the learned critic and replaces it with a group-relative baseline computed from multiple sampled trajectories (Figure 7.19). For each question $q$, it samples a group of outputs $\{o_{1},o_{2},\cdots,o_{G}\}$ from the old policy $\pi_{\theta_{\text{old}}}$ and optimizes $\pi_{\theta}$ by maximizing

where $\epsilon$ and $\beta$ are hyperparameters and the advantage $A_{i}$ is computed from the rewards $\mathbf{r}=\{r_{1},\dots,r_{G}\}$ that a reward model assigns to the group, normalized within the group only:

Eliminating the value network reduces memory and stabilizes training. Although explored first for language models, the formulation transfers to spatial decision-making wherever several candidate plans or trajectories can be scored against one another, and it has become the standard recipe for reinforcement fine-tuning of spatial vision–language models on visual reasoning, navigation, multi-step assembly, and video spatial reasoning [1424, 1425, 1426, 1427].

Architectural Spatial Inductive Biases. The backbones above are domain-agnostic; what makes a policy spatial is the prior $S$ in its architecture, and three families recur across the examples already met. Map-based representations give the agent an explicit allocentric memory: cognitive maps [1405] and Neural Map [1428] write observations into a spatially indexed latent grid, while Neural SLAM [1411] and Active Neural SLAM [1429] couple differentiable mapping with a hierarchical exploration policy. Differentiable planning modules embed dynamic programming in the network, as in the VIN / GPPN / QMDP-Net line discussed under value-based RL, or learn a value-equivalent model and plan by lookahead search, as in MuZero [148]. Relational abstractions replace flat feature maps with object- or graph-structured state, letting attention or message passing capture relations that transfer across layouts [1407]. In each case the RL objective is unchanged; the spatial competence comes from the prior, which is why these architectures generalize across geometries where unstructured policies overfit.

Classical Paradigms. Before learning, coordination relied on potential fields, formation keeping via graph Laplacians, and optimal multi-agent pathfinding with conflict-based search [1228], treated in §7.1.3; these methods offer strong guarantees but struggle with perception noise, combinatorial scaling, and model mismatch in open worlds.

CTDE and Value Decomposition. Two lines made CTDE work. Centralized critics resolve credit assignment and non-stationarity while keeping execution decentralized: COMA uses a counterfactual baseline computed by a centralized critic for decentralized actors [1432], and MADDPG extends deterministic policy gradients with agent-specific centralized critics [1431]. Value factorization instead decomposes the joint value: VDN sums per-agent utilities to approximate $Q_{\text{tot}}$ for cooperative tasks [1437], and QMIX generalizes the sum to a monotonic mixing network that preserves individual-global argmax consistency with more representational capacity [1433]. These approaches made MARL scalable on SMAC [1435], where the value-decomposition line dominated the early cooperative leaderboard while the centralized-critic methods anchored other regimes (MADDPG on the particle environments, COMA on StarCraft micromanagement); the monotonic constraint and homogeneous-role assumptions limit expressivity, as the challenges below detail.

Graph Neural Networks for Coordination. Graph-based MARL encodes agents as nodes and interactions as edges, and message passing or attention over the neighborhood learns role-specialized coordination [1438]; this family improves sample efficiency and robustness under topology changes and communication limits, and MAGEC [1434] shows resilience to agent attrition and communication disturbance in multi-robot patrol by combining GNN encoders with PPO-style multi-agent optimization. Graph MARL targets a different axis from the leaderboard methods, robustness to topology disturbances rather than headline return, which exposes a gap between coordination-quality benchmarks (SMAC, MPE) and deployment-quality ones (multi-robot patrol, driving forecasting on WOMD and nuScenes) that standardized suites still under-represent.

Sequence Models and Transformers. Casting MARL as sequence modeling applies attention over multi-entity, multi-horizon contexts: the Multi-Agent Transformer [1439] maps the sequence of agents’ observations to a sequence of actions with an encoder–decoder, using the multi-agent advantage decomposition to turn joint policy search into sequential decisions with linear complexity in the number of agents. Transformer controllers, often hybridized with graph layers, address long-range temporal and relational dependencies, unify perception and control, and support offline RL through trajectory modeling; learned memory alleviates partial observability, while quadratic attention and credit assignment over long horizons remain open.

Credit Assignment under Partial Observability and Long Horizons. The decentralized-execution constraint of the Dec-POMDP forces each agent to act on its own history $h^{i}_{t}$ alone, so relating a local action $a^{i}_{t}$ to a delayed team-level reward $r_{T}$ across a horizon $T$ produces an irreducibly noisy policy gradient. Counterfactual baselines such as COMA [1432] marginalize over alternative actions of agent $i$ while holding the rest of $\mathbf{a}_{t}$ fixed and reduce gradient variance substantially, but they still rely on a centralized critic that, at scale, becomes a moving target for itself. Value decomposition (VDN, QMIX) [1437, 1433] side-steps the centralized critic by factorizing $Q_{\mathrm{tot}}$ across agents, yet the monotonicity constraint $\partial Q_{\mathrm{tot}}/\partial Q_{i}\geq 0$ that guarantees decentralized argmax consistency cannot represent strictly non-monotonic cooperation games, a representational ceiling made explicit by the later non-monotonic factorizations QTRAN, weighted QMIX, and QPLEX, and visible on cooperative matrix games and SMAC’s hardest scenarios [1442, 1443, 1444, 1435]. Under sparse reward shaping, policies trained against these signals tend to chase short-term spatial cues (“move toward the closest enemy”, “follow the nearest teammate”) rather than team-level objectives.

Scaling Laws of Joint Reasoning and Communication. Sequence-model multi-agent Transformers and dense graph message passing both incur $\mathcal{O}(n^{2})$ complexity in the number of agents, plus additional quadratic terms across temporal contexts, which collides with the real-time latency budgets of multi-robot [1434] and autonomous-driving deployments [218, 445]. Sparse, learned interaction graphs are the natural mitigation, but they introduce their own credit-assignment difficulty: the edges $\mathcal{E}_{t}$ are themselves part of the learned policy, and gradients flowing through hard edge selection are biased or high-variance. Communication bandwidth is a related gap: in the formulation above any message $m^{i}_{t}$ should carry a cost that appears in $R$, but the standard simulators (SMAC [1435], MPE [1431], GRF [1436]) idealize communication as free and noiseless, leaving little benchmark surface against which to push bandwidth-aware coordination.

Non-stationarity, Heterogeneous Roles, and Partner Generalization. Even in fully cooperative settings, intra-team policies co-evolve, so from the perspective of any single agent the environment is non-stationary [1431], the failure mode the centralized-critic family of MADDPG / COMA [1431, 1432] was introduced to address. The problem sharpens when teammates are heterogeneous, may drop out (the patrol-with-attrition setting of MAGEC [1434]), or are drawn from an unseen partner distribution at evaluation time, the zero-shot coordination problem. Persistent open-world simulators such as Neural MMO [1440, 1441] push along this axis with procedurally generated maps and long-horizon survival, but standardized protocols for partner generalization and role specialization remain immature compared with the single-agent supervised benchmarks of §7.2.1 and §7.2.3.

Ambiguous Spatial Semantics and Sim-to-Real Transfer. The egocentric observations $o^{i}_{t}$ that drive decentralized policies are partial and noisy: occluded teammates, uncertain affordances, and depth-discontinuity-induced map errors distort both prediction and control. Driving benchmarks such as WOMD [218] and nuScenes [445] expose the prediction side of this gap, but the closed-loop control side (whether the same forecasts survive when an agent acts on its own predictions) is comparatively under-evaluated. The sim-to-real gap on multi-robot systems is wider still: perception noise and actuation latency interact non-linearly with the coordination signal in ways that simulators rarely model, and resilience under realistic communication disturbance and agent attrition has only recently received first-class benchmark coverage [1434].

Three routes follow from these axes. Topology-aware sparse interaction (learned edges, hierarchical groupings, or attention masks parameterized by $\mathcal{G}_{t}$) preserves long-range coordination while scaling sub-quadratically, with the GNN+PPO patrol architecture of MAGEC [1434] as an early instantiation and graph encoders combined with sequence-model attention over short temporal windows as the natural next step. The monotonicity ceiling of VDN / QMIX [1437, 1433] can be relaxed by attention-weighted mixers, weighted projection schemes, or dueling-style decompositions that keep individual-global argmax consistency while admitting non-monotonic cooperation, so that COMA-style counterfactual credit assignment [1432] no longer depends on a joint-action critic that becomes the bottleneck. And explicit objectives for agent attrition and communication disturbance [1434], paired with failure-centric curricula and hooks for formal verification, move resilience from an emergent property of training to a first-class objective, decisive in safety-critical multi-robot and driving deployments [218, 445] where worst-case performance dominates the deployment decision; closed-loop evaluation suites that jointly report team return, safety, calibration, and latency are the missing measurement substrate, and the benchmarks for partner generalization, bandwidth-aware coordination, and sim-to-real transfer that would play the role SMAC and GRF played for CTDE are still under construction.