深度强化学习笔记

暂时完结

蒙特卡洛

近似期望

1. 离散型

$$E(f(X)) = \sum_{i=1}^{n} f(x_i) p_i$$

2. 连续型

$$E(f(X)) = \int f(x)·p(x) dx$$

用如下方式减少内存开销：
初始化$q_{0}=0$，从$t=1$开始，依次更新$q_t$：

$$q_t = (1 - 1/t)·q_{t-1} + 1/t·f(x_t)$$

把$1/t$替换为$\alpha_t$，则有：

$$q_t = (1 - α_t)·q_{t-1} + α_t·f(x_t)$$

该式称为Robbinson-Monro算法，其中$\alpha_n$为学习率

随机梯度下降

随机梯度下降（Stochastic Gradient Descent, SGD）是一种常用的优化算法，用于最小化目标函数。我们可以用蒙特卡洛方法的思想来理解随机梯度下降。
神经网络的训练可以定义为这样的优化问题：

$$\min_{w} \mathbb{E}_{X \sim p(·)}[L(X;w)]$$

其中，$w$是神经网络的参数，$p(·)$是输入数据的分布，$L$是损失函数。
目标函数的梯度\mathbb{E}_{X \sim p(·)}[L(X;w)]关于参数$w$的梯度可以表示为：

$$g \triangleq \nabla_w \mathbb{E}_{X \sim p(·)}[L(X;w)] = \mathbb{E}_{X \sim p(·)}[\nabla_w L(X;w)]$$

可以做梯度下降更新w，以减小目标函数的值：

$$w \leftarrow w - \alpha g$$

其中，$\alpha$是学习率。直接计算全部样本的梯度g的期望会非常耗时，因此做蒙特卡洛方法近似，把得到的近似梯度$\hat{g}$作为w的更新量。

1. 根据p(x)随机采样得到B个样本，记作$\hat{x}_1, \hat{x}_2, \ldots, \hat{x}_B$
2. 计算每个样本的梯度$\hat{g}_i = \nabla_w L(\hat{x}_i;w)$
3. 计算B个样本的梯度的平均值$\hat{g} = \frac{1}{B} \sum_{i=1}^B \hat{g}_i$
4. 更新w：$w \leftarrow w - \alpha \hat{g}$
   样本数量B称作batch size（批大小），通常是比较小的正整数，比如1、8、16、32等。所以称之为小批量SGD。
   在实际应用中，p(x)一般未知，训练神经网络时通常收集一个训练集$\mathcal{X} = {x_1, x_2, \ldots, x_n}$，并求解下面这样一个经验风险最小化问题：

$$\min_{w} \frac{1}{n} \sum_{i=1}^n L(x_i;w)$$

这相当于用下面这个概率密度函数来代替 $p(x)$：

$$p(x) = \begin{cases} \frac{1}{n} & \text{if } x \in \mathcal{X} \\ 0 & \text{otherwise} \end{cases}$$

强化学习基本概念

回合episode和epoch的区别

• episode
  回合指示一个完整的交互过程，包括一系列的状态、动作和奖励。一个回合可以包含多个交互步骤，直到达到终止状态或达到最大步数。就是打完一把游戏。
• epoch
  一个epoch表示在整个训练数据集上进行一次完整的前向传播和反向传播过程。一个epoch通常包含多个回合，每个回合都包含多个交互步骤。

回报return

return是从当前时刻开始，到回合结束的所有奖励之和，也叫为累计奖励。
强化学习的目标是最大化回报，而不是最大化当前奖励。

折扣率$\gamma$

使用折扣率小于1，无限期MDP的回报是有界的。

动作价值函数$Q_{\pi}(s,a)$

动作价值函数是指在给定状态$s$和动作$a$的情况下，根据策略$\pi$，未来可能获得的累计奖励的期望值。

$$Q_{\pi}(s,a) = \mathbb{E}_{\pi}[R_{t+1} + \gamma R_{t+2} + \cdots | S_t = s, A_t = a]$$

最优动作价值函数$Q^*(s_t,a_t)$

最优动作价值函数是指在给定状态$s_t$和动作$a_t$的情况下，在最优策略下未来可能获得的累计奖励的期望值。

$$Q^*(s_t,a_t) = \max_{a} Q_{\pi}(s_t,a)$$

意思就是有多种策略$\pi$可以选择，选择最优策略$\pi^*$，在最优策略$\pi^*$下未来可能获得的累计奖励的期望值。

状态价值函数$V_{\pi}(s)$

状态价值函数是指根据策略$\pi$,在给定状态$s$的情况下，未来可能获得的累计奖励的期望值。

$$V_{\pi}(s_t) = \mathbb{E}_{\pi}[Q_{\pi}(s_t,a_t) | S_t = s_t] = \sum_{a \in \mathcal{A}} \pi(a|s_t) Q_{\pi}(s_t,a)$$

只依赖于状态$s_t$，不依赖于动作$a_t$。也是回报的期望值。

DQN与Q-Learning

用$Q^*$最优动作价值函数使用最大化消除策略$\pi$。
可以这样理解$Q^*$：已知状态$s_t$和动作$a_t$，不论未来采取什么样的策略$\pi$，回报的期望不可能超过$Q^*$。
所以要训练一个近似的$Q^*$。

深度Q网络（Deep Q Network, DQN）

记作Q(s,a;w)，其结构如下：

1. 输入：状态$s$
2. 卷积层：提取特征
3. 全连接层：映射到动作空间
4. 输出：离散动作空间$\mathcal{A}$上的每个动作$a$的Q值，即输出是一个$\mathcal{A}$维的向量

DQN的梯度：

