从第一章中了解到强化学习中，智能体通过和环境进行交互获得信息。这个交互过程可以通过马尔可夫决策过程来表示，所以了解一下什么是MDP至关重要。
  不过在了解马尔可夫决策过程之前，先要一些预备知识，它们分别叫马尔可夫性质、马尔可夫过程/马尔可夫链、马尔可夫奖励过程。
  马尔可夫性质(Markov property)：如果一个状态的下一个状态只取决于当前状态，跟它当前状态之前的状态都没有关系。换句话说：未来的转移跟过去是独立的，只取决于现在。
  给定一个状态的历史概念(其实就是过去状态的一个集合表示)：

  马尔可夫链(Markov Chain)：一个状态转移链，从起始状态到结束状态。代表状态转换过程。
  状态转移有很多种表示形式：
  表示法1：图解法(图中包括状态之间发生转移的关系以及状态转移对应的回报值)

  表示法2：状态转移矩阵法(矩阵维度等于状态，矩阵值为转移概率，以条件概率形式表示)

  马尔可夫过程(Markov Process)：其实书中并没有和马尔可夫链做太大的区分，对于RL来说，只需要明确它们都是表示存在状态转移就可以。但实际上还是有不同的，马尔科夫链更广泛一点，具体内容可以参考：马尔可夫链_百度百科 (baidu.com)
  举个马尔可夫链的例子：s3,s2,s3,s2,s1。从头到尾的执行过程就可以叫做马尔可夫过程。
  马尔可夫奖励过程(Markov reward process)=马尔可夫链+奖励函数
  那什么是奖励函数呢？在前面的概论中，了解到RL过程中状态转移会有奖励。这个奖励函数就是这个奖励的一种表示。之前是概念性的，现在用数学化的方式来表达一下。
  回报(return)：当前状态及之后状态的总收益，一般把之后的状态打折扣。如下，回报常用G表示：

  ps：上式中R就是奖励函数
  回报是针对每一个状态的，从上一章中了解到。价值函数是用来判断策略好坏的。那有没有办法去衡量一个状态的价值呢？方法当然有，其实就是价值函数的分类之一：状态价值函数(state-value function)。对于马尔可夫过程而言，状态价值函数定义为回报的期望：

  这个的γ是折扣因子，原因之前介绍过了，认为未来的奖励对于当前状态的影响会小。 折扣因子的作用有如下几点：
  1）避免过程中有环路，出现无穷奖励
  2）用来表达不确定性
  3）表达出倾向于立刻的奖励

  马尔可夫决策过程：马尔科夫链+奖励+决策(动作)
  由上面的定义式知，马尔可夫决策也等于马尔可夫奖励+决策。所以决策和奖励二者之间存在这样的转化关系：
  一个明显的问题就是：马尔可夫决策过程和马尔可夫过程/奖励过程有什么区别呢？区别就是决策的存在，体现为是否有具体动作的选择。用图来说明这个问题：
   注：上面右边这个图其实叫备份图，备份类似于自举之间的迭代关系，对某一个状态当前的价值和未来价值线性相关。对于备份有两种分类 同步备份：每一次迭代都会完全更新所有的状态。异步备份：通过某种方式，每一次迭代不需要更新所有的状态。

  左边这个图可以代表过程/奖励过程，右边代表决策过程。很直观的可以看出决策中增加了动作的选择(也就是决策Π)。普通的马尔可夫过程只是代表状态的转移，而马尔可夫决策过程中加上动作层。状态执行动作由策略决定，执行动作后变成的状态是其实一个概率事件(原因在于不同时间，即使相同状态执行相同动作的结果也不一定相同。情况在变)。
  马尔可夫决策中引入了策略，那如何定义策略的好坏呢？就需要引入另一种评价指标，价值函数。价值函数决定了策略的好坏。之前提过价值函数分两种：状态价值函数、动作状态价值函数。下面对这两种价值函数给出定义：
  ps：价值函数的引入已经反复提了很多次，但其实整体是一个逻辑有策略就有价值函数。不过本节会更倾向于数学化的表示
  状态价值函数(state-value function)：

  动作状态价值函数(action-value function，也叫Q函数)：
  从上面的数学式上看，都是与回报相关的期望。而且是策略确定
  当了解到这里后，会有两个很直接的问题：
  1）如果策略已知，它的两个价值函数怎么求？(以函数做类比，函数形式是什么样的？)
  2）价值函数求出来了，想要更好的策略。怎么利用求出来的价值函数更新更好的策略
  关于这两个问题，这章可能不能给出直接的答案。但后面会逐渐介绍解决方法的，敬请期待~
  想这样一个问题：对于两个状态，最关心的是什么？应该是两个状态是怎么转换的！能不能了解到两个状态转换的表达式，而且根据马尔可夫性质，这两个状态应该是时间上连续的。做一个假定(后面都是按照这个来)：s是当前状态，s’是下一个状态。
  假设现在有了一个策略(其实总会有初始化的一个策略，只不过可能不好)，关心的是两类价值函数。结合上面说的过程转换，那对于两类价值函数来说，状态转换表达式是啥呢？(hhh，终于绕过来了)
  能够解释上个问题的就是贝尔曼期望方程(Bellman expectation equation，有的时候会简称为贝尔曼方程)，其实理解马尔可夫决策过程的关键就是明白贝尔曼方程的含义及推导过程，贝尔曼方程的作用是定义了当前状态和未来状态的关系。先给出贝尔曼方程的结果式，然后再来进行推导：


  对于贝尔曼方程的推导比较难以理解，直接啃书本可能会懵。这里推荐一个视频课，我觉得讲的很清楚(直接去看，不要多说，看了就会)：
