bandit基础看了一下并不是很难，先记录一下，文集里没有贴个公众号地址吧：https://mp.weixin.qq.com/s?src=11×tamp=1635867497&ver=3412&signature=yJjYIHXEZzMB3U5OPfJqGSxONeUnQ6tzYyz7wT2aFB96E25wLA3xgrIDZkMcVXHE34a0I6LVZwvKUzJdGzqAZh3ej8U6wLgfO7rsvURUK-MKhUVU40IqL1SJynjiClzQ&new=1
bandit起源于多臂老虎机问题（Multi-armed bandit），要找到一个合适的策略去确定摇哪个老虎机，如果经过一些初始试验得到了当前每个老虎机的观察概率，那么一直摇那个高的就是exploitation，但是因为真实概率和观察概率的差别可能还有更高的，就要去exploration。
那么怎么去摇呢，有以下几种基于bandit（这个直译过来应该是老虎机的意思吧，反正只要能指代这些算法就行）的算法：
1.朴素bandit：先随机试若干次找到收益最高的，然后一直摇那个
2.epsilon-greedy算法：先随机试若干次，然后以epsilon的概率去随机找一个摇，以1-epsilon的概率摇收益最高的那个，摇完之后更新现有收益期望；这个有一个问题在于每次都还是随机找一个摇，没用到更新之后收集到的信息（比如之前摇多次有的一直出钱，有的从来不出；有的是摇10次出10次，有的是摇1次出1次）
3.Thompson采样：之前一直听到这个词，其实原理也不太难；这个要用到Beta分布，首先说一下什么是Beta分布：https://www.zhihu.com/question/30269898（这里我觉得前两个回答都在说Beta分布的性质，第三个才在说什么是Beta分布）
我的理解是Beta分布就是某个概率的概率分布，举个例子一枚硬币是不均匀的，有一定的概率p是正面朝上，那么不停地抛硬币得到正面/反面的数据之后，p会有一个分布(p不会就完全等于正/(正+反))，这个分布就是Beta分布；
引用回答里的原话是：所谓的以α,β为参数的Beta分布f(p,α,β) ，其实描述的就是我们在做抛硬币实验的过程中，我们当前如果已经观测到α+1次正面，β+1次反面，那么此时硬币正面朝上的真实概率的可能性分布。
然后前两个回答说了Beta分布一个很厉害的性质：那就是如果还是独立同分布地进行实验（比如继续抛硬币）那么每次更新Beta分布的两个参数wins和loses，所得到的分布还是Beta分布；再引用原话：对于一个我们不知道概率是什么，而又有一些合理的猜测时，beta分布能很好的作为一个表示概率的概率分布。
然后回到摇钱问题就假设每个老虎机吐钱（可以是吐or不吐，可以是吐的钱数）的概率p都服从Beta(wins,loses)分布，每摇一次有收益就wins+1，否则lose+1；下一次摇就选择所有老虎机在现有分布里产生的最大值对应的那个去摇；这个就利用到了每次收集到的信息。
4.UCB(Upper Confidence Bound)：假设当前老虎机观察到的吐钱概率是p'，而真实概率是[p'-delta,p'+delta]，那么我们假设每次都乐观地取上限作为收益（起名由来），且根据https://zhuanlan.zhihu.com/p/32356077，delta取sqrt(2*lnT/n)是一个比较好的值，T是总摇的次数，n是当前老虎机摇的次数，越摇这个数会越小，没摇的会变大，也就是当前的会接近到真实概率，没摇的会增大摇到的机会。
附带再说下这个delta的取值，根据上面的链接是这么来的，主要是这个Hoeffding Bound假设：
这个举例说明白了，delta=sqrt(2*lnT/n)是以概率1-2/T^4成立的，也就是说delta这个取值让p在一个观察概率很合理的范围内，并且满足我们越观察越接近真实等直觉。
UCB和Thompson采样的区别在于一个是概率学派一个是贝叶斯学派，前者认为每个老虎机吐钱的概率是固定的，实验无穷次就可以得到这个概率，但是因为无法实验无穷次，于是就有一个置信区间；后者认为老虎机吐钱的概率是一个分布，实验次数越多在真实θ附近的概率密度就会越大。
