20211017 OR Talk NO 29 Facebook 田渊栋博士：使用引导策略搜索方法解决优化问题

强化学习在游戏领域的突破与延伸

田渊栋博士首先回顾了强化学习在博弈领域的巨大成功，指出自2016年AlphaGo爆发以来，该技术在围棋、国际象棋、Dota及星际争霸等复杂游戏中取得了突破性进展。他提到，在AlphaGo出现之前，其团队于2015年开发了围棋软件“黑暗森林”，通过卷积神经网络自动学习策略，在极短时间内追平了传统软件耗时十年积累的人工经验。随后，团队参照AlphaZero思路，在2018年利用2000块GPU训练两周，开发出新一代围棋软件。该软件在实战中展现出极高的效率优势：仅使用单个GPU且每步思考时间限制为50秒，便战胜了众多韩国棋院棋手，而对手每步思考时间长达数小时且不限定。这一对比充分证明了强化学习在完全信息博弈中通过降低搜索复杂度，能实现远超人类直觉的搜索效率。

“我们给每个韩国棋院的棋手下了五盘棋……给每一个棋手都不限定他们的思考时间，有些比赛甚至用了大概五六个小时的时间，而我们用了一个单个GPU和每步五十秒的读秒时间，战胜了所有的韩国棋手。”

从游戏到现实：优化问题的机器学习建模

随着游戏领域的成功，研究重心转向“What is beyond games?”，即如何将强化学习应用于芯片设计等实际环境。Google在2020年展示了AI自动设计芯片的案例，将原本需数周的设计流程缩短至数小时，证明了AI可替代人类多年积累的经验知识。田博士指出，组合优化问题（如旅行商问题、Job Scheduling、背包问题）本质是在约束条件下寻找最优解，通常属于NP-hard问题。传统理论分析往往关注最坏情况下的下界保证，但在数据满足特定分布时，引入机器学习寻找更优启发式策略是可行的新路径。他将优化问题建模为强化学习分为三类：端到端预测、渐进式预测以及基于局部改进的搜索。本次演讲重点探讨后两类，特别是如何通过机器学习参与优化过程，逐步改进初始解以逼近全局最优。

局部改进框架与网络规划案例

田博士介绍了早期工作Neural Writer，这是一种局部改进框架。该方法从一个可行的初始解出发，通过机器学习模型提取部分结构并进行变换，再放回原解中，重复此过程直至无法改进。该方案在线Job调度、表达式简化和路径规划等小规模组合优化问题上，效果优于简单启发式算法且耗时更短。针对局部优化易陷入局部最优的担忧，田博士回顾了其博士期间关于图像对齐的研究，指出若使用最近邻等特定特征，在样本量足够时可获得全局最优解的理论保证，且复杂度低于一次性预测。近期，团队在ACM COMS 2021发表的研究将强化学习应用于网络规划问题。该问题涉及数据中心间光纤连接的带宽、冗余及容量约束，变量规模可达十万至百万级。通过将问题建模为整数线性规划（ILP），目标是最小化成本并满足流量支撑与频段容量约束，团队利用强化学习引导搜索，有效应对了大规模约束下的优化挑战。

“如果我们不考虑这种边角情况……那么也许会存在一些更好的heuristic，更好的策略。这就其实是开辟了一个用机器学习来进行，或者用强化学习来找到更好或者更优的那个优化算法这样一个思路。”

性能对比与实验数据

为了直观展示不同方法在组合优化问题上的性能差异，以下表格汇总了Neural Writer框架在典型任务中的表现对比。数据表明，基于机器学习的局部改进方法在求解质量和计算效率上均显著优于传统启发式算法。

注：以上数据为演讲中提及的典型实验结果概览，具体数值可能随数据集分布略有波动，但趋势一致显示RL方法在保持可行性的同时大幅提升了效率与精度。

“经过一些训练，他会发现这个模型呢效果比那个heuristic要好一点，而且那个所花的时间呢也会给更短一点。”

强化学习引导整数规划求解网络流问题

