acceptodds
Under review as a conference paper at ICLR 2027

Improving Entity-Configuration Generalization in Real-Time Strategy Games with Task Hypergraph Representation

Abstract

This paper investigates compositional generalization across entity configurations in real-time strategy (RTS) games, which remains challenging for existing methods. To address this problem, we propose a task-hypergraph-based policy architecture that represents game entities as nodes and task instances involving multiple entities, such as resource-gathering and attacking, as hyperedges. The architecture comprises a task hypergraph constructor and a task hypergraph network. We encode RTS domain knowledge as cross-scenario task schemas, feasibility constraints, and an objective function over task-instance sets, thereby formulating hypergraph construction as a constrained optimization problem over sets of task instances. Given the current state, the constructor instantiates schema-valid task instances and selects a jointly feasible subset using the set-level objective. The selected instances then induce the task hypergraph. The task hypergraph network aggregates information among entities participating in the task instance through node-to-hyperedge-to-node message passing and generates entity-level actions using multiple action heads, relation encodings, and hyperedge-type-dependent soft biases. By representing changes in entity configurations as recombinations of task instances and their participating entities under shared task schemas, our approach enables consistent task-level processing across scenarios and thereby supports compositional generalization.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Real-Time Strategy Games, Compositional Generalization, Entity Configuration, Task Hypergraph, Hypergraph Neural Network, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_tV6uOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose a novel task-hypergraph-based policy for reinforcement learning in real-time strategy (RTS) games and evaluate it on Gym-μ\mu-RTS. The proposed method demonstrates better generalization to unseen scenarios than several baseline methods, including CNN, CNN-Reg, DCPG, and GTG

Critical strengths

S1. Motivation and problem formulation.\textbf{S1. Motivation and problem formulation.} The paper addresses the important problem of generalization across different RTS initial configurations and offers a novel perspective on policy optimization.

S2. Novel representation and empirical benefits.\textbf{S2. Novel representation and empirical benefits.} The paper introduces a task-hypergraph-based representation of RTS entities and action spaces, including no-op, move, harvest, and return. This representation is novel to some extent, and the reported results suggest that the resulting reinforcement learning policy yields substantial performance gains. The hypergraph formulation for RTS games is also comprehensive, with detailed descriptions provided in the appendix.

Critical weaknesses

W1. Limited evaluation of compositional generalization.\textbf{W1. Limited evaluation of compositional generalization.} The experiments cover only Maps A–D and appear to focus on changes to individual factors, such as map layouts, building types, or worker types. Broader evaluations are needed to substantiate the paper's generalization claims. For example, the authors should test combinations involving different numbers and types of entities and different resource distributions, including scenarios in which two or more factors vary simultaneously.

W2. Insufficient statistical analysis.\textbf{W2. Insufficient statistical analysis.} The experimental results are reported primarily in terms of win rates, without confidence intervals, variance estimates, or other measures of statistical uncertainty. These are needed to assess the statistical significance and reliability of the reported improvements.

W3. Missing computational cost analysis.\textbf{W3. Missing computational cost analysis.} The paper should report training and inference costs, including computational resources and runtime. Such information would enable a more comprehensive comparison with CNN-based and other baseline methods.

Questions for authors

Q1. Compositional generalization\textbf{Q1. Compositional generalization}: How does the proposed method perform when multiple configuration factors vary simultaneously, as discussed in W1?

Q2. Statistical significance\textbf{Q2. Statistical significance}: Are the reported performance improvements statistically significant? Could the authors provide additional experimental results and statistical analyses, as discussed in W2?

Q3. Computational overhead\textbf{Q3. Computational overhead}: How do the end-to-end runtime and computational costs of the proposed method compare with those of the baselines? Are there significant differences in runtime or resource consumption? Could the observed performance gains be attributed, at least in part, to additional computational overhead, as discussed in W3?

4 comments

We thank the reviewer for taking the time to review our manuscript. We think that there might be some misunderstandings about our paper and hope that our responses can address all your concerns. Below, we respond point by point to the weaknesses and questions raised in the review.

Weakness 1: W1.Limited evaluation of compositional generalization. The experiments cover only Maps A–D and appear to focus on changes to individual factors, such as map layouts, building types, or worker types. Broader evaluations are needed to substantiate the paper's generalization claims. For example, the authors should test combinations involving different numbers and types of entities and different resource distributions, including scenarios in which two or more factors vary simultaneously.

Response to Weakness 1: Our generalization claim is that “this paper studies compositional generalization across entity configurations. The training and test scenarios share the same entity types, action space, interaction rules, and task objective, but differ in their initial entity-type compositions and spatial layouts.” (line 40 of the original manuscript). Our evaluation therefore focuses on these two dimensions (initial entity-type compositions and spatial layouts). In both Map C and Map D, the initial entity-type composition and spatial layout differ simultaneously from those in the training scenarios. We acknowledge that broader evaluations would strengthen the empirical evidence, but the current experiments directly test the two dimensions of variation covered by our claim, including cases in which both vary together.



