强化学习-知根知底-深度理解值函数方法（一）

强化学习-Zee知根知底系列

搞科研、学习强化学习，重要在于知其然，然后知其所以然。
能够搞清楚，怎么实现强化学习，看源码 看论文其实就可以做到。
但是要真正的抓住核心部分的知识，还是要多做自己的仿真实验，然后认认真真的多看论文。
本系列文章，主要是针对当前主流深度强化学习的各种算法和Trick，分析其背后的原理，从而帮助你改进算法，更适应自己的环境。希望对大家有多帮助。
另外，我会将所有的文章及所做的一些简单项目，放在我的个人网页上。
水平有限，可能有理解不到位的地方，希望大家主动沟通交流。
邮箱：zachary2wave@163.com

强化学习-知根知底-深度理解值函数方法（一）

整个强化学习的学习过程是一个通过与环境交互中进行学习，寻优的过程。随着环境给出的reward 不断调整自身的从而得到最大的reward。值函数方法是强化学习算法中的一大门类。

一、值函数与Bellman方程

首先还是强调一下强化学习基础知识， 任何强化学习算法都需要去估算一个agent所处的状态和动作有多好，即估计值函数 动作值函数。值函数评估当前状态的好坏，动作值函数评估当前状态下做出该动作之后的好坏：
$$v_{\pi }(s)\doteq {\mathbb{E}}_{\pi }\left[G_t|S_t=s\right]={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s\right],\text{ for all }s\in \mathcal{S}$$
$$q_{\pi }(s,a)\doteq {\mathbb{E}}_{\pi }\left[G_t|S_t=s,A_t=a\right]={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a\right]$$

根据bellman方程：
v π ( s ) ≐ E π [ G t ∣ S t = s ] = E π [ R t + 1 + γ G t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ s ′ ∑ r p ( s ′ , r ∣ s , a ) [ r s , a + γ E π [ G t + 1 ∣ S t + 1 = s ′ ] ] = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r s , a + γ v π ( s ′ ) ] ,  for all  s ∈ S

$$\begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\left[r_{s,a}+\gamma \mathbb{E}_{\pi}\left[G_{t+1} | S_{t+1}=s^{\prime}\right]\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r_{s,a}+\gamma v_{\pi}\left(s^{\prime}\right)\right], \quad \text { for all } s \in \mathcal{S} \end{aligned}$$ vπ​(s)​≐Eπ​[Gt​∣St​=s]=Eπ​[Rt+1​+γGt+1​∣St​=s]=a∑​π(a∣s)s′∑​r∑​p(s′,r∣s,a)[rs,a​+γEπ​[Gt+1​∣St+1​=s′]]=a∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[rs,a​+γvπ​(s′)], for all s∈S​
公式解读：

从这个状态到下一个状态，首先根据策略$\pi$ 来选择动作 ，然后以一定的概率到达下一个状态，
所以对应第二步 到 第三步 为 策略$\pi$ 每一个动作的概率 乘以该动作之后的所有可能到达状态概率 再乘 $R_{t+1}+\gamma G_{t+1} $ 。

然而 此时 $r_{s,a}$是确定的，但是$G_{t+1}$ 是不确定的 ，所以 还需要对$G_{t+1}$ 继续求期望，也就是下一步的值函数。
q π ( s , a ) ≐ E π [ G t ∣ S t = s , A t = a ] = E π [ R t + 1 + γ G t + 1 ∣ S t = s , A t = a ] = ∑ s ′ p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] = ∑ s ′ p ( s ′ , r ∣ s , a ) [ r + γ ∑ a ′ π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) ]

$$\begin{aligned} q_{\pi}(s,a) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s, A_{t}=a\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s,A_{t}=a\right]\\ &=\sum_{s^{\prime}} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right] \\ &=\sum_{s^{\prime}} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma \sum_{a'}\pi(a'| s') q_{\pi}\left(s^{\prime},a'\right)\right] \end{aligned}$$ qπ​(s,a)​≐Eπ​[Gt​∣St​=s,At​=a]=Eπ​[Rt+1​+γGt+1​∣St​=s,At​=a]=s′∑​p(s′,r∣s,a)[r+γvπ​(s′)]=s′∑​p(s′,r∣s,a)[r+γa′∑​π(a′∣s′)qπ​(s′,a′)]​
公式解读：

