首先我们需要知道用于训练减小误差的均值方差公式：
$$
\overline{\mathrm{VE}}(\mathbf{w}) \doteq \sum_{s \in \mathcal{S}} \mu(s)\left[v_\pi(s)-\hat{v}(s, \mathbf{w})\right]^2
$$

其实在目前的研究中，均值方差未必是最好的目标函数，但是现在还没有找到其他更好的函数，且该目标函数是有效的，因此就一直连用了。

Episodic离散情况下的状态分布：
$$
\mu(s)=\frac{\eta(s)}{\sum_{s^{\prime}} \eta\left(s^{\prime}\right)}, \quad \text { for all } s \in \mathcal{S}
$$
其中$\eta$ 表示在每一个状态上的平均停留时间（步）：
$$
\eta(s)=h(s)+\sum_{\bar{s}} \eta(\bar{s}) \sum_a \pi(a \mid \bar{s}) p(s \mid \bar{s}, a), \quad \text { for all } s \in \mathcal{S} \text {. }
$$
$\bar{s}$： 状态$s$的前一个状态

$p(s \mid \bar{s}, a)$：从状态$\bar{s}$到状态$s$ 通过动作$a$转移到达的概率

$h(s)$: 表示episode从状态$s$开始的概率

SGD stochastic gradient-descent 随机梯度上升

使$\overline{VE}$ 达到最小，一个较好的策略是尽量减少观察到的样本的误差，由于$\overline{VE}$ 是权值$\mathbf{w}$的函数，则使用SGD方法来更新权值就是使用样本误差在最小化$\overline{VE}$ 的梯度方向上对权值$\mathbf{w}$进行更新。
$$
\begin{aligned}
\mathbf{w}_{t+1} & \doteq \mathbf{w}_t-\frac{1}{2} \alpha \nabla\left[v_\pi\left(S_t\right)-\hat{v}\left(S_t, \mathbf{w}_t\right)\right]^2 \
&=\mathbf{w}_t+\alpha\left[v_\pi\left(S_t\right)-\hat{v}\left(S_t, \mathbf{w}_t\right)\right] \nabla \hat{v}\left(S_t, \mathbf{w}_t\right)
\end{aligned}
$$
$\alpha$: 学习率

求梯度的函数为：
$$
\begin{equation}
\nabla f(\mathbf{w}) \doteq\left(\frac{\partial f(\mathbf{w})}{\partial w_1}, \frac{\partial f(\mathbf{w})}{\partial w_2}, \ldots, \frac{\partial f(\mathbf{w})}{\partial w_d}\right)^{\top}
\end{equation}
$$

Remark

  1. 一般来说，使用实际的状态值函数得到样本$S_t$的状态值$v_{\pi}(S_t)$很难得到，因此需要对其进行估计，使用$U_t$表示对状态$S_t$的估计状态值，则将$U_t$替换到公式中得到：
    $$
    \begin{equation}\label{w-update}
    \mathbf{w}_{t+1} \doteq \mathbf{w}_t+\alpha\left[U_t-\hat{v}\left(S_t, \mathbf{w}_t\right)\right] \nabla \hat{v}\left(S_t, \mathbf{w}t\right)
    \end{equation}
    $$
    如果$U_t$是对$v    {\pi}(S_t)$的无偏估计，那$\mathbf{w_t}$就能够保证收敛到局部最优。

Monte Carlo SGD

如果是episodic的情况下，就是完全进行一个episode再对$\mathbf{w}$进行更新的话，就可以将$U_t$换成$G_t$, 即：
$$
\begin{equation}\label{montecalosgd}
\mathbf{w} \leftarrow \mathbf{w}+\alpha\left[G_t-\hat{v}\left(S_t, \mathbf{w}\right)\right] \nabla \hat{v}\left(S_t, \mathbf{w}\right)
\end{equation}
$$
很明显这就是蒙特卡洛的SGD更新算法

image-20221119171836664

Semi gradient methods

样本的目标值$v_{\pi}(S_t)$ 在SGD公式里是独立于$\mathbf{w}$ 存在的，因此，如果使用bootstrapping的方法来估计$v_{\pi}(S_t)$的话就会失效，这是因为bootstrapping的方法产生的目标值都是依赖于当前的$\mathbf{w}$值的，如：

  • n-step return $G_{t: t+n}$
  • DP 方法$\sum_{a, s^{\prime}, r} \pi\left(a \mid S_t\right) p\left(s^{\prime}, r \mid S_t, a\right)\left[r+\gamma \hat{v}\left(s^{\prime}, \mathbf{w}_t\right)\right]$

