RL-Lec2.1 马尔可夫决策过程

Markov Decision Process

Posted by Watthu on September 14, 2022

马尔可夫过程(Markov Process)

称一个状态 $S_t$ 是马尔可夫的当且仅当

$\mathbb P(S_{t+1}\mid S_t)=\mathbb P(S_{t+1}\mid S_1,\dots,S_t),$

换言之,当前状态已知时,未来的状态与过去的状态无关,我们完全可以抛弃过去的状态,即当前状态是未来状态的充分统计量。

由此一个马尔可夫过程可以完全由状态转移概率矩阵及初始状态来决定。对当前状态 $s$ 和后继状态 $s’$,定义转移概率为

$\mathcal P_{ss'}=\mathbb P(S_{t+1}=s'\mid S_t=s).$

这样,状态转移概率矩阵即为所有状态之间的转移概率构成的 $n$ 阶矩阵

$\begin{array}{cc} ~ & \text{to}\\ \mathcal P=\text{from} & \left[\begin{array}{ccc} \mathcal P_{11} & \cdots & \mathcal P_{1n}\\ \vdots & ~ & \vdots\\ \mathcal P_{n1} & \cdots & \mathcal P_{nn} \end{array}\right]. \end{array}$

其中每一行的概率和为 $1$。


定义(马尔可夫过程) 一个马尔可夫过程(或马尔可夫链)是一个二元组 $\langle\mathcal S,\mathcal P\rangle$,其中:

  • $\mathcal S$ 是状态的集合;
  • $\mathcal P$ 是状态转移概率矩阵,$\mathcal P_{ss’}=\mathbb P(S_{t+1}=s’\mid S_t=s)$。

马尔可夫奖励过程(Markov Reward Process)

马尔可夫奖励过程是带效用的马尔可夫过程。


定义(马尔可夫奖励过程) 一个马尔可夫奖励过程是一个四元组 $\langle\mathcal S,\mathcal P,\mathcal R,\gamma\rangle$,其中:

  • $\mathcal S$ 是状态的集合;
  • $\mathcal P$ 是状态转移概率矩阵,$\mathcal P_{ss’}=\mathbb P(S_{t+1}=s’\mid S_t=s)$;
  • $\mathcal R$ 是奖励函数,$\mathcal R_s=\mathbb E(R_{t+1}\mid S_t=s)$;
  • $\gamma$ 是折扣率,$\gamma\in[0,1]$。

注意定义中的奖励函数是对当前状态的下一个可能奖励(随机变量)的期望。


定义(回报) 回报是指从当前时刻开始的总折扣奖励,即

$\displaystyle G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}.$

从回报的定义可以看出,折扣率 $\gamma$ 越接近于 $0$,越倾向于短视评估,越接近于 $1$,越具有长远的利益考虑。折扣率的引入主要是出于以下几个原因:

  • 数学表达式上更加方便对奖励进行折扣;
  • 避免陷入无限循环,如果存在某个环的整体奖励为正,则可通过在环内循环达到无穷的回报;
  • 远期利益具有比较大的不确定性;
  • 在金融中,即时奖励与延迟奖励存在本质差别;
  • 人们更加看重眼前的短期奖励。

定义(值函数) 一个马尔可夫奖励过程中某一状态的值函数为从当前状态开始的回报的期望,即

$v(s)=\mathbb E(G_t\mid S_t=s).$

值函数给出了某一状态的长期价值,由于 $G_t$ 是随机变量,因此这里可以对其取期望。

贝尔曼方程(MRP)

下面介绍求解值函数的重要方法,即贝尔曼方程。注意到回报可以被分解成两部分:

$\begin{array}{rl} G_t = &\!\!\!\! R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots\\ = &\!\!\!\! R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\cdots)\\ = &\!\!\!\! R_{t+1}+\gamma G_{t+1}, \end{array}$

于是

