1. Introduction

在现实中需要用强化学习解决的问题，往往是非常复杂的，它们要么具有非常大的状态空间（10的几百次方），要么就是一个连续的状态空间。这种情况下，我们即使有无限的时间和数据，都很难找到一个最优的Policy，只能退而求其次，尽可能寻找一个好的近似解。状态空间过大带来的主要问题并不是需要超大的存储空间，而且需要巨量的时间和数据去获得足够精准的value function。因为状态空间过大，就会使得可能训练数据中的每个状态都是之前从未出现过的，如何借助在某种条件下有些相似的状态来对现在的状态进行合理的决策就成了主要的问题。换句话说，此时的强化学习核心问题就在于Generalization——如何利用有限的状态子集泛化到整个状态空间以获得一个好的近似？

幸运的是，泛化问题是一个早已经被广泛研究的问题，所以我们无需发明新的算法，而是将已有的解决泛化的算法用在强化学习就行，其中有一种叫做function approximation最为合适。这是一种监督学习的算法，旨在利用目标函数的一些示例，从中归纳并构造整个函数的近似值。不过，相比于传统的监督信息场景，在强化学习存在 non-stationarity（数据的统计性质会随着环境或者时间等发生变化）, bootstrapping, delayed targets 这几个问题，这也是需要去解决的。

下图是强化学习中function approximation的三种形式：

输入状态S，学习一个参数W（例如神经网络等），使得可以输出state value
输入状态S和动作A，学习参数W，输出action value
输入状态S，学习参数W，输出所有动作的action value

2. Incremental Methods

2.1 Gradient Descent

梯度下降的概念应该都很熟悉，这里不介绍了，review一下PPT就行。

使用随机梯度下降去进行Value Function Approx也很简单，和机器学习的套路一样，定义一个Loss，然后求梯度，沿着梯度方向更新，这里使用MSE作为Loss：

2.2 Linear Function Approximation

我们可以用多种形式来表示状态，比如说我们可以定义一个feature vector，来对原来的状态进行线性组合，以获得更好的表示形式，其中 $\mathbf{x}_{i}:S → \mathrm{R}$ ，表示一个将状态映射到一个实数的函数，也就是说feature vector将一个状态映射成了一组 $n$ 个实数表示的向量：

$$
\mathbf{x}(S)=\left(\begin{array}{c}
\mathbf{x}_{1}(S) \\
\vdots \\
\mathbf{x}_{n}(S)
\end{array}\right)
$$

接着就可以按照梯度下降的步骤去进行学习，此时我们的梯度实际上就变成了 $x(S)$：

2.3 Incremental Prediction Algorithms

我们可以发现，在上面这些算法中，我们都假定了已知一段Episode的真实value值，作为监督信号。但是在RL中，Model-free的场景下我们唯一能知道的只有某个具体step的reward，然而真实的value是一个状态的return期望，我们无法获取所有状态的转移概率，自然无法得到准确的value值。

所以在实际使用中，我们使用value prediction的值替代监督信号，主要包括MC，TD等方法，就是将这些方法估计出的state value替代真实的value计算Loss，其中：

MC估计的 value 是无偏的，但是属于有噪声采样，方差高，受制于采样的质量，容易陷入局部最优解
TD类的估计是有偏估计，但是通过逐步更新机制，它可以反复修正偏差，理论上可以收敛至全局最优解

2.4 Incremental Control Algorithms

好，现在到了Control，如果看过前面Model-free Control，就知道依葫芦画瓢——无非就是从 State Value 变成 Action Value，然后套上 Function Approximation 的壳子，公式变的更复杂一点：

下面举一个例子：

该任务是控制小车在山谷里到达Goal，但是小车的动力不足以摆脱重力，无法从底部一次到达Goal，所以小车必须先后退到另一侧，然后借助重力冲到Goal上。这是非常经典的一个问题——小车首先需要远离目标，然后才能实现目标，很多Control的方法很难解决这一类问题，除非加入人类先验知识。然而，我们使用强化学习就可以解决这个问题，下图展示了训练过程，Z轴是reward的相反数。可以看到Step428时，连一个Episode都没完成，说明小车经过428次行动都没能到达Goal，一直在山谷之间左右摇摆。由于没有到达Goal，reward就一直是-1，所以可以看到图像呈现一个“盆地”的形状——所有被访问过的状态都被赋予更差的value，而没有被访问过的state还是处于初始值（value=0）。这样的value可以驱动小车朝着之前没有访问过的state不断探索，直到成功访问到了Goal，完成一个Episode。随后，在Episode12我们可以看见，图像初步成型，在经过多次迭代，形成最终的图像。

2.5 Convergence of Algorithms

3. Batch Methods

出发点是Incremental的方法每条数据更新一次就会舍弃不用，数据利用率太低，并且训练也会更加不稳定和低效，因此使用Batch化进行训练。

3.1 Least Squares Prediction

最简单的思路就是使用最小二乘法：

定义一个数据集，包含一些state-value对，然后对所有的state-value对计算Loss和，作为最终的Loss。

然后重复采样，SGD更新，再采样再SGD更新…的反复，直到收敛：

3.2 DQN

上述这样的方法简单粗暴，也算能解决问题。但是有两个问题：

target不稳定：我们在实际训练时，无法获得正式的value作为监督信号，所以一般都是使用一个估计值来代替，以Q-Learning为例，target就是 $r + \gamma max_{a^{\prime}}Q_{\theta_t}(s^{\prime}, a^{\prime})$ ，但是这个值本身还是依赖于 $Q_{\theta}(s, a)$ 的，所以我们如果改变 $\theta$ ，就会同时改变target，从而使得target不稳定。
同一个trajectory的数据相关性：在函数近似的方法里，我们通过修改参数 $\theta$ 使 $Q(s,a)$ 更加接近 target，可能会将 $s$ 附近其他状态的value也修改。比如我们调整参数之后 $Q(s,a)$ 变大了，那么如果 $s’$ 很接近 $s$，那么 $Q(s’,a)$ 也会变大。因此这会起到一种放大作用，使得所有估计都偏大，这就很容易造成训练的不稳定。

上述两个问题使得函数估计的方法很难应用在神经网络的训练中，特别是第二个问题，导致神经网络难以收敛。Deep Q-Networks DQN就解决了这一问题，主要提出两个策略分别解决上述两个问题：

Experience Replay：为了避免同一个Episode数据的相关性，DQN提出了Experience Replay的方法。它会有一个replay buffer，用来存储近期采样得到的一些 $(s,a,r,s’)$ 。训练的时候随机的从replay buffer里均匀的采样一个minibatch的 $(s,a,r,s’)$ 来调整参数 $\theta$。因为是随机挑选的，所以这些数据不太可能有前后相关性。当然能支持Experience Replay是因为Q-Learning很好的特性——off-policy，在计算target的时候只需要 $(s,a,r,s’)$

Target Network：为了解决target不稳定的问题，DQN引入了一个Target Network $Q_{θ^′}$，这个神经网络和之前的完全一样，只不过它的参数 $\theta^{\prime}$ 不会更新那么频繁，通常是经过一定时间才从$𝜃$ 里复制过来一次，这样可以保证target的稳定性。

于是，我们就可以得到DQN的伪代码 [1]：