这些bootstrapping方法产生target value的公式中都含有当前的$\mathbf{w}$，因此会导致最后的结果是有偏的结果，所以产生的差值也都是有偏的，因此自然差值的梯度不是完全真实的梯度值，所以这种只注重通过梯度改变权重系数，但没有注意到梯度的真实来源的方法称之为 semi-gradient 方法.

Semi-gradient TD(0) method

如果令目标值$U_t \doteq R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}\right)$ 代入原方程就得到了semi-gradient TD(0)算法

image-20221119174506259

semi-gradient方法的优点是速度快，可以不用等到整个episode都进行完再回溯使用return，但是这种方法也有问题，即不能够稳定地保证收敛，不过这种也分情况，在线性情况下semi-gradient方法基本上也是可以保证收敛的。

Liner Methods 线性方法

线性方法就是采用将特征值线性组合的方式来模拟状态值：
$$
\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}^{\top} \mathbf{x}(s) \doteq \sum_{i=1}^d w_i x_i(s)
$$
$\mathbf{x}(s)$:特征向量，用以表示状态$s$，

其中每一个分量$x_i(s)$都是对状态$s$的映射，表示为$x_i: \mathcal{S} \rightarrow \mathbb{R}$，注意在这里$s$是一个单个的状态，而$x_i$表示在某一个维度上（第$i$维上）对状态$s$的映射，整个$\mathbf{x}(s)$才是对状态$s$完整的映射，充分将状态$s$映射到实数域$\mathbb{R}$。

在线性方法里，特征向量$\mathbf{x}$都是基函数（basis function），因为这些特征向量形成估计函数的$d$维线性基（即一个特征向量有$d$维，每一维分量表示一部分最基础的映射，所谓基函数，意思就是没有拉伸旋转或者乘以某个倍数，是构成其他函数的最简化的形式），因此，状态值估计函数对于权值$\mathbf{w}$ 的偏微分就等于特征值（因为它比较基）。
$$
\nabla \hat{v}(s, \mathbf{w})=\mathbf{x}(s)
$$
所以对于公式$\eqref{w-update} \mathbf{w}$的更新函数就简化变成了
$$
\mathbf{w}_{t+1} \doteq \mathbf{w}_t+\alpha\left[U_t-\hat{v}\left(S_t, \mathbf{w}_t\right)\right] \mathbf{x}\left(S_t\right)
$$
这样就可以直接应用特征值对权值进行更新，而不需要计算状态值函数的梯度了。

Remark

  • 线性方法的另一个好处就是由于其对状态值函数的估计是基于线性拟合的，所以全局最优点只有一个，因此使用蒙特卡洛SGD方法$\eqref{montecalosgd}$得到的$\overline{VE}$ 最小值就是全局最小值，而不需要担心其陷入局部最优

在semi-gradient 算法中使用线性状态估计函数

使用semi-gradient的方法如TD(0)直接代入线性状态值拟合公式可以的到收敛的结果，但是这样的结果是收敛到最优点旁边的次优点，因为同样这有些违背semi-gradient方法中的一般原则，即更新权值$\mathbf{w}$时使用的状态估计值函数中也存在$\mathbf{w}$，因此使用semi-gradient方法会导致偏差。

