교환대수에서의 희소 보상 탐색을 위한 계층적 강화 학습

Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra

기계 학습 기법을 사용하여 오랜 기간 동안 제기된 수학적 추측 문제를 해결하는 것은 극심한 보상 희소성으로 인해 특히 어렵습니다. 예시로, 우리는 칼라이의 대수 하이르슈 추측을 고려하고, 그 반례를 구성하는 과정을 그래프 상에서의 희소 보상 강화 학습 문제로 재구성했습니다. 우리는 등변 그래프 신경망 정책을 갖춘 제약 조건 기반 옵션 기반 계층적 강화 학습 프레임워크를 제안하며, 이를 통해 이 작업에 유용한 시간 추상화를 학습할 수 있습니다. 다양한 차수에 대해 우리의 접근 방식을 평가한 결과, 기존의 강화 학습 알고리즘 및 탐욕적인 검색 방법보다 일관되게 우수한 성능을 보였습니다. 우리는 문제의 계층적 구조를 활용하여 교환 대수 분야에서 계층적 강화 학습을 적용하는 최초의 사례를 제공합니다.

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.