马尔科夫决策过程解法(Solution to MDP)

1. 马尔科夫决策过程

马尔科夫决策过程(Markov Decision Process) 是一个由4个元素组成的元祖 $(S, A, P, R)$ 组成。

$S$ 为状态; $A$ 为动作; $P$ 为概率转移，指定 $Pr{(x^\prime|x, a)}$ ; R为奖励函数，指定 $R(s)$ ；也可以指定为 $R(s,a)$ 。

马尔科夫决策过程

很容易定义状态函数 $V^\pi(s)$ 为折扣奖励的累计期望，折扣比例 $0 \leq\gamma < 1$ 。
$V^\pi(s)= E[\sum_{t=0}^{\infty} \gamma^t R(s_t) | s_0=s, a_t=\pi(s_t)]$

从后向传播的观点——当前的价值函数为及时奖励和未来奖励的期望之和，有：
$V^\pi(s)= R(s) + \gamma\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime)$

写成矩阵的形式，求解 $V(s)$ 即为求解线性方程组：
$\begin{align*} V^\pi(s) &= R(s) + \gamma \Pr(s^\prime|s, a)V^\pi(s^\prime) \\ (I_{|S|} - \gamma \Pr(s^\prime|s,a)) V^{\pi}(s) &= R(s) \end{align*}$

最优的价值函数 $V^\star(s) = \max_\pi V^\pi(s)$ ，满足：
$V^\star(s)= R(s) + \gamma\max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\star(s^\prime)$

2. 价值迭代算法

价值迭代的算法如下：

初始化 $\hat{V}(s)=0$

不断迭代更新
$\hat{V}(s)\leftarrow R(s)+\gamma \max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime) \quad \forall s\in S$

理解价值迭代，需要理解 $Bellman$ 最优算子是个压缩映射。定义 $Bellman$ 最优算子 $B: \mathbb{R}^{S} \rightarrow \mathbb{R}^{S}$ 如下，
$B\, \hat{V}(s) = R(s) + \gamma \max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime)$

由于 $B$ 是压缩映射，存在唯一的不动点 $V^\star(s)$ 。这就是上述价值迭代算法的收敛原理，对 $V(s)$ 进行多次迭代后，会收敛到最优价值函数 $V^\star(s)$ 。

压缩映射具有如下性质: 对任意 $V_1(s)$ 和 $V_2(s)$ ，有
$\max_{s \in S}{| B\, V_1(s) - B\, V_2(s)| \leq \gamma \max_{s \in S}|V_1(s)-V_2(s)|}$

上述性质说明了这样一个事情: 对于 $V^k(s)$ 进行迭代后，更新后的 $V^{k+1}(s) = B\,V^{k}(s)$ 与原来的 $V^k(s)$ ，最大误差不超过 $\gamma \max_{s \in S}|V_1(s)-V_2(s)| < \max_{s \in S}|V_1(s)-V_2(s)|$ （因为 $\gamma < 1$ ）。也就是每次迭代后，误差以比例 $\gamma$ 减小。

利用上面压缩性质，可以证明价值迭代算法的收敛性。(下面方框中的内容，可以暂时跳过)

首先，假设马尔科夫决策过程中的奖励 $R$ 是有界的，即 $R\leq R_{max}$ 。根据等比数列性质，那么 $V(s)$ 也是有上界的。
$V(s)= \sum_{t=0}^{\infty} \gamma^t R(s_t) \leq \sum_{t=0}^{\infty} \gamma^t R_{max} = \frac{R_{max}}{1-\gamma}$
那么，任意一次迭代过程中的值 $V^k(s)$ 与 $V^{\star}(s)$ 之间的差最大为 $\frac{R_{max}}{1-\gamma}$ 。利用压缩性质有，
$\max_{s \in S}|V^0(s) - V^{\star}(s) | \leq \gamma \frac{R_{max}}{1-\gamma}$
对初值 $V^0(s)$ 进行一次迭代后，
$\begin{align*} \max_{s \in S}|V^1(s) - V^\star(s)| &\leq \max_{s \in S}|B\, V^0(s) - V^\star(s)| \\ &\leq \gamma \max_{s \in S} | V^0(s) - V^{\star}(s)| (压缩性质) \\ &\leq \gamma^2 \frac{R_{max}}{1-\gamma} (最大误差) \end{align*}$
可以看到，每次迭代后，最大误差以比例 $\gamma < 1$ 减小。

3. 策略迭代算法

策略迭代算法如下：

初始化 $\hat{V}(s)=0$ .

策略评估：(一般而言，下式中 $\pi(s,a)$ 为固定策略由于策略更新)
$V^{(k+1)}(s) \leftarrow \sum_{a \in A} \pi(s, a) \sum_{s^\prime \in S}\Pr(s^\prime | s, a)(r(s,a) + V^{k}(s^\prime)) \quad \forall s \in S$

策略更新：
$\pi(s) \leftarrow \arg \max_{a} (R(s) + \gamma \sum_{s^\prime \in S} \Pr(s^\prime|s, a) V^\pi(s)) \quad \forall s \in S$

如果 $\pi(s)$ 与上次迭代相比没有变化，则停止；否则，转回2。

更多关于策略迭代的分析，请看这里。

4. 线性规划算法

线性规划算法如下：

$\begin{align*} minimize \quad &\sum_s V(s) \\ subject \,\,\, to \quad & V(s) \ge R(s) + \gamma \sum_{s^\prime \in S} \Pr(s^\prime | s, a) V(s^\prime) \quad \quad \forall s \in S, a \in A \end{align*}$

理解如下，假设不等式约束以等式成立，那么满足 $Bellman$ 最优算子；如果存在某个 $V(s)$ 使得不等式约束存在严格大于，优化目标一定会使得这个 $V(s)$ 继续减小，直至不等式约束以等式存在。所以最终的目标，使得 $V(s)$ 满足 $Bellman$ 方程最优解。

5. 附录

$Bellman$ 最优算子收缩性质证明

$\begin{align*} |B V_1(s) - B V_2(s)| &= |R(s) + \gamma\max_a\sum_{s^\prime}\Pr(s'|s,a) V_1(s^\prime)- R(s) - \gamma\max_a \sum_{s^\prime}\Pr({s^\prime}|s, a)V_2(s^\prime) | \\ &= \gamma|\max_a\sum_{s^\prime}[\Pr(s^\prime|s,a)(V_1(s^\prime) - V_2(s^\prime))]| \\ &\leq \gamma \max_s| V_1(s) - V_2(s)| \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \forall s \in S \end{align*}$
Thus,
$\max_s|BV_1(s) - BV_2(s)| \leq \gamma \max_s| V_1(s) - V_2(s)|$

最后编辑于：2018.09.21 16:54:30

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