BCAM Scientific Seminar: Non-deterministic algorithms and reinforcement learning

Abstract:
In this talk we will see how any non-deterministic algorithm can be formulated as a Markov Decision Process (MDP). This allows to use techniques from (deep) reinforcement learning, dynamic programming, etc. in order to, roughly speaking, eliminate the non-determinism of the algorithm. 

This idea will be applied to the NP-hard problem of assessing the solvability of word equations. This problem is relevant both in areas such as algebra and theoretical computer science, and also in industry, where it finds different applications such as automatic code debugging, system security analysis, document spanning, etc.

Following the above ideas, we will construct a novel word equation solver based on some Monte Carlo Tree Search techniques, similar to the one employed by the chess-playing program AlphaZero. Incidentally, we also provide a dataset and problem generator on which current state-of-the-art solvers have serious difficulties and we also present a "wrapper" that can be used to enhance the performance of any solver with relatively little computational cost. We will finish by observing that this ideas are potentially applicable to many other combinatorial problems for which one has a suitable non-deterministic algorithm.

Click to see the poster