使用线性拟合状态值估计函数在TD(0)方法中更新$\mathbf{w}$：
$$
\begin{aligned}
\mathbf{w}_{t+1} & \doteq \mathbf{w}t+\alpha\left(R{t+1}+\gamma \mathbf{w}t^{\top} \mathbf{x}{t+1}-\mathbf{w}_t^{\top} \mathbf{x}_t\right) \mathbf{x}t \
&=\mathbf{w}t+\alpha\left(R{t+1} \mathbf{x}t-\mathbf{x}t\left(\mathbf{x}t-\gamma \mathbf{x}{t+1}\right)^{\top} \mathbf{w}t\right)
\end{aligned}
$$
得到$\mathbf{w_t}$对于下一个$\mathbf{w{t+1}}$的期望值可以表示为：
$$
\begin{equation}
\mathbb{E}\left[\mathbf{w}{t+1} \mid \mathbf{w}t\right]=\mathbf{w}t+\alpha\left(\mathbf{b}-\mathbf{A} \mathbf{w}t\right)
\end{equation}
$$
其中：
$$
\begin{equation}
\mathbf{b} \doteq \mathbb{E}\left[R{t+1} \mathbf{x}t\right] \in \mathbb{R}^d
\end{equation}
$$
矩阵$\mathbf{A}$可以写作：
$$
\begin{equation}\label{A}
\mathbf{A} \doteq \mathbb{E}\left[\mathbf{x}t\left(\mathbf{x}t-\gamma \mathbf{x}{t+1}\right)^{\top}\right] \in \mathbb{R}^d \times \mathbb{R}^d
\end{equation}
$$
如果该期望值是收敛的，也就是最终更新达到了稳态，也就是$\mathbf{w{t+1}=w{t}}$ ,则上式有：
$$
\begin{equation}
\begin{aligned}
\mathbf{b}-\mathbf{A} \mathbf{w}{\mathrm{TD}} &=\mathbf{0} \
\mathbf{b} &=\mathbf{A} \mathbf{w}{\mathrm{TD}} \
\mathbf{w}{\mathrm{TD}} &\doteq \mathbf{A}^{-1} \mathbf{b} .
\end{aligned}
\end{equation}
$$
其中$\mathbf{w{TD}}$表示使用TD方法的稳定权值$\mathbf{w}$, 称之为TD固定点，从公式中也可以看出如果想要让使用线性状态值估计函数的TD方法收敛，则必须有$\eqref{A}$中$\mathbf{A^{-1}}$存在，那么如果$\mathbf{A}$ 是正定的矩阵，即$y^{\top} \mathbf{A} y>0$ 对于任意$y$，则$\mathbf{A^{-1}}$必然存在。

矩阵的正定性

如果一个矩阵所有列和相加是非负数，则该矩阵可以证明是positive definite，由以下两个定理证明：

  1. 一个矩阵其对称矩阵是正定的，即$\mathbf{S}=\mathbf{M}+\mathbf{M}^{\top}$是正定的，则该矩阵正定
  2. 任何是矩阵如果其对角线上元素都是正值，且每个对角线元素都大于该行非对角线其他元素之和，则该矩阵是正定的。

对于使用线性状态拟合函数的TD(0)算法的收敛性证明：

首先对于权值更新公式可以重写为：
$$
\begin{equation}
\mathbb{E}\left[\mathbf{w}_{t+1} \mid \mathbf{w}_t\right]=(\mathbf{I}-\alpha \mathbf{A}) \mathbf{w}_t+\alpha \mathbf{b}
\end{equation}
$$
假设$\mathbf{A}$是对角线矩阵，则如果其对角线上任意元素是负值的话，那么 在该位置的值将会大于1（相当于1加上了一个值），那么相应的在$\mathbf{w}$矩阵对应位置上的值在不断迭代的过程中会被放大，永远无法收敛。相反的，如果$\mathbf{A}$对角线元素都是正值的情况下，那么$\mathbf{I-\alpha A}$的结果可以由$\alpha$调整至区间$(0,1)$之间，那么$\mathbf{w}$的更新就能够保证收敛。

使用线性拟合状态值函数的TD(0)收敛性证明

对于TD(0)的更新，当discount factor $\gamma <1$的情况下，公式$\eqref{A}$矩阵$\mathbf{A}$可以写作：
$$
\begin{equation}
\begin{aligned}
\mathbf{A} &=\sum_s \mu(s) \sum_a \pi(a \mid s) \sum_{r, s^{\prime}} p\left(r, s^{\prime} \mid s, a\right) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \
&=\sum_s \mu(s) \sum_{s^{\prime}} p\left(s^{\prime} \mid s\right) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \
&=\sum_s \mu(s) \mathbf{x}(s)\left(\mathbf{x}(s)-\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s\right) \mathbf{x}\left(s^{\prime}\right)\right)^{\top} \
&=\mathbf{X}^{\top} \mathbf{D}(\mathbf{I}-\gamma \mathbf{P}) \mathbf{X}
\end{aligned}
\end{equation}
$$
其中：

$\mu(s)$是在策略$\pi$下的稳态状态分布概率

$p\left(s^{\prime} \mid s\right)$ 是在策略$\pi$下从状态$s$转移到状态$s^{\prime}$的概率

