CRII: III: Reinforcement Learning for Combinatorial Optimization in Societal Problems

A vast spectrum of real-world decision-making problems in domains such as public health can be formulated as combinatorial optimization problems (COPs). For example, a program may need to allocate screening services to a subset of people with symptoms in a community or a homeless youth shelter may need to invite a subset of people to participate in an educational program.

Both problems require identifying the most effective and timely subset of a group for inclusion. Solving these real-world problems is difficult as they involve large amounts of data. Combinatorial Optimization is a field that attempts to find solutions to these complex problems.

This project will build innovative technologies to efficiently solve the real-world COPs in public health. The main novelty is an Artificial Intelligence (AI)-based framework that addresses complex real-world COPs, which has been an open challenge for traditional non-machine learning based methods. The developed technologies will be able to assist the stakeholders to make more informed decisions about resource allocation and task scheduling, in a wide range of societal problems in public health, conservation, and more.

As an interdisciplinary research project, the research outcomes of this project will promote broader participation of AI research for communities outside of AI, and beyond academia. This project will get the AI research community more exposed to real-world societal problems and inspire more AI researchers to get involved in AI for social good research.

Moreover, this research will provide interdisciplinary experiential learning experiences to a cohort of graduate and undergraduate students under direct mentoring of the investigator, as well as the development of courses on the theme of Data Science and Society.

Due to the computational hardness of COPs, traditional algorithms for COPs rely on handcrafted heuristics to construct a solution. Such heuristics require domain knowledge and may be suboptimal. Recently, there have been increasing investigations that use reinforcement learning (RL) as an alternative approach to automate the search of these heuristics.

Despite the initial advancements, there is still a substantial gap when it comes to deploying RL for COPs in real life. This project identifies the following open challenges that are motivated by the above two problems in public health: (i) Hard objective functions (e.g., ill-shaped, or implicit); (ii) Uncertainty in problem parameters (or sim-to-real gap); and (iii) Multi-shot COPs.

The primary objective of this project is a fundamental RL system that addresses these open challenges. The project comprises three major research tasks, each with innovative RL solutions that target the corresponding open challenge. Research task #1 proposes the idea of physics-inspired (task-aware) graph representation learning to enhance function approximation in the RL framework for ill-shaped and implicit objective functions.

The new graph representation learning framework will incorporate the problem structure information into the design of the graph neural networks that better approximate the objective functions. Research task #2 designs a robust RL algorithm that deals with the uncertainties in the system parameters / sim-to-real gap, building on ideas from adversarial training and game theory that aims to better balance the trade-off between average-case and worst-case scenarios.

Research task #3 introduces the idea of a new hierarchical RL algorithm that jointly decides the budget allocation on the high level, and node selection on the low level. The two levels of RL are interdependent and will be trained interactively. These technical innovations will not only advance research on RL for COPs, but also research on deploying RL for real life in general.

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.