7.4-最优行动值估计:Q-Learning
本节将介绍Q-learning算法，这是经典的强化学习算法之一[38,39]。前面介绍的Sarsa只能估计给定策略的动作值，必须结合策略改进步骤才能得到最优策略。相比之下，Q-learning可以直接估计最优动作值进而找到最优策略。
7.4.1算法描述¶
Q-Learning算法为
其中 \(t =0,1,2, \dots\)。这里\(q_t(s_t, a_t)\)表示对\((s_t, a_t)\)的最优行动值的估计，\(\alpha_t(s_t, a_t)\)是学习率。
Q-learning的表达式与Sarsa相似，二者的区别仅在于TD目标：Q-learning的TD目标为\(r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)\)，而Sarsa的TD目标为\(r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\)。因此，如果当前的状态-行动是\((s_t, a_t)\)，Sarsa在每次迭代需要样本\((r_{t+1}, s_{t+1}, a_{t+1})\)，而Q-learning仅需\((r_{t+1}, s_{t+1})\)。
为什么Q-learning被设计为\((7.18)\)式中的表达式，它在数学上实现了什么功能？实际上，Q-learning是一个求解如下贝尔曼最优方程的随机近似算法。
这是用行动值表示的贝尔曼最优方程。其证明过程见Box 7.5。Q-Learning的收敛性分析与定理7.1类似，此处从略。更多细节可参阅文献[32,39]。
Note
这里得到的\(q\)值不是说哪一个策略的\(q\)值，而是最优的\(q\)值，对应的即为最优的策略。
7.4.2 Off-policy和On-policy¶
接下来介绍两个重要概念：Of-policy(异策略)和On-policy(同策略)。之所以在介绍Q-learning时引入这两个概念，是因为Q-learning相比前面的TD算法有一点特殊：Q-learning是Of-policy的，而前面介绍的算法如Sarsa都是On-policy的。
任何一个强化学习算法都会涉及两种策略：一种是行为策略(behavior policy),另一种是目标策略(target policy)。行为策略用于生成经验样本，而目标策略不断更新，从而收敛至最优策略。当行为策略与目标策略相同时，该算法被称为On-policy的，中文为同策略(因为两个策略相同);当它们不同时，该算法被称为Of-policy的，中文为异策略(因为两个策略不同)。
Offpolicy算法的优势在于它可以使用由其他策略生成的经验样本来学习最优策略。一个常见的情况是使用探索性较强的行为策略生成的经验数据。例如，如果我们想要估计所有动作值，则必须生成多次访问每个状态-动作的轨迹，此时可以使用\(\varepsilon\)-Greedy策略来生成轨迹。尽管Sarsa也使用\(\varepsilon\)-Greedy策略来保持一定的探索能力，但是为了保证最优性，其\(\varepsilon\)的值通常很小，因此探索能力有限。相比之下，如果我们能使用一个具有较强探索能力的策略(例如\(\varepsilon\)=1)来生成经验数据，然后使用Off-policy算法来学习最优策略，效率将显著提高。后面将给出一个例子来说明这一点。
如何确定一个算法是On-policy还是Off-policy呢?如果一个算法可以使用任何其他策略生成的经验数据来得到最优策略，那么这个算法就是Off-policy的；反之，则是On-policy的。当然，这并不是真正意义上的回答，而是基于Of-policy和On-policy的定义。为了真正回答这个问题，我们可以考察算法的两方面：第一个方面是算法旨在解决的数学问题，第二个方面是算法所需的经验样本。
-
Sarsa是on-policy算法:
原因如下。Sarsa在每次迭代中有两个步骤。第一步是通过求解贝尔曼方程来评价当前策略\(\pi\)。为此我们需要由\(\pi\)生成的样本，因此\(\pi\)是行为策略。第二步是基于对\(\pi\)的估计值获得一个改进的策略，\(\pi\)不断更新并最终收敛到最优策略，因此\(\pi\)也是目标策略，所以Sarsa中的行为策略和目标策略是相同的。
从另一个角度来看，我们可以分析算法所需的样本。Sarsa算法在每次迭代中需要的样本包括\((s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\)。这些样本的生成方式如下所示：
\[s_t\xrightarrow{\pi_b}a_t\xrightarrow{\mathrm{model}}r_{t+1},s_{t+1}\xrightarrow{\pi_b}a_{t+1}\]在此过程中，行为策略\(\pi_b\)用于在在状态\(s_t\)下生成行动\(a_t\)、在状态 \(s_{t+1}\)下生成行动\(a_{t+1}\)。Sarsa用这个经验数据来估计\(q_{\pi_b}(s_t,a_t)\),并基于此改进得到新的策略。换句话说，Sarsa评价进而改进的策略(即目标策略)就是用来生成样本的策略，因此Sarsa是On-policy的。
-
Q-Learning是一种off-policy算法:
其本质的数学原因在于Q-learning是求解贝尔曼最优方程，而Sarsa是求解用于生成经验数据的策略对应的贝尔曼方程。求解贝尔曼方程只能评价对应的策略，而求解贝尔曼最优方程则可以直接得到最优策略。
具体来说，Q-learning每次迭代所需的样本为\((s_t, a_t, r_{t+1}, s_{t+1})\)。这些样本的生成方式如下所示：
\[s_t\xrightarrow{\pi_b}a_t\xrightarrow{\mathrm{model}}r_{t+1},s_{t+1}\]在此过程中，行为策略\(\pi_b\)用于在状态\(s_t\)下产生行动\(a_t\)。Q-Learning算法的目标是估计\((s_t, a_t)\)的最优行动值。这一过程依赖于样本\((r_{t+1}, s_{t+1})\)。产生\((r_{t+1},s_{t+1})\)的过程完全由系统模型(即通过与环境的交互)决定。因此，\((s_t, a_t)\)的最优行动值的估计不再涉及\(\pi_b\)。
Note
注: Q-learning的行为策略就是需要从\(s_t\)出发根据一个策略得到一个\(a_t\)，而目标策略就是根据计算得到的\(q\)来选择对应的行动，当\(q\)逐渐收敛到最优\(q\)值时，也就收敛到了最优策略。
-
MC learning是一种on-policy算法:
原因与Sarsa算法类似。待评估和改进的目标策略与生成样本的行为策略是相同的。
最后，有的读者可能会问On-policy/Off-policy与Online/Ofline(在线/离线)的区别是什么?在线学习是指智能体在与环境交互的同时用生成的数据来更新值和策略。离线学习是指智能体不与环境交互，而是使用预先收集的数据来更新值和策略。如果算法是On-policy的，那么它可以实现在线学习，但不能实现离线学习，因为它无法使用预先收集的其他策略生成的数据。如果算法是Off-policy的，那么它既可以在线学习，也可以离线学习。
7.4.3 算法实现¶
由于Q-learning是Off-policy的，所以它在编程实现时有两种模式。
第一，On-policy模式，即行为策略和目标策略相同。算法7.2给出了伪代码。这种方式与算法7.1中的Sarsa类似，因为此时行为策略与目标策略相同，都是一个\(\varepsilon\)-Greedy 的策略。此外，该算法是在线学习的，即智能体一边与环境交互以获得数据，一边更新值和策略。
算法7.2
Note
看on-policy的Q-learning的update q-value可以看到，与Sarsa的公式不同的是，Sarsa中的最后项是\(q_t(s_{t+1},a_{t+1})\)，而Q-learning的最后项是\(\gamma \max_a q_t(s_{t+1},a)\)。可以看到，on-policy版本的Q-learning是根据策略生成经验样本更新\(q\)值，利用\(q\)值更新策略，然后重复。
第二，Off-policy模式，即行为策略和目标策略不同。算法7.3给出了伪代码。其中行为策略\(\pi_b\)可以是任意策略，只要它能生成足够的经验数据。因此，行为策略最好具有一定的探索性。在此算法中，目标策略\(\pi_T\)是Greedy的而不是\(\varepsilon\)-Greedy的，这是因为它不用生成经验数据，因此不需要具有探索性。此外，该算法是离线学习的，即先收集所有经验样本，然后再学习。
算法7.3
Note
这里与on-policy的不同之处在于update target policy从\(\varepsilon\)-贪婪策略变为了贪婪策略。
7.4.4 示例¶
第一个例子如图7.3所示，它展示了算法7.2中On-policy模式的Q-learning。这里的目标是从给定的状态出发找到达到目标状态的最优路径。参数设置在图7.3的标题中给出。如该图所示，Q-learning最终能找到一个最优路径。在迭代过程中，每个回合的长度逐渐缩短，而每个回合的回报逐渐增加。
第二组示例如图\(7.4\)和图\(7.5\)所示，展示了off-policy Q-learning过程。这里的任务是找到所有状态的最优策略。奖励设置为\(r_{\text{boundary}} = r_{\text{forbidden}} = -1\)，且\(r_{\text{target}} =1\)。折扣因子\(\gamma =0.9\)，学习率\(\alpha =0.1\)。
图\(7.3\)：Q-Learning算法的演示示例。所有训练回合均从左上角状态开始，并在到达目标状态后终止。目标是找到从起始状态到目标状态的最优路径。奖励设置为 \(r_{\text{target}} =0\)、\(r_{\text{forbidden}} = r_{\text{boundary}} = -10\)，以及 \(r_{\text{other}} = -1\)。学习率 \(\alpha =0.1\)，\(\gamma\)值为0.1。左图显示算法获得的最终策略，右图展示每个训练回合的总奖励与路径长度。
-
最优策略：为了验证Q-learning的有效性，我们首先使用之前介绍的需要模型的策略迭代算法求解出真实的最优策略和最优状态值，如图\(7.4(a)\sim(b)\)所示。
-
经验样本：行为策略在任意状态下采取任意动作的概率是相同的，都等于\(0.2\) (图\(7.4(c)\))。我们使用该行为策略生成一个包含\(100000\)步的回合(图\(7.4(d)\))。由于该行为策略具有良好的探索能力，这一个回合就能多次访问每个状态-动作。
-
学习到的策略：Q-learning最终学到的目标策略如图\(7.4(e)\)所示。这个策略是最优的，因为估计误差收敛到了\(0\) (图\(7.4(f)\)。此外，有的读者可能注意到Q-learning学到的最优策略与图\(7.4(a)\)中的最优策略不完全相同。实际上，这两个都是最优策略，它们对应相同的最优状态值。
-
不同的初始值：由于Q-learning采用自举方法，算法需要选取合适的初始动作值估计。如果初始估计靠近真实值，则估计过程收敛较快，例如在约\(10000\)步内收敛(图\(7.4(g)\))。否则，估计过程收敛较慢(图\(7.4(h)\))。
-
不同的行为策略：当行为策略的探索性较差时，学习的效果显著下降。例如，图\(7.5\)给出了一些探索性较差的行为策略。虽然它们是\(\varepsilon\)-Greedy,但是因为\(\varepsilon=0.5\)或\(0.1\)较小，所以探索性较差。结果表明，当\(\varepsilon\)从1减少到0.5,然后再减少到0.1时，学习速度显著降低，这是因为行为策略的探索能力较弱，导致经验样本不合理。
图\(7.4\)：用于展示 Of-policy模式的 Q-learning的例子。图(a)和(b)展示了最优策略和最优状态值。图©和(d)展示了行为策略和生成的回合。图(e)和(f)展示了学习到的策略和估计误差的收敛过程。图(g)和(h)展示了具有不同初始值的情况。
图\(7.5\)：当行为策略探索性较弱时，学习的效果会下降。左列的图展示了不同的行为策略。中间列的图展示了由相应行为策略生成的回合，每个回合有100000步。右列的图展示了最优状态值估计误差的演变过程。