Model-Based方法：策略迭代与价值迭代

在前一章我们已经知道，RL就是在给定了环境$p(s^{\prime },r|s,a)$的情况下，求$\pi (\cdot |s)$使得能够最大化期望累计收益$\mathbb{E}[{\sum }_t{\gamma }^t{R}_t]$。

$p(s^{\prime },r|s,a)$被称之为模型，如果它是已知的（注意给定和已知不一样，给定只是有输入可以得到输出，但是分布规律并不知道，已知意味着整个分布信息都知道），基于model求解policy的方法被称为model-based方法。

1 如何评价一个策略的好坏？- 策略评估

如何找一个好的策略，这个并不容易，一个容易点的问题是，如何评价一个策略的好坏？很自然能想到用优化目标，即期望累计收益$\mathbb{E}[{\sum }_t{\gamma }^t{R}_t]$去评价。

对于一个确定的策略$\pi (\cdot |s)$和model$p(s^{\prime },r|s,a)$，再加上初始状态$S_0$，整个期望可以完全确定，即期望累计收益为${\mathbb{E}}^{\pi }[{\sum }_t{\gamma }^t{R}_t|S_0]$。我们用$V^{\pi }(S_0)$来表示，即在策略$\pi$下，从$S_0$出发能够获得的期望累积收益。

直接用优化目标评价策略还是很难，困难主要来源于他一下把所有步骤全部表示了，为了降低这个难度，考虑只写出一步，其余的步骤利用上面$V$的定义递归表示。会让分析变得简单。所以我们尝试变形

Vπ(S0)=E[R0+γR1+…+γnRn∣S0]=E[R0∣S0]+γE[R1+…+γn−1Rn∣S0]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′p(s′∣S0)E[R1+…+γn−1Rn∣s′]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′∑a′p(s′∣S0,a)π(a∣S0)E[R1+…+γn−1Rn∣s′]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′∑a′∑rp(s′,r∣S0,a)π(a∣S0)Vπ(s′)
begin{aligned}

V^pi (S_0) &= mathbb{E}[R_0 + gamma R_1 + … + gamma^n R_n|S_0]

&= mathbb{E}[R_0|S_0] + gamma mathbb{E}[R_1 + … + gamma^{n-1} R_n|S_0]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}p(s’|S_0)mathbb{E}[R_1 + … + gamma^{n – 1}R_n|s’]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}sum_{a’}p(s’|S_0, a)pi(a|S_0)mathbb{E}[R_1 + … + gamma^{n – 1} R_n|s’]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}sum_{a’}sum_{r}p(s’, r|S_0, a)pi(a|S_0)V^pi (s’)

end{aligned}
Vπ(S0​)​=E[R0​+γR1​+…+γnRn​∣S0​]=E[R0​∣S0​]+γE[R1​+…+γn−1Rn​∣S0​]=r∑​ra∑​s′∑​p(s′,r∣S0​,a)π(a∣S0​)+γs′∑​p(s′∣S0​)E[R1​+…+γn−1Rn​∣s′]=r∑​ra∑​s′∑​p(s′,r∣S0​,a)π(a∣S0​)+γs′∑​a′∑​p(s′∣S0​,a)π(a∣S0​)E[R1​+…+γn−1Rn​∣s′]=r∑​ra∑​s′∑​p(s′,r∣S0​,a)π(a∣S0​)+γs′∑​a′∑​r∑​p(s′,r∣S0​,a)π(a∣S0​)Vπ(s′)​

第一行是定义，第二行是期望的线性性，第三行是把期望的条件换成下一个状态，因为下一个状态不确定，所以需要乘新的概率系数并求和。第四、五行是把$p(s^{\prime }|s)$利用policy和model表示出来。后面三行主要是条件概率公式的应用。

至此，我们找到了用递归方法表示累积期望收益的办法。

推广至对任何$t$时刻的状态$S_t$，我们有