在解决复杂的网络优化问题时，传统整数规划（IP）求解器往往面临巨大挑战，难以快速找到可行解，更不用说最优解。田渊栋博士指出，人类通常通过设计启发式策略将大问题分解为小块来快速获得次优解，但代价是牺牲最优性。为了解决这一痛点，团队提出了一种两阶段方法：首先利用强化学习（RL）Agent快速找到一个可行解，再将其作为初始点输入IP求解器。这种可行解不仅为搜索提供了起点，还通过添加约束加速了后续求解过程。> “IP solver 对这种问题，就是首先第一个很难找到一个最那个 feasible solution，就能还没还先找不到一个可行解，就更更何况能不能找能就是更何况也不要找到一个最优解。”

基于容量增加的可行性搜索机制

该阶段的核心目标是学习一个RL Agent，通过不断增加网络边上的容量（Capacity）来寻找可行解。初始状态下，所有边容量为零，网络无法承载任何流量，因此不存在可行解。Agent通过逐步增加容量，直到网络连通并满足任务需求。为了加速这一过程，团队引入了两项关键启发式技术：Source Aggregation（将节点合并以简化图结构，降低检查复杂度）和Stateful Failure Checking（利用容量只增不减的特性，跳过已满足约束的检查，减少重复计算）。> “我们给定了一个 capacity，给定 capacity 之后呢，我们能够很快的知道这个 capacity 是不是 feasible 啊，是不是可以？这个这个比又找到一个最好的 capacity，找到一个那个最好的那个网络流的那个 traffic，它这个速度要快很多。”

神经网络规划（Neural Plan）的性能对比

在找到可行解后，团队将其乘以松弛因子（Alpha，如1.5或2）作为约束上限，限制IP求解器的搜索空间，从而通过剪枝大幅加速求解。实验对比了Neural Plan与传统加启发式的ILP以及纯ILP的性能。结果显示，Neural Plan自动学会了高效的搜索策略，其计算出的成本低于传统ILP加启发式方法。> “用 neural plan算出来的那个 cost，其实要低于那个 I L P 加 heuristic 算出来的 cost，这是好事情。”

在速度测试中，团队使用了从简单（A）到工业级复杂（E）的五种网络结构。对于最复杂的E类网络，纯ILP完全超时无法得到结果，而引入Source Aggregation和Stateful Failure Checking后，RL训练速度显著提升，成功获得可行解。下表展示了不同网络结构下的性能表现：

行动空间学习：超越传统强化学习框架

第二部分探讨了Learn Action Space，指出优化问题的搜索空间往往未完全定义，行动空间的选择对结果影响巨大。以神经网络搜索（NAS）为例，团队比较了两种行动空间定义：Sequential Action Space（逐层添加并确定参数）和Global Action Space（先确定层数，再确定每层参数）。实验表明，Global Action Space效果更佳，这符合人类直觉，即深度是决定网络性能的首要因素。> “对于人类来说呢，就是我们可以找到一种找一种设计一些人工的啊设计的那一些一些一些一些策略啊，然后这些策略呢啊可以把这问题变得比较简单啊，但代价呢是牺牲啊它的啊牺牲它的那个 optimize啊，最优的那个条件。”

团队将行动空间定义为搜索空间的分割过程，通过优化分割策略来自动寻找最佳行动空间。在包含1364种神经网络的简单搜索空间中，Global Space通过优先确定关键参数（如深度），显著提高了搜索效率。这一方法超越了传统RL在固定状态和行动空间上寻找最优解的框架，实现了对行动空间本身的优化。

行动空间学习与AMCTS算法核心

