【机器学习】马尔科夫决策过程

2020 年 1 月 28 日 AINLP

本文介绍了马尔可夫决策过程，首先给出了马尔可夫决策过程的定义形式，其核心是在时序上的各种状态下如何选择最优决策得到最大回报的决策序列，通过贝尔曼方程得到累积回报函数；然后介绍两种基本的求解最优决策的方法，值迭代和策略迭代，同时分析了两种方法的适用场景；最后回过头来介绍了马尔科夫决策过程中的参数估计问题：求解 -即在该状态下采取该决策到底下一状态的概率。

作者 | 文杰

编辑 | yuquanle

马尔科夫决策过程

A、马尔科夫决策过程

机器学习算法（有监督，无监督，弱监督）中，马尔科夫决策过程是弱监督中的一类叫增强学习。增加学习与传统的有监督和无监督不同的地方是，这些方法都是一次性决定最终结果的，而无法刻画一个决策过程，无法直接定义每一次决策的优劣，也就是说每一次的决策信息都是弱信息，所以某种程度上讲，强化学习也属于弱监督学习。从模型角度来看，也属于马尔科夫模型，其与隐马尔科夫模型有非常强的可比性。

下面是一个常用的马尔科夫模型的划分关系

	不考虑动作	考虑动作
状态完全可见	马尔科夫链(MC)	马尔科夫决策过程(MDP)
状态不完全可见	隐马尔科夫模型(HMM)	不完全可观察马尔科夫决策过程(POMDP)

马尔科夫决策过程：

马尔科夫决策过程由五元组组成

：表示状态集合

：表示一组动作

：表示在某一状态下，采取动作，转移到转态的概率，也就是说在确定的状态下采取相应的动作之后不能完全确定下一状态，而是以一定的概率确定下一状态。

：表示决策过程的一个阻尼系数，用户定义回报在决策过程中随时间打折扣，加快决策国产的收敛

：表示在该状态下的一个回报，有时由动作和状态共同决定回报该时刻的回报。

有了上面的定义之后，一个完整的马尔科夫决策过程状态转移图如下：

该过程表示从出发，有决策函数来选择相应的动作，然后以概率到达下一状态，这里的只是表示第时刻的状态，而的值属于状态集。

回报函数定义之后，整个决策过程的累积回报如下：

当回报函数与状态无关累积回报如下：

其中为折扣因子，随着决策不断进行，回报不断打折扣。

当定义不同决策函数时，我们会得到不同的回报，因此就定义了一个决策到回报的函数。在整个决策过程中，给定决策函数 —在状态下采取动作。因此，从状态出发，采用决策函数，有累积回报函数如下：

直接最大化累积回报函数不易，从递推角度来看，由贝尔曼方程有：

其中为立即回报，表示由采取动作之后转移到下一个状态集中，具体到哪个状态的概率为。其解释性可以理解为下象棋最终的累积回报为输赢，在第状态下的累积回报则是当前状态下的立即回报以及未来的回报。第一项为立即回报，第二项就是未来的回报。

有了上面的贝尔曼方程，我们的目标就是最大化任意状态下出发的累积回报函数，其中也是一个决策函数，但是在累积回报函数中它是我们需要优化的变量。目标函数如下：

由目标函数可以看出，最优回报和最优决策一一对应。最大化累积回报对应的决策函数就是最有决策，最有决策对应的累积回报也是最大累积回报，所以最有决策如下：

有了最优决策和最大累积回报，那么必定有下式：

也就是说最优决策下对应的累积回报一定不小于一般的决策下的累积回报。

值得注意是，最优决策是出于全局考虑的，是从所有状态下出发到得到的累积回报的加和最大，这就意味着决策函数不保证其中每一个状态出发根据决策函数得到的累积回报都是最大的。

最优决策：

也许上面的目标函数还不清晰，如何求解最有决策，如何最大化累积回报

下面结合例子来介绍如何求解上面的目标函数。且说明累积回报函数本身就是一个过程的累积回报，回报函数才是每一步的回报。

下面再来看求解上述最优问题，其中就是以s为初始状态沿着决策函数走到结束状态的累积回报。