$V^{\pi }(S_t)={\sum }_{r}r{\sum }_a{\sum }_{s^{\prime }}p(s^{\prime },r|S_t,a)\pi (a|S_t)+\gamma {\sum }_{s^{\prime }}{\sum }_a{\sum }_{r}p(s^{\prime },r|S_t,a)\pi (a|S_t)V^{\pi }(s^{\prime })$

上面为了严谨使用了最基本的$p(s^{\prime },r|s,a)$和$\pi (\cdot |s)$表示。如果把被求和的中间量都省略掉，则${\sum }_a{\sum }_{r}p(s^{\prime },r|S_t,a)\pi (a|S_t)\equiv p^{\pi }(s^{\prime }|S_t)$，而${\sum }_a{\sum }_{s^{\prime }}p(s^{\prime },r|S_t,a)\pi (a|S_t)\equiv p^{\pi }(r|S_t)$。那方程就简化成了

$V^{\pi }(S_t)={\sum }_{r}r{p}^{\pi }(r|S_t)+\gamma {\sum }_{s^{\prime }}{p}^{\pi }(s^{\prime }|S_t)V^{\pi }(s^{\prime })$

上面这个方程是针对一个状态具体而言的，并不能刻画全貌，为了方便表示，假设状态离散且有限，为$S_a,S_b,\dots$，那么$V(\cdot )$其实就是一个向量，它的长度是状态的数量，第$i$个位置的数字表示第$i$个状态的$V$。我们可以用一个向量和矩阵的等式来表示。即

[Vπ(Sa)Vπ(Sb)…Vπ(Sz)]=[∑rrpπ(r∣Sa)∑rrpπ(r∣Sb)…∑rrpπ(r∣Sz)]+γ[pπ(Sa∣Sa)pπ(Sb∣Sa)…pπ(Sz∣Sa)pπ(Sa∣Sb)pπ(Sb∣Sb)…pπ(Sz∣Sb)…………pπ(Sa∣Sz)pπ(Sb∣Sz)…pπ(Sz∣Sz)]⋅[Vπ(Sa)Vπ(Sb)…Vπ(Sz)]
left[

begin{matrix}

V^pi(S_a)

V^pi(S_b)

…

V^pi(S_z)

end{matrix}

right] =

left[

begin{matrix}

sum_r r p^pi(r|S_a)

sum_r r p^pi(r|S_b)

…

sum_r r p^pi(r|S_z)

end{matrix}

right] +

gamma left[

begin{matrix}

p^pi(S_a|S_a) & p^pi(S_b|S_a) & … & p^pi(S_z|S_a)

p^pi(S_a|S_b) & p^pi(S_b|S_b) & … & p^pi(S_z|S_b)

… & … & … & …

p^pi(S_a|S_z) & p^pi(S_b|S_z) & … & p^pi(S_z|S_z)

end{matrix}

right] cdot

left[

begin{matrix}

V^pi(S_a)

V^pi(S_b)

…

V^pi(S_z)

end{matrix}

right]
⎣⎡​Vπ(Sa​)Vπ(Sb​)…Vπ(Sz​)​⎦⎤​=⎣⎡​∑r​rpπ(r∣Sa​)∑r​rpπ(r∣Sb​)…∑r​rpπ(r∣Sz​)​⎦⎤​+γ⎣⎡​pπ(Sa​∣Sa​)pπ(Sa​∣Sb​)…pπ(Sa​∣Sz​)​pπ(Sb​∣Sa​)pπ(Sb​∣Sb​)…pπ(Sb​∣Sz​)​…………​pπ(Sz​∣Sa​)pπ(Sz​∣Sb​)…pπ(Sz​∣Sz​)​⎦⎤​⋅⎣⎡​Vπ(Sa​)Vπ(Sb​)…Vπ(Sz​)​⎦⎤​

可以验算一下每一个S带进去都是成立的。

简记为$V=R+\gamma PV$

