今天来学习一下马可夫决策过程，以下简称MDP。
_不确定世界的决策方法/1.png)
现在考虑一个问题，如上图所示，机器人前面有一堆火，而它需要去取火那边的钻石，它如何才能取到那颗钻石。
下面是一张俯视图：
_不确定世界的决策方法/2.png)
游戏规则：
行动: 画叉的那一格是墙，不能进入的方格，所以在这张图中，机器人可以移动的方格总共是十一个。如果机器人采取向一个方格移动，80%的概率会成功，10%向左边的方向，10%会向右边的方向的方格移动。
奖惩: 如果机器人进入+1的方格，机器人加1分，游戏结束。若机器人进入-1的方格，机器人减1分，游戏结束。机器人每采取一个行动会获得小的奖惩，比如加0.1分或者减0.1分。
目标：得最多的分。
可以看出，MDP要解决的不是一个确定的世界的问题，是一个不一定的世界的问题。机器人虽然计划采取某个行动，但它不一定能完成计划，它想往北走，却有可能是向西或者向东走了一步。比如一个人想要到达一个目的地，选择开车，结果堵车了，选择坐地铁，地铁故障了，选择走路，结果摔了一跤骨折折到了医院，选择坐公交，结果一见钟情，坐过了站。
确定的世界，根据现在的状态来采取行动，就一定能到达想要达到的状态，
_不确定世界的决策方法/3.png)
不确定的世界，虽然根据现在的状态采取了行动，但是不一定能到达想要到达的地方，现实世界就是一个不确定的世界。
_不确定世界的决策方法/4.png)
MDP算法可以应用在指导机器人行动决策，工厂生产决策，农业生产决策等等不确定世界的问题上。
这篇文章主要分为三个部分：
1. Markov Decision Process 马可夫决策过程
2. Policy Evaluation 策略评估
3. Value Iteration 【找最佳策略】
1. Markov Decision Process 马可夫决策过程
定义一个MDP：
_不确定世界的决策方法/5.png)
以机器人拿钻石为例，S [States] 是状态集，包含机器人所有可能的状态，以第二张图为例，有十二个格子，除了墙之外的其他十一个格子机器人都可以进去，所以机器人在游戏中总共可以有11种状态，而机器人最初在的那一格为初始状态，用下标start注明，初始状态是一定会有的状态。A(s)[Actions(s)]是机器人在状态为s的时候所有可以做的行动的集合，这个例子中，机器人可以有向东，西，南，北移动这四个动作。T(s, a, s’)表示机器人在状态s的时候做了行为a，最后变为状态s’的概率，如果状态列举得完整，那么应该有：
_不确定世界的决策方法/6.png)
_不确定世界的决策方法/7.png)
R(s, a, s’) [Reward(s, a, s’)]表示机器人在状态s采取行动a，进入状态s’后会获得的奖励或惩罚。IsEnd(s)判断游戏是否结束。
由T(s, a, s’)和R(s, a, s’)可以看出，MDP的理念是，未来和过去是无关的，未来的可能只取决于现在的状态和即将采取的行动，和过去的状态和行动是无关的。如果要解决的问题不止依赖于现在的状态和行为，也依赖于过去的状态和行为，那可以重新定义更大的状态集(S)来使问题符合MDP的要求。
MDP得到的行动方案称之为策略π，比如机器人在状态s的时候下一步要采取的行动。
_不确定世界的决策方法/8.png)
最佳的策略为π*，是MDP要求得的结果。
到这里，MDP的定义就结束了。
2. Policy Evaluation 策略评估
假设MDP给出了一个策略(policy)，怎么评估它的好坏?
这里用效能(utility)来表示遵循策略衍生出来的路径产生的奖惩(reward)，比如给机器人下了一个向东的指令，它最后不一定成功向东，也可能向南或北移动了，向东之后如果游戏没有结束，它可能接着往南走，在结束游戏之前它会有很多种走法，每种走法全程产生的分数称之为效能(utility)：
_不确定世界的决策方法/9.png)
策略的价值(value)则是这个策略的效能的期望值，价值(value)最大的策略即最佳策略π*：
_不确定世界的决策方法/10.png)
下面看几个不同情况下的最佳策略：
<div align=center>_不确定世界的决策方法/11.png)
</div>
<div align=center>_不确定世界的决策方法/12.png)
</div>
<div align=center>_不确定世界的决策方法/13.png)
</div>
<div align=center>_不确定世界的决策方法/14.png)
</div>
图中R(s)表示的是机器人每做一个动作的得分，这样设置一个负分是为了促使机器人尽快完成游戏，R(s)值越小，则机器人越需要尽早结束游戏，免得拉低总分。图中每个箭头表示在当前格子中的最佳策略。当R(s)=-0.01的时候，如果机器人在第二排第三格，最佳策略是向西，所以会出现三种结果，80%原地不动，10%向北移一格，10%向南移一格。而当R(s)=-0.03的时候，同样的状态，最佳策略变成了向北，因为R(s)的减低，游戏对拖延的容忍值降低了，因此最佳策略产生了变化，机器人需要冒更多的风险去尽早结束游戏。当R(s)=-2.0时，则最佳策略是尽早结束游戏，同样的状态直接向东往-1格去。
此外还有一个概念是discount factor γ，即随着时间的推移，你的得分（收获，奖赏）会被打折扣。拖得越久折扣越大。
_不确定世界的决策方法/15.png)
这里我们引入一个新的游戏，这是一个掷骰子的游戏：
游戏规则:
1. **状态：**游戏有两种状态，in (在游戏中)和 end（退出游戏）
2. **动作**：有两个动作可以选，quit(退出游戏)和stay(留在游戏)
3. **奖惩**：选择quit时，退出游戏，获得$10奖励；选择stay，则会掷一个六面骰子，如果骰子是1，2向上，则奖励$4，并退出游戏，如果骰子是3，4，5，6朝上，则奖励$4，并继续留在游戏里。
通过游戏规则可以绘制如下状态图，蓝色圆框是状态，线路表示策略所产生的方向，线路上会注明策略和报酬，以及产生这条线路的概率。这里引入了一个中间状态，即红色虚线圆框，它表示在执行策略后，一个判断当前状态的动作。值得留意的是这个游戏只有一个动作会引发不确定的结果，即stay，quit的结果是确定的。
_不确定世界的决策方法/16.png)
以掷骰子的游戏为例，当discount factor γ 为1的时候，表示收到回报的时间不重要，回报不会因为收到时间上的延后而贬值。当 γ 为0的时候，表示只有当下收到的回报才是重要的，未来是不需要考虑的。而通常γ 的值会介于0-1之间，收到回报的时间是重要的，时间也是一个很重的成本，越早取得成功越好，但也不会只考虑当下的收益。当γ大于1呢？
_不确定世界的决策方法/17.png)
同样，以机器人取钻石的游戏为例，当 γ在0-1之间，越晚拿到钻石，回报也会越低。
下面这个游戏可以解一下，答案已经标在了上面：
_不确定世界的决策方法/18.png)
在状态s执行策略π的价值如下定义：
_不确定世界的决策方法/19.png)
在中间状态s执行动作a的价值如下定义：
_不确定世界的决策方法/20.png)
这两个定义的区别在哪里？即一个是当前状态的价值，另一个则是中间状态的价值，如果当前状态是end，则价值是0，当前状态是in的时候，有中间状态的价值：
_不确定世界的决策方法/21.png)
_不确定世界的决策方法/22.png)
以掷骰子游戏为例，策略为stay的价值如下：
_不确定世界的决策方法/23.png)
根据公式推导，则可以得出在状态in的时候，使用stay策略，价值是12。推导过程见下图：
_不确定世界的决策方法/24.png)
会不会有一个游戏可以永远玩下去，获得无穷无尽的收益呢？
避免这种情况产生的方法有两个：
1. 设置游戏的最长时间或者步数。或者随步数和时间的增加，可以执行的策略也随着产生变化。把人生比作一场游戏，那么很明显无论你采取如何正确的策略过每分每秒，这个游戏也必然有停止的时候，而随着年纪增大，能做的策略选择也越来越少，有天你会老得跑不动，只能拄着拐杖慢慢踱，有天你老得掉光了牙，很多东西也吃不了了，希望看到这里的人都有这么一天，O(∩_∩)O。 2. 另一个就是前面提到的discount factor γ ，根据下面的定理，只要 γ小于1，则收益必然收敛。最后的收益必然小于等于游戏中单步最大收益/(1-γ)。
_不确定世界的决策方法/25.png)
3. Absorbing state: 将游戏设计得无论游戏者设计什么样的游戏策略，最终都有可能到达游戏结束那个状态。
如何计算策略价值，虽然收益通过一些方法限制，最后也会收敛，但是游戏都是有可能无限长时间玩下去的，所以可以通过限制最长步长或者游戏时间的方式来计算策略价值。
_不确定世界的决策方法/26.png)
如上图所示，当最长步长为0的时候所有状态下的策略价值都是0，因为游戏根本就不会开始，当最长步长为1时，则会产生收益，当步长为t时，策略价值则可以基于s’状态下t-1为步长的策略价值来得到，以为已经走了一步，还剩下t-1步。
将最长步长设定为多少是比较合适的呢？那就是，当策略价值随着最长步长的增加几乎不再增加的时候。
_不确定世界的决策方法/27.png)
这样做的算法复杂度为：
_不确定世界的决策方法/28.png)
以掷骰子游戏为例，如果最长步数是1，策略价值为4，如果最长步数是100，策略价值则会很接近最大可能的收益：
_不确定世界的决策方法/29.png)
_不确定世界的决策方法/30.png)
3. Value Iteration
如何找到最佳策略，首先定义最大策略价值：
_不确定世界的决策方法/31.png)
中间最大行动价值定义：
_不确定世界的决策方法/32.png)
使得中间行动价值最大的动作则是最佳策略：
_不确定世界的决策方法/33.png)
以机器人拿钻石的游戏为例，首先会计算每个状态下每个策略的期望收益：
_不确定世界的决策方法/34.png)
再由此得到最佳策略：
_不确定世界的决策方法/35.png)
最佳策略获得的期望收益是：
_不确定世界的决策方法/36.png)
时间复杂度为：
_不确定世界的决策方法/37.png)
参考：
[1] Lecture 8: Markov Decision Processes (MDPs), CS188 Artificial Intelligence UC Berkeley, Spring 2013 Instructor: Prof. Pieter Abbeel
[2] Lecture 9: Markov Decision Processes II, CS188 Artificial Intelligence UC Berkeley, Spring 2013 Instructor: Prof. Pieter Abbeel
[3] Lecture 7: Markov Decision Processes - Value Iteration | Stanford CS221: AI (Autumn 2019), Percy Liang, Associate Professor & Dorsa Sadigh, Assistant Professor
Comments