acceptodds
Under review as a conference paper at ICLR 2027

Efficient Multi-Agent Reinforcement Learning under Sparse Binary Team Rewards with Few Suboptimal Prior Trajectories

Abstract

Learning efficient cooperative policies under sparse binary team rewards is particularly challenging when only a few suboptimal prior trajectories are available. Binary terminal feedback collapses trajectories of different qualities into identical outcomes, obscuring value estimation, while representative methods struggle to recover these hidden distinctions. We therefore propose TRACE, an online MARL framework that restores within-outcome reward resolution under binary feedback and converts the resulting trajectory-level supervision into discriminative transition-level learning signals. TRACE requires only the meaning of the original sparse binary reward and available terminal-state variables. Given this limited information and the proposed evaluator template, a fixed terminal-state graph evaluator can be instantiated either manually or with LLM assistance. The evaluator provides discriminative trajectory-quality scores within each outcome class while preserving success-failure separation. Uniform discount-aware relabeling then propagates this quality-derived terminal reward to preceding transitions without changing the induced policy ordering. Progressive prior-guided co-training integrates limited suboptimal priors with online experience while gradually reducing prior dependence. Across discrete-action SMAC v1/v2 and continuous-action MPE benchmarks, TRACE achieves the best overall training efficiency and performance. Further results show improved value discrimination, and robustness to prior quantity.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Sparse Binary Team Rewards, Few Suboptimal Prior Trajectories, Reward-Resolution Collapse, Sample Efficiency

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_YSdtOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The manuscript diagnoses a failure mode it terms intra-outcome-class reward-resolution collapse: under sparse binary team rewards, trajectories that share an outcome receive identical returns, so distinctions in task-relevant quality within success or failure are erased, and standard value learning cannot recover them from binary labels alone. TRACE addresses this by constructing a fixed terminal-state graph evaluator from the semantics of the original binary reward and the available terminal variables. The evaluator produces a within-class quality score, which is then propagated to preceding transitions through a discount-aware relabeling rule and exploited via prior-guided co-training with a decaying prior buffer and regularizer. The authors validate on SMAC v1/v2 and MPE Simple Spread, with ablations for the main modules, evaluator variants, prior count, and co-training hyperparameters.

Critical strengths
  1. The diagnostic study is the paper’s strongest asset. On 6h_vs_8z, the authors show substantial post-hoc quality variation among failed trajectories that all receive the same binary penalty, and they demonstrate that representative AIL, exploration, and offline-to-online methods recover that ordering only weakly or partially. This converts a vague complaint about sparse rewards into a measurable resolution problem, and it is the main reason the work merits serious consideration.
  2. The method is also simple, backbone-agnostic, and practically deployable. The evaluator is instantiated once and never queried during training; one evaluator is reused across all SMAC maps and another across all MPE settings. The ablation set is stronger than typical: TQR-Terminal isolates whether sparse terminal supervision alone suffices, while RandomTQR rules out the trivial explanation that any within-class variation helps. Gains are consistent across two action spaces and two backbones, and the prior-count study showing saturation at a few dozen trajectories is a useful practical finding.
Critical weaknesses
  1. The collapse result follows from the return definition, while the value and ordering results rely on assumptions that already assert the desired consistency and reduce to positive scaling; identifiability is therefore not established.
  2. No correlation is reported between evaluator scores and the post-hoc quality reference, so improved value alignment may reflect injected structure rather than recovered information; a length-correlated terminal bonus could yield similar results.
  3. The evaluator encodes health, alliance, proximity, and conflict priors, yet SimpleTQR already captures much of the gain and no misspecified or alternative evaluator is tested, leaving the graph contribution unclear.
  4. All non-terminal transitions receive the same value, so no within-trajectory credit assignment occurs and failed-trajectory returns become less negative with length; the scheme is not linked to potential-based shaping or return redistribution.
  5. Several baseline rows are identical across medium and medium-replay (LAIES in Table 3; MATD3, LAIES, CFCQL, MACal-QL in Table 4), with no significance testing, a short budget on hard maps, and TRACE behind ft-QMIX-DR on two dense-reward tasks.
  6. Prior-buffer admission and offline regularization are both evaluator-driven, so misspecification can be amplified; no diagnostic tracks drift from the reference distribution, and the assumed prior range is unverified on hard maps.
  7. Evaluation covers only SMAC v1/v2 and MPE Simple Spread, with no comparison to potential-based shaping, terminal-state intrinsic rewards, or return-redistribution baselines under the same prior budget, so gains may reduce to engineered terminal shaping.
