Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning
Aditya Kapoor, Sushant Swamy, Kale-ab Tessera, Mayank Baranwal, Mingfei Sun, Harshad Khadilkar, Stefano V. Albrecht · 2024
Read Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning by Aditya Kapoor, Sushant Swamy, Kale-ab Tessera, Mayank Baranwal, Mingfei Sun, Harshad Khadilkar, Stefano V. Albrecht (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14779.txt.
Introduction
Aditya Kapoor and co-authors address reward credit in multi-agent learning in a 2024 paper. When many agents learn together and rewards are rare or delayed, each agent struggles to tell which of its past actions helped. Long tasks make that judgment even harder, and learning can stall.
Their method, called TAR squared in plain terms, splits a sparse global reward across time steps and across agents by estimated contribution. The authors prove the split acts like a known reward shaping method, so the best policy stays the same. In tests, learning became steadier and faster. Added to single-agent learning methods, the approach matched or beat standard multi-agent methods, which broadens where it can be used.
Catalog record
| CREATOR | Aditya Kapoor, Sushant Swamy, Kale-ab Tessera, Mayank Baranwal, Mingfei Sun, Harshad Khadilkar, Stefano V. Albrecht |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14779
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning Aditya Kapoor, Sushant Swamy, Kale-ab Tessera, Mayank Baranwal, Mingfei Sun, Harshad Khadilkar, Stefano V. Albrecht 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 learning methods. 1 Introduction In cooperative multi-agent reinforcement learning (MARL), multiple autonomous agents learn to interact and collaborate to execute tasks in a shared environment by maximizing a global return ( Busoniu et al., 2008 ) . MARL has shown considerable potential in solving decentralized partially observable Markov decision processes (Dec-POMDPs) ( Oliehoek & Amato, 2016 ; Amato, 2024 ; Zhang et al., 2021 ) , where each agent has access to only local information (partial observation) and need to select actions based on their local action-observation (or sometimes only observation) histories to maximize the global (team) return. Applications of MARL include complex video games such as StarCraft-II ( Vinyals et al., 2019 ) , Defense of the Ancients (DOTA) ( Berner et al., 2019 ) , Google Football ( Kurach et al., 2020 ) , and Capture the Flag (CTF) ( Jaderberg et al., 2019 ) , and real world applications of warehouse logistics ( Krnjaic et al., 2022 ; Agrawal et al., 2023 ) , e-commerce ( Shelke et al., 2023 ; Baer et al., 2019 ) , robotics ( Sartoretti et al., 2019 ; Damani et al., 2021 ) , and routing problems ( Zhang et al., 2018 ; Vinitsky et al., 2020 ; Zhang et al., 2023b ) . These applications illustrate the potential of MARL to develop sophisticated strategies and behaviors through coordinated teamwork and collaboration. Despite these successes, cooperative multi-agent systems face a significant challenge in credit assignment, which is crucial for learning effective policies Foerster et al. (2018) . Credit assignment in multi-agent systems encompasses two main aspects: temporal credit assignment and agent credit assignment . Temporal credit assignment involves decomposing sparse, delayed rewards into intermediate time steps within a multi-agent trajectory. The assignment of agent credit focuses on discerning the contribution of each agent to these decomposed temporal rewards ( Albrecht et al., 2024 ) . Addressing both aspects is essential for effective learning in cooperative multi-agent systems. Significant progress has been made in addressing the credit assignment problem with methods such as VDN ( Sunehag et al., 2017 ) , QMIX ( Rashid et al., 2020 ) , QTRAN ( Son et al., 2019 ) , COMA ( Foerster et al., 2018 ) , and PRD ( Freed et al., 2021 ) . However, these methods are primarily designed to deal with agent credit assignment and may not be suitable for environments with sparse or delayed rewards ( Papoudakis et al., 2020 ; De Witt et al., 2020 ) . Additionally, the representations required for effective credit assignment might not align with those needed for learning Q-values or critics. Recent advances in temporal credit assignment have introduced dense reward functions in single-agent settings ( Arjona-Medina et al., 2019 ; Ren et al., 2021 ; Liu et al., 2019 ; Gangwani et al., 2020 ) and multi-agent settings ( Xiao et al., 2022 ; She et al., 2022 ) . These methods aim to learn a Markovian proxy reward function that replaces the environment’s sparse rewards with dense rewards. Motivated by this progress, we aim to address the combined challenge of agent and temporal credit assignment in multi-agent tasks with sparse or delayed rewards. In this paper, we propose Temporal-Agent Reward Redistribution (TAR 2 ), a novel approach to address the problem of agent-temporal credit assignment by learning a reward redistribution function that decomposes sparse environment rewards to each time step of the multi-agent trajectory and further redistributes the temporally decomposed rewards to each agent based on their contributions. We theoretically prove that there exists a class of reward redistribution functions that can be formulated as potential-based reward shaping ( Ng, 1999 ; Devlin & Kudenko, 2011 ) , under which the optimal policies are preserved in the original reward function of the environment. TAR 2 extends AREL’s ( Xiao et al., 2022 ) reward model that uses a temporal attention module to analyze the influence of state-action tuples along trajectories, followed by an agent attention module to identify the relevance of other agents for each agent. This alternation between the two attention modules allows the reward function to identify agent-specific state-action tuples that are key to the sparse environment rewards received by the multi-agent system. Thus, TAR 2 learns agent-specific temporal rewards and enables the use of single agent reinforcement learning (RL) algorithms such as IQL ( Tan, 1997 ) , IAC ( Foerster et al., 2018 ) , and IPPO ( Schulman et al., 2017 ; De Witt et al., 2020 ) to solve multi-agent tasks. This approach separates the problem of credit assignment from learning Q-functions and critics, leveraging the simplicity and scalability of single-agent RL algorithms in complex environments. We empirically demonstrate the sample efficiency of our approach against competitive state-of-the-art baselines on SMACLite ( Michalski et al., 2023 ) . In summary, our contribution is three folds:- • We introduce TAR 2 , a reward redistribution model that can be used to assign temporal and agent credit assignment to densify the reward signal. • We theoretically show that TAR 2 is equivalent to potential-based reward shaping which ensures that the optimal policy learned using TAR 2 is also optimal under the environment’s original reward function. • We theoretically prove that any intermediate policy gradient updates under TAR 2 and the environment’s original reward function share the same direction, ensuring that the trajectory of policy updates remains consistent across both reward functions. • We empirically validate our method on Alice & Bob, various battle environments in SMACLite ( Michalski et al., 2023 ) and various environment configurations of Google football ( Kurach et al., 2020 ) . 2 Related Works In this section, we review various techniques proposed to address temporal and agent credit assignment in both single-agent and multi-agent systems. We begin by discussing potential-based reward shaping, a method that provides theoretical guarantees of sample-efficient learning of optimal policies in single-agent ( Ng, 1999 ) and multi-agent ( Xiaosong Lu, 2011 ; Devlin & Kudenko, 2011 ) settings. The use of potential based shaping methods have shown to accelerate the learning process. 2.1 Temporal Credit Assignment Temporal credit assignment focuses on decomposing sparse or episodic environment rewards into dense reward functions by attributing credit to each time