强化学习课程学习系列笔记，RL Course by David Silve，按照课程顺序，每节课一篇博客笔记，主要记录课程内容和个人理解。
1. Introduction
前言：这一节课学习动态规划DP，作为曾经的算法竞赛选手，可以说是DNA动了，信竞中的DP最经典就是背包问题，一个NP完全问题，通过空间换时间的思想存储状态，可以将求解的时间复杂度大大缩短，不知道RL中的动态规划和信竞中的动态规划是不是一样的概念。
不过，从上节马尔科夫决策过程来看，Value Function的迭代推导就是一个动态规划中的状态转移方程（这里的状态不是RL中是state）——当前步骤的收益+ max(下一状态的收益) 就是最优解。最大的区别可能在于，MDP中都是基于概率的，是对未来的一种预测，竞赛题目中的背景通常给的是一个确定的收益。
上述只是在看课前的胡扯，不一定对，看完也不改，学完这节课再回头看看理解有多少偏差。
1.1 Requirements for Dynamic Programming
Dynamic Programming （DP）动态规划是一个用于解决复杂问题最优化的方法，如果一个问题可以使用DP来解决，必须满足以下两个性质，我们可以发现Markov decision process MDP天然具备这两个性质：
- 最优子结构 Optimal substructure：问题的最优解包含子问题的最优解，这一性质确保了我们可以通过求导子问题的最优解，推导出问题的最优解。MDP中Bellman equation将value function的求解递归得分解成了两个子问题—— $v(s) =\mathcal{R}_{s}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}} v\left(s^{\prime}\right)$ ，当前状态的Reward，以及后继状态的Value期望。
- 重叠子问题 Overlapping subproblems：指在解决一个问题的过程中，会多次遇到相同的子问题。因此，我们可以将这些子问题进行存储，再次遇到这一子问题就可以查表得到问题的解，以此减少计算开销。在MDP中，Value Function的求解依赖于其他状态的Value Function，并且状态之间可能多次转移，将每个状态的Value求解当做一个子问题，那么每个子问题在Value Function求解过程中就会多次遇到，为重叠子问题。
1.2 Planning by Dynamic Programming
DP需要获取MDP的所有信息，因此只能用于Planning（工作环境是已知，被告知了整个环境的运作规则的详细信息。在这种情况下智能体不用实时地与环境交互就能知道未来环境，只需要知道当前的状态，就能够开始思考，来寻找最优解。）主要有两种问题：
- 预测（Prediction）: 给你一个policy，计算这个policy能够得到多少reward，这是一个预估未来的过程。
- 控制（Control）: 确定众多决策中，哪一个决策能够得到最多的奖励。
1.3 Other Applications of Dynamic Programming
这些也是耳熟能详了，计算机专业的应该都了解过，所以这里讲的DP就是信竞中经常出现的DP。
2. Policy Evaluation
我们给定一个问题：evaluate a given policy $\pi$，即获得基于 $\pi$ 的 value function
解决方法是：迭代得进行Bellman expection backup，这里的迭代指的是从一组初始的value function $V_1$ 开始，迭代更新，得到$V_2, V_3,…,V_{\pi}$，同时我们使用synchronous backups来存储value function，即在每个迭代iteration$k+1$时，对于所有的状态 $s \in \mathcal{S}$ ，我们根据 $v_k({s^{\prime}})$ 更新所有的 $v_{k+1}(s)$ ，其中 $s^{\prime}$ 表示 $s$ 的后继状态。这样的操作保证是一定能收敛的，在后面会给出证明。下面是上述操作的示意图和对应公式：
以一个棋盘格的问题为例，规则如下：
我们可以迭代得到下述结果，$k$ 表示迭代次数，第一列网格是每个状态的value，它是基于均匀分布的一个随机Policy求得的，第二列表示的是基于计算得到的value，基于贪心思想得来的一个Policy：
- $k=0$ 时，每个状态的value初始化为0
- $k=1$ 时，我们可以得到左上角和右下角的value为0，因为这是终止状态。其余格子value都为-1，这是因为无论朝哪个格子移动都会产生即时的reward=-1，而$k=0$时所有格子value都是0，即所有格子的所有可能后继状态在$k=0$时的value都是0.
- $k=2$ 时，我们以第一行第二列的格子的value计算为例：此状态下有四种action，即向东南西北四个方向移动。其中向北移动会回到原点，即时reward=-1，原点在 $k=1$ 时的value=-1，则向北的action导致的value为-2。同理，向东和向南的value也都为-2. 而向西，会到达终止点，即时reward还是-1，但是到达的后继状态（终止状态）在 $k=1$ 时的value为0，因此总value为-1. 四个action的概率都是0.25，因此在 $k=2$ 我们更新第一行第二列的格子value=0.25 * (-2) * 3 + 0.25*(-1) = -1.75，图中由于空间限制，显示为-1.7
- 依次类推，我们可以得到收敛时所有状态的value
以上过程获得的value仅仅表示基于均匀分布的随机policy $\pi$ 的所有状态value，这里的policy显然不是一个最优的策略。我们可以依据得到的value去更新Policy，得到更优的策略，如上图中第二列的网格所示。策略为，在每个state，我们都选择value值最大的state去转移，要实现这一转移的action就组成了一套贪心的Policy。
3. Policy Iteration
3.1 Iteration Process
上面介绍了如何迭代式的去评测一个Policy如何，即获得某个Policy对应的所有状态value，但我们最终的目的是获得一个最优的Policy，而不只是评测。其实上面的例子已经提到了如何优化Policy了，就是基于贪心的思想，选择value最大的state去转移即可。上述的棋盘例子只是一个非常简单的例子，仅通过evaluate均匀分布的policy，然后根据evaluation的结果贪心选择策略得到的policy就是最优的。然而，在真实情况下，一般是需要多次迭代的，也就是说我们从一个初始的Policy开始，评测这个Policy，然后基于评测结果，利用贪心思想更新初始的Policy，然后再评测更新后的Policy，然后再更新，再评测，如此迭代反复，最终收敛得到最优Policy，上述过程就是Policy Iteration，如下图的示意图所示。
3.2 Improve
下面证明上述Policy迭代的正确性：
为了简单形式，我们考虑确定性的Policy 即 $a = \pi(s)$ ，根据上述的Policy iteration，我们每次迭代优化Policy的过程可以表述为：$\pi'(s) = \arg\max_{a \in \mathcal{A}} q_{\pi}(s, a)$. 由于我们可以得到下面的关系，因为我们的 $\pi^{\prime}$ 每次选择的是使得 $q_{\pi}(s, a)$ 最大的一个action，那么肯定 $q_{\pi}(s, \pi'(s)) = \geq q_{\pi}(s, \pi(s))$，即：
q_{\pi}(s, \pi'(s)) = \max_{a \in \mathcal{A}} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s)) = v_{\pi}(s)
$$
因此，每次优化Policy实际上就是在优化value function，即 $v_{\pi’}(s) \geq v_{\pi}(s)$：
\begin{aligned}
v_{\pi}(s) &\leq q_{\pi}(s, \pi'(s)) = \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s \right]\\
&\leq \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma q_{\pi}(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s \right]\\
&\leq \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 q_{\pi}(S_{t+2}, \pi'(S_{t+2})) \mid S_t = s \right]\\
&\leq \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \mid S_t = s \right] = v_{\pi'}(s)\\
\end{aligned}
$$
所以，一旦无法进行更新，即：
q_{\pi}(s, \pi'(s)) = \max_{a \in \mathcal{A}} q_{\pi}(s, a) = q_{\pi}(s, \pi(s)) = v_{\pi}(s)
$$
可以发现，上述式子满足Bellman optimality equation的定义：$v_{\pi}(s) = \max_{a \in \mathcal{A}} q_{\pi}(s, a)$，因此，此刻的value就是最优的value，也就代表此时的policy就是最优的policy
3.3 Modified Policy Iteration
实际上，在迭代的过程中，我们不一定需要保证evaluate某个policy时的那个迭代过程收敛，即value function不一定要是最终的状态，只要能体现出整体上贪心的策略就行。比如棋盘例子中，我们发现当 $k=3$时，即使value function没有收敛，我们也可以得到一个此刻最优的policy，与收敛时得到的结果没有区别。
于是自然可以想到，我们是否需要设置一个条件来限制 policy evaluation 的迭代次数？其实，当我们限制迭代次数为1时，就是 value iteration，在下一节就要介绍到。
4. Value Iteration
4.1 Principle of Optimality
一个最优的Policy可以进一步看做两个步骤：首先进行最优的初始动作，然后再后继状态继续采取最优的动作，那么整体就是最优的。根据这一思想可以延伸到value的最优：一个Policy在某个状态 $s$ 达到最优的value，当且只当任何的后继状态在该Policy下都能达到最优的value。
4.2 Deterministic Value Iteration
如果我们知道所有子问题$v_*(s^{\prime})$的解，也就是说我们知道所有后继状态的最优行动方式，我们就只需要使得下式最大即可：
v_{*}(s) \leftarrow \max _{a \in \mathcal{A}} \mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)
$$
以棋盘格为例，没走一格的reward是-1，可以朝四个方向走，黑色格子是终点，出界会返回原点。如果求每个状态的最优value，就可以通过迭代的方式去进行，每次选择最优的action使得即时reward和后继状态的最优value期望之和最大。这里我们在每次迭代会存储每个state的value，因此，每次更新时，只需要查找上一个迭代步中后继状态的value即可。由于这里的state转移是Deterministic的，换句话说，在你采取某个action后，比如向左移动，则状态一定会转移到左边一格的位置，不会存在一定的概率转移到其他格子。所以 $\mathcal{P}_{s s^{\prime}}^{a} = 1$.
4.3 Value Iteration
Value Iteration的主要定义如下，其实这一流程和Policy Evaluation非常相似，唯一区别就是Policy Evaluation只需要对Policy进行衡量，使用的是 Bellman expection backup，优化是在Policy improvement进行的；而 Value Iteration 要求找到最优的value function，所以在迭代的过程中直接寻找了每个value的可能最大值，使用Bellman optimality backup.
下面通过图示的方式对比Policy Evaluation和Value Iteration，更加清晰直观，两者流程上没有区别，只是在每次更新时使用不同的公式：
以下是一个对于上面介绍的几种Iteration的比较。
其实说白了，Value Iteration就是将Policy Iteration的两部迭代整合到了一起，没有显式得定义Policy，而是通过直接优化Value的方式间接获得最优Policy.
