acceptodds
Withdrawn from ICLR 2027

PRODUCT-SET DEFICIENCY: A TRAINING -FREE MEASURE OF JOINT-ACTION COUPLING IN MULTI -ROBOT TASKS

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Cooperative multi-agent reinforcement learning often relies on value factorisation to enable decentralised execution, but this can restrict the combinations of actions that multiple robots can select jointly. We apply product-set deficiency, δ, the complement of a known bounding-box fill ratio, as a training-free measure of this restriction. Given the feasible joint actions for an instruction, obtained by enu- merating joint actions in a contact simulator, δ measures how far this set deviates from the Cartesian product of the individually feasible actions; δ = 0 when ev- ery combination of individually feasible actions is jointly feasible. We evaluate δ on a two-robot rod-pushing task. Instructions requiring coordination through the object have substantially higher δ than an instruction that can be solved in- dependently. Although the absolute value of δ depends on action discretisation, the relative ordering of the instructions remains stable across K ∈ [6, 24], and the same pattern holds for three and four robots pushing a box. We then test whether higher δ translates into greater learning difficulty. Across our experiments, it does not: δ does not predict the cost of factorised learning, and coordination graphs show no detectable learning advantage over independent learners despite substan- tially higher computational cost. An edge-gating variant guided by δ gains where δ ≈ 0 and beats both on one set of fresh seeds, but not on a second, and controls show the same gain without δ. These results suggest that δ is useful for charac- terising non-factorisable joint-action structure, but should not be interpreted as a direct measure of learning difficulty.

Primary area:
reinforcement learning
Keywords:
multi-agent reinforcement learning, value factorisation, individual-global-max, coordination graphs, multi-robot manipulation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1fWxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the structure of successful joint actions in cooperative multi-robot tasks. For a state and instruction, the authors enumerate discretized joint actions in a contact simulator and construct the feasible set F. They define product-set deficiency as delta = 1 - |F| / product_i |proj_i F|: the fraction of the smallest Cartesian-product hull of F that is not feasible. The quantity is the complement of an existing bounding-box fill ratio. Proposition 1 connects non-product feasible sets to the inability of an additive value function to reproduce the entire feasible set as its greedy-action set, while explicitly noting that positive delta does not preclude finding one successful decentralized action.

Validation uses a two-pusher rod task in MuJoCo and three-/four-pusher box experiments. The authors examine action-grid resolution, predicate thresholds, and alternative dependence measures. They then compare IQL, VDN, QMIX, QTRAN, DCG, and two instruction-conditioned DCG variants in a two-agent, multi-step rod environment. The principal findings are negative: delta describes feasible-action coupling but does not predict learning difficulty in the tested settings; coordination graphs show no detectable advantage over independent learning; and the benefits of edge gating are not specific to delta or consistent across seed sets. No hardware experiments are reported, and learning experiments remain limited to two agents.

Critical strengths

S1. An interpretable distinction between feasible-action structure and learning difficulty. The definition gives a clear operational interpretation: independently and uniformly sampling from each agent’s projection of F fails with probability delta. The paper carefully distinguishes representing all successful combinations from finding one successful joint action, and explicitly states that positive delta does not imply an IGM violation (Section 2.1). This distinction is useful because it prevents a structural dependence measure from being mistaken for a general measure of coordination-learning difficulty.

S2. Transparent reporting of negative findings and meaningful controls. The authors examine discretization and predicate sensitivity, compare against total correlation, repeat learning comparisons on fresh seeds, and include always-edgeless and wrong-instruction gating controls. These controls undermine the proposed delta-specific algorithmic explanation, and the paper reports that outcome rather than presenting the favorable replication in isolation (Sections 3.2–3.4; Appendices E, G, K). It also correctly avoids claiming equivalence from a nonsignificant DCG–IQL difference. This transparency strengthens the credibility of the restricted empirical observations.

Critical weaknesses

