Machine Learning 16—Reinforcement Learning
之前我们学过3个部分的内容：监督学习、学习理论、半监督学习。现在我们来学习第四部分：自增强学习。 在监督学习中，给定了训练集以及对应的标签y ，算法要做的就是令预测输出尽可能地接近y 。在这种情况下，算法运行过程中对应的是有正确答案的。但有些时候，在对问题作出决策或者控制时，我们很难提供一个确切的正确答案。比如在四足机器人行走编程中，我们在一开始的时候对才去怎样的行动是“正确的”根本没有概念，我们只知道这是一个足部调节的过程，因此在这里，监督学习算法并不适用。
在自增强学习框架中，算法的核心是奖励函数，区分出学习过程中哪些行为是“好”的，哪些行为是“坏”的。对于四足机器人行走问题，当机器人能够向前进时，我们给予积极奖励；当机器人向后退或者跌倒时候，我们给予消极惩罚。这样，有了奖励惩罚机制，在多次训练后，机器人会越走越好。
自增强学习成功应用在了无人机飞行、机器人行走、市场决策选择等问题上。为了正式地定义自增强学习，我们先来看马尔科夫决策过程（Markov Decision Process,简写MDP ）。
Markov Decision Process
一个马尔科夫决策过程是一个五元组(S,A,{Psa },γ,R) ，当然有一些书籍上用四元组表示，本意是不变的哈。其中：
S 表示状态集（states ）
A 表示行为集（actions ）
对于当前状态s 和当前采取的动作a ，下一个状态s , 服从P sa 分布（下P sa 表示状态转换分布，
一个状态出现的概率依赖于前一个状态以及前状态所采取的动作），而且有∑P
s , sa (s, ) =1,P sa (s, ) ≥0。这里隐含的是马尔科夫性质：一个随机过程的未来状态的条件概
率分布仅仅依赖于当前状态与该状态下的动作，换句话说，在给定现在状态的时候，它与过去状态是条件独立的。在一些资料中将P sa 写成矩阵形式，即状态转换矩阵。 γ∈[0,1)表示的是discount factor，具体含义稍后解释。
R ：SxR →表示奖励函数。R 为实数。有时候R 只与状态S 有关（更多时候与状态S 与行为A 都有关），下面的例子就是如此。为了更加具体的表示五元组的含义，我们来说一个MDP 相关的具体例子：
上图的场景表征的是机器人导航任务，想象一个机器人生活在网格世界中，阴暗单元是一个障碍。假设我希望机器人到达的目的地是右上角的格子（4,3），于是我用+1奖励来关联这个单元；我想让它避免格子（4,2），于是我用-1奖励来关联该单元。现在让我们来看看在该问题中，MDP 的五元组是什么：
S ：机器人可以在11个网格中的任何一个，那么一共有11个状态；集合S 对应11个可能到达的位置。
A={N S E W}。机器人可以做出的动作有4个：向东 向南 向西 向北。
P sa ：假设机器人的行为核心设计并不是那么精准，机器人在受到相关指令后有可能会走偏方向或者行走距离不那么精确，为简化分析，建立机器人随机动态模型如下：
即命令机器人朝北（朝上）行走，他有0.1的概率朝着左右方向，0.8的概率朝指定方向。当机器人撞到墙上或者要走到不是相邻的格子时，其概率为0. （当然，也有关于P sa 的确定性模型，即命令机器人朝北，那么机器人就必然是向北运动的，这是很理想的模型，我们在此不加以研究。）让我们还是用例子来说明：假设上例中机器人状态为（3,1），动作指令为N ，则相应的如下：
P (3,1)N ((3,2))=0.8;P (3,1)N ((2,1))=0.1；
R ：奖励函数可以设置为： P (3,1)N ((4,1))=0.1；P (3,1)N ((3,3))=0；...
R ((4,3))=+1
R ((4,2))=-1
R (s ) =-0.02对于其他状态s
设置其他状态的奖励函数为R (s ) =-0.02的做法相当普遍，可以认为这是电池消耗所应有的付出，目的在于提醒机器人不要浪费时间，尽快达到目的地。
另外一个需要注意的是，当机器人达到目的地（我们这里是（4,3））后，那么系统应该停止，不再计算下去。
让我们来看看MDP 的动态处理过程： 初始状态s 0采取的动作是a 0∈A ，那么下一个状态将会被随机选择（只不过概率不一样），即s 1P s 0a 0。在s 1采取的动作是a 1∈A ，同样地得到一个新的状态s 2 P s 1a 1，类推。流程图如下：
我们令状态序列s 0,s 1,s 2的总回报为：
在上面机器人例子中，由于奖励函数R 只与状态S 有关，则总回报写成：
自增强学习算法的目标是使得总回报的期望最大化，即：
max E [R (s0) +γR (s1) +γ2R (s2) +
m ] （1） 在这样的目标函数下，因为γ∈[0,1)，越往后权重γ的值越小，因此采取的行动策略是：
积极的奖励尽量在前面（越快出现越好），消极惩罚尽量在后面（越晚出现越好）。
相应的，一个策略(policy)函数定义为π:S →A ，即输入为状态S ，输出为A ，亦即策略π(s ) =a 告诉我们在状态s 下该执行的动作是什么。例子中格子机器人行走至目的地的最佳策略如下：
对应目标函数，我们或许就不难理解机器人位于（3,1）时的最佳策略是向左走而不是向上走，因为希望“积极奖励越快出现越好，消极惩罚越晚出现越好”，向上确实可以更快得到奖励+1，但是路途中有更大的可能会出现消极惩罚-1. 因此该最佳策略可以理解为一种折中选择的结果。
为了知道如何得出最佳策略的算法，我们还需要定义一些变量：
V π：对于任意指定的策略π，定义值函数V π为：
V π(s ) =E [R (s0) +γR (s1) +γ2R (s2) +
πs 0=s , π]
（
2
） 由V π的定义可以看出，V (s ) 就是从状态s 出发，依据策略π采取行动后的总回报函数的
期望。
为直观理解，画出格子机器人例子中的某一个策略以及相应的计算出了的V π（具体计算方式很快会给出）：
当然，这个策略是一个很糟糕的策略，和最优策略相比差太多了。
π上式还可以写成：V (s ) =E [R (s0) +γ(R (s1) +γR (s2) +
π) s 0=s , π]，里面的一项其实就是：V (s1) =E [R (s1) +γR (s2) +s 1=s , π]。也就是说，值函数可以表示成：
（3）
上式就是贝尔曼公式(Bellman equation).其中，R (s ) 项可视为我们采取状态s 作为初始状态的立即回报，而第二项可视为将来的回报。
事实上，给定一个固定的策略π，我们可以通过贝尔曼公式求接触相应的V π，以刚刚的例子来说，设π为
对于状态（3,1），策略π指示动作为向上，写下贝尔曼公式为：
V π((3,1))=R ((3,1))+γ[0.8V π((3,2))+0.1V π((4,1))+0.1V π((2,1))]
同样的，还可以写下另外
10个状态下的贝尔曼公式，
一共11个公式，求解11个未知数（现在变成了求解线性方程组的问题了），可以求解出对应的V π。
V (s ) 定义最优值函数为： *
V *(s )=max V π(s ) π
从定义可以看出，V (s ) 其实就是从状态s 出发，依据任意一个π所能够获得的最大的总回报函数的期望。注意，这里不再限制需要依据某一个固定的策略π。关于最优值函数的贝尔曼方程可以写成： *
（4）
第一项可以视为采取状态s 作为最初状态的立即回报，第二项即使在状态s 上采取行动a 时获得的将来回报（由于a 有多重选择，选择可以令总回报期望最大的那个a ）。同样需要注意的是，这里不再限制需要依据某一个固定的π作选择。同样的，我们可以通过联立方程求解V *。
π*
--根据上面的推导，可以定义π*如下：
（5）
这是最优值函数的贝尔曼方程中的第二项，它回答的问题是：在当前状态s 下，才采取怎样的行动才是最优的。当然，想求解该表达式，必须先求得V *(s ) 的具体表示。但是公式（4）并没有给我们一个漂亮的算法去计算它（相比于之前固定的策略π然后求解n 个线性方程的解法，这里由于策略π不固定，可能有的π组合过多）。
这并不意味着我们无法求解π*了，毕竟我们的目标就是找到最优的策略π*来指导我们的行动。求解思路如下：先求解出V *，然后由π*的定义求解出π*，下面有两种算法可以帮助我们实现目标：
Value Interation
算法步骤：
1. 对于每个状态s ，初始化V (s ) =0;
2. 重复以下步骤直至收敛 {
对每个状态s ，更新
}
算法步骤简单，思想也简单但有效：重复贝尔曼公式（4），更新V (s ) 。经过验证，该算
*法最终能够使得V (s ) →V (s ) 。具体证明值迭代算法收敛的过程可以参考文档
中的3-10部分。
有了V *，我们就能够通过公式得到π*。该算法可以使用同步更新和异步更新，效果差不多。 回到格子机器人的例子，我们最终算出和π*如下所示：
让我们用计算来说明，为什么在状态（3,1）中向左走更好？
向左走：
∑P
s , sa (s, ) V *(s, )
=0.8*0.75+0.1*0.69+0.1*0.71=0.74
向上走： ∑P s , sa (s, ) V *(s, ) =0.8*0.69+0.1*0.75+0.1*0.49=0.67计算结果显示：向左走的总回报期望更大。
Policy Interation
算法步骤：
1. 随机初始化策略π；
2. 重复以下步骤直至收敛 {
(a) 令V :=V π；其中V π通过求解贝尔曼方程（多个方程联立）得到；
(b) 对每个状态s ，更新π(s ) :=arg max a ∈A ∑P s , sa (s, ) V (s, )
}
算法步骤依然简洁。在比较两个算法的计算成本时候，因为policy iteration 需要求解n 个方程联立的问题（n 为状态数），所以可以这样选：在状态数较少的时候，选policy iteration ，反之选value iteration。
下面来着手解决一个可能的情况：假设MDP 中的五元组中我不知道{P sa }，如何处理呢？这种情况是常见的：当试图控制直升机的时候，你一开始并不知道直升机从初始状态过渡到什么状态或者在某一状态下采取的行动是什么，因为直升机整个系统很复杂，
往往不清楚会到
达什么状态。
这个时候，需要做的事情就是尝试从数据中估计出状态转移分布{P sa }，具体做法如下：
1#在状态s 采取行动a 时转变到状态s , 的次数0, ，则令P sa (s ) =） P sa (s ) =s #在状态s 采取行动a 时转变转变状态的总次数0,
在实际工作中，随着我们试验次数的增加或者对实验对象了解程度有所加深，我们不仅仅可以使用以上方法来估计{P sa }，还可以结合更多的先验知识（经验方法）。当奖励函数R 不清楚的时候，同样的思路可以让我们去估计在状态s 下的即时奖励R （s ）.
值得注意的是，在增强学习算法当中，面对不同的实际问题时，有很多时候是多种方法混合使用的。我们不需要拘泥于仅仅使用一种算法。
补充：
关于MDP 的代码实现，由于我正在学习java ，找到一个java 的算法库：
这是一个基于面向对象MDP （OO-MDP ）建立起来的框架，能够实现增强学习方面的很多算法。由于是英文的，需要一段时间来慢慢理解整个布局。当然，将其作为一个工具箱来使用时非常不错的，而且可以实现很酷的界面效果：
（格子游戏：穿越阻碍，到达设定目标点） （策略图显示）
Machine Learning 16—Reinforcement Learning
之前我们学过3个部分的内容：监督学习、学习理论、半监督学习。现在我们来学习第四部分：自增强学习。 在监督学习中，给定了训练集以及对应的标签y ，算法要做的就是令预测输出尽可能地接近y 。在这种情况下，算法运行过程中对应的是有正确答案的。但有些时候，在对问题作出决策或者控制时，我们很难提供一个确切的正确答案。比如在四足机器人行走编程中，我们在一开始的时候对才去怎样的行动是“正确的”根本没有概念，我们只知道这是一个足部调节的过程，因此在这里，监督学习算法并不适用。
在自增强学习框架中，算法的核心是奖励函数，区分出学习过程中哪些行为是“好”的，哪些行为是“坏”的。对于四足机器人行走问题，当机器人能够向前进时，我们给予积极奖励；当机器人向后退或者跌倒时候，我们给予消极惩罚。这样，有了奖励惩罚机制，在多次训练后，机器人会越走越好。
自增强学习成功应用在了无人机飞行、机器人行走、市场决策选择等问题上。为了正式地定义自增强学习，我们先来看马尔科夫决策过程（Markov Decision Process,简写MDP ）。
Markov Decision Process
一个马尔科夫决策过程是一个五元组(S,A,{Psa },γ,R) ，当然有一些书籍上用四元组表示，本意是不变的哈。其中：
S 表示状态集（states ）
A 表示行为集（actions ）
对于当前状态s 和当前采取的动作a ，下一个状态s , 服从P sa 分布（下P sa 表示状态转换分布，
一个状态出现的概率依赖于前一个状态以及前状态所采取的动作），而且有∑P
s , sa (s, ) =1,P sa (s, ) ≥0。这里隐含的是马尔科夫性质：一个随机过程的未来状态的条件概
率分布仅仅依赖于当前状态与该状态下的动作，换句话说，在给定现在状态的时候，它与过去状态是条件独立的。在一些资料中将P sa 写成矩阵形式，即状态转换矩阵。 γ∈[0,1)表示的是discount factor，具体含义稍后解释。
R ：SxR →表示奖励函数。R 为实数。有时候R 只与状态S 有关（更多时候与状态S 与行为A 都有关），下面的例子就是如此。为了更加具体的表示五元组的含义，我们来说一个MDP 相关的具体例子：
上图的场景表征的是机器人导航任务，想象一个机器人生活在网格世界中，阴暗单元是一个障碍。假设我希望机器人到达的目的地是右上角的格子（4,3），于是我用+1奖励来关联这个单元；我想让它避免格子（4,2），于是我用-1奖励来关联该单元。现在让我们来看看在该问题中，MDP 的五元组是什么：
S ：机器人可以在11个网格中的任何一个，那么一共有11个状态；集合S 对应11个可能到达的位置。
A={N S E W}。机器人可以做出的动作有4个：向东 向南 向西 向北。
P sa ：假设机器人的行为核心设计并不是那么精准，机器人在受到相关指令后有可能会走偏方向或者行走距离不那么精确，为简化分析，建立机器人随机动态模型如下：
即命令机器人朝北（朝上）行走，他有0.1的概率朝着左右方向，0.8的概率朝指定方向。当机器人撞到墙上或者要走到不是相邻的格子时，其概率为0. （当然，也有关于P sa 的确定性模型，即命令机器人朝北，那么机器人就必然是向北运动的，这是很理想的模型，我们在此不加以研究。）让我们还是用例子来说明：假设上例中机器人状态为（3,1），动作指令为N ，则相应的如下：
P (3,1)N ((3,2))=0.8;P (3,1)N ((2,1))=0.1；
R ：奖励函数可以设置为： P (3,1)N ((4,1))=0.1；P (3,1)N ((3,3))=0；...
R ((4,3))=+1
R ((4,2))=-1
R (s ) =-0.02对于其他状态s
设置其他状态的奖励函数为R (s ) =-0.02的做法相当普遍，可以认为这是电池消耗所应有的付出，目的在于提醒机器人不要浪费时间，尽快达到目的地。
另外一个需要注意的是，当机器人达到目的地（我们这里是（4,3））后，那么系统应该停止，不再计算下去。
让我们来看看MDP 的动态处理过程： 初始状态s 0采取的动作是a 0∈A ，那么下一个状态将会被随机选择（只不过概率不一样），即s 1P s 0a 0。在s 1采取的动作是a 1∈A ，同样地得到一个新的状态s 2 P s 1a 1，类推。流程图如下：
我们令状态序列s 0,s 1,s 2的总回报为：
在上面机器人例子中，由于奖励函数R 只与状态S 有关，则总回报写成：
自增强学习算法的目标是使得总回报的期望最大化，即：
max E [R (s0) +γR (s1) +γ2R (s2) +
m ] （1） 在这样的目标函数下，因为γ∈[0,1)，越往后权重γ的值越小，因此采取的行动策略是：
积极的奖励尽量在前面（越快出现越好），消极惩罚尽量在后面（越晚出现越好）。
相应的，一个策略(policy)函数定义为π:S →A ，即输入为状态S ，输出为A ，亦即策略π(s ) =a 告诉我们在状态s 下该执行的动作是什么。例子中格子机器人行走至目的地的最佳策略如下：
对应目标函数，我们或许就不难理解机器人位于（3,1）时的最佳策略是向左走而不是向上走，因为希望“积极奖励越快出现越好，消极惩罚越晚出现越好”，向上确实可以更快得到奖励+1，但是路途中有更大的可能会出现消极惩罚-1. 因此该最佳策略可以理解为一种折中选择的结果。
为了知道如何得出最佳策略的算法，我们还需要定义一些变量：
V π：对于任意指定的策略π，定义值函数V π为：
V π(s ) =E [R (s0) +γR (s1) +γ2R (s2) +
πs 0=s , π]
（
2
） 由V π的定义可以看出，V (s ) 就是从状态s 出发，依据策略π采取行动后的总回报函数的
期望。
为直观理解，画出格子机器人例子中的某一个策略以及相应的计算出了的V π（具体计算方式很快会给出）：
当然，这个策略是一个很糟糕的策略，和最优策略相比差太多了。
π上式还可以写成：V (s ) =E [R (s0) +γ(R (s1) +γR (s2) +
π) s 0=s , π]，里面的一项其实就是：V (s1) =E [R (s1) +γR (s2) +s 1=s , π]。也就是说，值函数可以表示成：
（3）
上式就是贝尔曼公式(Bellman equation).其中，R (s ) 项可视为我们采取状态s 作为初始状态的立即回报，而第二项可视为将来的回报。
事实上，给定一个固定的策略π，我们可以通过贝尔曼公式求接触相应的V π，以刚刚的例子来说，设π为
对于状态（3,1），策略π指示动作为向上，写下贝尔曼公式为：
V π((3,1))=R ((3,1))+γ[0.8V π((3,2))+0.1V π((4,1))+0.1V π((2,1))]
同样的，还可以写下另外
10个状态下的贝尔曼公式，
一共11个公式，求解11个未知数（现在变成了求解线性方程组的问题了），可以求解出对应的V π。
V (s ) 定义最优值函数为： *
V *(s )=max V π(s ) π
从定义可以看出，V (s ) 其实就是从状态s 出发，依据任意一个π所能够获得的最大的总回报函数的期望。注意，这里不再限制需要依据某一个固定的策略π。关于最优值函数的贝尔曼方程可以写成： *
（4）
第一项可以视为采取状态s 作为最初状态的立即回报，第二项即使在状态s 上采取行动a 时获得的将来回报（由于a 有多重选择，选择可以令总回报期望最大的那个a ）。同样需要注意的是，这里不再限制需要依据某一个固定的π作选择。同样的，我们可以通过联立方程求解V *。
π*
--根据上面的推导，可以定义π*如下：
（5）
这是最优值函数的贝尔曼方程中的第二项，它回答的问题是：在当前状态s 下，才采取怎样的行动才是最优的。当然，想求解该表达式，必须先求得V *(s ) 的具体表示。但是公式（4）并没有给我们一个漂亮的算法去计算它（相比于之前固定的策略π然后求解n 个线性方程的解法，这里由于策略π不固定，可能有的π组合过多）。
这并不意味着我们无法求解π*了，毕竟我们的目标就是找到最优的策略π*来指导我们的行动。求解思路如下：先求解出V *，然后由π*的定义求解出π*，下面有两种算法可以帮助我们实现目标：
Value Interation
算法步骤：
1. 对于每个状态s ，初始化V (s ) =0;
2. 重复以下步骤直至收敛 {
对每个状态s ，更新
}
算法步骤简单，思想也简单但有效：重复贝尔曼公式（4），更新V (s ) 。经过验证，该算
*法最终能够使得V (s ) →V (s ) 。具体证明值迭代算法收敛的过程可以参考文档
中的3-10部分。
有了V *，我们就能够通过公式得到π*。该算法可以使用同步更新和异步更新，效果差不多。 回到格子机器人的例子，我们最终算出和π*如下所示：
让我们用计算来说明，为什么在状态（3,1）中向左走更好？
向左走：
∑P
s , sa (s, ) V *(s, )
=0.8*0.75+0.1*0.69+0.1*0.71=0.74
向上走： ∑P s , sa (s, ) V *(s, ) =0.8*0.69+0.1*0.75+0.1*0.49=0.67计算结果显示：向左走的总回报期望更大。
Policy Interation
算法步骤：
1. 随机初始化策略π；
2. 重复以下步骤直至收敛 {
(a) 令V :=V π；其中V π通过求解贝尔曼方程（多个方程联立）得到；
(b) 对每个状态s ，更新π(s ) :=arg max a ∈A ∑P s , sa (s, ) V (s, )
}
算法步骤依然简洁。在比较两个算法的计算成本时候，因为policy iteration 需要求解n 个方程联立的问题（n 为状态数），所以可以这样选：在状态数较少的时候，选policy iteration ，反之选value iteration。
下面来着手解决一个可能的情况：假设MDP 中的五元组中我不知道{P sa }，如何处理呢？这种情况是常见的：当试图控制直升机的时候，你一开始并不知道直升机从初始状态过渡到什么状态或者在某一状态下采取的行动是什么，因为直升机整个系统很复杂，
往往不清楚会到
达什么状态。
这个时候，需要做的事情就是尝试从数据中估计出状态转移分布{P sa }，具体做法如下：
1#在状态s 采取行动a 时转变到状态s , 的次数0, ，则令P sa (s ) =） P sa (s ) =s #在状态s 采取行动a 时转变转变状态的总次数0,
在实际工作中，随着我们试验次数的增加或者对实验对象了解程度有所加深，我们不仅仅可以使用以上方法来估计{P sa }，还可以结合更多的先验知识（经验方法）。当奖励函数R 不清楚的时候，同样的思路可以让我们去估计在状态s 下的即时奖励R （s ）.
值得注意的是，在增强学习算法当中，面对不同的实际问题时，有很多时候是多种方法混合使用的。我们不需要拘泥于仅仅使用一种算法。
补充：
关于MDP 的代码实现，由于我正在学习java ，找到一个java 的算法库：
这是一个基于面向对象MDP （OO-MDP ）建立起来的框架，能够实现增强学习方面的很多算法。由于是英文的，需要一段时间来慢慢理解整个布局。当然，将其作为一个工具箱来使用时非常不错的，而且可以实现很酷的界面效果：
（格子游戏：穿越阻碍，到达设定目标点） （策略图显示）