函数近似方法

有模型数值迭代算法、回合更新算法和时序差分更新算法，在每次更新价值函数时都只更新某个状态（或状态动作对）下的价值估计。但是，在有些任务中，状态和动作的数目非常大，甚至可能是无穷大，这时，不可能对所有的状态（或状态动作对）逐一进行更新。函数近似方法用参数化的模型来近似整个状态价值函数（或动作价值函数），并在每次学习时更新整个函数。这样，那些没有被访问过的状态（或状态动作对）的价值估计也能得到更新。本章将介绍函数近似方法的一般理论，包括策略评估和最优策略求解的一般理论。再介绍两种最常见的近似函数：线性函数和人工神经网络。后者将深度学习和强化学习相结合，称为深度Q学习，是第一个深度强化学习算法，也是目前的热门算法。

函数近似原理

本文介绍用函数近似（function approximation）方法来估计给定策略π的状态价值函数vπ 或动作价值函数q π 。要评估状态价值，我们可以用一个参数为w的函数v(s;w)（s∈ S）来近似状态价值；要评估动作价值，我们可以用一个参数为w的函数q(s,a;w)（s∈S  ,a∈A (s)）来近似动作价值。在动作集有限的情况下，还可以用一个矢量函数q(s;w)=(q(s,a;w):a∈A )（s∈S ）来近似动作价值。矢量函数q(s;w)的每一个元素对应着一个动作，而整个矢量函数除参数外只用状态作为输入。这里的函数v(s;w)（s∈S ）、q(s,a;w)（s∈S  ,a∈A ）、q(s;w)（s∈ S）形式不限，可以是线性函数，也可以是神经网络。但是，它们的形式需要事先给定，在学习过程中只更新参数w。一旦参数w完全确定，价值估计就完全给定。所以，本节将介绍如何更新参数w。更新参数的方法既可以用于策略价值评估，也可以用于最优策略求解。

随机梯度下降

本节来看同策回合更新价值估计。将同策回合更新价值估计与函数近似方法相结合，可以得到函数近似回合更新价值估计算法（算法6-1）。这个算法与第4章中回合更新算法的区别就是在价值更新时更新的对象是函数参数，而不是每个状态或状态动作对的价值估计。

算法1　随机梯度下降函数近似评估策略的价值

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（采样）用环境和策略π生成轨迹样本S0,A0,R1,S1,A1,R2,…,ST-1,AT-1,RT,ST。
2.2　（初始化回报）G←0。
2.3　（逐步更新）对t←T-1,T-2,…,0，执行以下步骤：
2.3.1　（更新回报）G←γG+Rt+1。
2.3.2　（更新价值）若评估的是动作价值则更新w以减小[G-q(St,At;w)]^2（如
w←w+α［G-q(St,At;w)］▽q(St,At;w)）；若评估的是状态价值则更新w以减小［G-v(
St;w)］2（如w←w+α［G-v(St;w)］▽v(St;w)）。

如果我们用算法6-1评估动作价值，则更新参数时应当试图减小每一步的回报估计Gt和动作价值估计q(St,At;w)的差别。所以，可以定义每一步损失为［ G t − q ( S t , A t ; w ) ］ 2 ，而整个回合的损失为∑ t = 0 T ［ G t − q ( S t , A t ; w ) ］ 2  。

如果我们沿着∑ t = 0 T ［ G t − q ( S t , A t ; w ) ］ 2  对w的梯度的反方向更新策略参数w，就有机会减小损失。这样的方法称为随机梯度下降（stochastic gradient-descent，SGD）算法。对于能够支持自动梯度计算的软件包，往往自带根据损失函数更新参数的功能。如果不使用现成的参数更新软件包，也可以自己计算得到q(St,At;w)的梯▽q(St,At;w)，然后利用下式进行更新：

对于状态价值函数，也有类似的分析。定义每一步的损失为［Gt-v(St;w)］2，整个回合的损失为∑ t = 0 T ［ G t − v ( S t ; w ) ］ 2  。可以在自动梯度计算并更新参数的软件包中定义这个损失来更新参数w，也可以用下式更新：

相应的回合更新策略评估算法与算法1类似，此处从略。

将策略改进引入随机梯度下降评估策略，就能实现随机梯度下降最优策略求解。算法2给出了随机梯度下降最优策略求解的算法。它与回合更新最优策略求解算法的区别也仅仅在于迭代的过程中不是直接修改价值估计，而是更新价值参数w。

算法6-2　随机梯度下降求最优策略

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（采样）用环境和当前动作价值估计q(·,·;w)导出的策略（如ε柔性策略）生成轨迹样本S0,A0,R1,S1,A1,R2,…,ST-1,AT-1,RT,ST。
2.2　（初始化回报）G←0。
2.3　（逐步更新）对t←T-1,T-2,…,0，执行以下步骤：
2.3.1　（更新回报）G←γG+R t + 1 R_{t+1}R t+1 ；
2.3.2　（更新动作价值函数）更新参数w以减小［ G − q ( S t , A t ; w ) ］ 2 ［G-q(St,At;w)］^2［G−q(St,At;w)］ 2 （如w←w+α［G-q(St,At;w)］▽q(St,At;w)）。

