第十六章 强化学习

• 任务与奖赏
• K-摇臂赌博机
• e-贪心
• Softmax
• 有模型学习
• • 策略评估
  • 策略改进
  • 策略迭代与值迭代
• 免模型学习
• • 蒙特卡罗强化学习
  • 时序差分学习
  • 值函数近似
  • 模仿学习

任务与奖赏

种瓜有许多步骤，但在种瓜的过程中，某些操作并不能立即得到最终奖励，只能得到一个当前反馈（例如瓜苗看起来更健壮了），我们需要不断摸索，才能总结出较好的种瓜策略，这个过程就是强化学习。

强化学习任务通常用马尔可夫决策过程 (Markov Decision Process，简称 MDP)来描述：机器处于环境E中，状态空间为X，其中每个状态 x∈X 是机器感知到的环境的描述，如在种瓜任务上这就是当前瓜苗长势的描述；机器能采取的动作构成了动作空间A，如种瓜过程中有浇水、施不同的肥、使用不同的农药等多种可供选择的动作；若某个动作 α∈A 作用在当前状态 x，则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态，如瓜苗状态为缺水，若选择动作浇水，则瓜苗长
势会发生变化，瓜苗有一定的概率恢复健康，也有一定的概率无法恢复；在转移到另一个状态的同时，环境会根据潜在的"奖赏" (reward) 函数R反馈给机器一个奖赏，如保持瓜苗健康对应奖赏 +1 ，瓜茵凋零对应奖赏一10 ，最终种出了好瓜对应奖赏 +100。 综合起来，强化学习任务对应了四元组 = (X,A,P,R), 其中 P：XAX →P指定了状态转移概率 ，R：XAX →R指定了奖赏；在有的应用中，奖赏函数可能仅与状态转移有关，即 R:X*X →R。其中在环境中状态的转移与奖赏的返回是不受机器控制的。机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。
一个简单的例子

机器要做的是通过在环境中不断地尝试而学得一个"策略" (policy) π，根据这个策略，在状态x下就能得知要执行的动作 a= (x) ，例如看到瓜苗状态是缺水时，能返回动作"浇水"策略有两种表示方法：二种是将策略表示为函数π :X →A，确定性策略常用这种表示；另一种是概率表示汀 ：X*A →R，随机性策略常用这种表示。π(x，a) 为状态 x下选择动作a的概率。

在强化学习任务中，学习的目的就是要找到能使长期累积奖赏最大化的策略。常用的奖励累计奖赏有“T步累积奖赏”。

K-摇臂赌博机

仅考虑异步操作，最大化单步奖赏。则需要知道每个动作带来的奖赏，然后执行奖赏最大的动作。然而，更一般的情形是，一个动作的奖赏值是来自于一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值。

单步强化学习任务对应了一个理论模型，即 K-摇臂赌博机 (K-armed bandit). K-摇臂赌博机有 个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币.

仅探索：将所有的尝试机会平均分配给每个摇臂(即轮流按下每个摇臂)，最后以每个摇臂各自的平均吐币橄率作为其奖赏期望的近似估计。
仅利用：:按下目前最优的(即到目前为止平均奖赏最大的)摇臂，若有多个摇臂同为最优，则从中随机选取一个。
“探索” 和"利用" 这两者是矛盾的，因为尝试次数(即总投币数)有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的探索-利用窘境。

e-贪心

e-贪心：基于一个概率来对探索和利用进行折中:每次尝试时，以e的概率进行探索，即以均匀概率随机选取一个摇臂；以 1-e的概率进行利用，即选择当前平均奖赏最高的摇臂(若有多个，则随机选取一个)。

若摇臂奖赏的不确定性较大，例如概率分布较宽时，则需更多的探索，此时需要较大的e值;若摇臂的不确定性较小，例如概率分布较集中时，则少量的尝试就能很好地近似真实奖赏，此时需要的e较小.通常令e取一个较小的常数如0.1或0.01。然而，若尝试次数非常大，那么在一段时间后，摇臂的奖赏都能很好地近似出来，不再需要探索，这种情形下可让正随着尝试次数的增加|而逐渐减小，例如令 e= 1/t。

Softmax

Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。若各摇臂的平均奖赏相当，则选取各摇臂的概率也相当；若某些摇臂的平均奖赏
明显高于其他摇臂，则它们被选取的概率也明显更高。

其中 Q(i) 记录当前摇臂的平均奖赏；t>0 称为"温度" , t越小则平均奖赏高的摇臂被选取的概率越高。t趋于 Softmax 将趋于"仅利用"，t趋于无
穷大时 Softmax 则将趋于"仅探索"。

有模型学习

在已知模型的环境中学习称为有模型学习，对于状态、每个状态的动作以及在状态x下执行动作a转移到状态x1的概率都是已知的。为了便于讨论，状态空间和动作空间都有限。

策略评估

