强化学习笔记（2）-- 马尔科夫决策过程

1.马尔科夫过程

Markov decision processes formally describe an environment for reinforcement learning, where the environment is fully ovservable.

大部分的RL问题都能用MDPs来描述

最优控制问题可以描述成连续MDPs
部分观测环境可以转化成POMDPs
赌博机问题是只有一个状态的MDPs

1.1 马尔科夫性质（Markov Property）

"The future is independent of the past given the present".

下个状态只与当前状态有关，跟更前面的状态无关。
定义：

如果在t时刻的状态 $S_t$ 满足如下灯饰，那么这个状态被称为马尔科夫状态，或者说该状态满足马尔科夫性
A state $S_t$ is Markov if and only if
$\mathbb{P}[S_{t+1} | S_t] = \mathbb{P}[S_{t+1} | S_1,...,S_t]$

状态 $S_t$ 包含了所有历史相关信息，所以无需再去了解之前的 $S_1,...,S_{t-1}$
数学上可以认为，当前状态是将来的充分统计量
所以，这里要求环境全观测
举例：
下棋时，只用关心当前局面（直接解残局，不需要）
打俄罗斯方块时，只用关心当前屏幕

有了马尔科夫状态之后，我们可以

定义状态转移矩阵
忽略时间的影响
PS：马尔科夫性和状态的定义息息相关

1.2状态转移矩阵(State Transition Matrix)

状态转移概率只从一个马尔科夫状态s跳转到后继状态s'的概率
For a Markov state s and successor states', the state transition probability is defined by
$\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

所有的状态组成行，所有的后继状态(successor)组成列，我们就可以得到状态转移矩阵
$\left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right]$

n表示状态的个数
每行元素相加等于1

当然如果状态太多，或者是无穷大（连续状态）时，更适合用状态转移函数，
$P(s'|s) = \mathbb{P}[S_{t+1} = s' | S_t = s]$

此时， $\int_{s'}P(s'|s) = 1$ 或 $\sum_{s'}P(s'|s) = 1$

重要的事情说三遍：
转移矩阵在MDP中被认为是环境的一部分！！！
转移矩阵在MDP中被认为是环境的一部分！！！
转移矩阵在MDP中被认为是环境的一部分！！！

1.3 马尔科夫过程

A Markov Process(or Markov Chain) is a memoryless random process, i.e. a sequence of random state $S_1$ , $S_2$ ,... with the Markov property
马尔科夫过程可以由一个二元组来定义 $<S, P>$
$S$ 代表了状态的集合
$P$ 描述了状态转移矩阵

$P_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