半梯度下降

动态规划和时序差分学习都用了“自益”来估计回报，回报的估计值与w有关，是存在偏差的。例如，对于单步更新时序差分估计的动作价值函数，回报的估计为U t = R t + 1 + γ q ( S t + 1 , A t + 1 ; w ) ，而动作价值的估计为q ( S t , A t ; w ) )，

这两个估计都与权重w有关。在试图减小每一步的回报估计Ut和动作价值估计q ( S t , A t ; w ) 的差别时，可以定义每一步损失为［ U t − q ( S t , A t ; w ) ］ 2  ，而整个回合的损失为。在更新参数w以减小损失时，应当注意不对回报的估计U t =R t + 1 + γ q ( S t + 1 , A t + 1 ; w ) 求梯度，只对动作价值的估计q ( S t , A t ; w ) )求关于w的梯度，这就是半梯度下降（semi-gradient descent）算法。半梯度下降算法同样既可以用于策略评估，也可以用于求解最优策略（见算法3和算法4）。

算法3　半梯度下降算法估计动作价值或SARSA算法求最优策略

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（初始化状态动作对）选择状态S。如果是策略评估，则用输入策略π(·|S)确定动作A；如果是寻找最优策略，则用当前动作价值估计q(S,·;w)导出的策略（如ε柔性策略）确定动作A。
2.2　如果回合未结束，执行以下操作：
2.2.1　（采样）执行动作A，观测得到奖励R和新状态S’。
2.2.2　如果是策略评估，则用输入策略π(·|S’)确定动作A’；如果是寻找最优策略，则用当前动作价值估计q(S’,·;w)导出的策略（如ε柔性策略）确定动作A’。
2.2.3　（计算回报的估计值）U←R+γq(S’,A’;w)。
2.2.4　（更新动作价值函数）更新参数w以减小［U-q(S,A;w)］^2（如w←w+α［Gq(S,A;w)］▽q(S,A;w)）。注意此步不可以重新计算U。
2.2.5　S←S’，A←A’。

算法6-4　半梯度下降估计状态价值或期望SARSA算法或Q学习

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（初始化状态动作对）选择状态S，再根据输入策略π选择动作A。
2.2　如果回合未结束，执行以下操作。
2.2.1　如果是策略评估，则用输入策略π(·|S)确定动作A；如果是寻找最优策略，则用当前动作价值估计q(S,·;w)导出的策略（如ε柔性策略）确定动作A。
2.2.2　（采样）执行动作A，观测得到奖励R和新状态S’。
2.2.3　如果是策略评估，则用输入策略π确定动作A’；如果是最优价值估计，则用当前动作价值估计q(S’,·;w)导出的策略（如ε柔性策略）确定动作A’。
2.2.4　（计算回报的估计值）如果是动作价值评估，则U ← R + γ v ( S ′ ; w )。如果是期望SARSA算法，则U ← R + γ Σ a π ( a ∣ S ′ ; w ) q ( S ′ , a ; w ) ，其中π ( ⋅ ∣ S ′ ; w ) 是 q ( S ′ , ⋅ ; w ) 确定的策略（如ε柔性策略）。若是Q学习U ← R + γ m a x a q ( S ′ , a ; w ) 。 
2.2.5　（更新动作价值函数）若是状态价值评估则更新w以减小［ U − v ( S ; w ) ］ 2 （ 如 w ← w + α ［ U − v ( S ; w ) ］ ▽ v ( S ; w ) ），若是期望SARSA算法或Q学习则更新参数w以减小［ U − q ( S , A ; w ) ］ 2 （ 如 w ← w + α ［ U − q ( S , A ; w ) ］ ▽ q ( S , A ; w ) ））。注意此步不可以重新计算U。
2.2.6　S←S’。

如果采用能够自动计算微分并更新参数的软件包来减小损失，则务必注意不能对回报的估计求梯度。有些软件包可以阻止计算过程中梯度的传播，也可以在计算回报估计的表达式时使用阻止梯度传播的功能。还有一种方法是复制一份参数w 目标 ← w w_{目标}，在计算回报估计的表达式时用这份复制后的参数w 目 标 来计算回报估计，而在自动微分时只对原来的参数进行微分，这样就可以避免对回报估计求梯度。

本节以半梯度下降SARSA算法为例，介绍最优策略的求解。算法6-5给出了在回合制任务中半梯度下降SARSA算法求解最优策略。它和第5章中SARSA算法的区别在于，它使用了含参函数q(S,A;w)来近似动作价值函数，并且用半梯度下降实现了最优价值函数估计的更新。

算法5　半梯度下降SARSA算法求解最优策略

