1、 1 强化学习导论 习题册 一、 强化学习相关问题 1. 请列举三个能够用强化学习框架描述的例子，并确定每个例子的状态、动作以及相应的回报值。请尽量列举三个不同的例子，并 针对其中一个例子，归纳在建模过程中的一些限制因素。 答：迷宫，俄罗斯方块等。 2. 强化学习框架是否能够用来描述所有的具有目标导向的任务？如果不可以，你是否可以举一个反例？ 答：可以。 3. 驾驶问题。 你可以根据油门、方向盘、刹车，也就是你身体能接触到的机械来定义动作。或者你可以进一步定义它们，当车子在路上行驶时，将你的动作考虑为轮胎的扭矩 。 你也 可以 退 一步定义它们， 首先 用你的头脑控制你的身体， 将 动作 定义
2、为通过肌肉抖动来控制你的四肢。或者你可以定义 一个高层次 的动作，比如 动作 就是目的地的 选择。 上述哪一个定义能够正确描述环境与 Agent 之间的界限？哪一个动作的定义比较恰当，并阐述其原因？ 答：第一个动作的定义比较恰当， Agent 与环境的界限是指有 Agent 所能绝对控制的的范围，并不是指有关 Agent 所有的信息，题中将司机抽象成一个 Agent，那么，由司机所能直接操作的只有油门，刹车和方向盘。 4. 假设 将 平衡杆问题 抽象成一个情节式任务 ， 同时也添加折扣因子来计算回报值 （对于每个状态的立 即奖赏，设定失败状态的奖赏为 0，其他状态的奖赏为 -1） 。 在该情况
3、下，每个状态的回报函数如何设定 ？ 该回报函数与公式（ 3.2）有何不同 ？ 答： 回报函数： Kk ktkKtKttt rrrrR0 1121 与公式（ 3.2）的区别就是，在任务描述中是否存在吸收状态，在公式中的体现就是，对立即奖赏的累加是否无穷。 5. 机器人迷宫 问题 。 对其中的奖赏做如下设定，机器人走出迷宫，奖赏为 1，而在其它情况下 奖赏 为 0。这个任务看上去 可以抽象成 一个情节 式 任务 （ 以走出迷宫作为一个情节的结束 ）， 目标是将 期望 回报值最大化 ，如公式 （ 3.1） 所 示 。 但是在 agent 学习一段时间后，你会发现 对于 Agent 来说， 走出迷宫的
4、任务毫无进展。 那么，这里问题出在什么地方 ？ 如何做出改进提高性能 ？ 答：问题出在回报值的设定上，题中设定，机器人走出迷宫的奖赏为 +1，其他情况为 0，那么，对于每个状态来说，根据公式（ 3.1），每个状态的回报值都为 +1，因此对于机器人的走向没有任何的导向作用。 对于该问题的改进可以使用上个问题的回报函数，即添加折扣因子。或者，对于回报可以按一下方式进行设定，走出迷宫奖赏为 0，其他情况奖赏为 -1。 6. 破损视觉系统问题。假设你是一个视觉系统。当 你第一次开机的时候， 一整幅图像涌入你的摄像头。 你能够看到很多东西，但不是所有东西 ，比如你无法看到被某一物体遮挡住的东西，或者是你
5、背后的东西。在你看到第一个场景之后，你是否可以认为，你所接触的环境具有马尔科夫性，其中的状态是马尔科夫状态？再假设你是一个破损的视觉系统，你的摄像头坏了，这种情况，你接收不到任何影像，那么在这种情况下，是否可以认为你所接触的环境具有马尔科夫性，其中的状态是马尔科夫状态？ 2 答： 如果一个状态包含所有环境相关信息，我们就认为这个状态具有马尔科夫性。 在第一种情况下，状态不具有马尔科夫性， 问题中也强调，视觉系统无法看见遮挡住的和背后的东西，因此，该状态不具有马尔科夫性。 在第二种情况下，可以认为具有马尔科夫性，你接收不到不到任何影像，你也可以认为，你说处的环境，就是你所感知的，认为，你所知道的
6、环境信息就是包含了所有相关信息，因此，可以认为具有马尔科夫性。 7. 对于一个有限的马尔科夫决策过程，奖赏值数量有限，结合公式 3.5，给出状态转移函数和回报函数。 答： ,|P r 1 aassssP tttass ,| 11 ssaassrER ttttass 8. 请给出动作值函数的 Bellman 等式 Q 。等式必须包含 ),( asQ 和 ),( asQ 。参考回溯图 3.4 及公式（ 3.10）。 答： ,|),( aassREasQ ttt ,|0 1 k ttktk aassrE ,|0 21 k ttktkt aassrrE ,|),(02 k ttktkaasssass
7、aassrasRP ),(),( asQasRP aasss ass 9. 根据 Be llman 等式 (3.10)可以计算每一个状态的 V ，如图 3.5b 所示。比如对于图中 0.7这个值来说，可以根据其四周的 +2.3， +0.4， -0.4 和 +0.7 这四个值计算得出。试计算图中其他值，根据公式 3.10，验证每个值的正确性。 答：略。 10. 在例子格子世界中，到达目标状态设定奖赏为正值，到达边界状态设定奖赏为负值，其他状态奖赏为 0。这样的设定是否必要，或者仅仅是为了区分不同状态的回报值？对于每个状态的立即奖赏加上常量 C，每个状态的回报值加上常量 K，在不影响每个状态回报
8、值与立即奖赏关系的前提下 ,试根据公式（ 3.2），将 K 用 C 和参数 来表示。 答： 设状态的回报值为 x，立即奖赏为 y )(),()( KsVCRpasKsVassa sass KsVRpasCassa sass )(),( KsVC )( 3 即： )1( CK 11. 考虑在情节式任务中，对每个状态的立即奖赏加上一个常量 C，比如迷宫问题。这样对最终结果是否有影响？这种情况对于连续式任务是否有影响， 比如针对上一个问题中的格子世界？给出解释。 答：，对于最终的结果没有影响，通过学习，最终是要能够得出一组最优策略，而对于每个状态的具体值是多少不关注，关注的是值之间的一个差异性。 1
9、2. 每个状态的状态值函数的值是由当前状态下的动作值函数的值以及动作的选择概率说确定的。我们可以用一幅回溯图来表示它们之间的关系： 根据上图，给出 )(sV 和 ),( asQ 之间的等量关系。 答： ),(),()( asQassV a 13. 动作值函数的值 ),( asQ 可以被分成两部分，期望立即奖赏值 ，该值不依赖与策略 ，和后续 回报值的累加和，该值依赖于后续状态和策略 。我们依然用一个回溯图来表示，根节点是一个动作（状态 -动作对），分支节点是可能的后续状态： 根据上图，给出 ),( asQ 和 )( sV 之间的等量关系。 答： )(),( sVRPasQ asss ass 1
10、4. 根据 高尔夫球问题，描述最优状态值函数。 答：对与每次球的落点，根据动作 driver 和 putter 所能到达的不同落点和每个落点的状态值，确定下一个 所要到达的 状态 ，并计算每个状态的状态值函数的值 。 15. 根据高尔夫球问题，针对 ),(* puttersQ ，描述最优动作值函数。 答： ),(* puttersQ 是指在状态 s 下，采用动作 putter，根据所可能到达的状态，结合每个状态所能采取的动作，分别是 putter 和 driver，计算 ),(* puttersQ 。 16. 针对 环保机器人，给出动作值函数的 Bellman 等式。 答：略。 4 17. 图
11、 3.8 给出格子世界中的最优状态的最优值函数的值 24.4。利用你所了解的最优策略的知识和公式（ 3.2），以数学的形式 计算 该值，并给出如何利用该值计算周围三个状态值。 答： 设最优状态的值为 x x)(0.9*0.90x 4 计算得 x=24.4 周围三个状态的值都是 x=0+0.9*24.4=22.0 二、 动态规划 1. 假如 是等概率随机策略，试计算 ),11( downQ 和 ),7( downQ . 答： )(),( sVRpasQasssass 000),11( d o w nQ 15)14(1),7( d o w nQ 2. 假设在表格中状态 13 下方添加一新的状态 1
12、5，动作分别是： left， up， right,down,分别到达状态 12， 13， 14 和 15。假设其他初始状态的状态 转向 没有改变。采用等概率随机策略时， )15(V 的值是多少？现假设 状态 13 的状态转向发生变化，即采用 down 时从状态 13 到 达状态 15，采用等概率随机策略， )15(V 的值又是多少？ 答： a. 4/)14()1()13()1()12()1()15(1()15( VVVVV 4/)4()15()14()20(22( V 解得： 2067.19)15( V b. 4/)14()14()9()12(4()13( VVVVV （ 1） 4/)14()
13、13()12()15()4()15( VVVVV （ 2） 联立公式（ 1）（ 2）解得： 209.19)13( V 206.19)15( V 注：该题还可以这么考虑，对于状态 15 来说，其实完全是等同于没有加状态 15之前的状态 13（从它的状态转向和相对于吸收状态的位置 ，并且当状态 15 的值为 20，正好满足最终的稳定状态时的值 ），故，其值应该是 20。 3. 根据公式（ 4.3）、（ 4.4）和（ 4.5），试给出对应的动作值函数 Q 。 答： ,|),( aassREasQ ttt 5 ,|0 1 k ttktk aassrE ,|),( 1 aassasQrE ttt ),(
14、),( asQasRP aasss ass ),(),(),( 1 asQasRPasQ kaasss assk 4. （编程） 根据例 4.2，并改变以下条件，写一个策略迭代的程序解决汽车租赁问题 。在租赁一店，有一雇员每晚需要乘公交车回家，而且她的家离租赁二店很近。因此，她很乐意免费将一辆车从一店开往二店。对于其他要移动的车辆每次仍然需要花费 2 美圆。另外， jack 每地的停车场空间有限。假如每地每晚停放 10 辆以上的汽车（在汽车移动之后），那么就需要使用第二个停车场，并且需要付额外的 4 美圆（不管有多少车停在那里 ）。这类非线性随机问题经常发生在现实生活中 ， 除了动态规划 方法
15、 ，其他的最优策略 一般 都很难解决这类问题。为了检查所编写的程序，可以先将原始问题所给出的答案复制下来。假如你的电脑比较慢，你可以将汽车的数量减半。 答：提示： 环境的搭建 a. 状态的表示 在二维平面中，利用坐标表示状态 b. 动作的表示 需要移动的车的数量，区分正向和反向（假设正向为从一店移动到二店） c. 立即奖赏 由每天租车的数量的盈利、移动费用及停车场费用构成 d. 状态的迁移 由两个泊松分布及动作决定 e. 动作的选择 开始采用随机 策略 （方向定为，从车多的店往车少的店移动） f. 初始状态的回报值都设为 0 5. 考虑如何利用策略迭代计算动作值函数 ？参考图 4.3 计算 *
16、V ，试给出一个完整的算法计算 *Q 。 答： 1、初始化 对于任意 Ss ， )()( sAs ， RssQ )(,( 2、策略评估 Repeat 0 For each Ss |)(,(|,m a x ()(,()(,()(,()(,()()()(ssQvssQssRPssQssQvssssssss Until (一个极小的数 ) 6 3、策略改进 tu resta b lep o lic y For each Ss ),(m a xm a xa r g)()(s aassassa asQRPssb If )(sb then fa ls es ta b lep o lic y If stab
17、lepolicy then stop ; else go to 2 6. 假如仅仅考虑 soft 策略，即在每一状态 s 所选择一动作的概率至少是 |)(|/ sA 。以步骤 3-2-1 的顺序，详细描述在图 4.3 中的 *V 的策略迭代算法每步的变化。 答： 考虑动作选择的概率，并添加至更新公式。 7. 考虑为什么描述赌徒问题最优策略的曲线会如图 4.6 所示？比如，当赌徒的资金数是 50美元的时候，他一次性压上所有的资金，但是当他的资金数是 51 美元的时候他却不这么做。试说明为什么说这是一个比较好的策略？ 答：（ 1）根据问题的描述，赌徒问题的最终目标是能够赢取 100 美元，那么对于
18、策略来说，要求该策略使得赌徒在每一个状态下，能够获得尽量大的赢取概率，这里的赢取概率其实就是回报值。参考图 4.6 的上图，我们发现，对于下图的策略，上图的赢取概率一直在增加，我们可以认为这是一个比较好的策略。 （ 2）其实判断一个策略的好坏， -在 4.2 节中，我们知道，可以通过计算 ),( asQ 来判断。 8. （编程）编程实现，当 p=0.25 和 p=0.55,得到 赌徒问题的 最优策略 。 程序执行后，你将很容易解释两个 假定的 最终状态，最后资金数分别是 0 和 100，反馈值分别 设定为 0 和1。将你的结果表示的如同图 4.6 一样。观察你的 策略是否稳定，即 0 ？ 答：
19、 提示：环境的搭建 a. 状态的表示 赌徒手中的资金数目 b. 动作的表示 )100,m in (,2,1 ssa c. 立即奖赏 当资金数达到 100，奖赏为 1，其他为 0 d. 状态的迁移 赌徒手中资金的改变 e. 动作的选择 开始采用随机策略 （从可选动作中随机选择） f. 初始状态的回报值都设为 0 9. 参考公式（ 4.10），试给出动作值函数的迭代公式 ),(1 asQk ？ 答： ),(m a x),(1 asQRpasQ kaasssassk 7 三、 蒙特卡 罗 1. 考虑图 5.2 中右边 的 两幅图表，为什么值函数在尾部最后两行突然跳 高 ？为什么在 最 左边一行 值
20、又下 降 了？为什么上图 中最突出的值要比下图还要大 ？ 答： 1 sum = 20 或 21 时， players policy is sticks，此时 Return = 1 的几率较大，获胜的概率较大； 2 dealer 爆点的概率小，获胜的概率大。因为 Ace 即可以当 1 用，又可当 11 用。 3 有 Ace 时爆点的概率小，获胜的概率大。因为 Ace 即可以当 1 用，又可当 11 用。 2. 蒙特卡罗 估计 Q值的回溯图 是什么 样的 ？ 答： 如下图 。 3. 已知策略 下 产生 的返回值 ，则 与（ 5.3）类似的 蒙特卡罗对 动作 值 的估计 计算 式是什么 ？ 答： L
21、et ),( aspi 和 ),( aspi denote the probabilities of that complete sequence happening given policies 和 and starting from s, taking action a。 ssniiini iiiaspaspsRasp aspasQ11),(),()(),( ),(),( 其中，在时刻 t 8 1)( 1 11 ),(),( sT tk a sskka sstti i k kkt tt PasPasp 1)(11)(11)(1),(),(),(),(),(),(1111 sTtk kkkk
22、sTtkasskkasssTtkasskkassttittiiikkktttikkktttasasPasPPasPaspasp( )(sTi is the time of termination of the ith episode involving state s. ) 4. 跑道问题（编程） 答：略。 5. 修改 first-visit MC 策略估计（图 5.1）算法，使 用 2.5 节中介绍的 静态平均值的增量实现技术 。 答：如下图。 6. 按照从（ 2.1）式中获得不加权规则（ 2.4）式的形式，从（ 5.4） 式中得到对平均值加权的更新规则 （ 5.5）。 答： 11111 n
23、k knk kkn wRwV初始化： 要被估计的策略 V 0 无限次重复： （ a） 使用 策略 产生一个 episode （ b） 对于出现在 该 episode 中的每个状态 s R 伴随 s 第一次发生的返回值 )(11)()(1 sVRnsVsV nnn 用 first-visit MC 算法来估计 V（增量实现） 9 1111111111 11 nnnnnnnnnnnnnk nnkk W RwwWVW RwWVW RwRw nnnnn VRWwV 111 7. 修改 off-policy 蒙特卡罗控制 算法（图 5.7） ，使之能使用上面介绍的算法来递增计算加 权 的 平均值。 答：
24、如下图。 四、 TD 学习 1. 这个练习是帮助你去形成一种直觉，这种直觉是关于为什么时间差分方法比蒙特卡罗方法更有效。考虑驾车回家的例子，它是怎样被时间差分方法和蒙特卡罗方法表述的。你能够想象这 样一个场景，在这个场景中，时间差分更新平均优于蒙特卡罗方法吗？给出一个示例场景 对过去经验的描述和一个当前状态 在其中你期望时间差分更新更好。提示：假设你有许多驾车回家的经验。后来你搬到了一幢新楼，停车地点也发生了变化（但是你仍然在相同的地方进入高速公路）。现在你正在学习这个新楼的预计值。初始化，对于任意 s S , a A(s): Q(s,a) 任意值 任意的一个确定的 策略 无限次重复 ： （
25、a） 选择一个策略 并用它产生片段 s0,a0,r1,s1,a1,r2, ,sT-1,aT-1,rT,sT （ b） 使 a(s) 成立的最晚 的时间 （ c） 对于在时间 或 后出现在片段中的每对 s, a： t 时间之后， 第一次出现的 s,a 的时间， t 对于第 n 个 episode 1 1 ,1T tk kkn asw if 1 n nn RasQ ),( Else 1 nnn WwW 11 ),(),(),( nnnnnn asQRWwasQasQ（ d） 对于每个 s S: (s) arg maxa Q(s,a) 10 在这种情况下至少是在最初时，你能看到为什么时间差分更新可能
26、更好一点吗？可能这个相同类型的事件发生在初始任务。 答： 略 2. 从图 6.6 可以看出第一个 片段 仅仅 导致 ()VA的改变。 通 过第一个情节之后，能说明什么问题？ 为什么只有第一个状态的估计改变呢？它准确地改变了多少呢？ 答： 1）在第一个情节中， Agent 向左移动一步，并到达左边的吸收状态，情节结束 2） Agent 向左移动一步，并到达左边的吸收状态，情节结束，并没有达到其他状态，因此其他状态的 V 值没有发生变化 3）计算公式如下 : ( ) ( ) ( ( ) ( ) )V A V A R V T V A 0 .5 0 .1* (0 0 0 .5 ) 0.45 3. 你认
27、为通过选择不同的步长参数 ，但仍然 保持 是 一个 常量 的话 ，算法能 明显 地比图6.7 中 所示的效果更好吗？为什么或者为什么不呢？ 答：步长参数体现当前样本对整个样本空间的影响， 值越大，表明当前样本对整个样本空间的影响越大，反之亦然。且当 值越大时，算法的收敛速度越快，同时收敛效果变差，当 值越小时，算法的收敛速度越慢，同时收敛效果变号，这个通过图 6.7可以看出。 4. 在图 6.7 中， TD 方法的 RMS 误差似乎先减少然后又增加， 特别是在 高的 中 。 什么导致这 个 结果的发生呢？你认为这 是一直 发生 的呢 ， 还是 这 可能是 一个函数关于 近似 值函数怎样初始化的 问题呢 ？ 答：一直会发生，但并不是一直增加，可能在某一个时刻，曲线又出现下降的趋势。当 值越大，表明当前样本对整个样本空间的影响越大，反之亦然。 因此，当 值 较大，并且算法趋近于收敛时，如果当前的样本较差，就容易使得收敛曲线发生震荡。 5. 我们 上 面 所述 的 随机 行走 任务的 对 A 到 E 的 所有状态的真实值是 1,6 324,6 6 6 和56 。至少用两种可以计算的方 式 来描述。你猜 哪 种实际上我们已经用过了 呢 ？为什么？ 答： 1）先确定 V( )C 的值为 0.5
