值迭代 | Value Iteration

值迭代（Value Iteration）直接利用递归性，通过不断迭代逼近最优状态值函数 $v^{\ast }(s)$。整个算法可以概括为：
$$v^{(k+1)}=f\left(v^{(k)}\right)=\underset{\pi }{\max }\left(r_{\pi }+\gamma P_{\pi }{v}^{(k)}\right),k=1,2,3\dots$$
因此这个算法理论上需要包含两个主要步骤：

1. 策略更新（PU）：${\pi }^{(k+1)}=\arg {\max }_{\pi }\left(r_{\pi }+\gamma P_{\pi }{v}^{(k)}\right)$

   现在我求出了${\pi }^{(k+1)}$，我就可以再代入下面的式子，再去求解$v^{(k+1)}$，他们有一个前后顺序！

2. 状态更新（VU）：$v^{(k+1)}=r_{{\pi }^{(k+1)}}+\gamma P_{{\pi }^{(k+1)}}{v}^{(k)}$

注意！此处的$v_k$并不是state value!因为step 2这个方程不是贝尔曼方程，是一个迭代式。对比一下贝尔曼方程的matrix-vector形式，你会看见方程左右应该是同一个$v_k$

而策略 π 更新的时候由于使用了贪心选择，这两个步骤可以合并简化，直接使用最优的动作价值去更新状态价值：
$$v^{(k+1)}(s)=\underset{a}{\max }{q}^{(k+1)}(s,a)$$

值得一提的是，贪心更新策略 π 也带来了一个有趣的现象：越靠近目标区域的状态越先变好。直观上就是因为 π 依赖于其他状态，而当其他状态都不好的时候无从更新，只有接近目标区域的状态有明确的优化方向。

具体步骤

1. 初始化值函数：设定初始值 $v^{(0)}(s)$，通常初始化为全零或任意常数。

2. 迭代更新值函数： 对于每个状态 s，根据贝尔曼最优公式更新
   $$v^{(k+1)}(s)=\underset{a}{\max }\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v^{(k)}(s^{\prime })\right]$$

3. 判断收敛： 检查值函数更新是否足够小（例如$\Vert v^{(k+1)}-v^{(k)}{\Vert }_{\infty }<ϵ$），若收敛则停止迭代并输出 v(k+1)。

4. 推导策略： 一旦得到收敛的值函数 v∗(s)，通过以下方式获得对应的最优策略 π∗：

$${\pi }^{\ast }(s)=\arg \underset{a}{\max }\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{\ast }(s^{\prime })\right]$$
假设我们有一个3 x 3的棋盘：

• 有一个单元格是超级玛丽，每回合可以往上、下、左、右四个方向移动
• 有一个单元格是宝藏，超级玛丽找到宝藏则游戏结束，目标是让超级玛丽以最快的速度找到宝藏
• 假设游戏开始时，宝藏的位置一定是(1, 2)

这个一个标准的马尔科夫决策过程(MDP)：

• 状态空间State：超级玛丽当前的坐标
• 决策空间Action: 上、下、左、右四个动作
• Action对State的影响和回报 P(State’, Reward | State, Action)：本文认为该关系是已知的
  • 超级玛丽每移动一步，reward = -1
  • 超级玛丽得到宝箱，reward = 0并且游戏结束

结合上图可以非常简单的理解价值迭代：

• 初始化：所有state的价值V(s) = 0

• 第一轮迭代：对于每个state，逐一尝试上、下、左、右四个Action

  • 记录Action带来的Reward、以及新状态 V(s’)
  • 选择最优的Action，更新V(s) = Reward + V(s’) = -1 + 0
  • 第一轮结束后，所有状态都有V(s) = -1，即从当前位置出发走一步获得Reward=-1

• 第二轮迭代：对于每个state，逐一尝试上、下、左、右四个Action

  • 记录Action带来的Reward、以及新状态 V(s’)
  • 选择最优的Action，更新V(s) = Reward + V(s’)
    • 对于宝箱周围的State，最优的Action是一步到达宝箱，V(s) = Reward + V(s’) = -1 + 0
    • 对于其他State，所有的Action都是一样的，V(s) = Reward + V(s’) = -1 + -1
  • 第二轮结束后，宝箱周围的State的价值保持不变 V(s) = -1，其他State的价值 V(s) = -2

• 第三轮迭代：对于每个state，逐一尝试上、下、左、右四个Action

  • 记录Action带来的Reward、以及新状态 V(s’)
  • 选择最优的Action，更新V(s) = Reward + V(s’)
    • 对于宝箱周围的State，最优的Action是一步到达宝箱，V(s) = Reward + V(s’) = -1 + 0
    • 对于宝箱两步距离的State，最优的Action是先一步到达宝箱周边的State，V(s) = Reward + V(s’) = -1 + -1
    • 对于宝箱三步距离的State，所有Action都是一样的，V(s) = Reward + V(s’) = -1 + -2

• 第四轮迭代：对于每个state，逐一尝试上、下、左、右四个Action

  • 记录Action带来的Reward、以及新状态 V(s’)

  • 选择最优的Action，更新V(s) = Reward + V(s’)

    • 对于宝箱周围的State，最优的Action是一步到达宝箱，V(s) = Reward + V(s’) = -1 + 0
    • 对于宝箱两步距离的State，最优的Action是先一步到达宝箱周边的State，V(s) = Reward + V(s’) = -1 + -1
    • 对于宝箱三步距离的State，最优的Action是所有Action都是一样的，V(s) = Reward + V(s’) = -1 + -2

  • 在第四轮迭代中，所有V(s)更新前后都没有任何变化，价值迭代已经找到了最优策略。、

    

