CAREER: Enabling Combinatorial Decision Making in Stochastic Environments

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.