aiqbench analysis
This paper investigates why neural networks fail to learn optimal strategies in impartial games like NIM, identifying a representational bottleneck where shallow quantized networks fall into the $\mathrm{AC}^0$ circuit class and cannot compute parity. The authors propose architectural solutions such as two-frame inputs and persistent recurrence to overcome these theoretical limits while retaining shallow network components. These findings offer critical insights into the boundaries of what neural architectures can represent, directly informing future designs for game-playing agents and complex sequential decision-making systems.
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
arXiv:2411.06403v4 Announce Type: replace Abstract: Why can neural networks struggle to learn optimal play in a game with a simple, efficient solution algorithm? Motivated by empirical difficulties with parity in impartial games, we use NIM to study a representational bottleneck and three ways around it. We show that a restricted model of shallow, fixed-scale quantised networks lies in $\mathrm{AC}^0$, a circuit class unable to compute parity on arbitrarily large inputs. This prevents optimal single-position play across all board sizes within the model. The obstruction also guides architectural design: two-frame inputs allow restoration from a known zero-nim-sum position; complementary rollout policies reveal the missing invariant; and persistent recurrence accumulates it row by row. Each route retains shallow network components while supplying additional information or processing time. Supervised experiments illustrate the benefits of two-frame restoration and multiple rollout heads; recurrence is a theoretical construction. These results establish representational possibilities, not guarantees of successful training: $\mathrm{AC}^0$ does not characterise practical learnability. Core mathematical results and constructions have been checked in Lean, with classical complexity results as explicit external inputs. The interactive edition and complete Lean sources are available online at https://sr123.github.io/impartial-games-learning-lean/.
Abstract:Why can neural networks struggle to learn optimal play in a game with a simple, efficient solution algorithm? Motivated by empirical difficulties with parity in impartial games, we use NIM to study a representational bottleneck and three ways around it. We show that a restricted model of shallow, fixed-scale quantised networks lies in $\mathrm{AC}^0$, a circuit class unable to compute parity on arbitrarily large inputs. This prevents optimal single-position play across all board sizes within the model. The obstruction also guides architectural design: two-frame inputs allow restoration from a known zero-nim-sum position; complementary rollout policies reveal the missing invariant; and persistent recurrence accumulates it row by row. Each route retains shallow network components while supplying additional information or processing time. Supervised experiments illustrate the benefits of two-frame restoration and multiple rollout heads; recurrence is a theoretical construction. These results establish representational possibilities, not guarantees of successful training: $\mathrm{AC}^0$ does not characterise practical learnability. Core mathematical results and constructions have been checked in Lean, with classical complexity results as explicit external inputs. The interactive edition and complete Lean sources are available online at this https URL.
48 pages, 8 figures. Substantially revised and retitled; adds persistent recurrence, Lean-checked constructions and an interactive edition. Interactive paper and Lean sources: this https URL
Artificial Intelligence (cs.AI)
F.1.1; I.2.6; I.2.8
arXiv:2411.06403 [cs.AI]
(or arXiv:2411.06403v4 [cs.AI] for this version)
Full text under the publisher's open licence · 224 words
