多臂赌博机问题.ppt

* * 动作值法为e贪心e=0.1 Rrl在A点较好 * 非联系任务：环境是固定的 联系任务：动作会改变环境，动作与场景联系起来 例子，有线索，学习策略：改变动作时改变颜色，用颜色标记每个任务，与该任务的最大动作联系起来. 联系有哪些信誉好的足球投注网站是 1：搜做最好动作与这些动作是最好动作时的环境联系起来（因为是不稳定的） 联系有哪些信誉好的足球投注网站要学习策略，且一个动作只影响直接奖赏。 有联系、只影响直接奖赏 * 低温使得每个动作的概率更加不同 分布可以变成其他的分布。 * 参考奖赏很自然的选择奖赏的平均值 小于参考奖赏应该削减 不管选择了哪个动作，参考奖赏都要被更新 * 非联系任务：环境是固定的 联系任务：动作会改变环 B=0.1 A=0.1 境 * 它根据优先级不断的追踪贪心动作，就是不断的加强贪心动作的概率 * 追踪方法：b=0.01 采用抽样方法更新Q * 联系指的是环境与动作之间的练习 * UCB目前比较好 * 每次选择一个上下文X集合中的一个x，执行动作a后得到奖赏r，目标是找到一个选择动作的策略，累计奖赏最高 * 指示函数是定义在某集合X上函数，表示其中有哪些元素属于某一子集A。 * 不断的更新观测的集合，根据观测的集合，然后计算后验分布来选择ci ta ，根据cita 和上下文选取期望值最大的那个动作，观察到回报后更新观测集合，这样线索就多了 之所以要采样，是因为每次迭代中，我们都得到了一个后验分布，这个后验分布是通过采样方式获得cita的 该过程就是更新三元组的过程 先验分布计算后验分布，采样进行随机选择 后验分布与先验分布同族，则称为共轭分布。 伯努利分布是每个臂有一定的概率pi获得回报1 而且有1-pi的概率获得0回报 * S 为成功次数，F为失败的次数 每次迭代更新Beta分布，根据cita获得 动作 获取回报（因为奖赏均值为cita，选择最大cita就是选择最大奖赏），回报为一成功，次数累计加一，失败的话，失败次数加1，然后在更新beta分布，每次更新的后验分布可以作为下一次的先验分布。 * 模拟中，最优动作的奖赏概率0.5 其他动作为0.5-e R（T）为后悔函数，后悔函数中参数为T,右边的式子为他的一个渐进下届 Pi为第i个杆子奖赏概率（奖赏是一个概率，受到cita控制）， p*为杆子最大的奖赏概率，D（pi||p*）为相对熵（衡量两个概率分布的差异） * 蓝色的Thompson 后悔函数最低，效果较好 ，上下两个变化的是e（一个参数，控制其他动作选择概率），e越小，各手臂之间与最优的那个手臂获得的奖赏概率差异越小，后悔函数变大，因为与最优的差不多，后悔没有探索更大的手臂。 左右探索的是K，手臂越多，应该探索的越多，探索越少越后悔 * 策略pi控制了上确界 我们希望找到一个让值函数的值最大。 假设我们选择了一个臂，那么这个臂会以马尔可夫链那种形式，其他的臂会被冻住 * 分子是一个t步的带折扣的期望累计奖赏，分母是分母是一个期望折扣的和 要计算所有臂i的所有状态的gittins指数 第一,gittins是一种规划 第二 我们要规划出最大的值。 * * 累积回报：20+15β+10β2+10β3+9β4+… * 2.9 总结 平衡探索和利用： ε-贪心：以一定小的概率随机选择动作 UCB方法：巧妙地探索当前为止被选择的动作比较少的动作 梯度方法：对动作有偏好，按照概率选择动作 最优初始值：在刚开始鼓励探索 * Thompson Sampling 上下文赌博机问题中包含：上下文X,动作集合A，选择动作后观察到的奖赏集合R。 Thompson Sampling 中的元素： 奖赏函数:带有参数?的似然函数P(r|a,x,?) 过去第i次的观测三元组(xi,ai,ri)，过去的观测集合D={(x,a,r)} 先验分布p(?),以及关于r分布的参量?的集合 后验分布 奖赏是动作a,文本x，参数?的随机函数，我们会选择最大期望奖赏的动作： * Thompson Sampling 在参数未知的情况下如果只关注最大期望奖赏(利用)： 由于探索与利用的平衡问题，那么就有概率选择动作了： I为指示函数 * Thompson Sampling 取样算法： 标准版的K臂伯努利问题：第i次动作的奖赏遵循均值为?的伯努利分布，可以通过Beta分布来模拟每个动作的平均奖赏。 Beta分布与二项分布的共轭分布。 这样更新分布时会形成一条链：后验分布可以作 为下一次计算的先验分布 * Thompson Sampling 对于伯努利分布的Thompson Sampling： * Thompson Sampling Thompson Sampling VS UCB UCB： 后悔函数：没有选择最优动