强化学习中的值函数近似：Sarsa与Q-learning的函数近似实现
强化学习中的值函数近似：Sarsa与Q-learning的函数近似实现
本文将介绍如何使用函数近似方法来实现强化学习中的Sarsa和Q-learning算法。通过线性函数近似，我们可以将传统的基于表格的算法扩展到连续状态空间，从而处理更复杂的问题。
一、前言
虽然通过前面一系列博客虽然已经了解值函数近似的原理，且熟悉 linear function approximation(线性函数拟合) 特征向量(feature vector) 应该如何选取。不过总的来说，前面的推导或者说示例过程，为了简单易懂使用一维的方式引入，即对状态价值进行估计。总的来说，是为了理解其核心实现。
该篇博客开始，将会开始通过值函数近似对 action(动作)价值评估进行拟合，相对于状态价值的拟合其要更加复杂一些，因为 action(动作) 价值评估需要考虑状态s的同时还需要考虑动作a，类似于二维的感觉。在前面的学习过程中，接触到的动作价值评估算法有 TD-SV、Sarsa、Expected Sarsa、 n-step Sarsa 以及 Q-learning，不过前面介绍这些算法都是基于表格，或者说离散形式进行推导与应用的，接下来将使用连续函数去拟合这些离散算法。
二、迭代公式(Sarsa)
首先回顾一下值函数近似状态价值的博客：【强化学习理论基础-通用】(32)从零开始白话给你讲[数学原理]：值函数近似，目标函数 与 linear function approximation，其首先构建目标函数：：J ( w ) = 1 2 E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] (01) 该目标函数对w求梯度(因为优化的参数是w)：∇ w J ( w ) = − E [ ( v π ( S ) − v ^ ( S , w ) ) ∇ w v ^ ( S , w ) ] (02) 进一步根据梯度下降算法，或者说罗宾逊-蒙罗算法(Robbins-Monro algorithm)：【强化学习理论基础-通用】(17)从零开始白话给你讲[数学原理]：随机近似(Stochastic Approximation)，罗宾逊-蒙罗算法(Robbins-Monro algorithm)，构建迭代优化等式如下：
w t + 1 = w t + α t ( v π ( s t ) − v ^ ( s t , w t ) ) ∇ w v ^ ( s t , w t ) (03) 虽然结果基本已经推导出来，但是其中v π 是理想真值，属于未知量，故退而求其次采用蒙特卡洛(MC)算法，或者时序差分(TD)算法去代替v π ，这里采用后者，即r k + 1 + γ v k ( s t + 1 ) 代替v π ，那么可得：w t + 1 = w t + α t [ r t + 1 + γ v ^ ( s t + 1 , w t ) − v ^ ( s t , w t ) ] ∇ w v ^ ( s t , w t ) (04) 上述就是对时序差分(TD)状态价值估算的近似函数迭代公式，关于动作价值的函数近似，只需要把上式中的v ^ ( s t + 1 , w t ) 替换成q ^ ( s t + 1 , a t , w t ) ，v ^ ( s t , w t ) 替换成q ^ ( s t , a t , w t ) 即可，如下：w t + 1 = w t + α t [ r t + 1 + γ q ^ ( s t + 1 , a t + 1 , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) (05) 具体的推导细节可以可以参考一下【强化学习理论基础-通用】(24)从零开始白话给你讲[数学原理]：时序差分(Temporal-Difference) - action values(Sarsa)，其是基于表格或者离散的方式，再结合(01)式构建关于动作价值的目标函数：J ( w ) = 1 2 E [ ( q π ( S , A ) − q ^ ( S , A , w ) ) 2 ] (06) 然后求导，再利用梯度下降或者 RM 算法即可，这里的目标函数是最小化动作价值误差。无论(04)式还是(05)式，其都是对价值评估策略进行优化，目的是为了让价值评估策略的评估结果更加准确，即两者都在优化 policy evaluation ，而非优化动作决策策略。
三、Sarsa伪代码分析(on-policy)
1、基本概念
通过前面的知识积累可以知道强化学习可以划分为 on-policy 与 off-policy 两个类比，具体如何区别判断可以参考前面博客【强化学习理论基础-通用】(28)从零开始白话给你讲[数学原理]：时序差分算法 --＞ Q-learning 伪代码(on-policy 与 off-policy)，示例对比说明，且通过 Q-learning 算法同时实现 on-policy 与 off-policy，另外还有十分详细的图示与伪代码协助分析。
不过要注意的是，无论 Q-learning 还是 TD-SV、Sarsa、Expected Sarsa、 n-step Sarsa 他们都是 policy evaluation ，故还需要结合 policy improvement 算法π才能组合成一个完整的策略优化算法。所以设动作决策策略π为 Epsilon Greedy，再结合值函数近似的 Sarsa 算法，也就是上面推导出来的(05)式，可得该组合的伪代码：
2、伪代码
3、代码分析
首先要知道该图示代码为 on-policy，因为其生成数据的策略π与被优化改善的策略π是同一个策略。熟悉前面博客【强化学习理论基础-通用】(28)从零开始白话给你讲[数学原理]：时序差分算法 --＞ Q-learning 伪代码(on-policy 与 off-policy)，示例对比说明的朋友，应该是很容易看明白的。
另外需要注意的是，未讲解值函数近似之前的一系列时序差分(Temporal-Difference)算法，比如 TD-SV、Sarsa、Expected Sarsa、 n-step Sarsa 以及 Q-learning 其优化公式于博客【强化学习理论基础-通用】(29)从零开始白话给你讲[数学原理]：时序差分(Temporal-Difference)，回顾与总结，TD算法统一形式中有介绍，且统一形式为其中(01)式，如下：q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − q ˉ t ] (07) 上式q ˉ t 就是迭代优化过程中的目标，随着具体算法的实现有所改变，但是总的来说，其目标都是直接优化动作价值q t + 1 ( s t , a t ) ，而上面值函数近似的Sarsa算法，也就是(05)式优化的是参数w，而非直接优化动作价值q。
经过前面一系列知识积累，现在来看上述伪代码，可以说是十分简单。总的来说每个回合(生命周期)内会进行多次迭代，若当前迭代时刻记为t，那么先使用动作决策策略π t 与环境进行交互，凑足如下 5 个数据：
{ s t , a t , s t + 1 , r t + 1 , a t + 1 } (08) 即可完成一次对动作价值估算策略q t 的优化，且s t ，a t 是上一时刻与环境交互的状态与动作，即该时刻只需要获取s t + 1 , r t + 1 , a t + 1 这三个数据即可，优化的之后的策略记录为q t + 1 。接着就是使用优化后的动作价值评估策略q t + 1 对动作决策策略π t 的所有动作进行评估，找到最大动作价值对应的动作a m ，对策略π t 进行优化更新，得π t + 1 。
另外还有一点与之前表格(离散)形式 Sarsa 算法有所区别的是，现在计算某个状态下某个动作的q，需要把状态s t 以及a t 带入到关于w t 参数的近似函数，即通过q t ( s t , a t , w t ) 求得具体近似动作价值。之前(离散)形式 Sarsa 算法本质上来说，是通过索引的方式直接获取存储的动作价值。
四、示例(Sarsa)
1.游戏规则
为深入体会到值函数近似 Sarsa 算法效果，这里再进行一个示例的讲解，游戏规则与参数如下：
动作:共五个动作，上(a1)、下(a2)、左(a3)、右(a4)、保持原地不动(a5)。奖励:进入黄色(禁止forbidden区域)=-1、进入白色可通行(passable)区域=0、到达终点(target)蓝色区域=1。特殊:若触碰边界(boundary)，奖励为=-1，如在最上边依旧往上走，不过机器人状态(位置保持不变)初始:初始状态， 每个回合开始只能从某个固定的状态(位置)出发注意:为了简单示例，转移为下一个状态时，只有一种奖励，且状态状态下执行某个动作，也只能达到下一种状态，而非概率，有多个选项。
上面是迷宫游戏的规则，相信大家已经很熟悉了，这里把奖励单独记录一下r f o r b i d e n 有改变：
r b o u n d a r y = − 1， r f o r b i d e n = − 1， r p a s s a b l e = 0 ， r t a r g e t = 1， γ = 0.9 (09) 另外还需要增加一个Sarsa 算法迭代优化需要的学习率：α = 0.1 (10)
2.效果图示
智能体与环境共交互 500 个回合，每个回合初始状态都为s ( 1 , 1 ) ，根据前面的讲解可以知道，并不需要像蒙特卡洛(Monte Carlo)一样，收集整个回合的经验轨迹数据才能开始优化，只需要与环境进行一次交互，收到到数据s t + 1 , r t + 1 , a t + 1 再结合上一时刻的s t , a t ，共计五个数据即可完成一次动作价值评估q以及动作决策策略π的优化，如下两幅图示：
图1
首先需要说明的是，上面的图示为 linear uncion approximation 版本的 Sarsa 算法，实现细节需参考【强化学习理论基础-通用】(32)从零开始白话给你讲[数学原理]：值函数近似，目标函数 与 linear function approximation，大致的来说，若为 linear uncion approximation，则上(05)式：w t + 1 = w t + α t [ r t + 1 + γ q ^ ( s t + 1 , a t + 1 , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) (11) 需要知道ϕ ( s t ) 为特征向量，随着特征向量ϕ ( s t ) 的选取不同，(11)式的具体实现也会不同，至于ϕ ( s t ) 应当如何选取在前面的博客也有详细的介绍，这里线性特征向量被选择为5阶傅里叶函数，下面来对结果进行分析。
接着先看左边的两幅图示，左上图横轴表示回合(生命周期)索引， 纵轴表示每个回合(生命周期)获得奖励总和，容易看出随着收集的回合经验数据越多，进行优化迭代，每个回合获得奖励总和再持续增加。接着来看左边下面的图示，其横轴依旧表示回合(生命周期)索引，纵轴表示每个回合(生命)周期的长度，由曲线可以看到，随着索增加，即迭代次数增多，其对应的比较差生命周期逐渐减少。这是因为，初始策略比较差，智能体需要进行很多 step 的探索才能到达终点(蓝色区域)，随着动作决策策略的优化，后续能够以较优的路径快速抵达终点，所以生命周期短。
右边的图示表示迭代优化完成之后的最终策略，容易看出部分决策非最优，不过这没有关系，因为我们的初始状态只能为s ( 1 , 1 ) ，所以只需要保证从该状态出发，到达终点的路径为最优路径即可。
五、迭代公式(Q-learning)
通过前面使用函数近似(funcion approximation)方式实现 Sarsa 的介绍，以及示例讲解，相信对于函数近似已经有了一定了解。现在使用函数近似的方式再来实现 Q-learning 算法，总的来说还是十分简单的，与函数近似(funcion approximation) 版的 Sarsa 算法十分相近，其参数迭代更新公式如下：w t + 1 = w t + α t [ r t + 1 + γ max a ∈ A ( s t + 1 ) q ^ ( s t + 1 , a , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) (13) 上式中max表示求参数为w t 时 处于s t + 1 状态下所有动作对应的最高价值，需要注意的一点，其并不需要知道最大价值 最大价值对应的动作 a m 。可与 Sarsa 算法，即上(05)式进行比较，可以看出他们是十分相近的，唯一的区别就是max a ∈ A ( s t + 1 ) 这个部分。
六、Q-learning伪代码分析(on-policy)
这里给出的代码依旧为 on-policy，不过通过前面的学习知道 Q-learning 算法即能实现 on-policy 也能实现 off-policy，所以后面讲解 Deep Q-learning 算法时会讲解 off-policy。与 Sarsa 一样，其本质仅是一个行为价值估计算法，同样与动作决策策略算法 Epsilon Greedy 结合，构建完整的 on-policy 算法，伪代码实现如下：
该伪代码就不解读了，因为有前面的只是积累太容易看明白。这里提要一下，那么就是更新参数w时使用max只需要知道参数为w t 时 处于s t + 1 状态下所有动作对应的最高价值即可，无需知道对应那个具体动作a m 。但是在对动作决策策略π更新时使用的是arg max，其是需要知道最大动作价值对应具体动作a m 。
另外需要注意的一点就是该实现方式为 on-policy，即与环境进行交互收集数据的策略π与 被优化的策略π是同一个动作决策策略，这是 on-policy 的核心标记。
七、示例(Q-learning)
这里同样给出一个 linear uncion approximation 版本的算法，游戏规则与设置不变，且线性特征向量被选择为5阶傅里叶函数，效果如下：
图2
若是与 Sarsa 算法的图一进行对比，可以看到迭代过程中 Q-learning 更加稳定，收敛较快。优化后的动作决策策略，即右图从状态s ( 1 , 1 ) 出发达到蓝色(终点)状态的路径同样为最有路径。
八、结语
通过该片博客，知道如何使用 linear uncion approximation 实现 Sarsa 与 Q-learning 算法，两者伪代码都是 on-policy 形式。这里还是要提要一点，无论 Sarsa 还是 Q-learning 算法，都是 policy evaluation ，故还需要结合 policy improvement 算法π才能组合成一个完整的策略优化算法，上面的两个示例都是选择与 Epsilon Greedy 结合。
下一篇博客将讲解目前最主流的算法 Deep Q-learning，其将深度神经网络整合到Q(动作价值)学习中，从而得到一种称为深度Q学习或深度Q网络(DQN)的方法。深度Q学习是最早且最成功的深度强化学习算法之一。值得注意的是，神经网络不一定要很"深"。对于像我们的网格世界这样的简单任务，具有一到两个隐藏层的浅层网络可能就足够了。具体细节就得参考下一篇博客了。