【强化学习】马尔科夫决策过程【白板推导系列】_哔哩哔哩_bilibili
  学的时候直接找这个就行，为了证明我会了，我也会手动推理一遍。并在旁边标上注释。可以作为学习参考：
  贝尔曼最优方程(Bellman optimality equation)推导如下：
  因为我们的目标是最优策略，所以贝尔曼最优方程就是从最优的角度出发。推导前后关系。
  现在，明确了贝尔曼方程。继续往下看：

  上式也是马尔可夫奖励函数的推导式，那现在来看看如何求解马尔可夫奖励函数的价值，有两种方式，分别对应了两种情况：
  1）解析解：对应状态量较小
   使用的主要思想是把整体矩阵化，在此不进行推导了。只摆出结论：
  其中V代表价值，I代表单位矩阵，γ代表折扣因子，P代表状态转移矩阵，R代表每个状态的回报(因为其中有求逆的操作，复杂度较高，状态数过多代表矩阵维度过高，不易计算)
  2）迭代解：对应状态量较大
  迭代求解的方法有很多种，在此简单介绍下(后面会多次详细的使用这些方法)：
    （1）蒙特卡洛法(MC)：进行一次实验，产生一次轨迹。得到一次奖励。多次实验取平均，作为价值。伪代码如下：
    （2）动态规划法(DP)：迭代中关注状态变化，等到状态变化不大时，更新停止，再计算当前状态对应的价值。伪代码如下：
    （3）时序差分法(TD)： MC中需要完成一次完成的奖励采样才能得到结论，那如果存在一些限制，无法结束。能否通过相邻两个状态的变化就求解出想要的内容呢？这就是时序差分干的事情。在此给一个思想，后面会详细的介绍相关内容的。
  ps：动态规划法中涉及到一个概念：自举，这是一种思想，指根据其他估算值来更新估算值。重点是估算值，说明就不是准确的。

  下面介绍一些概念，从概念引出要介绍的内容：
  策略评估：计算状态价值函数的过程叫做策略评估。另外一种含义是预测当前采取的策略最终会产生多少的价值

  预测和控制(马尔可夫决策过程里面的两个关键问题)：
  预测指给定一个马尔可夫决策过程<S,A,P,R,γ>及一个策略Π，去计算它的价值函数(两个输入一个输出)
  控制指我们去寻找一个最佳的策略，然后同时输出它的最佳价值函数和最佳策略(一个输入两个输出)
  比较两者区别，预测要策略已知，控制是策略未知。两者之间的存在递进关系，在RL中一般是先解决预测问题，然后再解决控制问题。
  马尔可夫决策过程控制：已有一个马尔可夫决策过程，确定最佳策略和最佳价值函数。
  最佳策略和最佳价值函数之间有什么关系吗？其实它们是一个东西，取到了最佳策略就对应的是最佳价值函数。一般求的话是先取得最佳的价值函数，然后问题转变成如何得到最佳策略，通过的方式就是Q函数极大化。
  啥意思呢？直白点儿说最优策略就是每步动作都是价值最大的，那就从所有的动作中选择一个最大的，以这个动作作为策略的一部分就OK了。当然这个只是概念上的一种方法，具体怎么实现呢？寻找最佳策略有个专业术语叫做：策略搜索。最简单的办法就是穷举，然后根据回报选一个最佳策略。但效率很低，常用的两种方法是策略迭代和价值迭代
  策略迭代：
  策略迭代由两部分组成：策略评估+策略改进
  策略评估：已有一个策略Π，计算这个策略的价值函数V
  策略改进：得到价值函数V，通过奖励函数和状态转移计算Q函数。通过最大化Q生成新策略。
  价值迭代：
  价值迭代算法的精髓是不停地去迭代贝尔曼最优方程，到最后会趋向于最佳策略，
  策略迭代与值迭代都属于强化学习里面策略求解中的动态规划方法
  如果到这儿还不太清楚策略迭代和价值迭代也不用着急，具体的内容还在后面，我在网上找了一些相关的内容，可以看一看，提前学习一下下：

  策略迭代流程：
  策略迭代的目的是寻找最优策略，方法是不断更新策略。更新策略的方法是不断选择状态价值最高的策略。让状态价值变高的方法是选择正确的状态。这是反向过程，首先根据状态计算状态的价值，让价值收敛就是选择出具有最高价值的状态/确定了新策略的评估函数。利用评估函数，确定每一个状态选择每一个动作的价值。选择价值最高的动作，将这个动作作为策略。这个策略比之前的有所改进。

  价值迭代流程:
  价值迭代的目的是寻找最优策略和最大价值函数。进行价值函数更新时就直接选择最好的。策略迭代中利用的是收敛即可，这里是要尝试所有状态的所有动作，选择其中最大的价值。并将这个期望价值函数作为当前状态的价值函数，然后收敛就行。利用最有价值函数和状态转移概率计算出最优动作，这就是最优策略
参考： 策略迭代与值迭代的区别_dadadaplz的博客-CSDN博客_值迭代和策略迭代区别
  老规矩，课后题来！

2-1 折扣因子有三个作用：1）防止无穷奖励 2）倾向与当前奖励 3）表达不确定性
2-2 解析解求解的时候计算了矩阵的逆，矩阵的维度是状态数，状态数过多时，求解时间复杂度很高
2-3 贝尔曼方程的推导写了一遍，我觉得我掌握一种就够了(狗头保命)
2-4 决策过程比奖励过程多了一个决策的动作层
2-5 马尔可夫奖励比马尔可夫过程结构上多了每次状态转移的奖励
2-6 价值迭代和策略迭代，策略迭代只寻找最优策略，价值迭代寻找最优策略及最优价值函数

