Task02
本次学习主要参照Datawhale开源学习及强化学习蘑菇书Easy RL

第2章 马尔可夫决策过程

本章给大家介绍马尔可夫决策过程。

• 第一部分先介绍它的简化版本：马尔可夫链以及马尔可夫奖励过程，最后介绍马尔可夫决策过程。
• 第二部分会介绍马尔可夫决策过程中的预测问题，就是当给定一个决策过程和策略函数，怎么去计算它的价值函数。
• 第三部分会介绍马尔可夫决策过程中的控制问题，就是寻找一个最佳策略，同时输出它的最佳价值函数以及最佳策略函数。具体有两种算法：policy iteration 和 value iteration。

在强化学习中，agent 跟环境就是这样进行交互的，这个交互过程是可以通过马尔可夫决策过程来表示的，所以马尔可夫决策过程是强化学习里面的一个基本框架。

2.1 马尔可夫过程 Markov Process(MP)

MP = State + Probability

2.1.1 马尔可夫性质（Markov Property）

如果一个状态转移是符合马尔可夫的，那就是说一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系。

我们设状态的历史为 $h_t=\left\{s_1,s_2,s_3,\dots ,s_t\right\}$（$h_t$ 包含了之前的所有状态），如果一个状态转移是符合马尔可夫的，也就是满足如下条件：
$$p\left(s_{t+1}\mid s_t\right)=p\left(s_{t+1}\mid h_t\right)\text{\hspace{1em}(1)}$$
$$p\left(s_{t+1}\mid s_t,a_t\right)=p\left(s_{t+1}\mid h_t,a_t\right)\text{\hspace{1em}(2)}$$

从当前 $s_t$ 转移到 $s_{t+1}$ 这个状态，它是直接就等于它之前所有的状态转移到 $s_{t+1}$。如果某一个过程满足马尔可夫性质(Markov Property)，就是说未来的转移跟过去是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

2.1.2 马尔可夫过程/马尔可夫链（Markov Process/Markov Chain）

马尔可夫链(Markov Chain)是概率论和数理统计中具有马尔可夫性质（Markov property）且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。举个例子，这个图里面有四个状态，这四个状态从 $s_1,s_2,s_3,s_4$ 之间互相转移。比如说从 $s_1$ 开始，

• $s_1$ 有 0.1 的概率继续存活在 $s_1$ 状态，
• 有 0.2 的概率转移到 $s_2$，
• 有 0.7 的概率转移到 $s_4$ 。

我们可以用状态转移矩阵(State Transition Matrix)$P$ 来描述状态转移 $p\left(s_{t+1}=s^{\prime }\mid s_t=s\right)$，如下式所示。
$$P=\left[\begin{array}{cccc}P\left(s_1\mid s_1\right)& P\left(s_2\mid s_1\right)& \dots & P\left(s_N\mid s_1\right)\\ P\left(s_1\mid s_2\right)& P\left(s_2\mid s_2\right)& \dots & P\left(s_N\mid s_2\right)\\ ⋮& ⋮& \ddots & ⋮\\ P\left(s_1\mid s_N\right)& P\left(s_2\mid s_N\right)& \dots & P\left(s_N\mid s_N\right)\end{array}\right]$$
状态转移矩阵类似于一个 conditional probability，当我们知道当前我们在 $s_t$ 这个状态过后，到达下面所有状态$s_{t+1}$的一个概率。

2.2 马尔可夫奖励过程 Markov Reward Process(MRP)

MRP = State + Probability + Reward
马尔可夫奖励过程(Markov Reward Process, MRP)是马尔可夫链再加上了一个奖励函数。奖励函数 $R$ 是一个期望，就是说当你到达某一个状态的时候，可以获得多大的奖励。

2.2.1 回报和价值函数（Return and Value function）

这里我们进一步定义一些概念。

• Horizon 是指一个回合的长度（每个回合最大的时间步数），它是由有限个步数决定的。

• Return(回报) 说的是把奖励进行折扣后所获得的收益。Return 可以定义为奖励的逐步叠加，如下式所示：

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^3{R}_{t+4}+\dots +{\gamma }^{T-t-1}{R}_T$$

这里有一个折扣系数$\gamma$，越往后得到的奖励，折扣得越多。这说明我们其实更希望得到现有的奖励，未来的奖励就要把它打折扣。

