人工智能 (8) Markov Decision Process
微信公众号：机器树
MDP简介
来一起学习Markov Decision Process (MDP) 之前，回顾一下之前提到的搜索问题，包含五个重点要素：
初始状态，终止状态，下一个状态，到达下一个状态采取的动作，和相应的代价。
MDP是这样一个过程：每一步采取的动作都是不确定的，并且每一个动作的代价取决于这个动作的起始和结束状态。
通常来讲MDP包含：
一系列状态，
初始状态，
一系列动作的概率（Transition Probabilities），T(s,a,s’), 采用动作a从状态s到达状态s’的概率。
Reward function（姑且理解为：报酬函数），reward（s, a, s’）, 采用动作a从状态s到达状态s’的reward。
目标（终止）条件，
Discount factor (折现因子)，γ 介于0和1之间，包含0和1.
通过一个例子来看一下实际中的MDP的情况：
现在要从第0层上到第20层，有两种选择：
每次上一层楼 (walk)
每次扔一个色子，看数字的大小k，然后有0.5的概率向上爬k层，0.5的概率下一层。(dice)
如果用MDP来模拟这一过程的话：
层数的状态用数字表示是0-20，初始和终止状态分别是0和20，动作无非是上面提到的两种方式：向上走和扔色子，也即a 属于 {walk, dice}。那么每一个动作的概率是：
T(s, walk, s’) = 1, s’ = s+1 (层数加1)
T(s, walk, s’) = 0, 其他情况不存在
T(s, dice, s’) = 0.5, s’ = s-1 (层数加1)
T(s, dice, s’) = 0.5*1/6, s’ = s+i for i = 1,..6,
T(s, dice, s’) = 0, otherwise.
Reward 的设置可以根据不同的情况来决定，比如reward（s,a,s’）= 1/|20-s’| ，s’ 不等于20，reward(s,a,20) = 2.
Discount factor 等于1.
此外：如果T(s, a, s’) > 0, 那么s‘ 就是s的可能的下一个状态。并且所有的transition probabilities 加起来为1.
那么对于一个MDP问题，解决方案到底是什么样子的？
因为面对不同的action要做出选择，所以一个真正的解决方案应该会声明在何种条件下采取什么样的动作。比如，在刚刚提到的问题中，action可以是walk，dice，或者nil（不采取任何行动）。
然后我们规定，一个Policy Π 是一个state到一个action的映射，比如说：
Π（s）= walk, 如果s是奇数,
Π（s）= dice, 如果s是偶数，但不是20，
Π（s）= nil, 如果s=20,
注意把policy和transition probabilities区别开来，前者相当于是一种规定，后者是概率，涉及到计算问题。特别的，T(s, nil, s’) =1, reward (s, nil, s’) = 0.
那么如何衡量评判一个policy到底是好还是坏呢？
常用的标准是：Expected Utilities （期望效用）
比如，现在的policy是 Π(s)=walk， 如果s不等于20的话。在这个policy下，有下面的一系列的动作产生：
0， walk，1，walk，2，walk，，，，，，walk，20，nil,20，nil,20,,
那么期望的Expected Utility 就是：
Reward (0,walk,1) + γ^2 * reward (1,walk,2) + γ^3 * reward (2,walk,3) + …
那么在上面提到的policy（分奇数和偶数）的条件下，Expected Utility应该是什么样？刚开始的状态，s= 0, 第一个动作是dice，Expected Utility 就是 T(0, dice, s’) * reward (0, dice, s’). 但下一个动作，明显是不确定的.因为后面状态的分布是，0.5的概率是层数-1，1/12的概率会在{1，2，3，4，5，6}层中，所以要考虑所有可能的结果：[0 dice -1],[0,dice 2],,,,[0,dice,7]。
在离散数学中，利用递归来处理无限种可能的序列，比如一个函数f(n) = 0 + 1+2 +，，，，n,那么可以写成 f(n) = f(n-1) + n. 在上面的问题中，给定一个policy Π，V_Π(s)来代表在状态s条件下，采用policy Π的Expected Utility 是：
V_Π(s) = 0， 如果s是终止状态
V_Π(s) = T(s, Π(s), s’) * [reward (s, Π(s), s’) + γ V_Π(s)], s不是终止状态。
通常更普遍的一种方式是使用交互式的递归来表示，用到一个叫做Q-value的值：
在给定的policy Π 条件下：
Value: V_Π(s)：在状态s下，使用policy Π得到的Expected Utility，
Q-value：在状态s下使用action a ，然后执行policy Π得到的Expected Utility。
Dice Game
Dice Game (From Percy Liang, Stanford University)
有这样一个色子游戏，在每一轮：
如果选择退出的话，可以得到10块
选择继续的话，你得到4块，然后抛一枚色子，如果是1和2的话，游戏结束；否则的话，进入到下一轮。
用MDP来模拟一下上面的游戏：
状态：在/出局 这个游戏。
开始的状态：在这个游戏中
最终的状态：出局这个游戏
动作：退出/继续游戏
T(in, quit, out) = 1,
T(in, stay, out) = 2/6,
T(in, stay, in) = 4/6, T(out, stay, out) = 1.
Reward(in, quit, out) = 10, reward (in, stay, in) = 4, reward (in, stay, out) = 4,
那么根据MDP的policy evaluation 过程来衡量一下这个过程：
考虑这样一个policy，在没有出局的情况下，选择继续游戏，也即Π(in) = stay, 假设discount factor 是1.
V_Π(out) = 0. (出局的状态下，无论采取什么样的policy，Expected utility 都是0)，
V_Π(in) = Q(Π,in, stay) = T(in, stay, out) [reward (in, stay, out) +γ V_Π(out)] + T(in, stay, in) [reward (in, stay, in) +γ V_Π(in)] = 1/3 * [4 + 0] + 2/3 * [4 + V_Π(in)] ,
V_Π(in) = 12,
通常的情况，不一定能找到一个封闭的解，因为我们要取utility值最大的那一个方案，是非线性的。但可以用迭代的方式来计算。
不妨用V^0_Π(s)来表示第0次迭代，也即初始的Expected Utility。
初始化所有的状态，V^0_Π(s) = 0, 对于所有的状态s，
对于迭代的次数，t 从1 到 n:
对于每一个不同的状态，
V^t_Π(s) = 对于所有的子状态s’，求和 [reward (s, Π(s), s’) +γ V^{t-1}_Π(s)]，直到Vt的值收敛的的时候停止迭代。
回到这个dice game中的话，两个action，只有选择继续游戏，才有迭代下去的可能，所以默认Π(in)是选择stay (继续有效)，
V^t_Π(in) = 2/3 * (4 + V^{t-1}_Π(in)) + 4/3
Policy improvement and value iteration.
Policy improvement 简单的来讲两步：
首先计算所有状态的utility，V(s)，
这样利用第一步计算出来的utility，对于每个状态s的所有action，都可以得到Q(s,a)，取其中最大的值对应的action就是状态s采取的policy。
Value iteration （Bellman 1957）的话直接用迭代的方式去计算最优的utility：
首先初始化所有状态的utility为0，
设置n重循环：
对于每一个状态s：
注意这里的公式和上面不太一样的地方是，reward的方式，reward有past reward 和 potential reward，之前我们看到的都是potential reward，这里是past reward，后面有机会再详细分析这两种的不同。
Maze Game
来看一个经常被用到的例子（Maze Example from CMU, Markov Decision Process_Handout）
现在有一个3*3的九宫格，每一个位置相当于一个状态（离散的），可以往上下左右四个方向移动，来模拟这样一个例子：
初始状态：（2，2）坐标，
下一个状态：（1，2），（2，3），（2，1），（3，2）都有可能。
可以选择的action：up, down, left, right （每个动作也都是离散的）.
Transition Model: T(s,a,s’)~P(s’|s,a), 这里需要说明一下。
Policy: Π。最优的policy是使得整体的reward 和 utility 最大的那一个。
需要说明一下的是：
这里的transition model使用的是 first order of Markov probability，下一个状态只和当前的状态有关系，和之前的都没有关系。
P(X_t|X_{t-1}, X_{t-2}, X_{t-3},,,,,x_1) = P(X_t|X_{t-1}),
X_t 是t次迭代的时候的状态，X_{t-1}是前一次的状态。
关于transition model，它是很重要的一个概念。在一个确定的环境中，(determined environment)，每采取一个行动，执行的概率就是1. 而在随机的环境中 (stochastic environment), 如果你采取一个action，比如up，那么可能0.8的概率是up，0.1的概率是left，0.1的概率是right，left和right是垂直于up操作，down我们暂时不考虑。
也即T(s,up,s’) = 0.8。
Π^* = argmax_a\sum T(s,up,s’)U(s')
T(s,a,s’) 是transition probability，也即P(s’|s,a), U(s’) 是在s状态下采取action a的utility。
那么求和是什么操作？注意，这里的求和不是针对所有的action求和，而是针对一个action，由于不确定性导致的不同的状态求和。举个例子，现在我们的policy只要求有一个action，也即求出来那个使得utility累加和最大的那个action：
optimal policy = argmax [
Up: 0.8U((2,3)) + 0.1 * U((1,2)) + 0.1 * U((3,2))
Left: 0.8U((1,2)) + 0.1 * U((2,3)) + 0.1 * U((2,1))
Down: 0.8U((2,1)) + 0.1 * U((1,2)) + 0.1 * U((3,2))
Right: 0.8U((3,2)) + 0.1 * U((2,3)) + 0.1 * U((2,1))]
上面的迭代次数只有一次。
根据Bellman 方程，
R(s)是一个immediate reward，一般会给定值，不同的状态R(s)可能不一样，并且这里结束的时候两个状态（胜利和失败）保持不变是1和-1。
假设有n个状态的话，n个U(s)计算，每个都是取最大值操作，不能用线性求解的方式得到解。
通常会随机给定初始的utility值，不断地更新，最后值会收敛，不断接近真实值，这样的一个过程就实现了 value iteration。
来看一下整理的简单代码实现了：
# 机器树
# Markov Decision Process
import numpy as np
length = 5width = 5maze = np.zeros((length,width))
# print (maze)
# 右上角两个元素分别代表胜利和结束
length -= 1
width = 1
# print (length,width)
maze[0,length] = 1
maze[1,length] = -1
print (maze)
df = 0.5
r = -0.04
iteration = 20
actions = ['up','down','left','right']
# trans = np.array([0.8,0.1,0.1])
# x = a > b and 10 or 11
def compute_qvalue(x,y,action,value):
if action == 'up':
# and or 操作，记住加括号, 并且 python中 “0 or (-1) == -1”，所以判断与0的关系时，使用了tricky的判断的嵌套
if x == 0:
value[0] = maze[x,((y+1)>length) and y or (y+1)]*0.8 + maze[((x+1)>width) and x or (x+1),y]*0.1 + maze[x,y]*0.1
else:
value[0] = maze[x,((y+1)>length) and y or (y+1)]*0.8 + maze[((x+1)>width) and x or (x+1),y]*0.1 + maze[(x-1),y]*0.1
elif action == 'down':
if (x==0 and y==0):
value[1] = maze[x,y]*0.8 + maze[x,y]*0.1 + maze[((x+1)>width) and x or (x+1),y]*0.1
elif (x==0 and y!=0):
value[1] = maze[x,y-1]*0.8 + maze[x,y]*0.1 + maze[((x+1)>width) and x or (x+1),y]*0.1
elif (x!=0 and y==0):
value[1] = maze[x,y]*0.8 + maze[x-1,y]*0.1 + maze[((x+1)>width) and x or (x+1),y]*0.1
else:
value[1] = maze[x,y-1]*0.8 + maze[x-1,y]*0.1 + maze[((x+1)>width) and x or (x+1),y]*0.1
elif action == 'left':
if (x==0 and y==0):
value[2] = maze[x,y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y]*0.1
elif (x==0 and y!=0):
value[2] = maze[x,y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y-1]*0.1
elif (x!=0 and y==0):
value[2] = maze[x-1,y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y]*0.1
else:
value[2] = maze[x-1,y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y-1]*0.1
elif action == 'right':
if (y==0):
value[3] = maze[((x+1)>width) and x or (x+1),y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y]*0.1
else:
value[3] = maze[((x+1)>width) and x or (x+1),y]*0.8 + maze[x,((y+1)>length) and y or (y+1)]*0.1 + maze[x,y-1]*0.1
# 以（1，1）元素（状态）为例，
maze_copy = np.copy(maze)
for i in range(0,iteration):
print ("Iteration ",i)
for x in range(0,length+1):
for y in range(0,width+1):
if ((x!=0 and y!=width) or (x!=1 and y!=width)):
value = np.zeros(4)# up,down,left,right
for action in actions:
compute_qvalue(x,y,action,value)
maze_copy[x,y] = r + df * max(value)
# print (maze)
# print (maze_copy)
maze = np.copy(maze_copy)
print (maze)
后面一起来看A* 搜索和 Reinforcement Learning.
Reference:
Implementing Reinforcement Learning with Markov Decision Process
CMU Markov Decision Process
