Sequential decision making under uncertainty: fundamental limits and applications

点击翻译按钮获取中文摘要

Sequential decision making (SDM) is an interactive process between a sequence of actions and observations: at each time, an action is taken by a decision-maker based on past data, which in turn affects the distribution of future observations. The problem is to come up with a strategy of selecting actions to achieve an overall objective, such as reaching a reliable conclusion as fast as possible, maximizing the cumulative rewards, etc. SDM tasks arise in a range of applications from different areas, including signal processing, clinical trials, personalized medicine, intelligent tutoring systems, online advertising, and recommendation systems, for which we aim to understand the fundamental limits and propose matching algorithms that are also computationally efficient. The major challenge is the complex dependence structure among observations induced by adaptive actions, which calls for a different set of tools than those for static data analysis. In this proposal, we investigate three themes in SDM with different formulations and applications. The first theme is on testing multiple hypotheses based on streaming data. In its simplest form, a decision-maker evaluates data as they arrive, and stops the sampling process until the evidence is strong enough for solving all the hypotheses. The goal is to minimize the sampling cost, while controlling error rates in some family-wise sense. We will also study the case where there exist sampling constraints (such as each time only a limited number streams can be observed) and/or different streams can have a separate stopping time. The second theme is on influencing and fast detecting a change-point. Motivated by applications such as online education, for which the goal is to actively help students master skills over time by adaptively administering educational items, we will consider a framework where the aim is to accelerate a hidden change, and then detect it as soon as possible, subject to false alarm constraint. The online procedures usually assume the knowledge of the dynamics, and we will also study the problem of offline model estimation. The third theme is on contextual bandit problem. Consider multiple treatments for a disease, whose efficacy depends on patients' characteristics (context), such as genes. As a new patient arrives, based on the context and past knowledge, the doctor needs to select a treatment, of which the outcome is observed. The goal is to minimize the regret against an oracle, who knows how the outcome depends on context and treatment. We will particularly consider the case where the context is high dimensional. The expected research outcomes will significantly advance the understanding and practice of SDM. We will document research results in top journals and incorporate the methodology into publicly released software such as R. This program will create and integrate educational opportunities for HQP, and support the training of 3 PhD students, 3 MSc students, and 2 USRAs.