Implicit Credit Learning for Sparse-Reward Multi-Agent Reinforcement Learning
Authors: The Viet Bui, Tien Mai, Hong Thanh Nguyen
Organizations: School of Computing and Information Systems Singapore Management University, Singapore · University of Oregon Eugene, Oregon United States
When a cooperative team receives feedback only at the end of an episode, a single outcome must guide many agents' earlier actions. Learning a dense team reward helps, but its decomposition does not automatically give each agent a useful policy update. We introduce IMAP, an online method that fits a shared Q/V reward model by comparing completed episodes according to their observed terminal outcomes. Local Q/V residuals provide agent-specific rewards; the same normalized weights combine them for a centralized critic and scale local advantages for decentralized PPO actors. We characterize when these local updates follow the learned team objective. With full returns and frozen reward heads, a sharp bound relates their gradient error to variation in future Q/V compatibility; an exact identity identifies additional continuation terms for general GAE. In experiments with terminal-only feedback, IMAP's local-actor configuration attains the highest reported mean among the compared methods on all nine SMACv2 scenarios and four MAMuJoCo tasks, and on two of three SMACLite scenarios. Controlled relay interventions confirm the predicted changes in actor credit while holding the learned team reward fixed. The gradient result concerns the fitted objective; benchmark returns measure performance on the original task outcomes.
Figures & tables
Figure 1: IMAP learns from sparse team outcomes. Completed episodes train a shared Q/V reward model; its local residuals supply a mixed reward for the centralized critic and agent-specific advantages for decentralized actors. Outcome comparisons are computed from the observed terminal returns.
Figure 2: Global and weighted local actor readouts on SMACv2. Both use the same Q/V reward-model design and a global critic; curves show win rate over 10M steps.
Figure 3: Global and weighted local actor readouts on MAMuJoCo, with the same Q/V reward-model design and global critic. IMAP-LA has higher final means after 10M steps.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
SMACv2
MAMuJoCo
Actor / critic learning rate
0.0005
0.0003
Discount / GAE
0.99 / 0.95
0.99 / 0.95
PPO clipping / epochs
0.2 / 10
0.2 / 10
PPO minibatch size
256
512
Entropy coefficient
0.01
0.01
Parallel environments
8
8
Appendix
Table 4: Benchmark training settings. The relay uses the separate settings below.
Figure 4: MAMuJoCo comparison with the benchmark baselines. IMAP (ours) denotes the terminal-outcome IMAP-Rule/LA configuration; this figure supplements the main-text GA/LA ablation.
Output shift
Mean
Sample SD
Seed range
Joint Q/V
0.00605
0.00275
[0.00236,0.01026]
Q-only
0.11496
0.05218
[0.04488,0.19488]
Appendix
Table 6: Variation across the ten fixed reference models at training λ=0.95 and unit amplitude ζ=1 . Values use the normalized response in Equation ( 73 ); SD and range are across seeds, not grid cells.
Figure 5: Local-credit sensitivity at unchanged mixed reward. (a,b) Mean response Δλ(ζ) over ten frozen models; shared color scale and dashed training λ=0.95 . Joint Q/V shifts preserve compatibility; Q-only shifts change it. (c) Full-return Fisher error versus the Theorem 1 bound for all 440 checkpoints; maximum error/bound ratio 0.2620 , with diagonal denoting equality. All panels use the frozen learned-return objective.
Figure 6: The attaining two-agent family at λ=1 , α=(0,1) and εQ=ε=1 . Analytic error and bound coincide at LH/2 . Six saved finite-model checks occupy five distinct coordinates; strictly positive mixers approach the same constant.
ζ
Positive alignment
Negative alignment
Oracle-scale certified
−2
60
0
0
−1
60
0
0
−0.5
60
0
0
0
60
0
6
0.5
60
0
0
1
57
3
0
Appendix
Table 9: Every prescribed intervention at the final fitting checkpoint. Each row contains 60 cases. The six certificates at ζ=0 repeat the six final cases in Table 7 . Return-scale certification is zero at every amplitude.
Figure 7: All 480 frozen product-action interventions. The horizontal coordinate is (Bcred+δg)/(agCfloor) ; the vertical coordinate is the cosine between gY and gL in F−1 geometry. Outlined points are certified and all have positive alignment. Many points outside the certificate region are also positive: failure of the sufficient test does not imply failure of the direction. The calibration scale is oracle, and the six outlined points are the unshifted controls already counted in Table 7 .
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.
To promote cooperation in Multi-Agent Reinforcement Learning, the reward signals of all agents can be aggregated together, forming global rewards that are commonly known as the fully cooperative setting. However, global rewards are usually noisy because they contain the contributions of all agents, which have to be resolved in the credit assignment process. On the other hand, using local reward benefits from faster learning due to the separation of agents' contributions, but can be suboptimal as agents myopically optimize their own reward while disregarding the global optimality. In this work, we propose a method that combines the merits of both approaches. By using a graph of interaction between agents, our method discerns the individual agent contribution in a more fine-grained manner than a global reward, while alleviating the cooperation problem with agents' local reward. We also introduce a practical approach for approximating such a graph. Our experiments demonstrate the flexibility of the approach, enabling improvements over the traditional local and global reward settings.
Bang Giang Le, Viet Cuong Ta
Human-Machine Interaction Laboratory VNU University of Engineering and Technology, Hanoi, Vietnam
Cooperative tasks in Multi-Agent Reinforcement Learning (MARL) require agents to collectively maximize a shared return. Under the Centralized Training with Decentralized Execution (CTDE) paradigm, policy gradients have remained difficult to compute directly. Prior methods largely follow two approaches: independent factorized updates with centralized critics, which lack general joint-improvement guarantees without value decomposition assumptions, or alternating best-response updates, which can converge to suboptimal Nash Equilibria. In this paper, we show the joint policy gradient admits an exact decentralized decomposition of per-agent terms, each formed from per-agent score functions and decentralized critics. Based on this decomposition, we develop Agent-Chained Policy Optimization (ACPO), where actors are trained independently, with their updates together constituting a single step on the joint policy gradient. Central to this result is a serialized view of the simultaneous joint decision in which agents commit actions one at a time, each conditioning on a belief over preceding actions. The belief acts as the coordination mechanism which ties the independent per-agent updates into a joint gradient step. We evaluate ACPO on Multi-Robot Warehouse, SMACv2, and MA-MuJoCo, where it outperforms strong baselines, with the gap widening as the number of agents grows.
Daiki E. Matsunaga, Junho Na, Tri Wahyu Guntara +4
Cooperative multi-agent reinforcement learning under partial observability and shared rewards requires assigning team outcomes to individual agents and high-order coalitions. A MAPPO-style critic compresses joint behavior into one global value, while critics that dynamically reconstruct the grouping topology change the mapping from agents and coalitions to value components as interactions or active agents evolve. We refer to this inconsistency as structural target drift. We introduce HySTAR, a MAPPO-based framework that separates adaptive representation learning from a temporally consistent high-order value-decomposition basis. HySTAR anchors an overlapping sparse hypergraph as a uniformly covered decomposition scaffold, uses a spatiotemporal encoder to represent physical and task-dependent interactions, and combines temporal and structural relevance to construct agent-specific advantages. Experiments on SMAC, GRF, Traffic Junction, and MPE demonstrate consistent improvements over MAPPO-style, value-factorization, and dynamic-grouping baselines. On the hardest SMAC settings, HySTAR achieves relative gains of 16.7% over MAPPO and 15.6% over HYGMA, ranks first on all six GRF scenarios, reduces Traffic Junction convergence epochs by up to 40.2% relative to MAGIC, and obtains the highest MPE episode rewards. Controlled topology, agent-death, neighborhood, and parameter analyses support the benefit of anchoring the decomposition scaffold while adapting the propagated representations.
Xinglong Luo, Yuding Zhang, Yuheng Kuang +5
University of Electronic Science and Technology of China · Independent Researcher