PaperlayerView exact revision on arXiv

Source-linked AI summary

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

Xiangwu Wang, Chengwei Cao, Hongyuan Tang

arXiv:2609.08366v1cs.MA

TL;DR

Persistent communication limits leave open which agents should retain a shared state channel throughout a rollout, since current proximity alone misses future interactions. RCSD uses reachability-based pair affinities to choose capacity-valid persistent teams and bound reward-deletion error. Its guarantees were not violated in the reported stochastic evaluations, while partition rankings varied across evaluation tiers.

  • Problem

    Under a hard persistent team-size limit, it remains unclear which agents should retain a shared state channel before planning.

    Source: §1 · p. 1

  • Method

    RCSD combines contact-time lower bounds and pair-reward envelopes into affinities for selecting capacity-valid persistent partitions and certifying reward deletion.

    Source: §1 · p. 1, §5 · p. 4

  • Results

    Across 384 exact four-agent partitions and 1,440 large-tier method evaluations, no deletion or regret bound was violated; exact-tier aggregate unrestricted regret was 21.6%, 24.1%, and 14.8% lower than Uniform, Distance, and Current, respectively.

    Source: §7 · p. 6

  • Takeaways & Limitations

    In the larger controller-library evaluation, paired intervals favored RCSD over Distance and Current, included zero for Uniform, and favored Envelope and Value-MIP over RCSD.

    Source: §7 · p. 6

    The policy-wise certificate requires an unchanged stationary Markov policy; reward-history-reactive controllers may not induce the same future actions after reward deletion.

    Source: §4 · p. 3

Abstract

from arXiv · show

Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.

1 Introduction

Persistent team membership is a deployment decision that cannot be made from current proximity or a static reward graph alone. RCSD uses reachability and reward bounds to select capacity-valid teams and certify the cost of deleting cross-team rewards during planning.

1 Introduction

  • Persistent teams must be chosen before planning, with at most L agents per team and no cross-team channel throughout the rollout.Team members share full state information; the partition remains fixed after the initial state.Source: §1 · p. 1
  • RCSD combines a lower bound on first contact with discounted pair-reward envelopes to bound the value at risk from any capacity-valid partition.RCSD-Exact minimizes this certificate to choose persistent subteams.Source: §1 · p. 1
  • A cut-affinity sum bounds unchanged stationary Markov policy value change, while a team-product cut-MDP optimum incurs at most 2B_P(x) regret against the centralized optimum.Both bounds are worst-case tight for signed rewards.Source: §1 · p. 1
  • The evaluation plan tests partition selectors on a controlled five-agent problem, checks stochastic two-dimensional settings, and measures partition construction up to 100 agents.The stochastic study separates unrestricted four-agent regret from controller-library regret at 8–20 agents.Source: §1 · p. 1

2 Related Work

Prior work studies sparse coordination, dynamic communication groups, and capacity-constrained coalition formation, but RCSD targets a fixed, rollout-persistent overlay selected before planning. Its distinctive element is a reachability-derived certificate for that deployment choice.

2 Related Work

  • Factorized and transition-independent MDP methods exploit local dynamics and sparse rewards, while LIMDPs model dynamically changing communication groups [6].RCSD instead selects an arbitrary capacity-valid overlay and holds it fixed during execution.Source: §2 · pp. 1–2
  • Learned communication and grouping methods [4] [10] [20] [21] [27] [31] do not provide RCSD’s a priori sufficient loss certificate under its physical model.RCSD also differs from Correlated Policy Optimization by enforcing block cardinality and certifying each feasible fixed partition before policy optimization.Source: §2 · p. 2
  • RCSD instantiates capacity-bounded edge-weight coalition formation [19, 26] with heterogeneous reachability-derived costs whose cut sum bounds distortion from deleting cross-team rewards.Its distinction is the initial-state, speed-limit delay and reward-envelope aggregation.Source: §2 · p. 2

