Abstract
In large-scale multiagent reinforcement learning (MARL), agents often struggle with credit assignment due to noisy global reward signals. This paper proposes a method to estimate "difference rewards" using function approximation. By modeling the global reward and calculating an agent's specific contribution, the approach significantly reduces noise and improves learning efficiency. Experiments on congestion-based benchmarks, including air traffic control simulations, demonstrate that modeled difference rewards can outperform raw global signals and scale effectively to hundreds of agents.
Introduction: The Credit Assignment Challenge
A central hurdle in MARL is the "credit assignment" problem. When hundreds of agents—such as autonomous vehicles or network nodes—receive a single global reward based on collective performance, the signal becomes highly noisy. An individual agent cannot easily discern whether a reward resulted from its own actions or the aggregate behavior of others.
Difference rewards ($D$) address this by isolating an agent's impact: $D = G(z) - G(z - z_i)$, where $G(z)$ is the system performance and $G(z - z_i)$ is the performance without agent $i$. However, in complex "black-box" systems, calculating the counterfactual $G(z - z_i)$ is often analytically impossible. This paper explores how to derive these signals when system dynamics are unknown.
Methodology: Reward Modeling
The authors propose using function approximation to learn a model of the global reward $G(z)$, which is then used to estimate difference rewards.
Function Approximators
Two types of models were evaluated:
- Tabular Linear Functions (TLFs): These use tables to store weights for discretized features, providing a flexible framework for discrete domains.
- Neural Networks: Employed for more complex, continuous environments like air traffic control.
The Bias Reducer Effect
A critical insight is that the subtraction operation in the difference reward calculation ($v(z) - v(z - z_i)$) acts as a natural bias reducer. Even if the learned model $v(z)$ contains systematic errors, these errors tend to cancel out, leaving a more accurate estimate of the agent's marginal contribution.
Training Strategies
Models were trained both offline (using pre-generated datasets) and online (learning concurrently with agent interaction). While offline training provided a stable baseline, online learning presented the challenge of a "moving target" as both the reward model and agent policies evolved.
Experimental Evaluation
The approach was tested on three benchmarks: the Multi-night Bar Problem (168 agents), FEATS (77 agents managing US national airspace), and a Generic Air Traffic Domain (up to 395 agents).
Key Results and Insights
The experiments yielded several significant findings:
- Performance Gains: In the Bar Problem, agents using modeled difference rewards achieved nearly a 200% performance increase over those using raw global rewards. In air traffic simulations, the method reduced costs (delays and congestion) by 25%.
- The Power of Subtraction: Surprisingly, learned models sometimes outperformed the "true" mathematical reward. In the Bar Problem, the model's approximation created a reward landscape that encouraged faster coordination.
- Scalability: As the system size grows, the advantage of modeled difference rewards becomes more pronounced. While global rewards fail to provide a useful signal in massive systems, the modeled approach scales effectively.
Conclusion
This research demonstrates that function approximation is a viable and powerful tool for deriving local credit assignment signals in complex multiagent systems. By filtering out background noise, modeled difference rewards enable efficient learning in environments where the global signal is too diluted to be useful. Future work will look into incorporating agent "states" to enable more complex, time-dependent strategies and improving the stability of simultaneous online learning.
Summary updated