• state value function 对于 MRP，state value function 被定义成是 return 的期望，如下式所示：
  $$\begin{array}{rl}{V}_t(s)& =\mathbb{E}\left[G_t\mid s_t=s\right]\\ & =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots +{\gamma }^{T-t-1}{R}_T\mid s_t=s\right]\end{array}$$

就是说从这个状态开始，你未来有若干条可能的状态路径，每一条路径都有不同的回报$G_t$。所以这个期望$V_t$可以看成是对未来可能状态路径获得回报的一个期望。就是当你进入某一个状态过后，你现在就有多大的价值。

这里解释一下为什么需要折扣系数。

• 有些马尔可夫过程是带环的，它并没有终结，我们想避免这个无穷的奖励。
• 我们并没有建立一个完美的模拟环境的模型，所以未来是不确定的。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
• 如果这个奖励是有实际价值的，我们可能是更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。。

Discount factor 可以作为强化学习 agent 的一个超参数来进行调整，然后就会得到不同行为的 agent。

2.2.2 贝尔曼等式（Bellman Equation）

Bellman Equation 就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。Bellman Equation 因其提出者、动态规划创始人 Richard Bellman 而得名 ，也叫作“动态规划方程”

Bellman Equation（贝尔曼等式） 如下式所示：
$$V(s)=\underset{\text{Immediate reward }}{\underbrace{R(s)}}+\underset{\text{Discounted sum of future reward }}{\underbrace{\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s\right)V\left(s^{\prime }\right)}}$$
其中：

• $s^{\prime }$ 可以看成未来的所有状态。
• 转移 $P(s^{\prime }|s)$ 是指从当前状态转移到未来状态的概率。
• $V(s^{\prime })$ 代表的是未来某一个状态的价值。

Bellman Equation 定义了当前状态跟未来状态之间的这个关系。当前立刻可以得到的奖励+未来打了折扣的奖励，就组成了这个 Bellman Equation。

Bellman equation 的推导过程如下：
$$\begin{array}{rl}V(s)& =\mathbb{E}\left[G_t\mid s_t=s\right]\\ & =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid s_t=s\right]\\ & =\mathbb{E}\left[R_{t+1}|s_t=s\right]+\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+{\gamma }^2{R}_{t+4}+\dots \mid s_t=s\right]\\ & =R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s]\\ & =R(s)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s]\\ & =R(s)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s\right)V\left(s^{\prime }\right)\end{array}$$

我们可以把 Bellman Equation 写成一种矩阵的形式，如下式所示。
$$\left[\begin{array}{c}V\left(s_1\right)\\ V\left(s_2\right)\\ ⋮\\ V\left(s_N\right)\end{array}\right]=\left[\begin{array}{c}R\left(s_1\right)\\ R\left(s_2\right)\\ ⋮\\ R\left(s_N\right)\end{array}\right]+\gamma \left[\begin{array}{cccc}P\left(s_1\mid s_1\right)& P\left(s_2\mid s_1\right)& \dots & P\left(s_N\mid s_1\right)\\ P\left(s_1\mid s_2\right)& P\left(s_2\mid s_2\right)& \dots & P\left(s_N\mid s_2\right)\\ ⋮& ⋮& \ddots & ⋮\\ P\left(s_1\mid s_N\right)& P\left(s_2\mid s_N\right)& \dots & P\left(s_N\mid s_N\right)\end{array}\right]\left[\begin{array}{c}V\left(s_1\right)\\ V\left(s_2\right)\\ ⋮\\ V\left(s_N\right)\end{array}\right]$$
当我们把 Bellman Equation 写成矩阵形式后，可以直接求解：
$$\begin{array}{rl}V& =R+\gamma PV\\ IV& =R+\gamma PV\\ (I-\gamma P)V& =R\\ V& =(I-\gamma P{)}^{-1}R\end{array}$$

我们可以直接得到一个解析解(analytic solution):
$$V=(I-\gamma P{)}^{-1}R$$
我们可以通过矩阵求逆把这个 V 的这个价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 $O(N^3)$。所以当状态非常多的时候，比如说从十个状态到一千个状态，到一百万个状态。那么当我们有一百万个状态的时候，这个转移矩阵就会是个一百万乘以一百万的矩阵，这样一个大矩阵的话求逆是非常困难的，所以这种通过解析解去求解的方法只适用于很小量的 MRP。

