## 0x07 值函数逼近

$V(s) = \hat{V}(s,\theta)\\ Q(s,a) = \hat{Q}(s,a,\theta)\\$

### 线性逼近

$\hat{V}(\boldsymbol{s},\boldsymbol{\theta}) =\boldsymbol{\theta}^T\boldsymbol{x}(s)=\sum_{i=1}^d \theta_i x_i(s)$

#### 增量法逼近

$E_{\theta} = E_{\pi}[(V_{\pi}(s)-\theta^Tx(s))^2]$

$-\frac{\partial E_{\theta}}{\partial \theta}=E_{\pi}[2(V_{\pi}(s)-\theta^Tx(s))x(s)]$

$\nabla \theta = \alpha(V_{\pi}(s)-\theta^Tx(s))x(s)$

• 基于蒙特卡罗方法的参数逼近：

$\nabla \theta = \alpha(G_t-\theta^Tx(s_t))x(s_t)$

• 基于时序差分法的参数逼近：

$\nabla \theta = \alpha(R_{t+1}+\gamma \hat{V}(S_{t+1},\theta)-\hat{V}(S_{t},\theta))\nabla_{\theta}\hat{V}(S_t,\theta) =\alpha(R_{t+1}+\gamma \theta^Tx(s_t)-\theta^Tx(s_{t+1}))x(s_t)$

• 基于前向TD($\lambda$)的参数逼近：

$\nabla \theta = \alpha(G_t^{\lambda}-\hat{V}(S_{t},\theta))\nabla_{\theta}\hat{V}(S_t,\theta) =\alpha(G_t^{\lambda}-\theta^Tx(s_t))x(s_t)$

• 基于后向TD($\lambda$)的参数逼近：

$\delta_t = R_{t+1}+\gamma \theta^Tx(s_{t+1})-\theta^Tx(s_t)\\ E_t=\lambda\gamma E_{t-1}+\nabla_{\theta}\hat{V}(S_t,\theta)=\lambda\gamma E_{t-1}+x(s_t)\\ \nabla \theta = a\delta_tE_t$

• 基于Sarsa的参数逼近：

$\nabla \theta = \alpha(R_{t+1}+\gamma\theta^Tx(s_{t+1},a_{t+1})-\theta^Tx(s_{t},a_{t}))x(s_{t},a_{t})$

• 基于Q-Learning的参数逼近：

$\nabla \theta=\alpha(R_{t+1}+\gamma\theta^Tx(s_{t+1},\pi(s_{t+1}))-\theta^Tx(s_{t},a_{t}))x(s_{t},a_{t})$

#### 批量法逼近

$L(\theta) = \sum_{t=1}^T(V^{\pi}_t-\theta^Tx(s_t))^2$

$\theta$进行求导，使导数为0：

$-\frac{\partial L(\theta)}{\partial \theta}=2\sum_{t=1}^T(V^{\pi}_t-\theta^Tx(s_t))x(s_t)=0$

• 最小二乘蒙特卡罗方法参数为：

$\alpha\sum_{t=1}^T(G_t-\theta^Tx(s_t))x(s_t)=0\\ \theta = (\sum_{t=1}^Tx(s_t)x(s_t)^T)^{-1}\sum_{t=1}^Tx(s_t)G_t$

• 最小二乘时序差分方法：

$\alpha\sum_{t=1}^T(R_{t+1}+\gamma \theta^Tx(s_{t+1})-\theta^Tx(s_t))x(s_t)=0\\ \theta = (\sum_{t=1}^Tx(s_t)(x(s_t)-\gamma x(s_{t+1}))^T)^{-1}\sum_{t=1}^Tx(s_t)R_{t+1}$

• 最小二乘前向TD($\lambda$)方法：

$\alpha\sum_{t=1}^T(G^{\lambda}_t-\theta^Tx(s_t))x(s_t)=0\\ \theta = (\sum_{t=1}^Tx(s_t)x(s_t)^T)^{-1}\sum_{t=1}^Tx(s_t)G^{\lambda}_t$

• 最小二乘后向TD($\lambda$)方法：

$\alpha\delta_t E_t = 0\\ \theta = (\sum_{t=1}^TE_t(x(s_t)-\gamma x(s_{t+1}))^T)^{-1}\sum_{t=1}^TE_tR_{t+1}$

