bandit基礎(chǔ)看了一下并不是很難，先記錄一下，文集里沒(méi)有貼個(gè)公眾號(hào)地址吧：https://mp.weixin.qq.com/s?src=11&timestamp=1635867497&ver=3412&signature=yJjYIHXEZzMB3U5OPfJqGSxONeUnQ6tzYyz7wT2aFB96E25wLA3xgrIDZkMcVXHE34a0I6LVZwvKUzJdGzqAZh3ej8U6wLgfO7rsvURUK-MKhUVU40IqL1SJynjiClzQ&new=1

bandit起源于多臂老虎機(jī)問(wèn)題（Multi-armed bandit），要找到一個(gè)合適的策略去確定搖哪個(gè)老虎機(jī)，如果經(jīng)過(guò)一些初始試驗(yàn)得到了當(dāng)前每個(gè)老虎機(jī)的觀察概率，那么一直搖那個(gè)高的就是exploitation，但是因?yàn)檎鎸?shí)概率和觀察概率的差別可能還有更高的，就要去exploration。

那么怎么去搖呢，有以下幾種基于bandit（這個(gè)直譯過(guò)來(lái)應(yīng)該是老虎機(jī)的意思吧，反正只要能指代這些算法就行）的算法：

1.樸素bandit：先隨機(jī)試若干次找到收益最高的，然后一直搖那個(gè)

2.epsilon-greedy算法：先隨機(jī)試若干次，然后以epsilon的概率去隨機(jī)找一個(gè)搖，以1-epsilon的概率搖收益最高的那個(gè)，搖完之后更新現(xiàn)有收益期望；這個(gè)有一個(gè)問(wèn)題在于每次都還是隨機(jī)找一個(gè)搖，沒(méi)用到更新之后收集到的信息（比如之前搖多次有的一直出錢，有的從來(lái)不出；有的是搖10次出10次，有的是搖1次出1次）

3.Thompson采樣：之前一直聽(tīng)到這個(gè)詞，其實(shí)原理也不太難；這個(gè)要用到Beta分布，首先說(shuō)一下什么是Beta分布：https://www.zhihu.com/question/30269898（這里我覺(jué)得前兩個(gè)回答都在說(shuō)Beta分布的性質(zhì)，第三個(gè)才在說(shuō)什么是Beta分布）

我的理解是Beta分布就是某個(gè)概率的概率分布，舉個(gè)例子一枚硬幣是不均勻的，有一定的概率p是正面朝上，那么不停地拋硬幣得到正面/反面的數(shù)據(jù)之后，p會(huì)有一個(gè)分布(p不會(huì)就完全等于正/(正+反))，這個(gè)分布就是Beta分布；

引用回答里的原話是：所謂的以α,β為參數(shù)的Beta分布f(p,α,β) ，其實(shí)描述的就是我們?cè)谧鰭佊矌艑?shí)驗(yàn)的過(guò)程中，我們當(dāng)前如果已經(jīng)觀測(cè)到α+1次正面，β+1次反面，那么此時(shí)硬幣正面朝上的真實(shí)概率的可能性分布。

然后前兩個(gè)回答說(shuō)了Beta分布一個(gè)很厲害的性質(zhì)：那就是如果還是獨(dú)立同分布地進(jìn)行實(shí)驗(yàn)（比如繼續(xù)拋硬幣）那么每次更新Beta分布的兩個(gè)參數(shù)wins和loses，所得到的分布還是Beta分布；再引用原話：對(duì)于一個(gè)我們不知道概率是什么，而又有一些合理的猜測(cè)時(shí)，beta分布能很好的作為一個(gè)表示概率的概率分布。

然后回到搖錢問(wèn)題就假設(shè)每個(gè)老虎機(jī)吐錢（可以是吐or不吐，可以是吐的錢數(shù)）的概率p都服從Beta(wins,loses)分布，每搖一次有收益就wins+1，否則lose+1；下一次搖就選擇所有老虎機(jī)在現(xiàn)有分布里產(chǎn)生的最大值對(duì)應(yīng)的那個(gè)去搖；這個(gè)就利用到了每次收集到的信息。

4.UCB(Upper?Confidence?Bound)：假設(shè)當(dāng)前老虎機(jī)觀察到的吐錢概率是p'，而真實(shí)概率是[p'-delta,p'+delta]，那么我們假設(shè)每次都樂(lè)觀地取上限作為收益（起名由來(lái)），且根據(jù)https://zhuanlan.zhihu.com/p/32356077，delta取sqrt(2*lnT/n)是一個(gè)比較好的值，T是總搖的次數(shù)，n是當(dāng)前老虎機(jī)搖的次數(shù)，越搖這個(gè)數(shù)會(huì)越小，沒(méi)搖的會(huì)變大，也就是當(dāng)前的會(huì)接近到真實(shí)概率，沒(méi)搖的會(huì)增大搖到的機(jī)會(huì)。

附帶再說(shuō)下這個(gè)delta的取值，根據(jù)上面的鏈接是這么來(lái)的，主要是這個(gè)Hoeffding Bound假設(shè)：

遙遠(yuǎn)的記憶中上那個(gè)臺(tái)大林老師的課提到過(guò)

這個(gè)舉例說(shuō)明白了，delta=sqrt(2*lnT/n)是以概率1-2/T^4成立的，也就是說(shuō)delta這個(gè)取值讓p在一個(gè)觀察概率很合理的范圍內(nèi)，并且滿足我們?cè)接^察越接近真實(shí)等直覺(jué)。

UCB和Thompson采樣的區(qū)別在于一個(gè)是概率學(xué)派一個(gè)是貝葉斯學(xué)派，前者認(rèn)為每個(gè)老虎機(jī)吐錢的概率是固定的，實(shí)驗(yàn)無(wú)窮次就可以得到這個(gè)概率，但是因?yàn)闊o(wú)法實(shí)驗(yàn)無(wú)窮次，于是就有一個(gè)置信區(qū)間；后者認(rèn)為老虎機(jī)吐錢的概率是一個(gè)分布，實(shí)驗(yàn)次數(shù)越多在真實(shí)θ附近的概率密度就會(huì)越大。