2-多臂老虎机

符号

  • : 动作集合 : 奖励概率分布,动作 对应一个奖励分布
  • 对动作 ,定义其期望奖励为
  • 最优期望奖励
  • 懊悔
  • : 对 的期望奖励估值

名称

  • MAB: 多臂老虎机
  • UCB: 上置信界法

问题表述

多臂老虎机是无状态的强化学习,即与环境交互不会改变环境。在下述算法里,每个老虎机的奖励服从伯努利分布,即以 的概率获得

贪心算法

Misplaced &a_t = cases( arg max_(a in cal(A)) Q^"hat" (a) & "采样概率" 1 - epsilon, "从" cal(A) "随机选择" & "采样概率" epsilon )

的概率随机探索一个。结果由于随机的部分,懊悔是线性增长的。

随时间衰减的 贪心算法

测试时 (老虎机个数),结果累计懊悔是 形式增长的。

image.png

上置信界算法

https://hrl.boyuai.com/chapter/1/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA/#25-%E4%B8%8A%E7%BD%AE%E4%BF%A1%E7%95%8C%E7%AE%97%E6%B3%95 中已经最小化讲清楚了。

用到了霍夫丁不等式。每一时刻设一个概率 。对于每个动作 算出一个 s.t. ,根据霍夫丁不等式必有: 至少以 概率成立,称不等式右边为期望奖励上界(其实是大概率上界)。当 增大时该可能性极大。

实操时, ,每次选择 其中 为控制不确定性比重的系数。ipynb 中

累计懊悔也是 形式:

image.png

汤普森采样算法

若拉杆 次奖励为 次奖励为 ,则大胆假设拉杆的奖励概率(注意奖励概率为 ,每次要么得 要么得 )的概率分布为

那么每步怎么做决策呢?我们已经大胆假设了所有拉杆的奖励的期望的分布,那么就直接对所有拉杆进行一次 分布上的采样。拉动采样最大的那个