W1. The incremental contribution of the structural measure is limited, and its distinctive value for learning remains insufficiently established. The authors acknowledge that delta is the complement of an established fill-ratio descriptor, and its ranking is almost identical to total correlation across the 230 tested sets (Spearman rho = 0.978; Appendix E). Proposition 1 establishes a simple property of the entire greedy set of an additive value function, but does not constrain finding a single successful policy, as the paper itself notes. The learning and graph-selection experiments do not establish a benefit specific to the measure. Thus, the remaining contribution is primarily an interpretable application of a known descriptor to feasible-action supports. This may be useful, but the paper does not yet demonstrate sufficient additional insight or utility beyond existing dependence measures to make the contribution compelling for ICLR.

The observed ordering is also narrower than general cross-task validation. The absolute value changes substantially with action discretization (approximately 0.633 at K = 8 to 0.906 at K = 24 for push forward), and the two-agent “each robot just move” control is a product set by construction. Three-/four-agent box tests extend the structural measurement within planar pushing, but do not validate learning consequences outside the two-agent rod environment. A scalar fill ratio also does not identify the relevant coordination graph: the pairwise extension fails to reliably select the intended pair, and the proposed partial-coupling predicate does not impose the intended restriction in 39 of 40 states (Appendix D). These limitations restrict the measure’s demonstrated reach; they do not invalidate its mathematical definition.

W2. The learning experiments do not yet isolate a sufficiently general or decisive negative result. The one-step bandit tests allow independent learners to settle on any matching successful action. Adding a uniform failure penalty does not introduce a safe suboptimal alternative, so the absence of a learning gap does not strongly test the relative-overgeneralization difficulty motivating the work (Appendix I). In the multi-step study, all learning experiments use one two-agent task family and shipped hyperparameters. Replay buffers differ between the DCG family and several factorized baselines (500 versus 5,000 episodes; Table A3), and every method declines after an early peak for an unresolved reason (Appendix J). These factors complicate interpreting the measured gap as a consequence of coordination structure rather than training configuration or task design.

The reported DCG–IQL difference is +1.13 with a 95% interval of [-3.07, 5.32], and the paper acknowledges limited power to detect anything but large effects. This supports “no advantage detected under these settings,” not a general conclusion that explicit coordination is unnecessary. The authors mostly maintain that distinction; the concern is that the resulting negative knowledge is too restricted to compensate for the limited novelty of the descriptor. The hand-specified uncoupled instruction set in LS-DCG, subsequently confirmed by measurement, also does not demonstrate the end-to-end graph-selection procedure of Algorithm 2. A lack of hardware or state-of-the-art performance is not itself a reason for this recommendation.

Questions for authors

Clarification requests

  1. Beyond interpretability, what specific new inference does delta enable that total correlation or existing support-dependence descriptors do not? Since Proposition 1 concerns matching the entire feasible set rather than finding a successful policy, what makes this connection consequential for the learning problem? A concrete distinction would materially affect the assessment of significance.
  2. How sensitive are the DCG–IQL and edgeless-DCG comparisons to matching replay-buffer settings and to evaluating the full learning trajectory rather than only the post-peak endpoint? Please distinguish configuration effects from coordination-structure effects using the existing rod task. This matters particularly because all methods exhibit unexplained late decline.

Focused additional evidence that could change the assessment

  1. Within the existing experimental framework, can the authors test a setting with a genuine competing safe-but-suboptimal action, and examine whether delta predicts the resulting independent-versus-joint learning gap? The uniform failure-penalty experiment does not create this situation. A well-controlled result, positive or negative, would make the learning-related conclusion more informative.
  2. Can the authors provide a controlled case in which the measured structure, rather than an instruction set chosen by hand, drives a consequential coordination decision? If not, please distinguish the demonstrated descriptive use of delta from the unvalidated practical role of Algorithm 2. The request is for evidence of distinctive utility, not necessarily a new state-of-the-art algorithm.

Future work, not a requirement for the current recommendation

Broader non-pushing environments, continuous-action or stochastic-success formulations, scalable alternatives to K^n enumeration, and hardware deployment would be useful future directions. A new real-robot system or a large new benchmark suite is not requested for rebuttal.

