Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra
For mathematicians and AI researchers, this provides a first application of hierarchical RL to a problem in commutative algebra, demonstrating a method to handle extreme reward sparsity in mathematical discovery.
The paper tackles the sparse-reward problem of constructing counterexamples to Kalai's algebraic Hirsch conjecture by framing it as a reinforcement learning task on graphs. Their hierarchical RL approach with equivariant graph neural networks consistently outperforms classical RL and greedy search across a range of degrees.
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.