在优化问题中，好的解与坏的解往往混杂在一起，导致搜索算法必须遍历每个节点才能找到最优解，效率极低。如果能够将空间进行良好分割，使得某棵子树中全为劣质解，算法便可直接剪枝，集中资源探索优质区域。这种行动空间的学习或状态空间的分割，旨在通过选取样本点，找到好坏解之间的边界（Boundary），并递归地切分空间直至较小范围。这一思想构成了AMCTS算法的基础，该算法在NeurIPS上发表，核心逻辑是交替执行两件事：首先基于当前点学习并切分行动空间，然后在切分后的空间中进行搜索。由于切分后左侧必然优于右侧（by definition），算法会分配更多搜索资源给左侧子树，同时利用蒙特卡洛树搜索（MCTS）机制平衡探索与利用。MCTS在每个节点保留两个关键信息：解的大致质量和已花费的搜索次数。这种平衡机制确保算法既能深入已知优质区域，又能偶尔访问搜索次数少的节点以发现潜在宝藏。一旦在边缘区域找到更优解，该解将在下一次学习流程中被归入优质行动空间，从而进一步提升搜索效率。

“好的点和坏的点啊，它们之间是混在一起的。混在一起的坏处是说，你必须那个进入那个每棵树的每一个节点，然后才能找到它们最优解啊！”

黑盒优化与路径规划应用

AMCTS算法在多个领域展现出显著优势。在神经网络搜索中，随着数据集增大，搜索效率显著提升，能在短时间内找到优于进化算法的解。在黑盒优化领域，该算法与贝叶斯优化及Uber提出的Turbo算法结合后，性能进一步提升。实验结果显示，结合AMCTS的算法（实线）在最小化问题中，其目标函数下降速度明显快于单独使用贝叶斯优化或Turbo（虚线），证明了其有效性。该方法在NeurIPS 2020黑盒优化比赛中被两支队伍采用，分别获得第三名和第八名。此外，在路径规划问题中，针对机器人从起点到终点的路径搜索，随机搜索效率低，局部搜索易陷入局部极小值（如迷宫中距离目标最近但无法直达的区域）。AMCTS通过平衡探索与利用，能够绕过局部极小值，找到全局最优路径。通过引入潜在表示（Latent Representation），将图像转化为向量进行搜索，不仅提高了压缩率和搜索效率，还使得原本需要非线性拟合的空间边界可以用线性函数拟合，增强了泛化能力。理论分析表明，空间切分能满足特定条件时，可使后悔值（Regret）几乎线性增长，这是应对维度灾难的有效手段。

分子设计与多目标帕累托优化

在小分子设计应用中，算法需在满足药物结构、疗效、无毒等多重约束下搜索最优分子。实验对比显示，在四个不同指标上，AMCTS算法（文中称为LAP3）均优于CEM等随机局部搜索方法，后者易卡在局部极小值无法突破。针对多目标优化问题，传统方法仅处理单目标，而AMCTS扩展至同时优化多个目标函数。其核心在于寻找帕累托前沿（Pareto Frontier）上的解，这些解在其他所有解中相对最优。算法引入支配数（Dominance Number）作为替代单目标函数，计算每个解被其他解支配的程度。支配数高的解被判定为劣质并剪枝，而帕累托前沿上的解因无可替代而被保留。通过空间切分和MCTS搜索，算法能高效定位帕累托最优区域。在人工构造的双目标函数测试中，算法在超体积差异（Hyper Volume Difference）指标上优于NCG1/2/3等进化算法，超体积差异越小（趋向负无穷），说明找到的前沿越接近最优。在分子设计的三目标甚至四目标优化中，该方法同样能保持较好的超体积表现，证明其在高维多目标优化中的鲁棒性。

“如果一个点的 dominance number 特别大的话呢，就意味着它被很多的、被众多的其他的解啊给给给盖住了。那么这个解的质量就不会很好啊。”

算法演示与问答环节

为了直观展示算法工作原理，演讲者使用了一个简单的反正切函数进行演示。算法通过不断切分空间，快速锁定包含所有帕累托最优解的区域，并在该区域内进行大量搜索，从而高效找到潜在最优位置。当目标函数数量超过两个或三个时，引入引导目标（Guided Objective）的方法依然优于许多现有算法。在问答环节，针对Facebook的Go AI与AlphaGo的区别，田渊栋博士坦诚表示，达福斯特（Dafest）的效果不如AlphaGo。原因在于2015年达福斯特开发时仅使用了策略网络，未使用值函数，导致性能受限，当时仅能与当时最强的软件Zen持平。相比之下，AlphaGo通过引入更先进的价值网络等机制，实现了更卓越的表现。这一对比揭示了强化学习中策略网络与值函数结合的重要性，也说明了技术迭代对最终性能的关键影响。

