马尔可夫决策过程

马尔可夫决策过程

马尔可夫决策过程,英文为:Markov decision processes,简称为:MDP。马尔可夫决策过程是顺序决策问题的经典数学描述,也是强化学习问题的数学描述和理论基础。几乎所有的强化学习问题都可以构造成马尔可夫决策过程。本文从介绍马尔可夫性质开始,接着介绍马尔可夫过程,然后介绍马尔可夫奖励过程,最后再介绍马尔可夫决策过程及其扩展。

马尔可夫性质

通俗地说,马尔可夫性质是指,未来只与当前状态有关,与过去无关。其数学定义为:

$$P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t]$$

从上式可知,当前状态包含了历史中的所有相关信息,因此,只要知道了当前状态,所有的历史信息就不再需要了。

马尔可夫过程

人们在实际中常遇到具有下述特性的随机过程:在已知它所处的状态的条件下,它未来的演变不依赖于它以往的演变。这种已知“现在”的条件下,“将来”与“过去”独立的特性称为马尔可夫性,具有这种性质的随机过程叫做马尔可夫过程。荷花池中一只青蛙的跳跃是马尔可夫过程的一个形象化的例子。青蛙依照它瞬间或起的念头从一片荷叶上跳到另一片荷叶上,因为青蛙是没有记忆的,当所处的位置已知时,它下一步跳往何处和它以往走过的路径无关。如果将荷叶编号并用$X_0,X_1,X_2,...$分别表示青蛙最初处的荷叶号码及第一次、第二次、……跳跃后所处的荷叶号码,那么$\{X_n,n \geqslant 0\}$ 就是马尔可夫过程。

马尔可夫奖励过程

马尔科夫奖励过程在马尔科夫过程的基础上增加了奖励$R$和折扣系数$\gamma$。其定义为:马尔科夫奖励过程是一个元组$<S,P,\color{red} R\color{default},\gamma>$,其中

  • $S$是有限数量的状态集
  • $P$是状态转移概率矩阵
  • $R$是一个奖励函数,$ R_{s} = E[R_{t+1} | S_{t} = s] $
  • $\gamma$是一个折扣因子,$\gamma \in [0,1]$

奖励函数

R是一个奖励函数。在当前状态$S_{t}$下,执行动作$a_{t}$,进入到下一个时刻(t+1)能获得的奖励期望。R约定为离开该状态获得的奖励,而不是进入该状态获得的奖励,即$S_{t}$对应奖励为$R_{t+1}$。这个约定主要原因:因为状态是从$S_{0}$ 开始的,智能体未采取动作之前,环境有一个初始状态。$S_{0}$的奖励为离开$S_{0}$的奖励,离开$S_{0}$后进入下一个状态。

回报

回报(或译为“收益”)[公式]为从时间步t开始带折扣的奖励总和。公式如下:

$G_{t} = R_{t+1} + \gamma R_{t+2} + \ldots = \sum_0^\infty \gamma^k R_{t+k+1}$

参考

https://zhuanlan.zhihu.com/p/494755866