Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning

Understand

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.