On July 1st, 2020, members of the European Union lifted earlier COVID-19 restrictions on non-essential travel. In response, we designed and deployed ``Eva" – a novel bandit algorithm – across all Greek borders to identify asymptomatic travelers infected with SARS-CoV-2 based on demographic characteristics and results from previously tested travelers. Eva allocates Greece’s limited testing resources to (i) limit the importation of new cases and (ii) provide real-time estimates of COVID-19 prevalence to inform border policies. Counterfactual analysis shows that our system identified on average 1.85x as many asymptomatic, infected travelers as random testing, and up to 2-4x as many during peak travel. For most countries, Eva identified atypically high prevalence 9 days earlier than machine learning systems based on public data. By adaptively adjusting border policies 9 days earlier, Eva prevented additional infected travelers from arriving.