Grammar Reinforcement Learning: path and cycle counting in graphs with a Context-Free Grammar and Transformer approach
Jason Piquenot, Maxime Berar, Romain Raveaux, Pierre Héroux, Jean-Yves RAMEL, Sébastien Adam
Abstract
This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating transformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements.
BibTeX
@inproceedings{
piquenot2025grammar,
title={Grammar Reinforcement Learning: path and cycle counting in graphs with a Context-Free Grammar and Transformer approach},
author={Jason Piquenot and Maxime Berar and Romain Raveaux and Pierre H{\'e}roux and Jean-Yves RAMEL and S{\'e}bastien Adam},
booktitle={The Thirteenth International Conference on Learning Representations},
year={2025},
url={https://openreview.net/forum?id=yEox25xAED}
}