2.2.3 价值函数求解（Computing Value of a MRP）

接下来我们来求解这个价值函数。我们可以通过迭代的方法来解这种状态非常多的 MRP(large MRPs)，比如说：

• 动态规划的方法。通过迭代的方法计算。
• 蒙特卡罗的方法。通过采样的方法计算。
• 时序差分学习的方法。 Temporal-Difference Learning 叫 TD Leanring，它是动态规划和蒙特卡罗的一个结合。

蒙特卡罗(Monte Carlo)方法 蒙特卡罗就是说当得到一个 MRP 过后，我们可以从某一个状态开始，把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的折扣的奖励 $g$ 算出来。算出来过后就可以把它积累起来，得到 return $G_t$。 当积累到一定的轨迹数量过后，直接用 $G_t$ 除以轨迹数量，就会得到它的价值。

动态规划的办法 先对所有未来时刻状态价值函数$V(s^{\prime })$初始化为0或其对应的奖励，然后根据 Bellman equation计算当前时刻状态价值函数$V^{\prime }(s)$，再用$V^{\prime }(s)$值替换$V(s^{\prime })$值计算一个新的$V^{\prime }(s)$，直到两次相邻迭代得到的$V^{\prime }(s)$值收敛。这时我们就可以输出最新的 $V^{\prime }(s)$ 作为它当前的状态价值函数$V(s)$。所以这里就是把 Bellman Equation 变成一个 Bellman Update，这样就可以得到它的一个价值。

动态规划的方法基于后继状态值的估计来更新状态值的估计。也就是说，它们根据其他估算值来更新估算值。我们称这种基本思想为 bootstrapping。

例：马尔可夫奖励过程如下图，计算回报$G_t$和状态价值函数$V_t(S)$：

a、回报$G_t$计算示例
从马尔可夫奖励过程中采样如下4个马尔科夫链，计算当$\gamma$= 1/2时，在t=1时刻$S_1=C_1$时状态$S_1$的采样回报分别为：

b、状态价值函数$V_t(S)$计算示例
现在采用动态规划法计算上图中状态的价值函数$V_t(S)$，状态FB,Pub,C1,C2,C3,Pass,Sleep的价值函数的初始值，可以初始化为0，或者其对应的奖励。

FB状态时，有0.9的概率进入FB，0.1的概率进入到C1，因此：
$V(F{B}^{\prime })=0.9\ast [-1+\gamma \ast V(FB)]+0.1\ast [-1+\gamma \ast V(C1)]$
同理有：
$V(Pu{b}^{\prime })=0.2\ast [1+\gamma \ast V(C1)]+0.4\ast [1+\gamma \ast V(C2)]+0.4\ast [1+\gamma \ast V(C3)]$
$V(C{1}^{\prime })=0.5\ast [-2+\gamma \ast V(C2)]+0.5\ast [-2+\gamma \ast V(FB)]$
$V(C{2}^{\prime })=0.2\ast [-2+\gamma \ast V(Sleep)]+0.8\ast [-2+\gamma \ast V(C3)]$
$V(C{3}^{\prime })=0.6\ast [-2+\gamma \ast V(Pass)]+0.4\ast [-2+\gamma \ast V(pub)]$
$V(Pass)=1\ast [10+\gamma \ast V(Sleep)]$

第一步迭代V(FB),V(Pub),V(C1),V(C2),V(C3),V(Pass)都为0：
$V(F{B}^{\prime })=0.9\ast [-1+0.9\ast 0]+0.1\ast [-1+0.9\ast 0]$=-1
$V(Pu{b}^{\prime })=0.2\ast [1+0.9\ast 0]+0.4\ast [1+0.9\ast 0]+0.4\ast [1+0.9\ast 0]$=1
$V(C{1}^{\prime })=0.5\ast [-2+0.9\ast 0]+0.5\ast [-2+0.9\ast 0]$=-2
$V(C{2}^{\prime })=0.2\ast [-2+0.9\ast 0]+0.8\ast [-2+0.9\ast 0]$=-2
$V(C{3}^{\prime })=0.6\ast [-2+0.9\ast 0]+0.4\ast [-2+0.9\ast 0]$=-2
$V(Pass)=1\ast [10+0.9\ast 0]$=10