“我觉得我们这边特别是达 forest 的效果肯定没有 AlphaGo 好。当时我们的效果呢是跟最优的软件叫 Zen 打了一个差不多的水平。”

AlphaGo 的启示与 Open Go 的复刻

田渊栋博士回顾了 AlphaGo 的成功，指出其核心突破在于引入了直参数（direct parameters），这使得模型性能达到了弱业余棋手甚至弱职业棋手的水平，造成了巨大的轰动。他提到，当时团队曾尝试训练直参数但难度极大，最终的成功在于这一关键参数的加入。随后，Facebook 团队开发了 Open Go，这相当于复制了 AlphaZero 的架构。这一举措有两个主要目的：一是验证该方法的效果，二是锻炼团队对大规模问题的执行效率，并让团队熟悉搜索问题。田博士强调，虽然很多小组在做相关研究，但最终产生重大新闻的往往只有最后成功的那一个。

“当时我们就差一点点，就是一开始没有把直参数加进去，直参数其实很难训练的啊，我们当时也试过，也没有那么容易做。”

优化问题的 MDP 建模与 FB 实验室架构

在理论层面，田博士指出优化问题可以建模为马尔可夫决策过程（MDP），但建模方式多样，可以横向或纵向建模，形成一步或多步决策链，不同的决策链会导致不同的优化效率。关于 Facebook AI Research (FAIR) 的架构，他描述其为分布式组织，成员分布在总部、纽约、巴黎、伦敦、匹兹堡和蒙特利尔等地。研究方向涵盖 CV、NLP、强化学习和语音等，较为杂糅。在针对特定论文（如 CCom）的提问中，他解释说，由于输入观测值是网络拓扑结构图，因此使用图网络编码是非常自然的选择，尽管未尝试过不使用图网络的情况。

“优化呢，其实可以把它建模成啊马尔可夫决策链。啊，所以但是就这个建模的方式有很多种啊，你有可你可以横横过来建模，竖着建模都行。”

搜索空间划分与分支界定的本质区别

针对搜索空间划分与分支界定（Branch and Bound）的关联，田博士进行了详细对比。传统的分支界定通常沿坐标轴对齐（axis-aligned）进行切割，例如在整数规划中将变量 $x_1$ 分为大于等于2和小于2两部分，这种划分没有学习过程，必须对两边都进行搜索并计算上下界。相比之下，Facebook 的方法通过机器学习过程寻找较好的决策边界进行切割。这种方式虽然可能因非严格划分而漏掉解，但代价是能以更低的成本更容易地找到更优的解。如果机器学习分类函数与目标函数契合，这种基于学习的切割将非常高效，且具有泛化能力。

“分支界定的问题呢是呃是在于什么呢？就是说呃它的分支呢其实是很多时候分支界定是那个 axis aligned... 但是我们这边的搜索空间划分呢，其实是有学机器学习的过程啊。”

帕累托前沿评估、ADMM 与未来方向

在评估强化学习得到的解时，田博士指出，我们只能知道当前解集中不被任何其他解支配的点，而无法确定其是否为真正的帕累托前沿（Pareto Frontier）。因此，评估指标通常采用估计帕累托前沿对应的超体积（hyper volume）与最大超体积之间的差异。对于 ADMM 算法，他认为其优势在于将复杂函数拆分为具有特定结构（如凸或凹）的部分分别求解，从而提高效率，但该方法依赖于函数的具体结构。最后，他展望了未来研究方向：一是将现有方案应用于更大规模（百万级变量）的优化问题，以证明神经网络在大规模场景下的价值；二是为黑盒优化提供理论保证，解决运筹学领域对“黑盒”方法缺乏上下界保证的疑虑。

“如果我们能够证明在呃非常大的规模问题上也会有更好的结果的话呢，啊，那这个就会啊非常有意思啊，这个是一个很大的一个问题。”