3 Model and Capacity-Limited Overlay

The model is a finite discounted multi-agent MDP with factorized physical transitions and local and ordered-pair rewards. At the initial state, a dispatcher fixes capacity-limited teams whose planners share state only within each team.

3 Model and Capacity-Limited Overlay

  • The setting uses a finite discounted MDP with a joint state space formed from local agent states and factorized physical transitions.The discount factor satisfies 0 < gamma < 1.Source: §3 · p. 2
  • Each agent has a position in a common metric space, and every positive-probability local transition obeys an almost-sure displacement bound v_i.The bound is not merely an expected-motion constraint.Source: §3 · p. 2
  • Rewards comprise local and ordered pair terms, with pair rewards zero beyond a symmetric finite interaction range and bounded in magnitude by known envelopes.Underestimated speed, range, or reward bounds would void the certificate.Source: §3 · p. 2
  • The dispatcher announces a fixed partition once; each team has at most L agents, shares its joint state internally, and has no cross-team information channel.The cut MDP preserves the physical kernel while deleting exactly the cross-team pair rewards for planning; executed policies are evaluated in the original reward model.Source: §3 · p. 2

4 Reachability Certificate

RCSD bounds the effect of deleting cross-team rewards by combining a speed-certified period of zero pair reward with discounted reward envelopes. The resulting certificate applies to unchanged stationary Markov policies, while execution-regret guarantees require additional factorization and team-optimal planning conditions.

4 Reachability Certificate

  • The affinity aggregates both directed reward envelopes and charges their discounted tail from the certified contact-time lower bound onward.It is a conservative envelope, not a contact probability or action value.Source: §4 · p. 3
  • The contact-time lower bound certifies that both ordered rewards of a pair vanish at every return index before contact can first occur.It uses initial distance, interaction range, and the sum of the agents’ almost-sure speed bounds; obstacles or policies may delay contact further.Source: §4 · p. 3
  • For any capacity-valid partition, the cut-affinity sum bounds the value change of an unchanged stationary randomized Markov state-feedback policy after cross-team reward deletion.The same policy must be evaluated in both reward models.Source: §4 · p. 3
  • The fixed-policy bound relies on a common trajectory law; controllers that observe deleted rewards and react through reward history may choose different future actions.The stated optimization result uses the stationary Markov policy class.Source: §4 · p. 3
  • Under the stated factorization conditions, the cut MDP separates into team problems, and a product of team-optimal policies is cut-MDP optimal.Executing that policy in the original MDP incurs at most 2B_P(x) regret; both certificate constants are worst-case tight for signed rewards.Source: §4 · p. 3

4.1 Certificate Properties

  • The certificate separates reward magnitude, certified contact delay, and discounting; one additional certified zero-reward step reduces a pair’s charge by exactly gamma.Exact minimization chooses the smallest theorem-derived upper bound, not necessarily the partition with minimum realized regret.Source: §4.1 · pp. 3–4
  • Conservative overestimates of speed, range, or reward magnitude preserve validity but weaken selection resolution; underestimates can break the guarantee.A pair already in range receives the undiscounted infinite-horizon envelope, not a prediction that reward will recur.Source: §4.1 · p. 4
  • The certificate is conditional on the initial state and fixed overlay; recomputing it later changes the information structure, cut reward, and policy being evaluated.Execution-regret guarantees additionally require product dynamics and actions, complete cross-team reward deletion in the surrogate, and team-optimal planning.Source: §4.1 · p. 4

5 Certificate-Guided Partitioning

RCSD combines a certificate construction with a capacity-valid partition solver, then uses team-local planning on the resulting cut MDP. The section describes exact and heuristic solvers, a capacity-based certification rule, and the distinction between partitioning cost and planning cost.