第二步迭代V(FB)=-1, V(Pub)=1, V(C1)=-2, V(C2)=-2, V(C3)=-2, V(Pass)=10：
$V(F{B}^{\prime })=0.9\ast [-1+0.9\ast -1]+0.1\ast [-1+0.9\ast -1]$=-1.99
$V(Pu{b}^{\prime })=0.2\ast [1+0.9\ast -2]+0.4\ast [1+0.9\ast -2]+0.4\ast [1+0.9\ast -2]$=-0.8
$V(C{1}^{\prime })=0.5\ast [-2+0.9\ast -1]+0.5\ast [-2+0.9\ast -2]$=-3.35
$V(C{2}^{\prime })=0.2\ast [-2+0.9\ast 0]+0.8\ast [-2+0.9\ast -2]$=-3.44
$V(C{3}^{\prime })=0.6\ast [-2+0.9\ast 10]+0.4\ast [-2+0.9\ast 1]$=-1.64
$V(Pass)=1\ast [10+0.9\ast 0]$=10

第三步迭代V(FB)=-1.99, V(Pub)=-0.8, V(C1)=-3.35, V(C2)=-3.44, V(C3)=-1.64, V(Pass)=10
…

当迭代次数到30次左右时，各状态的值趋于稳定（即迭代次数增加，各状态价值函数只有微小的变化）
V(FB)=-7.6, V(Pub)=1.9, V(C1)=-5, V(C2)=0.9, V(C3)=4.1, V(Pass)=10。

2.3 马尔可夫决策过程 Markov Decision Process(MDP)

MDP = State + Probability + Reward + Action

相对于 MRP，马尔可夫决策过程(Markov Decision Process)多了一个决策函数，其它的定义跟 MRP 都是类似的：

• 这里多了一个决策，多了一个动作。
• 状态转移函数也多了一个条件，变成了 $P\left(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a\right)$。未来的状态不仅是依赖于你当前的状态，也依赖于在当前状态 agent 采取的这个动作。
• 价值函数也是多了一个条件，变成了 $R\left(s_t=s,a_t=a\right)=\mathbb{E}\left[r_t\mid s_t=s,a_t=a\right]$。你当前的状态以及你采取的动作会决定你在当前可能得到的奖励多少。

2.3.1 策略（Policy in MDP）

• Policy 定义了在某一个状态应该采取什么样的动作。

• 知道当前状态过后，我们可以把当前状态带入 policy function，然后就会得到一个概率，即
  $$\pi (a\mid s)=P\left(a_t=a\mid s_t=s\right)$$

概率就代表了在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率往左走，有 0.3 的概率往右走，这是一个概率的表示。

• 另外这个策略也可能是确定的，它有可能是直接输出一个值。或者就直接告诉你当前应该采取什么样的动作，而不是一个动作的概率。

• 假设这个概率函数应该是稳定的(stationary)，不同时间点，你采取的动作其实都是对这个 policy function 进行采样。

我们可以将 MRP 转换成 MDP。已知一个 MDP 和一个 policy $\pi$ 的时候，我们可以把 MDP 转换成 MRP。在 MDP 里面，转移函数 $P(s^{\prime }|s,a)$ 是基于它当前状态以及它当前的 action。因为我们现在已知它 policy function，就是说在每一个状态，我们知道它可能采取的动作的概率，那么就可以直接把这个 action 进行加和，直接把这个 a 去掉，那我们就可以得到对于 MRP 的一个转移，这里就没有 action。

$$P^{\pi }\left(s^{\prime }\mid s\right)=\sum _{a\in A}\pi (a\mid s)P\left(s^{\prime }\mid s,a\right)$$

对于这个奖励函数，我们也可以把 action 拿掉，这样就会得到一个类似于 MRP 的奖励函数。

$$R^{\pi }(s)=\sum _{a\in A}\pi (a\mid s)R(s,a)$$

2.3.2 价值函数（Value function for MDP）

顺着 MDP 的定义，我们可以把 状态-价值函数(state-value function)，就是在 MDP 里面的价值函数也进行一个定义，它的定义是跟 MRP 是类似的，如式 (3) 所示：
$$v^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t\mid s_t=s\right]$$
但是这里 expectation over policy，就是这个期望是基于你采取的这个 policy ，就当你的 policy 决定过后，我们通过对这个 policy 进行采样来得到一个期望，那么就可以计算出它的这个价值函数。