• 最小二乘Sarsa方法（基于Q函数）：

$\alpha\sum_{t=1}^T(R_{t+1}+\gamma \theta^Tx(s_{t+1},a_{t+1})-\theta^Tx(s_t,a_t))x(s_t,a_t)=0\\ \theta = (\sum_{t=1}^Tx(s_t,a_t)(x(s_t,a_t)-\gamma x(s_{t+1},a_{t+1}))^T)^{-1}\sum_{t=1}^Tx(s_t,a_t)R_{t+1}$

• 最小二乘Q-learning方法（基于Q函数）：

$\alpha\sum_{t=1}^T(R_{t+1}+\gamma \theta^Tx(s_{t+1},\pi(s_{t+1}))-\theta^Tx(s_t,a_t))x(s_t,a_t)=0\\ \theta = (\sum_{t=1}^Tx(s_t,a_t)(x(s_t,a_t)-\gamma x(s_{t+1},\pi(s_{t+1}))^T)^{-1}\sum_{t=1}^Tx(s_t,a_t)R_{t+1}$

### 非线性逼近

#### DQN方法

• 与Q-learning思想一致，可以理解成Q-Learning的深度学习版

• 使用深度神经网络提取特征，近似行为值函数(Q函数)

• 利用经验回放进行训练

• 设置两套网络：TD目标网络、动作值函数逼近网络

使用梯度更新方式如下：

$\theta_{t+1} = \theta_t + \alpha(r+\gamma \mathop{max}_{a'}Q(s',a;\theta_t)-Q(s,a;\theta_t)) \nabla Q(s,a;\theta_t)$

这样就导致行为值Q与目标值用得是同一个网络，这样就存在很大的关联性。因此引入一个目标网络，目标值网络需要由动作值函数网络周期性更新：

$\theta_{t+1} = \theta_t + \alpha(r+\gamma \mathop{max}_{a'}Q(s',a';\theta_t^-)-Q(s,a;\theta_t)) \nabla Q(s,a;\theta_t)$

PS:此时可以理解成，对参数的更新就是对网络的更新

Target网络的更新方式：

• 直接赋值：$\theta^-=\theta$
• 逐渐更新：$\theta^-=(1-\tau)\theta^-+\tau \theta$

#### Double DQN方法

$a^* = \mathop{argmax}_{a}Q(s_{t+1},a;\theta^-_t)\\ Y^{DQN}_t = R_{t+1} + \gamma \mathop{max}_{a}Q(s_{t+1},a;\theta^-_t)$

Double DQN(DDQN) 分别采用不同的值函数来实现动作选择和评估

$Y^{DDQN}_t = R_{t+1} + \gamma Q(s_{t+1},\mathop{argmax}_{a}Q(s_{t+1},a;\theta_t);\theta^-_t)$

#### Dueling DQN方法

$Q(s,a) = V(s) + A(s,a)$

• Dueling DQN的思路：

把Q网络(求取Q值的神经网络)的结构显式地约束成两部分之和：更动作无关的状态值函数$V(s)$，与在该状态下各个动作的优势函数$A(s,a)$

• Dueling DQN结构图：

• 网络参数，$\theta$为卷积网络参数，$\alpha,\beta$分别为全连接层网络参数：

$Q(s,a;\theta,\alpha,\beta) = V(s;\theta,\beta) + A(s,a;\theta,\alpha)$

• New Problem：

上述等式中，存在两个未知数，这样就会出现一个无法识别的问题：给定一个Q,无法得到唯一的V和A (比如V和A同时加/减 相同的量)，于是就有如下改进：

$Q(s,a;\theta,\alpha,\beta) = V(s;\theta,\beta) + (A(s,a;\theta,\alpha) - \mathop{max}_{a'} A(s,a';\theta,\alpha))$

上述等式就能唯一确定V和A，但是实际使用中，更倾向于下面的等式：

$Q(s,a;\theta,\alpha,\beta) = V(s;\theta,\beta) + (A(s,a;\theta,\alpha) - \frac{1}{|A|}\sum_{a'} A(s,a';\theta,\alpha))$

这样缩小了Q的范围，去除多余的自由度，提高算法的稳定性！