  Multi-agent reinforcement learning (MARL) suffers from the non-stationarity
problem, which is the ever-changing targets at every iteration when multiple
agents update their policies at the same time. Starting from first principle,
in this paper, we manage to solve the non-stationarity problem by proposing
bidirectional action-dependent Q-learning (ACE). Central to the development of
ACE is the sequential decision-making process wherein only one agent is allowed
to take action at one time. Within this process, each agent maximizes its value
function given the actions taken by the preceding agents at the inference
stage. In the learning phase, each agent minimizes the TD error that is
dependent on how the subsequent agents have reacted to their chosen action.
Given the design of bidirectional dependency, ACE effectively turns a
multiagent MDP into a single-agent MDP. We implement the ACE framework by
identifying the proper network representation to formulate the action
dependency, so that the sequential decision process is computed implicitly in
one forward pass. To validate ACE, we compare it with strong baselines on two
MARL benchmarks. Empirical experiments demonstrate that ACE outperforms the
state-of-the-art algorithms on Google Research Football and StarCraft
Multi-Agent Challenge by a large margin. In particular, on SMAC tasks, ACE
achieves 100% success rate on almost all the hard and super-hard maps. We
further study extensive research problems regarding ACE, including extension,
generalization, and practicability. Code is made available to facilitate
further research.