这里我们另外引入了一个动作-价值函数 Q 函数(Q-function)。Q 函数也被称为 action-value function。Q 函数定义的是在某一个状态采取某一个动作，它有可能得到的这个 return 的一个期望，如式 (4) 所示：
$$q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t\mid s_t=s,A_t=a\right]$$
这里期望其实也是 over policy function。所以你需要对这个 policy function 进行一个加和，然后得到它的这个价值。对 Q 函数中的动作函数进行加和，就可以得到价值函数：
$$v^{\pi }(s)=\sum _{a\in A}\pi (a\mid s)q^{\pi }(s,a)$$
Q-function Bellman Equation

此处我们给出 Q 函数的 Bellman equation：

$$\begin{array}{rl}q(s,a)& =\mathbb{E}\left[G_t\mid s_t=s,a_t=a\right]\\ & =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid s_t=s,a_t=a\right]\\ & =\mathbb{E}\left[R_{t+1}|s_t=s,a_t=a\right]+\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+{\gamma }^2{R}_{t+4}+\dots \mid s_t=s,a_t=a\right]\\ & =R(s,a)+\gamma \mathbb{E}[G_{t+1}|s_t=s,a_t=a]\\ & =R(s,a)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s,a_t=a]\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)V\left(s^{\prime }\right)\end{array}$$

2.3.3 贝尔曼期望方程 Bellman Expectation Equation

我们可以把状态-价值函数和 Q 函数拆解成两个部分：即时奖励(immediate reward) 和后续状态的折扣价值(discounted value of successor state)。

通过对状态-价值函数进行一个分解，我们就可以得到一个类似于之前 MRP 的 Bellman Equation，这里叫 Bellman Expectation Equation：
$$v^{\pi }(s)=E_{\pi }\left[R_{t+1}+\gamma v^{\pi }\left(s_{t+1}\right)\mid s_t=s\right]$$
对于 Q 函数，我们也可以做类似的分解，也可以得到 Q 函数的 Bellman Expectation Equation：
$$q^{\pi }(s,a)=E_{\pi }\left[R_{t+1}+\gamma q^{\pi }\left(s_{t+1},A_{t+1}\right)\mid s_t=s,A_t=a\right]$$
Bellman expectation equation 定义了你当前状态跟未来状态之间的一个关联。

我们进一步进行一个简单的分解。

$$v^{\pi }(s)=\sum _{a\in A}\pi (a\mid s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{\pi }\left(s^{\prime }\right)\right)$$

$$q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)\sum _{a^{\prime }\in A}\pi \left(a^{\prime }\mid s^{\prime }\right)q^{\pi }\left(s^{\prime },a^{\prime }\right)$$

上面两式是 Bellman expectation equation 的另一种形式。

2.3.4 预测和控制概念（Prediction and Control）

MDP 的 prediction 和 control 是 MDP 里面的核心问题。

• 预测问题：

  • 输入：MDP $<S,A,P,R,\gamma >$ 和 policy $\pi$ 或者 MRP $<S,P^{\pi },R^{\pi },\gamma >$。
  • 输出：value function $v^{\pi }$。
  • Prediction 是说给定一个 MDP 以及一个 policy $\pi$ ，去计算它的 value function，就对于每个状态，它的价值函数是多少。

• 控制问题：

  • 输入：MDP $<S,A,P,R,\gamma >$。
  • 输出：最佳价值函数(optimal value function) $v^{\ast }$ 和最佳策略(optimal policy) ${\pi }^{\ast }$。
  • Control 就是说我们去寻找一个最佳的策略，然后同时输出它的最佳价值函数以及最佳策略。

在 MDP 里面，prediction 和 control 都可以通过动态规划去解决。这两者的区别就在于，预测问题是给定一个 policy，我们要确定它的 value function 是多少。而控制问题是在没有 policy 的前提下，我们要确定最优的 value function 以及对应的决策方案。实际上，这两者是递进的关系，在强化学习中，我们通过解决预测问题，进而解决控制问题。

举一个例子来说明 prediction 与 control 的区别。

首先是预测问题：

