用强化学习发现更优的格约化策略，可零样本推广到高维
Discovering Lattice Reduction Strategies via Self-Play
- 将格约化建模为自对弈马尔可夫决策过程，用深度网络学习优化策略
- 新方法DeltaStar在8维上训练，比LLL少用操作数，且可直接推广至32维
- 无需重训练即可适应未知模数和更高维度，适合密码学与算法优化领域
LLL算法是计算机科学中经典的格基约化方法，但其多项式时间输出在维度升高时远非最优。本文证明，深度强化学习可通过与LLL原始操作空间交互，发现严格更优且可泛化的约化策略。我们将格约化建模为单玩家马尔可夫决策过程，采用类似AlphaZero的自对弈框架，并引入自适应步长蒙特卡洛树搜索（MCTS），结合多步网络预测与熵门控扩展机制。所提出的策略DeltaStar仅在8维q-元格上训练，所需原始行操作数少于LLL。关键的是，它能零样本推广至未见过的模数及高达n=32的高维，无需重新训练。
原文摘要 · Abstract (English)
The Lenstra-Lenstra-Lovász (LLL) algorithm is a seminal contribution to computer science used for lattice basis reduction, yet its polynomial-time outputs produce bases that are far from optimal as the dimension grows. We show that deep reinforcement learning can discover strictly superior, generalizable reduction strategies by interacting with the primitive action space of LLL. We formulate lattice reduction as a single-player Markov Decision Process (MDP) and train a deep residual network using an AlphaZero-style self-play pipeline augmented with adaptive-horizon MCTS (Monte Carlo Tree Search), which couples multi-step network predictions with an entropy-gated expansion mechanism. The resulting policy, DeltaStar, is trained exclusively on small $8$-dimensional $q$-ary lattices and requires fewer primitive row operations than LLL. Crucially, it generalizes zero-shot to unseen moduli and higher dimensions up to $n=32$ without retraining.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。