我们有时候并一定知道 $P$ 的具体值，但是通常我们假设 $P$ 存在且稳定(即，从 $s$ 转移到 $s'$ 的概率任何时候都是一样的)

PS：当 $P$ 不稳定时，不稳定环境，在线学习，快速学习

Student Markov Chain Transition Matrix

椭圆：普通状态
有向线：从这个状态跳转到另一个状态的概率
方块：表示终止状态

1.4 片段(episode)

定义

episode = one a sequence of states, actions and rewards, which ends with terminal state
强化学习中，从初始状态 $S_1$ 到最终状态的序列过程，被称为一个片段(episode)
$S_1,S_2,..,S_T$

如果一个任务总以终止状态结束，那么这个任务被称为片段任务(episodic task).
如果一个任务没有终止状态，会被无线执行下去，则被称为连续性任务(continuing task).

episodes example

2.马尔科夫奖励过程(Markov reward process)

A Markov reward process is a Markov chain with values.
马尔可夫过程主要描述的是状态之间的转移关系，在这个转移关系上赋予不同的奖励值即得到了马尔可夫奖励过程。

马尔科夫奖励过程有一个四元组组成 $<\mathcal{S},\mathcal{P},\mathcal{R},\gamma>$
$\mathcal{S}$ 代表了状态的集合
$\mathcal{P}$ 描述了状态转移矩阵
$\mathcal{R}$ 表示奖励函数， $R(s)$ 描述了在状态 $s$ 的奖励.
$\mathcal{R}(s) = \mathbb{E}[R_{t+1} | S_t = s]$
$\gamma \in [0,1]，表示衰减因子$

敲黑板！！
注意区别 $\mathcal{R}\text{和}R\text{的区别}$ ：
$R$ :在t+1时刻，所获得的随机变量的值
$\mathcal{R}$ :一个函数

Student MRP

2.1 回报值

奖励值：对每一个状态的评价
回报值：对每一个片段的评价

定义
回报值(return $G_t$ )是从时间 $t$ 处开始的累计衰减奖励
对于片段任务：
$G_t = R_{t+1} + \gamma*R_{t+2} + ... + \gamma^{T-t-1}*R_{T} = \sum^{T-t-1}_{k=0} \gamma^k*R_{t+k+1}$
对于连续性任务:
$G_t = R_{t+1} + \gamma*R_{t+2} + ... = \sum^{\infty}_{k=0} \gamma^k*R_{t+k+1}$

2.2 再聊片段

可以这么理解，终止状态等价于自身转移概率为1，奖励为0的一个状态。
因此，我们可以能够将片段性任务和连续性任务进行统一表达

G_t = \sum^{T-t-1}_{k=0} \gamma^k*R_{t+k+1}

当

T = \infty

时，表示连续性任务，否则为片段性任务

2.3 再聊衰减值

为什么我们要使用这样的指数衰减值？

直观感受
1. 影响未来的因素不仅仅包含当前
2. 我们对未来的把我也是逐渐衰减的
3. 一般情况下，我们更关注短时间的反馈
数学便利
1. 一个参数就描述了整个衰减过程，只需要调节这一个参数 γ 即可以调节长时奖励和短时奖励的权衡 (trade-off)
2. 指数衰减形式又很容易进行数学分析
3. 指数衰减是对回报值的有界保证，避免了循环 MRP 和连续性 MRP 情况下回报值变成无穷

2.4 回报值vs值函数

回报值: the discounted sum of rewards in one whole episode（一次片段的结果，每次都不同，存在很大的样本偏差）
值函数: the expected discounted sum of rewards from a certain state/ an expectation over all possible episodes and can start from any state(关注的是状态s)

The state value function $v(s)$ of an MRP is the expected return starting from state $s$
$v(s) = \mathbb{E}[G_t | S_t = s]$

回报值的计算过程很简单

2.4.1MRP中的贝尔曼方程（Bellman Equation）

值函数的表达式可以分解成两部分：

瞬时奖励(immediate reward) $R_{t+1}$
后继状态 $S_{t+1}$ 的值函数乘上一个衰减系数
下面是推导过程：
$\begin{equation} \begin{aligned} v(s) &= \mathbb{E}[G_t|S_t = s]\\ &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... |S_t = s]\\&= \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + ... )|S_t = s] \\&=\mathbb{E}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\&\text{求和的期望等价于求期望的和}\\&R_{t+1} \text{的期望仍是} R_{t+1} \\&G_{t+1}\text{的期望就是}v(S_{t+1})\\&= \mathbb{E}[R_{t+1} + \gamma v(S_{t+1})|S_t = s] \end{aligned} \end{equation}$
体现了 $v(s)$ 与 $v(S_{t+1})$ 之间的迭代关系

2.4.2 解贝尔曼方程

矩阵-向量形式表达贝尔曼方程
$v = \mathcal{R} + \gamma \mathcal{P}v$
假设状态集合为 $\mathcal{S} = {s_1,s_2,...,s_n}$ ，那么
$\left[\begin{matrix} v(s_1) \\ \vdots \\ v(s_n)\end{matrix}\right] = \left[\begin{matrix} \mathcal{R}(s_1) \\ \vdots \\ \mathcal{R}(s_n)\end{matrix}\right] + \gamma\left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right] \left[\begin{matrix} v(s_1) \\ \vdots \\ v(s_n)\end{matrix}\right]$

贝尔曼方程本质上是一个线性方程，可以直接解
$\begin{equation} \begin{aligned} v &= \mathcal{R} + \gamma \mathcal{P}v \\ (I - \gamma \mathcal{P})v &= \mathcal{R} \\v &=(I - \gamma \mathcal{P})^{-1} \mathcal{R} \end{aligned} \end{equation}$

Computational complexity is $O(n^3)$ for n states.
State Transition Matrix $\mathcal{P}$ is required.
Direct solution only possible for small MRPs.
There are many iterative methods for large MRPs, e.g:
1. Dynamic programming
2. Monte-Carlo evaluation
3. Temporal-Difference learning

3.马尔科夫决策过程

我们把动作(Action)引入到MRPs中，就得到了马尔可夫决策过程（Markov Decision Processes, MDPs）