• 在下图的方格中，我们规定从 A $\to$ A’ 可以得到 +10 的奖励，从 B $\to$ B’ 可以得到 +5 的奖励，其它步骤的奖励为 -1。
• 现在，我们给定一个 policy：在任何状态中，它的行为模式都是随机的，也就是上下左右的概率各 25%。
• 预测问题要做的就是，在这种决策模式下，我们的 value function 是什么。下图 b 是对应的 value function。
  

接着是控制问题：

• 在控制问题中，问题背景与预测问题相同，唯一的区别就是：不再限制 policy。也就是说行为模式是未知的，我们要自己确定。

• 所以我们通过解决控制问题，求得每一个状态的最优的 value function（如下图 b 所示），也得到了最优的 policy（如下图 c 所示）。

• 控制问题要做的就是，给定同样的条件，在所有可能的策略下最优的价值函数是什么？最优策略是什么？
  

动态规划能够完成预测问题和控制问题的求解，是解 MDP prediction 和 control 一个非常有效的方式。动态规划(Dynamic Programming，DP)适合解决满足如下两个性质的问题：

• 最优子结构(optimal substructure)。最优子结构意味着，我们的问题可以拆分成一个个的小问题，通过解决这个小问题，最后，我们能够通过组合小问题的答案，得到大问题的答案，即最优的解。
• 重叠子问题(Overlapping subproblems)。重叠子问题意味着，子问题出现多次，并且子问题的解决方案能够被重复使用。

MDP 是满足动态规划的要求的，

• 在 Bellman equation 里面，我们可以把它分解成一个递归的结构。当我们把它分解成一个递归的结构的时候，如果我们的子问题子状态能得到一个值，那么它的未来状态因为跟子状态是直接相连的，那我们也可以继续推算出来。
• 价值函数就可以储存并重用它的最佳的解。

动态规划应用于 MDP 的规划问题(planning)而不是学习问题(learning)，我们必须对环境是完全已知的(Model-Based)，才能做动态规划，直观的说，就是要知道状态转移概率和对应的奖励才行

2.3.5 预测问题求解

预测 Policy evaluation 也叫 （value）prediction，它的核心思想就是把如下式所示的 Bellman expectation backup 拿出来反复迭代，然后就会得到一个收敛的价值函数的值。
$$v_{t+1}(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}P\left(s^{\prime }\mid s,a\right)v_t\left(s^{\prime }\right)\right)\text{\hspace{1em}(15)}$$
因为已经给定了这个函数的 policy function，那我们可以直接把它简化成一个 MRP 的表达形式，这样的话，形式就更简洁一些，就相当于我们把这个 $a$ 去掉，如下式所示：
$$v_{t+1}(s)=R^{\pi }(s)+\gamma P^{\pi }\left(s^{\prime }\mid s\right)v_t\left(s^{\prime }\right)\text{\hspace{1em}(16)}$$
这样它就只有价值函数跟转移函数了。通过去迭代这个更简化的一个函数，我们也可以得到它每个状态的价值。因为不管是在 MRP 以及 MDP，它的价值函数包含的这个变量都是只跟这个状态有关，就相当于进入某一个状态，未来可能得到多大的价值。

2.3.6 控制问题求解

控制 问题是说如果我们只有一个 MDP，如何去寻找一个最佳的策略，然后可以得到一个最佳价值函数(Optimal Value Function)。

Optimal Value Function 的定义如下式所示：
$$v^{\ast }(s)=\underset{\pi }{\max }{v}^{\pi }(s)$$
Optimal Value Function 是说，我们去搜索一种 policy $\pi$ 来让每个状态的价值最大。$v^{\ast }$ 就是到达每一个状态，它的值的极大化情况。

在这种极大化情况上面，我们得到的策略就可以说它是最佳策略(optimal policy)，如下式所示：
$${\pi }^{\ast }(s)=\underset{\pi }{\mathrm{argmax}}{v}^{\pi }(s)$$
Optimal policy 使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个 optimal value function，就可以说某一个 MDP 的环境被解。在这种情况下，它的最佳的价值函数是一致的，就它达到的这个上限的值是一致的，但这里可能有多个最佳的 policy，就是说多个 policy 可以取得相同的最佳价值。

最简单的策略搜索办法就是穷举。但是穷举非常没有效率，所以我们要采取其他方法。搜索最佳策略有两种常用的方法：policy iteration 和 value iteration。

2.3.6.1 策略迭代（Policy Iteration）