$\mathbf{P}$ 是 $|\mathcal{S}| \times|\mathcal{S}|$ 的概率矩阵

$\mathbf{D}$ 是$|\mathcal{S}| \times|\mathcal{S}|$ 对角矩阵，且 $\mu(s)$ 在其对角线上

$\mathbf{X}$ 是 $|\mathcal{S}| \times d$ 的特征矩阵，且$\mathbf{x}(s)$是其每一行行向量

上式中只需要证明是正定的即可证明$\mathbf{A}$是正定的。

由矩阵的正定性中第二点可知，只要$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$满足两个条件就可以证明其是正定的：

  1. 对角线上元素为正
  2. 对角线元素大于其余元素之和

对于第1点，由于$\mathbf{D}$是对角矩阵，且各对角线元素都为正值，且$(\mathbf{I}-\gamma \mathbf{P})$ 各对角线元素都大于0，其余元素小于0，因此整体$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$对角线上元素都是正值，其余元素都是负值（$-\gamma \mathbf{P}$对角线外相应位置的元素）。

由于$\mathbf{P}$是随机矩阵，所以其行和为1，所以$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$ 行和大于0

一个矩阵$\mathbf{M}$的列和所组成的行向量，可以写成由列向量$\mathbf{1}$的转置和该矩阵的乘积$\mathbf{1}^{\top} \mathbf{M}$（得到一个行向量，每个元素都是$\mathbf{M}$对应列的和），因此求$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$ 的列和可以写成$\mathbf{1}^{\top} \mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$ 的形式。

又因为$\mathbf{D}$是对角矩阵，且 $\mu(s)$ 在其对角线上，所以其列和就是稳态分布$\boldsymbol{\mu}(s)$ ,由于$\mathbf{P}$是状态转移矩阵，在稳态时有：
$$
\begin{equation}
\begin{aligned}
\boldsymbol{\mu}=\mathbf{P}^{\top} \boldsymbol{\mu} \
\boldsymbol{\mu}^{\top}=\boldsymbol{\mu}^{\top}\mathbf{P}
\end{aligned}
\end{equation}
$$
因此可以得到$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$ 的列元素和推导为：
$$
\begin{equation}
\begin{aligned}
\mathbf{1}^{\top} \mathbf{D}(\mathbf{I}-\gamma \mathbf{P}) &=\boldsymbol{\mu}^{\top}(\mathbf{I}-\gamma \mathbf{P}) \
&=\boldsymbol{\mu}^{\top}-\gamma \boldsymbol{\mu}^{\top} \mathbf{P} \
&=\boldsymbol{\mu}^{\top}-\gamma \boldsymbol{\mu}^{\top} \
&=(1-\gamma) \boldsymbol{\mu}^{\top},
\end{aligned}
\end{equation}
$$
取$\gamma<1$ 可以得到列和也为正值。

因此$\mathbf{D}(\mathbf{I}-\gamma \mathbf{P})$ 满足行和列和都是正值的条件，上述正定矩阵的满足第二点要求，所以其为正定矩阵，所以使用线性拟合函数的TD(0)算法可以收敛。

由上述收敛性证明也可以发现，在$\mathbf{w}$稳定时，也就是在$\overline{VE}$最小的时候，和semi-gradient方法的收敛点存在一个$1-\gamma$的系数，即semi-gradient方法的收敛点是TD点，在TD点的误差要比真实全局最优点的误差大，这个系数就是$\frac{1}{1-\gamma}$,注意这里$\gamma<1$，因此$\frac{1}{1-\gamma}>1$：
$$
\begin{equation}
\overline{\mathrm{VE}}\left(\mathbf{w}_{\mathrm{TD}}\right) \leq \frac{1}{1-\gamma} \min {\mathbf{w}} \overline{\mathrm{VE}}(\mathbf{w})
\end{equation}
$$
如果将$\frac{1}{1-\gamma}=c$, 则有
$$
\begin{equation}
\overline{\mathrm{VE}}\left(\mathbf{w}{\mathrm{TD}}\right) \leq c \times \min _{\mathbf{w}} \overline{\mathrm{VE}}(\mathbf{w})
\end{equation}
$$
即使用TD方法求得的稳定点有一个使用最小误差得到的误差上限，其收敛后的误差不会超过这个误差上限，因此其收敛性是较为稳定的，所以采用线性拟合状态值函数的TD方法比较广泛。

算法：

image-20221120140420092