Abstract
In multi-agent environments, agents often struggle to learn optimal policies due to sparse or delayed global rewards, particularly in long-horizon tasks where it is challenging to evaluate actions at intermediate time steps. We introduce Temporal-Agent Reward Redistribution (TAR\(^2\)), a novel approach designed to address the agent-temporal credit assignment problem by redistributing sparse rewards both temporally and across agents. TAR\(^2\) decomposes sparse global rewards into time-step-specific rewards and calculates agent-specific contributions to these rewards. We theoretically prove that TAR\(^2\) is equivalent to potential-based reward shaping, ensuring that the optimal policy remains unchanged. Empirical results demonstrate that TAR\(^2\) stabilizes and accelerates the learning process. Additionally, we show that when TAR\(^2\) is integrated with single-agent reinforcement learning algorithms, it performs as well as or better than traditional multi-agent reinforcement learnin