Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra
Giorgi Butbaia, Paul Orland, Coco Huang, Davide Passaro, Lucas Fagan, Michele Tarquini, Hailong Dao, David Eisenbud, Ali Shehper, Sergei Gukov
Abstract
Applying machine learning techniques to solving long-standing mathematical conjectures can be particularly challenging due to their extreme reward sparsity. As an illustrative example, we consider Kalai's algebraic Hirsch conjecture and recast the construction of its counterexamples as a sparse-reward reinforcement learning problem on graphs. We propose a constrained options-based HRL framework with an equivariant graph neural network policy, which allows us to learn useful temporal abstractions for this task. We evaluate our approach over a wide range of degrees and demonstrate that it consistently outperforms classical RL algorithms as well as greedy search. By exploiting the hierarchical structure of the problem, we effectively provide a first-of-its-kind application of HRL to a problem in commutative algebra.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement LearningAli Taghibakhshi, Scott P. MacLachlan, Luke N. Olson, Matthew WestNeurIPS 2021 · 43 citations
- Deep Equilibrium Algorithmic ReasoningDobrik Georgiev, Joseph Wilson, Davide Buffelli, Pietro LióNeurIPS 2024 · 7 citations
- Hierarchical Reinforcement Learning with Targeted Causal InterventionsMohammadsadegh Khorasani, Saber Salehkaleybar, Negar Kiyavash, Matthias GrossglauserICML 2025
- Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan CatanzaroNeurIPS 2020 · 77 citations
- Scaling Abstraction Refinement for Program Analyses in Datalog using Graph Neural NetworksZhenyu Yan, Xin Zhang, Peng DiOOPSLA 2024 · 1 citation
