Vishal Gupta

Reinforcement learning is a promising solution to sequential decision-making problems, but its use has largely been limited to simulation environments and e-commerce. This chapter describes a large-scale deployment of reinforcement learning in Greece during the summer of 2020 to adaptively allocate scarce testing resources to incoming passengers amidst the evolving COVID-19 pandemic. Our system, nicknamed Eva, used limited demographic information and recent testing results to guide testing in order to maximize the number of asymptomatic but infected travelers identified over the course of the tourist season. Results from the field evaluation show a marked improvement over other “open- loop” testing strategies and highlight some of the challenges of deploying reinforcement learning in real-world, high-stakes settings.

In the summer of 2020, in collaboration with the Greek government, we designed and deployed Eva – the first national scale, reinforcement learning system for targeted COVID-19 testing. In this paper, we detail the rationale for three major design/algorithmic elements: Eva’s testing supply chain, estimating COVID-19 prevalence, and test allocation. Specifically, we describe the design of Eva’s supply chain to collect and process thousands of biological samples per day with special emphasis on capacity procurement. Then, we propose a novel, empirical Bayes estimation strategy to estimate COVID-19 prevalence among different passenger types with limited data and showcase how these estimates were instrumental for a variety of downstream decision-making. Finally, we propose a novel, multi-armed bandit algorithm that dynamically allocates tests to arriving passengers in a non-stationary environment with delayed feedback and batched decisions. All of our design and algorithmic choices emphasize the need for transparent reasoning to enable human-in-the-loop analytics. Such transparency was crucial to building trust and buy-in among policymakers and public health experts in a period of global crisis.

This chapter introduces the small-data, large-scale optimization regime, an asymptotic setting that arguably better describes certain data-driven optimization applications than the more traditional large-sample regime. We highlight unique phenomena that emerge in the small-data, large-scale regime, and show how these phenomena cause certain traditional data-driven optimization algorithms like sample average approximation (SAA) to fail. We then propose a new debiasing approach that has provably good performance in this regime, highlighting a new path forward for research and development into these types of applications.

Increased availability of high-quality customer information has fueled interest in personalized pricing strategies, i.e., strategies that predict an individual customer’s valuation for a product and then offer a customized price tailored to that customer. While the appeal of personalized pricing is clear, it may also incur large costs in the form of market research, investment in information technology and analytics expertise, and branding risks. In light of these trade-offs, our work studies the value of personalized pricing strategies over a simple single price strategy. We first provide closed-form lower and upper bounds on the ratio between the profits of an idealized personalized pricing strategy (first-degree price discrimination) and a single price strategy. Our bounds depend on simple statistics of the valuation distribution and shed light on the types of markets for which personalized pricing has little or significant potential value. Second, we consider a feature-based pricing model where customer valuations can be estimated from observed features. We show how to transform our aforementioned bounds into lower and upper bounds on the value of feature-based pricing over single pricing. Finally, we demonstrate how to obtain sharper bounds by incorporating additional information about the valuation distribution (moments or shape constraints) by solving tractable linear optimization problems.

Throughout the coronavirus disease 2019 (COVID-19) pandemic, countries have relied on a variety of ad hoc border control protocols to allow for non-essential travel while safeguarding public health, from quarantining all travellers to restricting entry from select nations on the basis of population-level epidemiological metrics such as cases, deaths or testing positivity rates^1,2. Here we report the design and performance of a reinforcement learning system, nicknamed Eva. In the summer of 2020, Eva was deployed across all Greek borders to limit the influx of asymptomatic travellers infected with severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), and to inform border policies through real-time estimates of COVID-19 prevalence. In contrast to country-wide protocols, Eva allocated Greece’s limited testing resources on the basis of incoming travellers’ demographic information and testing results from previous travellers. By comparing Eva’s performance against modelled counterfactual scenarios, we show that Eva identified 1.85 times as many asymptomatic, infected travellers as random surveillance testing, with up to 2–4 times as many during peak travel, and 1.25–1.45 times as many asymptomatic, infected travellers as testing policies that utilize only epidemiological metrics. We demonstrate that this latter benefit arises, at least partially, because population-level epidemiological metrics had limited predictive value for the actual prevalence of SARS-CoV-2 among asymptomatic travellers and exhibited strong country-specific idiosyncrasies in the summer of 2020. Our results raise serious concerns on the effectiveness of country-agnostic internationally proposed border control policies³ that are based on population-level epidemiological metrics. Instead, our work represents a successful example of the potential of reinforcement learning and real-time data for safeguarding public health.