5 Certificate-Guided Partitioning

  • RCSD pairs the Eq. (5) certificate construction with a capacity-valid partition solver; exact team-local planning then returns the product-optimal cut policy.Every feasible partition output retains the policy-wise certificate, and the certificate is available before team planning.Source: §5 · p. 4
  • RCSD-Exact uses a subset dynamic program that enumerates each feasible partition once and exploits additive retained affinity for optimal substructure.The exact solver is intended for small n.Source: §5 · p. 4
  • RCSD-Greedy merges feasible block pairs with the largest positive rescued affinity, while RCSD-MnM-sum uses deterministic matching and contraction; neither has an asserted approximation ratio.Source: §5 · p. 4
  • Pair construction takes O(n^2) time and space, but dense tabular team planning remains exponential in capacity L.The stated link count is not a measure of bytes or latency, and excludes one-time membership announcement.Source: §5 · p. 4
  • A sufficient certification rule accepts capacity L when 2B*_L(x) plus the planning-error bound is at most the allowed value-loss tolerance δ.For heuristic partitions, the rule uses the returned cut certificate and corresponding planning-error bound.Source: §5 · p. 4
  • The large-n evaluation isolates partition construction, while the exact five-agent experiments measure policy quality; fast graph partitioning does not establish fast end-to-end planning.Source: §5 · pp. 4–5
  • Persistent membership limits each policy to at most L agents while physical agents continue moving and cross-team rewards remain in execution.Cross-team rewards are deleted in the surrogate MDP, not by physically removing interactions.Source: §5 · p. 5

6 Experimental Design

The experimental design combines finite-MDP verification, controlled exact-partition comparisons, solver-scaling tests, and stochastic two-dimensional studies. Policy-quality estimands use exact optimization over their stated policy classes to avoid training variance.

6 Experimental Design

  • The evaluation spans finite-MDP verification, partition utility, solver quality and scaling, and stochastic two-dimensional transfer, with policy-class optima computed exactly.Source: §6 · p. 5
  • Verification tests the contact lemma over 648 bounded-motion settings, evaluates policy-wise bounds for 2,048 deterministic policies, and checks 1,716 factorization or regret comparisons.The tests include signed asymmetric rewards, randomized policies on stochastic instances, and witnesses that attain both constants.Source: §6 · p. 5
  • The omitted-feature control sets every agent at position 3 with near-equal envelopes and random ports, making certified delays zero while useful grouping depends on unobserved port compatibility.Because this control changes several construction parameters, it does not isolate a single-variable causal effect.Source: §6 · p. 5
  • The five-agent Meeting-Port Corridor tests every feasible equal-communication partition at L=2 and L=3 using exact team planning and original-MDP return evaluation.It uses 4,500 instances from each family and compares RCSD-Exact with uniform, distance-only, and envelope-only selectors.Source: §6 · p. 5
  • Solver variants are tested at n=8 and n=12, while scaling at n=24, 48, and 100 measures partition construction only, not large-MDP value.Source: §6 · p. 5
  • Stochastic obstacle-grid tests measure unrestricted stationary-Markov regret for exact four-agent partitions and controller-library regret for maps with 8–20 agents.The larger-agent tier uses a partition-independent library of four waypoint controllers and averages L=2 and L=4 within each map.Source: §6 · p. 5

7 Results

Finite-MDP checks found no violations under the stated assumptions, and the stochastic two-dimensional study also found no bound violations across exact-partition and restricted-controller evaluations. RCSD-Exact outperformed comparison selectors on the controlled informative family, while results varied across the omitted-feature control and larger controller-library study.

Finite-MDP verification

  • All finite-state verification instances satisfied the scoped inequalities, factorization identity, and capacity constraints, with largest numerical residual 1.42×10−14; fixtures attained the B and 2B constants.Counterexamples with post-transition rewards, one-sided envelopes, and reward-reactive policies violated the unmodified formula.Source: §7 · pp. 5–6, Table 3 · p. 6