2-1 马尔可夫过程指状态转移过程，而且下一时刻状态只取决于当前状态，与当前状态前面的状态无关。马尔可夫决策过程指马尔可夫奖励过程+策略选择。 最重要的性质只有相邻状态间存在相关性
2-2 策略迭代和价值迭代
2-3 ？？？？？
2-4


2-5 都是最优情况下，按照最优的唯一性，最佳价值函数和最优策略对应的应该是相同情况
2-6 当n越来越大时，方差应该是变大的。这点类比于MC和TD的关系，MC相当于n趋近于无穷，MC的方差更大。类似MC的期望更小，n越大，期望也会越小

  学完MDP这一章，我们明确了要寻找最佳策略，给了策略迭代和价值迭代的方法。本文介绍了思想，但是它们具体是怎么实现的呢？且听下回分说。

因作者水平有限，如果错误之处，请在下方评论区指正，谢谢！

概念引入

强化学习的通俗理解

马尔可夫的通俗介绍

简介

马尔可夫决策过程 (Markov Decision Processes, MDPs)是对强化学习问题的数学描述.

马尔可夫决策过程（Markov Decision Process, MDP）是序贯决策（sequential decision）的数学模型，用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报 。MDP的得名来自于俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков），以纪念其为马尔可夫链所做的研究 。
MDP基于一组交互对象，即智能体和环境进行构建，所具有的要素包括状态、动作、策略和奖励 。在MDP的模拟中，智能体会感知当前的系统状态，按策略对环境实施动作，从而改变环境的状态并得到奖励，奖励随时间的积累被称为回报 。
MDP的理论基础是马尔可夫链，因此也被视为考虑了动作的马尔可夫模型 。在离散时间上建立的MDP被称为“离散时间马尔可夫决策过程（descrete-time MDP）”，反之则被称为“连续时间马尔可夫决策过程（continuous-time MDP）”。此外MDP存在一些变体，包括部分可观察马尔可夫决策过程、约束马尔可夫决策过程和模糊马尔可夫决策过程。
在应用方面，MDP被用于机器学习中强化学习（reinforcement learning）问题的建模 。通过使用动态规划、随机采样等方法，MDP可以求解使回报最大化的智能体策略 ，并在自动控制、推荐系统等主题中得到应用

• 要求环境是全观测的.
• 几乎所有的 RL 问题都能用 MDPs 来描述
• 最优控制问题可以描述成连续 MDPs
• 部分观测环境可以转化成 POMDPs
• 赌博机问题是只有一个状态的 MDPs

符号说明

用大写字母表示随机变量：S, A, R 等
用小写字母表示某一个具体的值：s, a,r 等
用空心字母表示统计运算符：E, P 等
用花体字母表示集合或函数：S, A,P 等

马尔可夫性

马氏性(Markov Property)用来描述一种特殊的、定义在某状态空间S上的随机变量列 {X(n): n>=0} 的性质，满足 P( X(n) = i(n) | X(n-1) = i(n-1), … , X(0) = i(0) ) = P( X(n) = i(n) | X(n-1) = i(n-1) )，可以理解为已知当前状态为i(n-1)的情况下，下一步状态为i(n)的概率只与i(n-1)有关，与之前的状态无关。马氏性有一个等价命题可以帮助理解：已知当前状态情况下，过去事件与未来相互独立。

简单来说
如果在 t 时刻的状态 St 满足如下等式，那么这个状态被称为马尔可夫状态，或者说该状态满足马尔可夫性.

状态 St 包含了所有历史相关信息，或者说历史的所有状态的相关信息都在当前状态 St 上体现出来
，一旦 St 知道了，那么 S1, S2, . . . , St−1 都可以被抛弃，数学上可以认为：状态是将来的充分统计量
因此，这里要求环境全观测

状态转移矩阵

状态转移矩阵是俄国数学家马尔科夫提出的控制理论中的矩阵，是时间和初始时间的函数，可以将时间的状态向量和此矩阵相乘，得到时间时的状态向量。他在20世纪初发现：一个系统的某些因素在转移过程中，第n次结果只受第n-1的结果影响，即只与上一时刻所处状态有关，而与过去状态无关。 在马尔科夫分析中，引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态；状态转移是指客观事物由一种状态转移到另一种状态。

状态转移概率指从一个马尔可夫状态s 跳转到后继状态 (successorstate)s′ 的概率

所有的状态组成行，所有的后继状态组成列，我们得到状态转移矩阵

• n 表示状态的个数
• 由于 P 代表了整个状态转移的集合，所以用花体
• 每行元素相加等于 1

用函数表达，就是

状态数量太多或者是无穷大（连续状态）时，更适合使用状态转移函数，此时

马尔可夫过程

马尔可夫过程（Markov process）是一类随机过程。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。马尔可夫过程是研究离散事件动态系统状态空间的重要方法，它的数学基础是随机过程理论
一个马尔可夫过程 (Markov process, MP ) 是一个无记忆的随机过程，即一些马尔可夫状态的序列
马尔可夫过程可以由一个二元组来定义 ⟨S,P⟩，S 代表了状态的集合，P 描述了状态转移矩阵。

片段

强化学习中，从初始状态 S1 到终止状态的序列过程，被称为一个片段

• 如果一个任务总以终止状态结束，那么这个任务被称为片段任务(episodic task)
• 如果一个任务会没有终止状态，会被无限执行下去，这被称为连续性任务 (continuing task)

马尔可夫奖励过程

马尔可夫过程主要描述的是状态之间的转移关系，在这个转移关系上，赋予不同的奖励值即得到了马尔可夫奖励过程。