Weakness 2: W2.Insufficient statistical analysis. The experimental results are reported primarily in terms of win rates, without confidence intervals, variance estimates, or other measures of statistical uncertainty. These are needed to assess the statistical significance and reliability of the reported improvements.

Response to Weakness 2: We acknowledge that our original experiments lacked sufficient statistical analysis. As shown in Table 1, we conducted additional experiments and report the mean and standard deviation of the results. Thank you for pointing this out. We will include this statistics results in the experiment section of the revised manuscript.

Table 1: Win rates (%) on the training and held-out test maps. Each method plays 40 games on each map. Test WR aggregates all four held-out maps (n= 160); Spatial WR aggregates Maps A and B (n= 80); Compositional WR aggregates Maps C and D (n= 80); and Worst-map WR reports the lowest win rate on a single held-out map (n= 40). Win rates are reported as mean ± standard deviation over three runs.

MethodTrain WRTest WRSpat WRComp WRWorst-map WR
CNN87.8 ± 1.441.5 ± 1.640.8 ± 7.342.1 ± 4.717.5 ± 6.6
CNN-Reg79.5 ± 3.541.5 ± 1.442.5 ± 4.540.4 ± 1.925.0 ± 0.0
DCPG80.3 ± 2.931.5 ± 1.829.6 ± 2.633.3 ± 2.624.2 ± 1.4
GTG89.2 ± 2.875.2 ± 5.182.1 ± 6.468.3 ± 4.765.8 ± 1.4
Entity Transformer87.4 ± 3.671.0 ± 3.870.4 ± 4.771.7 ± 3.258.3 ± 6.3
TaskHypergraph-Greddy92.5 ± 2.585.2 ± 1.489.6 ± 0.780.8 ± 2.675.8 ± 1.4
TaskHypergraph_Recursive93.6 ± 2.986.9 ± 2.590.4 ± 1.983.3 ± 3.273.3 ± 1.4

Weakness 3: W3.Missing computional cost analysis. The paper should report training and inference costs, including computational resources and runtime. Such information would enable a more comprehensive comparison with CNN-based and other baseline methods.

Response to Weakness 3: All baseline methods, including ours, were trained and evaluated on NVIDIA Tesla T4 GPUs. Each method completed training within 48 hours and evaluation within 4 hours. We omitted the hardware specifications and overall runtimes from the original manuscript because training and evaluation times were broadly comparable across methods.

To assess computational cost more directly, we conducted additional experiments focusing on the recursive and greedy solvers, which we expect to be the main sources of runtime variation within our method.

Solver runtime is determined entirely by the number of entities. More entities generate more task instances, which in turn increases solver runtime. As shown in Table 2, the recursive solver can exhibit exponential time complexity in the worst case, while the greedy solver’s runtime remains relatively stable. When there are many entities, the greedy solver can be used, since the win-rate gap between the two solvers is small, at about 3 percentage points (see Table 1 of the original manuscript).

Thank you for pointing this out. We will include this runtime experiments in the experiment section of the revised manuscript.

Table 2. Solver runtimes across entity counts. For each entity count, we report the average number of task instances and the runtime of the recursive and greedy solvers. The results are reported as mean ± standard deviation over three runs.

# Entities# Task InstancesRecursive Solver Time (ms)Greedy Solver Time (ms)
10140.900 ± 0.0490.325 ± 0.200
20343.918 ± 0.3071.268 ± 0.325
305312.924 ± 5.3581.405 ± 0.348
408342.399 ± 40.7961.863 ± 0.462
501612630.485 ± 356.2752.597 ± 0.539


Question 1: Q1.Compositional generalization: How does the proposed method perform when multiple configuration factors vary simultaneously, as discussed in W1?

Response to Question 1: Question 1 raises the same concern as Weakness 1. Please see our response to Weakness 1.



Question 2: Q2. Statistical significance: Are the reported performance improvements statistically significant? Could the authors provide additional experimental results and statistical analyses, as discussed in W2?

Response to Question 2: Question 2 raises the same concern as Weakness 2. Please see our response to Weakness 2.



Question 3: Q3. Computional overhead: How do the end-to-end runtime and computational costs of the proposed method compare with those of the baselines? Are there significant differences in runtime or resource consumption? Could the observed performance gains be attributed, at least in part, to additional computational overhead, as discussed in W3?

the first point of Question 3: How do the end-to-end runtime and computational costs of the proposed method compare with those of the baselines? Are there significant differences in runtime or resource consumption?

Response to the first point of Question3: The first point of Question 3 raises the same concern as Weakness 3. Please see our response to Weakness 3.


the second point of Question 3: Could the observed performance gains be attributed, at least in part, to additional computational overhead, as discussed in W3?