Questions for authors
  1. What is the rank correlation between the evaluator’s own scores and the post-hoc quality reference, per map and per evaluator variant (LLM, SimpleTQR, RandomTQR)? Without this, what evidence supports recovery rather than construction?
  2. Since the relabeled reward is constant across all transitions of a trajectory, what is the precise mechanism by which the method produces transition-level rather than trajectory-level discrimination? Can you rule out the horizon-dependent incentive on failure trajectories?
  3. Tables 3 and 4 contain identical baseline entries across medium and medium-replay for LAIES, MATD3, CFCQL, and MACal-QL. Are these shared runs? If so, how do the two regimes differ for those methods?
  4. How does the relabeling scheme relate to potential-based shaping and episodic return redistribution? Is the ordering-preservation result anything beyond invariance to positive scaling?
  5. How was the performance range of the prior datasets verified on hard maps where the CFCQL “medium” policy may be close to random?
  6. Does the evaluator-based admission rule for the prior buffer bias the replay distribution toward the evaluator’s preferences, creating a feedback loop that amplifies evaluator misspecification? Do you have a diagnostic for this?
  7. What performance is obtained with a structured but deliberately misspecified evaluator, for example one with reversed within-class ordering, and what does this imply about the practical robustness of the stated assumptions?
1 comment

Thank you for the clarifications and additional experiments. The explanations of baseline reporting and the matched comparisons are helpful. However, the weak or negative correlations between evaluator scores and the paper’s quality reference leave my main concern about within-outcome quality recovery unresolved. The noise experiments also do not directly address systematic misranking by the evaluator. I therefore maintain my rating of 2 (weak reject) and confidence of 2.

Reviewer_t4isOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes TRACE for cooperative MARL with sparse binary team rewards and few suboptimal prior trajectories. TRACE combines a fixed terminal-state graph evaluator, discount-aware reward relabeling, and progressively decaying prior-guided co-training. The central idea is to introduce within-outcome trajectory-quality distinctions and make them available as transition-level learning signals.

Critical strengths
  1. Strong empirical results across discrete- and continuous-action tasks.

  2. Interpretable evaluators with reuse within each task family.

Critical weaknesses
  1. The advantage over dense reward shaping using the same task knowledge is insufficiently established.

Terminal-state evaluation can be easier than process-level reward design in principle. However, the instantiated evaluators use health, positions, landmark distances, and assignment conflicts—quantities that appear naturally usable during an episode. It is therefore unclear why constructing these scoring rules is substantially easier than using the same information for dense shaping.

The dense-reward comparison in Appendix C.3 is useful, but it uses the original environment rewards rather than shaping constructed from TRACE’s own features and task knowledge. Consequently, it does not isolate the benefit of terminal-only evaluation followed by uniform relabeling. A matched comparison that retains the backbone, prior data, and co-training mechanism while replacing relabeling with dense shaping would address this concern more directly. Without it, the necessity of the proposed reward-processing pipeline remains unclear.

  1. The additional design and training complexity is not sufficiently justified.

Beyond constructing the evaluator, TRACE requires graph and aggregation choices, outcome-dependent reward scaling, dual-buffer selection, counterfactual conservative regularization, and schedules for prior sampling and regularization. Thus, the framework may relocate the reward-design burden rather than substantially reduce the overall effort required to adapt the method to a new task.