马尔可夫奖励 (Markov Reward Process, MRP) 过程由一个四元组组成⟨S,P, R, γ⟩

• S 代表了状态的集合
• P 描述了状态转移矩阵

• R 表示奖励函数，R(s) 描述了在状态 s 的奖励，
• R(s) = E [Rt+1|St = s]
• γ 表示衰减因子，γ ∈ [0, 1]

回报值

• 奖励值：对每一个状态的评价
• 回报值: 对每一个片段的评价

回报值 (return Gt) 是从时间 t 处开始的累计衰减奖励

• 对于片段性任务:
  

• 对于连续性任务

这个时候，我们结合前面所学，把旧概念做一定的挖掘

对于片段

终止状态等价于自身转移概率为 1，奖励为 0 的的状态，因此我们能够将片段性任务和连续性任务统一表达。

这里当 T = ∞ 时，表示连续性任务，否则即为片段性任务

然后是衰减值

用指数来表达衰减值的原因

• 影响未来的因素不仅仅包含当前，我们对未来的把握也是逐渐衰减的，一般情况下，我们更关注短时间的反馈
• 一个参数就描述了整个衰减过程，只需要调节这一个参数 γ 即可以调节长时奖励和短时奖励的权衡 (trade-off)，指数衰减形式又很容易进行数学分析，指数衰减是对回报值的有界保证，避免了循环 MRP 和连续性 MRP，情况下回报值变成无穷大

值函数

• 回报值是一次片段的结果，存在很大的样本偏差
• 回报值的角标是 t，值函数关注的是状态 s

一个 MRP 的值函数如下定义

这里的值函数针对的是状态 s，所以称为状态值函数，又称 V 函数
Gt 是一个随机变量
这里使用小写的 v 函数，代表了真实存在的值函数

MRPs 中的贝尔曼方程

贝尔曼方程（Bellman Equation）也被称作动态规划方程（Dynamic Programming Equation），由理查·贝尔曼（Richard Bellman）发现。贝尔曼方程是动态规划（Dynamic Programming）这些数学最佳化方法能够达到最佳化的必要条件。此方程把“决策问题在特定时间怎么的值”以“来自初始选择的报酬比从初始选择衍生的决策问题的值”的形式表示。借此这个方式把动态最佳化问题变成简单的子问题，而这些子问题遵守从贝尔曼所提出来的“最佳化还原理”。

贝尔曼方程是关于未知函数（目标函数）的函数方程组。应用最优化原理和嵌入原理建立函数方程组的方法称为函数方程法。在实际运用中要按照具体问题寻求特殊解法。动态规划理论开拓了函数方程理论中许多新的领域。
特点和应用范围 ：
若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用 [1] ，但动态规划还缺少严格的逻辑基础。
60年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。
动态规划方法的五个特点：
①在策略变量较多时，与策略穷举法相比可降低维数；
②在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；
③对于不能用解析形式表达的函数,可给出递推关系求数值解;
④动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；
⑤许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。
投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。

值函数的表达式可以分解成两部分

• 瞬时奖励 Rt+1
• 后继状态 St+1 的值函数乘上一个衰减系数

• 体现了 v(s) 与 v(St+1) 之间的迭代关系
• 注意 s 小写，St+1 大写

如果我们已知转移矩阵 P，那么

当 γ = 1 时 0.6 = −2 + 0.6 × 10 + 0.4 × −8.5

贝尔曼方程的矩阵形式

使用矩阵-向量的形式表达贝尔曼方程，即

假设状态集合为 S = {s1,s2, . . . ,sn}，那么

贝尔曼方程本质上是一个线性方程，可以直接解

计算复杂度

要求已知状态转移矩阵 P
直接求解的方式仅限于小的 MRPs

与 MP 和 MRP 的区别

MP 和 MRP 中，我们都是作为观察者，去观察其中的状态转移现
象，去计算回报值

• 对于一个 RL 问题，我们更希望去改变状态转移的流程，去最大化回报值

• 通过在 MRP 中引入决策即得到了马尔可夫决策过程（MarkovDecision Processes, MDPs）

• 通过在 MRP 中引入决策即得到了马尔可夫决策过程（Markov
  Decision Processes, MDPs）

马尔可夫决策过程

