用强化学习自动构建计算多项式的高效电路，验证了智能搜索的潜力。
CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
- 将电路构造建模为单玩家游戏，用RL代理逐步搭建加乘门组成的电路。
- SAC方法在双变量目标上成功率最高，PPO+MCTS可扩展至三变量并持续优化复杂实例。
- 适合研究自提升搜索策略，具备可验证性和紧凑性，对自动证明有启发意义。
受自动证明生成及Valiant的VP vs. VNP猜想驱动，我们研究如何利用加法和乘法门构造高效算术电路来计算多项式。将该问题建模为单玩家游戏，强化学习代理在固定操作数内尝试构建电路。采用类似AlphaZero的训练循环，比较了两种方法：带蒙特卡洛树搜索的近端策略优化（PPO+MCTS）与软演员-评论家（SAC）。SAC在双变量目标上取得最高成功率，而PPO+MCTS可扩展至三变量，并在更难实例上表现出持续改进。结果表明，多项式电路合成是研究自提升搜索策略的一个紧凑且可验证的设置。
原文摘要 · Abstract (English)
Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。