Deep Reinforcement Learning Discovers Superior Lattice Reduction Strategies

This research demonstrates that deep reinforcement learning can uncover lattice reduction strategies that are superior to the long-standing Lenstra-Lenstra-Lovász (LLL) algorithm. While LLL is a foundational algorithm in computer science, its outputs become suboptimal in higher dimensions. The study frames lattice reduction as a single-player Markov Decision Process. A deep residual network was trained using an AlphaZero-style self-play pipeline, enhanced with adaptive-horizon Monte Carlo Tree Search (MCTS). This MCTS couples multi-step network predictions with an entropy-gated expansion mechanism. The resulting policy, named DeltaStar, was trained exclusively on small 8-dimensional q-ary lattices. Crucially, it requires fewer primitive row operations than LLL and exhibits zero-shot generalization to unseen moduli and higher dimensions, up to n=32, without any retraining.