Scalable and Provable Decision-Making for Large-Population Multi-Agent Systems in Complex Domains