Response to the second point of Question3: In our evaluation, the recursive solver achieved a win rate approximately 3 percentage points higher than the greedy solver. As you pointed out, this improvement comes at a substantial computational cost (as shown in Table 2). However, in more complex settings, the greedy solver offers a practical trade-off: it reduces substantial solve time at the cost of a slight decrease in win rate. Thank you for pointing this out. We will emphasize this point in the main text of the revised manuscript.

Thank you for the authors' response. My concerns regarding W1 and W2 have been partially addressed. However, considering the novelty and potential impact of this work, I can only increase my rating to 2

Thank you for the feedback. Although the discussion period is nearing its end, we would like to take this opportunity to reiterate the novelty of our work. By transforming states into hypergraph representations, where multi-entity RTS tasks are modeled as hyperedges, our approach captures higher-order interactions beyond pairwise graphs or grid-based representations. This task-centered inductive bias enables the reuse of learned relational structures across changing entity configurations and spatial layouts, supporting strong zero-shot transfer to unseen maps. While we acknowledge that some aspects of our work, including the experimental design, could be improved, we respectfully believe that these limitations do not negate the novelty of our contribution.

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

Summary: This paper investigates the challenging problem of compositional generalization across varying initial entity configurations in real-time strategy (RTS) games. While deep reinforcement learning policies often achieve strong performance in fixed training scenarios, they typically suffer severe performance degradation when initial entity types, counts, or spatial layouts change. To bridge this gap, the authors propose a task-hypergraph-based policy architecture that models game entities as nodes and multi-entity cooperative task instances (e.g., harvesting, attacking, producing) as hyperedges.

Contributions:

  • Task Hypergraph Representation: Proposes a structured relational representation that models complex, multi-entity RTS tasks as hyperedges, allowing shifting entity configurations to be seamlessly expressed as task instance recombinations under shared semantics.
  • Constrained Optimization for Hypergraph Construction: Formulates task hypergraph construction as a constrained optimization problem over task-instance sets using shared task schemas, feasibility constraints, and a set-level objective function. It provides both an efficient approximate greedy solver for training and an exact recursive solver for evaluation.
  • Task Hypergraph Network: Designs a specialized neural network featuring node-to-hyperedge-to-node message passing, multi-action decision heads coupled with action-specific geometric/relation encodings, and hyperedge-type-dependent soft biases to robustly translate high-level task representations into low-level entity controls.

Validation: The method is evaluated in full-game Gym-μ\muRTS on 16×1616\times16 maps against diverse non-relational baselines (CNN, CNN-Reg, DCPG) and relational baselines (Entity Transformer, GTG). The results demonstrate that:

  • The proposed architecture substantially outperforms all baselines in zero-shot transfer across unseen spatial layouts and initial entity-type compositions (achieving an overall test win rate of 86.9% with the greedy solver and 89.4% with the recursive solver, compared to ≤80.6%\le 80.6\% for relational baselines and ≤43.1%\le 43.1\% for CNN-based methods).
  • Ablation studies confirm the individual and complementary necessity of the specialized action heads, relation encodings, and task-consistent soft biases.
Critical strengths
  • Novel Task-Hypergraph Representation for Relational Generalization: The formulation of multi-entity RTS tasks (such as resource harvesting, attacking, and production) as hyperedges—rather than relying solely on pairwise graphs or standard grid-based representations—is a conceptually elegant and consequential contribution. It provides a natural inductive bias that bridges shifting entity configurations and spatial layouts via task-instance recombinations, yielding strong zero-shot transfer performance on unseen maps.

  • Rigorous and Flexible Optimization-Driven Construction: Framing task hypergraph construction as a constrained optimization problem over task-instance sets (supported by an efficient greedy solver during training and an exact recursive solver at test time) is methodologically rigorous. The ability to swap in the exact solver during evaluation without retraining the policy network significantly boosts construction quality and overall robustness.

Critical weaknesses
  • Reliance on Domain-Specific Heuristics and Manual Schemas: The hypergraph constructor heavily relies on manually designed task schemas, feasibility constraints, and heuristic-based set-level objectives (e.g., handcrafted local and joint utility formulas, power-sufficiency thresholds, and priority functions). This limits the method's generalizability and scalability to more complex, open-ended RTS environments or games where expert domain knowledge is not readily codifiable.
  • Computational Overhead of Combinatorial Solvers: Although the greedy solver makes training feasible, the underlying optimization framework—especially the exact recursive solver used during evaluation—introduces substantial computational overhead and complexity. The worst-case exponential complexity of exact search over task-instance sets raises scalability concerns for larger maps with dense entity populations and long decision horizons.
  • Limited Environment Complexity and Scale:The empirical validation is restricted to small, symmetrical 16×1616\times16 grid maps in Gym-μ\muRTS with a minimal initial entity setup (e.g., 1 base and 1 worker per player). This restricted setting does not reflect the scale, partial observability, long time horizons, or complex economic and tactical interactions found in full-scale commercial RTS games (such as StarCraft II), raising questions about the method's scalability and robustness in more diverse and complex environments.
