David silver强化学习课程第六课 值函数近似
第六课 值函数近似
一开始看这节课内容的时候，还是有些乱的。不像前五章每一章的联系都很紧密，本章内容较分散，概念性的东西变少了，更多的引入了几种不同的算法，可以直接从算法上理解本课的内容—值函数近似。
对于预测问题，我们可以参数化的表示状态值函数；对于预测问题，可以参数化的表示状态-动作值函数。本章讲了值函数近似的两种方法：增量方法和批方法，这两种方法主要在数据的使用上有所不同，但是都是基于随机梯度下降法。本章最后还引入了线性值函数近似的直接求解方法。
上述方法在MC/TD(0)/TD(λ)下均有不同实现方式，同时本章列表对比了这些算法的收敛性。
前言
第四节课和第五节课讲了Model-free的基于值函数的预测和控制，每一个状态/状态-动作对都有唯一确定的状态值/状态动作值。这种方式类似于建一张表，将每个状态/状态-动作对存储其中，并在学习的过程中更新所有的值。
在实际生活中，我们可能面临的问题规模很大，具有很多的状态/状态-动作对（例如围棋有2**170个状态；飞机控制是连续的状态空间，存在无数个状态），无论是对存储的容量或是学习的速度来讲存储和更新每一个状态/状态-动作对显然是不现实的。因此引入本节将要讲的内容，利用值函数近似来估计任意状态下的值函数：
引入参数w来拟合任意状态的值函数，参数w可以用MC或TD方法更新。
值函数近似的类型：
- 状态作为输入，直接估计状态值函数
- 状态和动作作为输入，直接估计状态-动作值函数
- 状态作为输入，输出该状态下可能的状态-动作值函数
值函数近似方法：
- 特征线性组合（可微，参数是特征的权重）
- 神经网络（可微，参数是每层的连接权重）
- 决策树
- 最近邻
- 傅里叶
线性回归和神经网络在强化学习里应用得比较广泛，主要是考虑这两类方法是一个针对状态可导的近似函数。
进而，针对强化学习场景，我们需要适用于非静态、非独立同分布的数据训练方法来得到近似值函数。接下来讲了两种数据训练方法：递增方法和批方法。有点类似于机器学习当中的随机梯度下降和小批量梯度下降（批方法和小批量梯度下降还有点不太相同，后面会提到这个问题）。
1 增量方法
梯度下降
递增方法和批方法都是基于梯度下降，简单来说，梯度下降就是目标函数J(θ)朝着参数w的梯度的反方向更新w，使得J(θ)找到局部最小值，α是学习速率。
值函数近似：利用随机梯度下降
目标：找到参数w，最小化值函数预测值v^(S,w)和真实值vπ(S)之间的均方误差。
梯度下降可以找到局部最小值：
随机梯度下降对梯度进行采样，然后更新w：
注：第二个式子实际上是批量梯度下降，这里不使用批量梯度下降而使用随机梯度下降更新参数w，因为批量梯度下降这种方法在每次迭代中使用所有的数据对参数进行更新（实际上使用所有数据对参数进行更新的意思是就是用策略π对应的所有样本去更新参数，但这是无法实现的）。随机梯度下降对于参数w的期望更新与批量梯度下降是一致的。
线性值函数近似
将状态表示为特征向量：
用特征的线性组合表示值函数：
目标方程就变为:
使用随机梯度下降可以获得全局最优解（针对凸函数），参数更新大小为：
查表法可以看作线性值函数近似的特殊情况，有所有状态的0、1表示组成特征向量：
增量预测算法
增量预测算法实际上就是基于随机梯度下降的值函数近似方法。然而上面提到的随机梯度下降式子中存在我们不知道的真实值Vπ(S)，因此我们需要寻找Vπ(S)的代替值。
可以使用我们第四课讲过的三种方法：
-
MC，使用Gt作为目标值：
-
TD(0)，使用TD target作为目标值：
-
TD(λ)，使用λ-回报作为目标值：
注意这三种方法不对目标值求w的偏导，否则会导致不收敛。
对于使用MC来近似值函数，回报Gt是真实值Vπ(S)的有噪音，无偏采样。Gt可以看作监督学习中的标签，无论是线性MC值函数近似还是非线性MC值函数近似，都会收敛至局部最优（应该和无偏采样有关）。
对于使用线性TD(0)来近似值函数，TD-target是真实值Vπ(S)的有偏采样，近似收敛至全局最优。
对于使用TD(λ)来近似值函数，λ-回报Gtλ是真实值Vπ(S)的有偏估计，对于前向视角的线性TD(λ)：
对于后向视角的TD(λ)：
近似值函数控制
在预测问题中，我们计算状态值函数v；在控制问题中，我们计算状态-动作值函数q。
将预测值q^(·，·，w)作为qπ的近似策略评估值，从初始参数w开始，利用ε-贪婪策略选择动作，计算该动作下的目标值，然后更新参数w；反复选择动作、更新w逼近最优价值函数。（和策略迭代相比，策略迭代利用未来预期回报和q(s,a)的差值来更新q(s,a)；而这里利用这种类似的差值更新参数w）
动作-状态值函数近似
策略π的动作-状态值函数近似表示为：
目标：最小化近似动作-状态值函数和真实动作-状态值函数：
使用随机梯度下降，可以找到局部最小值：
线性动作-状态值函数近似
使用特征向量表示动作-状态：
通过特征的线性组合表示近似动作-状态值函数：
随机梯度下降更新：
增量控制算法
类似于增量预测算法，这里需要找到真实状态-动作值qπ(S,A)的目标值。
-
对于MC，使用Gt作为目标值：
-
对于TD(0)，使用TDtarget作为目标值：
-
对于前向视角的TD(λ)，使用动作-状态λ回报作为目标值：
-
对于后向视角的TD(λ)，等价更新为：
我们应该使用自举(bootstrap)吗？
在增量预测和控制问题中，根据是否自举我们有两种解决方案，MC和TD(λ)。如图所示显然自举的效果是优于不自举的(MC)。
预测算法的收敛性
TD算法不遵循任何目标函数的梯度，这导致在异策略或者非线性函数近似情况下发散。
Gradient TD遵循projected Bellman error的梯度而收敛。
控制算法的收敛性
(√) 表示在最优价值函数附近震荡
2 批方法
之前提到的随机梯度下降比较简单，在经历一步后利用这步的数据更新w，然后这步的数据就丢弃了，这并不是高效采样(sample efficient)。批方法则利用过去的经验，去寻找最优价值函数。
最小平方差预测
首先给出近似价值函数：
还有包含<状态，价值>对的经验D：
最小二乘法(Least squares)要求找到参数w最小化：
使用基于经验回放的随机梯度下降可以实现以上算法（相比于增量方法它的效率高）：
-
从经验D中采样：
-
应用随机梯度下降：
收敛至最小二乘法：
思考：如果将本课的增量方法/批方法和深度学习中随机梯度下降/小批量梯度下降对比。可能有以下几个角度：1 有无放回/经验重用 2 随机的含义
感觉批方法更类似于深度学习当中的随机梯度下降法（这里是笼统的定义，具体来说SGD和BGD、mini-BGD都不一样）
DQN
DQN使用了经验回放和固定Q-目标网络两个小技巧，能做到收敛而且保持很好的鲁棒性。
要点如下：
- 首先采取ε-贪婪获得大量的状态转移信息：(st, at, rt+1, st+1)并存储在D中。
- 然后随机从D中采样batch_size个样本。
- 使用固定目标网络计算目标值
- 利用随机梯度下降优化MSE（实际上这里就是小批量梯度下降）
线性最小二乘法预测
经验回放可以找到最小二乘法的结果，提高稳定性，但是需要迭代很多次。使用线性值函数近似我们可以直接求解最小二乘法：
线性函数近似：
对于最小化LS(w)，就是说期望的参数更新等于0：
直接求解w得到：
对于N个特征，直接求解的时间复杂度为O(N**3)。求解的时间复杂度和特征数量有关，与状态空间大小无关。
由于我们不知道真是值函数，因此可以利用MC/TD(0)/TD(λ)的目标值代替真实值，得到LSMC/LSTD/LSTD(λ)三种方法：
线性最小二乘法预测的收敛性：
注：对于最小二乘法动作-状态值近似也是类似的，只是换成近似状态-动作值函数。
最小二乘法控制
对于策略评估，我们想要高效利用所有的经验，这些经验从多种策略中产生，所以评估qπ(S,A)是异策略的。
在这里使用和Q-learning相同的思想：
-
使用旧策略产生的经验：
-
利用待评估策略产生下一个动作A’：
-
利用A‘更新q^(St,At,w):
这里引入最小二乘q-learning解决预测问题（更新参数w）：
- 首先考虑线性q-learning更新：
- 对于总更新量△w=0，得到LSTDQ算法：
然后利用LSTDQ算法用来进行策略评估，得到最小二乘策略迭代算法LSPI-TD：
最后给出几种控制算法的收敛性：
可以看到LSPI-TD改善了q-learning在线性近似值函数下的不收敛性。