一个马尔科夫决策过程(MDPs)由一个五元组构成 $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$
$\mathcal{S}$ 代表了状态的集合
$\mathcal{A}$ 代表了动作的集合
$\mathcal{P}$ 描述了状态转移矩阵 $\mathcal{P}^a_{ss'} = \mathbb{P}[\mathcal{S}_{t+1} = s' | S_t = s, A_t = a]$
$\mathcal{R}$ 表示奖励函数， $\mathcal{R}(s,a)$ 描述了在状态s做动作a的奖励 $\mathcal{R}(s,a) = \mathbb{E}[\mathcal{R}_{t+1} | \mathcal{S}_t = s, \mathcal{A}_t = a]$
$\gamma \in [0,1]，表示衰减因子$

3.1 策略(Policy)

A policy $\pi$ is a distribution over actions given states. 在MDPs中，一个策略 $\pi$ 是在给定状态下得动作的概率分布
$\pi(a|s) = \mathbb{P}[A_t = a | S_t = s]$

策略是对智能体行为的全部描述(智能体能够控制的是策略)
MDPs中的策略是基于马尔科夫状态的（而不是基于历史）
策略是时间稳定的，只与s有关，与时间t无关
策略的概率分布输出都是独热的(one-hot)，那么成为确定性策略，否则即为随机策略

3.2 MDPs和MRPs之间的关系

对于一个MDP问题 $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$ ，如果给定了策略 $\pi$ , MDP将会退化成MRP $<\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma>$
此时，
$\mathcal{P}^{\pi} = \sum_{a \in \mathcal{A}} \pi(a|s)\mathcal{P}^a_{ss'}$
$\mathcal{R}^{\pi}_s = \sum_{a \in \mathcal{A}} \pi(a|s)\mathcal{R}^a_{s}$

3.3 值函数

在MDPs问题中，由于动作的引入，值函数分为了两种：

状态值函数（V函数）
状态动作值函数（Q函数）

V函数
MDPs中的状态值函数是从状态s开始，使用策略 $\pi$ 得到的期望回报值
$v_{\pi}(s)=\mathbb{E}_{\pi}[G_t | S_t = s]$

Q函数
MDPs中的状态动作值函数是从状态s开始，执行动作a，然后使用策略 $\pi$ 得到的期望回报值
$q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$

Q函数中，之所以强调“然后”的意思是，在状态s下，智能体的动作a是随机选择的（不一定按策略来），之后的动作才是按策略来做选择。

MDPs中，任何不说明策略 $\pi$ 的情况下，讨论值函数都是在耍流氓！

3.4 贝尔曼方程

和MRP相似，MDPs中的值函数也能分解成瞬时奖励和后继状态的值函数两部分
状态值函数
$v_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]$
状态动作值函数
$q_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$

其中空心节点代表了state，实心点代表了state-action pair，从根节点

s

出发，它在policy

\pi

以一定概率选择图中action

a

，然后environment会做出反馈以概率

p

达到下一个state

s'

以及对应的reward，再对每一种可能求和，就得到了Bellman equation。

3.4.1 V函数与Q函数之间的相互转化

Q转V

这个本质上是全概率

V转Q

贝尔曼期望方程-V函数

贝尔曼期望方程-Q函数

贝尔曼方程矩阵形式
MDPs 下的贝尔曼期望方程和 MRP 的形式相同

v_{\pi} = \mathcal{R}^{\pi} + \gamma \mathcal{P}^{\pi}v_{\pi}

同样地，可以直接求解

v_{\pi} = (I -\gamma \mathcal{P}^{\pi})^{-1} \mathcal{R}^{\pi}

求解要求:

已知策略 $\pi(a|s)$
已知状态转移矩阵 $\mathcal{P}^{a}_{ss'}$

3.5 最优值函数

之前值函数，以及贝尔曼期望方程针对的都是给定策略 $\pi$ 的情况，是一个评价问题。
现在我们来考虑强化学习中的优化问题（找出最好的策略）

最优质函数值得是在所有策略中的值函数最大值，其中包括最优V函数和最优Q函数
$v_{*}(s) = \max_{\pi} v_{\pi}(s)$
$q_{*}(s,a) = \max_{\pi} q_{\pi}(s,a)$

最优值函数值的是一个MDP中所能达到的最佳性能

3.6 最优策略

为了比较不同策略的好坏，我们首先应该定义策略的比较关系

$\pi \geq \pi' if v_{\pi}(s) \geq v_{\pi'}(s), \forall{s}$

对于任何MDPs问题