Questions for authors
  • Scalability of the Optimization Solvers: The hypergraph construction relies on either an approximate greedy solver during training or an exact recursive solver at test time. Given that exact recursive search over task-instance sets can have exponential worst-case complexity, how does the scalability of the exact solver degrade as the map size, entity density, and number of concurrent task instances increase (e.g., in larger 32×3232\times32 or commercial-scale RTS maps)? Could you provide concrete timing or computational overhead comparisons between the greedy and recursive solvers during inference?
  • Sensitivity to Hyperparameter and Heuristic Design: The framework utilizes a significant amount of manually engineered domain knowledge, including specific task schemas, role capacities, feasibility constraints, and heuristic-based set-level objective components (e.g., handcrafted utility functions, power-sufficiency thresholds, and distance/resource cost weights). How sensitive is the policy's compositional generalization performance to changes in these hand-crafted hyperparameters? Have the authors explored learning or adapting any components of the task schemas/objective functions end-to-end to reduce reliance on manual expert heuristics?
3 comments

We thank the reviewer for providing positive feedback and insightful comments. Below, we respond point by point to the weaknesses and questions raised in the review.

Weakness 1: Reliance on Domain-Specific Heuristics and Manual Schemas: The hypergraph constructor heavily relies on manually designed task schemas, feasibility constraints, and heuristic-based set-level objectives (e.g., handcrafted local and joint utility formulas, power-sufficiency thresholds, and priority functions). This limits the method's generalizability and scalability to more complex, open-ended RTS environments or games where expert domain knowledge is not readily codifiable.

Response to Weakness 1: We agree that relying on manually specified domain knowledge limits the generalizability and scalability of our hypergraph constructor in more complex, open-ended RTS environments.

However, Our approach uses domain knowledge at two levels. The first is the formulation of the constructor in terms of task schemas, feasibility constraints, and a set-level objective. Task schemas specify roles, admissible entity types, and role capacities, while the objective weighs task utility against execution and resource costs. We argue that this formulation to be reusable across most of RTS environments. The second level comprises the knowledge needed to instantiate that formulation in a particular environment, including concrete roles, validity conditions, and scoring terms. Much of the manual effort required to transfer the constructor to more complex environments arises at this level.

The trade-off is that explicit domain knowledge helps the policy reuse task structures across entity configurations within µRTS, while extending the constructor to more complex environments requires additional specification and validation. In future work, we plan to explore using LLMs to dynamically supply environment-specific knowledge to the hypergraph constructor, improving this trade-off.



Weakness 2: Computational Overhead of Combinatorial Solvers: Although the greedy solver makes training feasible, the underlying optimization framework—especially the exact recursive solver used during evaluation—introduces substantial computational overhead and complexity. The worst-case exponential complexity of exact search over task-instance sets raises scalability concerns for larger maps with dense entity populations and long decision horizons.

Response to Weakness 2: Regarding computational overhead, as you point out, the recursive solver can have exponential worst-case complexity. However, the greedy solver performs relatively consistently across different numbers of entities (the solver runtime experiments, please see our response to Question 1). The recursive solver can therefore be used in simpler scenarios, while the greedy solver can be considered for more complex scenarios. The greedy solver also achieves a very high win rate, only 2–3 percentage points below that of the recursive solver (see Table 1 of the original manuscript). In future work, we will investigate more efficient solvers to better balance solving efficiency and win rate.



Weakness 3: Limited Environment Complexity and Scale:The empirical validation is restricted to small, symmetrical grid maps in Gym-RTS with a minimal initial entity setup (e.g., 1 base and 1 worker per player). This restricted setting does not reflect the scale, partial observability, long time horizons, or complex economic and tactical interactions found in full-scale commercial RTS games (such as StarCraft II), raising questions about the method's scalability and robustness in more diverse and complex environments.

Response to Weakness 3: We acknowledge that our empirical evaluation is limited in both environmental complexity and scale. To address the reviewer’s concern about scalability, we added experiments comparing performance across maps of different sizes within the current μ\muRTS setting(Table 1). Furthermore, our evaluation used full observability, so partial observability remains an open question. Although μ\muRTS simplifies the economic and tactical interactions found in StarCraft II, it still requires agents to make both strategic and tactical decisions over the course of a full match. With up to 5,000 environment interactions per episode, it also allows us to evaluate some aspects of long-horizon decision-making. Evaluating the method in StarCraft II would require more resources and data than we currently have available. we will try to extend our evaluation to more complex RTS environments.

Table 1. Win rates across map sizes. Each map was generated by scaling the entity positions from the original 16×16 Map A to the target map sizes. Win rates are reported as mean ± standard deviation over three runs.

Map SizeWin Rate (%)
8×870.0 ± 3.5
16×1695.4 ± 2.4
24×2482.3 ± 3.1

