Complex health problems require multi-strategy, multi-target interventions. We present a method that uses machine learning techniques to choose optimal interventions from a set of possible interventions within a case study aiming to increase General Practitioner (GP) discussions of physical activity (PA) with their patients. Interventions were developed based on a causal loop diagram with 26 GPs across 13 clinics in Geelong, Australia. GPs prioritised eight from more than 80 potential interventions to increase GP discussion of PA with patients. Following a 2-week baseline, a multi-arm bandit algorithm was used to assign optimal strategies to GP clinics with the target outcome being GP PA discussion rates. The algorithm was updated weekly and the process iterated until the more promising strategies emerged (a duration of seven weeks). The top three performing strategies were continued for 3 weeks to improve the power of the hypothesis test of effectiveness for each strategy compared to baseline. GPs recorded a total of 11,176 conversations about PA. GPs identified 15 factors affecting GP PA discussion rates with patients including GP skills and awareness, fragmentation of care and fear of adverse outcomes. The two most effective strategies were correctly identified within seven weeks of the algorithm-based assignment of strategies. These were clinic reception staff providing PA information to patients at check in and PA screening questionnaires completed in the waiting room. This study demonstrates an efficient way to test and identify optimal strategies from multiple possible solutions.