CAREER: Enabling Combinatorial Decision Making in Stochastic Environments

决策是人类的一项核心活动，对个人、组织和社会生活至关重要，它是基于价值观和偏好来识别和选择替代方案的研究。对人工智能增强决策管道的需求只会增长，因为创新技术及其应用正在大规模快速引入。在解决现实世界的决策应用中固有的不确定性时，该项目旨在全面了解抽样方法在决策管道的不同阶段的效用，从模型设计到训练方法，再到模型解释。该项目重点关注决策问题，涉及从具有内在对称性的离散空间（如图和集合结构）中提取的查询和决策，并强调环境协变量由未知分布控制的场景。这项研究将使新的数据驱动的决策方法，不仅是数学原理，而且适用于各种应用领域，包括社会网络分析，实时和嵌入式系统，以及基于传感器的行星探索。这项研究还将产生可解释性技术，这些技术预计将提供与领域知识互补的见解，以更好地理解支持AI的机器所做的决策。此外，教育工作将致力于各种课程的课程设计，重点是算法和学习基础;有关的外联活动将继续鼓励代表性不足的群体以及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.