This talk will present new techniques for leveraging deep multi-agent reinforcement learning (MARL) to address NP-hard combinatorial optimization challenges, including the Traveling Salesman Problem (TSP) and Sequential Assignment Problem (SAP). These problems are relevant to a variety of real world systems, ranging from power grids, to satellite assignment, to transportation logistics. Traditional polynomial-time solutions to these problems are computationally expensive and fail to adapt to dynamic real-world conditions, such as the need for rapid re-routing due to unexpected events. Instead, we develop new techniques combining neural network-based reinforcement learning methods which bootstrap from traditional polynomial time solvers. For TSP, we use a genetic curriculum learning method to generate new problems for agents to solve, improving worst-case performance. For SAP, a decentralized MARL approach optimizes task assignments unfolding over time, while initializing estimates using greedy one-step solutions, significantly enhancing efficiency. These techniques have the potential to significantly reduce costs and improve efficiency across a range of systems use cases which require dynamic solutions to routing and assignment problems.