马尔可夫决策过程

强化学习原理

马尔科夫决策过程

马尔可夫决策过程是一个离散时间的随机过程，有六元组$\{S, A, D, P, r， J \}$组成，六元组中:
1. $S$有限维的环境状态空间
2. $A$是有限维的动作空间，$D$为初始状态的概率分布，如果初始状态的确定的，$D$在该初始状态下的概率为1，当初始状态是以相等的概率从所有状态中选择时，$D$可以忽略。
3. $P(s, a, s') \in [0, 1]$为状态转移概率，表示在状态$s$下选择动作$a$后使环境被转移到$s'$的概率
4. $r(s,a,s') : S \times A \times S' \rightarrow \mathcal{R}$为学习系统从状态$s$执行动作$a$转移到$s'$得到的立即回报
5. $J$是决策优化目标函数

马尔可夫决策过程的特点是目前状态$s$向下一个状态$s'$转移的概率和回报仅仅和当前状态的$s$和选择的$a$有关，和历史无关，因此MDP的转移$P$和立即回报$r$也只取决与当前状态和选择的动作，与历史状态和动作无关，公式表达：

$$P(s = s_t, a = a_t, s' = s_{t+1}) = p_r(s_{t+1}|s_ta_ts_{t-1}a_{t-1}\ ...\ s_0a_0) = p_r(s_{t+1}|s_ta_t)$$

若转移概率$P(s,a,s')$和回报函数$r(s,a,s')$与决策时间无关，那么MDP叫做平稳MDP

MDP的策略优化目标函数J一般可以分为3个类型，即有限阶段回报总函数、无限折扣总回报目标和平均回报目标，如下：

$$J = E[\sum\limits_{t = 0} ^Nr_{t+1}]$$

$$J = E[\sum\limits_{t=0}^\inf \gamma^tr_{t+1}]$$

$$J = \lim\limits_{N\rightarrow\inf}E[\sum\limits_{t=0}^Nr_{t + 1}]$$

式中$\gamma \in (0, 1]$为折扣因子，用于权衡立即回报和将来长期回报之间的重要性。平均回报是折扣回报的特例，实际上当折扣因子等于1时，这两种目标函数等价，折扣回报目标函数和平均回报目标函数在强化学习研究中均得到了广泛应用，但不同形式的优化目标函数将产生不同的结果。实际上，科学家Mahadevan证明，这两种目标函数当N很大时，效果近似。

策略和值

在马尔科夫决策过程中，Agent是根据一个策略函数来选择动作的，策略(policy)定义了Agent在给定时刻的行为方式，直接决定了Agent的动作，一个平稳随机性策略定义为$\pi : S\times A\rightarrow[0,1]$， $\pi(s,a)表示在给定状态s下选择动作a的概率$，且$\pi$不随时间变化。一个平稳确定行策略定义为从状态空间到动作空间的一个映射，即$\pi: S\rightarrow A$表示在状态s下，选择动作$\pi(a)$的概率等于1，其他动作的概率为0

定义了马尔可夫策略后，MDP对应的值函数可以分为状态值函数$V^{\pi}(s)$和状态-动作值函数(也称为动作值函数)$Q^{\pi}(s, a)$两种。状态值函数$V^{\pi}(s)$表示系统从状态s开始根据策略$\pi$选择动作得到的回报总期望

$$V^{\pi}(s) = E^{\pi}[\sum\limits_{k=0}^\inf\gamma^kr_{t+k+1}|s_t = s]$$

式中，$E^{\pi}$表示在状态转移概率P和策略$\pi$分布上的数学期望即：
$V^{\pi}(s) = E^{\pi}\{r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} \ ...\ |s_t = 2 \} \\ \qquad \ \ = E^{\pi}\{r_{t+1} + V^{\pi}(s+1)|s_t = s \} \\ \qquad \ \ = \sum\limits_a \pi(s,a)\sum\limits_{s'}P(s,a,s')(R(s,a,s') + \gamma V^{\pi}(s'))|s_t=s, s_{t+1}=s'$
其中， $R(s,a,s')=E\{r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3}... | s_t = s \}$

类似的，动作值函数$Q^{\pi}(s,a)$表示系统从状态-动作对(s,a)出发，根据策略$\pi$选择动作所获得的期望回报

$$Q^{\pi}(s,a) = E^{\pi}[\sum\limits_{t=0}^{\inf} \gamma^kr_{t + k + 1}|s_t = s, a_t = a]$$

实际上动作值函数和策略函数有一定的关联:
1. 对于一个确定的策略，有$V^{\pi}(s) = Q^{\pi}(s,\pi(s))$
2. 对于一个随机策略$\pi$,有$V^{\pi}(s)=\sum\limits_{a\in A}\pi(s,a)Q^{\pi}(s,a)$

而给定一个策略，动作值函数都可以用状态值函数表示:

$$Q^{\pi}(s,a) = R(s,a) + \gamma \sum\limits_{s'\in S}P(s,a,s')V^{\pi}(s')$$