RL-Theory

强化学习2:MDP Reinforcement Learning2 Markov Decision Process

概述

本文基于 DeepMind research 领头人David Silver的Intro to RL教学视频和互联网上各大神的笔记统一整理，如有错误请斧正，谢谢！

因GitHub page与自己博客主题渲染引擎问题，部分公式提供Katex和Markdown两种公式代码，以确保根据您的浏览器获得最佳阅读效果。

为了一步步引入MDP，我们将循序渐进地从马尔科夫性质（Markov Process），马尔科夫奖励过程（Markov Reward Process，MRP），再到马尔科夫决策过程（Markov Decision Processes,MDP）。最后再对MDP进行部分扩展，如有限与连续MDPs(Infinite and continuous MDPs)，部分观测MDP（Partially Observable MDPs，POMDP）以及无折扣或平均奖励MDPs(Undiscounted, average reward MDPs)。

1. 马尔科夫性质（Markov Property）

进一步了解马尔科夫决策过程之前，需要先了解马尔科夫性质(Markov Property)，马尔科夫性质即未来的状态只依赖于当前状态，与过去状态无关。
正式的定义如下：

马尔科夫性质（Markov Property）定义：
在时间步 t+1t + 1时，环境的反馈仅取决于上一时间步tt的状态ss，与时间步t−1t-1以及tt步之前的时间步都没有关联性。
P[St+1∣St]=P[St+1∣S1,...,St]P[S_{t+1}|S_t]=P[S_{t+1}|S_1,...,S_t]

马尔科夫性，也就是无后效性。根据定义，当前状态捕捉了历史中所有相关的信息，所以知道了状态，状态是未来的充分统计。某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响，历史(history)就可以完全丢弃。也就是说，未来与过去无关。举个不恰当的例子：A股某些医疗股的变化指数。。。

然而在实际的环境中，智能体所需完成的任务不能够完全满足马尔科夫性质，即在时间步t+1t+1的反馈不一定仅仅依赖于时间步tt的状态和动作。但是为了简化问题的求解过程，仍然假设该任务满足马尔科夫属性（Markov Property），并通过约束环境的状态使得问题满足马尔科夫属性。

2. 马尔科夫过程（Markov Process）

AKA Markov Chain. 是一个无记忆的随机过程，可有用元组表示，其中S为有限数量的状态集，P为状态转移概率矩阵。

  • S为有限的状态空间集，sis_i表示时间步i的状态，其中S={s1,s2,...sn}S=\{s_1,s_2,...s_n\}。
  • pp为状态转移矩阵，S={s1,s2,...sn}Pss′=P[Ss+1=s′∣St=s]S=\{s_1,s_2,...s_n\} P_{ss'}=P[S_{s+1}=s'| S_t=s]

以下是将给定文本中的公式转换为Markdown公式的结果：

  • (S) 为有限的状态空间集，(s_i) 表示时间步 (i) 的状态，其中 (S={s_1, s_2, \ldots, s_n})。
  • (p) 为状态转移矩阵，(S={s1, s_2, \ldots, s_n}) (P{ss’}=P[S_{s+1}=s’| S_t=s])
    状态与状态之间的转换过程即为马尔科夫过程。虽然我们可能不知道P的具体值到底是什么，但是通常我们假设P是存在的（转移概率存在，如果是确定的，无非就是概率为1），而且是稳定的（意思是从状态A到其他状态的转移虽然符合某个分布，但是其转移到某个状态的概率是确定的，不随时间变化的）。

上图中，圆圈表示学生所处的状态，方格Sleep是一个终止状态，终止状态也可以理解成以100%的概率转移到自己，所以一旦进入，就停留在此。箭头表示状态之间的转移，箭头上的数字表示状态转移概率。

例如，当学生处在第一节课（Class1）时，有50%的概率会上第2节课（Class2）；同时也有50%的概率不认真听课，进入到刷facebook这个状态中。在刷facebook这个状态时，比较容易沉迷，有90%的概率在下一时刻继续浏览，有10%的概率返回到第一节课。当学生进入到第二节课（Class2）时，会有80%的概率继续参加第三节课（Class3），有20%的概率觉得课程较难而被迫下课（Sleep）。当学生处于第三节课这个状态时，有60%的概率通过考试，继而100%的结课，也有40%的概率去泡吧。泡吧之后，又分别有20%、40%、40%的概率返回值第一、二、三节课重新继续学习。

假设学生马尔科夫链从状态Class1开始，最终结束于Sleep。其间的过程根据状态转化图可以有很多种可能性，这些都称为采样片段Sample Episodes。以下四个Episodes都是可能的：

1
2
3
4
5
6
7
C1 - C2 - C3 - Pass - Sleep

C1 - FB - FB - C1 - C2 - Sleep

C1 - C2 - C3 - Pub - C2 - C3 - Pass - Sleep

C1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep

2.1 马尔科夫链与Episode

Episode可以翻译为片段、情节、回合等，在强化学习问题中，一个Episode就是一个马尔科夫链，根据状态转移矩阵可以得到许多不同的episode，也就是多个马尔科夫链。

强化学习问题分两种：

3. 状态转移矩阵(State Transition Matrix)

