强化学习
写在前面
-
2023.11.02: 有很多人反映gym代码报错，这是因为Gym新版本调用env.step(),env.reset()返回的值多了一个东西，详情请见这个issue,解决方法是修改代码，或者按照我提供的requirements.txt安装环境。
-
Note that the algorithm code comes from some experts in the field of reinforcement learning or I refactored the algorithms myself.
-
本仓库中的强化学习算法来自于Medium、YouTube、CSDN等等网站，详细的信息请见该readme下面的“参考资料”这一小节，或许会对您有些帮助。
-
此外，TRPO我似乎没有搞懂，代码并没有调试，请不要运行TRPO的代码。
-
有些公式无法显示不知道为什么，git clone 到本地使用VSCODE或者别的Markdown渲染软件能够完整显示，代码基本上都经过运行调试并能够生成tensorboard记录.
-
如果遇到bug，请给我提issue，O(∩_∩)O。
-
最近在搞MARL，后期会添加一些MARL的算法。
进度
where the * mark means the algorithm is important and worth diving into it
| method |
done |
| *Qlearning |
√ |
| Sarsa |
√ |
| SarsaLambda |
√ |
| *DQN |
√ |
| *DQNwithPER |
√ |
| DuelingDQN |
√ |
| *Policy Gradient |
√ |
| *AC and A2C |
√ |
| ACER |
√ |
| A3C |
√ |
| *SAC (PER optional) |
√ |
| *DDPG |
√ |
| TD3 (PER,HER optional) |
√ |
| *TRPO |
√ |
| *PPO |
√ |
| DPPO |
√ |
| Multi-Agent DDPG |
√ |
| TEMPPO |
× |
术语表
仿造这个博客也造了个术语表,这些术语都会在下面看到。
| 符号 |
意义 |
| $s \in \mathcal{S}$ |
状态 |
| $a \in \mathcal{A}$ |
动作 |
| $r \in \mathcal{R}$ |
奖励 |
| $S_t,A_t,R_t$ |
一个轨迹中时间$t$时候的状态、动作和奖励，其中大写的是随机变量，小写的是观测值 |
| $U_t$ |
被称为Return或者是未来的折扣奖励(discounted rewards),有的文章也叫 $G_t$ ，总之意义一样，$U_t=\gamma^0 R_t+\gamma^1R_{t+1}+\gamma^2R_{t+2}+…$，其中 $\gamma$ 为discount factor折扣因子 |
| $P(s’,r\vert s,a)$ |
从当前状态 $s$ 采取动作 $a$，转移到 $s_{t+1}$ 状态并获取奖励$r$的概率 |
| $\pi(a\vert s)$ |
随机策略,$\pi(a \vert s; \theta)$ 表示由 $\theta$ 作为参数初始化的策略网络 |
| $\mu(s)$ |
确定性的策略，在DDPG中可以见到，也可以表示为$\pi(s)$，一般用前者 |
| $V(s)$ |
状态价值函数，它预测状态$s$下的期望折扣奖励，其中$V(s;\mathbf{w})$是由参数$\mathbf{w}$初始化的价值网络 |
| $V_\pi(s)$ |
当我们遵循策略$\pi$的时候，状态$s$的价值，其中$ V_\pi(s) = \mathbb{E}_{a \sim \pi(\cdot \vert s)} [U_t \vert S_t =s]$ |
| $Q(s,a)$ |
在状态$s$时采取动作$a$的时候能够的到的期望折扣奖励(return)，其中$Q(s,a;\mathbf{w})$代表以参数$\mathbf{w}$初始化的动作价值函数 |
| $Q_\pi(s,a)$ |
遵循策略$\pi$的时候，在状态$s$时采取动作$a$的时候能够的到的期望折扣奖励(return)，$Q(s,a;\mathbf{w}) = \mathbb{E}_{a \sim \pi(\cdot \vert s)} [U_t \vert S_t =s,A_t=a]$ |
| $A(s,a)$ |
优势函数(advantage)，$A(s,a) = Q(s,a) - V(s)$ 它是另外一种Q-value，加入 $V(s)$ 作为baseline，具有更低的方差 |
| $r(\pi)$ |
根据策略$\pi$选取动作，能够得到的平均回报 |
| $d^\pi(s)$ |
策略$\pi$所决定的马尔科夫链的平稳分布 |
1. 关键概念 Key Concepts
-
代理(agent)在一个环境(environment)中执行动作/行为(action)。环境如何对代理的动作做出响应由一个已知或未知的模型(model)来定义。执行代理可以停留在环境中的某个状态(state) $s\in \mathcal{S}$，可以通过执行某个行为/动作(action) $a\in \mathcal{A}$来从一个状态$s$进入到另一个状态$s’$。代理会到达什么状态由状态转移概率$(P)$决定。代理执行了一个动作之后，环境会给出一定的奖励(reward) $r\in\mathcal{R}$作为反馈。
-
几乎所有的强化学习问题可以使用马尔科夫决策过程（MDPs）来描述，MDP 中的所有状态都具有“马尔科夫性”：未来仅仅依赖于当前的状态，并不与历史状态相关，在给定当前状态下，未来与过去条件独立，也就是当前状态包含了决定未来所需的所有信息。
-
策略：即智能体 agent 的行为函数 $\pi$，是当前状态到一个动作的映射，它可以是随机性的(random)也可以是确定性的(deterministic)：
- $\pi(s)=a$
- $\pi(a \mid s)= \mathbb{P}_{\pi}(A=a \mid S=s)$
-
动作-价值函数(Action-value Function) $Q(s,a)$：动作-价值函数是衡量一个状态或者是一个(状态，行为)元组的好坏，它是 $U_t$ 的期望:$Q_{\pi}(s_t,a_t) = \mathbb{E}[U_t\vert S_t = s_t, A_t = a_t]$；未来的奖励（称为回报）定义为带衰减的后续奖励之和(discounted rewards)
-
$$ U_t = R_{t+1} + \gamma R_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$
在下面第六节中会详细讲到
-
$\gamma$ 作为对未来奖励的惩罚(penaty)，因为：
- 未来奖励的不确定性
- 未来奖励不会直接提供收益
- 数学上便利，无需在乎太远的奖励，被 $\gamma$ 衰减掉了
- 使用衰减系数，无需担心存在无限循环的转移图
-
$Q^(s_t,a_t)=\mathop{\max}{\pi} Q{\pi}(s_t,a_t)$，可以对 $a_t$ 做评价，这个动作有多好,求出来了$Q^$之后，Agent便可以根据这个动作价值函数选取最优的动作
-
状态-价值函数(State-Value Function)存在两种形式：状态 $s$ 的状态价值——回报的期望值；某个（state，action）元组的行为价值函数——该行为相比于平均状态能够获得多大收益？
$V(s)$能够表示当前局势的好坏。而$Q_{\pi}(s,a)$能够衡量Agent在s状态下选取动作a的好坏。
- 我们可以利用行为的分布以及行为的价值函数来推导
状态价值函数
$$ \begin{aligned}V_{\pi}(s) &= \sum_{a \in \mathcal{A}} Q_{\pi}(s, a) \pi(a \vert s) \&=\mathbb{E}A[Q{\pi}(s, A)]
\end{aligned}$$
- 定义行为价值函数和状态价值函数之间的差称为
优势(advantage)函数，意味着这个动作比平均状态好多少？
$$ A_{\pi}(s, a) = Q_{\pi}(s, a) - V_{\pi}(s) $$
- 对$V_{\pi}(S)$求期望$\mathbb{E}S[V{\pi}(S)]$，我们可以得到这个 policy $\pi$ 的好坏
-
贝斯曼方程与 Return(aka cumulative future reward),注意Return跟上面的奖励Reward是不一样的。
- 贝尔曼方程指的是一系列的等式，它将价值函数分解为直接奖励加上衰减后的未来奖励。(discounted rewards)
- return(aka cumulative future reward),
Return并不是reward，它可以这么表示: $U_t={R_t}+R_{t+1}+R_{t+2}+…$
- discounted return (aka cumulative discounted future reward) : $U_t=\gamma^0 R_t+\gamma^1R_{t+1}+\gamma^2R_{t+2}+…$ ,其中 $\gamma$ 是一个超参数。在这里，$U_t$ 也是个位置变量，因为动作还没有发生，我们没有办法获得 $t$ 时候的奖励以及 $t$ 时刻之后的奖励，所以 $R$ 都是随机的，那么我们的 $U_t$ 也是随机的，因为下面的第七点
强化学习的随机性，所以我们在这里使用$R$来表示奖励，因为它是随机变量。
- 根据上面的分析，我们可以得知，$R_i$由$S_i$和$A_i$决定，那么$U_t$由一系列随机变量决定：$A_t,A_{t+1},A_{t+2},\dots \ and \ S_t,S_{t+1},S_{t+2},\dots $
-
强化学习的随机性
动作具有随机性，$\pi(\theta)$只输出各个动作的概率，动作是根据概率随机抽样而选取的，即$\mathbb{P}[A=a \vert S=s] =\pi(a\vert s)$状态转换具有随机性，并不是说在状态 $s_i$ 的情况下选取动作 $a$ 就一定会转移到一个固定的状态 $s_{i+1}$，这个状态也是随机的，他可能是 $s_1,s_2,s_3…$中的任意一个，即$\mathbb{P}[S^{\prime}=s^{\prime}\vert S=s,A=a]=p(s^{\prime}\vert s,a)$
-
轨迹 trajectory
我们把一轮游戏从开始到结束的动作、状态、奖励拼起来也就是$(s_1,a_1,r_1,s_2,a_2,r_2,s_3,a_3,r_3, \dots, s_n,a_n,r_n)$这就是个轨迹，称之为 trajectory,轨迹，后面很多算法要用到轨迹
-
AI 如何控制 agent 打游戏？
学习 Q*$(s_t,a_t)=max_\pi Q_{\pi}(s_t,a_t)$，根据状态 $s_t$ 选择 $a_t$，$a_t$ 满足条件：$a_t$ 能够使得 Q*最大学习策略 Pi(a|s)，根据状态 $s_t$，根据 $\pi(·|s_t)$的概率随机采样- 第一个就是ValueBased RL,第二种就是PolicyBased RL。
-
概率论相关的数学知识
-
随机变量
一个变量，它的值由一个随机事件决定，用大 X 表示随机变量，使用小 x 表示这个随机变量的观测值，概率统计中统一使用大小写来标记随机变量以及他的观测值
-
概率密度函数
Probability Density Function，表示随机变量在某个附近的取值点的可能性。像高斯分布（正态分布）的函数就是一个概率密度函数。
-
期望
给定 X 为随机变量，求 $f(X)$的期望：
- 在离散情况下，就是 $p(x)f(x)$的加和
- 在连续情况下，就是 $P(x)f(x)$的积分即$\int_x P(x)f(x)$
-
随机抽样
获得 $X$ 的观测值 $x$ 的操作叫做随机抽样
-
蒙特卡洛 Monte Carlo 抽样的用法
-
计算 $\pi$
假定$(x,y)$是在一个边长为 $1$ 的正方形之内随机选一个点，那么这个点符合均匀分布的规律，那么这个点落在正方形内接圆的概率是多少呢？用面积可以算出来是 $π/4$,那我们抽样 $n$ 个点，应该有 $πn/4$ 个点落在圆里面，如果 $n$ 非常大的话我们发现 $m$ 个点在圆里面，那么 $m≈πn/4$。
要保证抽样是均匀的
-
Buffon’s Needle Problem
投针问题也能够很好地近似估算 $\pi$
-
估计阴影部分的面积
使用蒙特卡洛进行近似计算
-
近似求积分
有些函数过于复杂，没有解析的积分，需要蒙特卡洛方法求定积分，也是无限次抽样
-
近似期望
X 是一个 d 维的随机变量，p(x)是概率密度函数，平均分布的概率是 $p(x)=1/t \ for \ x\in[0,t]$
高斯分布/正态分布：$p(x)=1/(\sigma (2π)^2)\exp[-(x-\mu)^2/2\sigma^2]$
直接求 $F(x)$关于 $P(x)$的定积分有时候很难，我们抽按照 $p(x)$的分布抽 $n$ 个样本，计算 $Q_n=\sum \frac {f(x_i)} {n}$，即 $Q_n$ 是 $ \mathbb{E}[f(x)]$
-
关于TD学习
TD 学习 temporal difference,与蒙特卡洛方法类似，时差(TD)学习是一个无模型(model free)方法，它从每轮的经验数据中学习。不同的是，TD 学习可以从不完整的一轮数据中学习，因此我们无需让代理一直执行到环境为终止态。
2. 价值学习 Value Based Leaning --学习 $Q^*(s,a)$
-
关于Qlearning的收敛性证明，请查看这里
-
$U_t$ 被定义为折扣回报或者是折扣奖励，那么我们关于策略 π 的动作-价值函数 $Q_{\pi}(s_t,a_t)$等于 $U_t$ 的期望（因为 $U_t$ 求不出来，所以要求期望），叫做期望回报。
-
那么当前的 $Q_{\pi}$ 只与当前的状态和动作 $s_t$ 和 $a_t$ 有关，它反映了当前这个状态下执行动作 $a_t$ 的好坏
-
$Q^(s,a)$ 为当策略最好的时候我们的动作状态值(optimal action-value function)，也就是说，不管我们使用什么策略 $\pi$，我们最后选取的动作，他的 Q 值都不会比 Q好, $Q^*$ 函数的意义是指示Agent在 $s$ 状态下选取动作 $a$ 时的好坏。
-
难点在于我们不知道所谓的 $Q^(s,a)$ ，于是我们使用深度神经网络 $Q(s,a;\mathbf{w})$ 去拟合 $Q^(s,a)$ ,对于不同的问题，神经网络的结构也可能不同。
-
关于 TD 学习 temporal difference Learning：
- $Q(\mathbf{w})$负责估计代价，我们采样 $q=Q(\mathbf{w})$，假设采样值为1000
- 在现实中，我们进行试验，比如说玩一整轮游戏，然后得到实际的代价 $y=860$
- 计算损失$\mathcal{L}=\frac{(q-y)^2}{2}$
- 计算$\mathcal{L}$ 关于参数$\mathbf{w}$ 的梯度，根据链式求导法则，我们可以得到 $
\frac{\partial{\mathcal{L}}}{\partial \mathbf{w}}=\frac{\partial q}{\partial \mathbf{w}}\frac{\partial{\mathcal{L}}}{\partial q}=(q-y)\frac{\partial Q(\mathbf{w})}{\partial \mathbf{w}}$
- 进行梯度下降，$w_{t+1} = w_t - \alpha \frac{\partial{\mathcal{L}}}{\partial \mathbf{w}}|_{\mathbf{w}=\mathbf{w}_t}$，其中 alpha 是超参数，是步长。
/TDLearningNaive.png?v=3)
- 但是在玩游戏的过程中，我们因为某种原因，只玩到一半，得到价值，我们需要$ Q(w)$估计另外一半的代价，两者相加得到代价 $\hat y$，这个 $\hat y$称为
TD target，它肯定比 $Q(w)$估计整个过程要靠谱，因为我们有一半的数值是真的。我们用这个 $\hat y$ 来代替上面的 $y$，也可以更新参数。
- 由上一步，我们将$Q(\mathbf{w})-\hat y$称为
TD ERROR, Temporal Difference Error
- 我们的优化目标就是让 TD Error = 0
1. Qlearning - off_policy TD control
建议对比下面的[Sarsa](# 2. Sarsa (State-Action-Reward-State-Action) - on_policy TD control)算法来看
-
QLearning 训练最优的动作-价值函数 $ Q^(s,a)$，TD Target是 $y_t=r_t + \gamma \ \underset{a}{max} Q^(s_{t+1},a) $，DQN就是这个模式。
-
维护一个 Q 表，表中的每个元素代表每个状态下每个动作的潜在奖励
根据 Q 表选择动作，然后更新 Q 表
state 1 2 3 4 5
left 0 0 0 0 0
right 0 0 0 1 0
-
更新策略：现实值=现实值+lr*（估计值-现实值）
1. 推导
-
对于所有的策略 $\pi$ 有
$$
Q_{\pi}(s_t,a_t) = \mathbb{E}[R_t+\gamma \cdot Q_{\pi}(S_{t+1},A_{t+1})]
$$
对于最优的策略 $\pi^$来说也有
$$
Q_{\pi^}(s_t,a_t) = \mathbb{E}[R_t+\gamma \cdot Q_{\pi^*}(S_{t+1},A_{t+1})]
$$
-
在QLearning中，我们使用
$$ A_{t+1} = \underset{a}{argmax} \ Q^(S_{t+1},a)$$
来计算 $ A_{t+1} $，所以我们有
$$
Q_{\pi^}(S_{t+1},A_{t+1}) = \underset{a}{max} \ Q^*(S_{t+1},a)
$$
-
消掉 $Q_{\pi^}(S_{t+1},A_{t+1})$ ,于是我们消掉了 $A_{t+1}$，于是我们有
$$
Q_{\pi^}(s_t,a_t) = \mathbb{E}[R_t+\gamma \cdot \underset{a}{max} \ Q^*(S_{t+1},a)]
$$
-
期望很难求，于是又要做蒙特卡洛近似，使用观测值$r_t$,$s_{t+1}$来近似$R_t$,$S_{t+1}$，于是有：
$$
Q_{\pi^}(s_t,a_t) = \mathbb{E}[r_t+\gamma \cdot \underset{a}{max} \ Q^(s_{t+1},a)]
$$
我们称为 $r_t+\gamma \cdot \underset{a}{max} \ Q^*(s_{t+1},a)$叫做TD Target $y_t$
2. 算法步骤(表格形式)
- 观测到状态 $(s_t,a_t,r_t,s_{t+1})$
- 计算TD Target : $r_t+\gamma \cdot \underset{a}{max} \ Q^*(s_{t+1},a)$
- 计算 TD Error : $ \delta_t = Q^*(s_t,a_t)-y_t$
- 更新$Q^$ : $Q^(s_t,a_t) \gets Q^*(s_t,a_t) - \alpha \cdot \delta_t$
- 根据 $\underset{a}{max} \ Q^*(s_{t+1},a)$采样动作，然后采取该动作，转1
2. Sarsa (State-Action-Reward-State-Action) - on_policy TD control
1. 与QLearning的区别
-
Qlearning 更新方法：根据当前Q表选择动作->执行动作->更新Q表
-
Sarsa 更新方法：执行动作->根据当前估计值选择下一步动作->更新Q表
-
总结：Sarsa 是行动派，Qlearning 是保守派
-
Sarsa 训练动作-价值函数 $Q_{\pi}(s,a) $ ，它的 TD Target是 $y_t= r_t + \gamma \cdot Q_{\pi}(s_{t+1},a_{t+1})$, Sarsa是更新价值网络(Critic)
-
QLearning 训练最优的动作-价值函数 $ Q^(s,a)$，TD Target是 $y_t=r_t + \gamma \ \underset{a}{max} Q^(s_{t+1},a) $，DQN就是这个模式。
如果状态空间很大的话我们的表格就很大，如果是连续的动作或者连续的状态的话，就不能用表格来表示了，这时可以使用神经网络来近似状态-价值函数 $Q_{\pi}(s,a)$
- 由前面的推导我们可以知道
$$
U_t = R_t + \gamma \cdot U_{t+1}
$$
- 假设 $R_t$ 由 $(S_t,A_t,S_{t+1})$决定
- 那么可以推导出
$$
\begin{aligned}
Q_{\pi}(s_t,a_t) &= \mathbb{E}[U_t \vert s_t,a_t]\
&=\mathbb{E}[R_t + \gamma \cdot U_{t+1} \vert s_t,a_t]\
&=\mathbb{E}[R_t\vert s_t,a_t] + \gamma \cdot \mathbb{E}[U_{t+1} \vert s_t,a_t]\
&=\mathbb{E}[R_t\vert s_t,a_t]+ \gamma \cdot \mathbb{E}[Q_{\pi}(S_{t+1},A_{t+1}) \vert s_t,a_t]
\end{aligned}
$$
- 期望很难算，所以又要做蒙特卡洛近似，使用 $r_t$和 $Q_{\pi}(s_{t+1},a_{t+1})$去近似 $R_t$ 和 $Q_{\pi}(S_{t+1},A_{t+1})$
- 于是就有了
$$ Q_{\pi}(s_t,a_t) \approx r_t + \gamma \cdot Q_{\pi}(s_{t+1},a_{t+1})$$
我们把 $r_t + \gamma \cdot Q_{\pi}(s_{t+1},a_{t+1})$ 称为TD Traget $y_t$
- TD Learning 的想法就是鼓励 $Q_{\pi}(s_t,a_t)$向 $y_t$逼近
2. 算法步骤(表格形式的Sarsa)
- 观测到状态 $(s_t,a_t,r_t,s_{t+1})$
- 采样动作 $ a_{t+1} \sim \pi(\cdot \vert s_{t+1})$ 其中 $\pi$是策略函数
- 计算TD Target $y_t = r_t + \gamma \cdot Q_{\pi}(s_{t+1},a_{t+1})$
- 计算TD Errorr $\delta_t = Q_{\pi}(s_{t},a_{t}) - y_t $
- 更新 $Q_{\pi}(s_{t},a_{t})$: $Q_{\pi}(s_{t},a_{t}) \gets Q_{\pi}(s_{t},a_{t}) - \alpha\cdot\delta_t$ 其中$\alpha$是学习率，在神经网络中，我们采用梯度下降的方式来更新$Q_{\pi}(s_{t},a_{t})$
- 执行$a_{t+1}$转步骤1
3. 使用多步TD Target 来减少偏差
之前说到$ U_t = R_t + \gamma U_{t+1}$,我们可以进一步展开：
$$
U_t = R_t + \gamma (R_{t+1}+\gamma U_{t+2})
$$
这样就可以使用2步甚至更多步的数据来更新我们的神经网络，来提升稳定性。
3. SarsaLambda
是Sarsa 的升级版
4. DQN Off-Policy
-
神经网络 $Q(s,a;\mathbf{w})$近似 Q*函数，Q*能够告诉我们每个动作能够得到的平均回报。我们需要 agent 遵循这个 Q*函数。
-
用神经网络代替 Q 表的功能/dqn.jpg?v=3)
-
Q 表无法进行所有情况的枚举，在某些情况下是不可行的，比如下围棋。
1. Features: Expericence Replay and Fixed Q-targets
-
Experience Replay : 将每一次实验得到的经验片段记录下来，然后作为经验，投入到经验池中，每次训练的时候随机取出一个 BATCH，可以复用数据。并且可以在经验池上面做一些文章，增加收敛性比如HER、PER、ERE等等。
-
Fixed Q-target: 在神经网络中，Q 的值并不是互相独立的，所以不能够进行分别更新操作，那么我们需要将网络参数复制一份，解决该问题。
-
为了解决 overestimate 的问题，引入 double DQN，算法上有一点点的改进，复制一份网络参数，两个网络的参数异步更新
-
在强化学习中，我们使用于Bootstrapping来更新网络参数，因为TD target和$Q(s_t,a_t;\mathbf{w})$都有估计的成分，我们更新网络参数$\mathbf{w}$的时候是用一个估计值来更新它本身，类似于自己把自己举起来。
-
TDLearning会使DQN高估动作价值(overestimate),原因在于：
-
1.Qlearning中TD target中有最大化操作：
$ y_t = r_t + \gamma \cdot \underset{a}{max} \ Q(s_{t+1},a;\mathbf{w})$这个操作会导致overestimating
设$x(a_1),\dots,x(a_n)$为真实的动作价值，$a_1,\dots,a_n$是$a \in \mathcal{A}$中的所有动作。
我们使用DQN来对上面的动作价值做有噪声的估计：$Q(s,a_1;\mathbf{w}),\dots,Q(s,a_n;\mathbf{w})$
假设这个估计是无偏差的(unbiased estimation)：$\underset{a}{mean}(x(a)) = \underset{a}{mean}(Q(s,a;\mathbf{w}))$
而$q = \underset{a}{max}Q(s,a,\mathbf{w})$,所以我们有 $q \ge \underset{a}{max}(x(a))$(因为Q的估计有偏差，所以它的最大值应该是大于或等于真实值的最大值)
总结 ： 求最大化使估计值大于实际值，导致overestimate的问题。
-
2.Bootstrapping使用估计值更新自己的话，会传播这个高估的值。
我们首先回顾TD target需要用到下一时刻的估计：$ q_{t+1} = \underset{a}{max}Q(s_{t+1},a;\mathbf{w}) $,然后我们使用TD target 来更新我们的$ Q(s_t,a_t;\mathbf{w}) $
假设DQN已经因为最大化高估了动作价值(action-value)，由于$Q(s_{t+1},a;\mathbf{w})$已经高估了，然后还要使用$ q_{t+1} = \underset{a}{max} \ Q(s_{t+1},a;\mathbf{w}) $中的max操作，这就导致了更严重的高估，然后使用$r_t + \gamma q_{t+1}$来更新，传播了这个高估，变得更严重了。
总结：TD target本身有max操作，产生更严重的高估，用TD target更新DQN又进一步加剧了高估
-
为什么Overestimating会带来不好的影响？
如果DQN将每个动作的价值都高估了一个一样的值的话，我们通过max操作得出一样的结果：
假设$Q(s,a^i;\mathbf{w})= Q^*(s,a^i) + 100$，我们使用max操作还是能够得到一样的结果
但是如果高估是非均匀的话，那么就会影响最后的max操作的结果了，这样我们就会基于错误的价值进行决策。
很不幸，在ReplayBuffer里面，我们这种高估是非均匀的：状态$(s_t,a_t)$这个二元组每一次被抽样到就会让DQN高估$(s_t,a_t)$的值，越被频繁抽样到就会产生越严重的高估。而$s$和$a$在经验池中的频率是不均匀的，最终会导致不均匀的高估，他是非常有害的。
-
如何缓解高估问题？
-
使用Fixed Q-targets避免bootstrapping。
-
我们使用两个神经网络$Q(s,a;\mathbf{w}^-)，Q(s,a;\mathbf{w})$来近似动作价值函数，这两个神经网络有一样的结构，但是它们的参数是不同的。
-
使用$Q(s,a;\mathbf{w})$来控制agent来收集经验${(s_t,a_t,r_t,s_{t+1}}$
-
使用target networtk $Q(s,a;\mathbf{w}^-)$来计算TD Target，从而避免了bootstrapping，缓解了高估问题。
-
具体的来说，我们计算TD target用的是Target Network: $y_t = r_t + \gamma \cdot \underset{a}{max} Q(s_{t+1},a;\mathbf{w}^-)$,然后计算TD Error $\delta_t = Q(s_t,a_t;\mathbf{w}) - y_t$,再执行梯度下降更新原来网络的参数$\mathbf{w}$的权重，不更新$\mathbf{w}^-$这样就避免了自举。
-
更新Target Network的方式有两种：一种是直接复制$\mathbf{w}$到$\mathbf{w}^-$上，另外一种是soft_update，将两个参数进行加权平均：$\mathbf{w}^- \gets \tau \mathbf{w}^- + (1-\tau)\mathbf{w} $,其中$\tau$一般取比较保守的值0.95,0.9这些。
-
总结：使用Fixed Q-targets来计算TD Target 避免bootstrapping，但是Target Network无法脱离原来的网络，上面看到了，Target Network的更新是与原来的Network有关的，所以它无法完全避免自举。
-
使用Double DQN来缓解最大化造成的高估。
-
与Fixed Q-targets的区别是计算TD Target的时候使用的网络不一样，前者使用：
$$
\begin{aligned}
a^&= \underset{a}{argmax} Q(s_{t+1},a;\mathbf{w}^-)\
y_t &= r_t +\gamma \cdot Q(s_{t+1},a^;\mathbf{w}^-)
\end{aligned}
$$
来计算TD Target，后者使用
$$
\begin{aligned}
a^&= \underset{a}{argmax} Q(s_{t+1},a;\mathbf{w})\
y_t &= r_t +\gamma \cdot Q(s_{t+1},a^;\mathbf{w}^-)
\end{aligned}
$$
double dqn做出的改动很小，但是性能提升很大，然而它还是没有彻底解决高估的问题。
-
为什么它比前面的Fixed Q-targets要好？
因为$ Q(s_{t+1},a^*;\mathbf{w}^-) \le \underset{a}{max} \ Q(s_{t+1},a;\mathbf{w}^-)$
2. TD 算法在 DQN 中的使用
-
类似于我们在本章开头中提出 TD 学习的概念，我们在 DQN 中也有：$Q(s_t,a_t;\mathbf {w})≈r_t + \gamma Q(s_{t+1},a_{t+1};\mathbf {w})$
-
在上式中，$\gamma$ 为一个奖励的折扣因子
-
折扣回报：$U_t= R_t + \gamma ((R_{t+1})+\gamma(R_{t+2})+…)$ --(在前面消掉一个$\gamma$)
-
那么我们的折扣回报可以写成 $U_t = R_t + \gamma U_{t+1}$, 因为$ \gamma U_{t+1}=\gamma ((R_{t+1})+\gamma(R_{t+2})+…)$
-
反映了两个相邻状态之间的折扣回报的关系
-
那么我们使用 DQN 来输出这个 $U_t$ 的期望（说过很多次，在 $t$ 时刻之后，动作 $A$ 和状态 $S$ 都是随机变量，所以求期望）
-
我们有了$U_t = R_t + \gamma U_{t+1}$，而且$Q(s_t,a_t;\mathbf{w})$是$\mathbb{E}[U_t]$的估计， $Q(s_{t+1},a_{t+1};\mathbf{w})$是$\mathbb{E}[U_{t+1}]$的估计,所以我们有
$$
Q(s_t,a_t;\mathbf{w}) ≈ \mathbb{E}[R_t + \gamma Q(s_{t+1},a_{t+1};\mathbf{w})]
$$
-
到了$t$时刻，我们已经获得观测值 $r_t $了，所以有$Q(s_t,a_t;\mathbf{w}) ≈ r_t +\gamma Q(s_{t+1},a_{t+1};\mathbf{w})$,约等于号后面的那个值肯定要准确一些，我们称之为 TD target , 前面$Q(s_t,a_t;\mathbf{w})$是 prediction（预测值）
-
于是我们的 $loss = \frac{1}{2} ||predict - target ||_2$，再进行梯度下降就可以了
-
使用Experience Replay的动机
- 一个Transition $(s_t,a_t,r_t,s_{t+1})$使用完之后就把它丢弃掉了，不再使用，这是一种浪费，经验可以被重复使用。
- $s_t$和$s_{t+1}$是高度相关的，这样不利于我们模型的收敛，所以需要把$s_t,s_{t+1},\dots,s_T$这个序列打散。
- 于是我们将最近$n$个transitions放到一个
经验池中,$n$是一个超参数，他一般是十万或者百万级别的。
- 在ER里面，可以做mini-batch SGD，随机均匀抽取一小部分样本，取梯度的平均值进行梯度下降。
- 除了均匀抽样以外，我们还有非均匀抽样，这也就是下面的PrioritizedExperienceReplay
3.三种方法的价值网络的更新方式比较
| method |
selection |
evaluation |
| Naive DQN |
$\mathbf{w}$ |
$\mathbf{w}$ |
| Fixed Q-targets |
target network $\mathbf{w}^-$ |
target network $\mathbf{w}^-$ |
| double DQN |
$\mathbf{w}$ |
target network $\mathbf{w}^-$ |
5. Dueling DQN Off-Policy
将 Q 值的计算分成状态值 state_value 和每个动作的值 advantage，可以获得更好的性能，这是网络架构上面的改进，这个思想也可以用在其它地方。
1. Advantage Function 优势函数
$$
\begin{aligned}
Q^* (s,a) &= \underset{a}{max} \ Q_{\pi}(s,a)\
V^* (s) &= \underset{\pi}{max} \ V_{\pi}(s)\
A^* (s,a) &= Q^(s,a) -V^(s)
\end{aligned}
$$
$A^(s,a)$的意思是动作$a$相对于baseline $V^(s)$的优势，动作$a$越好，$A^*(s,a)$越大。
由于$ V^(s) = \underset{a}{max} \ Q ^(s,a)$，我们对左右两边取最大值，有：
$$
\underset{a}{max} \ A^(s,a) = \underset{a}{max} \ Q_{\pi}(s,a) - V^(s) =0
$$
我们将公式变换一下：
$$
Q^(s,a) = V^(s) + A^* (s,a)
$$
再减去一个0 ： $\underset{a}{max} \ A^(s,a)$得到：
$$
Q^(s,a) = V^(s) + A^ (s,a) - \underset{a}{max} \ A^*(s,a)
$$
2. Dueling DQN的设计
-
我们使用神经网络$A(s,a;\mathbf{w}^A)$去近似$A^* (s,a)$
-
再使用$V(s;\mathbf{w}^V)$来近似$V^*(s)$
-
然后，我们的$Q^*(s,a)便可以用两个神经网络来表示：
$$
Q(s,a;\mathbf{w}^A,\mathbf{w}^V) = V(s;\mathbf{w}^V)+ A(s,a;\mathbf{w}^A) - \underset{a}{max} \ A(s,a;\mathbf{w}^A)
$$
它相比Naive DQN多了一个参数，训练过程是一样的，因为两者都需要采取状态$s$作为输入，我们一般共享feature层。
-
为什么上面的公式需要减上$\ \underset{a}{max} \ A(s,a;\mathbf{w}^A)$
因为$ Q^(s,a) = V^(s) + A^(s,a)$中满足这个条件的$V^(s) + A^* (s,a)$有很多组，比如$ 1+9=10, 2+8=10$这样会使训练不稳定
所以加上后面的最大化，防止这种不唯一性，防止上下波动导致的训练不稳定。
$$
Q^(s,a) = V^(s) + A^(s,a) - \underset{a}{max} \ A^(s,a)
$$
在实践中，我们会把max换成mean:
$$
Q^(s,a) = V^(s) + A^(s,a) - \underset{a}{mean} \ A^(s,a)
$$
在DuelingDQN的模型代码中我们可以看到：
def forward(self, x: t.Tensor) -> t.Tensor:
feature1 = F.relu(self.feature_layer(x))
feature2 = F.relu(self.feature_layer(x))
# value
value = self.value_layer(feature1)
# advantage
advantage = self.advantage_layer(feature2)
# 其实在这里写advantage.mean(dim=1).expand_as(advantage)也是可以的
# advantage满足 sum(advantage)=0
return value+advantage-advantage.mean(dim=1, keepdim=True)
6. DQN with Prioritized Experience Replay Off-Policy
在 DQN 中，我们有 Experience Replay，但是这是经验是随机抽取的，我们需要让好的、成功的记忆多多被学习到，所以我们在抽取经验的时候，就需要把这些记忆优先给网络学习，于是就有了Prioritized Experience Replay。
PER只在经验池这个地方做了改进，具体部分可以查看代码。
-
使用TD Error来判断Transitions的重要性，如果DQN不熟悉这个transition，我们就让这个transition多多的出现，就能够让DQN熟悉。
-
使用重要性采样(importance sampling)来替代均匀抽样(uniform sampling):
$ p_t \propto \vert \delta_t \vert +\epsilon$或者是 $ p_t \propto \frac{1}{rank(t)}$，其中$rank(t)$是td error第t大的transition。
-
两种方法的原理是一样的，就是让$\delta_t$越大的transition更多地被采样到。
-
不均匀抽样会导致偏差，我们需要对学习率进行缩放
- 将lr缩放至 $ \gamma \gets \gamma \cdot (n p_t)^{-\beta}$ ，其中 $\beta \in (0,1)$
- 拥有较高优先级（较高的 $p_t$ ）的transitions有较低的学习率；开始的时候 $\beta$ 很小，之后随着训练的进程提升到1。
-
如果新经验没有被学习，我们将它的$\delta_t$设置为$ \delta_{max}$，之后随着训练的进程，当这个经验被学习到的时候，我们更新这个$\delta_t$
3. 策略学习 Policy Based Learning --学习策略 $\pi(a|s)$
-
在连续空间下，State是无限的，使用基于Qlearning的方法需要求 $ max_{a \in \mathcal{A}} Q_{\pi}(s,a)$ 的计算代价很大，我们期望基于策略的方法在连续空间中的表现会比策略迭代法有用。
-
Policy Function $\pi(a \vert s)$是一个概率密度函数(probability density function)，它以状态$s$为输入，输出的是每个动作对应的概率值。
在DDPG等算法中，我们的Policy是确定的，也就是它输出一个动作，而不是概率值，我们称之为 $ a = \mu(s)$
-
Discounted Return, Action-value function, State-value function
$$
\begin{aligned}
U_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \dots
\
Q_{\pi}(s_t,a_t) &= \mathbb{E}[U_t \vert S_t=s_t,A_t= a_t]\
V_{\pi}(s_t)&=\mathbb{E}_
A[Q_{\pi}(s_t,A)], A \sim \pi (\cdot \vert s_t)
\end{aligned}
$$
对于离散的动作我们有
$$
V_{\pi}(s_t) = \mathbb{E}[Q_{\pi}(s_t,A)] =\Sigma_a \pi(a \vert s_t)Q_{\pi}(s_t,a),A \sim \pi (\cdot \vert s_t)
$$
对于连续的动作，我们需要求个积分
$$
V_{\pi}(s_t) = \mathbb{E}[Q_{\pi}(s_t,A)] =\int \pi(a \vert s_t)Q_{\pi}(s_t,a),A \sim \pi (\cdot \vert s_t)
$$
-
在基于策略的方法里，我们需要使用神经网络$\pi (a\vert s_t;\mathbf{\theta})$来近似策略函数$\pi(a\vert s_t)$,使用$V(s_t;\mathbf{\theta})=\Sigma_a \pi(a \vert s_t;\mathbf{\theta})Q_{\pi}(s_t,a)$来状态价值函数state-value function
-
在Policy-based methods里面，我们要尝试最大化$V(s;\mathbf{\theta})$的期望。
即$J(\mathbf{\theta})=\mathbb{E}_S[V(s;\mathbf{\theta})]$
-
使用梯度上升方法来更新$\theta$
观测到状态$s$
Update Policy by: $\theta \gets \theta + \beta \cdot \frac{\partial V(s;\theta)}{\partial \theta}$
其中这个$\frac{\partial V(s;\theta)}{\partial \theta}$就叫做策略的梯度Policy Gradient,详细的推导请见下面的Policy Gradient方法
-
在这个章节中，除了 Policy Gradient 算法没有用到 Critic，其余好像都用到了 critic 或者类似于 actor-critic 的架构，比如说 DDPG 是个 AC 架构，而 AC A2C A3C TRPO 等都用到了 Actor 和 Critic，两者的区别就是Actor参数更新方式不同，AC架构仍然使用Q Value作为Actor的loss，而AC就是使用带权重的梯度更新。
-
PG 算法学习的就是策略，像PG 中 readme里面说的一样我们为什么不用神经网络来近似 $Q_{\pi}$，就可以不用 Discounted Rewards 来代替 $Q_{\pi}$。
-
所以我们可以转为策略学习+值学习，他是 Value based methods 和 Policy based methods 的结合
-
状态价值$ V_{\pi}(s)=\Sigma_a \pi(a|s) Q_{\pi}(s,a)$，使用 Actor 来近似 $\pi$，使用 Critic 来近似 $Q_{\pi}$.
-
减少方差–策略梯度方法中的baseline
-
baseline $b$可以是任何独立于动作$A$的函数
-
证明baseline的理论性质
$$
\begin{aligned}
\mathbb{E}
_
{A \sim \pi(\cdot \vert s; \theta)}\left[b \cdot \frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} \right] &= b \cdot \mathbb{E}_ {A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} \right]\
&= b \cdot \sum_a \pi(a \vert s; \theta) \cdot \frac{\partial \ln \pi(a \vert s;\theta) }{\partial \theta}\
&= b \cdot \sum_a \pi(a \vert s; \theta) \cdot \frac {1}{\pi(a \vert s; \theta)}\frac{\partial \pi(a \vert s;\theta) }{\partial \theta}\
&= b \cdot \sum_a \frac{\partial \pi(a \vert s;\theta) }{\partial \theta}\
&= b \cdot \frac{\sum_a \partial \pi(a \vert s;\theta) }{\partial \theta}\
&= b\cdot \frac{\partial 1 }{\partial \theta}\
&= 0
\end{aligned}
$$
于是有策略梯度公式：
$$
\begin{aligned}
\frac{\partial V(s;\theta)}{\partial \theta}&=
\mathbb{E}_
{A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} Q_{\pi}(s,A)\right]\
&= \mathbb{E}_
{A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} Q_{\pi}(s,A)\right] - \mathbb{E}_ {A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} \right]\
&=\mathbb{E}_
{A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s;\theta) }{\partial \theta} \left(Q_{\pi}(s,A)-b\right)\right]
\end{aligned}
$$
所以我们有：如果$b$与$A_t$是独立的，那么策略梯度可以表示为：
$$
\mathbb{E}_
{A_t \sim \pi(\cdot \vert s_t; \theta)}\left[\frac{\partial \ln \pi(A_t \vert s_t;\theta) }{\partial \theta} \left(Q_{\pi}(s_t,A_t)-b\right)\right]
$$
baseline $b$不会影响上面的结果，在我们对这个梯度进行蒙特卡洛近似的时候，一个好的$b$会让后面的$\left(Q_{\pi}(s_t,A_t)-b\right)$会让方差降低，算法收敛更快
-
蒙特卡洛近似
现在我们知道了策略梯度：
$$
\frac{\partial V(s;\theta)}{\partial \theta}=\mathbb{E}_
{A_t \sim \pi(\cdot \vert s_t; \theta)}\left[\frac{\partial \ln \pi(A_t \vert s_t;\theta) }{\partial \theta} \left(Q_{\pi}(s_t,A_t)-b\right)\right]
$$
令
$$
\left[\frac{\partial \ln \pi(A_t \vert s_t;\theta) }{\partial \theta} \left(Q_{\pi}(s_t,A_t)-b\right)\right] = \mathbf{g}(A_t)
$$
我们随机抽样动作$a_t$ : $a_t \sim \pi(\cdot \vert s_t; \theta)$然后计算梯度$\mathbf{g}(a_t)$，而且$\mathbf{g}(a_t)$是对原来梯度的一个无偏估计:
$$
\mathbb{E}_
{A_t \sim \pi(\cdot \vert s_t; \theta)}[\mathbf{g}(a_t)] \approx \frac{\partial V_\pi(s_t;\theta)}{\partial \theta}
$$
然后执行梯度上升
$$
\theta \gets \theta + \beta\cdot \mathbf{g}(a_t)
$$
前面证明了只要$b$跟$A_t$无关，我们的$\mathbf{g}(a_t)$的期望$\mathbb{E}_{A_t \sim \pi(\cdot \vert s_t; \theta)}[\mathbf{g}(A_t)]$就不会变，但是$b$会影响抽样结果$\mathbf{g}(a_t)$，所以一个好的$b$会使方差减少，增加算法收敛
-
baseline的选取
-
策略梯度算法的一般形式
/gae.png?v=3)
1. Policy Gradient On-Policy
核心思想：让好的行为多被选择，坏的行为少被选择。
/5-1-1.png?v=3)
1. 具体推导（简单版本）
这里是不严谨的推导，便于直观地上手，我们假设 $Q_\pi$ 不依赖于 $\theta$，要查看详细的推导，请移步至
本文的这里,具体的过程以及一系列讲解请查看
这个网站
$$V(s_t;\mathbf{\theta})=\Sigma_a \pi(a \vert s_t;\mathbf{\theta})Q_{\pi}(s_t,a)$$
$$
\begin{aligned}
\frac{\partial V(s;\theta)}{\partial \theta} &= \frac{\partial \Sigma_a \pi(a \vert s;\theta) Q_{\pi}(s,a)}{\partial \theta}\
&= \Sigma_a\frac{\partial \pi(a \vert s;\theta) Q_{\pi}(s,a)}{\partial \theta}\
&= \Sigma_a\frac{\partial \pi(a \vert s;\theta) }{\partial \theta} Q_{\pi}(s,a) \text{ 假设Qpi不依赖于theta,但不严谨}\
\end{aligned}
$$
于是就有了
$$
\begin{aligned}
\frac{\partial V(s;\theta)}{\partial \theta}&=\Sigma_a\frac{\partial \pi(a \vert s;\theta) }{\partial \theta} Q_{\pi}(s,a)\
&= \Sigma_a\ \pi(a \vert s;\theta)\frac{\partial \log \pi(a \vert s;\theta) }{\partial \theta} Q_{\pi}(s,a)\
&= \mathbb{E}_ {A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \log \pi(A \vert s;\theta) }{\partial \theta} \ Q_{\pi}(s,A)\right]
\end{aligned}
$$
-
对于离散的动作来说使用
$$
\frac{\partial V(s;\theta)}{\partial \theta}=\Sigma_a\frac{\partial \pi(a \vert s;\theta) }{\partial \theta} Q_{\pi}(s,a)
$$
对于每个动作都求一次，然后加起来就可以辣
-
对于连续的动作来说使用
$$
\frac{\partial V(s;\theta)}{\partial \theta}=
\mathbb{E}{A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \log \pi(A \vert s;\theta) }{\partial \theta} Q{\pi}(s,A)\right]
$$
-
使用蒙特卡洛抽样来求梯度
- 根据概率密度函数$\pi (\cdot \vert s;\theta)$采样出一个$\hat a$
- 计算$\mathbf{g}(\hat a ,\theta) = \frac{\partial \log \pi(\hat a \vert s;\theta) }{\partial \theta} Q_{\pi}(s,\hat a)$
- 很显然，$\mathbb{E}_A [\mathbf{g}(A,\theta)]=\frac{\partial V(s;\theta)}{\partial \theta}$而且$\mathbf{g}(\hat a ,\theta)$是$\frac{\partial V(s;\theta)}{\partial \theta}$的一个无偏估计。
这种方法对于上面的离散行为也适用
2. Policy Gradient算法细节
-
观测到当前状态$s_t$
-
根据策略网络$\pi (\cdot \vert s; \theta_t)$来选取一个动作$a_t$,注意动作$a_t$是随机抽样得来的
-
计算$q_t \approx Q_{\pi}(s_t,a_t)$，在这一步需要做一些估计
-
求$J(\theta)$关于$\theta$的梯度$\mathbf{g}(a_t ,\theta_t) = q_t \frac{ \log \pi(a_t \vert s_t;\theta) }{\partial \theta} |_{\theta =\theta_t}$
-
梯度上升:$\theta_{t+1} = \theta_t + \beta \cdot \mathbf{g}(a_t,\theta_t)$
在第三步中，我们如何计算 $q_t \approx Q_{\pi}(s_t,a_t)$ ? 有两种方法：
-
REINFORCE
玩一局游戏得到这局游戏的轨迹Trajectory
$s_1,a_1,r_1,s_2,a_2,r_2,\dots,s_T,a_T,r_T$
对于所有的$t$计算discounted return
$
u_t = \sum_{k=t}^T \gamma^{k-t}r_k
$
由于$Q_{\pi}(s_t,a_t) = \mathbb{E}[U_t]$,我们可以使用$u_t$来去近似$Q_{\pi}(s_t,a_t)$，这种方法显而易见有一个缺点：玩完一局游戏才能进行更新，低效。
-
使用神经网络去近似$Q_{\pi}$
这就是下面的ActorCritic Methods
3. REINFORCE with Baseline
-
关于baseline可以在策略学习这里看到
-
我们有随机策略梯度：
$$
\mathbf{g}(a_t) = \frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta} \cdot \left(Q_\pi (s_t,a_t)-V_\pi(s_t) \right)
$$
-
由于 $Q_\pi(s_t,a_t) = \mathbb{E}[U_t \vert s_t,a_t]$,我们可以进行蒙特卡洛近似$Q_\pi(s_t,a_t) \approx u_t$，最后我们需要求$u_t$
-
如何求$u_t$？我们玩一局游戏观测到轨迹$(s_t,a_t,r_t,s_{t+1},a_{t+1},r_{t+1},\dots,s_n,a_n,r_n)$，然后计算return:$u_t = \sum_{i=t}^{n}r^{i-t} \cdot r_t$，而且$u_t$是对$Q_\pi(s_t,a_t)$的无偏估计
-
我们还差个$V_{\pi}(s_t)$，我们用神经网络来$V_{\pi}(s_t;\mathbf{w})$近似，于是策略梯度可以近似为：
$$
\frac{\partial V_{\pi}(s_t)}{\partial \theta} \approx \mathbf{g}(a_t) \approx \frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta} \cdot \left(u_t - v(s_t;\mathbf{w}) \right)
$$
-
总结下来我们用了三个蒙特卡洛近似：
$$
\frac{\partial V_{\pi}(s_t)}{\partial \theta} = \mathbf{g}(A_t) = \mathbb{E}_ {A \sim \pi(\cdot \vert s; \theta)}\left[\frac{\partial \ln \pi(A \vert s_t;\theta) }{\partial \theta} \ \left(Q_{\pi}(s_t,a_t) -V_\pi(s_t)\right)\right]
$$
用$a \sim \pi(\cdot \vert s_t)$去采样动作，这是第一次近似。
$$
\mathbf{g}(a_t) = \left[\frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta} \ \left(Q_{\pi}(s_t,a_t) -V_\pi(s_t)\right)\right]
$$
然后用$u_t$和$v(s_t;\mathbf{w})$去近似$Q_{\pi}(s_t,a_t) $和$V_\pi(s_t)$，这是第二三次近似：
$$
\mathbf{g}(a_t) \approx \frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta} \cdot \left(u_t - v(s_t;\mathbf{w}) \right)
$$
-
这么一来我们就有两个网络了：策略网络$ \pi(a \vert s)$和价值网络：$V(s;\mathbf{w})$，同样地也可以共享feature层的参数。
-
算法步骤
-
我们玩一局游戏观测到轨迹$(s_t,a_t,r_t,s_{t+1},a_{t+1},r_{t+1},\dots,s_n,a_n,r_n$
-
计算return:$u_t = \sum_{i=t}^{n}r^{i-t} \cdot r_t$ 和 $\delta_t = v(s_t;\mathbf{w}) - u_t$
-
更新参数$\theta$和$\mathbf{w}$：
$$
\begin{aligned}
\theta &\gets \theta - \beta \cdot \delta_t \cdot \frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta}\
\mathbf{w} &\gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial v(s_t;\mathbf{w})}{\partial \mathbf{w}}
\end{aligned}
$$
4. Policy Gradient 算法的详细推导,有点难
在上面的推导中，我们说了假设$Q_\pi$不依赖于$\theta$,但不严谨，在这里我们写一个完整的推导版本，上面不严谨的推导便于我们快速了解算法，这里是它的真面目。
注意在下面的公式里面 $Q^\pi$和之前出现的$Q_\pi$是一个意义，同样地，$ \pi_\theta(s\vert a)$和 $\pi(s\vert a;\theta)$是一样的意义。
-
首先我们的目标函数定义为:
$$
J(\theta) = \sum_{s\in \mathcal{S}} d^\pi(s) V^\pi(s) = \sum_{s\in \mathcal{S}} d^\pi(s)\sum_{a \in \mathcal{A}} \pi(a\vert s;\theta) Q^{\pi}(s,a)
$$
其中 $d^\pi(s)$为策略$\pi(\theta)$决定的马尔科夫平稳分布，其余的符号可以在术语表中看到。
马尔科夫链的平稳性：如果我们可以持续永久遍历马尔科夫链中的所有状态，那么随着时间的推移，最终停留在某个状态的概率是一定的，这就是策略 $\pi(\theta)$的平稳性。
我们定义 $d^\pi(s)$为:
$d^\pi(s)= \lim_{t \to \infty}P(s_t = s \vert s_0,\pi_\theta)$
意思是在初始状态 $s_0$开始，遵循策略$\pi$的时候，执行$t$步之后，状态停留在$s$的概率。
根据目标函数$J(\theta)$的梯度 $\nabla_\theta J(\theta)$，我们可以提升策略梯度算法，最终可以最大化最终收益。
上面的$J(\theta)$是在连续环境（没有固定的终止状态）下的目标函数(被称为平均值)，连续环境下还有一种性质更好的目标函数，叫做平均回报：
$$
\begin{aligned}
J(\theta) &\approx r(\pi)\
& \approx \lim_{h \to \infty} \frac{1}{h} \sum_{t=1}^h \mathbb{E} [R_t \vert S_0, A_{0:t-1} \sim \pi]\
&= \lim_{t \to \infty} \mathbb{E} [R_t \vert S_0, A_{0:t-1}]\
&= \sum_s \mu(s) \sum_a \pi_\theta(a \vert s) \sum_{s^{\prime},r} p(s^{\prime},r \vert s,a)r\
\end{aligned}
$$
我们还定义：
$$
\begin{aligned}
G_t &= R_{t+1} - r(\pi)+R_{t+2} - r(\pi)+R_{t+3} - r(\pi)+\dots\
V^\pi(s) &= \sum_a \pi_\theta(a \vert s) \sum_{r,s^\prime} p(s^\prime,r \vert s,a) [r-r(\pi) + V^\pi(s^\prime)]\
Q^\pi(s,a)&= \sum_{r,s^\prime} p(s^\prime,r \vert s,a) [r-r(\pi) +\sum_{a^\prime} \pi_\theta(a^\prime \vert s^\prime)Q^\pi({s^\prime,a^\prime})]\
\end{aligned}
$$
分别为差分累计回报定义——回报与平均回报差值的累加值、差分状态-价值函数和差分动作状态-价值函数。
平均值目标函数是 $J(\theta)$的另外一种形式：
$$
\begin{aligned}
J(\theta) &= \sum_{s\in \mathcal{S}} d^\pi(s) V^\pi(s)\
&= \sum_{s\in \mathcal{S}} d^\pi(s)\underbrace {\sum_a \pi_\theta(a \vert s) \sum_{r,s^\prime} p(s^\prime,r \vert s,a) [r +\gamma V^\pi(s^\prime)]}_{V^\pi(s)}\
&= r(\pi) + \sum_{s\in \mathcal{S}} d^\pi(s) {\sum_a \pi_\theta(a \vert s) \sum_{r,s^\prime} p(s^\prime,r \vert s,a) [V^\pi(s^\prime)]},根据定义把r(\pi)提出来\
&= r(\pi) + \gamma \sum_{s^\prime}V^\pi(s^\prime) \sum_s d^\pi(s) \sum_a \pi_\theta(a \vert s) p(s^\prime \vert s,a)\
&= r(\pi) + \gamma \sum_{s^\prime}V^\pi(s^\prime)d^\pi(s^\prime)\
&= r(\pi) + \gamma J(\theta)\
&= r(\pi) + \gamma (r(\pi) + \gamma J(\theta))\
&= \dots\
&= \frac{1}{1-\gamma} r(\pi)
\end{aligned}
$$
因此在下面的推导中，只考虑平均回报形式的目标函数$r(\pi)$
综上所述，目标函数有3种形式:
$$
\begin{aligned}
J(\theta) &\overset{\text{def}}{=} \sum_{s\in \mathcal{S}} d^\pi(s)\sum_{a \in \mathcal{A}} Q^{\pi}(s,a) \pi_\theta(a \vert s) \text{连续环境下的平均值形式目标函数,无固定终结状态}\
& \overset{\text{def}}{=} \sum_s \mu(s) \sum_a \pi_\theta(a \vert s) \sum_{s^{\prime},r} p(s^{\prime},r \vert s,a)r\text{连续环境下的平均回报形式目标函数,无固定终结状态}\
&\overset{\text{def}}{=} V^\pi(s_0) =\mathbb{E}\left[\sum_{t=1}^{+\infty}\gamma^t r_t \vert s_0,\pi\right]\text{周期环境下的目标函数,有固定的起始状态和终结状态}
\end{aligned}
$$
-
策略梯度定理
由于梯度 $ \nabla_\theta J(\theta)$的计算是非常棘手的，但是我们有策略梯度定理：
$$
\begin {aligned}
\nabla_\theta J(\theta) &= \nabla_\theta \sum_{s\in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s,a) \pi(a \vert s;\theta)\
& \propto \sum_{s\in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s,a) \nabla_\theta \pi(a \vert s;\theta)
\end{aligned}
$$
-
策略梯度定理的证明
首先对状态价值函数求导：
$$
\begin {aligned}
\nabla_\theta V^\pi(s)
&=\nabla_\theta \left(\sum_{a\in \mathcal{A}} \pi(a\vert s;\theta) Q^\pi(s,a)\right)\
&=\sum_{a\in \mathcal{A}} \left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \nabla_\theta Q^\pi(s,a) \right)\
&=\sum_{a\in \mathcal{A}}\left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \nabla_\theta \underbrace{\sum_{s^{\prime},r} P(s^\prime,r \vert s,a)(r + V^\pi(s^\prime))}_{Q^\pi(s,a)} \right)\
&=\sum_{a\in \mathcal{A}}\left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \sum_{s^{\prime},r} P(s^\prime,r \vert s,a) \nabla_\theta V^\pi(s^\prime) \right) \text{r和状态转移概率与theta无关}\
&=\sum_{a\in \mathcal{A}}\left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \sum_{s^{\prime}} \underbrace{P(s^\prime \vert s,a)}{P(s^\prime \vert s,a) = \sum{r}P(s^\prime,r \vert s,a)} \nabla_\theta V^\pi(s^\prime) \right)
\end{aligned}
$$
我们有了：
$$
\nabla_\theta V^\pi(s) =\sum_{a\in \mathcal{A}}\left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \sum_{s^{\prime}} P(s^\prime \vert s,a) \nabla_\theta V^\pi(s^\prime) \right)
$$
因为上面的等式中同时有 $V^\pi(s)$和 $V^\pi(s^\prime)$,我们可以考虑展开一下。先来做一些准备工作：
我们定义从状态 $s$ 开始在策略 $\pi_\theta$ 下经过 $k$ 个时间步到达状态 $x$ 的概率记为 $\rho^\pi(s \to x, k)$
-
k=0时，$\rho^\pi(s \to s, 0) = 1 $
-
k=1时，我们遍历在状态$s$时所有可能的动作然后进行一个累加： $ \rho^\pi(s \to s^\prime, k =1 ) = \sum_a \pi_\theta(a \vert s) P(s^\prime \vert s,a)$
-
如果目标是从状态$s $按照策略$\pi_\theta$经过$k+1$个时间步最终达到了$x$状态，我们可以看做从$s$状态经过$k$个时间步到了 $s^\prime \in \mathcal{S}$ 状态，然后再经过最后一个时间步到达了$x$状态那么我们可以这么计算：
$\rho^\pi(s \to x,k+1) = \sum_{s^\prime} \rho^\pi(s \to s^\prime,k)\rho^\pi(s^\prime \to x,1)$
递归展开$\nabla_\theta V^\pi(s)$
为了简洁，我们使用 $\phi(s)$ 来替代 $ \sum_{a \in \mathcal{A}} \nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a)$
于是有：
$$
\begin{aligned}
\nabla_\theta V^\pi(s) &=\sum_{a\in \mathcal{A}}\left(\nabla_\theta \pi_\theta(a\vert s)Q^\pi(s,a) + \pi_\theta(a \vert s) \sum_{s^{\prime}} P(s^\prime \vert s,a) \nabla_\theta V^\pi(s^\prime) \right)\
&= \phi(s) + \sum_a \pi_\theta(a \vert s)\sum_{s^{\prime}} P(s^\prime \vert s,a) \nabla_\theta V^\pi(s^\prime)\
&= \phi(s) + \sum_a\sum_{s^{\prime}} \pi_\theta(a \vert s) P(s^\prime \vert s,a) \nabla_\theta V^\pi(s^\prime)\
&= \phi(s)+ \sum_a \underbrace{\rho^\pi(s \to s^\prime, 1 )}
_
{
\sum_{s^{\prime}} \pi_\theta(a \vert s) P(s^\prime \vert s,a)
} \nabla_\theta V^\pi(s^\prime)\
&= \phi(s) + \sum_{s^{\prime}}\rho^\pi(s \to s^\prime, 1 )\left[\phi(s^\prime) + \sum_{s^{\prime\prime}}\rho^\pi(s^\prime \to s^{\prime\prime},1) \nabla_\theta V^\pi(s^{\prime\prime}) \right]\
&= \phi(s) + \sum_{s^{\prime}} \rho^\pi(s \to s^\prime, 1 )\phi(s^\prime) + \sum_{s^{\prime}} \rho^\pi(s \to s^\prime, 1 )\sum_{s^{\prime\prime}}\rho^\pi(s^\prime \to s^{\prime\prime},1) \nabla_\theta V^\pi(s^{\prime\prime}) \
&= \phi(s) + \sum_{s^{\prime}} \rho^\pi(s \to s^\prime, 1 )\phi(s^\prime) + \sum_{s^{\prime\prime}}\rho^\pi(s \to s^{\prime\prime},2) \nabla_\theta V^\pi(s^{\prime\prime}) \text{将s撇作为中间状态}\
&= \phi(s) + \sum_{s^{\prime}} \rho^\pi(s \to s^\prime, 1 )\phi(s^\prime) + \sum_{s^{\prime\prime}}\rho^\pi(s \to s^{\prime\prime},2)\phi(s^{\prime\prime}) + \sum_{s^{\prime\prime\prime}}\rho^\pi(s \to s^{\prime\prime\prime},2)\nabla_\theta V^\pi(s^{\prime\prime\prime})\
&= \dots \
&= \sum_{x\in \mathcal{S}}\sum_{k=0}^{\infty} \rho^\pi(s \to x,k)\phi(x)
\end{aligned}
$$
到此为止我们可以避免计算所谓的 $Q^\pi(s,a)$，然后我们将刚刚推导的式子代入到这里：
-
在周期环境下的情况
$$
\begin{aligned}
\nabla_\theta J(\theta) &= \nabla_\theta V^\pi(s_0)\
&= \sum_s \underbrace{\sum_{k=0}^{\infty} \rho^\pi(s_0 \to s,k)}_{\eta(s)}\phi(s)\
&= \sum_s {\eta(s)}\phi(s)\
&= (\sum_s \eta(s)) \sum_s \frac{\eta(s)}{\sum_s \eta(s)}\phi(s) \ \text{正则化} \eta(s)\text{使其成为一个概率分布}\
&\propto \sum_s \frac{\eta(s)}{\sum_s \eta(s)}\phi(s)\
&= \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a) \ 因为\sum_s \eta(s)是常数,d^\pi(s)=\frac{\eta(s)}{\sum_s \eta(s)}是平稳分布
\end{aligned}
$$
-
在连续环境下的证明情况，要用到上面所谓的差分状态-价值函数
$$
\begin{aligned}
\nabla_\theta V^\pi(s) \
&= \nabla_\theta(\sum_{a\in \mathcal{A}} \pi_\theta(a \vert s)Q^\pi(s,a))\
&= \phi(s) + \sum_{a\in \mathcal{A}}\pi_\theta(a \vert s)\nabla_\theta Q^\pi(s,a)\
&= \phi(s) + \sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\nabla_\theta \sum_{s^\prime,r} P(s^\prime,r \vert s, a)(r -r(\pi) + V^\pi(s^\prime))\right),展开Q^\pi\
&= \phi(s)+ \sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\left[-\nabla_\theta r(\pi) + \sum_{s^\prime,r} P(s^\prime,r \vert s, a)\nabla_\theta V^\pi(s^\prime) \right]\right),r(\pi)与s^\prime和r无关，可以提出来 \
&= \phi(s)+ \sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\left[-\nabla_\theta r(\pi) + \sum_{s^\prime} P(s^\prime \vert s, a)\nabla_\theta V^\pi(s^\prime) \right]\right) ,消掉一个r，因为P(s^\prime \vert s,a) =\sum_rP(s^\prime,r \vert s, a) \
&=-\nabla_\theta r(\pi)+\phi(s) +\sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\sum_{s^\prime} P(s^\prime \vert s, a)\nabla_\theta V^\pi(s^\prime) \right) \
&\Rightarrow \nabla_\theta r(\pi)= \phi(s)+\sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\sum_{s^\prime} P(s^\prime \vert s, a)\nabla_\theta V^\pi(s^\prime) \right)-\nabla_\theta V^\pi(s)
\end{aligned}
$$
于是我们平均回报形式的目标函数的梯度有：
$$
\begin{aligned}
\nabla_\theta J(\theta) &= \nabla_\theta r(\pi)\
&= \sum_s d^\pi(s) \left[\phi(s)+\sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\sum_{s^\prime} P(s^\prime \vert s, a)\nabla_\theta V^\pi(s^\prime) \right)-\nabla_\theta V^\pi(s)\right]\
&= \sum_s d^\pi(s)\phi(s) + \sum_s d^\pi(s)\sum_{a\in \mathcal{A}}\left(\pi_\theta(a \vert s)\sum_{s^\prime} P(s^\prime \vert s, a)\nabla_\theta V^\pi(s^\prime) \right)- \sum_s d^\pi(s)\nabla_\theta V^\pi(s),因为\sum_s d^\pi(s)=1，所以可以放在前面\
&= \sum_s d^\pi(s)\phi(s) + \sum_{s^\prime}\underbrace{\sum_s d^\pi(s)\sum_{a\in \mathcal{A}}\pi_\theta(a \vert s) P(s^\prime \vert s, a)}_
{d^\pi(s^\prime)}\nabla_\theta V^\pi(s^\prime) - \sum_s d^\pi(s)\nabla_\theta V^\pi(s)\
&= \sum_s d^\pi(s)\phi(s) + \sum_{s^\prime}d^\pi(s^\prime)\nabla_\theta V^\pi(s^\prime)- \sum_s d^\pi(s)\nabla_\theta V^\pi(s)\
&= \sum_s d^\pi(s)\phi(s)\
&= \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a)
&\propto \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a)
\end{aligned}
$$
对于平均值形式的目标函数有：
$$
\begin{aligned}
\nabla_\theta J(\theta) &= \frac{1}{1-\gamma} \nabla_\theta r(\pi)\
&= \frac{1}{1-\gamma}\sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a)\
&\propto \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a)
\end{aligned}
$$
至此，我们有：
$$
\begin{aligned}
\nabla_\theta J(\theta) &\propto \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s) Q^\pi (s,a)\
&= \sum_s d^\pi(s) \sum_a \pi_\theta(a \vert s) \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi_\theta(a \vert s)} Q^\pi (s,a)\
&= \mathbb{E}
_\pi[Q^\pi (s,a)\nabla
_\theta \ln\pi
_\theta(a \vert s) ]
\end{aligned}
$$
也就是上面简单推导中的形式了
2. Actor Critic On-Policy and Advantage Actor Critic On-policy
直观的来说：使用神经网络来近似价值函数 V，瞎子背着瘸子,仓库中我们实现的是A2C算法
-
就目前在网上看到的情况有以下几种 AC 架构
- 使用 Actor 来学习策略，Critic 学习 $Q_{\pi}(a,s)$，接受状态 s 作为输入(Policy Based),更新Actor使用
带权重的梯度上升。
- 使用 Actor 来学习策略，Critic 学习 $Q_{\pi}(a,s)$，接受状态 s，a 的 concatenation 作为输入(Value Based)，更新Actor直接使用Critic的输出的
Qvalue
- 与2相同，但是 s 是作为特征（features）从 actor 提取出来的，也就是说共享前面层的参数。
1. AC算法的训练流程
-
训练：
- 定义：使用神经网络来近似状态-价值函数： $V(s;\theta,\mathbf{w}) = \sum_a \pi(a\vert s;\theta) \cdot q(s,a;\mathbf{w})$.–使用Actor 来学习策略$\pi$ ，Critic 学习动作-状态价值函数$Q_{\pi}(s,a)$
- 目标：使 policy $\pi(a\vert s;\mathbf{\theta})$ 能够获取最大的回报，$q_{\pi}(s,a;\mathbf{w})$能够更精准的估计动作-状态价值函数
- 更新 $\theta$ 是为了让 $V(s;\theta,\mathbf{w})$最大，监督完全来自于价值网络-Critic
- 更新 $\mathbf{w}$ 是为了让 $q_{\pi}(s,a;\mathbf{w})$更加精准，监督完全是来自于环境给的奖励
-
步骤：
- 获取状态 $s_t$
- 通过 $\pi(\cdot \vert s_t;\mathbf{\theta}_t)$的分布进行一个随机采样，得到下一步的动作$ a_t$
- 执行动作，获取状态 $s_{t+1} $和奖励 $r_t$
- 使用 td error 来更新 $\mathbf{w}$
- 计算 $q(s_t,a_t;\mathbf{w})$和 $q(s_{t+1},a_{t+1};\mathbf{w})$
- 计算
td target : $y_t = r_t + \gamma \cdot q(s_{t+1},a_{t+1};\mathbf{w})$ ，显然 $y_t$ 比 $q(s_t,a_t;\mathbf{w})$更加可靠
- 计算二次距离(也就是
均方误差):$||y_t - q(s_t,a_t;\mathbf{w})||_2$，
- 进行梯度下降，让损失变得更小
- 使用 policy gradient（策略梯度）来更新 $\mathbf{\theta}$
- 定义梯度 $g(a,\mathbf{\theta})=\frac{\partial \log \pi(a\vert s;\mathbf{\theta}) }{\partial \mathbf{\theta}} q(s_t,a;\mathbf{w})$，而且上面PG算法中推导了：$\frac{\partial V(s;\mathbf{\theta},\mathbf{w}_t)}{\partial \mathbf{\theta}}=\mathbb{E}_A[\mathbf{g}(A,\mathbf{\theta})]$
- 由于无法求 $\mathbb{E}_A[\mathbf{g}(A,\mathbf{\theta})]$，我们只能够抽样进行
蒙特卡洛近似，所以直接使用 $g$ 来代替 $\mathbb{E}_A[\mathbf{g}(A,\mathbf{\theta})]$作为期望的近似,因为$a \sim \pi(\cdot \vert s_t;\mathbf{\theta}_t)$，所以$g$是$\mathbb{E}_A[\mathbf{g}(A,\mathbf{\theta})]$的一个无偏估计(unbaised estimation)
- 进行抽样，并计算 $g(a,\mathbf{\theta}t)$并进行梯度上升: $\mathbf{\theta}{t+1} = \mathbf{\theta}_t + \beta \cdot \mathbf{g}(a,\mathbf{\theta}_t)$，使期望越来越高。
注意：在实际代码中有的时候梯度是 $g(a,\mathbf{\theta})=\frac{\partial \log \pi(a\vert s;\mathbf{\theta}) }{\partial \mathbf{\theta}} q(s_t,a;\mathbf{w})$,有时候是 $g(a,\mathbf{\theta})=\frac{\partial \log \pi(a\vert s;\mathbf{\theta}) }{\partial \mathbf{\theta}} [\underbrace{r_t + \gamma \cdot v(s_{t+1};\mathbf{w})}_{td \ target} - v(s_t;\mathbf{w})]$，前者是不带baseline 后者带baseline，在本仓库中的代码就是后者，它的方差较小，收敛更快，后者的思路可以在下面看到。
-
Critic 在训练完毕之后就没有用辣！
2. 使用baseline:Actor Critic With Baseline (A2C)
-
它也是由两个网络组成：
策略网络(policy network)
$ \pi(a\vert s;\theta)$和
状态价值网络(state value function)
$ v(s;\mathbf{w})$，
状态价值网络是对状态价值函数的近似，它只依赖于状态$s_t$而并不向上面policy gradient算法中$Q_{\pi}(s_t,a_t)$依赖$s_t$和$a_t$，所以它更好训练。
-
训练流程
- 观测到transition $(s_t,a_t,r_t,s_{t+1})$
- 计算TD Target $y_t = r_t + \gamma \cdot v(s_{t+1};\mathbf{w})$
- 计算 TD Error $ \delta_t = v(s_t;\mathbf{w})- y_t$
- 执行梯度上升更新策略网络$ \pi(a\vert s;\theta)$： $\theta \gets \theta - \beta \cdot \delta_t \cdot \frac{\partial \ln \pi(a_t \vert s_t;\theta)}{\partial \theta}$
- 执行梯度下降来更新状态价值网络$ v(s;\mathbf{w})$:
$ \mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial v(s_t;\mathbf{w})}{\partial \mathbf{w}}$ (使用均方误差作为损失函数)
-
数学推导
-
$Q_{\pi}(s_t,a_t) = \mathbb{E}_
{S_{t+1},A_{t+1}}[R_t+ \gamma \cdot Q_{\pi}(S_{t+1},A_{t+1})]$
-
于是可以推导出来
$$
\begin{aligned}
Q_{\pi}(s_t,a_t) &= \mathbb{E}_
{S_{t+1},A_{t+1}}[R_t+ \gamma \cdot Q_{\pi}(S_{t+1},A_{t+1})]\
&= \mathbb{E}_
{S_{t+1}}\left[R_t + \gamma \cdot \mathbb{E}_
{A_{t+1}}[Q_{\pi}(S_{t+1},A_{t+1})]\right]\
&= \mathbb{E}_
{S_{t+1}}[R_t + \gamma \cdot V_{\pi}(S_{t+1})]
\end{aligned}
$$
-
因为$V_{\pi}(s_t)$的定义为$V_{\pi}(s_t) = \mathbb{E}{A{t}}[Q_{\pi}(s_{t},A_{t})]$，把$Q_{\pi}(s_{t},A_{t})$换进去得到
$$
\begin{aligned}
V_{\pi}(s_t) &= \mathbb{E}{A{t}}[Q_{\pi}(s_{t},A_{t})]\
&= \mathbb{E}{A{t}}\left [ \mathbb{E}_
{S_{t+1}}[R_t + \gamma \cdot V_{\pi}(S_{t+1})]
\right]\
&= \mathbb{E}{A{t},S_{t+1}}\left [R_t + \gamma \cdot V_{\pi}(S_{t+1})
\right]
\end{aligned}
$$
-
对$Q_{\pi}(s_t,a_t)=\mathbb{E}_
{S_{t+1}}[R_t + \gamma \cdot V_{\pi}(S_{t+1})]$做蒙特卡洛近似：
我们知道了$(s_t,a_t,r_t,s_{t+1})$,那么可以近似$Q_{\pi}(s_t,a_t)$:
$Q_{\pi}(s_t,a_t)\approx r_t + \gamma \cdot V_{\pi}(s_{t+1})$ (这是关键公式)
-
对$V_{\pi}(s_t)= \mathbb{E}_
{A_{t},S_{t+1}}\left [R_t + \gamma \cdot V_{\pi}(S_{t+1})
\right]$做近似
$V_{\pi}(s_t) \approx r_t + \gamma \cdot V_{\pi}(s_{t+1})$ , TD target就是这么得来的。
-
所以有两个近似:
$Q_{\pi}(s_t,a_t)\approx r_t + \gamma \cdot V_{\pi}(s_{t+1})$
$V_{\pi}(s_t) \approx r_t + \gamma \cdot V_{\pi}(s_{t+1})$
-
我们在策略梯度里面推导出了
$$
\mathbf{g}(a_t) = \left[\frac{\partial \ln \pi(a_t \vert s_t;\theta) }{\partial \theta} \ \left(Q_{\pi}(s_t,a_t) -V_\pi(s_t)\right)\right]
$$
我们称$(Q_{\pi}(s_t,a_t) -V_\pi(s_t))$为优势函数 Advantage function这就是A2C比AC多一个A的原因，于是我们用上面的东西做近似：
$$
\begin{aligned}
Q_{\pi}(s_t,a_t) -V_\pi(s_t) &\approx r_t + \gamma \cdot V_{\pi}(s_{t+1}) - V_\pi(s_t)\
&\approx r_t + \gamma \cdot v(s_{t+1};\mathbf{w}) - v(s_t;\mathbf{w}) \ \text{使用神经网络进行近似}
\end{aligned}
$$
把$ r_t + \gamma \cdot v(s_{t+1};\mathbf{w})$ 称为$y_t$
-
使用近似的策略梯度进行梯度上升，来更新策略网络：
$$
\theta \gets \theta + \beta \cdot \frac{\partial \ln \pi(a_t \vert s_t;\theta)}{\partial \theta}\left(y_t - v(s_t;\mathbf{w})\right)
$$
-
使用TD 算法更新价值网络
$V_{\pi}(s_t) \approx r_t + \gamma \cdot V_{\pi}(s_{t+1})$，用神经网络进行近似得到：
$v(s_t;\mathbf{w}) \approx r_t + \gamma \cdot v(s_{t+1};\mathbf{w}) $
TD target $y_t = r_t + \gamma \cdot v(s_{t+1};\mathbf{w})$
TD算法鼓励$v(s_t;\mathbf{w})$去接近TD target，于是我们将它们相减得到$\delta_t = v(s_t;\mathbf{w}) - y_t$
执行梯度下降：
$$ \mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial v(s_t;\mathbf{w})}{\partial \mathbf{w}}$$
-
对A2C的直观解释
-
我们有近似梯度：
$$
\mathbf{g}(a_t)=\frac{\partial \ln \pi(a_t\vert s_t;\theta)}{\partial \theta} \cdot \underbrace{(r_t + \gamma \cdot v(s_{t+1};\mathbf{w})- v(s_t;\mathbf{w}))}_{\text{critic做出的评估}}
$$
-
$(r_t + \gamma \cdot v(s_{t+1};\mathbf{w})- v(s_t;\mathbf{w}))$如何评价动作的好坏？
$v(s_t;\mathbf{w})$是$\mathbb{E}[U_t\vert s_t]$的近</https:>
README 内容过长，已截取前 64 KB。完整内容请前往 GitHub 仓库查看。
评论