Sequential decision making under uncertainty: fundamental limits and applications

序贯决策（SDM）是一系列行动和观测之间的交互过程：在每一个时刻，决策者根据过去的数据采取行动，这反过来又影响未来观测的分布。问题是要想出一个选择行动的策略，以实现一个整体目标，如尽可能快地得出一个可靠的结论，最大化累积奖励等SDM任务出现在一系列应用程序从不同的领域，包括信号处理，临床试验，个性化医疗，智能辅导系统，在线广告和推荐系统，为此，我们的目标是了解基本的限制，并提出匹配算法，也是计算效率。主要的挑战是由自适应行为引起的观测之间的复杂依赖结构，这需要一套不同于静态数据分析的工具。在这个建议中，我们调查三个主题在SDM与不同的配方和应用。第一个主题是基于流数据测试多个假设。在最简单的形式中，决策者在数据到达时对其进行评估，并停止采样过程，直到证据足够强大，足以解决所有假设。我们的目标是尽量减少抽样成本，同时在某种意义上控制错误率。我们还将研究存在采样约束（例如每次只能观察到有限数量的流）和/或不同流可以具有单独的停止时间的情况。第二个主题是影响和快速检测一个变化点。受在线教育等应用程序的启发，其目标是通过自适应管理教育项目来积极帮助学生随着时间的推移掌握技能，我们将考虑一个框架，其目的是加速隐藏的变化，然后尽快检测到它，受到虚警约束。在线程序通常假设的动态知识，我们也将研究离线模型估计的问题。第三个主题是语境强盗问题。考虑对一种疾病进行多种治疗，其疗效取决于患者的特征（背景），如基因。当一个新的病人到达时，根据背景和过去的知识，医生需要选择一种治疗方法，并观察其结果。我们的目标是尽量减少对神谕的遗憾，谁知道结果如何取决于上下文和治疗。我们将特别考虑上下文是高维的情况。预期的研究成果将大大促进对可持续发展机制的理解和实践。我们将在顶级期刊上记录研究结果，并将该方法纳入公开发布的软件，如R。该计划将为HQP创造和整合教育机会，并支持3名博士生，3名硕士生和2名USRA的培训。

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.