【论文笔记】OpenAI宫斗背后：发现了可能优于小鸡毛表现的机器人，AGI的希望 Q* search and Q transformer(A star search with Q-Learning)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【论文笔记】OpenAI宫斗背后：发现了可能优于小鸡毛表现的机器人，AGI的希望 Q* search and Q transformer(A star search with Q-Learning)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

最近OpenAI的宫斗剧上演的精妙绝伦，简直就是《硅谷》+《继承》，强烈推荐这两部剧集。AIGC的群里都在说Q*是揭示AI接近AGI的一篇论文，那就费点时间拨开云雾吧。为了方便大众更好地理解Q*，本人在快速浏览过论文后首先得出此结论公式：

Q* = (1992年的Q-learning + 1968年的A star算法) * Deep Transformer Learning

本篇文章解读两篇论文。强烈建议延伸阅读第二篇文章的视频：Q-Transformer

Q-Transformer简介之机器人如何实现自主Q学习的动画

1、第一篇介绍Q* search论文全称是：A* SEARCH WITHOUT EXPANSIONS: LEARNING HEURISTIC FUNCTIONS WITH DEEP Q-NETWORKS，作者是加州大学尔湾分校和南卡罗琳娜大学的研究员在2023年5月份提出的。原文链接：https://arxiv.org/abs/2102.04518

2、第二篇介绍Q transformer论文的全称是：Q-Transformer: Scalable Offline Reinforcement Learning via Autoregressive Q-Functions，作者是Deep Mind团队在2023年9月提出的。[2309.10150] Q-Transformer: Scalable Offline Reinforcement Learning via Autoregressive Q-Functions (arxiv.org)

Gpt-4先summary：

Q* search论文解决了使用A*搜索在大动作空间中高效解决问题的挑战，这是人工智能领域一个重要的方法。A*搜索的计算和内存需求随动作空间大小线性增长，尤其是当使用由深度神经网络学习的计算成本高昂的启发式函数时。为了克服这一问题，作者引入了Q*搜索，这是一种新的搜索算法，采用深度Q网络。这种方法允许通过网络的单次前向传递计算节点子项的转换成本和启发式值之和，无需显式生成这些子节点。这显著减少了计算时间和每次迭代生成的节点数量。作者以包含1872个元动作的大动作空间下的魔方为例，展示了Q*搜索的有效性。结果显示，Q*搜索比A*搜索快达129倍，生成的节点数量少达1288倍。此外，他们证明了Q*搜索在给定适当启发式函数的情况下总能找到最短路径。

在Q transformer这项工作中，作者提出了一种可扩展的强化学习方法，用于从大型离线数据集中训练多任务策略，这些数据集可以利用人类示范和自动收集的数据。作者的方法使用Transformer为通过离线时差备份训练的Q函数提供可扩展的表示。因此，我们将这种方法称为Q-Transformer。通过离散化每个动作维度并将每个动作维度的Q值表示为单独的标记，我们可以应用有效的高容量序列建模技术进行Q学习。作者介绍了几个设计决策，这些决策使得离线RL训练具有良好的性能，并展示了Q-Transformer在一套大型多样化的现实世界机器人操控任务中，超越了以前的离线RL算法和模仿学习技术。

到这里GPT已经剥夺了我解读论文的乐趣了。

论文解读

【Q* Search】A* SEARCH WITHOUT EXPANSIONS: LEARNING HEURISTIC FUNCTIONS WITH DEEP Q-NETWORKS

首先，在介绍Q* search之前要知道，A*算法是一个贪心算法。其讲求邻近收益最大化，即找到最近最好的路径，以此猜测通过迷宫的最优方法。它主要用于agent在现实中的行动指导，对计算量和内存空间的要求很高，并根据需要行动的地图大小呈线性增长。常见的用法是用在物流计算的问题上。我以前学过经典的旅行商问题TSP，用的就是A star算法作为一个补偿算法，面对需要较大的计算代价来寻求最优解时，在较短时间内找到较优解，也可以理解为在找local minima。算法非常简单，也很好用。

