强化学习笔记(二): 马尔可夫决策过程

1. 基本概念

马尔可夫决策过程(Markov Decision Process,MDP)可以给真实世界的任务进行建模,所以其形式化地描述了强化学习的框架
马尔可夫决策过程假设所有环境都可以被观测

马尔可夫决策过程可以看作下列逐渐复杂模型的最终形态:

马尔可夫过程/马尔可夫链(Markov Processes,MP)
==>马尔可夫奖励过程(Markov Reward Processes,MRP)
==>马尔可夫决策过程(Markov Decision Processes,MDP)

马尔可夫性质:未来只与当前状态有关,与历史状态无关

2. 马尔可夫过程/马尔可夫链

马尔可夫链类似于有限状态机(把行为换成概率):

• 有限个状态(state)
• 不同状态可以互相转换(有不同的概率)

设状态总数为 n,马尔可夫链可以表示为一个 n×n 的矩阵
其中的元素表示一个状态转换到另一个状态的概率

3. 马尔可夫奖励过程

3.1 基本概念

马尔可夫奖励过程可以看作是在马尔可夫链的基础上加上状态转换的奖励机制

• 不同的状态本身有一个价值(可以把所有状态的值表示为一个向量)

$$R(S_t=s)=E[r_t|s_t=s]$$

• 奖励在传播的过程中会衰减,衰减系数为:

$$\gamma \in [0,1]$$

• Horizon:马尔可夫过程一次经历(episode)的最大步数,记作T,可以为无限大(称为无限马尔可夫过程)

$$T$$

• Return:在一个状态上,对于未来所有的奖励的衰减求和(Discounted sum)

$$G_t=R_{t+1}+\gamma R_{t+2} + \gamma ^2 R_{t+3}+...+\gamma ^{T-t-1}R_T$$

• value function:s 状态Return的期望值,同时value function满足Bellman equation

