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

王梦迪与叶荫宇等人合作，结合经典的价值迭代算法，以及样本与方差缩减技巧，首次提出了能基于样本精确解决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

4、拓展强化学习在复杂现实场景中的通用性
所有强化学习的算法都受限于马尔可夫决策过程中的奖励可加性 (reward additivity)，即「目标价值函数是每一步所得奖励的累加值期望」。奖励的可加性是贝尔曼方程（Bellman Equation）、控制论、乃至所有强化学习算法的数学基础。
尽管奖励的可加性能推导出数学上优美的贝尔曼方程，却极大地限制了强化学习的应用，因为在大量的非游戏的现实场景中，目标函数往往不是奖励的简单相加。在风险控制、策略模仿、团队协作等场景中，真正的目标函数往往是关于状态轨迹的复杂非线性函数，如风险函数、散度等等，甚至包含复杂的非线性安全约束条件。由于缺乏可加性，这些重要的实际问题无法用强化学习解决。
然而，当可加性不再成立，强化学习和控制的数学基础不复存在，我们熟悉的价值函数（Value Function）也不再存在。同时，策略优化算法的基础——强化学习之父Rich Sutton证明的策略梯度定理（Policy Gradient Theorem）也不复成立。
在智能决策领域，不满足奖励可加性的问题无解。
王梦迪团队挑战了这个全新的领域，拓展了强化学习的边界。当面对复杂目标函数、奖励不再可加时，王梦迪团队利用数学对偶原理，重新定义了策略梯度，得到了全新的更泛用的变分策略梯度定理（Variational Policy Gradient Theorem）。他们证明，对于更复杂的目标函数，其策略梯度依然可以计算，并且其等价于一个极大极小值问题的最优解。被重新定义的策略梯度，带来了全新的算法和应用。也就是说，强化学习可以进一步推广到金融风控、多智能体、模仿学习等现实场景中。