This paper describes the advantages of introducing learning capabilities into autonomous agents that make decisions at run-time about which mechanism to exploit in order to coordinate their activities. Specifically, the efficacy of learning is evaluated for making the decisions that are involved in determining when to coordinate. Our motivating hypothesis is that in dynamic and unpredictable environments it is important to have agents that can learn about the key factors which influence their decisions about when to attempt coordination. This hypothesis is evaluated empirically, using reinforcement based algorithms, in a grid-world scenario in which an agent cannot correctly predict the others? behaviour. The results presented show that having agents with learning capabilities is more effective in this context than having agents with no such abilities.