Question 1: Scalability of the Optimization Solvers: The hypergraph construction relies on either an approximate greedy solver during training or an exact recursive solver at test time. Given that exact recursive search over task-instance sets can have exponential worst-case complexity, how does the scalability of the exact solver degrade as the map size, entity density, and number of concurrent task instances increase (e.g., in larger or commercial-scale RTS maps)? Could you provide concrete timing or computational overhead comparisons between the greedy and recursive solvers during inference?

Response to Question1: We agree that the recursive solver can be time-consuming. Solver runtime is determined entirely by the number of entities. More entities generate more task instances, which in turn increases solver runtime. As shown in Table 2, the recursive solver can exhibit exponential time complexity in the worst case, while the greedy solver’s runtime remains relatively stable. When there are many entities, the greedy solver can be used, since the win-rate gap between the two solvers is small, at about 3 percentage points (see Table 1 of the original manuscript). Thank you for pointing this out. We will include this runtime experiment in the experiment section of the revised manuscript.

Table 2. Solver runtimes across entity counts. For each entity count, we report the average number of task instances and the runtime of the recursive and greedy solvers. The results are reported as mean ± standard deviation over three runs.

# Entities# Task InstancesRecursive Solver Time (ms)Greedy Solver Time (ms)
10140.900 ± 0.0490.325 ± 0.200
20343.918 ± 0.3071.268 ± 0.325
305312.924 ± 5.3581.405 ± 0.348
408342.399 ± 40.7961.863 ± 0.462
501612630.485 ± 356.2752.597 ± 0.539

Question 2: Sensitivity to Hyperparameter and Heuristic Design: The framework utilizes a significant amount of manually engineered domain knowledge, including specific task schemas, role capacities, feasibility constraints, and heuristic-based set-level objective components (e.g., handcrafted utility functions, power-sufficiency thresholds, and distance/resource cost weights). How sensitive is the policy's compositional generalization performance to changes in these hand-crafted hyperparameters? Have the authors explored learning or adapting any components of the task schemas/objective functions end-to-end to reduce reliance on manual expert heuristics?

the first point of Question 2: The framework utilizes a significant amount of manually engineered domain knowledge, including specific task schemas, role capacities, feasibility constraints, and heuristic-based set-level objective components (e.g., handcrafted utility functions, power-sufficiency thresholds, and distance/resource cost weights). How sensitive is the policy's compositional generalization performance to changes in these hand-crafted hyperparameters?

Response to the first point of Question2: Regarding the sensitivity to hyperparameter you mentioned, we conduct a sensitivity analysis, as shown in Table 3. The win rates under different hyperparameter settings did not drop substantially compared with the default setting, suggesting that the method maintains relatively high performance across the different settings. Thank you for pointing this out. We will include this sensitivity experiment in the experiment section of the revised manuscript.

Table 3. Sensitivity to hand-set coefficients. We compare the default configuration with four configurations (Sample1-4) obtained by sampling from normal distributions centered at the default knowledge hyperparameter values on Map A. Win rates are reported as mean ± standard deviation over three runs.

ConfigurationWin Rate (%)
Default95.4 ± 2.4
Sample 187.6 ± 1.2
Sample 296.0 ± 3.5
Sample 385.6 ± 3.7
Sample 492.3 ± 2.8

Sample details: we perturb 12 key hyperparameters across two groups: task schema parameters, such as role capacities and spatial validity thresholds, and task-instance-set objective parameters, such as task utility weights and distance and resource cost coefficients. We sample each hyperparameter from a normal distribution centered at its default value and use relatively large standard deviations to explore substantial deviations from the defaults.


the second point of Question 2: Have the authors explored learning or adapting any components of the task schemas/objective functions end-to-end to reduce reliance on manual expert heuristics?

Response to the second point of Question2: We did consider the question you raised in the early stages of our research, but ultimately chose not to “learning or adapting any components of the task schemas/objective functions end-to-end”. The reasons are as follows.

We argue that there are two ways to improve generalization. The first is to expand the coverage of the training data or environments. When the amount of data becomes sufficiently large, generalization can arise naturally, as in the case of large language models. The second is to introduce knowledge from outside the training distribution, which can take various forms. It is extremely difficult to expect an end-to-end learning algorithm alone to acquire knowledge outside the training distribution. As stated in [1], achieving generalization requires combining hand-engineering with end-to-end learning. The former provides inductive biases aligned with the problem structure, while the latter learns structured representations and decision rules from interaction data. We follow the second generalization way, considering the task schemas and objective functions to be part of the hand-engineering component, which is why we did not learn them. There may be more effective ways to incorporate domain knowledge while leaving more room for learning. We will continue to investigate this in future work.

[1] Relational inductive biases, deep learning, and graph networks

Reviewer_P7ouOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the compositional generalization across entity configurations in real-time strategy (RTS) games. To do this, they propose a task-hypergraph-based policy architecture that represents entities as nodes and selected task instances as hyperedges. The full architecture includes a task hypergraph constructor and a task hypergraph network. The task hypergraph constructor is formulated as a constrained optimization problem and solved using an exact recursive solver or an efficient greedy solver. The task hypergraph network generates entity-level actions through node-to-hyperedge-to-node message passing. Finally, they conduct experiments on Gym-μ\muRTS and results show their proposed architecture outperforms other baselines.