$$\nabla_w Q(s,a;w) \triangleq \frac{\partial Q(s,a;w)}{\partial w}$$

TD算法

训练DQN最常用的算法是TD（Temporal Difference, 时序差分）算法。
损失函数：

$$L(w) = \frac{1}{2}[Q(s,a;w) - y]^2$$

梯度：

$$\nabla_w L(w) = \nabla_w \frac{1}{2} [Q(s,a;w) - y]^2 = (\hat{q} - y)·\nabla_w Q(s,a;w)$$

然后梯度下降更新w。
TD算法就是把预测到中途的数据也利用上。
把到中途的q记作r（训练时是一个状态上的奖励），中途之后的路程$\hat{q}$，则TD目标为$\hat{y} \triangleq r + \hat{q}$，新的梯度为：

$$\nabla_w L(w) = (\hat{q} - \hat{y})·\nabla_w Q(s,a;w)$$

$\delta = \hat{q} - \hat{y}$ 称为TD误差。做一次梯度下降更新w：

$$w \leftarrow w - \alpha \nabla_w L(w) = w - \alpha (\hat{q} - \hat{y})·\nabla_w Q(s,a;w) = w - \alpha · \delta ·\nabla_w Q(s,a;w)$$

TD误差$\delta$就是模型的估计与真实值之间的差距。

用TD算法训练DQN

近似可得：

$$Q^*(s_t,a_t) \approx r_t + \gamma · \max_{a \in \mathcal{A}}Q^*(s_{t+1},a)$$

把上式中的$Q^*(·)$替换为神经网络$Q(s,a;w)$，则有：

$$Q(s,a;w) \approx r_t + \gamma · \max_{a \in \mathcal{A}}Q(s_{t+1},a;w)$$

做梯度下降：

$$w \leftarrow w - \alpha · \delta_{t} ·\nabla_w Q(s_t,a_t;w)$$

训练流程

收集训练数据
用任意策略$\pi$与环境交互，收集训练数据，此时称为行为策略$\pi$。比较常用的是$\epsilon$-贪婪策略。

$$a_t = \begin{cases} argmax_{a} Q(s_t,a;w) & \text{with probability } 1 - \epsilon \\ \mathcal{A} 中的随机动作 & \text{with probability } \epsilon \end{cases}$$

把一个回合的数据称为一个轨迹，记作：

$$\mathcal{T} = \{s_1,a_1,r_1,s_2,a_2,r_2,\cdots,s_T,a_T,r_T\}$$

把一条轨迹分为n个$(s_t,a_t,r_t,s_{t+1})$这样的四元组，存入缓存，这个缓存称为回放缓冲区。

更新参数w
从经验回放缓冲区中随机采样一个小批量的四元组$(s_t,a_t,r_t,s_{t+1})$，当前参数$w_{now}$，执行以下步骤对参数做一次更新，得到新参数$w_{new}$：

1. 对DQN做正向传播，得到Q值：

$$\hat{q}_j = Q(s_j,a_j;w_{now})$$

$$\hat{q}_{j+1} = \max_{a \in \mathcal{A}} Q(s_{j+1},a;w_{now})$$

2. 计算TD目标和TD误差：

$$\hat{y}_j = r_j + \gamma · \hat{q}_{j+1}$$

$$\delta_j = \hat{q}_j - \hat{y}_j$$

3. 对DQN进行反向传播，计算梯度：

$$g_j = \nabla_w Q(s_j,a_j;w_{now})$$

4. 梯度下降更新参数：

$$w_{new} = w_{now} - \alpha · \delta_j · g_j$$

收集数据和更新参数可以同时进行。

Q-Learning

TD目标

$$\hat{y}_j = r_j + \gamma · \max_{a \in \mathcal{A}} \overset{\sim}{Q}(s_{j+1},a)$$

更新表格$\overset{\sim}{Q}$中$(s_t,a_t)$位置上的元素：

$$\overset{\sim}{Q}(s_t,a_t) \leftarrow \overset{\sim}{Q}(s_t,a_t) + \alpha · (\hat{y}_j - \overset{\sim}{Q}(s_t,a_t))$$

训练流程

收集训练数据
与DQN一致
经验回放更新表格$\overset{\sim}{Q}$
随机从经验回放缓冲区中采样一个小批量的四元组$(s_j,a_j,r_j,s_{j+1})$，记作$Q_{now}$，执行以下步骤对表格$\overset{\sim}{Q}$做一次更新：

1. 把$Q_{now}$中$(s_j,a_j)$位置上的元素记作$q_j$:

$$q_j = \overset{\sim}{Q}(s_j,a_j)$$

2. 把第$s_{j+1}$行的最大Q值记作$\hat{q}_{j+1}$：

$$\hat{q}_{j+1} = \max_{a \in \mathcal{A}} \overset{\sim}{Q}_{now}(s_{j+1},a)$$

3. 计算TD目标和TD误差：

$$\hat{y}_j = r_j + \gamma · \hat{q}_{j+1}$$

$$\delta_j = \hat{q}_j - \hat{y}_j$$

4. 更新表格$\overset{\sim}{Q}$中$(s_j,a_j)$位置上的元素：

$$\overset{\sim}{Q}_{new}(s_j,a_j) \leftarrow \overset{\sim}{Q}_{now}(s_j,a_j) - \alpha · \delta_j$$

同策略与异策略

同策略（on-policy）
收集经验的行为策略和更新参数的策略是同一个策略。

异策略（off-policy）
收集经验的行为策略和更新参数的策略是不同的策略。
经验。经验回放只适用于异策略。DQN与Q-Learning都是异策略。

