CAREER: Enabling Combinatorial Decision Making in Stochastic Environments

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

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.