Markov Property
马尔科夫性质指的是状态转移的方程与历史状态无关而仅仅和当前状态相关。用数学表达马尔科夫状态$s_t$：
Markov Process
马尔科夫过程也可以被称作马尔科夫链，是一种具有马尔科夫性质的无记忆随机过程。马尔科夫过程由一个有限状态集$S$以及一个状态转移模型$P$构成，其中$P$指定了从某个特定状态转移到另一个状态的概率:
需要注意的是在马尔科夫过程的设定中还没有reward或者action，这两项元素会逐步被加进来。如果状态集$S$是有限的，那么我们可以将$P$用一个矩阵表示：
Markov Reward Process
马尔科夫奖励过程其实就是马尔科夫链（Markov Chain）加上rewards。马尔科夫奖励过程由以下四项元素组成：
- $S$：代表环境或者世界的一个有限状态集
- $P$：一个状态转移模型，声明了$P(s_{t+1}=s’|s_t=s)$
- $R$：一个奖励函数，声明了在某一状态下agent收到的奖励，$R(s_t=s)=E[r_t|s_t=s]$
- $\gamma$：对于未来奖励进行加权的折扣因子，$\gamma \in [0,1]$
Parameter Explanation
Horizon
注意这个名词很少在项目中被提到，简单来说它就是一个episode的time step数目。horizon可以是无限的，如果任意一个horizon都是有限的，那么我们可以将这样的MRP称作Finite MRP。
Return
Return $G_t$ 的中文译名我没有关注，在数学上的含义就是从某个时间步$t$开始沿着某个状态$s$的序列获得的奖励之和：
State Value Function
状态$s$的状态价值函数指的是从状态$s$出发取得的return的期望值：
Discount Factor
折扣因子是小于等于1的正数，这个参数的提出基于两个考虑。第一是能够带来数学上的便利：在其小于1时保证每个状态的状态价值函数的值保证收敛；第二就是符合人在行动时的常见模式：比起远处的reward人们更在意immediate reward。当$\gamma=0$时，意味着模型只考虑immediate reward，成为完全的贪婪模型；当$\gamma=1$时则适用于有限马尔科夫过程，认为未来和当前的reward有相同的重要性。
Computing State Value Function for MRP
Via simulation
首先最直观的方法是通过模拟（simulation）的方法求得每个状态的state value，得到大量的episodes，将所有的return值进行加和求平均即可，这样做不需要整个环境是符合马尔科夫假设的。
Via matrix equation
如果马尔科夫假设在应用场景中是合理的，那么我们可以写出一条state value之间的关系式，其含义是 状态$s$的value = 当前状态的immediate reward + 经过折扣的各个状态的价值期望。
因为对于所有的状态都成立，所以我们可以将上面针对某个状态的等式写成矩阵形式（依然只适用于有限马尔科夫过程）：
更进一步地简化矩阵内部的元素，得到：
最终目标是算出$V$向量，通过矩阵解方程方法，得到：
根据数值分析中的知识，我们知道矩阵求逆是$O(N^3)$的复杂度。
Via dynamic programming
其实我们可以通过递推的方式来解得最终的表示，不过我们需要证明整个递推表达式是收敛的。
Dynamic Programming with tolerence $\epsilon$：
每一次iteration的时间复杂度为$O(|S|^2)$，也就是$O(|N|^2)$。事实上我们可以证明这个算法最终收敛到真实的$V$上，并且我们还能够给出误差估计值为。证明分为以下步骤：
- 定义Bellman Operator，证明这个算子是strict contraction的。
- 根据引理得知，strict contraction的算子只有一个不动点，而$BV=R+\gamma PV=V$，则这个不动点就是真实的$V$。
- 利用三角不等式和Bellman Operator 的性质得到，严格证明式为以下：
Markov Decision Process
马尔科夫决策过程（MDP）是马尔科夫奖励过程（MRP）+actions。类似的，MDP由以下5组元素构成：
- $S$：代表环境或者世界的一个有限状态集，$s\in S$
- $A$：代表agent能够执行的有限动作集，$a\in A$
- $P$：一个状态转移模型。和MRP不同的是，MDP中的状态转移模型是一个同时关于当前状态$s$和当前行动$a$的函数，声明了$P(s_{t+1}=s’|s_t=s,a_t=a)$
- $R$：一个奖励函数。同样的奖励函数也接受了动作$a$作为其中一个变量，声明了在某一状态下采取某一动作agent收到的奖励，$R(s_t=s,a_t=a)=E[r_t|s_t=s,a_t=a]$ 。需要注意的是这仅仅是这门课程中的表示方法，仔细想一下其实$R$是一个仅关于状态的函数也是正确的。
- $\gamma$：对于未来奖励进行加权的折扣因子，$\gamma \in [0,1]$
综上我们可以将MDP简化写为一个五元组$(S,A,P,R,\gamma)$。
MDP + Policy
对于给定的Policy（这里的给定指的是policy为一个stationary policy，即不随着time step的变化而变化的），MDP会退化成一个MRP，因为给定的Policy导致了给定的状态转移概率分布，同时也导致了给定的奖励函数分布。
以上的退化形式告诉我们能够利用MRP中的评价方法对于某个特定的policy $\pi$ 进行评价，即计算每个状态的价值函数。Iterative的方法递推公式如下所示，这被称作某个特定policy的Bellman Backup，关于Bellman Operator，我们现在只需要知道这是一个用于辅助证明迭代方法最终能够收敛的手段，在未来如果有机会可以进行更详细的了解。
MDP Control
MDP Control目的在于找到一个最优的策略$\pi^*$使得在该策略下的状态价值函数最大化。
课程中提到这种情况下一定存在一个唯一的最优价值函数，但这里还需要再进一步研究。对于Infinite Horizon problem，最优策略一定是deterministic & stationary的，也就是最终会坍缩到不依赖于time step。
寻找最优的Policy即Policy Search有三种思想，除去最简单的Enumeration的暴力方法（如果是Deterministic Policy的话可以将所有的Policy都罗列出来，复杂度为$|A|^{|S|}$），最为重要的两种方法为策略迭代（Policy Iteration，PI）和价值迭代（Value Iteration，VI）。
Policy Iteration
策略迭代的想法是找到最优的value & policy。
定义State-Action Value $Q$，其含义为在当前状态$s$下采取动作$a$之后再follow策略$\pi$收获的价值：
上述公式实际上是采取了未来一步的探索。将这条式子应用于迭代模型，对于当前迭代轮次$i$：每个$(s,a)$ pair都可以算出相应的$Q$值并且可以更新到下一个迭代轮次：
需要证明这样的更新方法最终是一定能够收敛到全局最优解的，也就是说需要证明这是一个Monotonic Improvement。定义策略价值函数的序关系之后再进行一些简单的放缩即可得到整个更新的过程是单调的。
因为策略更新是单调的，所以整个策略迭代的过程的停止终点就是策略的更新为零的时候，即：
同时策略的更新次数是有界的，也就是在之前提到的Enumeration方法的复杂度$|A|^{|S|}$之内一定能够达到最优点。
Value Iteration
价值迭代的核心思想在于“Maintain optimal value of starting in a state $s$ if have a finite number of steps k left in the episode.”也就是说首先假设未来只有k步，通过迭代不断地将k往后推，从而达到拟合。
首先介绍Bellman Equation，一个策略的价值函数必须满足以下等式：
Bellman Operator也被称作Bellman Backup Operator。算子（Operator）就是作用在一个函数上将函数再进行一次映射。Bellman Operator作用在这里的value function上同时返回一个新的映射到所有状态的函数。
Value Iteration的算法中的迭代部分公式为：
从整个迭代从Bellman Backup的角度来看，每一次迭代的过程就是做了以下的操作：
这里，每个迭代轮次$k$对应的价值$V_k$其实代表了从当前状态向后行动$k$个时间步的最大价值。对于FInite Horizon问题来说迭代不需要等到Converge，只需要运行最大Horizon步长即可。
回到策略迭代，同样可以用Bellman Operator来表达策略迭代的过程，$B^\pi$是针对于某个特定的策略$\pi$的Bellman算子：
Policy Evaluation相当于计算$B^\pi$的不动点，只需要不断地进行Bellman Operator的变换直到$V$不再变化即可。
下面介绍Bellman Operator是一个压缩算子（Contraction）。压缩算子$O$指的是对于任何形式的norm，都有以下不等式成立。如果$V’$是上次迭代的结果，那么该不等式是迭代过程收敛的一个充分条件，表明最终的结果会收敛到一个不动点。
可以证明当折扣因子$\gamma < 1$，Bellman Operator是一个压缩算子，因此说明我们的迭代过程是收敛的。证明过程如下：
VI v.s. PI
VI算法依次计算Horizon为$k$的最优值，PI则被用于计算一个策略的Infinite Horizon值，并用于选择一个更好的策略，和未来即将介绍的RL重要算法Policy Gradient有非常紧密的联系。简单来说，PI算法首先随机初始化一个策略，通过evaluate这个策略得到关于这个策略的价值函数，然后再不断优化这个策略（取得更大的价值函数值）达到拟合；而VI则是将价值函数初始化为0向量，每一次迭代计算当前价值函数的Bellman Optimality Operator，由于该算子是一个压缩算子，因此具有唯一的不动点，并且该不动点是最优点，最后通过价值函数来取得最优的策略。
Policy Improvement
最后再formulate一下利用Policy Iteration进行Policy Improvement的具体流程：
首先计算当前策略$\pi_i$的$Q$值：
因为有以下不等式成立：
意味着state-action value是严格非减的，通过迭代就能够不断优化策略。定义下一个迭代轮次$i+1$的策略：