Reinforcement Learning of Theorem Proving
We introduce a theorem proving algorithm that uses practically no domain heuristics for guiding its connection-style proof search. Instead, it runs many MonteCarlo simulations guided by reinforcement learning from previous proof attempts. We produce several versions of the prover, parameterized by different learning and guiding algorithms. The strongest version of the system is trained on a large corpus of mathematical problems and evaluated on previously unseen problems. The trained system solves within the same number of inferences over 40% more problems than a baseline prover, which is an unusually high improvement in this hard AI domain. To our knowledge this is the first time reinforcement learning has been convincingly applied to solving general mathematical problems on a large scale.
This paper presents a theorem proving algorithm that leverages Monte-Carlo simulations guided by reinforcement learning  from previous proof searches. In particular, to guid the search, the authors use the UCT formula augmented by (1) learning prior probabilities of actions for certain proof states (policy learning), and (2) learning the values corresponding to the same proof states (policy evaluation). The proposed algorithm is using no domain engineering. The authors evaluate their proposal on two datasets: Miz40 and M2k. The evaluation shows the proposed solution outperforms state-of-the are by solving ~40% more problems.  This is a solid paper: it addresses a hard problem, and provide solutions that show significant improvements over the prior work. I have a few questions however, which mainly seek clarifications of the evaluation results: - You mention "We have also experimented with PUCT as in AlphaZero, however the results are practically the same." Can you provide some more color on this? How close were the results? Any tradeoffs? - Does rlCoP with policy and value guidance solve all the problems mlCoP solves on Miz40 dataset? If not, which problems does mlCoP solve and rlCoP doesn't? Same questions for rlCop with policy guidance vs mlCoP for the M2k dataset. - Is there anything special about the solutions shown in Sec 4.6 besides the fact they are more involving? It would be nice to provide some more intuition of why your algorithm perform well in those cases. - When you are training rlCoP on the Miz40 dataset how do you pick the problems in the training set? Randomly? How robust are the results to picking a different training set?  Minor: - "Published improvements in the theorem proving field are typically between 3 and 10 %." Can you please give some references to support your claim. - Please user either Mizar40 or Miz40 for consistency.