Back to search

Cornell University

Deep Combinatorial Reasoning: From Games To Scientific Discovery

Abstract

dc:description.abstract

While significant strides have been made in deep reinforcement learning (RL), the intricacies of combinatorial realms, such as in AI planning and scientific discovery, continue to pose formidable challenges to RL methodologies. The main difficulty in these domains is that the occurrence of a positive reward signal becomes increasingly rare as the minimal solution length or the number of states dramatically increase. In this thesis, I will describe our deep combinatorial reasoning approach for tackling challenging problems with a significant combinatorial component. I will start by describing how the approach bridges the gap between specialized AI solvers and the state-of-the-art performance achieved by humans for Sokoban, a prototypical AI planning problem. Further, I will showcase the adaptability of our framework, illustrating its application to mass spectrometry prediction and metabolite identification. In the first part of the thesis, I will delve into the enhancement of traditional best-first search with various deep reinforcement learning techniques to improve performance in Sokoban. These techniques include sub-instance creation, curriculum training, and fully differentiable search, all of which strive to minimize the disparity between learning and searching. I will exemplify how this framework surpasses the expertise of human players in tackling challenging Sokoban instances, yielding both ingenious and efficient solutions. Subsequently, I will highlight the applicability of our deep combinatorial reasoning approach within the realm of scientific discovery, with a particular emphasis on mass spectrometry prediction. Our methodology exploits a Directed Acyclic Graph (DAG) representation of the fragmentation process, which enables the learning algorithm to swiftly pinpoint a small subset of states responsible for most of the fragmentation probability. Importantly, the unraveled fragmentation path is interpretable, fostering the rediscovery of numerous chemical rules based solely on the available data. In conclusion, our deep combinatorial reasoning approach exhibits flexibility and adaptability, making it suitable for tackling a myriad of challenging combinatorial problems that require a tight integration of AI reasoning and learning.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Feng, Dieqiao
Chair dc:contributor.chair
  • Selman, Bart
Committee members dc:contributor.committeemember
  • Kuleshov, Volodymyr
  • Gomes, Carla

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16454667
Dc Identifier Other
ProQuest Submission ID: 14001
ProQuest Publication ID: 30634509

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Feng, Dieqiao. Deep Combinatorial Reasoning: From Games To Scientific Discovery. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/115675