Frugal and Adaptive Testing – FATE

Testing is the process of gathering observations about an unknown system (for example a new drug and a placebo) in order to answer a question (e.g. which treatment is more efficient). Good testing protocols are such that the test can be stopped after few observations, while obtaining a correct answer with high probability. In applications where a large number of observations is available, like online advertising, algorithms that can adaptively change their future gathering of observations based on previously obtained information (called bandit algorithms) can be shown to stop as early as possible. In particular, they stop faster than non-adaptive algorithms. However the guarantees on the stopping time of these methods are insufficient for applications in which the number of observations available is small, like clinical trials. Nonetheless, experimental evaluation of bandit algorithms show promising performance in that case. The first goal of FATE is to adapt bandit algorithms to the regime where observations are scarce and to prove that they allow faster testing than less adaptive protocols.

Beyond the number of observations, a challenge of clinical trials is the long delay between administration of a drug and observation of the effect. Waiting for each observation before deciding which drug should be given to the next patient (full adaptivity) is not feasible. We will investigate how much adaptivity is needed to retain its benefits over non-adaptive protocols. Finally, some clinical tests have a double objective: find the best drug, while at the same time curing as many patients as possible. Optimal trade-offs between the two goals are unknown and our third objective is to find them and provide methods which attain them.