RL-Ch5-Q-Learning
本文提到的actor等效于前几章笔记中的agent+policy。
Critic $V^\pi(s)$
- 不直接采取行动
- 对actor进行评判(即对agent采取的policy进行评判)
- $V^\pi(s)$：在状态s时使用策略$\pi$后的累计收益
如何估计$V^\pi(s)$？
Mento-Carlo(回合更新)
示意图如下：
实际上是一个回归问题。
Tenmporal-Difference(单步更新)
取一个episode的中间几个值，即${s_t,a_t,r_t,s_{t+1}}$，计算图如下：
MC vs. TD
MC的方差较大，而TD有小方差，但更新往往不够准确。
例子
取一个游戏的八个回合，
$s_a,r=0,s_b,r=0,END$
$s_b,r=1,END\quad \times \quad7$
$s_b,r=0,END$
可以计算得到$V^\pi(s_b)=\frac{3}{4}$，而MC/TD得到的$V^\pi(s_a)$得到的值是不一样的。
MC：考虑到$s_a$在采样时只出现一次，所以$V^\pi(s_a)=r_a=0$，采样中的reward值即为其state value。
TD：由更新公式得到$V^\pi(s_a)=V^\pi(s_b)+r_a=\frac{3}{4}+0=\frac{3}{4}$。
可以看到两者的取值区别在于：MC考虑到$s_a$出现会对$s_b$有影响，而TD则对$s_b$的常见state value进行求均值，在根据TD法则对$s_a$的state value进行更新。
Another Critic $Q^\pi(s,a)$
state-action value function $Q^\pi(s,a)$，指代的是在policy $\pi$ 下，在状态s时采取动作a得到的回报，回报可以是离散的数值，也可以是下一可能状态的概率分布。
Q-Learning
介绍
基本概念在Ch2与Ch3已经提及，这里做图表的说明：
其中找更好的策略$\pi$，即寻找一个$\pi’$比原先的$\pi$更好(证明过程可见系列博文的Ch2)，数学表达式为
$$
V^{\pi’}(s) \geq V^\pi(s)\quad for ,all, s \in S
$$
此时，策略$\pi’$满足
$$
\pi’(s)=arg \max_{a}Q^\pi(s,a)
$$
策略$\pi’$只取决于Q，以上方法不适合状态/动作空间为连续的情形。
编程技巧
Target Network
原先的网络需要两个Network，即两个$Q^\pi$。若两个$Q^\pi$同时更新，训练不容易收敛，所以让下方的Net固定，只调上方Net的参数，变为regression问题。当上方Net更新过多(N)次后，再将其参数copy到下方Net中，重复执行以上步骤，直至收敛。
Exploration
policy $\pi$是基于Q-function的，即$a=arg\max_{a}Q(s,a)$。先前在状态s取样到的动作a的Q值如果为正，则之后会一直取该动作。所以可以使用一些方法来兼顾探索。
- $\epsilon-greedy$ 算法
$$
\begin{equation}
a=\left{
\begin{aligned}
&arg\max_{a}Q(s,a) &1-\epsilon\
&\text{random action} &\epsilon
\end{aligned}
\right.
\end{equation}
$$
$\epsilon$可以选择随着学习次数的增加而下降，更符合实际情况。
- Baltzman Exploration
对在状态s下采取每个动作a的概率进行构造：
$$
P(a|s)=\frac{exp(Q(s,a))}{\sum_a exp(Q(s,a))}
$$
Replay Buffer
这是off-policy的一种策略，具体做法是：从已知的经验(buffer)中挑选一个短序列(batch)，用以更新Q-function。示意图如下：
Typical Q-Learning Algorithm^1
•Initialize Q-function Q, target Q-function $\hat{Q}=Q$
•In each episode
•For each time step t
•Given state $s_t$, take action $a_t$ based on Q (epsilon greedy)
•Obtain reward $r_t,$ and reach new state $s_{t+1}$
•Store $(s_t, a_t, r_t, s_{t+1})$ into buffer
•Sample $(s_i, a_i, r_i, s_{i+1})$ from buffer (usually a batch)
•Target $y=r_i+\max_a[\hat{Q}(s_{i+1},a)]$
•Update the parameters of Q to make $Q(s_i , a_i )$ close to y (regression)
•Every C steps reset $\hat{Q}=Q$
Q-Learning的变种
Double DQN
Q值总会被高估：因为可能存在动作a真正Q值得估计错误(估高或低)，而Q值的更新公式
$$
Q(s_t,a_t)=r_t+\max_aQ(s_{t+1},a)
$$
总是取使得Q最大的a，估高则Q也会被高估，估低则无碍。
所以对式(5)等号两边得Q进行分别估计，即设立两个Q-Function：Q和Q‘(Target Network)。则Q值的更新公式更正为
$$
Q(s_t,a_t)=r_t+Q’(s_{t+1},arg\max_a Q(s_{t+1},a))
$$
此举的好处在于：若Q高估了a，则Q’不一定会给a高值；若Q‘高估了a，而Q不一定会给a高值。可以认为Q负责提案，而Q’负责执行，互不干扰职权。
Dueling DQN
改Network的架构，其余想法与DQN(Q-Learning+Deep Learning)相同。
传统的DQN的架构如图^1：
Dueling DQN的架构如图^1：
其中Q(s,a)是table，V(s)是vector，A(s,a)是table，三者之间的关系为
$$
Q(s,a)=V(s)+A(s,a)
$$
其中V与A的加和用到了广播机制。
因为随机采样难以做到充分性(即不一定在每个状态每个动作都可以尝试)，所以对table的充分更新难以做到。Dueling DQN的想法是：只让网络更新V值，而不更新A值，通过V的更新来实现对Q进行更新。
为了让算法更稳定，具体可以采用如下的做法：
取V-vector的各元素分别为Q-table每列的均值
取A-table中的每列和均为0(均值归一化)
Prioritized Reply
略
Multi-step
这个方法可以实现MC与TD之间的平衡，即精确度和方差的平衡。既有MC\TD的优点，也有它们的缺点。具体做法是在Replay Buffer机制中只对一个时间步的短序列取样，延伸至多个时间步的序列取样。机制运作图如下：
Noisy Net
$\epsilon-greedy$是在action上加入Noise，我们接下来的想法是能否在每个episode开始前在Q-function的参数里加入Noise呢？即$Q(s,a)\to \widetilde{Q}(s,a)$。
在action上加入noise，即agent在针对相同情况会有不一样的应对反应，这往往是不合现实的。而在Q-function的参数里加入Noise，agent不会出现上述问题，且有原则也有尝试。如果说Noise on action表现的是agent的随机尝试，那么Noise on parameter表现的则是agent有系统地尝试。
Distributional Q-function
真实的Q(s,a)是一个分布，Q-Learning使用的是各分布的均值表现，所以我们其实可以把这个分布给表现出来。Q-Learning的Q-functiong和Distributional Q-function的区别如下图^1所示：
Q-Learning在连续动作上的改进
传统的Q-Learning是使用回归方法估计Q-function，较容易操作，但处理的往往是离散有限动作空间的问题，而对连续动作空间问题难以解决。连续动作空间问题包括：自动驾驶(方向盘转动角度)、机器人控制(手臂移动/转动)等。
解决方法有四种：
- 取样足够多的动作，再取能使Q最大的a。
- 用梯度下降算法去解决该优化问题。缺点：不一定能找到全局最优解，且运算量太大。
- 设计一个能够让优化更为简单的网络。
能够证明$\Sigma(s)$为正定矩阵，所以二次型计算得到的数值(不计入负号)为非负值，所以当$a=\mu(s)$时，Q(s,a)能够取到最大值，此时就要优化网络$Q^\pi$，使得$\mu(s)=arg\max_aQ(s,a)$。
- 不使用Q-Learning算法。
总结
目前为止，李宏毅老师的课程已经讲完了Value-based和Policy-based的方法以及其中的Q-Learning和PPO算法。两种方法分别代表学习actor和学习critic，下一章我们将介绍两个的结合，actor-critic系列算法。
