CAREER: Enabling Combinatorial Decision Making in Stochastic Environments

决策是一项对个人、组织和社会生活至关重要的核心人类活动，它是基于价值观和偏好识别和选择替代方案的研究。随着创新技术及其应用被迅速广泛地引入，对人工智能增强决策管道的需求只会增长。为了解决现实世界决策应用中固有的不确定性，本项目旨在全面理解采样方法在决策管道的不同阶段的效用，从模型设计到训练方法，再到模型解释。该项目专注于涉及从具有内在对称性的离散空间（如图和集合结构）绘制的查询和决策的决策问题，并强调环境协变量由未知分布控制的场景。这项研究将使新的数据驱动的决策方法成为可能，这些方法不仅具有数学原理，而且适用于各种应用领域，包括社会网络分析、实时和嵌入式系统以及基于传感器的行星探测。这项研究还将产生可解释性技术，预计将提供与领域知识互补的见解，从而更好地理解由人工智能支持的机器做出的决策。此外，教育工作将致力于各种课程的课程设计，重点是算法和学习基础；有关的外展活动将继续鼓励代表性不足的群体以及K-12学生的参与。该项目的技术目标分为三个重点。最初的探索旨在从理论上理解由组合和随机核增强的决策管道的可行性和性能；这将通过函数近似分析和泛化分析的共同努力来实现。其次，由于组合过程的不可微性和np -硬度，在决策管道中涉及组合过程不可避免地给模型训练带来挑战；本项目将首先探索离散凸性的概念，用于解决一般设置下的推理问题，然后设计可以通过自适应采样解决最小-最大近似硬度的训练方案。最后，根据环境变量之间的组合依赖关系，通过开发衡量模型等效性的新概念，本项目将开发用于推断学习决策模型的主要成分的方法，该模型可用于解释环境变量在决定决策质量中的作用。所追求的框架的实际效用将通过对现实世界数据集和测试平台的实证研究来补充。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Decision-making, a central human activity fundamental to individual, organizational, and societal life, is the study of identifying and choosing alternatives based on values and preferences. The need for AI-enhanced decision-making pipelines will only grow, as innovative technologies and their applications are introduced speedily on a broad scale. In addressing the inherent uncertainties in real-world decision-making applications, this project seeks to provide a comprehensive understanding of the utility of sampling methods in different stages of a decision-making pipeline, from model design, to training methods, to model explaining. This project sharply focuses on decision-making problems that involve queries and decisions drawn from discrete spaces with intrinsic symmetries, such as graphs and set structures, and emphasizes scenarios where the environment covariates are governed by unknown distributions. This investigation will enable new data-driven decision-making methodologies that are not only mathematically principled but also applicable to various application sectors, including social network analysis, real-time and embedded systems, and sensor-based planetary exploration. This research will also result in explainability techniques that are projected to offer insights that are complementary to domain knowledge towards a better understanding of the decisions made by AI-enabled machines. Furthermore, educational efforts will be devoted to the curriculum design of various courses, with the emphasis on algorithmic and learning foundations; the involved outreach activities will continue to encourage the participation of underrepresented groups as well as K-12 students. The technical aims of the project are grouped into three thrusts. The initial exploration seeks to theoretically understand the feasibility and performance of decision-making pipelines that are enhanced by combinatorial and randomized kernels; this will be achieved through a joint effort of function approximation analysis and generalization analysis. Second, having combinatorial processes being involved in the decision-making pipeline inevitably brings about challenges in model training due to their indifferentiability and NP-hardness; this project will first explore the concept of discrete convexity for solving the inference problem under general settings, and then design training schemes that can resolve the min-max approximation hardness through adaptive sampling. Finally, by developing new concepts for measuring model equivalence in terms of the combinatorial dependence between the environment variables, this project will develop methodologies for inferring the principal components of the learned decision-making model, which can be used to explain the role of environment variables in determining decision qualities. The practical utility of the pursued framework will be supplemented by empirical studies on real-world datasets and testbeds.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.