多臂赌博机问题

1强化学习第2章多臂赌博机2概述一个K臂赌博机问题动作-值方法增量实现方法跟踪不稳定问题最优初始值方法置信上界动作选择梯度方法联系搜索总结3概述区分强化学习和其他学习的方式的一个特征是它评价动作而不是通过给定正确动作来进行指导。纯评价反馈：采用的动作有多好纯指导反馈：应采用的正确动作监督学习采用指导的方式。本章的研究背景：只在一个场景中行动42.1:K臂赌博机问题问题描述：在n个不同选择中选择一个动作.根据动作会得到一个数字奖赏，该奖赏服从一个分布.目标是最大化某一时段的预期奖赏总和.另外一种类比是医生对病人试验性治疗.是探索好还是利用好？52.1:K臂赌博机问题K臂赌博机中几个相关概念：动作的值：一个动作被选择时的一个预期或平均奖赏.At:在时间步t时选择的动作.Rt:在时间步t时所获得的奖赏.q*(a):动作a的期望回报,q*(a)=E[Rt|At=a],真实获得的.Qt(a)：动作a在t时刻的估计值.贪婪动作：在时间步t中选择估计的值最大的动作。利用：选择贪婪动作。探索：选择非贪心动作。探索好还是利用好？取决于：估计的精确值、不确定性和剩余操作次数62.2动作-值方法动作值的估计方法：抽样平均法：每个估计是相关奖赏的简单平均。分母为0时可以定义为一个默认的值t之前动作a被选择的次数。T之前动作a所获得回报之和。大数定律的保证：分母→∞，Q(a)收敛到Q*(a)72.2动作-值方法选择动作的方法：动作与奖赏分布：贪心法：选择当前估计值最大的动作。ε-贪心法：以ε的概率随机均匀的选择与动作值的估计无关的动作。82.2动作-值方法进行了2000次实验每次实验操作1000次q*(a)~N(0,1)行动a的立即奖赏~N(q*(a),1)92.3增量实现普通方法计算Q：增量实现：102.4跟踪不稳定问题不稳定强化学习问题中近期奖赏的权重比长久以前的权重应该更高。令步长参数为一个定值，由增量更新公式得：和为1112.4跟踪不稳定问题随机逼近理论中保证收敛的条件：并且1)(kka12)(kka保证执行次数足够多保证最终收敛所用的次数足够少kak/1)(满足两个条件)(ak不满足第二个条件，不会完全收敛，但是会不断的变化以响应最近获得的奖赏，在不稳定的环境下是我们希望的。122.5乐观的初始值初始值的设定：一般情况下设置为0还可以设置为一个比较乐观的值如5，这样会鼓励探索。132.6置信上界动作选择根据接近最大值的程度与估计的不确定程度选择一个最有潜质的动作：在强化学习中，该方法有一定的困难：很难去解决不稳定问题很难去解决大的状态空间动作a在t时刻被选择的次数，如果Nt(a)=0，a被认为是最大动作控制探索程度，C0142.6置信上界动作选择152.7利用梯度思想：对每个动作设置偏好，按照概率选择动作更新偏好公式：T时刻选择动作a的概率一个基线162.7利用梯度172.7利用梯度在梯度下降中：其中：182.7利用梯度在梯度下降中：写成期望的形式：带入2.11式：192.7利用梯度202.7利用梯度21二值赌博机问题在二值赌博机问题中，称两个奖赏为成功与失败监督学习处理方式：如果是成功的，推测这个动作是成功，如果得到失败推测没选的动作是成功但是奖赏是不确定的话：考虑下列情况：两个动作的成功概率：0.10.20.80.90.10.922二值赌博机问题LR-P方法:按照如下公式更新概率：另外一个动作反向调整，保证两个动作概率之和为1LR-l方法:对成功的操作进行更新，失败的不更新)](1[)()(1ttttttddd选中dt的概率没选中的概率第t次操作的正确操作23二值赌博机问题242.8联系搜索非联系任务：动作选择是在单一场景中联系任务：动作和环境有联系联系搜索介于n-臂赌博机问题和完全强化学习问题之间动作与场景有联系动作只影响直接奖赏搜索最好动作（试错学习）动作不仅影响奖赏，还影响下一场景25软最大化方法ε-贪心的缺点：均匀的选择动作。软最大化动作选择规则（Softmax）：按照概率选择动作。nbbQaQttee1/)(/)(一个正参数，称为温度，高温使得动作完全趋近于等概率Gibbs或Boltzmann分布26强化比较选取一个参考标准做比较，这个标准叫做参考奖赏。奖赏大于参考奖赏则强化。根据软最大化关系决定动作选择的概率更新优先级公式：参考奖赏更新：nbbpapttteea1)()()(软最大化的动作选择概率优先级][)()(1ttttttrrapap][1ttttrrrr27强化比较强化比较(ReinforcementComparison)方法通常不维持动作值的估计，只维持整个奖赏程度的估计28追踪方法追踪方法(PursuitMethod)同时维持动作值的估计和动作优先级（即动作选择概率）)](1[)()(*1*1*11ttttttaaa)](0[)()(1aaattt贪心动作的选择概率非贪心动作的选择概率动作值的更新与前面一样：][11kkkkQrQQ29追踪方法图中的追踪方法在指定参数下是最好的，但是在不同的参数下，各种方法都有自己的优点。302.9总结问题的三种类型：n-臂赌博机：非联系、只影响直接奖赏联系搜索问题：有联系、只影响直接奖赏完全强化学习问题：有联系，影响奖赏和下一场景312.9总结平衡探索和利用：ε-贪心：以一定小的概率随机选择动作UCB方法：巧妙地探索当前为止被选择的动作比较少的动作梯度方法：对动作有偏好，按照概率选择动作最优初始值：在刚开始鼓励探索32ThompsonSampling上下文赌博机问题中包含：上下文X,动作集合A，选择动作后观察到的奖赏集合R。ThompsonSampling中的元素：奖赏函数:带有参数Ө的似然函数P(r|a,x,Ө)过去第i次的观测三元组(xi,ai,ri)，过去的观测集合D={(x,a,r)}先验分布p(Ө),以及关于r分布的参量Ө的集合后验分布奖赏是动作a,文本x，参数Ө的随机函数，我们会选择最大期望奖赏的动作：33ThompsonSampling在参数未知的情况下如果只关注最大期望奖赏(利用)：由于探索与利用的平衡问题，那么就有概率选择动作了：I为指示函数34ThompsonSampling取样算法：标准版的K臂伯努利问题：第i次动作的奖赏遵循均值为Ө的伯努利分布，可以通过Beta分布来模拟每个动作的平均奖赏。Beta分布与二项分布的共轭分布。这样更新分布时会形成一条链：后验分布可以作为下一次计算的先验分布35ThompsonSampling对于伯努利分布的ThompsonSampling：36ThompsonSamplingThompsonSamplingVSUCBUCB：后悔函数：没有选择最优动作而后悔之前的选择，没有选择利用。动作选择次数√(1/t)总回报37ThompsonSampling38Gittinsindex解决多臂赌博机的一个思想是采用MDP：我们希望找到一个值函数：第i臂的状态折扣因子39Gittinsindex定义Gittinsindex：关于终止时间：第一次满足的时间步第i个臂在状态xi下的gittins指数一个终止时间40Gittinsindex思想：每一时刻，选择Gittinsindex值为最大的。为了选择动作，我们要计算所有臂在各种状态下的Gittinsindex。过程：开始时，要给出初始回报和迁移概率。选择最大的回报的动作，计算该状态的Gittinsindex，然后计算转移到下个状态的Gittinsindex，依次迭代，每次选择Gittinsindex值是最大的动作如果状态空间无限，可以采用类似值迭代算法逼近Gittinsindex。41Gittinsindex比如：G1:10,10,9,5,5,3G2:20,15,7,4,2,2选择：20，15，10，10，9，7，5，5，4，3，2，2