马尔可夫决策过程（Markov Decision Process, MDP）是序贯决策（sequential decision）的数学模型，用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报 [。MDP的得名来自于俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков），以纪念其为马尔可夫链所做的研究 [3] 。
MDP基于一组交互对象，即智能体和环境进行构建，所具有的要素包括状态、动作、策略和奖励 。在MDP的模拟中，智能体会感知当前的系统状态，按策略对环境实施动作，从而改变环境的状态并得到奖励，奖励随时间的积累被称为回报 。
MDP的理论基础是马尔可夫链，因此也被视为考虑了动作的马尔可夫模型 。在离散时间上建立的MDP被称为“离散时间马尔可夫决策过程（descrete-time MDP）”，反之则被称为“连续时间马尔可夫决策过程（continuous-time MDP）” 。此外MDP存在一些变体，包括部分可观察马尔可夫决策过程、约束马尔可夫决策过程和模糊马尔可夫决策过程。
在应用方面，MDP被用于机器学习中强化学习（reinforcement learning）问题的建模 。通过使用动态规划、随机采样等方法，MDP可以求解使回报最大化的智能体策略 ，并在自动控制、推荐系统等主题中得到应用 。

一个马尔可夫决策过程 (MDPs) 由一个五元组构成 ⟨S, A,P, R, γ⟩

• S 代表了状态的集合

• A 代表了动作的集合

• P 描述了状态转移矩阵
  

• R 表示奖励函数，R(s, a) 描述了在状态 s做动作 a的奖励，
  
  γ 表示衰减因子，γ ∈ [0, 1]

策略

我们将之前 MRPs 中的状态转移矩阵分成了两个部分

• 能被智能体控制的策略, Policy
• MDPs 中的转移矩阵P (不受智能体控制，认为是环境的一部分)

在 MDPs 中，一个策略 (Policy)π是在给定状态下的动作的概率分布

• 策略是对智能体行为的全部描述
• MDPs 中的策略是基于马尔可夫状态的（而不是基于历史）
• 策略是时间稳定的，只与 s 有关，与时间 t 无关
• 策略是 RL 问题的终极目标
• 如果策略的概率分布输出都是独热的 (one-hot)2的，那么称为确定性策略，否则即为随机策略

MDPs 和 MRPs 之间的关系

对于一个 MDP 问题 ⟨S, A,P, R, γ⟩, 如果给定了策略 π
MDP 将会退化成

此时

MDPs 中的值函数

在 MDPs 问题中，由于动作的引入，值函数分为了两种：1，状态值函数（V 函数）2，状态动作值函数 (Q 函数)

MDPs 中的状态值函数是从状态 s 开始，使用策略 π 得到的期望回报值

MDPs 中的状态动作值函数是从状态 s 开始，执行动作 a，然后使用策略 π 得到的期望回报值

和 MRP 相似，MDPs 中的值函数也能分解成瞬时奖励和后继状态的值函数两部分

V 函数与 Q 函数之间的相互转化

贝尔曼期望方程-V 函数

实际上等价于

贝尔曼期望方程-Q 函数

实际上等价于

贝尔曼期望方程的矩阵形式

MDPs 下的贝尔曼期望方程和 MRP 的形式相同。

同样地，可以直接求解

求解的要求

• 已知 π(a|s)
• 已知

最优值函数

之前值函数，以及贝尔曼期望方程针对的都是给定策略 π 的情况，是一个评价的问题。现在我们来考虑强化学习中的优化问题，即找出最好的策略。
最优值函数指的是在所有策略中的值函数最大值，其中包括最优 V 函数和最优 Q 函数

最优值函数指的是一个 MDP 中所能达到的最佳性能，如果我们找到最优值函数即相当于这个 MDP 已经解决了

最优策略

为了比较不同策略的好坏，我们要定义策略的比较关系

对于任何 MDPs 问题，
总存在一个策略 π∗ 要好于或等于其他所有的策略，π∗ ≥ π, ∀π
所有的最优策略都能够实现最优的 V 函数 vπ∗(s) = v∗(s)
所有的最优策略都能够实现最优的 Q 函数 qπ∗(s, a) = q∗(s, a)

**当我们已知了最优 Q 函数后，我们能够马上求出最优策略，只要根据q∗(s, a) 选择相应的动作即可。
**

由此可以得出，对于任何 MDPs 问题，总存在一个确定性的最优策略

v∗ 与 q∗ 的相互转化

之前我们已经探讨了 vπ(s) 和 qπ(s, a) 之间的关系——贝尔曼期望方程，同样地，v∗(s) 和 q∗(s, a) 也存在递归的关系——贝尔曼最优方程

和贝尔曼期望方程的关系

贝尔曼最优方程——V 函数

贝尔曼最优方程——Q 函数

和贝尔曼期望方程的关系

贝尔曼最优方程本质上就是利用了 π∗ 的特点，将求期望的算子转
化成了 maxa，在贝尔曼期望方程中，π 是已知的。而在贝尔曼最优方程中，π∗是未知的解贝尔曼期望方程的过程即对应了评价，解贝尔曼最优方程的过程即对应了优化。

1. 马尔可夫过程

1.1 马尔可夫性质

一个状态的下一个状态只取决于它当前状态，而跟当前状态之前的状态没有关系。
$$P(S_{t+1}|S_t)=P(S_{t+1}|S_t,S_{t-2},\cdots )$$

1.2 状态转移矩阵（state transition matrix）

状态转移概率
$$P_{s{s}^{\prime }}=P(S_{t+1}=S^{\prime }|S_t=S)$$

状态转移矩阵
由状态转移概率组成的大小为$n\ast n$的矩阵。它每一行描述了从一个节点到达其他节点的概率。
$$P=\left[\begin{array}{ccc}{p}_{11},& \cdots ,& p_{1n}\\ ⋮,& \cdots ,& ⋮\\ p_{n1},& \cdots ,& p_{nn}\end{array}\right]$$

给定一个马尔科夫链后，对这个链状态的采样，可以生成很多的轨迹。

2. 马尔可夫奖励过程（MRP）

定义
一个马尔科夫奖励过程(Markov Reward Process）是马尔可夫链再加上了一个奖励函数。它由一个四元组构成：$<S,P,R,\gamma >$

• S为有限状态空间集，$s_i$表示时间i的状态。
• P为状态转移矩阵
• R为奖励函数，$R_S=E[R_{t+1}|S_t=S]=\sum P_{S{S}^{\prime }}{R}_{S^{\prime }}$
• $\gamma$为折扣因子，$\gamma \in [0,1]$
  注意：奖励$R_S$是实时奖励，当发生状态转移时就会得到奖励。

2.1 回报与折扣因子

回报
回报（return）是把奖励进行折扣后获得的收益。因为我们更希望得到现有的奖励，所以就要把未来奖励打折扣。对于每一个轨迹，我们都可以计算得到它的回报。
$$G_t=R_{t+1}+\gamma R_{t+2}+\cdots {\gamma }^k{R}_{t+1+k}=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+1+k}$$

其中，$\gamma$为折扣因子，介于$[0,1]$之间。认为距离当前时间步越远的奖励，其重要性就越低。当$\gamma$为0时，只考虑当前奖励。当未来奖励可以提前获得，则不需要折扣计算，令$\gamma =1$。

问题：折扣因子的作用是什么？

① 马尔可夫过程可能带环，我们想避免无穷的奖励。
② 模型的不确定性，对未来的评估是不一定准确的。
③ 希望立刻就得到奖励

2.2 状态价值函数（state-value function）

价值函数表示状态s的长期价值，被定义为回报的期望值。
$$V(S)=E[G_t|S_t=S]$$

问题：如何利用一些轨迹的回报计算状态的价值函数呢？
方法一：蒙特卡洛采样（MC）算法：
选择初始进入的某个状态s，产生很多轨迹然后把这些轨迹的回报跌加起来。最后取平均作为状态s的价值。

方法二：Bellman Equation

2.3 贝尔曼方程

贝尔曼方程(Bellman Equation）定义了当前状态和未来状态间的迭代关系：当前状态价值 = 未来奖励的折扣总和 + 即时奖励。
$$V(s)=R_s+\gamma \times \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}V(s^{\prime })$$

推导：
$V(s)=E[G_t|S_t=s]$
$=E[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^k{R}_{t+1+k}|S_t=s]$
$=E[R_{t+1}]+\gamma E[R_{t+2}+\cdots +{\gamma }^{k-1}{R}_{t+1+k}|S_t=s]$
$=R(s)+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}E[R_{t+2}+\cdots +{\gamma }^{k-1}{R}_{t+1+k}|S_t=s,S_{t+1}=s^{\prime }]$
$=R(s)+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}E[R_{t+2}+\cdots +{\gamma }^{k-1}{R}_{t+1+k}|S_{t+1}=s^{\prime }]$
$=R(s)+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}V(s^{\prime })$