I appreciate the shared evaluator settings and the sensitivity analyses for βstart\beta_{\mathrm{start}} and TdT_d. Nevertheless, these do not establish the portability of the full configuration or its benefit relative to simpler alternatives. Leave-one-module-out ablations show that components help within the chosen configuration, but do not demonstrate that comparable performance cannot be obtained with the same scoring information and simpler replay or shaping mechanisms. Comparisons under matched tuning budgets, together with wall-clock measurements, would better justify the additional complexity.

Questions for authors
  1. Since Proposition 3 preserves the recovered objective rather than the original binary objective, what prevents improved within-outcome scores from compensating for a lower success rate?

  2. What evidence supports the expectation-level within-outcome consistency required by Assumption 2? How robust is TRACE to systematic evaluator errors, rather than completely random scores?

  3. How is the standard off-policy TD update justified when relabeled immediate rewards depend on subsequent behavior actions? The trajectory-return identity alone does not establish equivalence of the corresponding TD updates.

Reviewer_uk1jOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript proposes TRACE, a framework for cooperative multi-agent reinforcement learning with sparse binary terminal rewards and a small prior trajectory dataset. Its central idea is to supplement success and failure feedback with a fixed evaluator of terminal multi-agent configurations. This evaluator uses task semantics and terminal-state variables to distinguish trajectories within the same outcome class. It then distributes the resulting terminal score across preceding transitions using a discount-aware rule and combines prior and online experience through progressively reduced conservative regularization and prior sampling. Experiments are over six SMAC v1 and v2 scenarios and three continuous-action MPE configurations, each under two prior-data regimes. This manuscript reports substantial improvements over the selected baselines, supported by component ablations, evaluator comparisons, value–quality correlation analyses, and sensitivity to prior quantity.

Critical strengths
  1. The reported empirical improvements are reasonably broad. TRACE achieves the highest reported AUC across all SMAC and MPE task/data combinations in Tables 3 and 4. The evaluation uses five runs and common online interaction budgets.
  2. The framework is simple and effective, and the ablations provide meaningful support for its design. The evaluator consists of explicit deterministic functions, remains fixed during learning, and is reused across a task family without ongoing LLM queries, which makes the additional supervision inexpensive and inspectable.
Critical weaknesses
  1. The trajectory-level policy-ordering result does not justify the TD control update, and the stated variable-length setting admits a counterexample. The rewards assigned to earlier transitions depend on the terminal score and episode length. Both of them can depend on later actions. Section 5.5 uses an ordinary TD target. A later action can therefore change rewards assigned to earlier transitions, while its TD value accounts only for the remaining rewards.
  2. The central contribution is insufficiently distinguished from task-informed reward shaping and existing reward redistribution. The 'reward-resolution collapse' proposition establishes that equal expected binary returns imply equal action values. Those values are correct for the specified binary objective. Introducing an additional preference over terminal health, cohesion, or landmark proximity changes the learning objective. The empirical question is therefore whether TRACE offers a distinctive and effective way to exploit this additional task knowledge.
Questions for authors
  1. How does the TD update in Section 5.5 account for actions changing rewards retrospectively assigned to earlier transitions? What assumption or implementation detail resolves the variable-length counterexample above?
  2. Appendix A.1 explicitly selects 50 successful trajectories for the two reused CFCQL datasets. Does success filtering also apply to the remaining environments and every nonzero prior-size setting in Figure 7?
  3. Appendix B.1.2 requires each agent to cover its assigned landmark, whereas Figure 11 describes coverage of every landmark by any agent, and the evaluator uses nearest-landmark proximity and assignment conflicts. Which success definition was implemented?
Reviewer_TjvqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes TRACE for cooperative MARL with sparse binary team rewards and a few suboptimal prior trajectories. The main idea is to score each trajectory with a fixed evaluator over its terminal state, q^(τ)=κy(τ)[fV(XT)+0.1fE(WT)]\hat q(\tau)=\kappa_{y(\tau)}[f_V(X_T)+0.1 f_E(W_T)] in Eq. 1, so that trajectories with the same binary outcome receive different terminal rewards. The evaluator is proposed by an LLM from the reward description and the terminal-state variables, and is fixed before training. TRACE then spreads this terminal score uniformly over all preceding transitions, which by Eq. 2 scales every trajectory return by 2. It also co-trains on a prior buffer with a decaying CFCQL-style regularizer. Experiments on six SMAC v1/v2 tasks and MPE Simple Spread use 50 prior trajectories and 5 seeds. In Table 3, TRACE reaches an average win-rate AUC of 46.38 on medium data, while the strongest baseline reaches 19.52.

