【NeurIPS 2021】随机最短路径:极大极小，无参数，走向水平无关遗憾

 姚班2018级本科生周润龙作为共同第一作者完成的论文《Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret》被2021年神经信息处理系统进展大会（NeurIPS 2021）接收并评为焦点（Spotlight）论文。本年度大会上获得该荣誉的论文占总提交论文数不足3%。该论文研究了理论强化学习中最为根本的问题——马尔科夫决策过程随机最短路问题（SSP-MDP），并得出了理论最优的算法。

https://www.zhuanzhi.ai/paper/616680d5758b82a133a4ce3dc4e540b9

由于其普适性，马尔科夫决策过程是理论强化学习领域中最受关注的问题模型。在这类问题中，人工智能可以将其所在的环境抽象成一个马尔科夫链，即用状态、操作、转移状态、回报刻画。在不知道每个操作的转移状态和回报的情况下，人工智能需要在K轮学习后最优化某个特定目标。理论研究最为深入的MDP通常假设人工智能一轮只能走固定、有限的步数，或者假设回报随着步数增长呈指数衰减，这样的假设过于强大，以至于生活中的另一些基本问题不能被很好地表示。随机最短路（SSP）问题则没有上述假设，而采用了一个较弱的假设，即假设按照最优策略执行的人工智能，其一轮的期望总代价不超过一个特定值B*，同时期望步数不超过另一个特定值T*。同时，SSP的目标为搜寻到一个特定状态的最小总代价，这也与人们以目标为导向的行为方式更加吻合。采用遗憾刻画算法的优劣，即前K轮所花的实际代价减去K倍最优代价。

    该论文提出了SSP问题的三点要求：(1)最小化最劣情况下的遗憾，由信息论推知下界为Ω(B√(SAK))，依照理论强化学习惯例，可以忽略对数项和与K无关的项；(2)算法的执行不需要事先知道参数B和T*，实际情况中人工智能也是不可能知道这两个参数的；(3)忽略对数项后，遗憾与T无关，因为T可能会比B大任意多倍。该论文与另一篇同时投稿的论文分别独立提出了满足要求(1)的不同算法，而该论文的独有贡献在于提出了满足要求(2)的通用算法。最后，该论文中的算法还能以牺牲要求(2)中的T换取要求(3)，而同时满足三点要求的算法是否存在目前仍是开放性问题。

    对于要求(1)，该论文提出的算法基于乐观估计、值迭代的有限时间近似收敛来保证运行效率和遗憾上界。乐观估计部分用到了上确信界的思路，通过引入统计量方差来获得较同领域前作更精细的分析方式。该论文通过构造一个新式的贝尔曼算子来保证值迭代的单调、收敛。基于这两点，该论文将遗憾分解为贝尔曼误差和统计误差，并通过递归（推）的方式得到方差总和的上界，从而证明遗憾上界。对于要求(2)，该论文的通用算法核心对于B的估计。只要给定一个满足要求(1)的算法，通用算法可以通过定期比较其实际总代价与估计B的遗憾上界来自适应调整B的估计值。对于遗憾上界的估计需要精细构造常数以及对数项。由于零代价环的存在，需要对对代价增加微小扰动来保证算法的执行效率，而代价就是会在小项上引入T。如果事先知道关于T*的阶的正确估计，那么就可以精细地计算扰动值来满足要求(3)。