Techniques for determining network paths for voice calls include analyzing network path measurements of the network paths to determine historical network performance data for the network paths, and identifying a group of top-k network paths based on those network paths having better network performance data other network paths. A particular network path may be selected using various techniques, such as selecting the network path with the best historical network performance, selecting a network path by applying a multi-armed bandit algorithm to select the path from the group of top-k network paths, or selecting a network path at random. The selected network path may be used to by a source-destination pair of computing devices for a voice call, and a record of that voice call may be used to update network performance information for the particular network path.