SARSA算法

表格形式的SARSA

学习动作价值函数$Q_{\pi}(s,a)$
TD目标：

$$\hat{y}_j \triangleq r_j + \gamma · q (s_{j+1},\overset{\sim}{a}_{j+1})$$

更新表格$s$中的$(s_t,a_t)$位置上的元素：

$$q(s_t,a_t) \leftarrow q(s_t,a_t) + \alpha · (\hat{y}_t - q(s_t,a_t))$$

训练流程
设当前表格$q$，当前策略为${\pi}_{now}$,每一轮更新表格中的一个元素，把更新之后的表格记为$q_{new}$，执行以下步骤：

1. 观测到当前状态$s_t$，根据当前策略做抽样：

$$a_t \sim \pi_{now}(·|s_t)$$

2. 把$q_{now}$中$(s_t,a_t)$位置上的元素记作：

$$\hat{q}_t = q_{now}(s_t,a_t)$$

3. 执行动作$a_t$，得到奖励$r_t$和下一个状态$s_{t+1}$
4. 根据当前策略做抽样：$\overset{\sim}{a}_{t+1} \sim \pi_{now}(·|s_{t+1})$，$\overset{\sim}{a}_{t+1}$并不执行，是假想的动作。
5. 把$q_{now}$中$(s_{t+1},\overset{\sim}{a}_{t+1})$位置上的元素记作：

$$\hat{q}_{t+1} = q_{now}(s_{t+1},\overset{\sim}{a}_{t+1})$$

6. 计算TD目标和TD误差：

$$\hat{y}_t = r_t + \gamma · \hat{q}_{t+1}$$

$$\delta_t = \hat{q}_t - \hat{y}_t$$

7. 更新表格$q_{new}$中$(s_t,a_t)$位置上的元素：

$$q_{new}(s_t,a_t) \leftarrow q_{now}(s_t,a_t) - \alpha · \delta_t$$

8. 用某种算法更新策略$\pi_{new}$。该算法与SARSA算法无关。

SARSA算法是同策略的，近似$Q_{\pi}$。
Q学习算法是异策略的，近似$Q^*$。

神经网络形式的SARSA

用神经网络$q(s,a;w)$来近似$Q_{\pi}(s,a)$，也称为价值网络，首先随机初始化w，然后用SARSA算法更新w。

梯度下降

$$w \leftarrow w - \alpha · \delta_t · \nabla_w q(s_t,a_t;w)$$

训练流程

1. 观测到当前状态$s_t$，根据当前策略做抽样：

$$a_t \sim \pi_{now}(·|s_t)$$

2. 用神经网络$q(s_t,a_t;w)$做正向传播，得到Q值：

$$\hat{q}_t = q(s_t,a_t;w_{now})$$

3. 执行动作$a_t$，得到奖励$r_t$和下一个状态$s_{t+1}$
4. 根据当前策略做抽样：$\overset{\sim}{a}_{t+1} \sim \pi_{now}(·|s_{t+1})$，$\overset{\sim}{a}_{t+1}$并不执行，是假想的动作。
5. 用神经网络$q(s_{t+1},\overset{\sim}{a}_{t+1};w)$做正向传播，得到Q值：

$$\hat{q}_{t+1} = q(s_{t+1},\overset{\sim}{a}_{t+1};w)$$

6. 计算TD目标和TD误差：

$$\hat{y}_t = r_t + \gamma · \hat{q}_{t+1}$$

$$\delta_t = \hat{q}_t - \hat{y}_t$$

7. 用神经网络$q(s_t,a_t;w)$做反向传播，计算梯度：

$$g_t = \nabla_w q(s_t,a_t;w)$$

8. 梯度下降更新参数：

$$w_{new} = w_{now} - \alpha · \delta_t · g_t$$

9. 用某种算法更新策略$\pi_{new}$。该算法与SARSA算法无关。

多步TD目标

m步TD目标（到中途前走了m步）：

$$\hat{y}_t \triangleq \sum_{k=0}^{m-1} \gamma^k r_{t+k} + \gamma^m · \hat{q}_{t+m}$$

训练流程
需要注意的是更新价值网络参数（$(n-m)$表示回到中途需要这么多步）：

$$w \leftarrow w - \alpha · \sum_{k=0}^{n-m} \gamma^k \delta_t · g_t$$

蒙特卡洛方法与自举

蒙特卡洛方法
用实际观测值近似期望。
好处：无偏性。
坏处：方差大。

自举（bootstraping）
TD目标。
好处：方差小，收敛快。
坏处：有偏差，会让偏差从$(s_{t+1},a_{t+1})$传播到$(s_t,a_t)$。

价值学习高级技巧

经验回放

把智能体与环境交互的记录（即经验）存储在经验回放缓存中。实践中要等待经验回放缓存中有足够多的四元组才开始做经验回放更新DQN。

经验回放的优点

1. 收集经验时相邻两个四元组有很强的相关性，经验回放每次从缓存里随机抽取一个四元组，可以打破相关性，提高训练效率。
2. 重复利用收集到的经验，可以用更少的样本数量达到同样的效果。

局限性
不适用于on-policy算法。

优先经验回放
优先经验回放是指在经验回放时，根据经验的重要性(TD误差大的)，给经验赋予不同的权重，从而使得重要经验被重复利用的概率更大。做非均匀抽样会导致DQN的预测有偏差。应该根据抽样概率调整学习率：

$$\alpha_j = \alpha · \frac{1}{(b · p_{j})^\beta}$$

b是经验回放缓存中样本的总数，$\beta \in (0,1)$是一个需要调整的超参数。

高估问题及解决方法

