强化学习 课件 第2章 Bandit问题

第二章Bandit问题北京大学余欣航目录

Bandit问题多臂老虎机问题（Multi-ArmedBandit，MAB）

多臂老虎机问题是退化的MDP

多臂老虎机问题（Multi-ArmedBandit）

如何使累积奖励最大？满足伯努利分布：只取0（吐出硬币）或1（未吐出硬币）简单策略

摇臂编号10.720.530.240.150.8最佳操作是选择第5个摇臂期望奖励估计表简单策略的缺点

贪心策略（greedy）

摇臂编号10.720.530.240.150.8摇臂编号10.720.530.240.150.82期望奖励估计表进行第1次游戏选择5号摇臂进行操作，得到1枚硬币

期望奖励估计表贪心策略的缺点总是选择当前概率最大的摇臂进行操作，而真正中奖概率高的摇臂可能是那些当前估计概率低的摇臂！在有限游戏次数下，是坚持在当前中奖概率高的摇臂下操作（利用），还是尝试别的摇臂（探索）呢？如何在探索和利用之间进行平衡，称为探索利用困境(exploration-exploitationdilemma)探索与利用平衡生活中的探索与利用去经常光顾的咖啡馆喝咖啡（利用）尝试去其它咖啡馆，或许会喝到更喜欢的咖啡（探索）在MAB问题基础上增加状态的ContextualBandit问题经常被用于广告推荐Agent不断选择商品推送给顾客，并通过反馈判断其喜欢什么商品只有通过不断试验，才能逐步了解顾客，推送准确的商品但这个过程中，如果推送了顾客不喜欢的产品，必然会造成经济损失Refer:/news/201704/c9wvaAoGb39f8OBt.html生活中的探索与利用临床试验利用：试验期间尽可能有效地治疗患者探索：通过研究确定最佳治疗方法在线广告利用：坚持至今效果最好的广告探索：目标是使用点击率收集有关广告效果的信息生活中的探索与利用探索利用困境强化学习中，经常会考虑另外一种设定，即先将Agent在特定的环境上训练好，然后再考察它的效果例如要训练一个玩游戏的Agent，可以先用它在电脑上训练很多轮，然后再看它能达到何种性能唯一目标是在训练完毕之后它能拿出足够好的表现而其在训练中的表现是完全不重要的！这样的话，还需不需要exploitation？有监督学习与强化学习的区别有监督学习中，训练与测试必须严格分开，而评价算法的标准必须是测试误差而非训练误差强化学习中，直接针对未知环境学习最佳策略，训练与测试都是在同一个环境进行，训练误差与测试误差不必严格分开需要结合现实中的具体情况，去定义问题是“边训练边测试”还是“先训练后测试”算法的成本任何的算法都要考虑成本在“先训练后测试”的情形下，所考虑的成本主要是用到了多少数据例如在训练玩游戏的Agent时，训练的成本是它训练的轮数，而不是训练时它的表现在“边训练边测试”的情形下，所考虑的成本不只是数据的成本，也和数据的内容有关例如在多臂老虎机问题中，训练的主要成本是损失的金币玩多臂老虎机的时候，究竟是否需要考虑赢输金币的多少？关键要确定目标！重新定义MAB问题

重新定义MAB问题在前50次模拟中，得出如下估计结果：接下来还应该认为各个摇臂都有相同可能是最佳摇臂吗应该认为第1、2、5号摇臂更有可能是最佳摇臂摇臂编号实验次数10.71020.51030.21040.11050.810将接下来50次试验的机会平均分配给第1、2、5号摇臂，得到如下结果：上述结果可以认为，第1和第5两个摇臂更可能是最佳摇臂重新定义MAB问题摇臂编号实验次数10.762720.582630.21040.11050.7827重新定义MAB问题将最后50次试验机会平均分配给第1和第5号摇臂，得到如下结果：根据右表的结果可以认为，

第5号摇臂更可能是最佳摇臂！摇臂编号实验次数10.755220.582630.21040.11050.7952

利用的意义

反映了exploitation的基本思想利用的意义

探索与利用

探索和利用

探索率的选择如果将其设计得太高（即更倾向于“探索”）会导致较少选择“看起来是最好”的摇臂如果将其设计得太低（即更倾向于“利用”）则会导致不能充分探索环境以及时发现“最好”的摇臂应该如何选择探索率呢？

初步探索次数的选择

ε递减策略（ε-greedywithεdecayed）

Boltzmann策略

在“先训练再测试”的设定下，ε-greedy并不是一个高效的算法假设先对每个摇臂各试验10次（即一共试验了50次），得到：第1号摇臂比起第3号摇臂更有可能是最佳摇臂但是在ε-greedy算法中，并没有体现出第1与第3号摇臂的不同—只要它们不是“当前认为最佳”的摇臂，在它们上面分配的次数就是一样多的摇臂编号实验次数10.71020.51030.21040.11050.810回顾上节给出的算法结果：最后不仅需要选择一个最好的摇臂，还要尽力比较所有候选的摇臂不应该根据摇臂能够带来多大的收益来对每一个摇臂分配实验次数，而应该根据它“有多大可能是最佳的摇臂”摇臂编号实验次数10.755220.582630.21040.11050.7952

Boltzmann策略

Boltzmann策略

Boltzmann策略上置信界策略（UCB）UCB策略（UpperConfidenceBound）

UCB策略

UCB策略的理解

UCB策略的理解

总结

实践案例：多臂老虎机问题策略实现案例简介利用Python实现多臂老虎机问题的4种策略：随机选择、ε-greedy、Boltzmann和UCB摇臂的个数为5，真