In one embodiment, a service in a network computes an expected information gain associated with rerouting traffic from a first tunnel onto a backup tunnel in the network. The service initiates, based on the expected information gain, rerouting of the traffic from the first tunnel onto the backup tunnel. The service obtains performance measurements for the traffic rerouted onto the backup tunnel. The service uses the performance measurements to train a machine learning model to predict whether rerouting traffic from the first tunnel onto the backup tunnel will satisfy a service level agreement (SLA) of the traffic.