【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.值函数近似
前面我们一直假定强化学习任务是在有限状态空间上进行，每个状态可用一个编号来指代；值函数则是关于有限状态的“表格值函数”（tabular value function），即值函数能表示为一个数组，输入$i$对应的函数值就是数组元素$i$的值，且更改一个状态上的值不会影响其他状态上的值。然而，现实强化学习任务所面临的状态空间往往是连续的，有无穷多个状态。这该怎么办呢？
个人注解：解释下什么叫“有限状态空间”，假设一个小迷宫只有9个格子，那么每个格子就是一个状态，每个状态对应一个状态价值$V$。
一个直接的想法是对状态空间进行离散化，将连续状态空间转化为有限离散状态空间，然后就能使用前面介绍的方法求解。遗憾的是，如何有效地对状态空间进行离散化是一个难题，尤其是在对状态空间进行探索之前。
个人注解：假设自动驾驶汽车的状态为$s=(位置,速度,方向,距离)$，这些变量理论上可以取任意实数。
实际上，我们不妨直接对连续状态空间的值函数进行学习。假定状态空间为$n$维实数空间$X = \mathbb{R}^n$，此时显然无法用表格值函数来记录状态值。先考虑简单情形，即值函数能表达为状态的线性函数：
\[V_{\mathbf{\theta}}(\mathbf{x}) = \mathbf{\theta}^T \mathbf{x} \tag{1}\]其中$\mathbf{x}$为状态向量，$\mathbf{\theta}$为参数向量。由于此时的值函数难以像有限状态那样精确记录每个状态的值，因此这样值函数的求解被称为值函数近似（value function approximation）。
我们希望通过式(1)学得的值函数尽可能近似真实值函数$V^{\pi}$，近似程度常用最小二乘误差来度量：
\[E_{\theta} = \mathbb{E}_{\mathbf{x} \sim \pi} \left[ \left( V^{\pi}(\mathbf{x}) - V_{\mathbf{\theta}}(\mathbf{x}) \right) ^2 \right] \tag{2}\]其中$\mathbb{E}_{\mathbf{x} \sim \pi}$表示由策略$\pi$所采样而得的状态上的期望。
为了使误差最小化，采用梯度下降法，对误差求负导数：
\[\begin{align*} - \frac{\partial E_{\mathbf{\theta}}}{\partial \theta} &= \mathbb{E}_{\mathbf{x} \sim \pi} \left[ 2(V^{\pi}(\mathbf{x}) - V_{\mathbf{\theta}} (\mathbf{x})) \frac{\partial V_{\mathbf{\theta}} (\mathbf{x})}{\partial \mathbf{\theta}} \right] \\&= \mathbb{E}_{\mathbf{x}\sim \pi} \left[ 2 (V^{\pi} (\mathbf{x}) - V_{\mathbf{\theta}} (\mathbf{x}) ) \mathbf{x} \right] \end{align*} \tag{3}\]于是可得到对于单个样本的更新规则：
\[\mathbf{\theta} = \mathbf{\theta} + \alpha (V^{\pi}(\mathbf{x}) - V_{\mathbf{\theta}} (\mathbf{x})) \mathbf{x} \tag{4}\]我们并不知道策略的真实值函数$V^{\pi}$，但可借助时序差分学习，基于$V^{\pi}(\mathbf{x}) = r+\gamma V^{\pi} (\mathbf{x}’)$用当前估计的值函数代替真实值函数，即：
\[\begin{align*} \mathbf{\theta} &= \mathbf{\theta} + \alpha (r + \gamma V_{\mathbf{\theta}}(\mathbf{x}')-V_{\mathbf{\theta}}(\mathbf{x})) \mathbf{x} \\&= \mathbf{\theta} + \alpha (r + \gamma \mathbf{\theta}^T \mathbf{x}' - \mathbf{\theta}^T \mathbf{x}) \mathbf{x} \end{align*} \tag{5}\]其中$\mathbf{x}’$是下一时刻的状态。
需注意的是，在时序差分学习中需要状态-动作值函数以便获取策略。这里一种简单的做法是令$\mathbf{\theta}$作用于表示状态和动作的联合向量上，例如给状态向量增加一维用于存放动作编号，即将式(1)中的$\mathbf{x}$替换为$(\mathbf{x};a)$；另一种做法是用$0/1$对动作选择进行编码得到向量$\mathbf{a}=(0;…;1;…;0)$，其中“1”表示该动作被选择，再将状态向量与其合并得到$(\mathbf{x;a})$，用于替换式(1)中的$\mathbf{x}$。这样就使得线性近似的对象为状态-动作值函数。
基于线性值函数近似来替代Sarsa算法中的值函数，即可得到图16.14的线性值函数近似Sarsa算法。类似地可得到线性值函数近似Q-学习算法。显然，可以容易地用其他学习方法来代替式(1)中的线性学习器，例如通过引入核方法实现非线性值函数近似。
- 第5步：原始策略的$\epsilon$-贪心策略。
- 第6步：式(5)更新参数。