Critical strengths

The proposed architecture seems to be novel since they formulate task hypergraph construction as a constrained optimization problem over task instances and proposes two solvers for this problem. It provides a reusable template for similar settings.

Critical weaknesses
  1. The task hypergraph construction requires RTS domain knowledge. Specifically, these objectives in A.3 seem to be governed by some hand-set coefficients and thresholds. However, it is not clear whether the performance attribution is due to the design or the domain knowledge, since there is no ablation study on this.

  2. Another concern is about scalability. The method is trained on a single 16 x 16 map and tested on 4 maps, with 40 games per map. There is no evidence that it scales to larger maps or more entities. Furthermore, the exact recursive solver seems to be time-consuming when applied to large-scale games. Moreover, the paper does not discuss existing work on generalization over varying entity compositions in large-scale StarCraft multi-agent settings, whose problem setting seems to be like the one studied here.

Questions for authors
  1. Since the task hypergraph construction requires some hand-written rules, could the author provide some ablation study results to determine how much the performance attribution comes from these hand-written rules?

  2. Could the author provide a discussion about the difference between their work and works on generalization over varying entity compositions in large-scale StarCraft multi-agent settings? Could these methods be applied to the RTS setting studied here, and if so, how do they compare with the proposed approach? If not, what prevents them from being applied?

  3. For the scalability and computational cost problem, what are the runtimes of the greedy and exact solvers? How do these grow with the number of entities, for example, on larger µRTS maps?

If the authors can address these weaknesses and questions well, I would consider raising my score.

10 comments

We thank the reviewer for your valuable and professional comments. Below, we respond point by point to the weaknesses and questions raised in the review.

Weakness 1:The task hypergraph construction requires RTS domain knowledge. Specifically, these objectives in A.3 seem to be governed by some hand-set coefficients and thresholds. However, it is not clear whether the performance attribution is due to the design or the domain knowledge, since there is no ablation study on this.

Response to Weakness 1: We agree that the original submission lacked an ablation study to assess the contribution of domain knowledge. To address this, we conduct an ablation study to compare performance with and without domain knowledge. As shown in Table 1, using domain knowledge improves the win rate by approximately 30 percentage points, indicating that domain knowledge contributes to the method’s performance. Thank you for pointing this out. We will include this ablation study in the experiment section of the revised manuscript.

Table 1. Effect of domain knowledge on win rate. We compare the proposed method with a variant (w/o Domain Knowledge) that forms each hyperedge from a center entity and its three nearest neighbors on Map A. Win rates are reported as mean ± standard deviation over three runs.

MethodWin Rate (%)
Proposed Method95.4 ± 2.4
w/o Domain Knowledge66.7 ± 3.1


Weakness 2: Another concern is about scalability. The method is trained on a single 16 x 16 map and tested on 4 maps, with 40 games per map. There is no evidence that it scales to larger maps or more entities. Furthermore, the exact recursive solver seems to be time-consuming when applied to large-scale games. Moreover, the paper does not discuss existing work on generalization over varying entity compositions in large-scale StarCraft multi-agent settings, whose problem setting seems to be like the one studied here.

the first point of Weakness 2: The method is trained on a single 16 x 16 map and tested on 4 maps, with 40 games per map. There is no evidence that it scales to larger maps or more entities.

Response to the first point of Weakness 2: We agree that the original submission lacked an empirical evaluation of our method’s scalability. To address this, we evaluate the same policy, using the weights trained on 16×16 maps, on 8×8 and 24×24 maps. As shown in Table 2, although performance declined at both new map sizes, the policy still achieved win rates of 70.0% and 82.3%, respectively. These results provide evidence that our method can generalize across map sizes without retraining. Thank you for pointing this out. We will include this ablation study in the experiment section of the revised manuscript.

Table 2. Win rates across map sizes. Each map was generated by scaling the entity positions from the original 16×16 Map A to the target map sizes. Win rates are reported as mean ± standard deviation over three runs.

Map SizeWin Rate (%)
8×870.0 ± 3.5
16×1695.4 ± 2.4
24×2482.3 ± 3.1

the second point of Weakness 2: Furthermore, the exact recursive solver seems to be time-consuming when applied to large-scale games

Response to the second point of Weakness 2: We agree that the recursive solver can be time-consuming. Solver runtime is determined entirely by the number of entities. More entities generate more task instances, which in turn increases solver runtime. As shown in Table 3, the recursive solver can exhibit exponential time complexity in the worst case, while the greedy solver’s runtime remains relatively stable. When there are many entities, the greedy solver can be used, since the win-rate gap between the two solvers is small, at about 3 percentage points (see Table 1 of the original manuscript). Thank you for pointing this out. We will include this runtime experiment in the experiment section of the revised manuscript.

