第⼗⼆讲：强化学习（ReinforcementLearning ）和控制（Control ）
这⼀章我们就要学习强化学习（reinforcement learning）和适应性控制（adaptive control）了。
在监督学习（supervised learning）中，我们已经见过的⼀些算法，输出的标签类 都是在训练集中已经存在的。这种情况下，对于每个输⼊特征 ，都有⼀个对应的标签作为明确的“正确答案（right answer）”。与之相反，在很多的连续判断（sequential decisions making）和控制（control）的问题中，很难提供这样的明确的显⽰监督（explicit supervision）给学习算法。例如，假设咱们制作了⼀个四条腿的机器⼈，然后要编程让它能⾛路，⽽我们并不知道怎么去采取“正确”的动作来进⾏四条腿的⾏⾛，所以就不能给他提供⼀个明确的监督学习算法来进⾏模仿。在强化学习（reinforcement learning）的框架下，我们就并不提供监督学习中那种具体的动作⽅法，⽽是只给出⼀个奖励函数（reward function），这个函数会告知学习程序（learning agent） 什么时候的动作是好的，什么时候的是不好的。在四腿机器⼈这个样例中，奖励函数会在机器⼈有进步的时候给出正⾯回馈，即奖励，⽽有退步或者摔倒的时候给出负⾯回馈，可以理解成惩罚。接下来随着时间的推演，学习算法就会解决如何选择正确动作以得到最⼤奖励。电视定制
强化学习（Reinforcement learning，下⽂中缩写为 RL）已经成功⽤于多种场景了，例如⽆⼈直升机的⾃主飞⾏，机器⼈⽤腿来运动，⼿机的⽹络选择，市场营销策略筛选，⼯⼚控制，⾼效率的⽹页索引等
等。我们对强化学习的探索，要先从马尔可夫决策过程（Markov decision processes，缩写为 MDP）开始，这个概念给出了强化学习问题的常见形式。
1 马尔可夫决策过程（Markov decision processes ）
⼀个马尔可夫决策过程（Markov decision process）由⼀个元组（tuple）： 组成，其中元素分别为：
1. 是⼀个状态集合（a set of states）。（例如，在⽆⼈直升机飞⾏的案例中， 就可以是直升机所有的位置和⽅向的集合。） 2. 是⼀个动作集合（a set of actions）。（例如，还以⽆⼈直升机为例， 就可以是遥控器上⾯能够操作的所有动作⽅向。）
3. 为状态转移概率（state transition probabilities）。对于每个状态 和动作 ， 是在状态空间上的⼀个分布（a distribution over the state space）。后⾯会再详细讲解，不过简单来说， 给出的是在状态 下进⾏⼀个动作 ⽽要转移到的状态的分布。
4. 叫做折扣因⼦（discount factor）。
5. 就是奖励函数（reward function）。（奖励函数也可以写成仅对状态 S 的函数，这样就可以写成 。）马尔可夫决策过程（MDP）的动⼒学（dynamics）过程如下所⽰：于某个起始状态 启动，然后选择某个动作 来执⾏ MDP 过程。根据所选的动作会有对应的结果，MDP 的状态则转移到某个后继状态（successor state），表⽰为 ，根据 得到。然后再选择另外⼀个动作 ，接下来⼜有对应这个动作的状态转移，状态则为 。接下来在选择⼀个动作 ，就这样进⾏下去。可以⽤下⾯的过程来作为表⽰：
通过序列中的所有状态 和对应的动作 ，就你能得到给出的总奖励值，即总收益函数（total payoff）为
如果把奖励函数只作为仅与状态相关的函数，那么这个值就简化成了
多数情况下，我们都⽤后⾯这种仅为状态的函数这种形式，虽然扩展到对应状态-动作两个变量的函数 也并不难。强化学习的⽬标就是到的⼀组动作，能使得总收益函数（total payoff）的期望值最⼤：
y x (S ,A ,P ,γ,R )sa S S A A P sa s ∈S a ∈A P sa P sa s a γ∈[0,1]R :S ×A →R R :S →R s 0a ∈0A s 1s 1∼P s a 00a 1s ∼2P s a 11a 2s s s s …
0a 01a 12a 23a 3s ,s ,...01a ,a ,...01R (s ,a )+00γR (s ,a )+11γR (s ,a )+⋅⋅⋅
222R (s )+0γR (s )+1γR (s )+⋅⋅⋅
22R (s ,a )E [R (s )+0γR (s )+1γR (s )+⋅⋅⋅]
22
注意，在时间步长（timestep） 上的奖励函数（reward）通过⼀个参数（factor）⽽进⾏了缩减（discounted）。因此，要使得期望最⼤化，就需要尽可能早积累符号为正的奖励（positive rewards），⽽尽量推迟负⾯奖励（negative rewards，即惩罚）的出现。在经济⽅⾯的应⽤中，其中的 就是盈利⾦额（amount of money made）， 也可以理解为利润率（interest rate）的表征，这样有⾃然的解释（natural interpretation），例如今天的⼀美元就⽐明天的⼀美元有更多价值。
有⼀种策略（policy），是使⽤任意函数 ，从状态（states）到动作（actions）进⾏映射（mapping）。如果在状态 ，采取动作 ，就可以说正在执⾏（executing）某种策略（policy） 。然后还可以针对策略函数（policy） 来定义⼀个值函数（value function）：
就是从状态 开始，根据 给出的动作来积累的部分奖励函数（discounted rewards）的期望总和（expected sum）。给定⼀个固定的策略函数（policy），则对应的值函数 满⾜贝尔曼⽅程（Bellman equations）：
这也就意味着，从状态 开始的这个部分奖励（discounted rewards）的期望总和（expected sum） 由两部分组成：⾸先是在状态 时候当时⽴即获得的奖励函数值 ，也就是上⾯式⼦的第⼀项；另⼀个就是第⼆项，即后续的部分奖励函数值（discounted rewards）的期望总和（expected sum）。对第⼆项进⾏更深⼊的探索，就能发现这个求和项（summation term）可以写成水质快速检测
的形式。这种形式也就是从状态 开始的这个部分奖励（discounted rewards）的期望总和（expected sum） ，此处的 是根据 分布的，在 MDP 过程中从状态 s 采取第⼀个动作 之后，确定了这个分布所在的空间。因此，上⾯的第⼆项实际上也就是给出了在 MDP 过程中第⼀步之后的部分奖励（discounted rewards）的期望总和（expected sum）。
贝尔曼等式（Bellman’s equations）可以有效地解出 。尤其是在⼀个有限状态的 MDP 过程中，即 ()，我们可以把每个状态 对应的 的⽅程写出来。这样就得到了⼀系列的 个线性⽅程，有 个变量（也就是对应每个状态的未知的 ），这些 都很容易解出来。
然后可以定义出最优值函数（optimal value function）
换⼀种说法，这个值也就是能⽤任意⼀种策略函数（policy）来获得的，最佳的可能折扣奖励（discounted rewards）的期望总和（expected sum）。另外对于最优值函数（optimal value function），也有⼀个版本的贝尔曼等式（Bellman’s equations）：
上⾯这个等式中的第⼀项，还是跟之前⼀样的，还是即时奖励函数值。第⼆项是在采取了动作 之后的所有动作 的部分奖励
（discounted rewards）的未来期望总和（expected future sum）的最⼤值。要确保理解这个等式，并且要明⽩为什么这个等式有意义。
另外还定义了⼀个策略函数（policy） ，如下所⽰：
注意，这⾥的 给出的动作 给出的在上⾯等式（2）当中能够使 项取最⼤值。
对于每个状态 和每个策略函数（policy），都有：
t γt R (⋅)γπ:S →A s a =π(s )ππV (s )=E [R (s )+γR (s )+γR (s )+⋅⋅⋅∣s =s ,π].
π01220V (s )πs ππV πs V (s )πs R (s )E [V π(s )]s ′∼P s π(s )′s ′V (s )π′s ′P s π(s )π(s )V π∣S ∣<∞s V (s )π∣S ∣∣S ∣V (s )πV (s )πV (s )=V (s )∗πmax π(1)
V (s )=R (s )+γP (s )V (s )∗a ∈A max s ∈S ′∑sa ′∗′(2)
a a π:∗S →A π(s )=arg P (s )V (s )∗a ∈A max s ∈S ′∑sa ′∗′(3)
π(s )∗a “max ”s π
上⾯的第⼀个等式关系表明，对应策略函数（policy） 的值函数（value function） 等于对于每个状态 的最优值函数 。右边的不等式则表明， 的值⾄少也等于任意其他策略函数的值。也就是说，上⾯在等式（3）当中定义的这个 就是最佳策略函数（optimal policy）。
注意，这个 有⼀个有趣的特性，它是所有状态 下的最佳策略。具体来讲，并不是说只是如果从某个状态 开始 MDP 过程，这个 是对应这个状态的最佳策略，⽽如果从某个别的状态 开始就有其他的最佳策略。⽽是对于所有的状态 ，都是同样的⼀个策略函数 能够使得等式（1）中的项⽬取得最⼤值。这也就意味着⽆论 MDP 过程的初始状态（initial state）如何，都可以使⽤同样的策略函数 。2 值迭代（Value iteration ）和策略迭代（policy iteration ）
现在我们要讲两种算法，都能很有效地解决有限状态的马尔可夫决策过程问题（finite-state MDPs）。⽬前为⽌，我们只考虑有限状态和动作空间的马尔可夫决策过程，也就是状态和动作的个数都是有限的，即。
第⼀种算法，值迭代（value iteration），过程如下所述：
1. 对每个状态 , 初始化 .
2. 重复直到收敛 {
对每个状态，更新规则：
}
这个算法可以理解成，利⽤贝尔曼等式（Bellman Equations）（2）重复更新估计值函数（estimated value function）。
在上⾯的算法的内部循环体中，有两种进⾏更新的⽅法。⾸先，我们可以为每⼀个状态 计算新的值 ，然后⽤新的值覆盖掉所有的旧值。这也叫做同步更新（synchronous update）。在这种情况下，此算法可以看做是实现（implementing）了⼀个“贝尔曼备份运算符（Bellman backup operator）”，这个运算符接收值函数（value function）的当前估计（current estimate），然后映射到⼀个新的估计值（estimate）。（更多细节参考作业题⽬中的内容。）
另外⼀种⽅法，就可以使⽤异步更新（asynchronous updates）。使⽤这种⽅法，就可以按照某种次序来遍历（loop over）所有的状态，然后每次更新其中⼀个的值。
⽆论是同步还是异步的更新，都能发现最终值迭代（value iteration）会使 $V 收敛到 。到了 之后，就可以利⽤等式（3）来到最佳策略（optimal policy）。
除了值迭代（value iteration）之外，还有另外⼀种标准算法可以⽤来在马尔可夫决策过程（MDP）中寻⼀个最佳策略（optimal policy）。这个策略循环（policy iteration）算法如下所述：
1. 随机初始化 。
2. 重复直到收敛{
(a) 令 .
(b) 对每个状态 s，令
}
因此，在循环体内部就重复计算对于当前策略（current policy）的值函数（value function），然后使⽤当前的值函数（value
function）来更新策略函数（policy）。（在步骤 b 中到的策略 也被称为对应 的贪⼼策略（greedy with respect to V）。）注意，步骤 a 可以通过解贝尔曼等式（Bellman’s equation）来实现，之前已经说过了，在固定策略（fixed policy）的情况下，这个等式只是⼀系列有 个变量（variables）的 个线性⽅程（linear equations）。
在上⾯的算法迭代了某个最⼤迭代次数之后， 将会收敛到 ，⽽ 会收敛到 。
V (s )=V (s )≥V (s ).∗π∗
ππ∗V π∗s V ∗π∗π∗π∗s s π∗s ′s π∗π∗∣S ∣<∞,∣A ∣<∞s V (s ):=0V (s ):=R (s )+max γP (s )V (s )
a ∈A ∑s ′sa ′′s V (s )V ∗V ∗πV :=V ππ(s ):=arg max P (s )V (s ).
a ∈A ∑s ′sa ′′πV ∣S ∣∣S ∣V V ∗ππ∗
值迭代（value iteration）和策略迭代（policy iteration）都是解决马尔可夫决策过程（MDPs）问题的标准算法， ⽽且⽬前对于这两个算法哪个更好，还没有⼀个统⼀的⼀致意见。对⼩规模的 MDPs 来说，策略迭代（policy iteration）通常⾮常快，迭代很少的次数就能瘦脸。然⽽，对有⼤规模状态空间的 MDPs，确切求解 就要涉及到求解⼀个⾮常⼤的线性⽅程组系统，可能⾮常困难。对于这种问题，就可以更倾向于选择值迭代（value iteration）。因此，在实际使⽤中，值迭代（value iteration）通常⽐策略迭代（policy iteration）更加常⽤。
3 学习⼀个马尔可夫决策过程模型（Learning a model for an MDP ）
⽬前为⽌，我们已经讲了 MDPs，以及⽤于 MDPs 的⼀些算法，这都是基于⼀个假设，即状态转移概率（state transition
probabilities）以及奖励函数（rewards）都是已知的。在很多现实问题中，却未必知道这两样，⽽是必须从数据中对其进⾏估计。（通常 ， 和 都是知道的。）
例如，加⼊对倒⽴摆问题（inverted pendulum problem，参考习题集 4），在 MDP 中进⾏了⼀系列的试验，过程如下所⽰：
其中 表⽰的是第 次试验中第 次的状态，⽽ 是该状态下的对应动作。在实践中，每个试验都会运⾏到 MDP 过程停⽌（例如在倒⽴摆问题（inverted pendulum problem）中杆落下（pole falls）），或者会运⾏到某个⼤但有限个数的时间步长（timesteps）。有了在 MDP 中⼀系列试验得到的“经验”，就可以对状态转移概率（state transition probabilities）推导出最⼤似然估计（maximum likelihood estimates）了：
或者，如果上⾯这个⽐例出现了 的情况，对应的情况就是在状态 之前没进⾏过任何动作 ，这样就可以简单估计 为 。（也就是说把 估计为在所有状态上的均匀分布（uniform distribution）。）
注意，如果在 MDP 过程中我们能获得更多经验信息（观察更多次数），就能利⽤新经验来更新估计的状态转移概率（estimated state transition probabilities），这样很有效率。具体来说，如果我们保存下来等式（4）中的分⼦（numerator）和分母（denominator）的计数（counts），那么观察到更多的试验的时候，就可以很简单地累积（accumulating）这些计数数值。计算这些数值的⽐例，就能
够给出对 的估计。
利⽤类似的程序（procedure），如果奖励函数（reward） 未知，我们也可以选择在状态 下的期望即时奖励函数（expected immediate reward） R(s) 来当做是在状态 观测到的平均奖励函数（average reward）。
学习了⼀个 MDP 模型之后，我们可以使⽤值迭代（value iteration）或者策略迭代（policy iteration），利⽤估计的状态转移概率（transition probabilities）和奖励函数，来去求解这个 MDP 问题。例如，结合模型学习（model learning）和值迭代（value iteration），就可以在未知状态转移概率（state transition probabilities）的情况下对 MDP 进⾏学习，下⾯就是⼀种可⾏的算法：
1. 随机初始化 π 。
2. 重复 {
（a） 在 MDP 中执⾏ 作为若⼲次试验（trials）。
（b）利⽤上⾯在 MDP 积累的经验（accumulated experience），更新对 的估计（如果可以的话也对奖励函数 R 进⾏更
新）。
（c）利⽤估计的状态转移概率（estimated state transition probabilities）和奖励函数（rewards），应⽤值迭代（value智能抄表
iteration），得到⼀个新的估计值函数（estimated value function） 。
（d） 更新 为与 对应的贪婪策略（greedy policy）。
}
印刷制版机V πS A γs s s s …0(1)a 0(1)
1(1)a 1(1)2(1)a 2(1)3(1)a 3(1)s s s s …0(2)a 0(2)1(2)a 1(2)2(2)a 2(2)3
滑动水口
(2)a 3(2)…
s i (j )j i a i (j )P (s )=sa ′# times we took action a in state s # times took we action a in state s and got to s ′
(4)
“0/0”s a P (s )sa ′1/∣S ∣P sa P sa R s s πP sa V πV
我们注意到，对于这个特定的算法，有⼀种简单的优化⽅法（optimization），可以让该算法运⾏得更快。具体来说，在上⾯算法的内部循环中，使⽤了值迭代（value iteration），如果初始化迭代的时候不令 启动，⽽是使⽤算法中上⼀次迭代到的解来初始化，这样就有了⼀个更好的迭代起点，能让算法更快收敛。
4 连续状态的马尔可夫决策过程（Continuous state MDPs ）
⽬前为⽌，我们关注的都是有限个状态（a finite number of states）的马尔可夫决策过程（MDPs）。接下来我们要讲的就是有⽆限个状
态（an infinite number of states）的情况下的算法。例如，对于⼀辆车，我们可以将其状态表⽰为 ，其中包括位置（position） ，⽅向（orientation）， 在 和 ⽅向的速度分量 和 ，以及⾓速度（angular velocity）。这样， 就是⼀个有⽆限的状态集合，因为⼀辆车的位置和⽅向的个数是有⽆限可能的 。与此相似，在习题集4 中看到的倒⽴摆问题（inverted pendulum）中，状态也有 ，其中的 是杆的⾓度。在直升机飞⾏的三维空间中，状态的形式则为 ，其中包含了滚动⾓（roll），俯仰⾓（pitch），以及偏航⾓（yaw），这⼏个⾓度确定了直升机在三维空间中的运动⽅向。在本节中，我们考虑状态空间为 的情况，并描述此种情况下解决 MDPs 的⽅法。
4.1 离散化（Discretization ）
解决连续状态 MDP 问题最简单的⽅法可能就是将状态空间（state space）离散化（discretize），然后再使⽤之前讲过的算法，⽐如值迭代（value iteration）或者策略迭代（policy iteration）来求解。
例如，假设我们有⼀个⼆维状态空间，就可以⽤下⾯的⽹格（grid）来将这个状态空间离散化：
如上图所⽰，每个⽹格单元（grid cell）表⽰的都是⼀个独⽴的离散状态 。这样就可以把⼀个连续状态 MDP ⽤⼀个离散状态的 来进⾏逼近，其中的 是离散状态集合，⽽ 是此离散状态上的状态转移概率（state transition
probabilities），其他项⽬同理。然后就可以使⽤值迭代（value iteration）或者策略迭代（policy iteration）来求解出离散状态的 MDP 的 和 。当真实系统是某种连续值的状态 ，⽽有需要选择某个动作来执⾏，就可以计算对应的离散化的状态 ，然后执⾏对应的动作 。
这种离散化⽅法（discretization approach）可以解决很多问题。然⽽，也有两个缺陷（downsides）。⾸先，这种⽅法使⽤了对 和 相当粗糙的表征⽅法。具体来说，这种⽅法中假设了在每个离散间隔（discretization intervals）中的值函数（value function）都去⼀个常数值（也就是说，值函数是在每个⽹格单元中分段的常数。）。
要更好理解这样表征的的局限性，可以考虑对下⾯这⼀数据集进⾏函数拟合的监督学习问题：
很明显，上⾯这个数据适合使⽤线性回归。然⽽，如果我们对 轴进⾏离散化，那么在每个离散间隔中使⽤分段常数表⽰，对同样的数据进⾏拟合，得到的曲线则如下所⽰：
这种分段常数表⽰，对于很多的光滑函数，都不能算好。这会导致输⼊值缺乏平滑（little smoothing over the inputs），⽽且在不同的望各单元中间也没有进⾏扩展（generalization）。使⽤这种表⽰⽅法，我们还需要⼀种⾮常精细的离散化过程（也就是⽹格单元要⾮常⼩），才能得到⼀个⽐较好的近似估计。
第⼆个缺陷可以称之为维度的诅咒（curse of dimensionality）。设 ，然后我们队每个 维度状态离散成 个值。这样总共的离散状态的个数就是 。在状态空间 的维度中，这个值会呈指数级增长，对于⼤规模问题就不好缩放了。例如，对于⼀个 10 维的状态，如果我们把每个状态变量离散化成为 100 个值，那么就会有 个离散状态，这个维度太⼤了，远远超过了当前桌⾯电脑能应付的能⼒之外。
根据经验法则（rule of thumb），离散化通常⾮常适合⽤于 1 维和 2 维的问题（⽽且有着简单和易于快速实现的优势）。对于 4 维状态的问题，如果使⽤⼀点⼩聪明，仔细挑选离散化⽅法，有时候效果也不错。如果你超级聪明，并且还得有点幸运，甚⾄也有可能将离散化⽅法使⽤于 6 维问题。不过在更⾼维度的问题中，就更是极其难以使⽤这种⽅法了。
4.2 值函数近似（Value function approximation ）电磁大锅灶
现在我们来讲另外⼀种⽅法，能⽤于在连续状态的 MDPs 问题中出策略，这种⽅法也就是直接对进⾏近似 ，⽽不使⽤离散化。这个⽅法就叫做值函数近似（value function approximation），在很多强化学习的问题中都有成功的应⽤。V =0(x ,y ,θ,,,)x ˙y
˙θ˙(x ,y )θx y x ˙y
˙θ˙S =R 6(x ,θ,,)x ˙θ˙θ(x ,y ,z ,ϕ,θ,ψ,,,,,,)x ˙y ˙z ˙ϕ
˙θ˙ψ˙ϕθψS =R n （s ，s ）12s ˉ(,A ,{P },γ,R )S a s S {P }a s (,A ,{P },γ,R )S a s V ()∗s π()∗s s ∈S s π()∗s V ∗π∗x S =R n n k k n n 100=101020V ∗
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议