首先探索和利用

探索Exploration——发现***的分布，探索新的可能
利用Exploitation——从最beneficial的***上寻求利益最大，在已知中找最优

随机MAB

最简单的MAB(Multi-Armed Bandits

Arm可以看作一个握杆，***的一个动作

每个***有k个Arm作为可能的行动{1..k}

每个Arm_i都产生奖励，服从一个均值为u_i的分布P_i

有1...T轮：
——每轮都做一个动作i_t
——从Arm{1..k}种选择一个Arm_i
——然后收到服从P_i,t的一个奖励

我们的目标就是最大限度的减少累积遗憾Regret：
最佳事后预期累计回报—***的预期累计奖励

最佳事后预期累计回报：
就是在啥都知道的情况下，每轮都做最优选择得到的回报 uT 这里u=max(x_i*u_i)
***的预期累计奖励：
啥也不知道的情况下，每轮随机做选择得到的回报期望

这是最简单的随机多臂***基础，就是尽可能的去实现像全部已知一样的好效果。

Greedy 贪心算法

改进了一下基础MAB

把一个动作i已经观测到的报酬取平均作为该动作i的估计值
而没有观测过的动作，则使用一个初始值Q0作为估计值，直到使用过之后，使用观测值作为估计值
每轮观测之后更新估计值

贪心算法就是选择估计值最优的动作，但这样有可能会陷入局部最优——尝试到大于初始值的动作之后，不再探索。

𝜀-Greedy 加参数的贪心

前面对估计值的设置不变
但是每轮有𝜀概率再重新在{1..k}种去做随机探索，1-𝜀概率从已知的最优种去做选择

超参𝜀控制探索和利用的概率

改进过的Greedy，有一定可能会去探索，跳出局部找到全局最优解

注意：如果找到全局最优，可能还会继续探索 所以超参不能太大 不然后期会浪费 降低收益率

𝜀=0就是普通的贪心算法

贪心算法的效果

探索概率𝜀的取值

可以看到
1.纯贪心算法增长快，但是整体奖励低
2.𝜀-贪心算法的长期回报更好
3.𝜀=0.01-贪婪开始比较缓慢（很少探索），但最终会优于𝜀=0.1-贪婪（过度探索后的开发）

初始值Q0的取值

悲观主义：初始Q低于可观察到的回报➡️仅尝试一只手臂
Q0很小 可能就会在有收益后 只尝试那一个

乐观：初始Q高于可观察的奖赏➡️探索更多手臂
Q0足够大 就能探索很多 然后找到最好的

中段初始Q➡️最多探索一次
但纯贪心算法从来没有探索手臂超过一次

贪心的局限性

1.我们可以通过乐观的初始值Q0和减少𝜀来改进基础的贪心算法

2.探索和利用在这里过于“不同”
——探索行动完全无视有希望的动作，对所有Arm一视同仁：其实应该倾向于更有潜力的
——只有在“冷启动”的情况下初始值技巧才有帮助。

3.利用对估计的可信度视而不见
——应该根据估计可信度来判断
(比如找收益最大 只尝试几次可能只是巧合)

UCB 上置信边界算法

动作的估计值由两部分组成

给估计的收益u加上了置信区间(有上下限)，如果尝试次数多了，区间就会变小
开方内很大就是没怎么尝试，潜力很大
u很大就是尝试过，收益真的很大

挑选上限最大的：u很大或者开方内的很大，或者都大

同时做到了利用和探索 同时进行 ——UCB的优点
缺点是可能会停在某个不好的点一段时间 一开始会有点低 但最终会超过 可以看和贪心算法的对比图