Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra
2026-06-22 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors explore how machine learning can help solve a difficult math problem called Kalai's algebraic Hirsch conjecture, which is hard because it gives very few clues about progress. They turn the problem into a special kind of decision-making task on graphs and use a hierarchy-based reinforcement learning method with a graph neural network to break down the task into manageable steps. Their approach works better than traditional methods across various problem sizes. This study is the first to apply hierarchical reinforcement learning to a problem in commutative algebra by leveraging the problem’s layered structure.
Kalai's algebraic Hirsch conjecturesparse-reward reinforcement learninghierarchical reinforcement learningequivariant graph neural networkstemporal abstractionscommutative algebragraph theorymachine learninggreedy search
Authors
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.