对于马尔科夫状态ss以及后续的状态s′s',状态转移概率可以定义为：Pss′=P[Ss+1=s′∣St=s]P_{ss'} = P[S_{s+1}=s'| S_t=s]状态转移矩阵是马尔科夫过程中状态之间转移的概率所组成的矩阵，因此大小是状态数n的平方。他反映了所有当前状态ss以及后续的状态$s’$的映射，所以他的每行概率之和必定为1。

对于马尔科夫状态 (s) 以及后续的状态 (s’)，状态转移概率可以定义为： (P{ss’} = P[S{s+1}=s’| S_t=s])。状态转移矩阵是马尔科夫过程中状态之间转移的概率所组成的矩阵，因此大小是状态数 (n) 的平方。它反映了所有当前状态 (s) 以及后续的状态 (s’) 的映射，所以它的每行概率之和必定为 1。

[P11aP12a⋯P1naP21aP22a⋯P2na⋮⋮⋱⋮Pn1aPn2a⋯Pnna]\begin{bmatrix} P_{11}^a & P_{12}^a & \cdots & P_{1n}^a \\ P_{21}^a & P_{22}^a & \cdots & P_{2n}^a \\ \vdots & \vdots & \ddots & \vdots \\ P_{n1}^a & P_{n2}^a & \cdots & P_{nn}^a \\ \end{bmatrix}

Markdown版本：
[
\begin{bmatrix}
P{11}^a & P{12}^a & \cdots & P{1n}^a \
P{21}^a & P{22}^a & \cdots & P{2n}^a \
\vdots & \vdots & \ddots & \vdots \
P{n1}^a & P{n2}^a & \cdots & P_{nn}^a \
\end{bmatrix}
]

4.马尔科夫奖励过程(Markov Reward Process)

原本的马尔科夫过程加上奖励值R之后就变成了马尔科夫奖励过程，元素由$$变为$$。其中R就是奖励，$\gamma$ 是折扣因子。

马尔科夫奖励过程(Markov Reward Process)定义：

一个马尔科夫奖励过程(MRP)，由一个四元组构成：$$

  • S为有限的状态空间集，$s_i$表示时间步$i$的状态，其中$S={s_1,s_2,…s_n}$。
  • $P$为状态转移矩阵，$\mathbb P{ss’}=\mathbb P[S{s+1}=s’| S_t=s]$
  • R为奖励函数，$Rs=\mathbb E[R{t+1}|S_t=s]$
  • $\gamma$为折扣因子，$\gamma \in [0,1]$

为了找到长期累积奖励，不仅要考虑当前时间步t的奖励，还需要考虑到未来的奖励。总奖励（Total Reward）$R$的计算公式如下：

根据总奖励R的计算公式可知，长期累积奖励从当前时间步$t$开始，直到最终状态的奖励$r_n$，得到未来累积奖励(Future Cumulative Reward)$R_t$。


一般而言，环境是随机的或者未知的，这意味着下一个状态可能也是随机的。即由于所处的环境是随机的，所以无法确定下一次执行相同的动作，以及是否能够获得相同的奖励。向未来探索得越多，可能产生的分歧(不确定性)就越多。因此，在实际任务中，通常用折扣未来累积奖励（Discounted Future Cumulative Reward）$G_t$来代替未来累积奖励。

如果考虑到无限时间的场景，更加通用的表示为（当前获得的奖励表示为$R_{t+1}$）：

其中$\gamma$为折扣因子（Discount Factor），是介于$[0,1]$的常数。对于距离当前时间步越远的奖励，其重要性就越低。

4.2 回报（Return）与折扣因子$\gamma$

大多数的马尔科夫奖励过程（MRP）与马尔科夫决策过程（MDP）都会使用折扣因子$\gamma$。主要基于如下几点考虑：

4.3. 价值函数(Value Function)

价值函数是状态$s$的长期价值表示。它是上面说的回报的期望。

在概率论和统计学中，数学期望是试验中每次可能的结果的概率乘以结果值得总和。这里回报的期望，即价值函数会会随着折扣因子的变化而取不同的值，因为回报会因为$\gamma$的值而改变，期望自然也就会改变。

上图是$\gamma$为0.9时，例子中的马尔科夫奖励过程，红色的就是状态的价值。


通过价值函数的公式我们可以知道,要想求解一个状态的状态价值， 需要根据马尔科夫链把所有的可能列出来。每个可能都在终点终止，但是上面这个马尔科夫过程其实是有环的， 可能陷入无限循环的局面。

因为折扣因子还是1，所以会导致回报G无限大，期望也就无限大，状态价值V也就无限大。下一章节引入贝尔曼方程就是为了更好的求解价值函数的。

以下是python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//initialization
V_fb = 0;
V_pub =0;
V_c1 = 0;
V_c2 = 0;
V_c3 = 0;
V_pass = 0;
V_slp = 0;
gamma =0.9;

//Iteratively computing Value function
for n in  range(1,30):
    V_fb_next  = 0.9*(-1+gamma*V_fb) + 0.1*(-1+gamma*V_c1)
    V_pub_next = 0.2*(1+gamma*V_c1) + 0.4*(1+gamma*V_c2)+0.4*(1+gamma*V_c3)
    V_c1_next  = 0.5*(-2+gamma*V_c2) + 0.5*(-2+gamma*V_fb)
    V_c2_next  = 0.2*(-2+gamma*V_slp) + 0.8*(-2+gamma*V_c3)
    V_c3_next  = 0.6*(-2+gamma*V_pass) + 0.4*(-2+gamma*V_pub)
    v_pass_next = 1*(10 + 0.9*V_slp)

    V_fb = V_fb_next;
    V_pub = V_pub_next;
    V_c1 = V_c1_next;
    V_c2 = V_c2_next;
    V_c3 = V_c3_next;
    v_pass =v_pass_next

print("fb = ",V_fb);
print("pub=",V_pub);
print("V_c1 =",V_c1)
print("V_c2 =",V_c2)
print("V_c3 =",V_c3)

About this Post

This post is written by Rui Xu, licensed under CC BY-NC 4.0.

#AI#Reinforcement Learning