Mobile networks are composed of many base stations and for each of them manyparameters must be optimized to provide good services. Automatically anddynamically optimizing all these entities is challenging as they are sensitiveto variations in the environment and can affect each other throughinterferences. Reinforcement learning (RL) algorithms are good candidates toautomatically learn base station configuration strategies from incoming databut they are often hard to scale to many agents. In this work, we demonstratehow to use coordination graphs and reinforcement learning in a complexapplication involving hundreds of cooperating agents. We show how mobilenetworks can be modeled using coordination graphs and how network optimizationproblems can be solved efficiently using multi- agent reinforcement learning.The graph structure occurs naturally from expert knowledge about the networkand allows to explicitly learn coordinating behaviors between the antennasthrough edge value functions represented by neural networks. We showempirically that coordinated reinforcement learning outperforms other methods.The use of local RL updates and parameter sharing can handle a large number ofagents without sacrificing coordination which makes it well suited to optimizethe ever denser networks brought by 5G and beyond.