策略迭代 | Policy Iteration

策略迭代是另一种求解 BOE 的方法，核心思想是交替优化策略和状态值函数，直到收敛到最优策略 π∗。

与值迭代不同的是，策略迭代先初始化一个随机策略，再交替进行以下两个主要步骤：

• 策略评估（PE）：$v_{{\pi }^{(k)}}=r_{{\pi }^{(k)}}+\gamma P_{{\pi }^{(k)}}{v}_{{\pi }^{(k)}}$
• 策略改进（PI）：${\pi }^{(k+1)}=\arg {\max }_{\pi }\left(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }^{(k)}}\right)$

这个算法按照如下顺序

$${\pi }_0\stackrel{PE}{\to }{v}_{{\pi }_0}\stackrel{PI}{\to }{\pi }_1\stackrel{PE}{\to }{v}_{{\pi }_1}\stackrel{PI}{\to }{\pi }_2\stackrel{PE}{\to }{v}_{{\pi }_2}\stackrel{PI}{\to }\dots$$

PE=policy evaluation, PI=policy improvement

1. 初始化策略：随机初始化一个初始策略${\pi }^{(0)}$。

2. 策略评估：在当前策略${\pi }^{(k)}$下，通过求解以下线性方程组来获得状态

值函数$v_{{\pi }^{(k)}}(s):$

$$v_{{\pi }^{(k)}}(s)=\sum _a{\pi }^{(k)}(a\mid s)\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{{\pi }^{(k)}}(s^{\prime })\right]$$

​ $\circ$当状态空间较小时，可以直接解线性方程组，

​ $\circ$对于较大的问题，可以使用 Bootstrap 迭代逼近的方法。这个算法过程如下：首先把所有的$V_0(s)$都初始化成0，然后根据V0计算V1，…，一直继续下去直到收敛。根据$V_k(s)$计算$V_{k+1}(s)$的公式如下：
$$V_{k+1}(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V_k(s^{\prime })]$$
我们可以看一下收敛的时候，Vk+1=Vk，Δ=0，那么上面的迭代公式正好就是贝尔曼方程！有了上面的迭代算法，任何给定的策略ππ，我们都可以计算出它的价值函数。

3. 策略改进：基于更新后的值函数$v_{{\pi }^{(k)}}$,贪心更新策略：

$${\pi }^{(k+1)}(s)=\arg \underset{a}{\max }\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{{\pi }^{(k)}}(s^{\prime })\right]$$

4. 检查收敛：如果策略不再变化，即${\pi }^{(k+1)}={\pi }^{(k)}$,则算法结束，${\pi }^{(k)}$
   即为最优策略；否则返回步骤 2。

策略提升定理

假设$\pi$和${\pi }^{\prime }$是两个确定的策略(一个状态s下只有一个行为a的概率是1，其余是0),如果对于所有的
$s\in {\mathcal{S}}_{\text{都有：}}$

$$q_{\pi }(s,{\pi }^{\prime }(s))\ge v_{\pi }(s)$$

那么策略${\pi }^{\prime }$比$\pi$要“好”,也就是对于所有的$s\in \mathcal{S}:$

$$v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$$

并且如果第一个不等式是严格大于，那么第二个不等式也是严格大于，也就是${\pi }^{\prime }$一定比$\pi$更好(而不
是一样)。

如果这个定理成立，那就证明了我们前面结论，因为我们新的策略在s的时候采取的满足
$q_{\pi }(s,a)\ge v_{\pi }(s)$,而其它的状态s’都是一样的，因此新的策略会更好。当然上面的新策略是随便选择一个满足条件的行为a，但更好的办法是从所有可能的a里选择$q_{\pi }(s,a)$最大的那个a，此外我们可以改变所有s的策略，而不是一个s，这个改进版本就是我们最终用到的策略提升算法。如果所有的状态，当前的a已经是$q_{\pi }(s,a)$中最大的那个呢？那说明当前策略已经是最优的策略了。下面我们来证明这个定理：
$$\begin{array}{rl}& v_{\pi }(s)\le q_{\pi }(s,{\pi }^{\prime }(s))\\ & \text{t时刻使用策略}{\pi }^{\prime },\text{t+1时刻之后还是用策略}\pi \\ & ={\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]\\ & \text{用前面的假设}\\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma q_{\pi }(S_{t+1},{\pi }^{\prime }(S_{t+1}))|S_t=s]\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma {\mathbb{E}}_{{\pi }^{\prime }}[R_{t+2}+\gamma v_{\pi }(S_{t+2})]|S_t=s]\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{v}_{\pi }(S_{t+2})|S_t=s]\\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^3{v}_{\pi }(S_{t+3})|S_t=s]\\ & \dots \\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^3{R}_{t+4}\dots +|S_t=s]\\ & =v_{{\pi }^{\prime }}(s)\end{array}$$

上面的证明就是不停的应用假设条件，里面有一点就是$E_{\pi }{E}_{\pi }X=E_{\pi }X$,因为求一次期望之后就和

$\pi$无关了，可以认为是常量了。

我们最终使用的策略是“贪心”的策略，对于所有的s，我们都选择qπ(s,a)最大的那个a。

参考文章：
https://zhuanlan.zhihu.com/p/33229439
https://hwcoder.top/RL-Note-3