淘先锋技术网

首页 1 2 3 4 5 6 7

 MDP简介 --Markov decision process

马尔可夫决策过程可以更正式地描述强化学习的环境environment,其中,这个环境是完全可观测的【fully observable】,也就是当前状态完全体现了这个过程特征 ,基本上所有RL问题都可以化为MDP的形式,比如最优控制主要和连续型MDP有关。部分可观测的问题也可以转化为MDP。

目录

 MDP简介 --Markov decision process

马尔可夫性质

状态转移矩阵

马尔可夫过程

马氏链MDP:以学生上课的状态为例

Markov Reward Process

MRP:以学生上课的状态为例

回报Return

值函数 value function

举例:学生上课的MRP Returns

举例: 学生上课的MRP的状态-值函数

MRP 的Bellman Equation【贝尔曼方程】

贝尔曼方程的矩阵表示

贝尔曼方程的求解

马尔可夫决策过程MDP: a Markov reward process with decisions



 


马尔可夫性质

   我们用状态S_{t} 来切分历史数据,H_{1:t}\, \rightarrow \, S_{t}\, \rightarrow \, H_{t+1:\infty }  状态 S_{t}从history中捕获了所有县官的信息。若已知状态S_{t},则H_{1:t}\, 就可以被丢掉。状态 S_{t}H_{t+1:\infty } 的充分统计量。


状态转移矩阵

一个马尔可夫状态从当前的s转到下一状态 s^{​{}'}的概率定义为状态转移概率:

所有的当前状态s转移到所有后继状态的概率构成一个矩阵 ——状态转移矩阵P:

由于当前状态必然转移到下一个可选的状态中的某一个,所以P矩阵的每一行的和都为1.

 

马尔可夫过程

是一个无记忆性的随机过程,也就是随机状态序列S_{1}\, ,\, S_{2}\, ,...具有马尔可夫性。

 

马氏链MDP:以学生上课的状态为例

学生们上课的状态,在上课堂【Class1】时,

  • 有50%的人会选择继续听下一节课,另外50%的人(可能觉得课程无聊)选择去刷Facebook,
  • 刷Facebook的人: 有90%的继续刷Facebook,还有10%的人会回到课堂1,
  • 在课堂2处,有20%的人选择睡觉,80%的人选择去听课堂3,
  • 在课堂3处,有60%的人通过考试,有40%的人选择去酒吧喝两杯;
  • 去到酒吧的人,有20%的人回到课堂1,40%的人回到课堂2,40%的人回到课堂3,
  • 通过考试的人,全都去睡觉。

假设状态S1 = C1,用FB表示Facebook,那么我们从上述的马氏链中采样序列【episodes】,

,可以得到以下几种:【状态有C1、 C2、 C3、 Pass 、Pub 、FB 、Sleep】

  • 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

Markov Reward Process

马尔可夫奖励过程是具有values的马氏链,可以定义为一个四元组  < \, S\, ,P,\, R, \,\gamma >,其中R是奖励函数,\gamma是折扣因子。

与MDP的不同在于增加了从一个状态转到下一个状态的奖励的期望。

MRP:以学生上课的状态为例


回报Return

大多数马尔可夫reward and decision过程都要乘以折扣因子\gamma。为什么?

  • 数学上的计算简便
  • 避免了周期性马氏过程的 infinite returns 问题。
  • 无法充分地表示未来的不确定性。
  • 如果奖励是关于金融方面的,那么眼前的回报会比延迟得到的回报赚得更多的利息。
  • 人类和动物的天性都是偏好眼前利益。
  • 如果所有的序列是有限个时间步,有时候也使用不带折扣因子的MRP (i.e. \gamma = 1),
  • 每一个时间步都要乘以\gamma,由此可知在隔k+1个时间步后,再接受到奖励的R值变为\gamma ^{k}R. ,说明了比起延迟得到的奖励,这个值更看重眼前的奖励。

因为未来的奖励要在未来才能兑现,在当前状态下就要打个折扣。比如最近的知乎话题(马云这类大佬的经验与知识和一千万你选哪个)的高赞回答(马云的经验知识,可能就是告诉你要选这一千万),为什么呀?因为未来具有很大的不确定性,就像鸡汤说的:明天和意外不知哪一个先来。所以要给当下的奖励以更高的权重,对于长远未来的奖励要打个折扣。


值函数 value function

值函数v(s) 给出了MRP中从状态s开始的 expected return【回报的期望】。


举例:学生上课的MRP Returns

 从学生的MRP中,对 returns 采样。从S1 = C1开始,\gamma =\frac{1}{2}


举例: 学生上课的MRP的状态-值函数

 


MRP 的Bellman Equation【贝尔曼方程】

值函数可以分解为两个部分:immediate reward R_{t+1};下一状态的值函数乘以\gamma

 


贝尔曼方程的矩阵表示

 

   是一个线性方程

其中v是一个列向量,它表示每一个状态的值函数

贝尔曼方程的求解

由于线性方程可直接求解:

对于求解有n个状态的贝尔曼方程,的计算复杂度为,因此只有n很小时才直接求解,当n很大时用迭代方法求解,比如:

动态规划、 Monte-Carlo估计、时序差分学习Temporal-Difference learning】


马尔可夫决策过程MDP: a Markov reward process with decisions