David Silver deep reinforcement learning course in 2019. For document and discussion.

Lecture2: Markov Decision Processes

Ⅰ Markov Processes (Markov Chain)

1.Introduction to MDPs

• MDP描述的是RL中的环境(environment)，且该环境是fully observable
• MDP中的state完全描述了这个过程
• 几乎所有的RL问题都可以转换为MDPs
  • 最优控制主要处理连续的MDPs
  • Partially observable problems可以转换为MDPs
  • 多臂**机是只有一种state的MDPs

2.Markov Property

• state $S_t$St​是Markov当且仅当$P[S_{t+1}|S_t]=P[S_{t+1}|S_t,...,S_t]$P[St+1​∣St​]=P[St+1​∣St​,...,St​]

• 当前的状态已经包含了所有$t-1$t−1及其之前的历史信息，因此history可以丢弃，因此所有信息可用当前时刻$t$t下的一个特定的状态来表示,而不需要保留历史信息

• 该状态是future的充分统计量（$s$s包含了足够信息来描述未来所有的reward）

• state transition matrix (状态转移矩阵):

  • 对于一个Markov state $s$s及其后继state $s'$s′，状态转移概率为

• 状态转移矩阵$P$P定义了从state $s$s 转移到后继 $s'$s′ 的转移概率（每行的和为1），即从任一状态转移到其他状态的概率有多少（转移到其他所有状态的概率和为1）

3.Definition of Markov Process (Markov Chain)

• 是一个无记忆的，具有随机状态序列的，具有Markov属性的过程

• 定义为一个tuple $<S, P>$<S,P>， $S$S是一个有限的状态的集合，P为状态转移概率矩阵

• Example

• e.g.1 其中Sleep为Markov Process的最终状态，$P$P为该过程的状态转移矩阵

学生提问：如果处理概率随着时间变化的情况

答：有两种答案，一种是可以设定一个non-stationary Markov process，仍然使用stationary MDP的算法，但逐步调整算法来找到最好的算法，另一种是将其变为一个更复杂的Markov process，可以假设各个state上停留的时间，增加状态转移概率，但不改变MDP的基本结构。

Ⅱ Markov Reward Processes (MRP)

1.定义

• MRP是一个带有value的Markov chain，可知道在MP中积累了多少reward

• 定义为一个tuple $<S, P, R, γ>$<S,P,R,γ>

  • $S$S 是有限状态集合
  • $P$P 是状态转移概率矩阵
  • $R$R 是(immediate)reward函数，$R_s=E[R_{t+1}|S_t=s]$Rs​=E[Rt+1​∣St​=s]
  • $γ$γ 是折扣因子，$γ∈[0, 1]$γ∈[0,1]

• Example

2.Return（回报）

• 定义为$G_t$Gt​ ，是在$t$t时刻时的总折扣奖励（total discounted reward）→目标是最大化回报

  ​ $G_t=R_{t+1}+γR_{t+2}+...=∑_{k=0}^∞γ^kR_{t+k+1}$Gt​=Rt+1​+γRt+2​+...=k=0∑∞​γkRt+k+1​

  • 折扣$γ∈[0, 1]$γ∈[0,1]是对未来reward的关注程度值，$γ$γ值为0代表最大短视myopic（对应immediate reward），表示目光短浅，注重当前利益；$γ$γ值为1代表最大远见far-sighted（对应delayed reward），表示目光长远，深谋远虑。
  • 在$k+1$k+1时间后agent收到的reward是$γ^kR$γkR

学生提问：为何$G_t$Gt​不需要求取期望值

答：因为此处$G$G只是MRP中的一个随机样本

• 为什么需要折扣$γ$γ? 答：没有比较完美的model可以完全适用于环境中，或者说未来有很多的不确定性；便于数学计算；避免循环MPs中出现无限回报；未来的不确定性可能没有得到充分体现；如果reward是经济上的，立即的reward可能比延迟的reward获得更多的利息；人和动物的行为对immediate reward有趋向性；如果所有序列都终止，那么也可以使用非折扣的MRPs。

3.Value Function

• 定义为$v(s)$v(s)，是从状态$s$s 开始的预期return，是对所有可能过程的平均，即$v(s)=E[G_t|S_t=s]$v(s)=E[Gt​∣St​=s]
• Example $γ = 1/2$γ=1/2

4.Bellman Equation for MRPs (贝尔曼方程)

• value function可分解为$R_{t+1}$Rt+1​和$γv(S_{t+1})$γv(St+1​)两部分，可以看出，其只与状态s有关

• 贝尔曼方程可以被分成两部分，第一部分是在$t+1$t+1时刻获取到的immediate reward的期望和下一状态的有折扣的return的期望。第一部分因为$t+1$t+1时刻获取的reward期望其实是$t$t时刻的状态所获得的，因此期望符号可以略去，第二部分可以利用如下图所示的状态转移概率矩阵来求。

• 贝尔曼方程的矩阵形式-
  
• 贝尔曼方程的求解（为一个线性方程），计算需要$O(n^3)$O(n3)的时间复杂度，因此大型的MRPs问题不适合直接求解

• 对于大型的MRPs一般采取迭代的方法
  • 动态规划（Dynamic programming ）
  • 蒙特卡洛估计（Monte-Carlo evaluation）
  • 时间差分学习（Temporal-Difference learning）

Ⅲ Markov Decision Processes (MDPs)

1.MDPs的定义

• MDP其实是MRP基础上再加入action，处于所有状态都是Markov的环境，下一个state取决于采取的action和当前的state。

