Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning
Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning

  • Author(s): Lederman, Gil
  • Rabe, Markus N
  • Lee, Edward A
  • Seshia, Sanjit A
  • et al.
Abstract

We demonstrate how to learn efficient heuristics for automated reasoning algorithms for quantified Boolean formulas through deep reinforcement learning. We focus on a backtracking search algorithm, which can already solve formulas of impressive size - up to hundreds of thousands of variables. The main challenge is to find a representation of these formulas that lends itself to making predictions in a scalable way. For a family of challenging problems, we learned a heuristic that solves significantly more formulas compared to the existing handwritten heuristics.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View