Stochastic two-dimensional study

  • Across 384 exact four-agent partitions and 1,440 large-tier evaluations, no deletion or regret bound was violated; exact-tier regret was lower than Uniform, Distance, and Current by 21.6%, 24.1%, and 14.8%.In the controller-library tier, pointwise intervals favored RCSD over Distance and Current, included zero for Uniform, and favored Envelope and Value-MIP over RCSD.Source: §7 · p. 6

Controlled five-agent family

  • Mean normalized regret was 0.03910 for RCSD-Exact, versus 0.08895 for Uniform, 0.05492 for Distance, and 0.05235 for Envelope; median certificate–regret rank correlation was 0.7143.The results support the mechanism on the controlled informative construction, not a universal ordering of partitions.Source: §7 · p. 6, Table 4 · p. 6, Figure 2 · p. 7

Omitted-feature control

  • In the omitted-feature control, RCSD-Exact versus Uniform had ARR 0.03096, paired mean difference 0.00219, standardized effect 0.1000, and win rate 0.5164.The contrast is a scope boundary, not a causal ablation, because other generator parameters also differ.Source: §7 · p. 6

Certificate optimization and scaling

  • RCSD-Greedy’s normalized certificate gap had median 0.01110, p90 0.05287, and maximum 0.13845 across 1,200 oracle-sized cases; at n=100 and L=4, its median construction time was 0.0545 seconds.The timings exclude affinity formation and team-MDP planning, and the empirical gaps are not an approximation guarantee.Source: §7 · pp. 6–7, Figure 3 · p. 7

Capacity utilization

  • RCSD-MnM-sum at L=4 uses one third of the maximum because perfect first-round matching leaves no singleton, so the implementation stops with pairs; RCSD-Greedy’s median normalized gap remains below 0.027.Source: §7 · p. 7

8 Discussion

RCSD’s empirical support is strongest when affinity inputs encode coordination-relevant variation, but the certificate is a conservative upper bound rather than a predictor of realized regret. Its guarantees and evaluations have specific capacity, model, and planning boundaries.

Evidence scope

  • The evidence supports q_ij when its inputs encode coordination-relevant variation; the omitted-feature contrast is a scope boundary, not a causal ablation.Certified delays are zero and port compatibility is absent from q_ij in the control, where standardized effect and win-rate shifts are much smaller.Source: §8 · pp. 7–8

Capacity trade-off

  • Increasing L cannot increase the exact minimum certificate, but raises the directed-link ceiling and exponentially expands a tabular team’s state–action space.At L=1 every pair is cut; at L=n, B_P=0 and centralized information and joint planning are recovered.Source: §8 · p. 8

Evaluation scope

  • The 100-agent result times graph partitioning only; unrestricted planning is exact at four agents, while 8–20-agent evaluation is exact only within a fixed controller library.These evaluation regimes keep selector comparisons within the same partition shape and policy class.Source: §8 · p. 8

Certificate conservatism

  • The certificate is conservative because it charges the full pair envelope after the certified contact-time lower bound; sharper scores require additional verified information and a new bound argument.Obstacles, reachable sets, occupancy bounds, or policy restrictions could sharpen the score if their information is certified.Source: §8 · p. 8

Certificate versus regret

  • Minimizing the certificate minimizes an available upper bound, not necessarily realized regret, because deleted rewards may cancel, contact may occur later, or interactions may not affect the optimal action.Heuristic partitions also retain valid certificates even when their solvers miss the minimum.Source: §8 · p. 8

Guarantee assumptions

  • The policy-wise certificate assumes finite-state/action models, pre-transition finite-range rewards, valid motion and reward bounds, and one unchanged stationary Markov policy; execution regret additionally requires product dynamics and actions plus team-optimal cut planning.Coupled dynamics, shared action constraints, higher-order rewards, dynamic repartitioning, and general Dec-POMDP observation structures require different guarantees.Source: §8 · p. 8

9 Conclusion