与上一个类似，但是此时已经选择好了动作$a$，所以直接省去策略$\pi$ 的概率。这里用到了$V$和$Q$的关系
$$V(s)=\sum \pi (a|s)\ast Q(s,a)$$

$$Q(s,a)=\sum P\left(s^{\prime },r|s,a\right)\ast \left(r+\gamma V\left(s^{\prime }\right)\right)$$
bellman方程说明当前状态的值函数可以用下一个时刻所有的值函数来表示。然后进行迭代求解。可以看出值函数与策略息息相关，其实值函数就是去描述策略的好坏的。所以最优的策略的目的就是使得值函数能够达到最大。

针对公式3，一个最优的策略一定是将当前状态下的最优动作选择出来，也就是
$$V(s)=\underset{a}{\max }{Q}_{\pi \ast }(s,a)=\underset{a}{\max }\sum _{s^{\prime },r}p\left(s^{\prime },r|s,a\right)\left[r+\gamma v_{\ast }\left(s^{\prime }\right)\right]$$
同理
$$q_{\ast }(s,a)=\sum _{s^{\prime },r}p\left(s^{\prime },r|s,a\right)\left[r+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }\left(s^{\prime },a^{\prime }\right)\right]$$
其实对比5、6式与bellman 方程之间的差距就是一个 $\pi$ ， $\pi$ 总可以使得下一步的最大的$q$ 选择出来。

然而最优策略的主要原因在于没有办法知道最优的值函数 和 动作值函数。

目前，解决该问题主要有三种算法动态规划、蒙特卡洛、TD差分方法。

二 动态规划

动态规划方法中，假设我们已经知道了所有的转移概率$p$和每个情况下的r，那么根据值函数的bellman等式，我们把一个固定的策略代入之后，通过迭代的方式就可以求出该策略下的值函数。这个过程叫做策略估计。

算法如下：

---

随机初始化$V(s)$

循环：

​ 令$\Delta$=0

​ 循环：

​ v ← V ( s ) V ( s ) ← ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V ( s ′ ) ] Δ ← max ⁡ ( Δ , ∣ v − V ( s ) ∣ )

$$\begin{array}{l}{v \leftarrow V(s)} \\ {V(s) \leftarrow \sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma V\left(s^{\prime}\right)\right]} \\ {\Delta \leftarrow \max (\Delta,|v-V(s)|)}\end{array}$$ v←V(s)V(s)←∑a​π(a∣s)∑s′,r​p(s′,r∣s,a)[r+γV(s′)]Δ←max(Δ,∣v−V(s)∣)​

结束循环 当 $\Delta <\theta$

---

这样我们已经知道该策略下准确的值函数，根据公式（4）自然可以根据当前值函数 计算出 动作状态值函数 $q$ 。此时如果我们发现存在动作a使得 $q_{\pi }\left(s,a\right)\ge v_{\pi }(s)$ 那么就说明 该动作至少比原来用策略$\pi$时选择的动作的期望要好。所以可以改变策略$\pi$使得其更好。这个过程叫做策略提升。

结合整个过程 ，就是动态规划方法。

然而实际上，上述方法必须已经得到所有状态下，所有动作的奖励值 才能计算更新的值函数，然而往往这是做不到的。因为复杂度太高 要完成很多次才可以采到，所以将原来迭代求解值函数的公式改变为：
$$V(s)\leftarrow \sum _{s^{\prime },r}p\left(s^{\prime },r|s,\pi (s)\right)\left[r+\gamma V\left(s^{\prime }\right)\right]$$
总结之后 就可以得到：

可以看出的是 该算法是一个确定性的策略，也就是说 每个状态下，只能选择固定的动作，同样在更新的时候依旧是选择最好的动作进行更新。

三 蒙特卡洛算法

动态规划算法，可以非常有效的进行求解马尔科夫决策过程，但是往往我们需要所有的状态转移概率。这个实际上是不满足的，比如说两个人下围棋，我下一个子之后，我并不知道对手下在哪里。同样，如果在控制机器人手臂抓握东西的时候，我们虽然知道了控制哪个关节转动了30度，但是我们要建模手臂动了之后所抓握的东西变成什么样是一件非常困难的事情。

