Q-Learning基本思想
文章目录
Q-learning
Q-learning 是 value-based 的方法，在这种方法中我们不是要训练一个 policy，而是要训练一个critic网络。critic 并不直接采取行为，只是对现有的 actor Π，评价它的好坏。V函数的意思是当使用actor Π时，计算从看到状态s开始一直到当前episode结束的reward。
Value-Fuction
critic 给出了一个 value function
V
π
(
s
)
V^\pi(s)
Vπ(s)，代表在遇到游戏的某个 state 后，采取策略为
π
\pi
π的actor 一直玩到游戏结束，所能得到的 reward 之和。
V
π
(
s
)
V^\pi(s)
Vπ(s)（即critic）的输入是某个state，输出是一个scalar标量。上图游戏画面中左边的
V
π
(
s
)
V^\pi(s)
Vπ(s) 很大，因为当前怪物比较多，防护罩也没被摧毁，从此时玩到游戏结束得到的 reward 就会比较多；而相对的右边的
V
π
(
s
)
V^\pi(s)
Vπ(s) 就比较小。综上 critic 的输出取决于两点：
state，这个就是左右图对比，刚才说过了
actor 的策略
π
\pi
π，如果是个很弱的actor即便左图可能也得到很低的reward。
怎么计算 V π ( s ) V^\pi(s) Vπ(s)呢？
计算 V π ( s ) V^\pi(s) Vπ(s)的2种方式：
1、Monte-Carlo (MC) based approach ：
将
S
a
S_a
Sa作为
V
π
(
s
)
V^\pi(s)
Vπ(s)的输入最终输出
V
π
(
S
a
)
V^\pi(S_a)
Vπ(Sa)，而实际上应该得到的cumulative reward是
G
a
G_a
Ga。这其实和 regression problem 很相似，因为我们的目标就是通过训练让
V
π
(
S
a
)
V^\pi(S_a)
Vπ(Sa) 越来越接近
G
a
G_a
Ga ，即理想情况下
V
π
(
S
a
)
=
G
a
V^\pi(S_a) =G_a
Vπ(Sa)=Ga(这里为了方便，假设学习率
α
\alpha
α为1，原始的公式为
V
(
S
t
)
=
V
(
S
t
)
+
α
(
G
t
−
V
(
s
t
)
)
)
V(S_t) = V(S_t) + \alpha (G_t-V(s_t)))
V(St)=V(St)+α(Gt−V(st)))。
注意： V π ( s ) V^\pi(s) Vπ(s)是一个网络，因为在游戏中，不可能所有的image都看过，所以将 V π ( s ) V^\pi(s) Vπ(s)做成网络来提高泛化性。
2、Temporal-difference (TD) approach
MC based的方法要求遇到
S
a
S_a
Sa后把游戏玩到结束，如果游戏太长的话，那就可能收集不到多少数据去让网络去拟合
G
a
G_a
Ga。
而 TD 只需要从 S t S_t St 玩到 S t + 1 S_{t+1} St+1 就行，因此只需要算 V π ( S t ) = V π ( S t + 1 ) + r t V^\pi(S_t) = V^\pi(S_{t+1}) + r_t Vπ(St)=Vπ(St+1)+rt (这里为了方便，假设学习率 α \alpha α和衰减系数 γ \gamma γ都为1，原始的公式为 V ( S t ) = V ( S t ) + α ( r t + γ V ( S t + 1 ) − V ( s t ) ) ) V(S_t) = V(S_t) + \alpha (r_t+\gamma V(S_{t+1})-V(s_t))) V(St)=V(St)+α(rt+γV(St+1)−V(st)))。
那么 V π ( S t + 1 ) − V π ( S t ) V^\pi(S_t+1) - V^\pi(S_t) Vπ(St+1)−Vπ(St) 应该要越接近 r t r_t rt才是正确的结果，所以将网络往这个方向去train，就可以把这个function训练出来。
MC v.s. TD ：
MC 方法的问题在于最后得到的
G
a
G_a
Ga 的方差很大（
G
a
G_a
Ga 是 在遇到
S
a
S_a
Sa 的情况下使用策略
π
\pi
π的actor一直玩游戏直到结束得到的实际 reward，是一个随机变量，因为游戏是有随机性的，所以每一次得到
G
a
G_a
Ga 是不一样的）。
假设 G a G_a Ga 是k步 reward 的求和，而根据公式 V a r [ k X ] = k 2 V a r [ X ] Var[kX]=k^2Var[X] Var[kX]=k2Var[X]，最终会相差 k 2 k^2 k2倍。所以最后 G a G_a Ga 的方差很大，即每次算出来的 V π ( S a ) V^\pi(S_a) Vπ(Sa) 都会相差很多。
而用 TD base 中有随机性的部分是 r，它的方差比较小。但 TD 的问题在于
V
π
(
S
t
+
1
)
V^\pi(S_{t+1})
Vπ(St+1) 可能不准确。可以看出，同一个actor，用MC based和TD，算出来的结果是不一样的，两种结果没有绝对的正确与否。
其中，在第一个episode中， S a S_a Sa出现后 S b S_b Sb的reward变为0。
在Monte-Carlo方法中，就会认为 S a S_a Sa是一个不好的state，才导致后来的 S b S_b Sb的reward变为0，所以 V π ( S a ) V^\pi(S_a) Vπ(Sa) 为0.
而TD方法中， 会认为 S a S_a Sa 后 S b S_b Sb 得到 reward 为 0 只是一个巧合，与 S a S_a Sa 无关。大部分情况下 S b S_b Sb 还是会得到 3/4 的 reward，所以认为 V π ( S a ) V^\pi(S_a) Vπ(Sa) 为3/4。（因为 V π ( S a ) = V π ( S b ) + r a V^\pi(S_a) = V^\pi(S_b) + r_a Vπ(Sa)=Vπ(Sb)+ra）
Q-function:
Q
π
(
s
,
a
)
Q^\pi(s,a)
Qπ(s,a)的输入是一个
(
s
,
a
)
(s, a)
(s,a) 的 组合，然后输出一个cumulated reward的期望值。这里的cumulated reward指的是在state s下强制采取 action a（不管这个actor认为在state s下采取action a是不是好的，都强制采取a），然后用这个actor
π
\pi
π 一直玩到游戏结束所得到的cumulated reward。
以上是Q function的两种常见的写法。如果action可以穷举，则可以使用右边的写法；否则，使用左边的写法。
critic 看上去只能评价某个 action 的好坏，但是实际上可以直接用它来做 reinforcement learning。方法是只要学到一个
π
\pi
π 的 Q function
Q
π
(
s
,
a
)
Q^\pi(s,a)
Qπ(s,a) ，就能有办法找到一个更好的 actor
π
′
\pi'
π′，这样就能不断更新policy
π
\pi
π 。
什么叫 π ′ \pi' π′ 比 π 好呢？
就是说面对所有 state s 时，使用策略
π
′
\pi'
π′ 得到的 value 一定比使用策略
π
\pi
π 得到的Q value 大，即：
V
π
′
(
s
)
⩾
V
π
(
s
)
V^{\pi'}(s)\geqslant V^\pi(s)
Vπ′(s)⩾Vπ(s)
找 π ′ \pi' π′ 的方法是，对于已经学到的 Q function Q π ( s , a ) Q^\pi(s,a) Qπ(s,a)，在某个给定的 state 下，分别带入可能的 action，看看哪一个 action 使得Q value最大，把使得函数值Q value最大的 a，作为以后面对该 state 时采取的 action。
下图证明了
V
π
′
(
s
)
⩾
V
π
(
s
)
V^{\pi'}(s)\geqslant V^\pi(s)
Vπ′(s)⩾Vπ(s)：
Q-Learning使用技巧：
技巧1：使用Target network
Q-function的训练，参考了TD的方法，即
Q
π
(
s
t
,
a
t
)
=
r
t
+
Q
π
(
s
t
+
1
,
π
(
s
t
+
1
)
)
Q^\pi(s_t,a_t) = r_t + Q^\pi(s_{t+1},\pi(s_{t+1}))
Qπ(st,at)=rt+Qπ(st+1,π(st+1))。
现在以 s t s_t st、 a t a_t at作为输入，则输出的结果 Q π ( s t , a t ) Q^\pi(s_t,a_t) Qπ(st,at)，由上图可以得出，这个结果应该尽可能接近以 s t + 1 s_{t+1} st+1、 a t + 1 a_{t+1} at+1作为输入，则输出的结果 Q π ( s t + 1 , π ( s t + 1 ) ) Q^\pi(s_{t+1},\pi(s_{t+1})) Qπ(st+1,π(st+1))再加上 r t r_t rt的结果。
也是一个类似回归的问题，但是这里不同于前面的Monte-Carlo (MC) based approach和Temporal-difference (TD) approach的回归问题，这里的 Q π ( s t + 1 , π ( s t + 1 ) ) Q^\pi(s_{t+1},\pi(s_{t+1})) Qπ(st+1,π(st+1))是一直在变化的，即 Q π ( s t , a t ) Q^\pi(s_t,a_t) Qπ(st,at)要去拟合的目标，其实是一直在变化，这就对训练产生很大的干扰。
所以
1.将以
s
t
+
1
s_{t+1}
st+1、
a
t
+
1
a_{t+1}
at+1作为输入的网络（也叫Target network）固定住，这样
r
t
+
Q
π
(
s
t
+
1
,
π
(
s
t
+
1
)
)
r_t + Q^\pi(s_{t+1},\pi(s_{t+1}))
rt+Qπ(st+1,π(st+1))也变成一个固定的值，然后让以
s
t
s_t
st、
a
t
a_t
at作为输入的网络去拟合这个固定的值。
2. 经过N次训练后，将左边的网络的参数覆盖掉Target network，形成新的Target network
重复1、2的步骤一直训练下去。
技巧2：使用exploration
Q-learning方法是根据查表来估值的，只有在状态
s
t
s_t
st执行过动作
a
t
a_t
at之后，我们才能估得出
Q
π
(
s
t
,
a
t
)
Q^\pi(s_t,a_t)
Qπ(st,at)。即便是使用DQN（就是说将Q-function改为一个network，把查表的过程变成network的输入输出）减缓了这个问题，但也可能存在一些状态
s
t
s_t
st没执行过动作
a
t
a_t
at，没办法估出
Q
π
(
s
t
,
a
t
)
Q^\pi(s_t,a_t)
Qπ(st,at)。现在在状态s下，都没有采取过action
a
1
a_1
a1、
a
2
a_2
a2、
a
3
a_3
a3，所以所有的Q-value都为0。接下来与环境的互动中，sample到在状态s下，采取动作
a
2
a_2
a2，会使得Q-value从0变成1。
由
可以知道，接下去在状态s下就会一直采取动作
a
2
a_2
a2，而不会去尝试可能未来会获得更大reward的
a
1
a_1
a1、
a
3
a_3
a3。
为了解决这个问题可以使用以下两种方法：
1、Epsilon Greedy
假设
ϵ
\epsilon
ϵ为0.3，那就会有0.7（1-0.3）的几率会使用以往的经验去执行动作，而剩下0.3的概率随机去试探新的动作。
ϵ \epsilon ϵ会随着训练的进行不断减少，就是说在一开始的时候 ϵ \epsilon ϵ的值会大一点，因为还不知道哪个action是好的，所以还要提高探索（exploration）的次数。随着训练的进行，开始知道哪些action是好的哪些是不好的，就可以减少探索（exploration）的次数。
2、Boltzmann Exploration
因为Q-value可能有正有负，所以先取exp全部转成正的。然后除以分母，做Normalization。
这样就将所有动作的Q value转化为概率，概率的大小和Q value的大小有关。然后通过概率的大小去选择不同动作a，概率大的被选到的次数就会多，概率小的被选到的次数就会少，这样即便Q value小的action也还是有可能会被选到。
技巧3：使用Replay Buffer
把actor的每笔experience (st,at,rt,st+1)放到一个buffer里面，其中buffer里面的exp可能来自采取不同policy的actor（假设actor和环境互动一万次后就更新参数，而buffer里面能存放5万个的exp，就会导致buffer里有5种不同的actor的exp），当buffer满了再替换旧的exp。训练过程时每次从buffer里面sample一个batch（比如说100个exp）出来训练。
因为buffer里有采取不同policy的actor的exp，所以导致这个训练过程变成off-policy的。但是因为我们只用一个exp训练，并不是整个trajectory，所以off-policy也没关系。
这样做的好处：
1、训练过程中与环境交互很耗时间，而Replay Buffer可以使得之前的actor的exp被反复利用到，减少很Env互动次数；
2、增加数据多样性，降低batch内相关性，提高泛化性能，训练效果更好。