RCSD converts reachability and finite-range reward envelopes into a certificate for capacity-limited persistent subteams, bounding unchanged-policy reward deletion and, under product dynamics, execution regret. The appendix makes the conditions and limits of these guarantees explicit and reports tightness witnesses and finite-MDP checks.

9 Conclusion

  • The cut-affinity sum bounds unchanged-policy reward deletion and, under product dynamics, centralized execution regret for capacity-valid persistent subteams.The conclusion reports no certificate violations in exact and stochastic tests, with partition experiments scaled to 100-agent affinity graphs.Source: §9 · p. 8

A Assumptions and Expanded Proofs

  • The fixed-policy certificate assumes a finite discounted MDP, almost-sure motion bounds, pre-transition rewards, symmetric pair ranges, and a partition fixed for one initial state.Walls, clipped motion, stochastic slip, or an agent’s policy can delay contact beyond the certified lower bound without threatening the certificate.Source: A Assumptions and Expanded Proofs · p. 10, §A.1 · p. 10

A.2 Policy-wise value difference

  • The deletion bound covers a reward-blind history-dependent action kernel only when held fixed; it does not cover a controller that reads deleted rewards and changes future actions.Such changes can make the coupled state–action paths diverge.Source: §A.2 · p. 10

A.3 Cut-MDP factorization

  • Cut-MDP separation requires Cartesian team action spaces, product transitions, and no cross-team reward terms; shared constraints, coupled dynamics, or undeleted higher-order rewards invalidate it.Source: §A.3 · p. 10

A.4 Two-sided transfer and tight constants

  • The fixed-policy value-difference constant B_P is tight, and the execution-regret factor 2 is also tight for signed rewards without an added structural or tie-breaking condition.The factor-two witness depends on a cut-optimal tie: the solver selects the negative-reward action while the original optimum selects the positive-reward action.Source: §A.4 · p. 11

B.1 RCSD algorithm

  • RCSD-Exact minimizes the certificate, while feasible heuristic partitions retain the policy-wise deletion certificate; the 2B_P regret guarantee additionally requires team-optimal planning.With approximate planning, that regret bound needs an additional planning-error term.Source: §B.1 · p. 11

B.2 Exact subset dynamic program

  • The exact subset dynamic program is exact relative to its stated tolerance, whereas the greedy merge only monotonically decreases B_P and has no global approximation ratio.The MnM-sum procedure is an implementation baseline, and its cited approximation statement is not transferred to that completion.Source: §B.2 · p. 11, §B.3 · p. 11, §B.4 · p. 11

C Finite-MDP Verification and Boundary Cases

  • Finite-MDP verification covers bounded-motion grids, signed-reward policy evaluations, stochastic motion, and partition/product-optimum comparisons; it does not evaluate learning, partial observation, or dynamic repartitioning.Separate witnesses attain B and 2B, while counterexamples examine reward timing, directed envelopes, and reward-observing controllers.Source: C Finite-MDP Verification and Boundary… · pp. 11–12, §C.1 · p. 12

D.2 Stratum-evaluation pseudocode

The evaluation specifies balanced partition strata, paired statistical comparisons, and solver and scaling checks. The reported certificate is numerically non-negligible on most tested positive-regret rows, but the passage cautions that this does not establish general tightness.

E Evaluation Protocol and Complete Results

E.1 Paired statistical procedure

  • The paired analysis compares seed-level average normalized regret against RCSD-Exact, uses bootstrap intervals and sign-flips, and adjusts Uniform, Distance, and Envelope tests with Holm correction.Certificate-rank intervals resample instance seeds while carrying both capacities as one cluster.Source: §E.1 · p. 13

E.2 Full utility statistics

  • 97.3% of 107,833 positive-regret partition rows have regret/(2B) ≥ .01, indicating a numerically non-negligible certificate on most tested rows, not general tightness.All 4,500 informative-family seeds have nonzero aggregate Uniform comparator regret.Source: §E.2 · p. 13

