# First-Order Problem Solving through Neural MCTS based Reinforcement Learning

arXiv: https://arxiv.org/abs/2101.04167 · HTML: https://mlsanity.com/paper/2101.04167/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 11 Jan 2021.

## Builds on (most cited first, 14 of 14)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study](https://mlsanity.com/paper/2006.05990/) (2020)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/1807.01672/) (2018)
- [Combining Q-Learning and Search with Amortized Value Estimates](https://mlsanity.com/paper/1912.02807/) (2019)
- [Learning Self-Game-Play Agents for Combinatorial Optimization Problems](https://mlsanity.com/paper/1903.03674/) (2019)

## Built on by (most cited first, 2 of 2)

- [Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework](https://mlsanity.com/paper/2110.08423/) (2021)
- [BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems](https://mlsanity.com/paper/2312.15864/) (2023)

## Abstract (arXiv)

The formal semantics of an interpreted first-order logic (FOL) statement can be given in Tarskian Semantics or a basically equivalent Game Semantics. The latter maps the statement and the interpretation into a two-player semantic game. Many combinatorial problems can be described using interpreted FOL statements and can be mapped into a semantic game. Therefore, learning to play a semantic game perfectly leads to the solution of a specific instance of a combinatorial problem. We adapt the AlphaZero algorithm so that it becomes better at learning to play semantic games that have different characteristics than Go and Chess. We propose a general framework, Persephone, to map the FOL description of a combinatorial problem to a semantic game so that it can be solved through a neural MCTS based reinforcement learning algorithm. Our goal for Persephone is to make it tabula-rasa, mapping a problem stated in interpreted FOL to a solution without human intervention.