Cutting Weak Influence: Graph-Cut Coordination Blocks for Networked MDPs

When many agents share a network (sensors, radios, or the nodes of an epidemic), planning for all of them jointly runs into state space explosion: the joint state is the product of every agent's local state, so it grows exponentially with the number of agents. The usual remedy is to let each agent coordinate only with a small group and plan for that group exactly. How that group is chosen matters a great deal. Recent theory shows that coordinating within each agent's $m$-hop neighborhood is enough when influence between agents is weak. That rule ignores how strong each link actually is, though, and constructing the resulting policies still requires the global optimal value function. That requirement is exactly what one cannot compute.

We propose to choose coordination groups by graph-cut energy minimization, the combinatorial labeling machinery from computer vision that assigns a discrete label to every site of a graph by trading off local costs against penalties on neighboring sites that disagree. Here the sites are agents, the labels are coordination blocks, and the penalty for separating two agents is a measured influence weight. The hypothesis is that the loss from planning in blocks is controlled by the total influence that crosses block boundaries, not by the neighborhood radius. If so, the right partition is a minimum-cut problem. Each block is small enough to solve exactly, and outside agents are modeled by their marginal behavior, so the method never touches the global value function.

Core Claim

Consider a cooperative networked MDP (Markov decision process) whose reward is a sum of local agent rewards and whose influence structure is summarized by the pairwise influence matrix $C$ of Local Policies for Graph-Structured Markov Decision Processes. Entry $C_{ij}$ bounds, in total variation, how much agent $j$'s state can change agent $i$'s transition. For a block assignment $L=(l_1,\dots,l_n)$, we minimize

$$E(L)=\sum_{i\neq j} w_{ij}\,\mathbb{I}[l_i\neq l_j]+\sum_{l} c\,\mathbb{I}[\exists i: l_i=l],\qquad w_{ij}=C_{ij}\,\bar r_i ,$$

where $\bar r_i$ is the range of agent $i$'s local reward and $c$ is a per-block cost. The block size is capped at $b$, so each block MDP has at most $|S_0|^b$ states, with $|S_0|$ the local state count.

The theoretical target has two parts. First, the policy obtained by solving each block exactly, with outside agents replaced by their marginals, loses at most on the order of $\gamma E_{\text{cut}}(L)/(1-\gamma)^2$, where $E_{\text{cut}}$ is the first sum and $\gamma$ is the discount factor. This form comes from the simulation lemma: ignoring a cut neighbor perturbs agent $i$'s transitions by at most $C_{ij}$ per step. The additive reward then turns the per-agent errors into a sum over cut edges. Second, the Potts penalty $\mathbb{I}[l_i\neq l_j]$ is a metric. By What Energy Functions Can Be Minimized via Graph Cuts?, every binary move of α-expansion (the algorithm that repeatedly lets each site keep its label or switch to a fixed label α) is therefore regular, meaning it can be solved exactly as an s-t minimum cut. That gives polynomial-time moves with a known approximation factor.

Faizal et al.'s bound decays as $(\gamma\rho(C))^m$ in the neighborhood radius $m$, where $\rho(C)$ is the spectral radius of $C$. Ours is instead indexed by cut weight. On graphs with heterogeneous link strengths, such as a few strong clusters joined by weak bridges, a cut-optimized block of size $b$ should cross far less influence than an $m$-hop ball of the same size.

Relation to Prior Work

Faizal, Ozdaglar and Wainwright supply the influence matrix and the stability condition we reuse. They also motivate the proposal: their neighborhoods are distance-based, and they leave efficient construction of local policies open because existence is proved by projecting $Q^*$. We change both the neighborhood rule and the construction.

Two other lines of work define the endpoints of the design space. Gunduz et al. fully decouple energy-harvesting nodes into restless bandits and prove a myopic policy optimal in their setting. That corresponds to blocks of size one, and it is exact only when cross influence vanishes. Khodaian et al. document the exponential blow-up in exactly the networked-radio setting where intermediate block sizes should matter.

On the graph side, Comanici and Precup partition an MDP's state graph spectrally using bisimulation affinities. Their work is the closest use of graph partitioning for dimensionality, but it clusters states rather than agents, uses a continuous relaxation at cubic cost, and does not produce blocks with an error bound tied to cut weight. Matejek et al. show that lifted multicuts can handle large partitioning problems with attractive and repulsive edges. This constrains our design toward cut objectives that do not fix the number of parts, which our label cost provides.