Policy iteration 由两个步骤组成：policy evaluation 和 policy improvement。

• 第一个步骤是 policy evaluation，当前我们在优化这个 policy $\pi$，在优化过程中得到一个最新的 policy。我们先保证这个 policy 不变，然后去估计它出来的这个价值。给定当前的 policy function 来估计这个 v 函数。
• 第二个步骤是 policy improvement，得到 v 函数过后，我们可以进一步推算出它的 Q 函数。得到 Q 函数过后，我们直接在 Q 函数上面取极大化，通过在这个 Q 函数上面做一个贪心的搜索来进一步改进它的策略。

第一个步骤：policy iteration。在初始化的时候，我们有一个初始化的 $V$ 和 $\pi$ ，然后就是在这两个过程之间迭代。左边这幅图上面的线就是我们当前 v 的值，下面的线是 policy 的值。跟踢皮球一样，我们先给定当前已有的这个 policy function，然后去算它的 v。算出 v 过后，我们会得到一个 Q 函数。Q 函数我们采取 greedy 的策略，这样就像踢皮球，踢回这个 policy 。然后进一步改进那个 policy ，得到一个改进的 policy 过后，它还不是最佳的，我们再进行 policy evaluation，然后又会得到一个新的 value function。基于这个新的 value function 再进行 Q 函数的极大化，这样就逐渐迭代，然后就会得到收敛。

第二个步骤： policy improvement。得到这个 v 值过后，我们就可以通过这个 reward function 以及状态转移把它的这个 Q-function 算出来，如下式所示：
$$q^{{\pi }_i}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{{\pi }_i}\left(s^{\prime }\right)$$
对于每一个状态，第二个步骤会得到它的新一轮的这个 policy ，就在每一个状态，我们去取使它得到最大值的 action，如下式所示：
$${\pi }_{i+1}(s)=\underset{a}{\mathrm{argmax}}{q}^{{\pi }_i}(s,a)$$
你可以把 Q 函数看成一个 Q-table:

• 横轴是它的所有状态，
• 纵轴是它的可能的 action。

得到 Q 函数后，Q-table也就得到了。

那么对于某一个状态，每一列里面我们会取最大的那个值，最大值对应的那个 action 就是它现在应该采取的 action。所以 arg max 操作就说在每个状态里面采取一个 action，这个 action 是能使这一列的 Q 最大化的那个动作。

Bellman Optimality Equation

当一直在采取 arg max 操作的时候，我们会得到一个单调的递增。通过采取这种 greedy，即 arg max 操作，我们就会得到更好的或者不变的 policy，而不会使它这个价值函数变差。所以当这个改进停止过后，我们就会得到一个最佳策略。

当改进停止过后，我们取它最大化的这个 action，它直接就会变成它的价值函数，如下式所示：
$$q^{\pi }\left(s,{\pi }^{\prime }(s)\right)=\underset{a\in \mathcal{A}}{\max }{q}^{\pi }(s,a)=q^{\pi }(s,\pi (s))=v^{\pi }(s)$$
所以我们有了一个新的等式：
$$v^{\pi }(s)=\underset{a\in \mathcal{A}}{\max }{q}^{\pi }(s,a)$$
上式被称为 Bellman optimality equation。从直觉上讲，Bellman optimality equation 表达了这样一个事实：最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。

最佳的价值函数到达过后，这个 Bellman optimlity equation 就会满足。

满足过后，就有这个 max 操作，如第一个等式所示：
$$v^{\ast }(s)=\underset{a}{\max }{q}^{\ast }(s,a)$$
当我们取最大的这个 action 的时候对应的值就是当前状态的最佳的价值函数。

另外，我们给出第二个等式，即 Q 函数的 Bellman equation：
$$q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{\ast }\left(s^{\prime }\right)$$
我们可以把第一个等式插入到第二个等式里面去，如下式所示：
$$\begin{array}{rl}{q}^{\ast }(s,a)& =R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{\ast }\left(s^{\prime }\right)\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)\underset{a}{\max }{q}^{\ast }(s^{\prime },a^{\prime })\end{array}$$
我们就会得到 Q 函数之间的转移。它下一步这个状态，取了 max 这个值过后，就会跟它最佳的这个状态等价。Q-learning 是基于 Bellman Optimality Equation 来进行的，当取它最大的这个状态的时候（ $\underset{a^{\prime }}{\max }{q}^{\ast }\left(s^{\prime },a^{\prime }\right)$ ），它会满足下面这个等式：
$$q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)\underset{a^{\prime }}{\max }{q}^{\ast }\left(s^{\prime },a^{\prime }\right)$$