Reviewer_RP7QOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces a measure called product-set deficiency, or δ\delta for short, which aims to quantify how "factorizable" the joint action space is in a multi-agent task. Here, factorization refers to the decentralized execution paradigm: I.e., each agent chooses its own action based on its own Q function, which (at least after learning) does not depend on the actions or Q functions of the other agents. For a given state, the δ\delta measure is computed by enumerating all joint actions in a discretized grid, empirically estimating the success rate of each joint action, and then subtracting the set of successful joint actions from its bounding box in the grid. The fraction of bounding box volume that remains after subtraction is the δ\delta measure. The bounding box is viewed as a Cartesian product of per-agent action sets with the potential to lead to success (depending on how other agents behave). Cartesian product is appropriate in a decentralized execution paradigm, to the extent that each agent's Q function marginalizes over the actions of other agents in some sense. The paper's empirical experiments study whether δ\delta is correlated with learning difficulty and whether it can be incorporated into the Q function architecture to guide learning. This includes not only fully factorized approaches but also loosely coupled approaches in which pairwise (but not higher-order) inter-agent Q function dependencies are realized via message passing over an agent graph structure.

Critical strengths
  • Conceptually, the paper's goal of measuring a multi-agent task's "factorizability" is compelling. Such a measure would be useful in determining whether decentralized execution is an appropriate approach for a given task.
Critical weaknesses
  • There seems to be a number of issues with the δ\delta metric. First, it requires discretization of the action space, which will prevent scaling to large or even modest size teams especially in continuous action spaces. Second, while the paper claims that the metric is "training-free," its computation algorithm requires rollouts of some reference policy, which is unlikely to produce meaningful information if it is not trained. It also appears to only work in deterministic environments since it only employs a single rollout per joint action, and treats the success of that one rollout as a success "predicate".

  • As the paper acknowledges, δ\delta is not predictive of decentralized execution learning difficulty, nor does it have much correlation with performance when integrated into the Q function architecture. So there is no clear utility demonstrated for this metric.

Questions for authors
  • In eq 3, shouldn't there be some expectation over rollouts here, or is the environment assumed deterministic? And does including a rollout not mean that the metric depends on the policies used for rollouts, making prior training required?

  • In def 2, the a_{-i} notation should be defined. I think I know what it means based on my prior knowledge of MARL, but can you confirm what you take it to mean?

  • The text describes eq 8 as "selecting the edge set", which sounds like deciding which agent pairs are connected by edges. But the formula looks more like a global all-or-nothing gate: when the gate is closed, there are no edges, and there is no per-pair gate deciding whether a particular edge is included. Did I misunderstand?

  • In algo 1, line 3: where does the 2pi come from? Is this algorithm only applicable to robot agents with a single rotational joint?

Reviewer_8R5FOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes product-det deficiency as a training-free measure that quantifies how much the set of feasible joint actions in a multi-robot setting differs from the cartesian product of the sets of individual actions. The results show that PSD captures aspects of task structure but it does not predict the difficulty of the task nor does it lead to advantages in joint learning.

Critical strengths

I must confess that I had a difficult time reading and understanding the paper. That said, as far as I could gather, two positive aspect that are worth mentioning are:

  • The measure proposed in the paper (product-set deficiency) is well-defined and interpretable; it seeks to quantify joint-action coupling in multi-robot settings based on the geometry of feasible action sets.
  • Additionally, the empirical study appears careful and the authors are commendably honest about negative findings, avoiding stronger claims than the evidence supports.
Critical weaknesses

As mentioned above, I found the paper exceptionally difficult to follow. A recurring issue is that concepts and notation are often introduced before sufficient context is provided. For example, Section 2.1 immediately jumps into the Individual-Global-Max condition using notation such as QtotQ_{tot}, qiq_i, or qijq_{ij}, but these quantities are never introduced, explained or motivated. Similarly, Definition 1 refers readers to Section 3.1 for context, requiring navigation to later sections before the basic terminology has been established. Throughout the paper, I frequently encountered definitions, notation, and claims whose purpose only became apparent much later, making it difficult to maintain a coherent understanding of the central argument.

Besides the presentation concerns, my other concern is that, after finishing the paper, I still do not understand what PSD is ultimately useful for. The paper shows that PSD provides a measure of action-space coupling, but the results seem to suggest that PSD is neither a reliable predictor of learning difficulty nor can be used to improve MARL algorithms. As a result, I remain uncertain about its practical use and what decisions the resulting value is supposed to inform.

Questions for authors

Given your conclusion that PSD is not a reliable predictor of learning difficulty, what do you see as the primary practical application of PSD?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.