bandit算法(老虎機問题)

admin

bandit問题最先在1952年被Herbert Robbins提出，被大量用于临床實验，投資组合辦理，举薦體系等范畴中，也包含AlphaGo。

山君機（bandit）是赌场里常见的一種呆板，玩家将硬币投入後拉下拉杆，接着會随機呈現分歧圖案，若是遏制時呈現不异圖案，则可以按照相干赔率得到特定的收益（reward）。简略點說就是每台山君機你能赚錢的几率纷歧样，你该怎样样讓你赚更多的錢就是Bandit問题。

若是用告白投放去理解的话可能更易一些，假如你有機遇给统一個用户投放100個告白，這100個告白细分在十種種别下，好比說册本類告白，活动類告白等等等等，你在投放告白的進程中要去搞大白用户到底喜好哪一類此外告白，讓CTR點击率最大化這就是bandit問题。

可是有一個問题就是在你刚起頭玩山君機，你不晓得每台山君機讓你赚錢的几率是几多，或刚起頭投放告白的時辰，你不晓得每一個用户更偏心于哪種類型的告白，因而就引出了"摸索"(七日孅減肥茶,exploration)的觀點治療龜頭炎,，简略来讲就是试一下，试玩一下山君機看看他收益几率高不高，试着投放一種類型的告白，看看用户點不點進去看，堆集足够次数的摸索，對付每台呆板的收益几率，每一個告白的點击率有了必定的领會以後，就引出咱们另外一個觀點“開辟”（exploitation），也就是你經由過程前面的“摸索”已晓得哪一個山君機收益几率最高，那末接下来你就一向玩這個山君機，哪一種類型的告白用户最喜好，那末接下来你就一向给這個用户投放這類告白（换句话說就是一向举行“開辟”），如许就可以最大化收益了。

現實上這就是举薦體系范畴中两個經典問题之一的EE（exploration-exploitation）問题，（另外一個是用户的冷启动問题，接下来也會讲到）

若何更好的處置EE問题就是Bandit問题的焦點，简略来讲，暖手寶,若是摸索的太多，你可能就會把不少時候挥霍在低收益几率的山君機上（或是低點击率的告白）；反之，若是摸索的太少也是問题，可能會错事後面的高收益几率的山君機（高點击率的告白）。

基于此提出了

ε-first 中的 ε ，指的是摸索次数占总次数的百分比。

假如玩家只能玩1000次山君機，ε = 10%，那末在举行前100次遊戲時玩家城市處在摸索阶段，摸索分歧的山君機的收益几率 （分歧告白的點击率），在以後的900次遊戲里，全数玩收益几率最高的那台山君機（投放最高點击率的告白），如许只要找到最合适的ε 值， 就可以将收益最大化。

可是ε-first 實在有两個比力大的問题，一是在前100次遊戲里，是不是真的摸索足够了？若是今天有250種可能收益几率（250種點击率几率     ），那末前100次遊戲中咱们就有可能不克不及找到最優解决方案（最高收益山君機或最     高點击率的告白），另外一個問题是，在這前100次的摸索中現實上咱们很大要率是只能得到很低的收益，也就是說這100次摸索咱们可能绝大屡次都挥霍在低收益的计谋上了。

那末基于這两個問题，提出了

ε-greedy：邊學邊玩 （贪心）

ε-greedy 是但愿可以或许在极力開辟的同時，偶然也去试着摸索，是以在每轮選擇時，有ε 的几率随機選擇一種方案去摸索（無论收益的），有1-ε 的几率是去選擇收益最大的方案開辟。

如许的话 ε-greedy 就解决了方才提到的两個問题，第一個，摸索次数是不是不敷，ε-greedy 在每轮起頭都有機遇去摸索，只要没有到达最大收益，始终是有必定几率去摸索。第二個，ε-first 的摸索阶段其實是挥霍了很大的收益，ε-greedy 则是在每轮起頭城市按照你設置的 ε值 的巨细去举行對應几率的@摸%9K62q%索或開治療肩頸痛,%Kp9iR%辟@，如许比拟于 ε-first 摸索阶段的挥霍，提高了收益。

可是，可是，可是

但是跟着次数n的增长，你對分歧方案的收益几率也就愈来愈领會，這時辰摸索的感化也就愈来愈小，那末你每轮起頭時辰依然有 ε 的几率去做摸索的话也就是在挥霍收益了，是以ε-greedy 就被扩大為了εn-g搓泥神器,reedy ，也就是在每轮起頭時，有 εn 的几率去摸索，1 - εn 的几率去開辟（選擇最高收益的方案），如许跟着轮次的增长，摸索的几率也就低落，也就到达了咱们最大化收益的目標

ε 設置的大模子就會有更大的機动性（能更快的摸索到未知，顺應變革），ε 小的话會有更好的不乱性（有更多機遇去"開辟"）