AF: Small: Online Decision-Making under Uncertainty: Prophets and Secretaries

在算法的理论研究中，我们经常假设最坏情况分析。这通常意味着，在将实例交给算法之前，我们对它有完全的不确定性，这太悲观了。然而，在实践中，这种假设通常并不完全正确，并且来自不同应用领域的优化问题的实例通常具有重要的结构。在这个项目中，我们利用在线决策算法输入的统计数据和分布信息来缓解悲观情绪。由于在电力市场、广告拍卖、动态机制设计、(强化)学习、投资程序、股票市场甚至联邦机构检查计划中的深刻应用，这种在线决策算法最近有了相当大的发展势头。我们的算法将建立并开发新的通用框架，用于解决上述现实生活场景中的算法问题。该项目将涉及博士生和博士后、本科生，甚至高中生(特别是少数族裔、女性、LGBT和残疾人的学生)，他们中的许多人将继续在其他学术机构和研究中心进行研究，进一步扩大该项目的影响。传统的在线环境要求我们随着时间的推移做出决定，因为投入是慢慢显现的，而不是(完全)对未来的了解。在这个项目中，我们研究关于投入需求的随机不确定性，这被认为是非常现实的，在过去已经被广泛研究。这个项目感兴趣的在线设置是“预言者”设置、“秘书”设置、“预言者秘书”设置以及“I.I.D.”。为他们每一个人设定，这位调查员已经有了开创性的工作和深刻的贡献。在预言家的设置中，需求来自可能事先已知的不同分布，而在秘书设置中，需求是以随机顺序到来的。在先知秘书的设置中，需求来自不同的分布(在不同的时间)，这些分布是随机排列的，但事先就知道了。最后，在身份证上。设置是以前所有设置的特例，需求始终来自相同的分布。在这些背景下，我们考虑基本问题以及在机构设计、网络设计和运动规划中的应用。这个项目的目标是结合来自停止理论、在线算法、机器学习、机械设计和运筹学等领域的工具，通过新技术解决该领域的重要研究挑战，并在这些领域之间建立更深层次的联系。我们将特别考虑实际应用以及我们的算法和基本原理的简单性，以适应现实世界的设置。我们还将把我们的发现融入到现有的和新的关于近似算法、机器学习基础和算法博弈论的课程中，并与统计学家和经济学家讨论进一步的整合。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

We often assume worst-case analysis in theoretical studies of algorithms. This often means we have complete uncertainty about an instance before it is handed to an algorithm, which is too pessimistic. In practice, however, often this assumption is not quite right and instances of optimization problems arising from different application domains often have significant structure. In this project we exploit statistical data and distribution information on inputs of online decision-making algorithms to relax the pessimistic view. Such online decision-making algorithms had considerable momentum lately due to profound applications in the electricity market, advertisement auctions, dynamic mechanism designs, (reinforcement) learning, investment procedures, stock market, and even federal agency inspection programs. Our algorithms will build on and develop new general frameworks for solving algorithmic problems in the above real-life scenarios. The project will involve Ph.D. students and postdocs, undergraduate students, and even high-school students (especially students among minorities, women, LGBT, and persons with disabilities), many of whom will continue their research at other academic institutions and research centers, further broadening the impact of this project.The classic online setting requires us to make decisions over time as the input is slowly revealed, without (complete) knowledge of the future. In this project we study stochastic uncertainty about input demands which are considered very realistic and has been widely studied in the past. Online settings of interest in this project are the ``prophet'' setting, the ``secretary'' setting, the ``prophet secretary'' setting, as well as the ``i.i.d.'' setting that for each of them, the investigator has already had pioneering work and deep contributions. In the prophet setting, demands are coming from possibly different distributions known in advance while in the secretary setting, demands are coming in a random order. In the prophet secretary setting, demands are coming from different distributions (at different times) which are randomly permuted but known in advance. Finally, in the i.i.d. setting, a special case of all previous settings, demands are coming from the same distribution all the time. In these settings, we consider fundamental problems as well as applications in mechanism design, network design, and motion planning. The goal of this project is to combine tools, from areas such as stopping theory, online algorithms, machine learning, mechanism design, and operations research to resolve important research challenges in the field via novel techniques and to forge deeper connections among these areas. We will have special considerations for practical applications and simplicity of our algorithms and underlying principles to real-world settings. We will also incorporate our discoveries into existing and new courses about approximation algorithms, foundations of machine learning, and algorithmic game theory, and discuss further incorporation with statisticians and economists.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.