马尔可夫决策过程

马尔可夫性

简单表述为:下一个状态只与当前状态有关。

例如下象棋就满足马尔可夫性,但斗地主则不满足。因为对于象棋来说,你仅需看到当前棋子位置便能做出下一步的决策,例如残局。但斗地主则不行,你不能只看当前自己的牌面去选择打什么牌,你还需要记住已经打过哪些牌了才能做出最好的决策,这就和历史状态有关了。(当然,如果将已经出牌的过程作为当前状态的要素,则也是满足马尔可夫性的)

用公式表示为:

$$ P(s_{t+1}|s_t) = P(s_{t+1}|s_t, s_{t-1}, s_{t-2}…s_0) $$

解释为:从状态 \( s_t \) 转移到状态 \(s_{t+1}\) 的概率与从状态 \(s_{t0}->s_{t1}->…s_t\) 转移到 \(s_t\) 的概率相同

马尔可夫链(MP)

或称马尔可夫过程,满足马尔可夫性的状态转移过程

如下图看着貌似复杂,其实很简单,就是从一个状态转移到另一个状态的概率。例如从宿舍去网吧的概率为30%,而从宿舍到教室学习的概率为50%,还有20%的概率是呆在宿舍。

这些状态转移的过程就形成了一条条的链,例如:从宿舍到网吧,再到健身房,再成为三和大神就是一条链。

马尔可夫奖励过程(MRP)

上面图中的每个状态都对应一个奖励(图中表示的就是自信心增长程度,可能为负)。

宿舍 -> 网吧 -> 健身房 -> 三和大神 这个过程的总奖励(最终精神状态)为 -1 -2 +10 -30 = -23

但是,我从网吧出来有可能去健身房最终走向人生巅峰,也有可能直接成为大神,它们的奖励不同,我该如何评价我在网吧这个状态呢?显然你不能简单得说它是好还是不好。最简单的方式就是计算该状态下,可能得到所有奖励的数学期望。即:

$$ R_s = \mathbb{E}[R_{t+1} | S_t = s] $$

\( t \) 时刻的状态 \( S_t \) 为 \( s \),其下一个时刻 \( t+1 \) 可能进入 \( S_{t+1} \) 状态,该新状态得到的奖励值为 \(R_{t+1} \),\( R_s \) 即为所有可能的 \( S_{t+1} \) 状态奖励的期望。

故,一个马尔可夫奖励过程可以用一个四元组 \( <S, P, R, γ> \) 表示。其中 S 为状态集合(教室、网吧、宿舍等),P 为状态转移概率矩阵(从一个状态转移到另一个状态的概率集合),R 为状态奖励(各个状态的奖励),γ为折扣因子。

折扣因子:一个大于0小于1的数。上图中,你从宿舍去网吧或者从宿舍到教室最终都有可能走上人生巅峰,但显然,你之所以能从网吧走向人生巅峰,是因为你可能会去健身房,然后遇到了一个富婆。但是遇到富婆这件事和你去网吧的关系不是很大,而是和你去健身房的关系比较大。可以想到,你当前做的事对你短期的未来可能会产生较大影响,而对长期的未来产生的影响会越来越小,即遥远的将来产生的奖励和你现在的状态关系越来越小。所以就引入折扣因子这个概念。

上面只是在一个状态下可能得到的奖励均值。一局完整的游戏可能需要经历很多状态,这个过程中的某个状态及其后续所有状态的奖励相加得到总奖励,称之为该状态的回报。故,在某一局游戏(或者一个人的一生)中,计算某个状态的回报可以表示为:

$$ G_t = R_{t+1} + λ*R_{t+2} + λ^2*R_{t+3} +… $$

使用回报的期望(多局游戏的回报平均值)来表示某个状态的价值:

