【强化学习】第一篇--马尔科夫决策过程

作者：王小草
笔记时间：2019年1月20日

1 马尔科夫性质与过程

1.1 马尔科夫性质

• 马尔科夫性质即：
  系统的下一状态只与当前状态有关，与以前的历史状态无关。

• 公式表达：
  

• 特点：

  • 当前状态蕴含所有相关历史信息
  • 一旦当前状态已知，历史信息将会被抛弃

1.2 马尔科夫过程

• 马尔科夫过程即：
  该过程中所有状态都满足马尔科夫性。

• 表示：
  马尔科夫过程可以用一个二元组表示(S, P)

  • S 是一个有限的状态集合
  • P 是状态之间的转移概率矩阵，P_ss’表示从状态s转移到状态s’的概率
    

• 转移矩阵
  若马尔科夫过程有N个状态，则转移概率矩阵就是一个N*N的方正：
  

  转移概率矩阵的性质为：

  • （1）非负性：P_ij>0
  • （2）每行的和为1

  注意：每列的和不一定为1，该矩阵不一定是对称矩阵，即P_ij不一定等于P_ji

• 示例
  

  这是一个经典例子，表示一个学生学习，圆圈代表的是状态（刷facebook,class1,class2,class3, pass, sleep,泡pub）；箭头代表的是状态之间的转移，箭头上的概率就是状态之间的转移概率，比如若是在刷facebook,下一个状态有0.9的概率还是在刷facebook, 只有0.1的概率去上class1，作孽啊；方框代表着终止状态，即一旦到达这个状态就停止了，不会再转移到其他状态。

2 马尔科夫奖励过程MRP

马尔科夫奖励过程比马尔科夫过程多两个元素：奖励函数与折扣因子。

• 表示：
  马尔科夫奖励过程可以用四元组表示：M = < S, P, R, γ >

  • S 是一个有限的状态集合
  • P 是状态之间的转移概率矩阵，P_ss’表示从状态s转移到状态s’的概率
  • R 是一个奖励函数，是状态s转移到下一状态的奖励的期望
    
  • γ 是一个折扣因子，即未来的奖励在今天看来需要有打一个折扣，毕竟现在给你100万和10年后给你100万是不一样的嘛。
    

• 示例
  
  还是同一个例子，但是现在在每个状态上都加上一个奖励值，比如pass状态的奖励值10， 而刷facebook的奖励值是-1

  概率状态矩阵可以如下表示：
  

3 马尔科夫决策过程MDP

马尔科夫决策过程是强化学习的基础，所有强化学习的模型和变体都是依赖于马尔科夫决策过程的。

• 表示
  马尔科夫决策过程通常用五元组表示：M = < S, P, R, A, γ >
  • S 是一个有限的状态集合（和上文中的一模一样）
  • P 是状态转移矩阵，表示在状态s的情况下，执行动作a,转移到状态s’的概率
    
  • R 是在某个状态下，执行某个动作所得到的期望奖励（因为执行了某个动作，会可能转移到多个状态）
    
  • A 动作的集合
  • γ 是折扣因子，与上文中的一样，是一个[0,1]之间的系数

3.1 折扣系数

折扣系数有3种情况：
（1）T=1， 则为贪婪模型，当前状态的奖励只与下一状态有关，不会去考虑后面的动作再来的影响，虽然简单，但很多情况下它就是最优解，此时γ=0
（2）T属于（1，正无穷），最符合实际情况，即为有限个步数，每个状态的收益折减都一样
（3）T=正无穷，即无限模型，此时γ取值很重要，因为需要保证无限计算的结果是收敛的。

3.2 长期回报

根据折扣系数可以计算长期回报，无限期的折扣回报可以如下计算：

此处，R是总回报，r是及时回报，将每一步的及时回报根据折扣系数加权求和就是总回报。

有些论文中会用下面这个公式：

此处，G是总回报，R是即时回报。两个公式逻辑都是一样的，只是表达不一样而已。

现在来用老例子计算长期回报，先以马尔科夫奖励过程的例子来计算：

若是假定从class1状态开始，一直到终止状态的sleep，总共有4条路径可以走，设γ=0.5，计算每条路径的总回报如下：

3.3 马尔科夫决策过程示例

