  A critical challenge in multi-agent reinforcement learning(MARL) is for
multiple agents to efficiently accomplish complex, long-horizon tasks. The
agents often have difficulties in cooperating on common goals, dividing complex
tasks, and planning through several stages to make progress. We propose to
address these challenges by guiding agents with programs designed for
parallelization, since programs as a representation contain rich structural and
semantic information, and are widely used as abstractions for long-horizon
tasks. Specifically, we introduce Efficient Multi-Agent Reinforcement Learning
with Parallel Program Guidance(E-MAPP), a novel framework that leverages
parallel programs to guide multiple agents to efficiently accomplish goals that
require planning over $10+$ stages. E-MAPP integrates the structural
information from a parallel program, promotes the cooperative behaviors
grounded in program semantics, and improves the time efficiency via a task
allocator. We conduct extensive experiments on a series of challenging,
long-horizon cooperative tasks in the Overcooked environment. Results show that
E-MAPP outperforms strong baselines in terms of the completion rate, time
efficiency, and zero-shot generalization ability by a large margin.
