[强化学习实战]函数近似方法-线性近似与函数近似的收敛性

线性近似

最常使用的函数近似就是线性近似和人工神经网络。本节介绍线性近似。线性近似是用许多特征向量的线性组合来近似价值函数。特征向量则依赖于输入（即状态或状态动作对）。以动作价值近似为例，我们可以为每个状态动作对定义多个不同的特征x ( s , a ) = ( x j ( s , a ) : j ∈ J )，进而定义近似函数为这些特征的线性组合，即 

对于状态函数也有类似的近似方法：

精确查找表与线性近似的关系对于动作价值而言，可以认为有∣ S ∣ × ∣ A ∣个特征向量，每个向量的形式为

即在某个的状态动作对处为1，其他都为0。这样，所有向量的线性组合就是整个动作价值函数，线性组合系数的值就是动作价值函数的值。

线性最小二乘策略评估

在使用线性近似的情况下，不仅可以使用基于随机梯度下降的策略评估方法，还可以使用线性最小二乘来进行策略评估。线性最小二乘是一种批处理（batch）方法，它每次针对多个经验样本，试图找到在整个样本集上最优的估计。

将线性最小二乘用于回合更新，可以得到线性最小二乘回合更新（Linear Least Square Monte Carlo，Linear LSMC）。线性最小二乘回合更新试图最小化 

在线性近似的情形下，其梯度为

将待求的权重w L S M C 代入上式并令其等于零，则有

求解该线性方程组得：

这样就得到了线性最小二乘回合更新的计算式。在实际使用时，直接使用上式更新权重，就实现了线性最小二乘回合更新。
将线性最小二乘用于时序差分，可以得到线性最小二乘时序差分更新（Linear Least Square Temporal Difference，Linear LSTD）。对于单步时序差分的情况，线性最小二乘时序差分试图最小化。

其中U t = R t + 1 + γ q ( S t + 1 , A t + 1 ; w ) 。在线性近似的情况下，其半梯度为

将待求的权重w L S T D 代入上式并令其等于零，则有

求解该线性方程组得：

这样就得到了线性最小二乘时序差分更新的计算式。在实际使用时，直接使用上式更新权重，就实现了线性最小二乘时序差分更新。

线性最小二乘最优策略求解

最小二乘也可以用于最优策略求解。本节介绍基于Q学习的最小二乘最优策略求解算法。

在Q学习中，回报的估计为

这和上一节介绍的时序差分策略估计相比，就是把回报的估计值R t + 1 + γ q ( S t + 1 , A t + 1 ; w ) 中 的 A t + 1 换 成 q ( S t + 1 , a ; w ) 。所以，其最小二乘的解相应从

变为

求解上述最小二乘解，可以得到最优价值函数的估计，进而得到最优策略的更新。据此反复进行策略迭代，就得到了线性最小二乘Q学习算法（见算法8）。

算法8　线性最小二乘Q学习算法求解最优策略

输入：许多经验。
输出：最优动作价值估计q ( s t , a t ; w ) , s ∈ , a ∈ ( s ) q(st,at;w),s∈ ,a∈ (s)q(st,at;w),s∈,a∈(s)和确定性最优策略的估计π。
1.（初始化）w ← 任 意 值 ； 用 q ( s t , a t ; w ) , s ∈ , a ∈ ( s ) 确定贪心策略π。
2.（迭代更新）迭代进行以下操作：
2.1　（更新价值） ，其中是由确定性策
略π决定的在状态%S_{t+1}%的动作。
2.2　（策略改进）根据q ( s , a ; w ′ ) , s ∈ , a ∈ ( s ) 决定确定性策略π’。
2.3　如果达到迭代终止条件（如w和w’足够接近，或π和π’足够接近），则终止迭
代；否则更新w ← w ′ ， π ← π ′ 进行下一轮迭代。

函数近似的收敛性

线性近似具有简单的线性叠加结构，这使得线性近似可以获得额外的收敛性。表1和表2分别给出了策略评估算法和最优策略求解算法的收敛性。在这两个表中，查找表指的是不采用函数近似的方法。一般情况下，它们都能收敛到真实的价值函数或最优价值函数。但是，对于函数近似算法，收敛性往往只在采用梯度下降的回合更新时有保证，而在采用半梯度下降的时序差分方法时是没有保证的。限定函数近似采用线性近似后，在个别情况下收敛情况有提升。当然，所有收敛性都是在学习率满足RobbinsMonro序列的情况下（即同时满足( 1 ) α t ≥ 0 , t = 0 , 1 , … ； ( 2 ) ∑ t = 0 + ∞ α t = + ∞ ( 3 ) ∑ t = 0 + ∞ α 2 < + ∞ 才具有的。线性近似还可以和批处理的线性最小二乘结合，可能得到更好的收敛性。对于能保证收敛的情况，收敛性一般都可以通过验证随机近似Robbins-Monro算法的条件证明。

另外，最优策略求解的收敛性证明用到了其随机优化的版本。

表1　策略评估算法的收敛性

表2　最优策略求解算法的收敛性

值得一提的是，对于异策的Q学习，即使采用了线性近似，仍然不能保证收敛。研究人员发现，只要异策、自益、函数近似这三者同时出现，就不能保证收敛。一个著名的例子是

Baird反例（Baird’s counterexample），有兴趣的读者可以自行查阅。