这样我们就需要model-free的算法。也就是，如果我们不知道系统的模型是什么样的时候，我们怎么求解这个问题。

首先，直接观察强化学习的目标，如果 我们已经可以估计得到公式（1）、（2）的期望的$G_t$，那么直接用这个期望的$G_t$来计算值函数就可以了。蒙特卡洛算法的思路是直接根据采用了平均采样汇报来估算值函数、动作值函数的方法。直接上算法：

---

初始化策略$\pi$和值函数$V$；

循环：

​ 利用策略$\pi$ 与环境交互，这样可以得到 K个轨迹 ，每个轨迹都可以表示为：$S_0,A_0,S_1,A_1,S_2,A_2,S_3,A_3，\dots ，S_T,A_T$;

​ 令G=0；

​ 循环每一个轨迹，从T ->T-1 ->……>1：

​ 直接计算$G=\gamma G+R_{t+1}$

​ 算法一（first-visit Monte Carlo estimating $V$）：如果$S_t$第一次出现，那么令$V(S_t)=G$

​ 算法二（every-visit Monte Carlo estimating $V$）：每当$S_t$出现，则记录$G$。 当所有循环结束 令$V(S_t)=mean（G）$。

​ 算法三（every-visit Monte Carlo estimating $G$）：每当$S_t，A_t$出现，则记录$G$。 当所有循环结束 令$G(S_t,A_t)=mean（G）$。

​ 更新策略：

​ $\pi (s)\doteq \arg {\max }_{a}q(s,a)$（贪婪策略）

---

上述算法中，算法一、算法二已经渐渐被算法三替代。

主要原因是首先从本质上来讲，如果不知道转移概率，单纯估计状态值函数是一件误差很大的事儿。

这个道理很简单，对比$V$函数和$Q$函数的bellman方程，可以看出的$V$函数估计受到了策略估计影响要大于$Q$函数的，在所有的reward都是没有误差的状态下，从状态$S_t$到下一步$S_{t+1}$， 这个$S_{t+1}$ 可能有很多种，因为不确定动作，也不确定转移概率，所以就是经过了2次随机。但是在有限次的采样中，很难反应出来。但是我们都对其平均了，也就是让其转移概率都近似于一致。但是如果确定了动作状态对，那么就相当于取消了一次不确定的动作。但是如果采用了确定性策略，也就是每当达到状态$S_t$的时候，一定做出动作$A_t$，那么这个时候$V$和$Q$其实是一样的，也就没什么区别了。

Temporal-Difference（时序差分）方法

其实TD算法其实与蒙特卡洛类似，面对的是没有办法拿到转移概率的时候的强化学习问题。 那么在这个问题下，假如环境没有终点，可以一直无限的运行下去，那么蒙特卡洛算法就显出了局限性。其次，蒙特卡洛算法采样效率更低，具体对比请看第二篇博文。所以我们想找到一个样本利用率更高的算法。

假如说，在与环境交互的时候，每次到达状态$S_t$之后，已知了该状态下的损失奖励值估计值$G_t$，那么更新其值函数$V\left(S_t\right)$可以用下式来表示：
$$V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left[G_t-V\left(S_t\right)\right]$$
根据上式，即使损失奖励值估计值$G_t$ 每次都不是那么准确的时候或者存在噪声的时候，始终可以使得该值函数收敛。但是上式中，始终存在一些问题，因为损失奖励值估计值$G_t$ 是比较难估计的。所以更近一步，如果我们利用bellman方程的第二步，即已有的值函数去代替原来的损失奖励值估计值$G_t$ 。这样就可以进行循环的迭代，从而得到下式：
$$V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left[R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right]$$
根据上式来更新的算法叫做TD(0)算法。

---

初始化策略$\pi$和值函数$V$；

循环：

​ 根据策略$\pi$ 选择状态$S$下的动作$A$，并执行该动作$A$。

​ 从环境得到奖励$R$, $S^{\prime }$。

​ 根据该样本更新值函数$V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left[R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right]$

​ 更新策略：
​
​ $\pi (s)\doteq \arg {\max }_{a}q(s,a)$ （贪婪策略）

​ 结束循环直到$V\left(S_t\right)$ 不在变化。

---

在这个算法的基础上，又演化出了一系列的算法，包括著名的Q-learning算法。