系统学习机器学习之增强学习（三）--马尔可夫决策过程策略
DP求解及参数估计
1. 值迭代和策略迭代法
上节我们给出了迭代公式和优化⽬标，这节讨论两种求解有限状态MDP具体策略的有效算法。这⾥，我们只针对MDP是有限状态、有限动作的情况，。
* 值迭代法
1、 将每⼀个s的V(s)初始化为0
2、 循环直到收敛 {
对于每⼀个状态s，对V(s)做更新
}
值迭代策略利⽤了上节中公式（2）
内循环的实现有两种策略：
1、 同步迭代法
拿初始化后的第⼀次迭代来说吧，初始状态所有的V(s)都为0。然后对所有的s都计算新的V(s)=R(s)+0=R(s)。在计算每⼀个状态时，得到新的V(s)后，先存下来，不⽴即更新。待所有的s的新值V(s)都计算完毕后，再统⼀更新。
这样，第⼀次迭代后，V(s)=R(s)。
2、 异步迭代法
与同步迭代对应的就是异步迭代了，对每⼀个状态s，得到新的V(s)后，不存储，直接更新。这样，第⼀次迭代后，⼤部分V(s)>R(s)。
不管使⽤这两种的哪⼀种，最终V(s)会收敛到V*(s)。知道了V*后，我们再使⽤公式（3）来求出相应的最优策略，当然可以在求V*的过程中求出。
* 策略迭代法
值迭代法使V值收敛到V*，⽽策略迭代法关注，使收敛到。
1、 将随机指定⼀个S到A的映射。
2、 循环直到收敛 {
（a） 令
（b） 对于每⼀个状态s，对做更新
}
(a)步中的V可以通过之前的Bellman等式求得
这⼀步会求出所有状态s的。
(b)步实际上就是根据(a)步的结果挑选出当前状态s下，最优的a，然后对做更新。
对于值迭代和策略迭代很难说哪种⽅法好，哪种不好。对于规模⽐较⼩的MDP来说，策略⼀般能够更快地收敛。但是对于规模很⼤（状态很多）的MDP来说，值迭代⽐较容易（不⽤求线性⽅程组）。
2. MDP中的参数估计
在之前讨论的MDP中，我们是已知状态转移概率和回报函数R(s)的。但在很多实际问题中，这些参数不能显式得到，我们需要从数据中估计出这些参数（通常S、A和是已知的）。
假设我们已知很多条状态转移路径如下：
其中，是i时刻，第j条转移路径对应的状态，是状态时要执⾏的动作。每个转移路径中状态数是有限的，在实际操作过程中，每个转移链要么进⼊终结状态，要么达到规定的步数就会终结。
如果我们获得了很多上⾯类似的转移链（相当于有了样本），那么我们就可以使⽤最⼤似然估计来估计状态转移概率。
分⼦是从s状态执⾏动作a后到达s’的次数，分母是在状态s时，执⾏a的次数。两者相除就是在s状态下执⾏a后，会转移到s’的概率。
为了避免分母为0的情况，我们需要做平滑。如果分母为0，则令，也就是说当样本中没有出现过在s状态下执⾏a的样例时，我们认为转移概率均分。
上⾯这种估计⽅法是从历史数据中估计，这个公式同样适⽤于在线更新。⽐如我们新得到了⼀些转移路径，那么对上⾯的公式进⾏分⼦分母的修正（加上新得到的count）即可。修正过后，转移概率有所改变，按照改变后的概率，可能出现更多的新的转移路径，这样会越来越准。
同样，如果回报函数未知，那么我们认为R(s)为在s状态下已经观测到的回报均值。
当转移概率和回报函数估计出之后，我们可以使⽤值迭代或者策略迭代来解决MDP问题。⽐如，我们将参数估计和值迭代结合起来（在不知道状态转移概率情况下）的流程如下：
1、 随机初始化
2、 循环直到收敛 {
(a) 在样本上统计中每个状态转移次数，⽤来更新和R
(b) 使⽤估计到的参数来更新V（使⽤上节的值迭代⽅法）
(c) 根据更新的V来重新得出
}
在(b)步中我们要做值更新，也是⼀个循环迭代的过程，在上节中，我们通过将V初始化为0，然后进⾏迭代来求解V。嵌套到上⾯的过程后，如果每次初始化V为0，然后迭代更新，就会很慢。⼀个加快速度的⽅法是每次将V初始化为上⼀次⼤循环中得到的V。也就是说V的初值衔接了上次的结果。
3.连续状态的MDP
之前我们的状态都是离散的，如果状态是连续的，下⾯将⽤⼀个例⼦来予以说明，这个例⼦就是inverted pendulum问题，也就是⼀个铁轨⼩车上有⼀个长杆，要⽤计算机来让它保持平衡(其实就是我们平时玩杆⼦，放在⼿上让它⼀直保持竖直状态)，这个问题需要的状态有：都是real的值
x(在铁轨上的位置)
theta(杆的⾓度)
x’(铁轨上的速度)
thata'(⾓速度)
/离散化///
也就是把连续的值分成多个区间，这是很⾃然的⼀个想法，⽐如⼀个⼆维的连续区间可以分成如下的离散值：
但是这样做的效果并不好，因为⽤⼀个离散的去表⽰连续空间毕竟是有限的离散值。
离散值不好的另⼀个原因是因为curse of dimension(维度灾难)，因为连续值离散值后会有多个离散值，这样如果维度很⼤就会造成有⾮常多状态
从⽽使需要更多计算，这是随着dimension以指数增长的
//simulator⽅法///
也就是说假设我们有⼀个simulator，输⼊⼀个状态s和⼀个操作a可以输出下⼀个状态，并且下⼀个状态是服从MDP中的概率Psa的分布，即：
这样我们就把状态变成连续的了，但是如何得到这样⼀个simulator呢？
①：根据客观事实
⽐如说上⾯的inverted pendulum问题，action就是作⽤在⼩车上的⽔平⼒，根据物理上的知识，完全可以解出这个加速度对状态的影响也就是算出该⼒对于⼩车的⽔平加速度和杆的⾓加速度，再去⼀个⽐较⼩的时间间隔，就可以得到S(t+1)了
②：学习⼀个simulator
这个部分，⾸先你可以⾃⼰尝试控制⼩车，得到⼀系列的数据，假设⼒是线性的或者⾮线性的，将S(t+1)看作关于S(t)和a(t)的⼀个函数
得到这些数据之后，你可以通过⼀个supervised learning来得到这个函数，其实就是得到了simulator了。
⽐如我们假设这是⼀个线性的函数：
在inverted pendulum问题中，A就是⼀个4*4的矩阵，B就是⼀个4维向量，再加上⼀点噪⾳，就变成了：其中噪⾳服从
我们的任务就是要学习到A和B
(这⾥只是假设线性的，更具体的，如果我们假设是⾮线性的，⽐如说加⼀个feature是速度和⾓速度的乘积，或者平⽅，或者其他，上式还可以写作：)
这样就是⾮线性的了，我们的任务就是得到A和B，⽤⼀个supervised learning分别拟合每个参数就可以了
4.连续状态中得Value(Q)函数
这⾥介绍了⼀个fitted value(Q) iteration的算法
在之前我们的value iteration算法中，我们有：
这⾥使⽤了期望的定义⽽转化。fitted value(Q) iteration算法的主要思想就是⽤⼀个参数去逼近右边的这个式⼦
也就是说：令
其中是⼀些基于s的参数，我们需要去得到系数的值，先给出算法步骤再⼀步步解释吧：
算法步骤其实很简单，最主要的其实就是他的思想：
在对于action的那个循环⾥，我们尝试得到这个action所对应的，记作q(a)
这⾥的q(a)都是对应第i个样例的情况
然后i=1……m的那个循环是得到是最优的action对应的Value值，记作y(i)，然后⽤y(i)拿去做supervised learning，⼤概就是这样⼀个思路
⾄于reward函数就⽐较简单了，⽐如说在inverted pendulum问题中，杆⼦⽐较直⽴就是给⾼reward，这个可以很直观地从状态得到衡量奖励的⽅法
在有了之上的东西之后，我们就可以去算我们的policy了：
5.确定性的模型
上⾯讲的连续状态的算法其实是针对⼀个⾮确定性的模型，即⼀个动作可能到达多个状态，有P在影响到达哪个状态
如果在⼀个确定性模型中，其实是⼀个简化的问题，得到的样例简化了，计算也简化了
也就是说⼀个对于⼀个状态和⼀个动作，只能到达另⼀个状态，⽽不是多个，特例就不细讲了
6.控制MDP算法
前⾯重点讲的都是每个状态有个明确的奖励，并且没有时间的限制。但是在这⾥开始，我们的策略是有时间限制的，因此，我们的奖励最⼤值的计算，在到达时间T的时候就已经终结了。
开始讲了如何求解含有T时间的策略⽅程。知道V*（T）是容易的，然后通过逆推的动态规划函数就可以解出。但是，有时间的策略⽅程，因为是有关于st和s(t+1)之间关系的，因此，也需要进⾏线性拟合，这个在之前已经讲过，这⾥不再赘述。有s(t+1)=As(t)+Balpha(t)。但是，这⾥的逆推在⼀些特殊情况下将会有⾮常⾼的效率。
实际上，就是假设：
，其中噪声项服从⾼斯分布，不是很重要。
但同时假设了边界时间，⼆次奖励函数。
7.动态规划
上⼀篇我们已经说到了，增强学习的⽬的就是求解马尔可夫决策过程(MDP)的最优策略，使其在任意初始状态下，都能获得最⼤的Vπ值。(本⽂不考虑⾮马尔可夫环境和不完全可观测马尔可夫决策过程(POMDP)中的增强学习)。
那么如何求解最优策略呢？基本的解法有三种：
动态规划法(dynamic programming methods)
蒙特卡罗⽅法(Monte Carlo methods)
时间差分法(temporal difference)。
动态规划法是其中最基本的算法，也是理解后续算法的基础，因此本⽂先介绍动态规划法求解MDP。
本⽂假设拥有MDP模型M=(S, A, Psa, R)的完整知识。
1. 贝尔曼⽅程（Bellman Equation）
上⼀篇我们得到了Vπ和Qπ的表达式，并且写成了如下的形式
在动态规划中，上⾯两个式⼦称为贝尔曼⽅程，它表明了当前状态的值函数与下个状态的值函数的关系。
优化⽬标π*可以表⽰为：
分别记最优策略π*对应的状态值函数和⾏为值函数为V*(s)和Q*(s, a)，由它们的定义容易知道，V*(s)和Q*(s, a)存在如下关系:
状态值函数和⾏为值函数分别满⾜如下贝尔曼最优性⽅程(Bellman optimality equation)：
有了贝尔曼⽅程和贝尔曼最优性⽅程后，我们就可以⽤动态规划来求解MDP了。
2. 策略估计(Policy Evaluation)
⾸先，对于任意的策略π，我们如何计算其状态值函数Vπ(s)？这个问题被称作策略估计，
前⾯讲到对于确定性策略，值函数
现在扩展到更⼀般的情况，如果在某策略π下，π(s)对应的动作a有多种可能，每种可能记为π(a|s)，则状态值函数定义如下：
⼀般采⽤迭代的⽅法更新状态值函数，⾸先将所有Vπ(s)的初值赋为0（其他状态也可以赋为任意值，不过吸收态必须赋0值），然后采⽤如下式⼦更新所有状态s的值函数（第k+1次迭代）：
对于Vπ(s)，有两种更新⽅法，
第⼀种：将第k次迭代的各状态值函数[Vk(s1),Vk(s2),Vk(s3)..]保存在⼀个数组中，第k+1次的Vπ(s)采⽤第k次的Vπ(s')来计算，并将结果保存在第⼆个数组中。s parameter
第⼆种：即仅⽤⼀个数组保存各状态值函数，每当得到⼀个新值，就将旧的值覆盖，形如[Vk+1(s1),Vk+1(s2),Vk(s3)..]，第k+1次迭代的Vπ(s)可能⽤到第k+1次迭代得到的Vπ(s')。
通常情况下，我们采⽤第⼆种⽅法更新数据，因为它及时利⽤了新值，能更快的收敛。整个策略估计算法如下图所⽰：
3. 策略改进(Policy Improvement)
上⼀节中进⾏策略估计的⽬的，是为了寻更好的策略，这个过程叫做策略改进(Policy Improvement)。
假设我们有⼀个策略π，并且确定了它的所有状态的值函数Vπ(s)。对于某状态s，有动作a0=π(s)。 那么如果我们在状态s下不采⽤动作a0，⽽采⽤其他动作a≠π(s)是否会更好呢？要判断好坏就需要我们计算⾏为值函数Qπ(s,a)，公式我们前⾯已经说过：
评判标准是：Qπ(s,a)是否⼤于Vπ(s)。如果Qπ(s,a)> Vπ(s)，那么⾄少说明新策略【仅在状态s下采⽤动作a，其他状态下遵循策略π】⽐旧策略【所有状态下都遵循策略π】整体上要更好。
策略改进定理(policy improvement theorem)：π和π'是两个确定的策略，如果对所有状态s∈S有Qπ(s,π'(s))≥Vπ(s)，那么策略
π'必然⽐策略π更好，或者⾄少⼀样好。其中的不等式等价于Vπ'(s)≥Vπ(s)。
有了在某状态s上改进策略的⽅法和策略改进定理，我们可以遍历所有状态和所有可能的动作a，并采⽤贪⼼策略来获得新策略π'。即对所有的s∈S, 采⽤下式更新策略：
这种采⽤关于值函数的贪⼼策略获得新策略，改进旧策略的过程，称为策略改进(Policy Improvement)
最后⼤家可能会疑惑，贪⼼策略能否收敛到最优策略，这⾥我们假设策略改进过程已经收敛，即对所有的s，Vπ'(s)等于Vπ(s)。那么根据上⾯的策略更新的式⼦，可以知道对于所有的s∈S下式成⽴：
可是这个式⼦正好就是我们在1中所说的Bellman optimality equation，所以π和π'都必然是最优策略！神奇吧！
4. 策略迭代(Policy Iteration)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。