• 定义为一个tuple $<S, A, P, R, γ>$<S,A,P,R,γ>

  • $S$S是有限状态集
  • $A$A是有限动作集
  • $P$P是状态转移概率矩阵，其中$P_{ss'}^a=P[S_{t+1}=s'|S_t=s,A_t=a]$Pss′a​=P[St+1​=s′∣St​=s,At​=a]
  • $R$R是奖励函数，其中$R_s^s=E[R_{t+1}|S_t=s,A_t=a]$Rss​=E[Rt+1​∣St​=s,At​=a]
  • $γ$γ是折扣因子，

• Example：从例子中可以看出，每个action都有其对应的reward

2.Policy

• 定义为$π$π，是给定state下action的分布，实际上是一个状态转移矩阵，$π(a|s) = P[A_t = a | S_t = s]$π(a∣s)=P[At​=a∣St​=s]

• Policy完全定义了agent的行为（Markov Property）

• MDP的policy是基于当前state的（并非基于history）

• MDP转换为MP，MRP

3.Value Function

• state-value function定义为$v_π(s) $，是从状态s（遵循policy $π$π）开始的期望回报$v_π(s) = E_π [G_t | S_t = s]$vπ​(s)=Eπ​[Gt​∣St​=s]

• action-value function定义为$q_π(s,a)$qπ​(s,a) ，是从状态s和动作a（遵循policy $π$π）开始的期望$q_π(s,a) = E_π [G_t | S_t = s,A_t = a]$qπ​(s,a)=Eπ​[Gt​∣St​=s,At​=a]

• Example

• 贝尔曼期望方程，同样也可以分解为reward项和下一state的期望

• 同样对以上方程进行分解

• 将二者叠加则会产生如下结果

• 基于以上分解，就不难计算出Example中的各个值

• 贝尔曼分解方程的矩阵形式

### 4.Optimal Value Function（最优值函数）

• 目的：找到MDPs中最优的动作（即最优解决问题的方法

• 最佳状态值函数 $v_*(s)$v∗​(s)是所有策略情况下的最大值函数 $v_∗(s) = max_πv_π(s)$v∗​(s)=maxπ​vπ​(s)

• 最佳动作值函数 $q_∗(s,a)$q∗​(s,a)是所有策略情况下的最大动作值函数 $q_∗(s,a) = max_π q_π(s,a)$q∗​(s,a)=maxπ​qπ​(s,a)

• 最佳值函数(the optimal value function)说明了MDP中可能出现的最佳性能

• 当知道最优值函数后，可以MDP过程相当于有解了

• Example（从最优值10往前推）

5.Optimal Policy（最优策略）

• 定义策略上的偏序 $π ≥ π'\;if\;v_π(s) ≥ v_{π'}(s),∀s$π≥π′ifvπ​(s)≥vπ′​(s),∀s，即一个最优策略的状态值函数要在任何状态下都优于（至少等于）其他的策略状态值函数，

• 任何一个MDP都至少存在一个最佳的策略 $π_*$π∗​优于或等于其他的策略 $π_*≥π,∀π$π∗​≥π,∀π

• 最优策略表示一个MDP中最好的behavior是什么

• 最优策略都能达到最优的值函数(optimal policies → optimal value functions) $v_{π_∗}(s) = v_∗(s)$vπ∗​​(s)=v∗​(s)

• 最优策略都能达到最优的动作值函数 (optimal policies → optimal action-value functions) $q_{π_∗}(s,a) = q_∗(s,a)$qπ∗​​(s,a)=q∗​(s,a)

• 寻找最优策略：通过最大化$q_*(s,a)$q∗​(s,a)可以找到，如下公式所示

• 因此，如果知道了$q_*(s,a)$q∗​(s,a)，就可以获得最优策略

• Example

6.Bellman Optimality Equation（贝尔曼最优方程）

• 最优值函数通过贝尔曼最优性方程递归关联
  

• 进一步推算

• Example

• ​ 求解贝尔曼最优方程（非线性，因为包含max函数，因此没有闭式解）
  • Value Iteration（值迭代）
  • Policy Iteration（策略迭代）
  • Q-learning
  • Sarsa

Ⅳ Extensions to MDPs

1.Infinite and continuous MDPs （无限和连续）

• 可数无限的状态和动作空间，按以上方式求解
• 连续状态和动作空间，使用线性二次模型的封闭形式
• 连续时间的情况，需要偏微分方程及HJB方程求解，贝尔曼方程时间步长为0的极限情况

2.Partially observable MDPs（部分可观察POMDP）

• 定义：部分可观察MDP是一种具有隐状态的MDP决策过程，这是一个具有动作的隐马尔可夫模型。
• 从定义中可以看出，状态转移矩阵$P$P是不可见的，$s'$s′为隐状态，而$o$o才为实际可观测状态

• history重新定义为 actions, observations and rewards $H_t = A_0,O_1,R_1,...,A_{t−1},O_t,R_t$Ht​=A0​,O1​,R1​,...,At−1​,Ot​,Rt​

• 隐状态分布，也就是信念状态 $b(h)$b(h)是在给定history下的状态的概率分布

  $b(h) = (P[S_t = s^1 | H_t = h],...,P[S_t = s^n | H_t = h])$b(h)=(P[St​=s1∣Ht​=h],...,P[St​=sn∣Ht​=h])

• POMDP的简化表示

3.Undiscounted, average reward MDPs（无折扣，奖励平均）

• 各态历经的MP，历经无限时间，无系统的周期

• 各态历经的MDP（满足任意策略的导出的MP都是各态历经的）

• 平均奖励值函数

References

https://www.bilibili.com/video/BV1kb411i7KG?from=search&seid=5362588914313557002

https://blog.****.net/u013745804/category_7216686.html

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

（转载整理自网络，如有侵权，联系本人删除，仅供技术总结使用）