The abstraction theory of Abel et al. and Abel frames the goal. Their three desiderata are small abstractions, bounded loss, and construction cheaper than solving the problem. Existing ε-threshold constructions fail the third because they need $Q^*$. Our construction needs only $C$, which can be estimated from local transition samples, and $\bar r_i$.

Research Program

The program has three parts.

The first is the bound. We will prove the cut-weight inequality for block policies that use marginal models of outside agents, and then check whether a second-order term is needed for strongly coupled blocks. We expect such a term to look like a Neumann series in the within-block influence, analogous to the Dobrushin condition $\gamma\rho(C)<1$.

The second is the solver. We will use α-expansion with label costs, and enforce the size cap $b$ through per-label Lagrangian unary penalties updated between sweeps. This cap is not graph-representable, so it is a heuristic, and we will report violations.

The third is construction. Each block MDP is solved by exact value iteration. Outside agents are replaced by stationary marginals under the current joint policy, and we iterate block best-responses until the policies stop changing. We will estimate $C$ from sampled local transitions and measure how estimation noise in $C$ degrades the chosen partition.

Baselines

The naive reference is fully independent control, with every agent in its own block and outside agents treated as marginals. This is the regime in which Gunduz et al. show decoupling can be optimal. It costs the least, and it sets the floor that any coordination has to beat.

The strongest existing method is the $m$-hop local policy of Faizal et al.. On small instances we will run it exactly as specified, projecting the true $Q^*$. On large instances $Q^*$ is unavailable, so we pair $m$-hop balls with our block solver. This isolates neighborhood choice from construction. For fairness, ball radius and our cap $b$ are set so that the largest block state space is identical, and wall-clock time is reported for both. No reported scalar result was found on Lacuna for the Binary Infection Model: the paper reports only that the Bellman residual decays sharply with $m$ and is negligible almost immediately on trees. We will therefore rerun it ourselves.

Beating it means lower true suboptimality at equal maximum block state count on at least the heterogeneous-weight graphs, with no loss on uniform trees.

A generic balanced partitioner serves as a further baseline: spectral clustering of the Laplacian of $C$, in the spirit of Comanici and Precup, given the same size cap. Two ablations isolate the key ingredients. The first runs our energy with unit weights on graph edges, which removes the influence weighting. The second uses random partitions with matched block sizes. All methods get the same block solver, the same number of best-response iterations, and the same tuning grid over $c$ or $m$.

Why not just…?

Why not just use $m$-hop balls, which already have a proof? On uniform-strength trees, balls may be near-optimal, and Faizal et al. report negligible error almost immediately there. Balls, however, spend the size budget on hop distance even when a neighbor's influence is tiny, and they miss strongly coupled agents that sit two hops away. The heterogeneous-graph experiments below are designed so that the two rules disagree. If balls match cut blocks on those graphs too, the cut-weight bound adds nothing practical, and we will report that.

Why not just run a standard graph partitioner on $C$? This is a real threat. If our weights are right, any good minimum-cut partitioner with a size constraint may do as well as α-expansion. We will accept that outcome. In that case the contribution becomes the objective, meaning the weights $C_{ij}\bar r_i$ and the bound that justifies them, together with the $Q^*$-free construction, not the particular solver. The spectral-partitioner baseline and the unit-weight ablation separate the two questions: whether the weights matter, and whether the combinatorial solver matters.

Why not just decouple fully and use index or myopic policies? Decoupling is optimal only when cross-agent influence vanishes or has special structure, as in Gunduz et al.. In epidemic spread, influence is by construction what drives outcomes. The independent baseline measures directly how much return coordination recovers as influence grows.

Proposed Experiments

We will use the Binary Infection Model on trees, loops and grids from Faizal et al. and add heterogeneous variants: clustered graphs with weak inter-cluster bridges, and graphs with log-normal edge strengths. We will also build a multi-node wireless queue and battery model following Khodaian et al. For ground truth we use instances with up to about 14 binary agents, where the joint MDP can be solved exactly. There we measure the true optimality gap and plot it against the predicted cut weight, which directly tests the bound's shape. At larger scales, from 50 to several hundred agents, we measure average discounted return and compute time relative to the baselines.

The decisive checks are three. First, the true gap must track $E_{\text{cut}}$ across partitions more closely than it tracks ball radius; we will quantify this with rank correlation over many random and optimized partitions of the same instance. Second, cut blocks must beat equal-budget balls on the heterogeneous graphs. Third, the advantage must survive when $C$ is estimated from a limited number of transition samples rather than given.