在模型已知的前提下，我们可以对任意策略的进行评估（后续会给出演算过程）。一般常使用以下两种值函数来评估某个策略的优劣：

状态值函数（V）：V（x），即从状态x出发，使用π策略所带来的累积奖赏；
状态-动作值函数（Q）：Q（x,a），即从状态x出发，执行动作a后再使用π策略所带来的累积奖赏。

那么有状态值函数：
状态动作函数：

则对于T步累积奖赏有

类似的，对于r折扣累积奖赏有：

易知：当模型已知时，策略的评估问题转化为一种动态规划问题，即以填表格的形式自底向上，先求解每个状态的单步累积奖赏，再求解每个状态的两步累积奖赏，一直迭代逐步求解出每个状态的T步累积奖赏。基于T步累积奖赏的策略评估算法：

有了状态值函数V，就能直接计算出状态-动作值函数：

策略改进

对某个策略的累积奖赏进行评估后，若发现它并非最优策略，则当然期望对其进行改进。理想的策略应能最大化累积奖赏。最优策略所对应的值函数V*称为最优值函数。

由于最优值函数的累积奖赏值己达最大，因此将对动作的求和改为取最优:

即

策略迭代与值迭代

由前两小节我们知道了如何评估一个策略的值函数，以及在策略评估后如何改进至获得最优策略.显然，将这两者结合起来即可得到求解最优解的方法：从一个初始策略(通常是随机策略)出发，先进行策略评估，然后改进策略，评估改进的策略，再进一步改进策略，……不断迭代进行策略评估和改进，直到策略收敛、不再改变为止。这样的做法称为"策略迭代" (policy iteration)。

策略迭代法在每次改进策略后都要对策略进行重新评估，因此比较耗时。若从最优化值函数的角度出发，即先迭代得到最优的值函数，再来计算如何改变策略，这便是值迭代算法，算法流程如下所示：

免模型学习

蒙特卡罗强化学习

在免模型情形下，策略选代算法首先遇到的问题是策略无法评估，这是由于模型未知而导致无法做全概率展开。此时只能通过在环境中执行选择的动
作来观察转移的状态和得到的奖赏。受摇臂赌博机的启发，一种直接的策略评估替代方法是多次"采样"，然后求取平均累积奖赏来作为期望累积奖赏
的近似，这称为蒙特卡罗强化学习由于采样必须为有限次数，因此该)方法适合于使用T步累积奖赏的强化学习任务。

在模型米知的情形下，我们从起始状态出发、使用某种策略进行采样，执行该策略T步并获得轨迹

对轨迹中出现的每一对状态-动作，记录其后的奖赏之和，作为该状态自动作对的一次累积奖赏采样值。多次来样得到多条轨迹后，将每个状态-动作对的累积奖赏采样值进行平均，即得到状态-动作值函数的估计。

在上面的算法流程中，被评估和被改进的都是同一个策略，因此称为同策略蒙特卡罗强化学习算法。引入ε-贪心仅是为了便于采样评估，而在使用策略时并不需要ε-贪心，那能否仅在评估时使用ε-贪心策略，而在改进时使用原始策略呢？这便是异策略蒙特卡罗强化学习算法。

时序差分学习

蒙特卡罗强化学习算法通过考虑采样轨迹，克服了模型未知给策略估计造成的困难。此类算法需在完成一个采样轨迹后再更新策略的值估计，而前而介绍的基于动态规划的策略迭代和值迭代算法在每执行一步策略后就进行值函数更新。两者相比，蒙特卡罗强化学习算法的效率低得多，这里的主要问题是蒙特卡罗强化学习算法没有充分利用强化学习任务的 MDP 结构。时序主分(Temporal Difference ，简称 TD) 学斗则结合了动态规划与蒙特卡罗方法的思想，能做到更高效的免模型学习。

蒙特卡罗强化学习算法的本质，是通过多次尝试后求平均未作为期望累积奖赏的近似，但它在求平均时是"批处理式"进行的，即在一个完整的采样轨迹完成后再对所有的状态-动作对进行更新。

不如单步更新。对于状态-动作对 (x，α)，不妨假远基于t个采样己估计出值函数
则在第t+1个采样时，有

令1/t+1为更新步长，更新步长越大，则越靠后的累计奖赏越重要。

则对于r折扣奖赏：

每执行一步策略就更新一次值函数估计，则得到算法：

Sarsa：其中评估（第6行）、执行（第5行）都是e-贪心策略，因此是同策略算法。
Q-学习：其中评估（第6行）是e-贪心策略，执行（第5行）是原始策略，因此是异策略算法。

值函数近似

有限状态空间：值函数
无限状态空间：将值函数表达为状态的线性函数

基于线性值函数近似Sarsa：

模仿学习

直接模仿学习：直接模仿人类专家的状态-动作对，学习的策略模型可作为初始策略，在进行强化学习。
逆强化学习：从人类专家提供的也例数据
中反推出奖赏函数，这就是逆强化学习。