用强化学习自动选多项式排序，比传统方法快得多
Learning Fast Monomial Orders for Gröbner Basis Computations
- 把排序选择变成强化学习任务，用计算成本做奖励信号
- 在生物系统和视觉任务上，计算时间显著减少
- 学出的策略难以用简单规则解释，说明发现了新规律
Gröbner基计算是求解多项式方程组的标准方法，其效率高度依赖于单项式序的选择。尽管存在近乎连续的单项式序空间，多数实现仍依赖如GrevLex等静态启发式策略，主要基于专家直觉。本文将单项式序选择建模为在可接受序空间上的强化学习问题，利用反映计算成本的领域感知奖励信号，并支持高效的蒙特卡洛估计。在系统生物学和计算机视觉基准问题上的实验表明，所学策略持续优于标准启发式，大幅降低计算开销。此外，这些策略无法被简化为可解释的模型，为深度强化学习能捕捉传统启发式无法触及的非线性几何结构提供了实证支持。
原文摘要 · Abstract (English)
The efficiency of Gröbner basis computation, the standard engine for solving systems of polynomial equations, depends on the choice of monomial ordering. Despite a near-continuum of possible monomial orders, most implementations rely on static heuristics such as GrevLex, guided primarily by expert intuition. We address this gap by casting the selection of monomial orderings as a reinforcement learning problem over the space of admissible orderings. Our approach leverages domain-informed reward signals that accurately reflect the computational cost of Gröbner basis computations and admits efficient Monte Carlo estimation. Experiments on benchmark problems from systems biology and computer vision show that the resulting learned policies consistently outperform standard heuristics, yielding substantial reductions in computational cost. Moreover, we find that these policies resist distillation into simple interpretable models, providing empirical evidence that deep reinforcement learning allows the agents to exploit non-linear geometric structure beyond the scope of traditional heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。