总存在一个策略 $\pi_∗$ 要好于或等于其他所有的策略 $\pi_∗ \geq \pi, \forall\pi$
所有的最优策略都能够实现最优的 V 函数 $v_{\pi_∗} = v_*(s)$
所有的最优策略都能够实现最优的 Q 函数 $q_{\pi_∗} = q_*(s,a)$

怎么得到最优策略？

已知 $q_*$
当我们已知了最优 Q 函数后，我们能够马上求出最优策略，只要根据 $q_∗(s, a)$ 选择相应的动作即可

$\pi_*(a|s) = \begin{equation} \begin{aligned} \left\{ \begin{array}{**lr**} 1, if \ a = \arg\max_{a \in \mathcal{A}}q_*(s,a) \\ 0, otherwise \end{array} \right. \end{aligned} \end{equation}$

可以看出对于任何MDPs问题，总存在一个确定性的最优策略。

已知 $v_*$
为了求解最优策略，只需要做一步搜索就行。也就是在 $s$ 对于不同的 $a \in \mathcal{A}(s)$ ，计算 $\sum_{s',r}p(s',r|s,a)[r + \gamma v_*(s')]$ ，获得最大值对应的a就是我们的最优策略

同样地， $v_*(s)$ 和 $q_*(s,q)$ 也存在递归的关系，也可以相互转换

最优v函数转最优q函数

最优q函数转最优v函数

同样根据上面的两个图，我们可以推导出：

贝尔曼最优方程——V函数

贝尔曼最优方程——Q函数

贝尔曼最优方程本质上就是利用了 $\pi_{*}$ 的特点，将其期望的算子转化成了max
在贝尔曼期望方程中， $\pi$ 是已知的，而在贝尔曼最有方程， $\pi_{*}$ 是未知的
解贝尔曼期望方程的过程即对应了评价，解贝尔曼最优方程的过程即对应了优化

贝尔曼最优方程是非线性的，一般很难有闭式的解(closed-form solution)，可以使用迭代优化的方法去解：

Value Iteration
Policy Iteration
Q-learning
Sarsa
...

4.MDPs的拓展

4.1 无穷或连续 MDPs

动作空间或状态空间无限可数
动作空间或状态空无限不可数（连续）
时间连续

4.2 部分可观测 MDPs（Partially observable MDPs, POMDPs)

此时观测不等于状态 $O_t \neq S_t$
POMDPs由七元组 $<\mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{P}, \mathcal{R}, \mathcal{Z}, \gamma>$
\mathcal{Z} 是观测函数
$\mathcal{Z}^{a}_{s'o} = \mathbb{P} [O_{t+1} = o | S_{t+1} = s', A_{t} = a]$
观测不满足马尔可夫性，因此也不满足贝尔曼方程
状态未知，隐马尔科夫过程
又是对于POMDPs，最优的策略是随机性

4.3 无衰减 MDPs

用于各态经历（平稳随机过程的一种特性）马尔科夫决策过程
存在独立于状态的平均奖上 $p*{\pi}$
求值函数时，需要减去该平均奖赏，否则有可能奖赏爆炸

Reference

最后编辑于：2019.02.19 12:33:26

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,552评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,666评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,519评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,180评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,205评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,344评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,781评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,449评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,635评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,467评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,515评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,217评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,775评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,851评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,084评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,637评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,204评论 2赞 341

强化学习笔记（2）-- 马尔科夫决策过程

强化学习笔记（2）-- 马尔科夫决策过程

目录：

1.马尔科夫过程

1.1 马尔科夫性质（Markov Property）

1.2状态转移矩阵(State Transition Matrix)

1.3 马尔科夫过程

1.4 片段(episode)

2.马尔科夫奖励过程(Markov reward process)

2.1 回报值

2.2 再聊片段

2.3 再聊衰减值

2.4 回报值vs值函数

2.4.1MRP中的贝尔曼方程（Bellman Equation）

2.4.2 解贝尔曼方程

3.马尔科夫决策过程

3.1 策略(Policy)

3.2 MDPs和MRPs之间的关系

3.3 值函数

3.4 贝尔曼方程

3.4.1 V函数与Q函数之间的相互转化

3.5 最优值函数

3.6 最优策略

4.MDPs的拓展

4.1 无穷或连续 MDPs

4.2 部分可观测 MDPs（Partially observable MDPs, POMDPs)

4.3 无衰减 MDPs

Reference

推荐阅读更多精彩内容