强化学习导论习题册

1强化学习导论习题册一、强化学习相关问题1请列举三个能够用强化学习框架描述的例子，并确定每个例子的状态、动作以及相应的回报值。请尽量列举三个不同的例子，并针对其中一个例子，归纳在建模过程中的一些限制因素。答迷宫，俄罗斯方块等。2强化学习框架是否能够用来描述所有的具有目标导向的任务如果不可以，你是否可以举一个反例答可以。3驾驶问题。你可以根据油门、方向盘、刹车，也就是你身体能接触到的机械来定义动作。或者你可以进一步定义它们，当车子在路上行驶时，将你的动作考虑为轮胎的扭矩。你也可以退一步定义它们，首先用你的头脑控制你的身体，将动作定义为通过肌肉抖动来控制你的四肢。或者你可以定义一个高层次的动作，比如动作就是目的地的选择。上述哪一个定义能够正确描述环境与AGENT之间的界限哪一个动作的定义比较恰当，并阐述其原因答第一个动作的定义比较恰当，AGENT与环境的界限是指有AGENT所能绝对控制的的范围，并不是指有关AGENT所有的信息，题中将司机抽象成一个AGENT，那么，由司机所能直接操作的只有油门，刹车和方向盘。4假设将平衡杆问题抽象成一个情节式任务，同时也添加折扣因子来计算回报值（对于每个状态的立即奖赏，设定失败状态的奖赏为0，其他状态的奖赏为1）。在该情况下，每个状态的回报函数如何设定该回报函数与公式（32）有何不同答回报函数KKKTTTTTRRRR01121与公式（32）的区别就是，在任务描述中是否存在吸收状态，在公式中的体现就是，对立即奖赏的累加是否无穷。5机器人迷宫问题。对其中的奖赏做如下设定，机器人走出迷宫，奖赏为1，而在其它情况下奖赏为0。这个任务看上去可以抽象成一个情节式任务（以走出迷宫作为一个情节的结束），目标是将期望回报值最大化，如公式（31）所示。但是在AGENT学习一段时间后，你会发现对于AGENT来说，走出迷宫的任务毫无进展。那么，这里问题出在什么地方如何做出改进提高性能答问题出在回报值的设定上，题中设定，机器人走出迷宫的奖赏为1，其他情况为0，那么，对于每个状态来说，根据公式（31），每个状态的回报值都为1，因此对于机器人的走向没有任何的导向作用。对于该问题的改进可以使用上个问题的回报函数，即添加折扣因子。或者，对于回报可以按一下方式进行设定，走出迷宫奖赏为0，其他情况奖赏为1。6破损视觉系统问题。假设你是一个视觉系统。当你第一次开机的时候，一整幅图像涌入你的摄像头。你能够看到很多东西，但不是所有东西，比如你无法看到被某一物体遮挡住的东西，或者是你背后的东西。在你看到第一个场景之后，你是否可以认为，你所接触的环境具有马尔科夫性，其中的状态是马尔科夫状态再假设你是一个破损的视觉系统，你的摄像头坏了，这种情况，你接收不到任何影像，那么在这种情况下，是否可以认为你所接触的环境具有马尔科夫性，其中的状态是马尔科夫状态2答如果一个状态包含所有环境相关信息，我们就认为这个状态具有马尔科夫性。在第一种情况下，状态不具有马尔科夫性，问题中也强调，视觉系统无法看见遮挡住的和背后的东西，因此，该状态不具有马尔科夫性。在第二种情况下，可以认为具有马尔科夫性，你接收不到不到任何影像，你也可以认为，你说处的环境，就是你所感知的，认为，你所知道的环境信息就是包含了所有相关信息，因此，可以认为具有马尔科夫性。7对于一个有限的马尔科夫决策过程，奖赏值数量有限，结合公式35，给出状态转移函数和回报函数。答,|PR1ASSTTTAS|1ERTTTTS8请给出动作值函数的BELLMAN等式。等式必须包含和。参考Q,AS,SQ回溯图34及公式（310）。答,|,ASREASQTT,|01KTTKTR,|021KTTKTTASE,|,02KTTKTASSAASRRP,ASQASSA9根据BELLMAN等式310可以计算每一个状态的，如图35B所示。比如对于图中V07这个值来说，可以根据其四周的23，04，04和07这四个值计算得出。试计算图中其他值，根据公式310，验证每个值的正确性。答略。10在例子格子世界中，到达目标状态设定奖赏为正值，到达边界状态设定奖赏为负值，其他状态奖赏为0。这样的设定是否必要，或者仅仅是为了区分不同状态的回报值对于每个状态的立即奖赏加上常量C，每个状态的回报值加上常量K，在不影响每个状态回报值与立即奖赏关系的前提下,试根据公式（32），将K用C和参数来表示。答设状态的回报值为X，立即奖赏为Y,SVRPASKSVASSASKVC3即1CK11考虑在情节式任务中，对每个状态的立即奖赏加上一个常量C，比如迷宫问题。这样对最终结果是否有影响这种情况对于连续式任务是否有影响，比如针对上一个问题中的格子世界给出解释。答，对于最终的结果没有影响，通过学习，最终是要能够得出一组最优策略，而对于每个状态的具体值是多少不关注，关注的是值之间的一个差异性。12每个状态的状态值函数的值是由当前状态下的动作值函数的值以及动作的选择概率说确定的。我们可以用一幅回溯图来表示它们之间的关系根据上图，给出和之间的等量关系。SV,AQ答,SA13动作值函数的值可以被分成两部分，期望立即奖赏值，该值不依赖与策略，,S和后续回报值的累加和，该值依赖于后续状态和策略。我们依然用一个回溯图来表示，根节点是一个动作（状态动作对），分支节点是可能的后续状态根据上图，给出和之间的等量关系。,ASQSV答,RPSSS14根据高尔夫球问题，描述最优状态值函数。答对与每次球的落点，根据动作DRIVER和PUTTER所能到达的不同落点和每个落点的状态值，确定下一个所要到达的状态，并计算每个状态的状态值函数的值。15根据高尔夫球问题，针对，描述最优动作值函数。,PUTERSQ答是指在状态S下，采用动作PUTTER，根据所可能到达的状态，结合,PUTERSQ每个状态所能采取的动作，分别是PUTTER和DRIVER，计算。,PUTERSQ16针对环保机器人，给出动作值函数的BELLMAN等式。答略。417图38给出格子世界中的最优状态的最优值函数的值244。利用你所了解的最优策略的知识和公式（32），以数学的形式计算该值，并给出如何利用该值计算周围三个状态值。答设最优状态的值为X09X4计算得X244周围三个状态的值都是X009244220二、动态规划1假如是等概率随机策略，试计算和,1DOWNQ,7DON答,SVRPASQASS0,1DOWN15472假设在表格中状态13下方添加一新的状态15，动作分别是LEFT，UP，RIGHT,DOWN,分别到达状态12，13，14和15。假设其他初始状态的状态转向没有改变。采用等概率随机策略时，的值是多少现假设状态13的状态转向发生变化，即采用VDOWN时从状态13到达状态15，采用等概率随机策略，的值又是多少15V答A4/13121515V4/5420解得679VB（1）/11413VV（2）43255联立公式（1）（2）解得090695注该题还可以这么考虑，对于状态15来说，其实完全是等同于没有加状态15之前的状态13（从它的状态转向和相对于吸收状态的位置，并且当状态15的值为20，正好满足最终的稳定状态时的值），故，其值应该是20。3根据公式（43）、（44）和（45），试给出对应的动作值函数。Q答,|,ASREASQTT5,|01KTTKTASRE,|,1QTTT,ASRPASSA,1QKASSAK4（编程）根据例42，并改变以下条件，写一个策略迭代的程序解决汽车租赁问题。在租赁一店，有一雇员每晚需要乘公交车回家，而且她的家离租赁二店很近。因此，她很乐意免费将一辆车从一店开往二店。对于其他要移动的车辆每次仍然需要花费2美圆。另外，JACK每地的停车场空间有限。假如每地每晚停放10辆以上的汽车（在汽车移动之后），那么就需要使用第二个停车场，并且需要付额外的4美圆（不管有多少车停在那里）。这类非线性随机问题经常发生在现实生活中，除了动态规划方法，其他的最优策略一般都很难解决这类问题。为了检查所编写的程序，可以先将原始问题所给出的答案复制下来。假如你的电脑比较慢，你可以将汽车的数量减半。答提示环境的搭建A状态的表示在二维平面中，利用坐标表示状态B动作的表示需要移动的车的数量，区分正向和反向（假设正向为从一店移动到二店）C立即奖赏由每天租车的数量的盈利、移动费用及停车场费用构成D状态的迁移由两个泊松分布及动作决定E动作的选择开始采用随机策略（方向定为，从车多的店往车少的店移动）F初始状态的回报值都设为05考虑如何利用策略迭代计算动作值函数参考图43计算，试给出一个完整的算法V计算。Q答1、初始化对于任意，SSSARSQ,2、策略评估REPEAT0FOREACHS|,|,MAX,SQVSQSRPQVSSSUNTIL一个极小的数63、策略改进TURESTABLPOLICYFOREACHS,MAXMAXRGSASSQRPSIFTHENBFLETBLPOLICYIFTHENSTOPELSEGOTO2STLEPOLICY6假如仅仅考虑策略，即在每一状态S所选择一动作的概率至少是。F|/SA以步骤321的顺序，详细描述在图43中的的策略迭代算法每步的变化。V答考虑动作选择的概率，并添加至更新公式。7考虑为什么描述赌徒问题最优策略的曲线会如图46所示比如，当赌徒的资金数是50美元的时候，他一次性压上所有的资金，但是当他的资金数是51美元的时候他却不这么做。试说明为什么说这是一个比较好的策略答（1）根据问题的描述，赌徒问题的最终目标是能够赢取100美元，那么对于策略来说，要求该策略使得赌徒在每一个状态下，能够获得尽量大的赢取概率，这里的赢取概率其实就是回报值。参考图46的上图，我们发现，对于下图的策略，上图的赢取概率一直在增加，我们可以认为这是一个比较好的策略。（2）其实判断一个策略的好坏，在42节中，我们知道，可以通过计算来,ASQ判断。8（编程）编程实现，当P025和P055,得到赌徒问题的最优策略。程序执行后，你将很容易解释两个假定的最终状态，最后资金数分别是0和100，反馈值分别设定为0和1。将你的结果表示的如同图46一样。观察你的策略是否稳定，即0答提示环境的搭建A状态的表示赌徒手中的资金数目B动作的表示10,MIN,2SAC立即奖赏当资金数达到100，奖赏为1，其他为0D状态的迁移赌徒手中资金的改变E动作的选择开始采用随机策略（从可选动作中随机选择）F初始状态的回报值都设为09参考公式（410），试给出动作值函数的迭代公式,1ASQK答,MAX,1SRPASQKSSAK7三、蒙特卡罗1考虑图52中右边的两幅图表，为什么值函数在尾部最后两行突然跳高为什么在最左边一行值又下降了为什么上图中最突出的值要比下图还要大答SUM20或21时，PLAYERSPOLICYISSTICKS，此时RETURN1的几率较大，获胜的1概率较大；DEALER爆点的概率小，获胜的概率大。因为ACE即可以当1用，又可当11用。2有ACE时爆点的概率小，获胜的概率大。因为ACE即可以当1用，又可当11用。32蒙特卡罗估计Q值的回溯图是什么样的答如下图。3已知策略下产生的返回值，则与（53）类似的蒙特卡罗对动作值的估计计算式是什么答LET和DENOTETHEPROBABILITIESOFTHATCOMPLETESEQUENCEHAPPENING,ASPI,SIGIVENPOLICIES和ANDSTARTINGFROMS,TAKINGACTIONA。SSNIIIAPRASQ1,其中，在时刻T811,STTKASKATIIKTPPSP11,11STTKKSTTKASKASTSTIIIKTIKTAPPSPISTHETIMEOFTERMINATIONOFTHEITHEPISODEINVOLVINGSTATESTI4跑道问题（编程）答略。5修改FIRSTVISITMC策略估计（图51）算法，使用25节中介绍的静态平均值的增量实现技术。答如下图。初始化要被估计的策略V0无限次重复（A）使用策略产生一个EPISODE（B）对于出现在该EPISODE中的每个状态SR伴随S第一次发生的返回值11VRNVNN用FIRSTVISITMC算法来估计V（增量实现）6按照从（21）式中获得不加权规则（24）式的形式，从（54）式中得到对平均值加权的更新规则（55）。答11NKNWRV11111NNNNNKNWRWVWRVW9NNVRWWV17修改OFFPOLICY蒙特卡罗控制算法（图57），使之能使用上面介绍的算法来递增计算加权的平均值。答如下图。初始化，对于任意SS,AASQS,A任意值任意的一个确定的策略无限次重复（A）选择一个策略并用它产生片段S0,A0,R1,S1,A1,R2,ST1,AT1,RT,ST（B）使AS成立的最晚的时间（C）对于在时间或后出现在片段中的每对S,AT时间之后，第一次出现的S,A的时间，T对于第N个EPISODE1,TTKKASWIF1NNRQ,ELSE1NNWW1,NNASQRASS（D）对于每个SSSARGMAXAQS,A四、TD学习1这个练习是帮助你去形成一种直觉，这种直觉是关于为什么时间差分方法比蒙特卡罗方法更有效。考虑驾车回家的例子，它是怎样被时间差分方法和蒙特卡罗方法表述的。你能够想象这样一个场景，在这个场景中，时间差分更新平均优于蒙特卡罗方法吗给出一个示例场景对过去经验的描述和一个当前状态在其中你期望时间差分更新更好。提示假设你有许多驾车回家的经验。后来你搬到了一幢新楼，停车地点也发生了变化（但是你仍然在相同的地方进入高速公路）。现在你正在学习这个新楼的预计值。在这种情况下至少是在最初时，你能看到为什么时间差分更新可能更好一点吗可能这个相同类型的事件发生在初始任务。答略102从图66可以看出第一个片段仅仅导致的改变。通过第一个情节之后，能说明什VA么问题为什么只有第一个状态的估计改变呢它准确地改变了多少呢答1）在第一个情节中，AGENT向左移动一步，并到达左边的吸收状态，情节结束2）AGENT向左移动一步，并到达左边的吸收状态，情节结束，并没有达到其他状态，因此其他状态的V值没有发生变化3）计算公式如下ARTVA0510543你认为通过选择不同的步长参数，但仍然保持是一个常量的话，算法能明显地比图67中所示的效果更好吗为什么或者为什么不呢答步长参数体现当前样本对整个样本空间的影响，值越大，表明当前样本对整个样本空间的影响越大，反之亦然。且当值越大时，算法的收敛速度越快，同时收敛效果变差，当值越小时，算法的收敛速度越慢，同时收敛效果变号，这个通过图67可以看出。4在图67中，TD方法的RMS误差似乎先减少然后又增加，特别是在高的中。什么导致这个结果的发生呢你认为这是一直发生的呢，还是这可能是一个函数关于近似值函数怎样初始化的问题呢答一直会发生，但并不是一直增加，可能在某一个时刻，曲线又出现下降的趋势。当值越大，表明当前样本对整个样本空间的影响越大，反之亦然。因此，当值较大，并且算法趋近于收敛时，如果当前的样本较差，就容易使得收敛曲线发生震荡。5我们上面所述的随机行走任务的对A到E的所有状态的真实值是和1,6324,。至少用两种可以计算的方式来描述。你猜哪种实际上我们已经用过了呢为什56么答1）先确定的值为05VC2）不确定的值，直接计算11猜测第一种方法被用过，在例子的描述中，有提到确定的值为05VC6使用KINGSMOVES的有风的格子世界（编程）假设有八个可能的动作解决有风的格子世界任