值迭代：

将每一个初始状态为s的初始化为0,目标状态累积回报为1
循环直到收敛{

对于每一个初始状态，对进行更新：

}

可以看出，更新第一次所有的，也就是说都只看眼下的立即回报，然后由于奖励状态和惩罚状态的分布不同，由靠近奖励状态和惩罚状态的状态决策逐渐导向到初始状态的决策，这也就是累积回报不断更新的原因（动力）。但是值得思考的还是最终会不会收敛到最优累积回报（暂时不作讨论）。

内循环迭代的的处理方法有两种：

同步迭代：即在一次循环过程中，累积回报不更新，而是计算完所有的累积回报之后，再统一更新。
异步迭代，即在一次循环过程中，每计算完一个初始状态下累积回报就立即更新，不需要等到所有的累积回报都计算出来之后再更新。

可以看出两种迭代方式造成不同的原因是第二项，因为立即更新之后，再计算下一个初始状态下的累积回报与暂时不更新得到的累积回报肯定不一样，拿第一次更新为例，同步更新第一次，而异步更新则第一次内循环中，除了第一次更新的s会出现，剩下的都有，值得肯定的是异步迭代的收敛速度肯定是快于同步迭代。

策略迭代：

值迭代是使累积回报值最优为目标进行迭代，而策略迭代是借助累积回报最优即策略最优的等价性，进行策略迭代。

随机指定一个策略。
循环直到收敛{

a:令

b:对于每一个状态s，对做更新

}

这里要说明的是a步是通过前面的贝尔曼方程，以解方程的形式求解出每一个状态下的累积回报：

在b步则是根据累积回报值，重新更新决策。

同样，收敛性也是值得探讨的，这里简单的思考一下，由于奖励状态和惩罚状态的分布，以及累积回报唯一确定决策函数，那么未达到最优决策，必然累积回报和决策函数处于不稳定的状态，而只有当到达最优决策时，才有：

所以该过程就是在a步由决策函数确定累积回报，然后最大化累积回报来更新决策，如此反复，则有最优决策。值迭代和策略迭代比较：可以看出策略迭代涉及从决策函数到累积回报的解线性方程组的步骤，值迭代则是反复的，所以策略迭代更适合处理少量状态的情况，一般10000以内还是可以接受的。

MDP中的参数估计：

回过头来再来看前面的马尔科夫决策过程的定义是一个五元组，一般情况下，五元组应该是我们更加特定的问题建立马尔科夫决策模型时该确定的，并在此基础上来求解最优决策。所以在求解最优决策之前，我们还需更加实际问题建立马尔科夫模型，建模过程就是确定五元组的过程，其中我们仅考虑状态转移概率，那么也就是一个参数估计过程。（其他参数一般都好确定，或设定）。

假设，在时间过程中，我们有下面的状态转移路径：

其中表示步，第条转移路径对应的状态，是状态下执行的动作，每一条转移路径中状态数都是有限的，在实际过程中，每一个状态转移路径都要进入终结状态。如果我们获得了很多上面的转移路径，那么我们就可以来估计参数。

分子是在状态下采取动作都转移到的次数，分母是在状态下采取动作的次数。为了避免的情况，同样采用拉普拉斯平滑。也就是说当到达的状态是样本中为为到达过的状态，那么在该状态下的执行的动作达到下一状态的概率均分。上面的这种估计方法是从历史数据中进行统计的，同样该方法适合于在线更新。对于立即回报函数的估计，一般根据实际情况学习或者设定。

所以整个马尔科夫决策过程流程如下（以策略迭代为例）：

随机初始化策略。
循环直到收敛{

a 在样本上统计该策略下每个状态转移的次数，来估计和

b 使用估计到参数来更新对应决策函数下的累积回报

c 根据更新的累积回报重新进行决策，即更新

}

整个流程就是在策略迭代的基础上，同时进行了参数估计。

代码实战

A、马尔可夫决策过程值迭代