当前状态的价值函数由即时奖励与未来奖励的折扣总和相加获得

• $R_{t+1}$：即时奖励
• ${\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}V(s^{\prime })$：未来奖励的折扣总和

矩阵形式
$$\left[\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_N)\end{array}\right]=\left[\begin{array}{c}R(s_1)\\ R(s_2)\\ ⋮\\ R(s_N)\end{array}\right]+\gamma \left[\begin{array}{cccc}{P}_{s_1{s}_1},& P_{s_1{s}_2},& \cdots ,& P_{s_1{s}_N}\\ P_{s_2{s}_1},& P_{s_2{s}_2},& \cdots ,& P_{s_2{s}_N}\\ ⋮,& ⋮,& \cdots ,& ⋮\\ P_{s_N{s}_1},& P_{s_N{s}_2},& \cdots ,& P_{s_N{s}_N}\end{array}\right]\left[\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_N)\end{array}\right]$$

将贝尔曼方程写成矩阵形式后，可以直接求解：
$$\begin{gathered} V=R+\gamma PV \\ V=(1-\gamma P{)}^{-1}R \end{gathered}$$

因此可以通过矩阵求逆把V价值直接求出来。但时间复杂度为$O(N^3)$，当状态非常多时矩阵求逆很困难。因此解析法求V价值只适用于很小量的马尔可夫奖励过程。
例子

期望值计算如图所示，根据价值函数公式可知，某一状态S的状态函数$V(S)$由奖励函数$R_S$和可转移状态价值函数$V(S^{\prime })$的期望决定。假设$\gamma =1$，则$4.3=-2+0.6\ast 10+0.4\ast 0.8$

2.4 计算马尔可夫奖励过程的迭代算法

可以通过动态规划算法、蒙特卡洛采样、时序差分法学习等方法，求解大型马尔科夫奖励过程
（1）蒙特卡洛模拟
选择初始状态后生成大量轨迹。当生成一定轨迹后，直接用$G_t$除以轨迹数量，将轨迹的回报期望作为状态价值。

（2）动态规划法
将贝尔曼方程变成一个贝尔曼更新（Bellman update），通过不停的迭代更新每个状态的价值，最终达到收敛而获得每个状态的价值。

3. 马尔可夫决策过程MDP

定义
多引入动作因子，将MRP转化为MDP马尔科夫决策过程。
一个马尔科夫决策过程(Markov DecisionProcess)，由一个五元组构成：
$<S,A,P,R,\gamma >$

• S为有限状态空间集，$s_i$表示时间i的状态。
• A为动作空间集，$a_i$表示时间t的动作
• P为状态转移矩阵
• R为奖励函数，表示在状态s下执行动作a后获得的即时奖励$R_S^a=E[R_{t+1}|S_t=S,A_t=a]$
• $\gamma$为折扣因子，$\gamma \in [0,1]$

由于引入了动作，奖励函数将不再只与状态相关，还与动作相关。现在的奖励函数是某个状态下采取某个特定动作的即时奖励。

3.1 策略

（1）定义：
定义了某个状态应该采取什么样的动作。把当前状态带入策略函数，就会得到一个概率。
$$\pi (a|s)=P[A_t=a|S_t=s]$$

表示了在状态s下，动作a发生的概率。

（2）马尔可夫决策过程转换成马尔可夫奖励过程
状态转移矩阵
$$P_{s,s^{\prime }}^{\pi }=\sum _{a\in A_t}\pi (a|s)P_{s{s}^{\prime }}^a$$

奖励函数
$$R_S^{\pi }=\sum _{a\in A_t}\pi (a|s)R_s^a$$

问题：马尔可夫决策过程与马尔可夫奖励过程的区别

