增强学习（ReinforcementLearningandControl.pdfVIP

增强学习（Reinforcement Learning and Control） JerryLead@ISCAS csxulijie@ 2011 年 5 月 13日 来自 Andrew Ng Machine Learning讲义 在之前的讨论中，我们总是给定一个样本 x，然后给或者不给 label y。之后对样本进行 拟合、分类、聚类或者降维等操作。然而对于很多序列决策或者控制问题，很难有这么规则 的样本。比如，四足机器人的控制问题，刚开始都不知道应该让其动那条腿，在移动过程中， 也不知道怎么让机器人自动找到合适的前进方向。 另外如要设计一个下象棋的 AI，每走一步实际上也是一个决策过程，虽然对于简单的 棋有 A*的启发式方法，但在局势复杂时，仍然要让机器向后面多考虑几步后才能决定走哪 一步比较好，因此需要更好的决策方法。 对于这种控制决策问题，有这么一种解决思路。我们设计一个回报函数（reward function）， 如果 learning agent（如上面的四足机器人、象棋 AI程序）在决定一步后，获得了较好的结 果，那么我们给 agent 一些回报（比如回报函数结果为正），得到较差的结果，那么回报函 数为负。比如，四足机器人，如果他向前走了一步（接近目标），那么回报函数为正，后退 为负。如果我们能够对每一步进行评价，得到相应的回报函数，那么就好办了，我们只需要 找到一条回报值最大的路径（每步的回报之和最大），就认为是最佳的路径。 增强学习在很多领域已经获得成功应用，比如自动直升机，机器人控制，手机网络路由， 市场决策，工业控制，高效网页索引等。 接下来，先介绍一下马尔科夫决策过程（MDP，Markov decision processes）。 1. 马尔科夫决策过程 一个马尔科夫决策过程由一个五元组构成(S, A, *??????+, ??, ??) ? S 表示状态集（states）。（比如，在自动直升机系统中，直升机当前位置坐标组成状态 集） ? A 表示一组动作（actions）。（比如，使用控制杆操纵的直升机飞行方向，让其向前，向 后等） ? ??????是状态转移概率。S 中的一个状态到另一个状态的转变，需要 A 来参与。??????表示的 是在当前s ∈ S状态下，经过a ∈ A作用后，会转移到的其他状态的概率分布情况（当前 状态执行 a后可能跳转到很多状态）。 ? ?? ∈ ,0,1)是阻尼系数（discount factor） ? R: S × A ? ?，R 是回报函数（reward function），回报函数经常写作 S 的函数（只与 S 有关），这样的话，R 重新写作R: S ? ?。 MDP 的动态过程如下：某个 agent 的初始状态为??0，然后从 A中挑选一个动作??0执行， 执行后，agent 按??????概率随机转移到了下一个??1状态，??1 ∈ ????0??0。然后再执行一个动作??1， 就转移到了??2，接下来再执行??2…，我们可以用下面的图表示整个过程 如果对 HMM 有了解的话，理解起来比较轻松。 我们定义经过上面转移路径后，得到的回报函数之和如下 如果 R 只和 S 有关，那么上式可以写作 我们的目标是选择一组最佳的 action，使得全部的回报加权和期望最大。 从上式可以发现，在 t 时刻的回报值被打了????的折扣，是一个逐步衰减的过程，越靠后 的状态对回报和影响越小。最大化期望值也就是要将大的R(????)尽量放到前面，小的尽量放 到后面。 已经处于某个状态 s 时，我们会以一定策略π来选择下一个动作 a 执行，然后转换到另 一个状态 s’。我们将这个动作的选择过程称为策略（policy），每一个 policy其实就是一个状 态到动作的映射函数π ∶ S ? A。给定π也就给定了a = π(s)，也就是说，知道了π就知道了 每个状态下一步应该执行的动作。 我们为了区分不同π的好坏，并定义在当前状态下，执行某个策略π后，出现的结果的 好坏，需要定义值函数（value function）也叫折算累积回报（discounted cumulative reward） 可以看到，在当前状态 s下，选择好 policy后，值函数是回报加权和期望。这个其实很 容易理解，给定π也就给定了一条未来的行动方案，这个行动方案会经过一个个的状态，而 到达每个状态都会有一定回报值，距离当前状态越近的其他状态对方案的影响越大，权重越 高。这和下象棋差不多，在当前棋局s0下，不同的走子方案是π，我们评价每个方案依靠对 未来局势（R(s1), R(s2),…）的判断。一般情况下，我们会在头脑中多