$$\begin{aligned} V_t(s) &= E[G_t|s_t=s] \\ &= E[R_{t+1}+\gamma R_{t+2} + \gamma ^2 R_{t+3}+...+\gamma ^{T-t-1}R_T|s_t=s]\\ V(s) &= R(s) + \gamma \sum_{s' \in S}P(s|s')V(s') \end{aligned}$$

3.2 贝尔曼等式

贝尔曼等式(Bellman equation)是价值函数(value function)满足的一个等式

$$V(s) = R(s) + \gamma \sum_{s' \in S}P(s|s')V(s')$$

贝尔曼等式可以写成矩阵的形式

需要注意的是,价值函数只有在完全收敛之后才满足贝尔曼等式
所以可以通过解贝尔曼等式来得到价值函数的解析解
但是这样代价太大,很难做到,只能对一些小型的模型这么做

3.3 MRP 的蒙特卡洛解法

简单来说就是通过大量的实验,取结果的平均值作为期望
我们已知每个状态的 R(固有价值/奖励),从一个状态出发,模拟大量路径(episode)
计算所有路径的返回值,并取其平均值作为状态的价值(value)

3.4 MRP 的迭代解法

小型的 MRP 问题可以通过解贝尔曼等式得到答案,但是大型的 MRP 必须通过其他方法解

迭代解法的思想就是把贝尔曼等式作为迭代规则(rule)
在迭代到价值函数不再变化的时候,认为贝尔曼等式成立,即得到最终的解

4. 马尔可夫决策过程

4.1 基本概念

马尔可夫决策过程可以看成是,在 MRP 的基础上增加了动作
即在一个状态时,可以选择不同的动作,从而选择接下来状态的概率

原本 MRP 进入不同状态的概率及其回报

$$P(s_{t+1} = s'|s_t = s)\\ R(s_t = s) = E[r_t|s_t = s]$$

MDP 进入不同状态的概率及其回报(选择不同的策略会得到不同的回报确实有点迷)

$$P(s_{t+1} = s'|s_t = s, a_t = a)\\ R(s_t = s, a_t = a) = E[r_t|s_t = s, a_t = a]$$

同时 MDP 新增了一个策略概念(Policy),即在不同的状态选择那个行动
同时根据马尔可夫过程的假设,策略只根据当前状态选择不同的行动

$$\pi(a|s) = P(a_t = a|s_t = s)$$

在给定一个策略的时候,一个 MDP 可以等价于一个 MRP

$$\begin{aligned} P^{\pi}(s'|s) &= \sum _{a \in A}\pi(a|s)P(s'|s,a)\\ R^{\pi}(s)&=\sum_{a \in A}\pi(a|s)R(s,a) \end{aligned}$$

4.2 MDP 的价值函数

MDP 除了价值函数外,还有一个特殊的action-value function,即 Q 函数
Q 函数为给定了行动的行动价值函数
而原本的价值函数为

$$\begin{aligned} v^{\pi}(s)&=E_{\pi}[G_t|s_t=s] \\ q^{\pi}&=E_{\pi}[G_t|s_t=s,A_t=a] \\ v^{\pi}(s)&=\sum _{a \in A}\pi(a|s)q^{\pi}(s,a) \end{aligned}$$

同时 MDP 的价值函数也有两个个与 MRP 类似的贝尔曼等式

$$\begin{aligned} &MDP中价值函数的定义\\ &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)] \\ \\ &MDP中v函数与q函数的关系\\ &v^{\pi}(s)=\sum _{a \in A}\pi(a|s)q^{\pi}(s,a)\\ &q^{\pi}(s,a)=R_s^a + \gamma \sum _{s' \in S}P(s'|s,a)v^{\pi}(s')\\ \\ &MDP中的贝尔曼等式\\ &v^{\pi}(s)=\sum_{a\in A}\pi[a|s](R(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)v(s'))\\ &q^{\pi}(s,a)=R(s,a) + \gamma \sum_{s'\in S}P(s'|s,a)\sum_{a'\in A}\pi(a'|s')q^{\pi}(s',a') \end{aligned}$$

4.3 Making Decision on MDP

不知道该翻译成啥好,大概就是怎么解 MDP 模型,通常有两种类型的问题:

1. Prediction(Policy Evaluation)
   根据一个策略和一套 MDP 环境得到一套价值函数,方法即4.4节的方法
2. Control(search the optimal policy)
   输入 MDP 的环境(即 <$S,A,P,R,\gamma$> )
   输出最佳的价值函数及其对应的策略

最佳价值函数及其对应的策略定义如下:

$$v^*(s)=\max_{\pi}v^{\pi}(s)\\ \pi ^*(s)= argmax_{\pi}v^{\pi}(s)$$

当得到$v^*$时,我们就可以说”解”完了一个 MDP 问题
一个 MDP 问题的解必定对应一套最佳价值函数,但是可能对应多套最佳策略
在知道最佳价值函数后,最佳策略可以按照如下公式得到

$$\pi ^*(a|s)= \begin{cases} 0&,if\ a = argmax_{a\in A} q^*(s,a)\\ 1&,otherwise \end{cases}$$

4.4 Policy Evaluation

和 MRP 类似,解 MDP 不能硬解,一般使用迭代的方式解

首先指定一套策略(Policy),然后根据不同状态的固有奖励$R(s)$,策略$\pi$和衰减系数$\gamma$,把贝尔曼等式作为迭代的规则进行迭代,最终得到这套策略在给定环境中对应的价值函数

$$v^{\pi}(s)=\sum_{a\in A}\pi[a|s](R(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)v(s'))$$

由于策略不变,并且同通过这个策略得到一套价值函数,所以这种方法称为Policy Evaluation(策略评估),也称为(value) prediction(价值预测)

4.5 MDP Control

Policy Iteration

可以使用Policy Iteration完成 MDP Control 任务,方法如下:

1. 执行Policy Evaluation
2. 在得到的价值函数上执行贪心算法,提升策略,即Policy Improvement

至于这种方法的有效性(即单调性)怎么证明,可以自行搜索(略过证明过程)

Policy Improvement 的方法如下:

1. 首先根据 Policy 计算 Q 函数(Q 函数就像是一个映射表,所以其又被称为Q-table,即 Q 表)

   $$q^{\pi i}(s,a)=R(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)v^{\pi i}(s')$$

2. 根据 Q 函数执行贪心算法得到更好的策略

$$\pi_{i+1}(s) = argmax_aq^{\pi i}(s,a)$$

Value Iteration

贝尔曼等式只有在最佳价值函数和最佳策略上才正确,但是可以将其作为更新策略进行迭代,这种方法称为价值迭代(Value Iteration)

如下是原本的贝尔曼等式

$$v^{\pi}(s)=\sum_{a\in A}\pi[a|s](R(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)v(s'))\\$$

结合策略的生成公式

$$\pi ^*(a|s)= \begin{cases} 0&,if\ a = argmax_{a\in A} q^*(s,a)\\ 1&,otherwise \end{cases}$$

可得价值函数的迭代方式(直接省去策略作为中间商赚差价(指耗费时间)):

$$v^{\pi}(s)=\max_{a\in A}[R(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)v(s')]$$

价值迭代的算法如下:

从某个方面来看,价值迭代可以看作是一个特化的策略迭代(但是速度更快)
即每次只迭代一次价值函数,而 max 函数可以看作是贪心算法的简化

4.6 Summary

问题	数学基础	算法
Prediction	Bellman Expectation Equation Iterative	Policy Evaluation
Control	Bellman Expectation Equation	Policy Iteration
Control	Bellman Optimality Equation	Value Iteration

5. 动态规划(番外内容)

5.1 基本概念

动态规划是一种非常通用的解法,其要求被解的问题有如下特点:

• 最优化问题可以分解为子问题
• 子问题依然满足动态规划条件要求(即可递归求解)
• 解可以缓存和重复利用

5.2 缺点及改进

动态规划解 MDP 最大的缺点—需要对整个状态集进行扫描
如果状态集非常大,则动态规划的每次扫描会花费大量时间
为了解决这个问题,异步动态规划方法使用”in-place”迭代的方法代替对整个状态集的扫描

三个异步动态规划的思想:

• In-place 动态规划

  

• 分优先级扫描

  优先级即哪些状态需要被优先扫描和更新,可以使用贝尔曼误差来作为优先级,可以使用优先级队列实现

  $$|\max_{a\in A}[R(s,a) + \gamma\sum_{s'\in S}P(s'|s,a)v(s')]-v(s)|$$

• 实时动态规划

  实时动态规划即在运行的同时对 MDP 进行动态规划更新
  根据状态被实际被遍历的频繁程度决定更新哪些状态