这是一个等式，并且含有未知数(未知函数)$V$。包含未知数的等式就是方程，所以上面的等式实际上是关于$V$的方程。既然是方程，能否把他解出来？只要解出来了，我们就得到了关于给定策略$\pi$在任何一个状态出发的期望累计收益。就能够评价策略的好坏了！

直接求解这个方程不太容易。但是可以迭代求解：假设我们有一个初始的$V$，按照方程右侧的方式计算，就能得到一个新的$V$，再次带入右侧，又能得到新的，如果不断迭代，直至有一次我们迭代出来的新$V$刚好和迭代之前的$V$相同，那就找到了这个方程的解了！

现在只剩最后一个问题：这样做能不能收敛？能的话，我们找到的是唯一解吗，还是有其他解？答案是能，并且是唯一解

注意上面的简记有一个好处，就是很多看上去是变量的$S_t$都不存在了，他们实际不过是向量中某个位置上的元素而已。这为后面的证明提供方便。

迭代计算一定可以找到解并且是唯一解。
把函数$V$按照方程右侧计算，得到还是一个函数，这种输入和输出都是函数的操作称为算子，所以我们把对方程右侧的计算看作一个算子（术语叫Bellman Policy Operator），用$B$表示，那么: $B^{\pi }V=R+\gamma PV$
迭代计算的过程就是对一个初始的$V_0$ 不断使用$B^{\pi }$的过程。
接下来我们证明Bellman算子在无穷范数度量空间是一个压缩映射。
Q:什么叫无穷范数？A:就是对一个向量取最大值。
Q: 什么叫度量空间？A: 就是对于所有的元素（我们这里是V向量）定义一种表示元素之间距离的方法，这个距离定义满足正定（元素间距离非负，等于0当且仅当两个元素相同）、对称（a到b的就和b到a的距离一样）、三角不等式(d(a,b) + d(b,c)$\le$ d(a,c))
Q: 什么叫无穷范数度量空间？A: 对任意两个$V_1,V_2$，我们定义距离$||V_1-V_2|{|}_{\infty }={\max }_i(|V_1[i]-V_2[i]|)$。注意这里取绝对值后才取最大值，可以自行验证这个距离定义满足度量空间里距离定义的正定、对称和三角不等式
Q: 什么叫压缩映射？
A：对任意的$V_1,V_2$，考察被贝尔曼算子作用后的距离:
$\begin{array}{rl}||B^{\pi }{V}_1-B^{\pi }{V}_2|{|}_{\infty }=& ||R+\gamma P{V}_1-R+\gamma P{V}_2|{|}_{\infty }\\ =& \gamma \underset{i}{\max }(P|V_1-V_2|[i])\\ \le & \gamma \underset{i}{\max }|V_1-V_2|[i]\\ =& \gamma ||V_1-V_2|{|}_{\infty }\end{array}$
第一行是距离定义，第二行是抵消合并，第三行是利用了$P$矩阵的每一行和等于1，加权平均之后的结果一定比直接取最大小。第四行是距离定义。
所以经过贝尔曼算子操作之后，所有的元素的距离都比之前更近了。那么经过足够多次操作之后，所有的元素都被压缩到一个点上，再运算结果也不会改变了。
这说明贝尔曼算子的操作会收敛，并且会收敛到一个不动点上，对应唯一的$V$的解！

2 如何根据评价的$V$改进策略？- 策略迭代

上一节说明，通过定义了一个$V$算子，然后利用递归的方式简化累计期望收益的表示得到了一个关于$V$的方程，然后把方程右侧的操作看作算子，竟然可以迭代收敛，从而找到了$V$的解。我们成功实现了评价策略的目标。接下来思考如何根据这个评价改进策略？

在之前的思路里，我们定义了$V^{\pi }(s)$，他表示在状态$s$开始，按照策略$\pi$交互获得的期望累计收益。这次与之不同是，因为需要考虑动作，所以我们把第一次的动作也作为条件。即定义函数$Q^{\pi }(s,a)$，表示状态$s$下采取动作$a$，之后按照$\pi$选取动作，能够获得的期望累积收益。 即:

