Grammar Reinforcement Learning: Path and Cycle Counting in Graphs with a Context-Free Grammar and Transformer Approach
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.
Cite
Text
Piquenot et al. "Grammar Reinforcement Learning: Path and Cycle Counting in Graphs with a Context-Free Grammar and Transformer Approach." International Conference on Learning Representations, 2025.Markdown
[Piquenot et al. "Grammar Reinforcement Learning: Path and Cycle Counting in Graphs with a Context-Free Grammar and Transformer Approach." International Conference on Learning Representations, 2025.](https://mlanthology.org/iclr/2025/piquenot2025iclr-grammar/)BibTeX
@inproceedings{piquenot2025iclr-grammar,
title = {{Grammar Reinforcement Learning: Path and Cycle Counting in Graphs with a Context-Free Grammar and Transformer Approach}},
author = {Piquenot, Jason and Berar, Maxime and Raveaux, Romain and Héroux, Pierre and Ramel, Jean-Yves and Adam, Sébastien},
booktitle = {International Conference on Learning Representations},
year = {2025},
url = {https://mlanthology.org/iclr/2025/piquenot2025iclr-grammar/}
}