Q*是什么呢，就是用了Deep Q-network来计算A star算法的邻近收益。Q-network的好处是能够计算下一节点的行动成本和启发值，而不用真的走到下一节点。翻译成人话就是：我在脑子里下棋。这就减少了计算开支、降低了内存空间的占用。作者用Q* search来解决魔方问题。解一个需要1872个动作才能完成的魔方，用Q*的好处是，当行动空间（action space）提高了157倍，计算时间只增加了不到4倍，计算内存空间也只增加了不到3倍。Q*相比A*快了129倍，并最多减少1288倍的计算空间。

看完abstract我就知道我不需要看全文了，只草草扫了一眼。如果有兴趣要复现算法并验证的小伙伴们，可以再去深入研究一下整个算法的代码实现，毕竟是强化学习，逻辑比较通俗易懂。想象你在下棋会比较好理解。在每次迭代中，Q* search会从OPEN中弹出一个节点操作元组（s，a），并创建一个新的节点s‘=A(s，a)。Q* search不去向s‘节点行动，而是将DQN应用到s’，以获得其所有下一步行动节点的过渡成本（transition cost）和待执行成本(cost-to-go)的总和。因此，我们只需要计算一次前向DNN，而不是计算|A|。Q* search强制打开所有下一次行动a‘的新节点操作元组（s’，a‘），其中代价是通过sum（通过s节点的路径+对应于下一次行动a’的DQN输出）。在Q* search中，唯一依赖行动空间的变量是OPEN节点。与A* search不同，无论行动空间的大小如何，每次迭代只生成一个节点，而启发式函数每次迭代只需要应用一次。以下post出这个论文里algorithm的伪代码给各位研究：

Algorithm Q* Search

        Input: starting state s0, DQN qφ

        OPEN ← priority queue

        CLOSED ← maps nodes to their path cost

        a = NO OP

        f(s0, a0) = mina′ q(s0, a′ )

        g(s0) = 0

        Push (s0, a, g(s0)) to OPEN with cost f(s0, a0)

        CLOSED[s0] = g(s0)

        while not IS EMPTY(OPEN) do

                (s, a, g(s)) = POP(OPEN)

                s ′ = A(s, a)

                if IS GOAL(s ′ ) then

                        return PATH TO GOAL(s ′ )

                end if

                g(s ′ ) = g(s) + g a (s, s′ )

                if s ′ not in CLOSED or g(s ′ ) < CLOSED[s ′ ] then

                        CLOSED[s ′ ] = g(s ′ )

                        q = qφ(s ′ , .)

                        for a ′ in 0 to |A| do

                        f(s ′ , a′ ) = g(s ′ ) + q[a ′ ]

                        Push (s ′ , a′ , g(s ′ )) to OPEN with cost f(s ′ , a′ )

                end for

        end if

end while

return failure

【Q Transformer】Q-Transformer: Scalable Offline Reinforcement Learning via Autoregressive Q-Functions

在这个项目中，作者提出了一种可扩展**的强化学习方法，用于在一个很大的利用人工演示和自动收集的离线数据库里训练多任务策略。这个方法用一个Transformer来提供对离线时间差异备份（temporal difference backups）训练的Q-functions的可扩展表示，所以又称为是Q-Transformer。Q-Transformer离散化每一个动作维度，并且将每一个动作维度的Q值作为独立的token，就得到了高效的高吞吐量序列建模技术，应用于Q-learning。作者用了一系列设计技巧来让离线的Q-Transformer强化学习在大型的复杂的现实世界机器人操作任务组中训练的结果优于以往的强化学习算法和模仿学习技术。这想必就是其被认为达到AGI的魅力之处。

**可伸缩性(可扩展性)是一种对软件系统计算处理能力的设计指标，高可伸缩性代表一种弹性，在系统扩展成长过程中，软件能够保证旺盛的生命力，通过很少的改动甚至只是硬件设备的添置，就能实现整个系统处理能力的线性增长，实现高吞吐量和低延迟高性能。

因github上的论文讲解已经很好地解释了原理，以下为我对其的中文理解和翻译：