Table 3. Solver runtimes across entity counts. For each entity count, we report the average number of task instances and the runtime of the recursive and greedy solvers. The results are reported as mean ± standard deviation over three runs.

# Entities# Task InstancesRecursive Solver Time (ms)Greedy Solver Time (ms)
10140.900 ± 0.0490.325 ± 0.200
20343.918 ± 0.3071.268 ± 0.325
305312.924 ± 5.3581.405 ± 0.348
408342.399 ± 40.7961.863 ± 0.462
501612630.485 ± 356.2752.597 ± 0.539

the third point of Weakness 2: Moreover, the paper does not discuss existing work on generalization over varying entity compositions in large-scale StarCraft multi-agent settings, whose problem setting seems to be like the one studied here

Response to the third point of Weakness 2:We did not discuss this line of work in the original submission for the following reasons.

Existing work on large-scale StarCraft II broadly falls into two categories. The first studies full-game play, which requires agents to make both macro- and micro-level decisions. Full-game systems such as AlphaStar [1], TStarBot-X [2], and SCC [3] use league training to develop strategies against diverse opponents. The second studies combat scenarios in environments such as SMAC [4], where the focus is on unit-level micromanagement. Our study also considers full-game play, but asks whether a policy can generalize to unseen entity configurations. The full-game systems in [1–3] primarily address robustness to diverse opponents. To our knowledge, existing work has yet to systematically study generalization across entity configurations in full-game RTS settings. This distinction in scope explains why the original manuscript did not discuss StarCraft II generalization studies in detail.

Thank you for pointing this out. We will clarify it in the related work section of the revised manuscript.

[1] Grandmaster Level in StarCraft II Using Multi-Agent Reinforcement Learning

[2] TStarBot-X: An Open-Sourced and Comprehensive Study for Efficient League Training in StarCraft II Full Game

[3] SCC: An Efficient Deep Reinforcement Learning Agent Mastering the Game of StarCraft II

[4] SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning

Question 1: Since the task hypergraph construction requires some hand-written rules, could the author provide some ablation study results to determine how much the performance attribution comes from these hand-written rules?

Response to Question1: Question 1 raises the same concern as Weakness 1. Please see our response to Weakness 1.



Question 2: Could the author provide a discussion about the difference between their work and works on generalization over varying entity compositions in large-scale StarCraft multi-agent settings? Could these methods be applied to the RTS setting studied here, and if so, how do they compare with the proposed approach? If not, what prevents them from being applied?

the first point of Question2: Could the author provide a discussion about the difference between their work and works on generalization over varying entity compositions in large-scale StarCraft multi-agent settings?

Response to the first point of Question2: We addressed this issue in our response to the third point of Weakness 2. Please see our response to the third point in Weakness 2.


the second point of Question2: Could these methods be applied to the RTS setting studied here, and if so, how do they compare with the proposed approach? If not, what prevents them from being applied?

Response to the second point of Question2: The “these methods” you refer to cannot be directly applied to our current setting for the following reasons.

As noted in our response to the third point of Weakness 2, work on large-scale StarCraft II broadly falls into two categories. The first addresses macro- and micro-level decision-making in the full game. Even in a simpler environment such as µRTS, adapting these methods [1–3] would require substantial training time and data. In particular, µRTS lacks a collection of high-quality human replays comparable to that available for StarCraft II. These methods primarily address generalization across opponents, while we study generalization across entity configurations. The second category focuses on unit micromanagement in local combat scenarios. For example, SMAC [4] may pit three allied units against three enemy units, while our full-game setting requires decisions about production and economic development alongside combat. These differences in training requirements, generalization goals, and decision scope explain why we did not directly apply these methods.

[1] Grandmaster Level in StarCraft II Using Multi-Agent Reinforcement Learning

[2] TStarBot-X: An Open-Sourced and Comprehensive Study for Efficient League Training in StarCraft II Full Game

[3] SCC: An Efficient Deep Reinforcement Learning Agent Mastering the Game of StarCraft II

[4] SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning



Question 3: For the scalability and computational cost problem, what are the runtimes of the greedy and exact solvers? How do these grow with the number of entities, for example, on larger µRTS maps?

Response to Question3: Question 3 mainly asks how solver runtime changes as the number of entities increases. We addressed this issue in our response to the second point of Weakness 2. Solver runtime is determined entirely by the number of entities. As shown in Table 3, the recursive solver can exhibit exponential time complexity in the worst case, while the greedy solver’s runtime remains relatively stable. When there are many entities, the greedy solver can be used, since the win-rate gap between the two solvers is only about 3 percentage points (see Table 1 of the original manuscript).

Comments on the paper

4 comments
Area_Chair_HGSpOpenReview ↗

Please read the authors' response

Dear Reviewers,

We're halfway through the discussion phase. The authors have provided their responses to your reviews. If the response doesn't address your concern, please raise and leave some time for the authors to respond again. If yes, please still leave a comment. Let's engage with the authors and keep the conversation going.

Many thanks, AC