E.3 Exact solver quality

  • At capacity 4, RCSD-MnM-sum uses one third of permitted directed communication, explaining its larger objective gaps; its capacity-2 zero gaps are specific to tested positive even-agent graphs.Those zero gaps do not extend to larger capacities.Source: §E.3 · p. 13

E.4 Scaling details

  • Scaling timings characterize implementation only; that evaluation arm performs no MDP planning.Source: §E.4 · p. 13

F Omitted-Feature Control Analysis

In the omitted-feature control, RCSD-Exact, envelope-only, and current-contact selectors choose identical partitions because every initial distance and delay is zero. Exploratory checks reproduce those selections, but do not establish equivalence or isolate a sole causal difference between generators.

F Omitted-Feature Control Analysis

  • All three selectors choose the same partition in all 9,000 control strata because every initial distance and delay is zero.The large-sample ARR is .03096, with d_z = .1000 and win rate .5164.Source: F Omitted-Feature Control Analysis · p. 13
  • 60/60 envelope-only recomputations reproduce the selections, with no exact objective tie and a smallest top-two margin of 0.001201.The check is exploratory and uses a 60-stratum subset.Source: F Omitted-Feature Control Analysis · p. 13
  • The naive row-permutation null flags the observed rank association, but the mechanism-aware interval [.1821, .3375] contains it (upper-tail p = .0774).The naive null ignores shared edges; the mechanism-aware null preserves partition/regret incidence structure.Source: F Omitted-Feature Control Analysis · p. 13
  • These analyses establish neither equivalence nor that the omitted feature is the sole causal difference between generators.The control is not an equivalence test.Source: F Omitted-Feature Control Analysis · p. 13

G.1 Task and estimands

The evaluation compares persistent, capacity-bounded subteam selectors on exact four-agent tasks and a larger fixed-controller library, while auditing certificate behavior and reproducibility.

G.1 Task and estimands

  • Both tiers use connected obstacle grids, fixed teams, and independent agent motion; positive pair rewards require finite-range contact in seeded rendezvous regions.Failed moves leave agents in place, and co-location does not couple transitions.Source: §G.1 · pp. 13–14
  • The small tier compares exact centralized stationary-Markov regret on 128 four-agent maps; the 8–20-agent tier measures regret within a four-controller library.The large-tier waypoint controllers are generated before partition selection and shared across methods.Source: §G.1 · p. 14

G.2 Comparators and statistics

  • Selectors use the same complete block shape and n(L−1) directed links; Value-MIP is planning-aware, and large-tier intervals are stratified by n.Generated maps are the statistical units; the large-tier capacities are averaged within each map.Source: §G.2 · p. 14

G.3 Certificate tightness and utility boundary

  • RCSD has lower aggregate small-tier regret than Uniform, Distance, and Current, while large-tier intervals favor it over Distance and Current but favor Envelope and Value-MIP over RCSD.Small-tier raw evidence is borderline against Current and unresolved against Envelope; large-tier intervals include zero for Uniform.Source: §G.3 · p. 14, Table 12 · p. 15, Figure 4 · p. 15
  • The certificate is conservative but nonvacuous: the largest audited ratios are .816 for deletion and .356 for restricted regret.The largest ratios are below one.Source: §G.3 · p. 15, Table 13 · p. 15
  • At n = 20, the complete six-method, two-capacity suite had median and 95th-percentile runtimes of 50.16 and 52.34 seconds, respectively; this is an implementation observation, not a deployment latency guarantee.Source: §G.3 · p. 15

H Reproducibility Details

  • Supplementary materials include implementation, fixed configurations, and seed-level outputs; checks cover bounds, solver residuals, complete seed sets and capacities, and both 2-D tiers.Reported software versions and reproduction requirements are specified in the paper.Source: H Reproducibility Details · p. 15
Loading 2609.08366v1…