MDP在当前状态跟未来状态转移过程中多了一层决策性。

3.2 价值函数

	$v(s)$	$q(s,a)$
关系	$v^{\pi }(s)={\sum }_{a\in A_t}\pi (a\Vert s)q^{\pi }(s,a)$	$q^{\pi }(s,a)=R(s,a)+{\sum }_{s^{\prime }\in S}P(s^{\prime }\Vert s,a)v(s^{\prime })$

价值函数的输入分为状态s和状态价值对$<s,a>$。当输入状态时称为状态价值函数，当输入<状态，动作>时称为动作状态函数
（1）状态价值函数（state-value function）
当决策$\pi$确定后，可以对这个决策进行采样来得到一个期望，从而计算出它的价值函数。
$$V^{\pi }(S)=E_{\pi }[G_t|S_t=s]$$

（2）动作价值函数（action-value function）
表示在某一个状态采取某一个动作，它有可能得到的回报的期望。
$$q^{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]$$

对Q函数中的动作进行加和，就可以得到价值函数：

$$v^{\pi }(s)=\sum _{a\in A_t}\pi (a|s)q^{\pi }(s,a)$$

（3）Q函数的贝尔曼方程
$$q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V(s^{\prime })$$

推导：
$=E[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^k{R}_{t+1+k}|S_t=s,A_t=a]$
$=E[R_{t+1}]+\gamma E[R_{t+2}+\cdots +{\gamma }^{k-1}{R}_{t+1+k}|S_t=s,A_t=a]$
$=R(s,a)+\gamma E[G_{t+1}|S_t=s,A_t=a]$
$=R(s,a)+\gamma {\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)E[G_{t+1}|S_t=s,A_t=a,S_{t+1}=s^{\prime }]$
$=R(s,a)+\gamma {\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)E[G_{t+1}|A_t=a,S_{t+1}=s^{\prime }]$
$=R(s,a)+\gamma {\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)V(s^{\prime })$

例子

3.3 贝尔曼期望方程（Bellman expectation equation）

贝尔曼期望方程定义了当前状态和未来状态之间的关联
$$\begin{gathered} v^{\pi }(s)=E_{\pi }[R_{t+1}+\gamma v^{\pi }(s_{t+1})|S_t=s] \\ {q}^{\pi }(s,a)=E_{\pi }[R_{t+1}+\gamma q^{\pi }(s_{t+1},A_{t+1})|S_t=s,A_t=a] \end{gathered}$$

对价值函数和Q函数进行化简，可以得到：
$$\begin{gathered} v^{\pi }(s)=\sum _{a\in A_t}\pi (a|s)q^{\pi }(s,a) \\ {q}^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V(s^{\prime }) \end{gathered}$$

（1）价值函数
$$v^{\pi }(s)=\sum _{a\in A_t}\pi (a|s)(R(s,a)+\sum _{s^{\prime }\in S}P(s^{\prime }\Vert s,a)v^{\pi }(s^{\prime }))$$

代表了当前状态期望价值和未来状态价值之间的关系。

（2）Q函数
$$q^{\pi }(s,a)=R(s,a)+\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })q^{\pi }(s^{\prime },a^{\prime })$$

代表了当前Q函数和未来Q函数之间的关系。

3.4 备份图（backup diagram）

备份图的关系构成了更新或备份操作的基础。其中每个空心圆圈代表一个状态，每个实心圆圈代表一个状态-动作对。
（1）状态价值函数
$$v^{\pi }(s)=\sum _{a\in A_t}\pi (a|s)(R(s,a)+\sum _{s^{\prime }\in S}P(s^{\prime }\Vert s,a)v^{\pi }(s^{\prime }))$$

备份图定义了下一时刻的状态价值跟上一时刻的状态价值函数之间的关联

（2）Q函数
$$q^{\pi }(s,a)=R(s,a)+\sum _{s^{\prime }\in S}P(s^{\prime }\Vert s,a)\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })q^{\pi }(s^{\prime },a^{\prime })$$

备份图决定了未来Q函数与当前Q函数之间的关联

3.6 策略评估（value prediction）

（1）定义
知道一个马尔可夫决策过程以及要采取的决策$\pi$，计算价值函数$v^{\pi }(s)$的过程。

（2）价值预测（value prediction）
通过贝尔曼期望方程，不停的迭代，直到所有状态价值收敛。收敛过后，状态的值便是其价值。
$$v^{\pi }(s)=\sum _{a\in A_t}\pi (a|s)(R(s,a)+\sum _{s^{\prime }\in S}P(s^{\prime }\Vert s,a)v^{\pi }(s^{\prime }))$$

3.7 预测（prediction）与控制（control）

（1）预测
给定一个马尔科夫决策过程以及策略$pi$，输出状态价值函数
输入：马尔可夫决策过程$<S,A,P,R,\gamma >$和策略$\pi$
输出：价值函数$v^{\pi }$

（2）控制
给定一个马尔可夫决策过程，寻找最佳的策略。输出最佳策略及其最佳的价值函数
输入：马尔可夫决策过程$<S,A,P,R,\gamma >$
输出：最佳价值函数$v^{\ast }$（optimal value function）和最佳策略${\pi }^{\ast }$（optimal policy）

（3）区别
prediction：给定一个策略去计算状态价值函数
control：在没有策略的前提下，寻找最优价值函数及其对应决策方案

3.8 马尔可夫决策过程中的策略评估

方法
把贝尔曼期望变成一个迭代过程，这样反复迭代直到收敛。这个迭代过程可以看作是同步备份（synchronous backup）的过程

同步备份：每一次迭代都会完全更新所有的状态，这样对于程序资源需求特别大