$Q^{\pi }(S_t,A_t)=\mathbb{E}[{\sum }_{t^{\prime }=t}^n{\gamma }^{t^{\prime }-t}{R}_t^{\prime }|S_t,A_t]$
我们当然可以按照以前计算$V$的思路，把他写成递归的形式表示。但我们已经好不容易求出$V$了，所以现在更希望用$V$来表示$Q$，从而为策略提供指导。其实根据定义很容易看出来

$Q^{\pi }(s,a)={\sum }_{r}rp(r|s,a)+\gamma {\sum }_{s^{\prime }}p(s^{\prime }|s)V^{\pi }(s^{\prime })$

推导思路是，先计算这一步在状态是$s$采取动作$a$带来的期望收益，${\sum }_{r}rp(r|s,a)$，然后计算下一状态的期望收益，下一状态的期望收益可以用$V$表示，具体转移到那个状态不确定，所以再求一次期望。这些$p(r|s,a)$和$p(s^{\prime }|s)$可以利用上一节计算$V$的方式用$p(s^{\prime },r|s,a)$和$\pi (\cdot |s)$表示出来，就不写了。

有了$Q$，一个直观的策略改进方法是${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$。

为什么这样可以呢? 因为

Vπ′(s)=Qπ(s,π′(s))=max⁡aQπ(s,a)≥∑aπ(a∣s)Q(s,a)=Vπ(s)
begin{aligned}

V^{pi’}(s) =& Q^pi(s,pi'(s))

=& max_a Q^pi(s, a)

ge & sum_a pi(a|s)Q(s, a)

=& V^pi(s)

end{aligned}
Vπ′(s)==≥=​Qπ(s,π′(s))amax​Qπ(s,a)a∑​π(a∣s)Q(s,a)Vπ(s)​

第一行是因为策略是确定的，并且选取动作总是基于当前的$Q$，不用求期望，第二行是因为新策略取argmax，所以得到的一定是$Q$的最大值，第三行是因为最大值一定大于所有值的加权平均，第四行是定义。

也就是说，在有了目前策略的$\pi$之后，我们对每个状态取argmax的方法，一定可以得到一个能够使$V$更大的$\pi$。而$V$就是我们评价策略好坏的标准，越大越好，所以策略得到了改进！再按照前一节的方法计算新策略的$V$，然后循环，就可以得到最优策略${\pi }^{\ast }$了！

此外还发现这里有一个不那么平凡的结论，就是如果一个策略${\pi }_1$比另一个策略${\pi }_2$好，那么它的$V^{{\pi }_1}$中的每一个$s$对应的数都比$V^{{\pi }_2}$大。这是因为前面的推导对任意$s$都成立。直观上我们可能觉得他有可能是有些状态大了，有些状态小了，但事实并不是如此。这个结论很关键。

这里Sutton的书上还特别提到了一个潜在的bug：如果有两个一样好的策略，那如果在策略提升的时候不去和过去的最优策略比较，有可能出现两个策略交替的情况。

广义策略迭代则是指，策略评估和价值迭代的过程都不需要进行充分（这里进行充分对策略评估过程指收敛，对价值迭代过程指遍历更新完全部状态）就进行下一步，这样最终也是可以收敛的。

3 更简单的方法 – 价值迭代

前面的过程中我们先用策略评估，计算$V$，然后用$V$计算$Q$，然后基于$Q$改进$\pi$，然后再计算$V$。

问题在于，我们都有能力从$V$计算出$Q$了 (也就是$Q^{\pi }(s,a)={\sum }_{r}rp(r|s,a)+\gamma {\sum }_{s^{\prime }}p(s^{\prime }|s)V^{\pi }(s^{\prime })$），那能不能直接求出$V$的最优取值$V^{{\pi }^{\ast }}$，然后直接计算出$Q$。

这样可以避免反复求$V$和$Q$。

此外，我们从$Q$改进策略的方法是取argmax，那这种思想能不能直接用到$V$上帮助我们找最优策略呢？答案是肯定的。

我们定义一个新的算子Bellman Optimal Operator

$B^{\ast }V=\arg {\max }_{a}R+\gamma PV$ 其实这个操作就是取$\arg \max Q(s,a)$的过程。因为$Q^{\pi }(s,a)={\sum }_{r}rp(r|s,a)+\gamma {\sum }_{s^{\prime }}p(s^{\prime }|s)V^{\pi }(s^{\prime })$。如果表示成矩阵那其实是一样的。

和公式(2)几乎一样可以证明这个最优算子也可以收敛到唯一解。

所以第2节讲的策略评估+策略改进的方法，本质上是先有了一个$V_{{\pi }_1}$，然后根据Q改进了一个${\pi }_2$，然后在第二节最后我们指出$V_{{\pi }_2}\ge V_{{\pi }_1}$，所以不断循环我们找到一个一个$\pi$每一个都比前一个的V大，直至找到了最大的。

现在不再通过$Q$去找下一个策略了，而是直接利用Bellman Optimal Operator，这个过程和之前用$Q$找是一样的，所以一样能找到最优策略。这样就避免了通过$Q$去导出$\pi$而是直接从$V$导出$\pi$，提高了计算速度。

在实际操作中，价值迭代往往不会分别maintain新旧价值表，而是只维护一张表，需要更新特定状态时直接原地更新，这种异步迭代方法同样有效。

Notes

• 1 Model-based方法之所以是model-base，就是因为计算$V$和$Q$的过程利用了$p(s^{\prime },r|s,a)$。这带来的最大优势是完全不需要和环境交互就可以求出最优策略。但是多数情况下这个是不知道的。如果问题比较简单，也许可以通过蒙特卡洛估计出$p(s^{\prime },r|s,a)$，然后利用价值迭代计算policy。但更多时候环境很复杂，这种方法不适用。

• 2 当model-base不适用的时候，从历史数据估计累计期望收益计算$V$或$Q$就变成了一个很关键的事情。主要有两种思路，蒙特卡洛采样和时序差分。蒙特卡洛采样是指直接从当前状态出发按照policy采样多个完整的episode然后求平均估计期望。时序差分则是利用推导中递归的思想，用一步或几步的真实reward + 目前的$V$或$Q$的值，实现自举地估计。前者的特点估计是无偏的，但是方差很大（因为是很多步reward求和）。后者的特点是有偏，但方差小（因为只有1步求和，但剩余部分用自己之前的估计，本身不准确）。

• 3 公式(3)很重要，它说明随便给一个策略，只要取argmax就能得到更好的策略，这个思想在Q-Learning中会再次体现，也是经验重放思想得以应用的关键。因为历史数据混合起来使用，可以看作诸多历史策略的叠加产生的结果，而argmax能够保证新得到的策略一定比之前好。经验重放让数据的利用率得到提高，缓解了RL样本利用低效、数据获取难的问题，非常伟大。

有趣问题：赌徒问题

问题描述：有一个赌局，你初始有一笔钱（整数，范围在1-99），每一轮你可以选择把你手上的钱部分或全部押注，然后抛硬币，硬币向上的概率为0.4，正面向上你可以赢得和你押注数量一样的钱，否则输掉你押注的钱。手上没有钱或大于等于100元结束。求出手上有不同数量钱时的最优策略。

技巧：

• 如果1）交互过程是有限、2）只有终止状态有reward、3）无折扣，可以为v添加终止状态，并且把值定死成reward。

• 根据value生成action，不要简单的argmax，这取决于你的精确度到多少，浮点数误差需要忽视。

​这个题目非常奇妙，值得分析。
图中横轴表示状态，纵轴表示策略，每个点是一个策略。

• 首先，50这个状态好，因为这个coin正面朝上概率小，意味着对我不利，我希望尽可能快的结束游戏，所以50的时候all in有助于直接完成，同样道理，51的时候如果只输掉1有助于我回到50的状态。注意这个题是多轮有限的，那么reward会受到持续时间的影响，想最大reward使得我们希望尽可能快的结束游戏。他能保证这是一个好的策略体现了长远眼光，即，充分考虑当前状态输了，也要尽可能落到一个取胜概率大的地方去。
• 在51这个地方不仅1是一个好的选择，49同样是好的选择，因为你有0.4的概率直接结束，虽然你可能输的很惨变成2，但是100的诱惑是很大的，毕竟他的value是1，0而50只有0.4左右，所以期望其实差不多。因此49和51都是有两个选择的，即要么扔的少一点可能输到50，要么赌个大的，没准一把就赢了。这种情况从50向两边扩展，直至37，68的位置。
• 37/68两个位置开始出现3个选择。其中有两个action是相邻的，倾向于回到50；还有一个对于左侧37是全押，对右侧是押一个能到100的。总之还是因为50和100的吸引力相似造成的。这种继续向两边延展，直到25，75。
• 25/75这两个点只有一个状态，对75而言就是押25，不论50和100都是好的，这两个点在此重合了，所以action也只有1个。对25这个点，全押是唯一最优选择，因为你最远只能到50，另一个跨越50的可能不再存在了。再向两边延展又是两个选择。这里的两个选择有分别以25和75作为参考界限了。一种是希望能够到达25/75的状态，另一种是全押（押100-s）希望能够跨越25（到达终点）。也就是说，1～50和50～100这两个分段呈现出和全局1～100相似的特点。
• 再一直向两边延展到了12、13，右侧是87左右。对左侧而言倾向于激进，总是全押，因为他没有机会跨越25了只能尽可能靠近，而右侧倾向于保守，因为50不具有吸引力，距离100已经很近了。

如果正面朝上的概率从0.4变成0.25，policy没有变化，因为正面还是劣势。但如果变成0.55，就有着显著变化。此时在钱比较少的时候，policy变得保守，只押1，因为硬币向上概率大，长期看是赚的，那么尽可能延长自己的玩的时间有助于提高本金。所以一直到41之前，最优策略都是只押1，最优策略从只有1，逐渐增加为{1,2}, {1,2,3}…到80和81的时候，策略多达19个。再往后开始减少，是因为押多了没用，到100就行了。策略图如下

如果是0.5那么你对于输赢完全没于任何把握，随机策略就是最好策略，换句话说，有10钱，1～10随便押就行了。策略图如下

这道题给出了一种智慧，对于胜利把握大的游戏，不要着急，看长线你总能赚。对于胜利把握小的游戏，快赢了的时候就得保守，快输了的时候就赌一把，拖延无好处。

附代码：

import numpy as np
import matplotlib.pyplot as plt

p_h = 0.4

def value_iteration(n_iter=10000):
    v = np.zeros(101)
    v[100] = 1.
    for it in range(n_iter):
        delta = 0.
        for s in range(1, 100):
            v_old = v[s]
            v[s] = np.max([p_h * v[s + a] + (1 - p_h) * v[s - a] for a in range(1, min(s, 100 - s) + 1)])
            delta = max(delta, abs(v_old - v[s]))
        if delta < 1e-5:
            print("converge at %d rounds" % it)
            break
    # pick all optimal actions for each state
    p = dict()
    for s in range(1, 100):
        cands = [p_h * v[s + a] + (1 - p_h) * v[s - a] for a in range(1, min(s, 100 - s) + 1)]
        max_value = np.max(cands)
        p[s] = []
        for a, cand in enumerate(cands):
            if abs(max_value - cand) < 1e-5:
                p[s].append(a + 1)
    return v, p

if __name__ == "__main__":
    value, policy = value_iteration(10000)
    plt.plot(value)
    plt.show()
    for s in policy:
        plt.scatter([s] * len(policy[s]), policy[s], marker='.', color='blue')
    plt.show()