我们还可以把第二个等式插入到第一个等式，如下式所示：
$$\begin{array}{rl}{v}^{\ast }(s)& =\underset{a}{\max }{q}^{\ast }(s,a)\\ & =\underset{a}{\max }\mathbb{E}[G_t|s_t=s,a_t=a]\\ & =\underset{a}{\max }\mathbb{E}[R_{t+1}+\gamma G_{t+1}|s_t=s,a_t=a]\\ & =\underset{a}{\max }\mathbb{E}[R_{t+1}+\gamma v^{\ast }(s_{t+1})|s_t=s,a_t=a]\\ & =\underset{a}{\max }\mathbb{E}[R_{t+1}]+\underset{a}{\max }\mathbb{E}[\gamma v^{\ast }(s_{t+1})|s_t=s,a_t=a]\\ & =\underset{a}{\max }R(s,a)+\underset{a}{\max }\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{\ast }\left(s^{\prime }\right)\\ & =\underset{a}{\max }\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)v^{\ast }\left(s^{\prime }\right)\right)\end{array}$$
我们就会得到状态-价值函数的一个转移。

2.3.6.2 价值迭代（Value Iteration）

我们从另一个角度思考问题，动态规划的方法将优化问题分成两个部分：

• 第一步执行的是最优的 action；
• 之后后继的状态每一步都按照最优的 policy 去做，那么我最后的结果就是最优的。

Principle of Optimality Theorem

一个 policy $\pi (s|a)$ 在状态 $s$ 达到了最优价值，也就是 $v^{\pi }(s)=v^{\ast }(s)$ 成立，当且仅当：

对于任何能够从 $s$ 到达的 $s^{\prime }$，都已经达到了最优价值，也就是，对于所有的 $s^{\prime }$，$v^{\pi }(s^{\prime })=v^{\ast }(s^{\prime })$ 恒成立。

Deterministic Value Iteration

Value iteration 就是把 Bellman Optimality Equation 当成一个 update rule 来进行，如下式所示：
$$v(s)\leftarrow \underset{a\in \mathcal{A}}{\max }\left(R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}P\left(s^{\prime }\mid s,a\right)v\left(s^{\prime }\right)\right)$$
之前我们说上面这个等式只有当整个 MDP 已经到达最佳的状态时才满足。但这里可以把它转换成一个 backup 的等式。Backup 就是说一个迭代的等式。我们不停地去迭代 Bellman Optimality Equation，到了最后，它能逐渐趋向于最佳的策略，这是 value iteration 算法的精髓。

为了得到最佳的 $v^{\ast }$ ，对于每个状态的 $v^{\ast }$，我们直接把这个 Bellman Optimality Equation 进行迭代，迭代了很多次之后，它就会收敛。

提取最佳策略的话，我们可以直接用 arg max。就先把它的 Q 函数重构出来，重构出来过后，每一个列对应的最大的那个 action 就是它现在的最佳策略。这样就可以从最佳价值函数里面提取出最佳策略。

value function 做的工作类似于 value 的反向传播，每次迭代做一步传播，所以中间过程的 policy 和 value function 是没有意义的。不像是 policy iteration，它每一次迭代的结果都是有意义的，都是一个完整的 policy。

2.3.6.3 预测和控制总结（Summary for Prediction and Control in MDP）

MDP 里面的 prediction 和 control 都是用动态规划来解，我们其实采取了不同的 Bellman Equation。

• 对于 prediction 的问题，即 policy evaluation 的问题，直接就是不停地 run 这个 Bellman Expectation Equation，这样我们就可以去估计出给定的这个策略，然后得到价值函数。
• 对于 control 的问题，如果采取的算法是 policy iteration，那这里用的是 Bellman Expectation Equation 。把它分成两步，先算它的价值函数，再去优化它的策略，然后不停迭代。如果采取的算法是 value iteration，那这里用到的 Bellman Equation 就是 Bellman Optimality Equation，通过 arg max 这个过程，不停地去 arg max 它，最后它就会达到最优的状态。