/***
 马尔科夫决策过程值迭代，关键在于第一次迭代要例外，
 因为目标状态是一个终止状态，放到迭代循环里面会出现
 临近的状态回报函数无限的，发散。
 迭代过程采用的是异步迭代，即每一次内层循环找到更优的
 回报就立即更新最大回报，以便与之相邻的状态能立即更新到最优
 */ 
   /****
 值迭代
 同步更新
 12*12*7
   */ 

while(!flag)
 {
 flag=1;
 for(i=0; i<size; i++)
 {
 if(action[i]>0||action[i]==0)
 maxreward[i]=reward[i]+maxreward[action[i]];
 else 
 maxreward[i]=reward[i];
 }//放到这意味着同步更新，count=1008是12*12的7倍，即扫了7遍
 for(i=0; i<size; i++)//对每一个状态求最大的V(s)
 {
 for(j=0; j<size; j++)//策略迭代的话这里其实可以换做扫一遍策略集，这也就是和值迭代不同的地方
 {
 //cout<<"i="<<i<<" "<<maxreward[i]<<" "<<endl;
 if(matrix[i][j]==1&&maxreward[j]>maxreward[i]-reward[i]+0.0001)//更新累积回报
 {
 action[i]=j;
 //if(action[i]>0||action[i]==0)
 //maxreward[i]=reward[i]+maxreward[action[i]];//放到这是异步更新，
 //else
 // maxreward[i]=reward[i];
 flag=0;//当累积回报不再更新，即不进入该if，那么就结束迭代
 }
 count++;
 }
 }
 }

B、马尔可夫决策过程策略迭代

while(!flag)
 {
 flag=1;
 for(i=0; i<size; i++)//对每一个状态求最大的V(s)
 {
 for(j=0; j<ACTION; j++)//策略迭代的话这里其实可以换做扫一遍策略集，这也就是和值迭代不同的地方
 {
 //cout<<"i="<<i<<" "<<maxreward[i]<<" "<<endl;
 if(matrix[i][ac[j]+i]==1&&maxreward[ac[j]+i]>maxreward[i]-reward[i]+0.0001)
 {
 action[i]=j;
 //if(reward[i]!=1&&reward[i]!=-1)
 maxreward[i]=reward[i]+maxreward[ac[j]+i];
 //else
 // maxreward[i]=reward[i];
 flag=0;
 }
 count++;
 }
 }
 }

C、马尔可夫决策过程动态规划版

/**
   4 非递归动态规划
   从最终状态出发，采用广度遍历不断的更新其上一状态的累积回报
 */ 
   /*
 
while(q!=NULL)//这里图的广度遍历没有用到队列，但也用到了队列的思想
 //对于当前步能到达的节点用链表连接起来，然后逐渐进行下一步的能到达的节点进行入链（入队列），同样是一种先进先出思想
 {
 for(i=0; i<size; i++) //由于不是策略迭代，只能遍历所有的状态，找出能到的，且更优的
 {
 if(matrix[i][q->data]==1&&maxreward[i]<0)//double类型比较大小的偏差，加上一个小数作为精度
 {
 maxreward[i]=reward[i]+maxreward[q->data];
 p=(subset *)malloc(sizeof(subset)*1);
 p->data=i;
 p->next=NULL;
 q=maxsubset;
 while((q->next)!=NULL)
 q=q->next;
 q->next=p;
 }
 count++;
 }
 maxsubset->next=maxsubset->next->next;//删除当前节点，即当前步下能到达的节点都已经走完了，可出队列了
 q=maxsubset->next;//
 }

The End

本文转载自公众号：AI小白入门，作者文杰

推荐阅读

AINLP年度阅读收藏清单

鼠年春节，用 GPT-2 自动写对联和对对联

大幅减少GPU显存占用：可逆残差网络(The Reversible Residual Network)

征稿启示| 让更多的NLPer看到你的文章

AINLP-DBC GPU 云服务器租用平台建立，价格足够便宜

我们建了一个免费的知识星球：AINLP芝麻街，欢迎来玩，期待一个高质量的NLP问答社区

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLP君微信(id：AINLP2)，备注工作/研究方向+加群目的。