Q学习算法训练出来的DQN会高估真实的价值：

1. 自举导致偏差传播。
2. 最大化导致高估。

想要解决高估，要么切断自举，要么避免最大化。

使用目标网络
使用目标网络可以切断自举。
用另一个神经网络，即目标网络来计算TD目标，记作：

$$Q(s,a;w^-)$$

设DQN和目标网络当前的参数分别为$w_{now}$和$w_{now}^-$，执行以下步骤：

1. 对DQN做正向传播，得到:

$$\hat{q}_t = Q(s_t,a_t;w_{now})$$

2. 对目标网络做正向传播，得到：

$$\hat{q}_{t+1}^- = \max_{a \in \mathcal{A}} Q(s_{t+1},a;w_{now}^-)$$

3. 计算TD目标和TD误差：

$$\hat{y}_t = r_t + \gamma · \hat{q}_{t+1}^-$$

$$\delta_t = \hat{q}_t - \hat{y}_t^-$$

4. 对DQN做反向传播，计算梯度：

$$g_t = \nabla_w Q(s_t,a_t;w_{now})$$

5. 梯度下降更新参数：

$$w_{new} = w_{now} - \alpha · \delta_t · g_t$$

6. 设$\tau \in (0,1)$是需要手动调节的超参数，做加权平均：

$$w_{neew}^- \leftarrow \tau · w_{new} + (1-\tau) · w_{now}^-$$

这种方法只是减轻自举，不能完全避免自举。

使用双Q网络
使用双Q网络可以避免最大化。
双Q学习算法，也就是double DQN，缩写DDQN。

训练流程

1. 对DQN做正向传播，得到：

$$\hat{q}_t = Q(s_t,a_t;w_{now})$$

2. 选择：

$$a^* = \argmax_{a \in \mathcal{A}} Q(s_{t+1},a;w_{now})$$

3. 求值：

$$\hat{q}_{t+1} = Q(s_{t+1},a^*;w_{now}^-)$$

4. 计算TD目标和TD误差：

$$\overset{\sim}{y}_t = r_t + \gamma · \hat{q}_{t+1}$$

$$\delta_t = \hat{q}_t - \overset{\sim}{y}_t$$

5. 对DQN做反向传播，计算梯度：

$$g_t = \nabla_w Q(s_t,a_t;w_{now})$$

6. 梯度下降更新参数：

$$w_{new} = w_{now} - \alpha · \delta_t · g_t$$

7. 设$\tau \in (0,1)$是需要手动调节的超参数，做加权平均：

$$w_{new}^- \leftarrow \tau · w_{new} + (1-\tau) · w_{now}^-$$

对决网络（dueling network）

最优优势函数
定义：

$$D^*(s,a) \triangleq Q^*(s,a) - V^*(s)$$

回顾：$Q^*(s,a) = \max\limits_{\pi}Q_{\pi}(s,a)$，最优价值函数是给定一个状态和动作后，选择最优的策略得到的Q值。

定理：

$$Q^*(s,a) = V^*(s) + D^*(s,a) - \max\limits_{a}D^*(s,a)$$

其中，

$$\max\limits_{a}D^*(s,a) \equiv 0$$

dueling network结构

$$Q(s,a;w) \triangleq V(s;w^V) + D(s,a;w^D) - \max\limits_{a}D(s,a;w^D)$$

解决不唯一性
V变大100，D变小100，不唯一，参数不稳定。加入$\max{D}$，解决不唯一性。

训练流程

1. 用$\epsilon$-greedy算法控制智能体，收集经验。四元组存入经验回放缓存
2. 用双Q学习算法更新参数
3. 完成训练后，基于当前状态用对决网络给所有动作打分，选择得分最高的动作。

噪声网络

可以用于几乎所有RL方法。

噪声网络的原理
把神经网络的参数w替换成：$\mu + \sigma \circ \xi$。其中，$\mu$和$\sigma$分别表示均值和标准差，是参数，需要从经验中学习。$\xi$是随机噪声，它的每个元素独立从正态分布$\mathcal{N}(0,1)$中采样。符号：$\circ$表示逐元素相乘。即：

$$w_i = \mu_i + \sigma_i · \xi_i$$

噪声DQN

$$\overset{\sim}{Q}(s,a,\xi;\mu,\sigma) = Q(s,a;\mu + \sigma \circ \xi)$$

噪声DQN参数量比标准DQN多一倍，因为$\mu$和$\sigma$需要从经验中学习。

1. 收集经验
   噪声DQN本身就具有随机性，因此不用$\epsilon$-greedy算法。直接用：

$$a_t = \argmax\limits_{a \in \mathcal{A}} \overset{\sim}{Q}(s,a,\xi;\mu,\sigma)$$

