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

整个强化学习的学习过程是一个通过与环境交互中进行学习，寻优的过程。随着环境给出的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方程： $\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}$ 公式解读：

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

然而 此时 $r_{s,a}$是确定的，但是$G_{t+1}$ 是不确定的 ，所以 还需要对$G_{t+1}$ 继续求期望，也就是下一步的值函数。 $\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}$ 公式解读：

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

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

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

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

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

二 动态规划

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

算法如下：

---

随机初始化$V(s)$

循环：

​ 令$\Delta$=0

​ 循环：

​ $\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}$

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

---

这样我们已经知道该策略下准确的值函数，根据公式（4）自然可以根据当前值函数 计算出 动作状态值函数 $q$ 。此时如果我们发现存在动作a使得 $q_{\pi}\left(s, a\right) \geq 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）采用了平均采样汇报来估算值函数、动作值函数的方法。直接上算法：

---

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

循环：

​ 利用策略$\pi$ 与环境交互，这样可以得到 K个轨迹 ，每个轨迹都可以表示为：$S_0,A_0,S_1,A_1,S_2,A_2,S_3,A_3，…，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方法

在上面两种方法中，都存在一个问题，如果说环境是发生缓慢变化的怎么办，那么DP算法每个时间段都要更新一次，而蒙特卡洛算法之前采样的数据肯定就没有办法使用了。

总结