  This paper proposes a novel multi-agent reinforcement learning (MARL) method
to learn multiple coordinated agents under directed acyclic graph (DAG)
constraints. Unlike existing MARL approaches, our method explicitly exploits
the DAG structure between agents to achieve more effective learning
performance. Theoretically, we propose a novel surrogate value function based
on a MARL model with synthetic rewards (MARLM-SR) and prove that it serves as a
lower bound of the optimal value function. Computationally, we propose a
practical training algorithm that exploits new notion of leader agent and
reward generator and distributor agent to guide the decomposed follower agents
to better explore the parameter space in environments with DAG constraints.
Empirically, we exploit four DAG environments including a real-world scheduling
for one of Intel's high volume packaging and test factory to benchmark our
methods and show it outperforms the other non-DAG approaches.
