目录
白话强化学习笔记
Q与V
-
Q：评估
动作
的价值。它代表了智能体选择这个
动作
后，一直到最终状态奖励总和的期望。 -
V：评估
状态
的价值。它代表了智能体在这个
状态
下，一直到最终状态的奖励总和的期望。 - VQVQVQVQ：状态—动作—状态—动作…
下面讲的都是从后向前更新
从Q到V
从动作反推状态
一个状态的V值，就是这个状态下的所有动作的Q值，在策略下的期望
。
v
π
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
q
π
(
s
,
a
)
v_{\pi}(s)=\sum_{a\in{A}}\pi(a|s)q_{\pi}(s,a)
v
π
(
s
)
=
a
∈
A
∑
π
(
a
∣
s
)
q
π
(
s
,
a
)
-
vπ
(
s
)
v_{\pi}(s)
v
π
(
s
)
：V值 -
π(
a
∣
s
)
\pi(a|s)
π
(
a
∣
s
)
：策略 -
qπ
(
s
,
a
)
q_{\pi}(s,a)
q
π
(
s
,
a
)
：Q值
从V到Q
从状态反推动作
q
π
(
s
,
a
)
=
R
s
a
+
γ
∑
s
′
P
s
s
,
a
v
π
(
s
′
)
q_{\pi}(s,a)=R_s^a+\gamma\sum_{s’}P_{ss^,}^av_{\pi}(s’)
q
π
(
s
,
a
)
=
R
s
a
+
γ
s
′
∑
P
s
s
,
a
v
π
(
s
′
)
-
qπ
(
s
,
a
)
q_{\pi}(s,a)
q
π
(
s
,
a
)
：Q值 -
Rs
a
R_s^a
R
s
a
：奖励 -
γ\gamma
γ
：折扣率 -
Ps
s
,
a
P_{ss^,}^a
P
s
s
,
a
：状态转移概率 -
vπ
(
s
,
)
v_{\pi}(s^,)
v
π
(
s
,
)
：V值 - 这里不需要关注策略，这里是环境的状态转移概率决定的。
-
当我们选择A，并转移到新的状态时，就能获得奖励，我们必须把这个
奖励也算上！
从V到V
把公式代进去就可以了。
v
π
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
(
R
s
a
+
γ
∑
s
,
∈
S
P
s
s
′
a
v
π
(
s
′
)
)
v_{\pi}(s)=\sum_{a\in{A}}\pi(a|s)(R_s^a+\gamma\sum_{s^,\in{S}}P_{ss’}^av_{\pi}(s’))
v
π
(
s
)
=
a
∈
A
∑
π
(
a
∣
s
)
(
R
s
a
+
γ
s
,
∈
S
∑
P
s
s
′
a
v
π
(
s
′
))
小结
- V就是子节点的Q的期望！但要注意V值和策略相关。
- Q就是子节点的V的期望！但要注意，记得把R计算在内。
蒙地卡罗
算法
- （小猴子走迷宫）
- 根据策略往前走，一直走到最后，期间什么都不用算，需要记录每一个状态转移，获得多少奖励r即可
-
从终点往回走，一边走一边计算G值。G值等于上一个状态的G值(记作G’),乘以一定的折扣
γ\gamma
γ
，再加上r - 进行多次试验后，有可能会经过某个状态多次，通过回溯，也会有多个G值；
- 平均每个状态的G值，这就是我们需要求的V值。
但蒙地卡罗有一个比较大的缺点，就是每一次游戏，都需要先从头走到尾，再进行回溯更新。如果最终状态很难达到，那小猴子可能每一次都要转很久很久才能更新一次G值。
平均香蕉
有两条长度分别为A，B的香蕉(并假设：A>B)。如果我要知道他们平均有多长。
我只需要把A切成和B长；然后把多出来的那一节，再切一半，接到B就可以了。
这时候，我们称那条加长了的B香蕉为平均香蕉。
V
n
e
w
=
V
o
l
d
−
G
N
+
V
o
l
d
V_{new}=\frac{V_{old}-G}{N}+V_{old}
V
n
e
w
=
N
V
o
l
d
−
G
+
V
o
l
d
甚至可以不用记录N，把
1
N
\frac{1}{N}
N
1
设置成一个固定的数（超参数），这个值就是学习率。
也就是说，每一次G都会引导V增加一些或者减少一些，而这个V值慢慢就会接近真正的V值
。
蒙地卡罗MC更新公式
V
(
S
t
)
←
V
(
S
t
)
+
α
[
G
t
−
V
(
S
t
)
]
V(S_t){\leftarrow}V(S_t)+\alpha[G_t-V(S_t)]
V
(
S
t
)
←
V
(
S
t
)
+
α
[
G
t
−
V
(
S
t
)]
-
Gt
G_t
G
t
：新来的G -
右边的
V(
S
t
)
V(S_t)
V
(
S
t
)
：原来的平均值
蒙地卡罗有一些缺点：
- 相对动态规划，会有点不那么准。因为蒙地卡罗每一次的路径都是不一样的。
- 如果环境的状态空间非常大，或者最终状态只有非常小的概率达到。那么蒙地卡罗算法将会很难处理。
时序差分TD估算状态V值
算法流程
- 小猴子每走1步，看一下这个路口的V值，还有获得的奖励r
- 回到原来的路口，把刚刚看到的V值和奖励r进行运算，估算出V值
可以把TD看成是这样一种情况：从A状态，经过1步，到B状态。什么都不管就当B状态是最终状态了。
但B状态本身就带有一定的价值，也就是V值。其意义就是从B状态到最终状态的总价值期望。
但是有一个问题，一开始B状态也是没有值的，怎么办：多走几次，整个系统就会慢慢建立起来了。
更新公式
V
(
S
t
)
←
V
(
S
t
)
+
α
[
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
]
V(S_t){\leftarrow}V(S_t)+\alpha[R_{t+1}+{\gamma}V(S_{t+1})-V(S_t)]
V
(
S
t
)
←
V
(
S
t
)
+
α
[
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)]
与MC的区别：
-
MC公式里更新目标是
Gt
G_t
G
t
。 -
TD公式里更新目标换成
Rt
+
1
+
γ
V
(
S
t
+
1
)
R_{t+1}+{\gamma}V(S_{t+1})
R
t
+
1
+
γ
V
(
S
t
+
1
)
。
TD更厉害的是，在很多时候，并不需要一直到最后，可以先用后面的估算，然后调整当前状态。
Qlearning
TD之于Q值估算
-
问题转换
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
的意义是，在
St
+
1
S_{t+1}
S
t
+
1
到最终状态获得的奖励期望值。
Q(
S
t
,
A
t
)
Q(S_t,A_t)
Q
(
S
t
,
A
t
)
的意义是，在
Q(
S
t
,
A
t
)
Q(S_t,A_t)
Q
(
S
t
,
A
t
)
到最终状态获得的奖励期望值。所以可以把
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
看成是下山途中的一个路牌，这个路牌告诉我们下山到底还有多远，然后加上R这一段路，就知道
Q(
S
t
,
A
t
)
Q(S_t,A_t)
Q
(
S
t
,
A
t
)
离山脚有多长的路。但在实际操作的时候，会有一个问题。 在这里我们要估算两个东西，一个是V值，一个是Q值。
人们想出的办法就是，
用下一个动作的Q值，代替V值
。（这边的解释去看看
博客
的图）因为从状态
St
+
1
S_{t+1}
S
t
+
1
到动作
At
+
1
A_{t+1}
A
t
+
1
之间没有奖励反馈，所以我们直接用
At
+
1
A_{t+1}
A
t
+
1
的Q值，代替
St
+
1
S_{t+1}
S
t
+
1
的V值。 -
麻烦的解决
麻烦来了：关键是马可洛夫链不是链，是树！
在
St
+
1
S_{t+1}
S
t
+
1
下，可能有很多动作
At
+
1
A_{t+1}
A
t
+
1
。不同动作的Q值自然是不同的。 所以
Q(
S
t
+
1
,
A
t
+
1
)
Q(S_{t+1},A_{t+1})
Q
(
S
t
+
1
,
A
t
+
1
)
并不能等价于
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
。虽然不相等，但不代表不能用其中一个来代表
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
。 -
采用方法
在
相同策略
下产生的动作
At
+
1
A_{t+1}
A
t
+
1
。这就是SARSA。选择能够产生最大Q值的动作
At
+
1
A_{t+1}
A
t
+
1
。这就是Qlearning。
SARSA
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
Q
(
S
′
,
A
′
)
−
Q
(
S
,
A
)
]
Q(S,A){\leftarrow}Q(S,A)+\alpha[R+{\gamma}Q(S’,A’)-Q(S,A)]
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
Q
(
S
′
,
A
′
)
−
Q
(
S
,
A
)]
其实SARSA和前面说的TD估算V值几乎一模一样，只不过挪了一下，从V改成Q了。
注意，这里的
A
t
+
1
A_{t+1}
A
t
+
1
是在同一策略产生的。也就是说，
S
t
S_t
S
t
选
A
t
A_t
A
t
的策略和
S
t
+
1
S_{t+1}
S
t
+
1
选
A
t
+
1
A_{t+1}
A
t
+
1
是同一个策略。
这也是SARSA和Qlearning的唯一区别
。
Qlearning
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
max
α
Q
(
S
′
,
A
′
)
−
Q
(
S
,
A
)
]
Q(S,A){\leftarrow} Q(S,A)+\alpha[R+{\gamma} \mathop{\max}\limits_{\alpha} Q(S’,A’)-Q(S,A)]
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
α
max
Q
(
S
′
,
A
′
)
−
Q
(
S
,
A
)]
道理其实也很简单：因为需要找的是能获得最多奖励的动作，Q值就代表我们能够获得今后奖励的期望值。所以我们只会选择Q值最大的，也只有最大Q值能够代表V值。
总结
- Qlearning和SARSA都是基于TD的。不过在之前的介绍中，用TD估算状态的V值。而Qlearning和SARSA估算的是动作的Q值。
-
Qlearning和SARSA的核心原理，是用下一个状态
St
+
1
S_{t+1}
S
t
+
1
的V值，估算Q值。 -
既要估算Q值，又要估算V值会显得比较麻烦。所以用下一状态下的某一个动作的Q值，来代表
St
+
1
S_{t+1}
S
t
+
1
的V值。 -
Qlearning和SARSA唯一的不同，就是用什么动作的Q值替代
St
+
1
S_{t+1}
S
t
+
1
的V值。 -
SARSA 选择的是在
St
S_t
S
t
同一个策略产生的动作。Qlearning 选择的是能够产生最大的Q值的动作。
Qlearning算法也有很大的局限性，无论现实世界还是游戏世界，很多时候状态都是连续的，像表格这种方式，只能解决状态有限且离散的任务。
DQN算法应运而生！用深度网络，解决了连续状态的问题。
DQN
Deep network + Qlearning = DQN
-
Qlearning中的Qtable在遇到
连续
的情况下就没办法了。但是函数就允许
连续
状态的表示。于是神经网络就派上用场了。 -
其实Qlearning和DQN并没有根本的区别。只是DQN用神经网络，也就是一个函数替代了原来Qtable而已。
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
max
α
Q
(
S
′
,
a
)
−
Q
(
S
,
A
)
]
Q(S,A){\leftarrow} Q(S,A)+\alpha[R+{\gamma} \mathop{\max}\limits_{\alpha} Q(S’,a)-Q(S,A)]
Q
(
S
,
A
)
←
Q
(
S
,
A
)
+
α
[
R
+
γ
α
max
Q
(
S
′
,
a
)
−
Q
(
S
,
A
)]
算法流程
假设需要更新当前状态
S
t
S_t
S
t
下的某动作A的Q值：
Q
(
S
,
A
)
Q(S,A)
Q
(
S
,
A
)
，可以：
-
执行A，往前一步，到达
St
+
1
S_{t+1}
S
t
+
1
； -
把
St
+
1
S_{t+1}
S
t
+
1
输入Q网络，计算
St
+
1
S_{t+1}
S
t
+
1
下所有动作的Q值； - 获得最大的Q值加上奖励R作为更新目标；
-
计算损失：logits（
Q(
S
,
A
)
Q(S,A)
Q
(
S
,
A
)
），labels（
max
Q
(
S
t
+
1
)
+
R
\mathop{\max}Q(S_{t+1})+R
max
Q
(
S
t
+
1
)
+
R
） - 用loss更新Q网络。
总结
- 其实DQN就是Qlearning扔掉Qtable，换上深度神经网络。
- 解决连续型问题，如果表格不能表示，就用函数，而最好的函数就是深度神经网络。
- 和有监督学习不同，深度强化学习中，需要自己找更新目标。通常在马尔科夫链体系下，两个相邻状态状态差一个奖励r经常能被利用。
代码
- Epsilon-greedy用大白话说就是：如果随机出来的值小于Epsilon这个门槛，就用greedy算法吧！如果大于，就随机。（跟Qlearning中说到的noisy-greedy差不多，都是让其有一个随机性，而不至于都是最大的Q）
-
建议看
博客
。
Double DQN与Dueling DQN
经验回放（Experience replay）
-
强化学习中，相比于网络训练的速度，数据采集总是太慢，因为采集是在游戏过程中的。
-
如果能把互动过程中的数据，都存起来，全部存在一个叫回放缓存的地方（replay buffer），当数据最够多的时候（如达到一个batch），再训练网络，那么就快很多了。
-
训练之后继续进行游戏，继续把新产生的数据添加到回放缓存里…
-
就这样，每次都随机抽出一个batch大小的数据训练智能体。这样，以前产生的数据同样也能用来训练数据了，效率自然更高。
固定Q目标（Fixed Q-targets）
-
DQN目标：
γmax
Q
(
S
′
)
+
r
\gamma\mathop{\max}Q(S’)+r
γ
max
Q
(
S
′
)
+
r
。 -
目标本身包含一个Q网络，这样理论上没有问题，但是会造成Q网络的学习效率比较低，而且不稳定。
-
如果把训练神经网络比喻成射击游戏，在target中有Q网络的话，就相当于在射击一个移动靶，因为每次射击一次，靶就会挪动一次。相比起固定的靶，无疑加上了训练的难度。
-
那怎么解决这个问题呢？既然现在是移动靶，那么就把它弄成是固定的靶，先停止10秒。10后挪动靶再打新的靶。这就是Fixed Q-targets的思路。
在实做的时候，其实和原来的DQN一样，唯一不同点是，用两个Q网络：
-
原来的Q网络，用于估算
Q(
s
)
Q(s)
Q
(
s
)
； - targetQ网络, targetQ自己并不会更新，也就是它在更新的过程中是固定的，用于计算更新目标。
-
y=
r
+
γ
max
(
t
a
r
g
e
t
Q
(
S
′
)
)
y=r+\gamma\mathop{\max}(targetQ(S’))
y
=
r
+
γ
max
(
t
a
r
g
e
tQ
(
S
′
))
。 - 进行N次更新后，就把新Q的参数赋值给旧Q。
Double DQN
DQN有一个显著的问题，就是DQN估计的Q值往往会偏大。这是由于Q值是以下一个
s
′
s’
s
′
的Q值的最大值来估算的，但下一个state的Q值也是一个估算值，也依赖它的下一个state的Q值…，这就导致了Q值往往会有偏大的的情况出现。两个办法可以缓解：
- 第一种：形象说，如果只有一个Q网络，它经常吹牛。那就用两个Q网络，因为两个Q网络的参数有差别，所以对于同一个动作的评估也会有少许不同。选取评估出来较小的值来计算目标。这样就能避免Q网络吹牛的情况发生。
-
第二种：也需要用到两个Q网络。Q1网络
推荐
能够获得最大Q值的动作；Q2网络计算这个动作在Q2网络中的Q值。
恰好，如果用上Fixed Q-targets，不就是有两个Q网络了吗？
所以可以看到，这个优化在DQN上很容易实现。这就是doubleDQN和DQN的唯一的变化。
以上说到的经验回放等建议看原
博客
和[代码]！！
Dueling DQN
建议直接看
博客
。
策略梯度（Policy Gradient）
- DQN=TD+神经网络
- PG=蒙地卡罗+神经网络
在神经网络出现之前，当遇到非常复杂的情况时，很难描述遇到每一种状态应该如何应对。但现在有了神经网络这么强大的武器，就可以用一个magic函数直接代替想要努力描述的规则。
如果智能体的动作是对的，那么就让这个动作获得更多被选择的几率；相反，如果这个动作是错的，那么这个动作被选择的几率将会减少。
问题在于，怎么衡量对和错呢？PG的想法非常简单粗暴：蒙地卡罗的G值！（还记得小猴子吗？）
直观感受PG算法
假设从某个state出发，可以采用三个动作，一开始智能体对动作好坏一无所知，假如采用平均策略
[33%,33%,33%]
。
-
选择动作A，达到最终状态后回溯，得到
G=
1
G=1
G
=
1
； -
让A概率，BC降低，得到
[50%,25%,25%]
； -
选择B，计算得到
G=
−
1
G=-1
G
=
−
1
； -
对B的评价较低，所以降低B概率，得到
[55%,15%,30%]
； -
最后随机到C，得到
G=
5
G=5
G
=
5
； -
C比A还要多得多。因此这一次更新，C的概率需要大幅提升，相对地，AB概率降低，得到
[20%,5%,75%]
。
Actor-Critic
PG算法用到蒙地卡罗，需要完成整个游戏过程，太慢了，改成TD快一点。
Actor-Critic其实用了两个网络，两个网络有一个共同点，输入状态S：
- 一个输出策略，负责选择动作，这个网络叫Actor；
- 一个负责计算每个动作的分数，这个网络叫Critic。
Actor在台上跳舞，一开始舞姿并不好看，Critic根据Actor的舞姿打分。Actor通过Critic给出的分数，去学习：如果Critic给的分数高，那么Actor会调整这个动作的输出概率；相反，如果Critic给的分数低，那么就减少这个动作输出的概率。
TD-error
-
为了避免
正数陷阱
，希望Actor的更新权重有正有负。因此，把Q值减去他们的均值V。有：
Q(
s
,
a
)
−
V
(
s
)
Q(s,a)-V(s)
Q
(
s
,
a
)
−
V
(
s
)
。（这步理解很关键） -
为了避免需要预估V值和Q值，我们希望把Q和V统一。
Q(
s
,
a
)
=
γ
V
(
s
′
)
+
r
Q(s,a) = \gamma V(s’) + r
Q
(
s
,
a
)
=
γV
(
s
′
)
+
r
。 -
所以：
TD
−
e
r
r
o
r
=
γ
V
(
s
′
)
+
r
−
V
(
s
)
TD-error=\gamma V(s’) + r-V(s)
T
D
−
error
=
γV
(
s
′
)
+
r
−
V
(
s
)
。 - TD-error就是Actor更新策略时，带权重更新中的权重值。
- 现在Critic不再需要预估Q，而是预估V。而根据马可洛夫链所学，我们知道TD-error就是Critic网络需要的loss，也就是说，Critic函数需要最小化TD-error。
- （主要看看代码理解）
PPO
AC问题一：离散到连续
PPO是基于AC架构的，也就是说，PPO也有两个网络，分别是Actor和Critic，这是因为AC架构有一个好处。这个好处就是解决了连续动作空间的问题。
- 离散动作：就像一个个的按钮，按一个按钮就能智能体就做一个动作。就像在CartPole游戏里的智能体，只有0,1两个动作分别代表向左走，向右走。
- 连续动作：相当于这些按钮不但有开关的概念，而且还有力度大小的概念。就像开车，不但是前进后退转弯，并且要控制油门踩多深，刹车踩多少的，转弯时候转向转多少的问题。
但这就有个问题，用神经网络预测输出的策略是一个固定的shape，而不是连续的。那又什么办法可以表示连续型的概率呢？
先假定策略分布函数服从一个特殊的分布，这个特殊的分布可以用一两个参数表示它的图像。
正态分布就是这样一个分布，他只需要两个参数，就可以表示了。
AC问题二：数据浪费
AC产生的数据，只能进行1次更新，更新完就只能丢掉，等待下一次跑游戏的数据。这可是天大的浪费。
那为什么只能用一次呢，像DQN也可以用经验回放，把以前的数据存起来，更新之后用？AC为什么就不行呢？
先清楚以下概念：
- 行为策略：不是当前策略，用于产出数据
- 目标策略：会更新的策略，需要被优化的策略
-
如果两个策略同一个策略，那么称为
在线策略（On Policy）
。 -
如果两个策略不是同一个策略，那么称为
离线策略（Off Policy）
。
举例：
- 如果在智能体和环境进行互动时产生的数据打上一个标记。标记这是第几版本的策略产生的数据，例如1，2… 10
- 现在智能体用的策略 10，需要更新到11。
- 如果算法只能用 10版本的产生的数据来更新，那么这个就是在线策略；如果算法允许用其他版本的数据来更新，那么就是离线策略。
- PG，就是一个在线策略。因为PG用于产生数据的策略（行为策略），和需要更新的策略（目标策略）是一致。
- DQN则是一个离线策略。智能体在环境互动一定次数，获得数据。用这些数据优化策略后，继续跑新的数据。但老版本的数据仍然是可以用的。也就是说，产生数据的策略，和要更新的目标策略不是同一个策略。
但为什么PG和AC中的Actor更新，就不能像DQN一样，把数据存起来，更新多次呢？
答案是在一定条件下，能。PPO做的工作就是这个。在了解在什么条件下可以的时候，需要先了解一下，为什么不能。看看
博客
吧。
Important-sampling
PPO通过**重要性采样技术（Important-sampling）**做到离线更新策略。
N步更新
把之前的TD叫做TD(0)，而N步更新为TD(n)。可以看成TD(0)其实是TD(n)的一种特殊情况。