强化学习基础篇（二十八）值函数近似法（Value Function Approximation）
在大规模的强化学习任务求解中，精确获得状态值或动作值较为困难。而值函数近似法通过寻找状态值或动作值
的近似替代函数
或
的方式来求解大规模强化学习任务，既避免了表格求解法所需大规模存储空间的问题，又提升了求解效率，是实际求解任务中被泛采纳的一种算法。
1、大规模强化学习
强化学习是可以去解决很多非常大型的问题的，比如像Backgammon游戏中有着个状态，在围棋游戏中有着
个状态，此外一些连续状态空间的环境也有着无数的状态。
那么如何把model-free方法中的预测与控制的算法应用在这些大规模强化学习任务之中呢？
这就需要使用值函数近似法，在之前我们所介绍的算法都是基于表格查找，也就是每一个状态在
的表格中都有相应的条目索引，或者说每个state-action对
在
的表格中都有相应的条目索引。
但是表格型的表述方法在大型的MDP问题中有着致命性的问题：
- 一是，存储这些大量的状态或者动作信息将会耗费海量的内存
- 二是，去单独学习每个状态的价值非常得慢。
所以，对于大型的MDP问题，我们只能使用函数去近似价值函数：
使用这种近似价值方法一方面可以将价值函数的近似从可见状态泛化到不可见状态，另一方面我们可以使用MC或TD学习的方法更新参数。
2、函数近似的模式
价值函数的近似可以有三种主要的方式：
- 输入状态
，输出价值函数
- 输入状态
，输出Q函数
.
- 输入状态
近似函数可以有很多的选择，比如线性函数，神经网络，决策树，最近邻算法，傅里叶基，小波变化等等。我们主要会集中于可微分的近似函数，比如线性函数和神经网络。
强化学习应用的场景其数据通常是非静态（non-stationary）、非独立同分布（non-iid）的，因为下一个状态通常与前一个状态高度相关。因此，函数近似器也需要适用于非静态、非独立同分布的数据
3、梯度下降（Gradient Descent）
如果目标函数是一个关于参数
的可微分函数，那么目标函数
的梯度就是：
为了去找到目标函数的最小值，我们只需要将参数
想着梯度的反方向进行调整。
，这里的超参数
是学习率。
梯度下降的可视化就可以看成沿着图形最陡峭的方向进行参数调整：
4、随机梯度下降（Stochastic Gradient Descent）
我如果已经知道策略的真实的价值函数
，那么我们可以将目标函数定义近似函数
和真实的价值函数
之间的均方误差（Mean-squared error ，MSE），我们需要找到为参数为
去最小化MSE的方法。
其关于参数梯度为：
上面计算期望在大型环境中是很困难的，他需要求出策略的概率分布，然后再加权求和。这样操作过于复杂，实际操作的时候会采用蒙特卡洛的形式，只用一个样本或者一批样本进行更新，此时会产生一定的样本误差。当样本足够多的时候，所有更新方向加权后就能逼近真实的梯度方向。）
随机梯度下降算法会对梯度进行采样：
5、线性函数近似
特征向量
状态我们是可以拆解为有一堆特征组成，所有的特征可以组成特征向量：
线性值函数近似
如果将值函数由线性方程来表示，可以是：
其MSE的目标函数可以表示为：
对于线性值函数近似，我们使用SGD方法是可以收敛到全局最优解的，其梯度更新的过程也非常得简洁：
这个梯度的更新过程，直观的看是：
表格检索特征
表格检索是线性值函数近似的一种特殊形式，他吧每一个状态看成一个特征，个体具体处在某一个状态时，该状态特征取1，其余取0。参数的数目就是状态数，也就是每一个状态特征有一个参数。特征的形式是：
参数向量本质上相当于给了每个状态对应的值函数:
6、增量预测算法
之前是假设了给定了真实的值函数，但是在RL环境中，并不知道真实的值函数，只有奖励值，所以在实际中，我们会用目标（target）去替换真实的值函数
，目标可以使用MC,
或
的方法计算：
-
如果使用MC方法，目标是回报值
:
如果使用
方法，则用TD目标
。
如果使用
方法，则用
使用MC方法的价值函数近似
如果使用MC方法，目标是回报值，
是一个对真实价值函数
的无偏差，但噪声很大的采样。我们在收集到很多训练数据后应用监督学习的方法进行训练。训练数据就是没个状态得到的回报对：
如果使用线性函数作为价值函数的近似，那么其MC方法下的梯度为：
MC评估方法在应用中就算是使用非线性价值函数近似，也可以收敛到局部最优解，
使用
方法的价值函数近似
如果使用方法，则用TD目标
，这是对真实价值函数
的有偏差采样，其收集到的训练数据是这样的：
如果使用线性函数作为价值函数的近似，那么其方法下的梯度为：
在收敛性上几乎可以收敛到全局最优解。
使用方法的价值函数近似
如果使用方法，则用
，其收集到的训练数据是这样的：
如果使用线性函数作为价值函数的近似，那么前向方法下的梯度为：
后向方法下的梯度为：
7、增量控制算法
控制的算法是指使用函数近似Q函数，。
在知道真实的action-value的时候，我们可以还是可以使用MSE作为目标函数：
然后用随机梯度下降（SGD）找到局部最优解：
使用线性函数近似Q函数
如果使用线性函数近似Q函数，我们将state-action对通过特征向量进行描述：
然后Q函数就可以表示为：
其SGD的更新方式为：
使用MC方法的Q函数近似
使用MC方法的Q函数近似，是将回报值代替真实的Q函数值
，其更新方式为：
使用
方法的Q函数近似
使用方法的Q函数近似，是将
代替真实的Q函数值
，其更新方式为：
使用方法的Q函数近似
使用前向方法的Q函数近似，是将
回报代替真实的Q函数值
，其更新方式为：
其等价的使用后向观点的方法中，使用资格迹进行如下更新：
8、收敛性
几种算法之间的收敛性比较在下面几张图。
首先是预测算法的收敛性，在On-policy与Off-policy下都是MC最优。
从预测算法的收敛性上可以看到TD算法的Off-policy上的收敛性较差，但是如果使用Gradient TD会好很多。
在控制算法的收敛性上的比较，其中 (✓) 表示接近最优值函数。
[图片上传失败...(image-be584f-1604324484205)]
9、批量方法（Batch Method）
前面讲的部分都是使用梯度下降进行增量更新，以使得目标函数接近最优解。但是其采样效率很低，批量方法进行批量得对训练数据进行学习，具有更高的效率。批方法要在最大化利用数据的同时去找到对于值函数最好的拟合。
MSE
假设给定近似函数，并且给定包含大量state-value对的经验池
，
我们需要找到一个最佳的参数能够使得函数
能够拟合经验池
中的所有数据，MSE作为目标函数就可以找到最优解：
使用经验回放的SGD
在给定经验池时，我们可以重复下面两个步骤应用SGD：
- 从经验池
中进行（state，value）对的采样：
- 应用SGD进行参数更新：
这样的结果可以收敛到最小二乘解：
DQN算法
DQN算法的成功就是主要使用了经验池与固定的目标Q网络两种技术，其关键在于以下几点：
使用
策略选取动作
将产生的转移数据
存储到经验池
从经验池
根据旧的，并且固定的参数
计算Q函数的目标值
优化Q-network和Q函数目标值之间的目标函数MSE：
使用SGD进行参数更新
DQN算法在Atari游戏中的应用
DQN算法在Atari游戏训练过程中，端到端得从游戏像素中学习Q函数
，其状态
是根据游戏最后4帧画面叠加而成，然后输出游戏手柄中18个动作按钮的Q值，其奖励就是在执行动作后游戏中的分数。
网络拓扑图如下所示：
线性最小二乘预测
在使用经验池的时候我们可以找到最小二乘解，但是知道最优解还是会花费非常多的迭代。如果使用线性近似函数，我们就可以直接找到最小二乘解。
在最小化的过程中，我们
的期望为0进行推导：
如果有N个特征，这种直接求解的复杂度是，如果使用Shermann-Morrison方法进行迭代更新可以将复杂度降低到
在不知道真实价值的时候，在实际中就需要使用到MC,TD的方法进行采样代替
。
- 如果使用MC方法，就有LSMC（Least Squares Monte-Carlo）算法，使用回报代替真值：
- 如果使用TD方法，就有LSTD（Least Squares Temporal-Di�erence）算法，
- 如果使用
回报代替真值:
在这三种方法的时候都可以直接进行求解最小二乘解：
对于LSMC:
对于LSTD：
对于LSTD():
这三种预测算法的收敛性如下：
最小二乘的策略迭代
使用最小二乘方法进行策略迭代的过程，只是在策略评估过程中使用least square Q-learning。
线性最小二乘控制
如果线性函数对q函数进行近似，
然后最小化真实与预测的
之间的MSE，其中
来自于经验池的
state,action
value
对：
在策略评估中，我们是要去高效得利用已有的经验，但是在控制中，我们是要去提升策略。经验池中的经验是从许多的策略中采样产生的，所以对进行评估必须进行off-policy学习，需要使用和Q-learning一样的想法：
- 使用旧的策略产生经验：
- 根据后续状态产生动作：
- 更新q函数
：
然后我们继续考虑线性函数的增量更新方式为：
如果使用最小二乘的方法直接求解：
我们利用这里的LSTDQ对值函数进行估计，得到下面的LSPI算法：
控制算法的收敛性：