Critical strengths
  • A clear and well-motivated diagnosis. Section 4.1 shows that failed trajectories with the same −1 reward differ substantially in quality. It also shows that the values learned by PegMARL and LAIES barely rank these trajectories, with ranking accuracy close to 0.5 in Figure 2.
  • Informative ablations. Figure 6 removes each module in turn. The TRACE-RandomTQR variant, which keeps outcome separation but uses random within-class scores, stays close to TRACE-noTQR. This shows that the gain comes from meaningful scores rather than from extra reward variance.
Critical weaknesses
  1. The evaluator re-creates the dense reward that the setting claims is unavailable. Appendix B.3.1 shows how the evaluators score trajectories:

    • In SMAC, a failed trajectory is scored by the remaining enemy health, and a successful one by the remaining ally health.
    • In MPE, trajectories are scored by agent–landmark proximity and by agents sharing a landmark.

    These closely mirror the standard SMAC damage-based reward and the Simple Spread reward, evaluated at the terminal state. As a result, the claim that TRACE "requires only the meaning of the original sparse binary reward" seems overstated. The setting reduces to RL with an LLM-designed terminal reward.

    This also makes Figure 5 nearly circular. The post-hoc reference qrefq_{\text{ref}} is the SMAC dense return, which for failed trajectories is largely determined by the damage dealt to enemies. A critic trained on enemy-health scores will naturally correlate with it, at a Spearman correlation of 0.871 and 0.898. Consistent with this, the SimpleTQR variant that only uses average ally health already gives a large gain in Figure 6. Also, in Table 5, TRACE beats ft-QMIX trained with the true dense reward, with an AUC of 46.38 against 36.84.

    I think the paper should frame the evaluator as reward design and compare it against LLM-based reward design such as Eureka [1].

  2. The comparison with baselines is not fair. All baselines receive only the binary reward, while TRACE receives the evaluator reward, the relabeling, and the prior co-training. Please report the strongest baselines, such as OVMSE and CFCQL, trained with the same evaluator reward and relabeling under the same codebase. This would isolate whether the gain comes from the evaluator signal or from TRACE's training pipeline.

    Also, the uniform relabeling in Section 5.4 is the same as the uniform return redistribution in IRCR [2]. Learned redistribution methods are neither cited nor compared: RRD [3], and AREL [4], which targets episodic MARL.

  3. The theory is mostly trivial, and the relabeling argument does not cover the TD update.

    • Section 4 states that two actions with equal expected binary return have equal Q-values.
    • Section 5.3 states that a strictly better recovered reward gives a strictly larger Q-value.
    • Eq. 2 only shows that relabeling doubles every trajectory return.

    However, the relabeled reward at step tt depends on the terminal outcome and on the episode length HH, so it is not a Markov reward. Therefore, the off-policy TD target with max⁡a′\max_{a'} in Section 5.5 does not inherit the ordering argument of Eq. 2. The authors should either analyze this case or tone down the term "policy-ordering-preserving".

[1] Ma et al. Eureka: Human-Level Reward Design via Coding Large Language Models. ICLR 2024.

[2] Gangwani et al. Learning Guidance Rewards with Trajectory-space Smoothing. NeurIPS 2020.

[3] Ren et al. Learning Long-Term Reward Redistribution via Randomized Return Decomposition. ICLR 2022.

[4] Xiao et al. Agent-Temporal Attention for Reward Redistribution in Episodic Multi-Agent Reinforcement Learning. AAMAS 2022.

Questions for authors

see weaknesses

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.