$$\begin{gathered} v_{t+1}(s)=\sum _{a\in A_t}\pi (a|s)[R(s,a)+\sum _{s^{\prime }\in S}p(s^{\prime }|s,a)v_t(s^{\prime })] \\ {v}_{t+1}(s)=R_s^{\pi }+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s)v_t(s^{\prime }) \end{gathered}$$

理解： 将贝尔曼期望备份拿出来反复迭代，就会得到一个收敛的价值函数的值。价值函数由即时奖励与未来折扣总和之和组成，所以t+1时刻状态s的价值函数可以由即时奖励$R_s^{\pi }$和t时刻其未来可达的状态s‘的折扣总和组成。当相关联状态达到最优值时，s状态同样达到最优值。

过程： 每一步进行迭代时，远的状态就会得到一些值。当执行很多次以后，所有状态都有了值且逐渐稳定下来。最终状态的值保持不变达成收敛，我们便得到了所有状态的价值函数的值。

3.9 马尔可夫决策过程控制

马尔科夫决策过程控制就是去为每个状态寻找一个最佳策略，然后得到最佳价值函数（optimal value function）
（1）最佳价值函数
$$\begin{gathered} v^{\ast }(s)=\underset{\pi }{\max }{v}^{\pi }(s) \\ {\pi }^{\ast }(s)=arg\underset{\pi }{\max }{v}^{\pi }(s) \end{gathered}$$

最佳策略使得每个状态的价值函数都达到最大值，这样一个马尔可夫决策过程的换就被解。
（2）最佳策略
在得到最佳价值函数后，可以通过对Q函数极大化来得到最佳策略。
$$q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V(s^{\prime })$$

如果能优化出一个Q函数$q^{\ast }(s,a)$，就可以直接在Q函数上面取一个让Q函数最大化动作的值，作为最佳策略。
$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1,& a=arg{\max }_{a\in A_t}{q}^{\ast }(s,a)\\ 0,& else\end{array}$$

（3）搜索最佳策略

1. 穷举法：把策略都穷举一遍，有$|A{|}^{|S|}$个可能策略，然后算出每种策略的价值函数，对比就可以得到最佳策略。
2. 策略迭代
3. 价值迭代

3.9.1 策略迭代

策略迭代由两个步骤组成：策略评估和策略改进（policy improvement）

（1）策略评估
计算当前给定策略$\pi$下的价值函数

（2）策略改进
① 利用获得的V函数推算出Q函数：
$$q^{{\pi }_i}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{{\pi }_i}(s^{\prime })$$

② 对于每个状态，取使Q函数达到最大值的状态
$${\pi }_{i+1}(s)=arg\underset{a}{\max }{q}^{{\pi }_i}(s,a)$$

可以将Q函数看作Q表格（Q-table），横轴表示状态，纵轴表示可能的动作。

得到Q函数后，Q表格也得到了。对于每个状态，每一列里面我们会取最大Q值，并把最大值对应的动作当作状态应该采取的动作。

③ 循环迭代策略评估和策略改进①②，直到价值函数取得收敛。此时每个状态均取得最佳策略。

（3）贝尔曼最优方程
当每个状态均取得最佳策略后，对Q函数进行极大化：
$$令：{\pi }^{\ast }(a|s)=\{\begin{array}{ll}1,& a=arg{\max }_{a\in A_t}{q}^{\ast }(s,a)\\ 0,& else\end{array}$$

便可以得到贝尔曼最优方程（Bellman optimality equation）：
$$v^{\pi }(s)=\underset{a\in A}{\max }{q}^{\pi }(s,a)$$

即，最佳策略的状态价值必须等于在此状态下采取最好动作得到的回报的期望。
最佳的价值函数到达过后，贝尔曼最优方程就会满足，便会有如下等式：
$$\begin{gathered} v^{\ast }(s)=\underset{a}{\max }{q}^{\ast }(s,a) \\ {q}^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)v^{\ast }(s^{\prime }) \end{gathered}$$
Q函数的贝尔曼方程
$$q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\underset{a^{\prime }}{\max }{q}^{\ast }(s^{\prime },a^{\prime })$$

V函数的贝尔曼方程
$$v^{\ast }(s)=\underset{a}{\max }(R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)v^{\ast }(s^{\prime }))$$

3.9.2 价值迭代

（1）最优性原理（principle of optimality therorem）
一个策略在状态s达到了最优值，当且仅当任何能从s到达的s’，都已经到了最优价值。

（2）确定性价值迭代
把贝尔曼最优方程当成一个更新规则进行：
$$v(s)\leftarrow \underset{a\in A}{\max }(R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)v(s^{\prime }))$$

通过不停的迭代，最终达到收敛的值便是每个状态的最优价值。
算法
通过不断地迭代更新Q表和价值函数，直到价值函数收敛获得最优价值。利用最优价值重构Q表并选取最佳策略。

如果相邻节点价值发生变化，则该节点会变得更好，直到相邻节点不再变化。

3.9.3 两种控制方法的比较

策略迭代和价值迭代获得的最优策略是一致的。
策略迭代：分为两个步骤“策略评估”和“策略改进”，每次迭代都会改进当前最优策略直到策略收敛得到最优策略。
价值迭代：先算出最优价值函数后，在重构Q函数获得最优策略。

常用的迭代方法

• Value Iteration
• Policy Iteration
• Q-Learning
• Sarsa

Reference

[1] 莫凡Python:https://www.bilibili.com/video/BV13W411Y75P?p=13
[2] 强化学习笔记:https://www.jianshu.com/p/fb33231ac3a8
[3] https://github.com/datawhalechina/easy-rl