马尔科夫决策过程

1 基本模型

马尔科夫决策过程的基本模型是一个四元组$<S,A,T,R>$

状态空间$S$：指智能体所有可能相处的状态的集合

行为空间$A$：指智能体在所有状态上可能采取的行为集合

状态转移函数$T：S\times A\times S^{\prime }\to [0,1]$，$T(s,a,s^{\prime })$表示在状态$s$采取动作$a$转移到状态$s^{\prime }$的概率，有${\sum }_{s^{\prime }\in S}T(s,a,s^{\prime })=1$

收益函数$R：S\times A\to R$，在这儿一般用$R(s,a)$表示在状态$s$采取动作$a$得到的立即收益。

2 模型的意义

马尔科夫决策过程模型的意义在于对智能体所处的每一个状态$s$给出一个最优的行为，在这里将之称为策略，用$\pi (s)$表示。这个行为要以智能体获得的长期报酬的期望最大化为目标，即$\max E[{\sum }_t{R}_t(s_t,a_t)]$。$R_t$表示智能体在第$t$步得到的报酬。为了保证模型收敛可解，这里通常会引入一个折扣因子$\gamma ,0<\gamma <1$，这时长期报酬就可写为

$\max E[{\sum }_t{\gamma }^t{R}_t(s_t,a_t)]$

定义智能体的值函数$V^{\pi }:S\to R$为在状态$s$，采用策略$\pi$的期望报酬

$V^{\pi }(s)=E[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_t(s_t,a_t)]$

对公式1利用全概率公式递归展开可得

$V^{\pi }(s)=R(s,\pi (s))+\gamma {\sum }_{s^{\prime }\in S}{T}^{\pi (s)}(s,s^{\prime })V^{\pi (s)}(s^{\prime })$

为了更好的描述策略，定义一个行为值函数的概念$Q^{\pi }:S\times A\to R$，表示在状态$s$采取行为$a$，其他状态继续采用策略$\pi$所得到的报酬，计算方法如下，

$Q^{\pi }(s,a)=R(s,a)+\gamma {\sum }_{s^{\prime }\in S}{T}^a(s,s^{\prime })V^{\pi }(s^{\prime })$

为了得到最大的报酬，有

$\pi (s)=\arg {\max }_{a\in A}{Q}^{\pi }(s,a)$

即

$\pi (s)=\arg {\max }_{a\in A}R(s,a)+\gamma {\sum }_{s^{\prime }\in S}{T}^a(s,s^{\prime })V^{\pi }(s^{\prime })$

结合公式2可得，

$V^{\pi }(s)={\max }_{a\in A}R(s,a)+\gamma {\sum }_{s^{\prime }\in S}{T}^a(s,s^{\prime })V^{\pi }(s^{\prime })$

3 模型的求解

值迭代

算法流程如下

1. 对所有的$s\in S$ 随机初始化$V(s)=0$
2. 根据公式6，对$V(s)$进行更新，直至收敛

与线性方程组的迭代解法类似，值迭代流程的第二步可以采用同步和异步的不同方式进行更新。

策略迭代

1. 对所有的$s\in S$,随机初始化策略$\pi (s)$
2. 根据公式6对V(s)进行更新，根据公式5，对策略进行更新