$\begin{array}{rl} v(s) = \mathbb E(G_t\mid S_t=s) = &\!\!\!\! \mathbb E(R_{t+1}+\gamma G_{t+1}\mid S_t=s)\\ = &\!\!\!\! \mathbb E[R_{t+1}+\gamma v(S_{t+1})\mid S_t=s]\\ = &\!\!\!\! \displaystyle\mathcal R_s+\gamma\sum_{s'\in\cal S}\mathcal P_{ss'}v(s'). \end{array}$

若记 $v=(v(1),\dots,v(n))^{\textsf{T}}$,$\mathcal R=(\mathcal R_1,\dots,\mathcal R_n)^{\textsf{T}}$,则上式可写成矩阵形式如下:

$v=\mathcal R+\gamma\mathcal Pv~\Longrightarrow~v=(I-\gamma\mathcal P)^{-1}\mathcal R.$

受限于矩阵求逆,求解值函数的算法复杂度为 $O(n^3)$。对于小规模的MRP可以直接得到显式解,而对于大规模的MRP通常需要迭代,相应的方法有:

  • 动态规划(Dynamic Programming)
  • 蒙特卡洛模拟(Monte-Carlo Evaluation)
  • 时序差分学习(Temporal-Difference Learning)

后面会一一进行介绍。

马尔可夫决策过程(Markov Decision Process)

马尔可夫决策过程是带决策的马尔可夫奖励过程。在MDP中,$\cal P$ 和 $\cal R$ 都与具体的行为有关,而不仅仅只依赖于状态。


定义(马尔可夫决策过程) 一个马尔可夫决策过程是一个五元组 $\langle\mathcal S,\mathcal A, \mathcal P,\mathcal R,\gamma\rangle$,其中:

  • $\mathcal S$ 是状态的集合;
  • $\mathcal A$ 是行动的集合;
  • $\mathcal P$ 是状态转移概率矩阵,$\mathcal P_{ss’}^a=\mathbb P(S_{t+1}=s’\mid S_t=s,A_t=a)$;
  • $\mathcal R$ 是奖励函数,$\mathcal R_s^a=\mathbb E(R_{t+1}\mid S_t=s,A_t=a)$;
  • $\gamma$ 是折扣率,$\gamma\in[0,1]$。

在同一个状态下Agent可能会采取不同的行动,这种行动的分布称为策略(Policy)。


定义(策略) 一个策略 $\pi$ 是给定状态下的行动分布,即

$\pi(a\mid s)=\mathbb P(A_t=a\mid S_t=s).$

这里需要注意的是,MDP策略仅仅取决于当前状态,也就是说,它是一个平稳分布(时间独立)$A_t\sim\pi(\cdot\mid S_t), \forall t>0$。

当给定一个MDP $\mathcal M=\langle\mathcal S,\mathcal A, \mathcal P,\mathcal R,\gamma\rangle$ 和策略 $\pi$ 之后,状态序列 $S_1,S_2,\dots$ 就是一个马尔可夫过程 $\langle\mathcal S,\mathcal P^\pi\rangle$,这样MDP就变成了MRP $\langle\mathcal S, \mathcal P^\pi,\mathcal R^\pi,\gamma\rangle$,其中

$\displaystyle\mathcal P_{ss'}^\pi=\sum_{a\in\cal A}\pi(a\mid s)\mathcal P_{ss'}^a,\quad\mathcal R_s^\pi=\sum_{a\in\cal A}\pi(a\mid s)\mathcal R_s^a.$

这本质上就是一个条件概率的乘法公式及全概率公式。从这里可以看出,基于策略产生的每一个马尔可夫过程都是一个MRP,各过程之间的差别是不同的选择产生了不同的后继状态,从而有不同的奖励和回报。


定义(状态值函数) 状态值函数是指在执行当前策略 $\pi$ 下MDP从当前状态开始的期望回报,即

$v_\pi(s)=\mathbb E_\pi(G_t\mid S_t=s).$


定义(行动值函数) 行动值函数是指在执行当前策略 $\pi$ 下,对当前状态执行某一具体行为所得到的期望回报,即

$q_\pi(s,a)=\mathbb E_\pi(G_t\mid S_t=s,A_t=a).$

贝尔曼方程(MDP)

有了上述概念基础,与MRP的贝尔曼方程类似地,同样我们希望求状态值函数和行动值函数的具体结果。

基于回报的分解,可以得到

$v_\pi(s)=\mathbb E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s].$

以及

$q_\pi(s,a)=\mathbb E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})\mid S_t=s,A_t=a].$

由全概率公式可知

$\displaystyle v_\pi(s)=\sum_{a\in\cal A}\pi(a\mid s)q_\pi(s,a),\quad q_\pi(s,a)=\mathcal R_s^a+\gamma\sum_{s'\in\cal S}\mathcal P_{ss'}^av_\pi(s').$

代入得

$\displaystyle v_\pi(s)=\sum_{a\in\cal A}\pi(a\mid s)\left(\mathcal R_s^a+\gamma\sum_{s'\in\cal S}\mathcal P_{ss'}^av_\pi(s')\right),$
$\displaystyle q_\pi(s,a)=\mathcal R_s^a+\gamma\sum_{s'\in\cal S}\mathcal P_{ss'}^a\sum_{a'\in\cal A}\pi(a'\mid s')q_\pi(s',a').$

不难发现,上式的矩阵形式即

$v_\pi=\mathcal R^\pi+\gamma\mathcal P^\pi v_\pi~\Longrightarrow~v_\pi=(I-\gamma\mathcal P^\pi)^{-1}\mathcal R^\pi.$

得到了 $v_\pi$,自然就有了 $q_\pi$,从而得到了最优策略和最优值函数。

后记

本文内容来自中国科学技术大学《强化学习》(2022Fall)课件。

如对本文内容有任何疑问,请联系 watthu@mail.ustc.edu.cn