还是原来的例子，不同的是加进了动作，注意红色文字表示的是采取的行为，而不是上文的状态。由于引入了action,为了避免与状态名混淆，因此途中没有给出状态的名称。
及时奖励与行为是对杨的，同一个状态下采取不同的行为得到的即时奖励是不同的。
当选择pub动作时，主动进入了一个临时状态，随后被动地被环境按照其动力学分配到了另外三个状态。

4 策略

策略是强化学习的核心部分，策略的好坏最终决定了agent的行动和整体性能。

• 定义：
  策略即在每个可能的状态下，agent应该采取的动作的概率分布。

• 表示：
  用π表示，π：S->A
  或表示成π(s)=a,输入为当前状态s，输出为在该状态下应该做的动作。

• 确定性策略与不确定性策略
  

  • 确定性策略:每个状态下只有一个确定的动作
  • 不确定性策略:每个状态下有多个动作以概率分布的形式存在

• 贪婪策略与????-geedy策略

  • 贪婪策略：每个状态只有一个动作
    
  • ????-geedy策略：每个状态有多个动作，一种一个策略概率最大，其他取很小概率
    

• 允许策略与不确定性策略

  • 允许策略：任意状态所能选择的策略组成的集合F，π ∈ F
  • 最优策略：在允许策略集合中找出使问题具有最优效果的策略

• MDP与MP、MRP的关系：可以将策略的可能性作为权重去得到转移概率
  

• MDP中的两重随机性：

  • 策略的随机性：即每个状态下有多个可能的随机动作
  • 状态转移概率的随机性（与环境交互导致）：每个状态下的每个动作会有多个可能的下一个状态

5 状态函数/状态-行为值函数

5.1 值函数

强化学习具有延迟回报的特点，比如若是第n步棋输了，只知道状态sn,动作an的即时奖励，前面所有状态的即时奖励均为0，因此也不知道前面所有策略的好坏。

因此，定义一个值函数（value function)来表明当前状态下策略π的长期影响。

5.2 状态值函数

状态值函数是指agent在状态st根据策略π采取后续动作所得到的累积回报的期望，记为V(st)

其中

5.3 状态-行为值函数

状态-行为值函数是指agent从状态s出发，采取行为a后，再按照策略π采取行为得到的累积回报期望。
。
注意行为a不一定是π产生的。

6 Bellman方程

用Bellman方程来推导状态值函数和状态-行为值函数。

6.1 推导结果

• 状态值函数推导：
  

• 状态-行为值函数推导
  

6.2 关系

• 状态值函数等于该状态下所有状态行为值函数q的加权和，权重即为该状态下采取行为的概率π(a|s)
  

• 状态值函数等于该状态、该行为执行后的即时奖励的期望，加上它所有导致的所有下一步状态的折减后状态值函数V的加权和
  

• 可见其实状态值函数和状态-行为值函数相互之间是递推关系：

• 

6.4 示例

还是老问题

agent遵循的是随机策略，多有可能的行为有相同的概率被选择执行，圆圈里的数值是计算好的状态价值，现在来看看7.4这个圆圈是怎么计算得到的。
（1）首先，它有两个可能的动作，分别为概率0.5（此处假设γ=1）
（2）若是选择study行为，则会有10的即时回报，随后就达到了终止状态；若是选择行为pub则会有1的即时回报，然后在该状态该行为下分别会转移到3种状态，0概率分别为0.2，0.4，0.4，去到的状态值分别为-1.3，2.7，7.4，于是写成公式如下：

7 最优价值函数

大费周章地去求状态函数，状态行为函数，目的就是为了去求得最优价值函数。

• 最优状态值函数： 从所有策略产生的状态价值函数中，选择使状态s价值最大的函数
  

• 最优状态行为值函数：从所有策略产生的行为价值函数中，选取使状态行为对< s, a >价值最大的函数。
  

根据Bellman公式，可以分别求最优状态值函数，最优状态行为值函数的贝尔曼最优方程：

有了贝尔曼方程和贝尔曼最优方程后，就可以用动态规划等方法来求解MDP了。

8 最优策略

可以通过最大化最优行为价值函数来找到最优策略。即对于任意状态，求出该状态下所有动作a的状态-行为价值函数q(s,a), 然后选择状态行为价值最大的那个动作作为确定策略。

可以求得，下图中黄色的线就是最优策略

---

参考资料：
小象学院强化学习课程
https://blog.csdn.net/zz_1215/article/details/44138823
https://blog.csdn.net/VictoriaW/article/details/78839929
https://zhuanlan.zhihu.com/p/28084942
https://blog.csdn.net/u013745804/article/details/78206794