$$ \begin{align} v(s) &= \mathbb{E}[G_t | S_t = s] \\ &= \mathbb{E}[R_{t+1} + λ*R_{t+2} + λ^2*R_{t+3} +…|S_t = s] \\ &= \mathbb{E}[R_{t+1} + λ(R_{t+2} + λ*R_{t+3} +…) |S_t = s] \\ &= \mathbb{E}[R_{t+1} + λ(G_{t+1}) |S_t = s] \\ &= \mathbb{E}[R_{t+1} |S_t = s] + \mathbb{E}[λG_{t+1} |S_t = s] \\ &= R_s + λv(s_{(t+1}|S_t = s)) \\ &= R_s + λ\sum_{s’∈S}P_{(s \rightarrow s’)}v(s’) \end{align}$$

其中 s’ 为 t+1 时刻的状态, \( P_{(s \rightarrow s’)} \) 表示从状态 s 转移到状态 s’ 的概率

马尔可夫决策过程(MDP)

马尔可夫决策过程就是在MRP中加入了动作策略。

若将上图中网吧和宿舍之间的状态转移过程单拿出来:

问题来了,为什么会有这些状态转移概率。例如为什么从宿舍到宿舍的概率为20%,而去网吧的概率为30%?

再在状态转移的基础上加上动作:

对上图的解释:假设这个人目前待在宿舍睡觉,他可以选择 打游戏(10%)、继续睡觉(10%)、起床(80%) 三个动作,选择每个动作的概率如图。并且执行每个动作后,都可能进入新的状态。例如若选择了继续睡觉,则状态100%转移为宿舍,若选择打游戏,则有60%的可能性去网吧打(状态从宿舍转移到网吧),有40%的概率在宿舍打(状态在宿舍不变)

此时就能计算出,他从宿舍这个状态转移到网吧这个状态的概率:10% * 60% + 80% * 30% = 30%

这就解释了为什么从宿舍转移到网吧的概率为30%,是因为其选择动作的概率不同。

由此,我们将上面的状态价值函数进行进一步的细分,假设整个系统中的动作集合为 A,动作选择策略为 Π(a|s) 则:

$$ \begin{align} v(s) = \sum_{a∈A}[Π(a|s)(R_s^a + λ\sum_{s’∈S}P_{(s \rightarrow s’)}^av(s’))] \end{align} $$

上式中 \(R_s^a\) 表示在s状态下选择a能带来的奖励,\(P_{(s \rightarrow s’)}^a\) 则表示在s状态下,选择a动作,状态从s转移到s’的概率(例如:在宿舍的状态下,选择打游戏,则状态有可能转移到网吧,也有可能还是宿舍)

事实上,由于动作的选择可能影响状态的转移,我们也能从状态价值函数中推出动作的价值函数:

$$ \begin{align} q_Π(a,s) &= \mathbb{E}[G_t|S_t = s, A_t = a] \\ &= R_s^a + λ\sum_{s’∈S}P_{(s \rightarrow s’)}^av(s’) \\ &= R_s^a +λ\sum_{s’∈S}P_{(s \rightarrow s’)}^a\sum_{a’ ∈A}Π(a’|s’)q_Π(a’s’) \end{align}$$

其实也很好理解,就是将之前的状态转移概率和奖励细分为了动作选择概率和动作的奖励

故马尔可夫决策过程可以使用一个五元组表示 \(<S, P, R, A, γ>\)

最优价值函数

综上,我们得到了两个价值函数:状态价值函数 \( v(s) \) 和动作价值函数 \( q_Π(a,s) \)。状态转移过程是基于策略选择 Π 的,策略不同,则两个价值函数就会有变化。我们的目标就是找到一个最优策略,运用该策略得到状态s下的价值函数比其他策略得到的都要大,即:

$$ v(s) = max(v_{Π_*}(s)) $$

$$ q_{Π_{best}}(a,s) = max(q_{Π_*}(a,s)) $$

由于动作价值函数和状态价值函数可以互换,故寻找最优策略时只用动作价值函数即可

根据动作价值函数求得最优动作,即满足策略Π选出来的最优动作应该也能取得最大的q值(动作价值)的一个递归函数:

$$ Π_{best}(a|s) = \begin{cases} 1 & \mathop{\arg\max}\limits_{a∈A}[q_{Π_{best}}(a,s)] \\ 0 & otherwise\end{cases} $$

参考

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

https://www.cnblogs.com/pinard/p/9426283.html

Leave a Comment