输入：环境（无数学描述）。
输出：最优动作价值估计q ( S , A ; w ) q(S,A;w)q(S,A;w)。
参数：优化器（隐含学习率α），折扣因子γ，策略改进的参数（如ε），其他控制回合数和回合步数的参数。
1.（初始化）w←任意值。
2.（时序差分更新）对每个回合执行以下操作。
2.1　（初始化状态动作对）选择状态S，再用动作价值q(S,·;w)导出的策略确定动作A。
2.2　如果回合未结束（比如未达到最大步数、S不是终止状态），执行以下操作：
2.2.1　（采样）执行动作A，观测得到奖励R和新状态S’；
2.2.2　用动作价值q ( S ′ , ⋅ ; w ) 导出的策略（如ε柔性策略）确定动作A’；
2.2.3　（计算回报的估计值）U ← R + γ q ( S ′ , A ′ ; w ) ；
2.2.4　（更新价值）更新w以减小［ U − q ( S , A ; w ) ］ 2 （ 如 w ← w + α ［ U − q ( S , A ; w ) ］ ▽ q ( S , A ; w ) ）；
2.2.5　S ← S ′ ， A ← A ′ S←S’。

带资格迹的半梯度下降

资格迹同样可以运用在函数近似算法中，实现回合更新和单步时序差分的折中。这时，资格迹对应价值参数w。具体而言，资格迹参数z和价值参数w具有相同的形状大小，并且逐元素一一对应。资格迹参数中的每个元素表示了在更新价值参数对应元素时应当使用的权重乘以价值估计对该分量的梯度。也就是说，在更新价值参数w的某个分量w对应着资格迹参数z中的某个分量z时，那么在更新w时应当使用以下迭代式更新：

w ← w + α z ［ U − q ( S t , A t ; w ) ］ w,更新动作价值

w ← w + α z ［ U − v ( S t ; w ) ］,更新状态价值

对价值参数整体而言，就有

w ← w + α ［ U − q ( S t , A t ) ］ z ,

w←w+α［U-q(S_t,A_t)］,

更新动作价值更新状态价值当选取资格迹为累积迹时，资格迹的递推定义式如下：当t=0时z0=0；当t>0时

z t = γ λ z t − 1 + ▽ q ( S t , A t ; w ),更新动作价值对应的资格迹
z t = γ λ z t − 1 + ▽ v ( S t ; w ) ,更新状态价值对应的资格迹

算法6和算法7给出了使用资格迹的价值估计和最优策略求解算法。这两个算法都使用了累积迹

算法6　TD(λ)算法估计动作价值或SARSA算法

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（初始化状态动作对）选择状态S。
如果是策略评估，则用输入策略π(·|S)确定动作A；如果是寻找最优策略，则用当前动作价值估计q ( S , ⋅ ; w ) q(S,·;w)q(S,⋅;w)导出的策略（如ε柔性策略）确定动作A。
2.2　如果回合未结束，执行以下操作：
2.2.1　（采样）执行动作A，观测得到奖励R和新状态S’。
2.2.2　如果是策略评估，则用输入策略π(·|S’)确定动作A’；如果是寻找最优策略，则用当前动作价值估计q(S’,·;w)导出的策略（如ε柔性策略）确定动作A’。
2.2.3　（计算回报的估计值）U ← R + γ q ( S ′ , A ′ ; w )。
2.2.4　（更新资格迹）z ← γ λ z + ▽ q ( S , A ; w ) 。
2.2.5　（更新动作价值函数）w ← w + α ［ U − q ( S , A ; w ) ］ z 。
2.2.6　S ← S ′ ， A ← A ′ 。 

算法7　TD(λ)估计状态价值或期望SARSA算法或Q学习

1.（初始化）任意初始化参数w。
2.逐回合执行以下操作。
2.1　（初始化状态动作对）选择状态S，再根据输入策略π选择动作A。
2.2　如果回合未结束，执行以下操作。
2.2.1　如果是策略评估，则用输入策略π(·|S)确定动作A；如果是寻找最优策略，则用当前动作价值估计q ( S , ⋅ ; w ) q(S,·;w)q(S,⋅;w)导出的策略（如ε柔性策略）确定动作A。
2.2.2　（采样）执行动作A，观测得到奖励R和新状态S’。
2.2.3　如果是策略评估，则用输入策略π确定动作A’；如果是最优价值估计，则用当前动作价值估计q ( S ′ , ⋅ ; w )导出的策略（如ε柔性策略）确定动作A’。
2.2.4　（计算回报的估计值）如果是动作价值评估，则U ← R + γ v ( S ′ ; w ) 。如果是期望SARSA算法，则U ← R + γ ∑ a π ( a ∣ S ′ ; w ) q ( S ′ , a ; w ) ，其中π(·|S’;w)是q(S’,·;w)确定的策略（如ε柔性策略）。若是Q学习则U ← R + γ m a x a q ( S ′ , a ; w ) 。
2.2.5　（更新资格迹）若是状态价值评估，则z ← γ λ z + ▽ v ( S ; w ) ；若是期望SARSA算法或Q学习，则z ← γ λ z + ▽ q ( S , A ; w ) 。
2.2.6　（更新动作价值函数）若是状态价值评估，则w ← w + α ［ U − v ( S ; w ) ］ ；若是期望SARSA算法或Q学习，则w ← w + α ［ U − q ( S , A ; w ) ］ z。
2.2.7　S ← S ′ 。