可加性|普林斯顿大学王梦迪：从基础理论到通用算法，看见更大的AI世界观( 三 )

CSML的主要研究内容是开发数据驱动的现代机器学习算法，与王梦迪的研究方向更契合。同样是举下棋的例子：就下棋而言，智能体的训练数据来自于游戏本身，每尝试新的玩法、就会收集到新的数据；在一个可以完美模拟的游戏环境中，智能体所收集的数据量甚至是无上限的。如何从模拟走向现实，即「sim2real」，是人工智能领域面临的难题之一。
自2015年DeepMind开发的Alpha Go 在与世界围棋冠军李世石的对峙中取胜，强化学习便成为许多人工智能研究员的神往之地，王梦迪也是其中之一。

文章插图

图 / 普林斯顿大学统计与机器学习中心（CSML）
在早期工作中，王梦迪是将数学优化方法与高维统计相结合，以解决大规模机器学习中的图问题。比如，当图问题离散组合时，如何利用问题的特殊结构，将问题进行对偶分解，从而获得一个出色的近似解。这一近似解借用了非凸优化的对偶性，与非凸问题的最优解相近。
她探索过复杂的多层期望嵌套的随机规划问题。通过巧妙的设计多层嵌套随机梯度法，能够在线的进行迭代，最终拿到的估计的统计效果与离线进行完整组合分析的效果一致。凭借这项研究，王梦迪在2016年获得三年颁发一次的国际数学规划学会青年学者奖（Young Researcher Prize in Continuous Optimization of the Mathematical Optimization Society）。
这些探索性的研究更加深了王梦迪对随机优化理论与机器学习结合的兴趣。接着，她又与斯坦福大学的叶荫宇（冯诺伊曼理论奖唯一华人获得者）等人合作，研究马尔可夫决策链（MDP）的理论复杂度与最优算法。
MDP是强化学习的基础模型，同时，MDP的算法复杂度也是运筹学领域的经典问题。他们要解决的问题是：当强化学习的样本来自于马尔可夫链时，要如何研究一个算法的最优收敛性与样本复杂度？如何定义MDP问题的最优算法与计算复杂度？从上世纪70年代起，便有许多学者开始研究这些问题，但一直悬而未决。
王梦迪与叶荫宇等人合作，结合经典的价值迭代算法，以及样本与方差缩减技巧，首次提出了能基于样本精确解决MDP的最优快速收敛算法，将马尔可夫决策链中的计算复杂度与样本复杂度做到了最优。他们的一系列工作（如“Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model”）于2019年发表在了计算机和机器学习顶会NeurIPS、SODA等上。

文章插图

论文地址：https://arxiv.org/pdf/1806.01492.pdf
凭借在马尔可夫决策链复杂度和在线强化学习上的一系列工作，王梦迪在2018年入选了「麻省理工科技评论35岁以下创新35人（MIT TR35）」的中国区榜单。
后来，她又在强化学习领域做了许多通用算法研究的工作，比如，在特征空间中进行在线自学习；再比如，探索强化学习的未知模：当未知价值函数属于一个无限维的抽象函数空间时，要如何在这个空间里不断迭代估计，并用该空间的复杂度来描述强化学习算法的效率。这些早期工作，也成为理论强化学习领域的奠基性工作。
2020年，DeepMind发布新一代强化学习系统Muzero。以往的强化学习算法如AlphaGo和AlphaZero往往只适用于单一类别的游戏。Muzero仅使用像素和游戏分数作为输入，同时在Atari、围棋、象棋等多个单人视频游戏和双人零和游戏上超越人类水平，达到AI算法最强战绩。
那时王梦迪正在DeepMind休学术假。她与团队成员联合 DeepMind 的科学家从理论上证明并进一步推广了Muzero的泛用性，移除了“价值函数导向回归”（value target regression）的特殊算法技巧，使得强化学习算法可以在任何一个黑箱环境中，对未知环境的变化进行判断、数据收集、并且构造后验概率模型，在一个抽象的大的函数空间里不断搜索、缩小模型范围，对未知环境及其最优策略快速逼近。
该算法同时结合了 model-based（基于环境模型的）和 model-free（不基于环境模型而是基于价值函数逼近）的两派强化学习算法各自的优点：对任意的黑箱环境进行探索、建模、并且利用深度价值网络快速训练、快速在线迭代策略，从而炼就了极强的泛化能力。这一系列新成果可以极大提高强化学习的效率，普适性，并降低对昂贵的算力和大规模数据资源的依赖。

文章插图

论文地址：https://arxiv.org/abs/2006.01107