2. Q-learning
   TD目标：$\hat{y}_t = r_t + \gamma · \max\limits_{a \in \mathcal{A}} \overset{\sim}{Q}(s_{t+1},a,\xi^{'};\mu,\sigma)$
   损失函数:$L(\mu,\sigma) = \frac{1}{2} [\overset{\sim}{Q}(s_t,a_t,\xi;\mu,\sigma) - \hat{y}_t]^2$
   这里的$\xi^{'}$和$\xi$是不同的。梯度下降更新$\mu$和$\sigma$。
3. 做决策
   做决策不需要噪声。把$\sigma$置0即可。

噪声迫使DQN容忍对参数的扰动，训练出来DQN具有健壮性。

训练流程
用到双Q学习、优先经验回放。
开始随机初始化$\mu$和$\sigma$，收集经验，赋值给目标网络参数：$\mu^- \leftarrow \mu$、$\sigma^- \leftarrow \sigma$。然后重复以下步骤更新参数：

1. 优先经验回放，从经验回放缓存中采样一个小批量的四元组$(s_j,a_j,r_j,s_{j+1})$
2. 用标准正态分布生成噪声$\xi$，对噪声DQN做正向传播，得到：

$$\hat{q}_j = \overset{\sim}{Q}(s_j,a_j,\xi;\mu_{now},\sigma_{now})$$

3. 用噪声DQN选出最优动作：

$$a^*_{j+1} = \argmax\limits_{a \in \mathcal{A}} \overset{\sim}{Q}(s_{j+1},a,\xi;\mu_{now},\sigma_{now})$$

4. 用标准正态分布生成噪声$\xi^{'}$，对目标网络做正向传播，得到：

$$\hat{q}_{j+1}^- = \overset{\sim}{Q}(s_{j+1},a^*_{j+1},\xi^{'};\mu_{now}^-,\sigma_{now}^-)$$

5. 计算TD目标和TD误差：

$$\hat{y}_j^- = r_j + \gamma · \hat{q}_{j+1}^-$$

$$\delta_j = \hat{q}_j - \hat{y}_j^-$$

6. 对噪声DQN做反向传播，梯度下降更新参数：

$$\mu_{new} \leftarrow \mu_{now} - \alpha_\mu · \delta_j · \nabla_{\mu} \overset{\sim}{Q}(s_j,a_j,\xi;\mu_{now},\sigma_{now})$$

$$\sigma_{new} \leftarrow \sigma_{now} - \alpha_\sigma · \delta_j · \nabla_{\sigma} \overset{\sim}{Q}(s_j,a_j,\xi;\mu_{now},\sigma_{now})$$

7. 设$\tau \in (0,1)$是需要手动调整的超参数，做加权平均更新目标网络参数：

$$\mu_{new}^- \leftarrow \tau · \mu_{new} + (1-\tau) · \mu_{now}^-$$

$$\sigma_{new}^- \leftarrow \tau · \sigma_{new} + (1-\tau) · \sigma_{now}^-$$

Rainbow DQN
优先经验回放，双Q学习，噪声网络，dueling network，噪声网络，多步TD目标，distributional learning。

策略梯度方法

本章假设动作空间是离散的。用神经网络$\pi(a|s;\theta)$近似策略函数$\pi(a|s)$，称为策略网络。结构为：

1. 输入：状态$s$
2. 卷积神经网络
3. 全连接层
4. softmax激活函数

策略学习的目标函数

回报$U_t$是从t时刻开始的所有奖励之和，依赖于t时刻开始的所有状态和动作，它的不确定性来自于未来未知的状态和动作。动作价值函数是确定当前t时刻状态和动作的回报的期望。
状态价值函数既依赖于当前状态$s_t$，也依赖于策略网络$\pi$的参数$\theta$。

当前状态$s_t$越好，则状态价值函数$V_{\pi}(s_t)$越大。
策略网络$\pi$越好，则状态价值函数$V_{\pi}(s_t)$越大。
如果一个策略很好，那么状态价值$V_{\pi}(S)$的均值应当很大。因此定义目标函数：

$$J(\theta) = \mathbb{E}_{\pi} [V_{\pi}(S)]$$

这个目标函数排除了状态S的因素，只依赖于参数$\theta$，策略越好，$J(\theta)$。所以策略学习可以描述成这样一个优化问题：

$$\max_{\theta} J(\theta)$$

要求解最大化问题，用梯度上升更新参数$\theta$：

$$\theta_{new} \leftarrow \theta_{now} + \beta · \nabla_\theta J(\theta_{now})$$

其中，$\beta$是学习率。梯度$\nabla_\theta J(\theta) \triangleq \frac{\partial J(\theta)}{\partial \theta}$称为策略梯度（policy gradient）。

策略梯度定理

$$\frac{\partial J(\theta)}{\partial \theta} = \mathbb{E}_S[\mathbb{E}_{A \sim \pi(A|S;\theta)} [\nabla_\theta \ln \pi(A|S;\theta) · Q_{\pi}(S,A)]]$$

近似策略梯度
蒙特卡洛，根据当前策略网络随机抽样得出一个动作：

$$a \sim \pi(·|s;\theta)$$

计算随机梯度：

$$g(s,a;\theta) \triangleq \nabla_\theta \ln \pi(a|s;\theta) · Q_{\pi}(s,a)$$

显然，$g(s,a;\theta)$是策略梯度$\nabla_\theta J(\theta)$的无偏估计：

$$\nabla_\theta J(\theta) = \mathbb{E}_S[\mathbb{E}_{A \sim \pi(·|S;\theta)} [g(S,A;\theta)]]$$

随机梯度上升更新{\theta}:

$$\theta_{new} \leftarrow \theta_{now} + \beta · g(s,a;\theta_{now})$$

REINFORCE

REINFORCE用蒙特卡洛方法近似$Q_\pi$（因为未知），把它替换成回报u。

训练流程

1. 用策略网络$\theta_{now}$得到一条轨迹：

$$\{s_1,a_1,r_1,s_2,a_2,r_2,\cdots,s_n,a_n,r_n\}$$

2. 计算回报：

$$u_t = \sum_{k=t}^n \gamma^{k-t} · r_k$$

3. 用${(s_t,a_t)}_{t=1}^n$作为数据，做反向传播计算：

$$\nabla_\theta \ln \pi(a_t|s_t;\theta_{now})$$

4. 随机梯度上升：

$$\theta_{new} \leftarrow \theta_{now} + \beta · \sum_{t=1}^n \gamma^{t-1}·u_t · \nabla_\theta \ln \pi(a_t|s_t;\theta_{now})$$

actor-critic

随机梯度：

$$g(s,a;\theta) \triangleq \nabla_\theta \ln \pi(a|s;\theta) · Q_{\pi}(s,a)$$

用神经网络近似$Q_\pi$。

价值网络
critic。近似动作价值函数$Q_\pi(s,a)$，记作$q(s,a;w)$。价值网络的训练用的是SARSA算法，属于同策略，不能用经验回放。

算法推导
策略网络$\pi(a|s;\theta)$，actor，基于状态s做出动作a。
价值网络$q(s,a;w)$，critic，基于状态s和动作a给出价值q。

1. 训练actor
   近似策略梯度：$\hat{g}(s,a;\theta) \triangleq \nabla_\theta \ln \pi(a|s;\theta) · q(s,a;w)$
   梯度上升：$\theta_{new} \leftarrow \theta_{now} + \beta · \hat{g}(s,a;\theta_{now})$
   更新参数后，评委critic打出的分数会越来越高。
2. 训练critic
   TD目标：$\hat{y}_t \triangleq r_t + \gamma · q(s_{t+1},a_{t+1};w)$
   TD误差：$\delta \triangleq q(s,a;w) - \hat{y}_t$
   梯度下降：$w_{new} \leftarrow w_{now} - \alpha · \delta · \nabla_w q(s,a;w)$

训练流程

1. 观测到当前状态$s_t$，根据策略网络actor做决策，并执行动作；
2. 观测到奖励和新的状态；
3. 根据策略网络做决策，但不执行$a_{t+1}$;
4. 用TD目标和TD误差更新价值网络critic；
5. 更新actor。

用目标网络改进训练
与上面的区别就是让critic只打分$(s_t,a_t)$，目标网络打分$(s_{t+1},a_{t+1})$，并且最后做加权平均更新目标网络的参数。

带基线的策略梯度方法

基线（baseline）

把b作为动作价值函数$Q_\pi(S,A)$的基线，用$Q_\pi(S,A)-b$替换$Q_\pi$。设b是任意函数，只要不依赖于动作A就可以。

带基线的策略梯度定理
设b是任意函数，但是b不依赖于A。把b作为动作价值函数$Q_\pi(S,A)$的基线，对策略梯度没有影响。

$$\nabla_\theta J(\theta) = \mathbb{E}_S[\mathbb{E}_{A \sim \pi(·|S;\theta)} [(Q_\pi - b) · \nabla_\theta ln \pi(A|S;\theta)]]$$

$b = V_\pi(s)$是很好的基线。

带基线的REINFORCE

训练流程

1. 用策略网络$\theta_{now}$控制智能体从头开始一个回合，得到一条轨迹：
2. 计算所有的回报：

$$u_t = \sum_{k=t}^n \gamma^{k-t} · r_k$$

3. 让价值网络做预测：

$$\hat{v}_t = v(s_t;w_{now})$$

4. 计算误差$\delta_t = \hat{v}_t - u_t$
5. 用$\{s_t\}_{t=1}^n$作为价值网络输入，做反向传播计算：

$$\nabla_w v(s_t;w_{now})$$

6. 更新价值网络参数：

$$w_{new} \leftarrow w_{now} - \alpha · \sum_{t=1}^n \delta_t · \nabla_w v(s_t;w_{now})$$

7. 用$\{(s_t,a_t)\}_{t=1}^n$作为数据，做反向传播计算：

$$\nabla_\theta \ln \pi(a_t|s_t;\theta_{now})$$

8. 随机梯度上升：

$$\theta_{new} \leftarrow \theta_{now} - \beta · \sum_{t=1}^n \gamma^{t-1}·\delta_t · \nabla_\theta \ln \pi(a|s;\theta_{now})$$

advantage actor-critic(A2C)

训练流程

1. 观测到当前状态$s_t$，根据策略网络做决策：$a_t ~ \pi(·|s_t;\theta_{now})$，并让智能体执行动作$a_t$；
2. 从环境中观测到奖励$r_t$和新的状态$s_{t+1}$；
3. 让价值网络打分：$\hat v_t = v(s_t;w_{now})$和$\hat v_{t+1} = v(s_{t+1};w_{now})$
4. 计算误差：$y_t = r_t + \gamma · \hat{v}_{t+1}$和$\delta_t = \hat{v}_t - y_t$
5. 更新价值网络：

$$w_{new} \leftarrow w_{now} - \alpha · \delta_t · \nabla_w v(s_t;w_{now})$$

6. 更新策略网络：

$$\theta_{new} \leftarrow \theta_{now} - \beta · \delta_t · \nabla_\theta \ln \pi(a_t|s_t;\theta_{now})$$

这里训练策略网络和价值网络的方法属于同策略，不能使用经验回放。

用目标网络改进训练
用目标网络给$s_{t+1}$打分。

策略学习高级技巧

置信域策略优化

置信域策略优化（trust region policy optimization，TRPO）是一种策略学习方法，跟策略梯度方法相比，表现更稳定，收敛曲线不会剧烈波动，对学习率不敏感，用更少的经验就能达到相同表现。

置信域方法
优化问题：$max_\theta J(\theta)$
几乎所有的数值优化算法都做了这样的迭代：

$$\theta_{new} \leftarrow Update(Data;\theta_{now})$$

置信域：
构造一个函数$L(\theta|\theta_{now})$，如果这个函数满足条件：$L(\theta|\theta_{now})$很接近$J(\theta)$， $\forall \theta \in N(\theta_{now})$
，则称$\theta$是$\theta_{now}$的置信域。

状态价值可以写成：

$$V_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s;\theta) · Q_\pi(s,a) \\ = \sum_{a \in \mathcal{A}} \pi(a|s;\theta_{now}) · \frac {\pi(a|s;\theta)} {\pi(a|s;\theta_{now})} · Q_\pi(s,a) = \mathbb{E}_{A \sim \pi(·|s;\theta_{now})} [\frac {\pi(a|s;\theta)} {\pi(a|s;\theta_{now})} · Q_\pi(s,A)]$$

目标函数的等价形式

$$J(\theta) = \mathbb{E}_S[\mathbb{E}_{A \sim \pi(·|S;\theta)} [\frac {\pi(A|S;\theta)} {\pi(A|S;\theta_{now})} · Q_\pi(S,A)]]$$

上面$Q_\pi$中的$\pi$指的是$\pi(A|S;\theta)$。

算法推导

1. 第一步——做近似
   用策略网络$\pi(A|S;\theta_{now})$完成一个回合，观测到一条轨迹。
   对$\frac {\pi(a_t|s_t;\theta)} {\pi(a_t|s_t;\theta_{now})} · Q_\pi(s_t,a_t)$求均值：

$$L(\theta|\theta_{now}) = \frac{1}{n} \sum_{t=1}^n \frac {\pi(a_t|s_t;\theta)} {\pi(a_t|s_t;\theta_{now})} · Q_\pi(s_t,a_t)$$

L作为目标函数J的近似。由于不知道动作价值Q，无法直接对L进行最大化，因此做两次近似：

$$Q_\pi(s_t,a_t) \Rightarrow Q_{\pi_{old}}(s_t,a_t) \Rightarrow u_t$$

$L(\theta|\theta_{now})$可以写成：

$$L(\theta|\theta_{now}) = \frac{1}{n} \sum_{t=1}^n \frac {\pi(a_t|s_t;\theta)} {\pi(a_t|s_t;\theta_{now})} · u_t$$

2. 第二步——最大化
   求解这个带约束的最大化问题：

$$\max_{\theta} L(\theta|\theta_{now}) \\ s.t. \quad \theta \in \mathcal{N}(\theta_{now})$$

一种置信域是以$\theta_{now}$为中心的一个半径为$\triangle$的球。另一种使用KL散度衡量$\pi(·|s_i;\theta_{}now)$和$\pi(·|s_i;\theta)$的距离。

策略学习中的熵正则

我们希望策略网络的输出的概率不要集中在一个动作上，至少要让其他动作有一些非零的概率，能被探索到。用熵来衡量概率分布的不确定性。熵大说明随机性很大。

带熵正则的策略梯度
概率分布的熵定义为：

$$H(s;\theta) \triangleq Entropy[\pi(·|s;\theta)] = - \sum_{a \in \mathcal{A}} \pi(a|s;\theta) · \ln \pi(a|s;\theta)$$

目标函数加上熵正则：

$$\max_\theta J(\theta) + \lambda · \mathbb{E}_S[H(S;\theta)]$$

优化

$$g(\theta) \triangleq \nabla_\theta [J(\theta) + \lambda · \nabla_\theta \mathbb{E}_S[H(S;\theta)]]$$

观测到状态s，按照策略网络做随机抽样，得到动作$a \sim \pi(·|s;\theta)$。

$$g(s,a;\theta) \triangleq [Q_\pi(s,a) - \lambda · ln \pi(a|s;\theta) - \lambda] · \nabla_\theta \ln \pi(a|s;\theta)$$

更新参数：

$$\theta_{new} \leftarrow \theta_{now} + \beta · g(s,a;\theta_{now})$$

连续控制

深度确定性策略梯度（deep deterministic policy gradient,DDPG）

深度说明它使用深度神经网络。确定性说明它的输出是确定性的动作。策略梯度说明它用策略梯度学习策略网络。
DDPG属于一种actor-critic方法。基于状态s做出动作a。

策略网络和价值网络
确定性策略网络$\mu(s;\theta)$的输出是d维向量a，作为动作。
结构：卷积神经网络、全连接层。
确定性策略可以看作是随机性策略的一个特例。确定性策略$\mu(s;\theta)$的输出是d维向量。它的第i个元素记作$\hat \mu_i = [\mu(s;\theta)]_i$。定义下面这个而随机性策略：

$$\pi(a|s;\theta,\sigma) = \prod_{i=1}^d \frac 1 {\sqrt{2 \pi}\sigma_i} \exp \left( -\frac {(a_i - \hat \mu_i)^2} {2 \sigma_i^2} \right)$$

这个随机性策略是均值为$\mu(s;\theta)$、协方差矩阵为$diag (\sigma_1,\dots,\sigma_d)$的多元正态分布。本节的确定性策略可以看作上述随机性策略在$\sigma = [\sigma_1,\dots,\sigma_d]$为全零向量时的特例。

价值网络是对动作价值函数$Q_\pi(s,a)$的近似。

算法推导

1. 行为策略收集经验 由于是异策略方法，行为策略可以任意，收集到的经验存入经验回放缓存，训练的时候重复利用。
2. 训练策略网络 价值网络根据当前状态s的打分为$q(s,\mu(s,\theta;w))$。我们希望打分的期望尽量高，所以把目标函数定义为打分的期望：$J(\theta) = \mathbb{E}_S[q(S,\mu(S,\theta;w))]$，关于S求期望消除了S的影响。不管面对什么样的状态S，策略网络都应该做出很好的动作，使得平均分$J(\theta)$尽量高。用梯度上升来增大$J(\theta)$。每次用随机变量S的一个观测值（记作$s_j$）来计算梯度：$g(s_j;\theta) \triangleq \nabla_\theta q(s_j,\mu(s_j;\theta);w) = \nabla_\theta \mu(s_j;\theta) · \nabla_a q(s_j,\hat a_j;w)$
   每次从经验回放缓存里随机抽取一个状态，记作$s_j$，计算$\hat a_j = \mu(s_j;\theta)$。用梯度上升更新一次$theta$：

$$\theta_{new} \leftarrow \theta_{now} + \beta · \nabla_\theta \mu(s_j;\theta) · \nabla_a q(s_j,\hat a_j;w)$$

3. 训练价值网络 价值网络拟合TD目标。每次取出一个四元组$s_j,a_j,r_j,s_{j+1}$，用它更新一次参数w。
   首先让价值网络做预测：$\hat q_j = q(s_j,a_j;w)$和$\hat q_{j+1} = q(s_{j+1},\mu(s_{j+1};\theta);w)$
   然后计算TD目标：$\hat y_j = r_j + \gamma · \hat q_{j+1}$
   定义损失函数：$L(w) = \frac{1}{2} [\hat q_j - \hat y_j]^2$
   计算梯度：$g(w) \triangleq \nabla_w L(w) = (\hat q_j - \hat y_j) · \nabla_w q(s_j,a_j;w)$
   梯度下降更新参数：$w_{new} \leftarrow w_{now} - \alpha · g(w)$

深入分析DDPG

DDPG的高估问题

1. 最大化造成高估 求解下面的优化模型来学习策略网络：
   $\theta^* = \argmax_\theta \mathbb{E}_S[q(S,\hat A;w)], s.t. \hat A = \mu(S;\theta)$
   这个式子的意思是$\mu(s;\theta^*)$是最优的确定性策略网络。
   训练价值网络q时用的TD目标是：
   $\hat y_j = r_j + \gamma · \hat q(s_{j+1},\mu(s_{j+1};\theta);w) \approx r_j + \gamma · \max_{a_{j+1}}q(s_{j+1},a_{j+1};w)$
   max会导致$\hat y_j$高估真实动作价值$Q_\pi(s_j,a_j;w)$ 。
2. 自举造成偏差传播

双延迟深度确定性策略梯度（twin delayed deep deterministic policy gradient，TD3）

高估问题的解决方案——目标网络
使用两个目标网络：$q(s,a;w^-)和\mu(s;\theta^-)$。
TD目标用目标网络计算。可以一定程度上缓解高估，但高估仍然很严重。

高估问题的解决方案——截断双Q学习
clipped double learning，可以更好地解决高估问题。截断双Q学习使用两个价值网络和一个策略网络：$q(s,a;w_1),q(s,a;w_2),\mu(s;\theta)$。
三个神经网络各对应一个目标网络。
用目标策略网络计算动作。用两个目标价值网络计算TD目标，取较小者。

在动作中加噪声 目标策略网络计算动作为：
$\hat a_{j+1}^- = \mu(s_{j+1};\theta^-) + \xi$
其中$\xi$从截断正态分布$\mathcal{CN}(0,\sigma^2,-c,c)$中独立随机抽取。截断正态分布的意思是变量落在区间$[-c,c]$之外的概率是零。防止噪声过大。

降低更新策略网络和目标网络的频率 让策略网络以及三个目标网络更新的频率比价值网络低，每隔k轮更新一次，k是超参数。

随机高斯策略

随机正态分布（也叫高斯分布）。

基本思路
最简单的情形：假设自由度等于1，动作a是实数。用正态分布的概率密度函数作为策略函数。定义两个神经网络：$\mu(s;\theta)和\rho(s;\theta)$，分别用于预测均值和方差对数。实践中不直接近似标准差$\sigma$而是近似方差对数$ln sigma^2$是因为标准差必须非负，会让优化模型有约束条件，给求解造成困难。

1. 观测到当前状态s，计算均值和方差对数：$\hat \mu = \mu(s;\theta)，\hat \rho = \rho(s;\theta)$，以及方差$\hat \sigma^2 = exp(\hat \rho)$;
2. 从正态分布中随机抽样：$a \sim \mathcal{N}(\hat \mu,\hat \sigma^2)$，然后智能体执行动作a。
   $\pi(a|s;\theta) = \frac 1 {\sqrt{2 \pi} \hat \sigma} \exp \left( -\frac {(a - \hat \mu)^2} {2 \hat \sigma^2} \right)$
   实际做控制的时候，只需要神经网络$\mu$和$\rho$，用不到真正的策略网络$\pi(a|s;\theta)$。

随机高斯策略网络
实际中自由度d大于1，那么动作a是d维向量。用标量$a_i$表示动作向量a的第i个元素，用函数$\mu_i(s;\theta)$和$\rho_i(s;\theta)$分别预测$a_i$的均值和方差对数。用特殊的多元正态分布的概率密度函数作为策略网络：
$\pi(a|s;\theta) = \prod_{i=1}^d \frac 1 {\sqrt{2 \pi} \hat \sigma_i} \exp \left( -\frac {(a_i - \hat \mu_i)^2} {2 \hat \sigma_i^2} \right)$
训练的时候不需要用到$\pi(a|s;\theta)$，而是要用辅助网络：
$f(s,a;\theta)$：$f(s,a;\theta) = -\frac {1} 2\sum_{i=1}^d(\rho_i(s;\theta) + \frac {[a_i-\mu_i(s;\theta)]^2} {exp[\rho_i(s;\theta)]})$
辅助网络和策略网络的关系：$f(s,a;\theta) = \ln \pi(a|s;\theta) + 常数$