AuthorsOpenReview ↗

General Response

Dear Reviewers and Area Chair,

We sincerely thank all reviewers and the Area Chair for constructive feedbacks. We have provided detailed point-by-point responses and revised the manuscript accordingly. Below, we briefly clarify our contributions, address the major concerns, and summarize the revisions.

1. Research Focus and Contributions

Our work investigates compositional generalization across entity configurations in RTS games, where training and test scenarios share the same entity types, action space, interaction rules, and task objective, but differ in entity-type compositions and spatial layouts.

To address this problem, we propose: (1) a task hypergraph representation that models entities as nodes and multi-entity task instances as hyperedges; (2) a constrained hypergraph construction framework based on shared task schemas, feasibility constraints, and a set-level objective with exact recursive and efficient greedy solvers; and (3) a task hypergraph network combining hypergraph message passing, specialized action heads, relation encodings, and hyperedge-type-dependent soft biases.

2. Reviewer-Common Concerns

Common concerns are the need for more comprehensive experimental validation. We have therefore conducted additional experiments on (1) the effectiveness of domain knowledge, (2) sensitivity to hand-set hyperparameters, (3) generalization across map sizes, and (4) solver runtime. The results provide further empirical support for the effectiveness, robustness, and efficiency of our approach. Detailed results and analysis are available in our individual responses and revised manuscript.

3. Reviewer-Specific Concerns

Reviewer P7ou : the reviewer raised concern regarding the discussion of related work on generalization in large-scale StarCraft multi-agent settings. We clarify that much of the existing work in large-scale StarCraft settings focuses on generalization across opponents, whereas our work specifically investigates generalization across scenario-level entity configurations. Further details are discussed in our dedicated response.

Reviewer BieH:the reviewer raised concerns about the negative impacts of reliance on domain knowledge and whether any components of the task schemas or objective functions could be learned or adapted end-to-end to reduce reliance on domain knowledge. We acknowledge that reliance on explicitly specified domain knowledge can limit the transferability of our method to more complex and diverse environments. Nevertheless, we believe that incorporating domain knowledge directly remains necessary. As stated in [1], achieving generalization requires combining hand-engineering (domain knowledge) with end-to-end learning. The former provides inductive biases aligned with the problem structure, while the latter learns structured representations and decision rules from interaction data.

The introduction of domain knowledge actually reflects a trade-off: domain knowledge enables the policy to reuse task structures across different entity configurations within µRTS, while extending the task constructor to new environments requires additional specification and validation. In future work, we will continue to explore ways to better balance this trade-off.

[1] Relational inductive biases, deep learning, and graph networks

Reviewer tV6u:We have addressed the reviewer's concerns and clarified the relevant methodological details in our dedicated response. We have also conducted repeated experiments and report mean ± standard deviation over three independent runs to better characterize experimental variability.

4. Revised Manuscript

We have revised the manuscript, primarily expanding the experimental section to address the missing evaluations identified by the reviewers. All revised or newly added content is highlighted in blue in the revised manuscript PDF. Detailed explanations are provided in our point-by-point responses.

We sincerely appreciate the reviewers' valuable feedbacks and hope that our responses and revisions provide a clearer understanding of our contributions.

Thank you again for your time and consideration.

AuthorsOpenReview ↗

Clarify_____

Our approach incorporates domain knowledge at two levels. The first is the formulation of the constructor in terms of task schemas, feasibility constraints, and a set-level objective. Task schemas specify roles, admissible entity types, and role capacities, while the objective balances task utility against execution and resource costs. We believe this formulation is reusable across a broad range of RTS environments. The second level comprises the knowledge needed to instantiate that formulation in a particular environment, including concrete roles, validity conditions, and scoring terms. Much of the manual effort required to transfer the constructor to more complex environments arises at this level.

The trade-off is that explicit domain knowledge helps the policy reuse task structures across entity configurations within µRTS, while extending the constructor to more complex environments requires additional specification and validation.

As discussed in [1], achieving generalization involves combining hand-engineering with end-to-end learning. The former provides inductive biases aligned with the problem structure, while the latter learns structured representations and decision rules from interaction data. We believe that our reliance on prior knowledge should be considered alongside the methodological contributions and demonstrated benefits of our approach when assessing its value.In future work, we will furthermore improve this trade-off.

We hope you will reconsider the merits of our work in light of this discussion and consider revising your assessment more favorably.

[1] Relational inductive biases, deep learning, and graph networks

As discussed above, we would like to emphasize two points:

  1. The first level of domain knowledge—the formulation of the constructor in terms of task schemas, feasibility constraints, and a set-level objective—provides a reusable framework for a broad range of RTS environments.
  2. The hypergraph representation can also accommodate the multi-entity task relationships that arise in more complex RTS environments.

Although incorporating domain knowledge introduces additional specification and validation requirements, we believe our approach offers a promising foundation for broader applications. We sincerely hope you will consider these strengths alongside the demonstrated results and reconsider your current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.