7.值函数方法（Value Function Methods）

1. 从Actor-Critc算法中抛开策略梯度

首先回顾下之前的actor-critic算法，其中的优势函数体现的是在策略下，执行动作要比平均reward好多少。

image.png

如果从actor-critic算法中，我们去除掉第四步的梯度部分，那么我们可以基于优势函数并选择最大化优势函数的动作，即 。这种情况下我们新的策略就可以是如下表示：

image.png

这种新的策略虽然说不一定是最好的，但是至少能够和原来的策略一样好。

2. 策略迭代（Policy Iteration）

从宏观上来看，我们新的方法可以表示为如下两个步骤的迭代，首先是评估优势函数，然后是更新策略。 image.png

和之前的actor-critic算法一样，其中的优势函数的计算是需要通过评估值函数进行的，即我们需要解决的是如何评估。

image.png

这一类的方法在广义上被称为动态规划（Dynamic Programming）。为了去解决如何评估的问题，我们首先需要加假设是已知的，并且状态空间与动作空间都是离散的。这样我们就可以为构建一个完整的表格，如下所示：

image.png

这样我们就可以通过bootstrapped更新得到值函数：

image.png

通过值函数我们选择了最大的优势函数，这样就构建了一个确定性的策略。

3. 策略迭代结合Dynamic Programming

第一步：评估

image.png

第二步：更新策略

这里的第二步中，我们之前的的策略是，但是在给定下，与之间只差了一个常数， 因此,所以可以用Q去代替A。

通过去查询每个状态对应的最大值的动作，我们就可以表示为一个新的基于Q的策略。

所以，更加简化一点我们可以跳过策略，直接计算Values.

image.png

4. 结合深度网络的fitted value iteration

我们可以用神经网络去拟合值函数，这样避免在表格表示中的维数灾难问题。

image.png

从fitted value iteration算法的第一步可以看到，我们需要知道不同的动作的对应的最大输出。然后第二步是去通过优化方法训练神经网络让网络输出与目标值函数之间的差异降低。但是第一步的max很难实现，因为max的前提是我们假设已经知道了transition dynamic。

但是如果我们不知道transition dynamic怎么办呢？在value Iteration中，我们第一步是求解Q，第二步用Q去更新策略。我们对V的反复迭代，可以使用Q去代替。同时Q函数可以使用样本拟合。

image.png

5. fitted Q iteration algorithm

我们可以和fitted value iteration算法一样，同样去拟合Q函数。进而得到了fitted Q iteration algorithm。

image.png

fitted Q iteration algorithm的好处在于不需要去同一状态尝试不同的行动选项，因为Q函数已经告诉你不同行动的效果了：我们无需在真实环境中尝试各种不同行动后复位，而只需要在我们所涉及的Q函数拟合器上做这点就可以了。此外，我们这样的两步算法有很大的优点。第一，算法中只需要用到很多的转移样本，而这些样本是可以off-line的。第二，这个算法只用到一个网络，没有用到策略梯度，因此也没有高方差的问题。但是，这个算法的致命缺点是，对于这样的非线性函数拟合机制下的算法，没有任何收敛性保证（不进行拟合的大表格Q迭代算法在一定条件下有收敛性。一个完整的Fitted Q-iteration的框架是这样的：

image.png

为什么Q-iteration是off-policy呢？

因为第二步和第三步的计算没有需要用到当前策略下的数据，而只是大量的就可以了。

fitted Q-iteration算法到底在优化什么呢？

第二步中，如果我们是表格Q函数迭代的话，max就是在改进策略。第三步中，我们在最小化一个期望误差

image.png

也被称为Bellman误差。可以发现，在理想情况下，如果这个误差为0，那么我们所求得的Q函数就满足

image.png

这正是确定最优Q函数的Bellman方程，也对应了最优策略：

[图片上传失败...(image-9e9201-1577635119153)]

这个最优策略最大化期望收益。如果我们不使用近似，且每个有概率发生的话，那么我们可以说期望误差为0对应着最优策略。

这里需要注意，虽然该算法是offline的，但是我们还是需要让收集的不能太失真。

6. Online Q iteration

在之前的拟合Q函数迭代算法中，我们收集大量数据，然后反复做样本回归。我们把每次收集的样本数设为1，然后把K设为1，并且设置只走一个梯度步，就变成了在线Q迭代算法 (Online Q-iteration)，循环以下三步。

image.png