arXiv cs.AI· S{\o}ren Riis·· 3 天前AI 评分22
如何突破无偏博弈的学习瓶颈：一种电路复杂度方法
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
AI 导读
针对神经网络在无偏博弈中难以学会最优策略的问题，研究者以 NIM 游戏为例，证明浅层固定规模量化网络属于 AC⁰ 电路类，无法计算任意大输入的奇偶性，因而无法在所有棋盘规模上实现最优单步走子。
正文 · AI 翻译
摘要：为什么神经网络在一个拥有简单高效求解算法的游戏中难以学会最优策略？受无偏博弈中奇偶性经验困难的启发，我们使用 NIM 来研究一种表示瓶颈及其三种绕行方法。我们证明，一种受限的浅层、固定规模量化网络模型属于 $\mathrm{AC}^0$，这是一个无法计算任意大输入奇偶性的电路类。这阻碍了该模型在所有棋盘尺寸上的最优单步走子。这一障碍也指导了架构设计：双帧输入允许从已知零 nim 和位置恢复；互补的 rollout 策略揭示了缺失的不变量；而持续递归则逐行累积它。每条路径都保留了浅层网络组件，同时提供额外信息或处理时间。监督实验说明了双帧恢复和多个 rollout 头的优势；递归是一种理论构造。这些结果确立了表示可能性，而非成功训练的保证：$\mathrm{AC}^0$ 并不刻画实际可学习性。核心数学结果和构造已在 Lean 中检查，经典复杂性结果作为显式外部输入。交互版和完整的 Lean 源代码可在 此 https URL 在线获取。
| Comments: | 48 页，8 幅图。大幅修订并更改标题；增加了持续递归、Lean 检查的构造和交互版。交互论文和 Lean 源代码：此 https URL |
| Subjects: | 人工智能（cs.AI） |
| MSC classes: | 91A46, 68Q15, 68T05, 03D15 |
| ACM classes: | F.1.1; I.2.6; I.2.8 |
| Cite as: | arXiv:2411.06403 [cs.AI] |
| （或 arXiv:2411.06403v4 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2411.06403 arXiv 颁发的 DOI 通过 DataCite |
Submission history
来自：Soren Riis [查看电子邮件]
[v1]
2024 年 11 月 10 日星期日 09:34:26 UTC（33 KB）
[v2]
2026 年 2 月 1 日星期日 09:12:48 UTC（171 KB）
[v3]
2026 年 2 月 15 日星期日 20:38:55 UTC（119 KB）
[v4]
2026 年 10 月 11 日星期日 08:22:57 UTC（93 KB）
来源：arXiv cs.AI · arxiv.org