求通俗解释下bandit老虎機到底是個什麼东西?
這篇答复節選自本人在知乎專栏上正在延续更新的一個系列文章的引子：要领會MAB（multi-arm bandit），起首咱们要晓得它是强化進修(reinforcement learning)框架下的一個特例。至于甚麼是强化進修：
咱们晓得，如今市道市情上各類“進修”處處都是。好比如今大師都出格認識呆板進修（machine learning）,或很多年之前實在统计進修（statistical learning）多是更易听到的一個词。那末强化進修的“進修”跟其它這些“進修”有甚麼區分呢？這里天然没有甚麼尺度谜底，我给如许一個诠释（也可见Sutton & Barto第二章弁言）：在傳统的呆板進修中，主流的進修法子都是所谓的“有监視進修”（supervised learning），不论是模式辨認，神經收集练習等等，你的分類器其實不會去自动评价（evaluate）你經由過程得到的每一個样本（sample）所举行的练習成果（反馈），也不存在自动選擇动作（action）的選項（好比，可以選擇在收集了一些样本以後去收集哪些特定的样本）。意思就是，在這些傳统的呆板進修法子中（現實上也包含其它無监視進修或半监視進修的不少法子），你其實不會动态的去按照采集到的已有的样本去调解你的练習模子，你的练習模子只是纯真被动地得到样本并被教诲(instruct，作為比拟，active learning重要就是来解决這一問题的）。
而强化進修重要针對的是在一個可能不竭演變的情况中，练習一個能自动選擇本身的动作，并按照动作所返回的分歧類型的反馈（feedback），动态调解本身接下来的动作，以到达在一個比力持久的時候段內均匀得到的反馈質量。是以，在這個問题中，若何evaluate每次得到的反馈，并举行调解，就是RL的焦點問题。
這麼讲可能還比力抽象，但若大師認識下围棋的AlphaGo，它的练習進程即是如斯。咱们認為每局棋是一個episode。全部的练習周期就是不少不少個epsiode。那末每一個episode又由不少步（step）组成。
动作——指的就是阿法狗每步下棋的位置（按照敌手的落子而定）
反馈——每次epsiode竣事，输赢子的数量。
明显，咱们但愿能找到一個RL算法，使得咱们的阿法狗可以或许在比力短的epsisode数量中經由過程调解落子的计谋，就到达一個均匀比力好的反馈。固然，對這個問题来讲，咱们的动作空間（action space，便可以選擇的动作）和状况空間（state space，即棋盘的落子状况）的可能性都是极為大的。是以，AlphaGo的RL算法也是很是繁杂的（比拟于MAB的算法来讲）。
至于甚麼是MAB/山君機問题：
咱们先斟酌最根基的MAB問题。如上圖所示，你進了一家赌场，假如眼前有 K 台山君機（arms）。咱们晓得，山君機本色上就是個命运遊戲，咱们假如每台山君機 i 都有必定几率 p_i 吐出一块錢，或不吐錢（ 几率1-p_i ）。假如你手上只有 T 枚代币（tokens），而每摇一次山君機都必要耗费一枚代币，也就是說你一共只能摇 T 次，那末若何做才能使得指望回報（expected reward）最大呢？
這就是最經典的MAB场景。那末問题的焦點是甚麼呢？天然，咱们應當要假如 p_i 们是不太同样的（否则怎样摇都同样了），即有一些山君機比力“好”（更易吐錢），有一些则比力“差”（不太轻易吐錢）。回到RL的框架，咱们的动作是甚麼？即每次摇哪台山君機。咱们的反馈呢？即咱们摇了某台特定的山君機當回合可以察看它吐了錢没有。
這里固然另有個首要的统计學/哲學問题：即咱们是贝叶斯人（Bayesian）仍是频率學家（frequentist）。對贝叶斯人来讲，咱们在一進入赌场就對每台山君機扔錢的几率 p_i 就有一個先验散布（prior distribution）的假如了，好比一個很常见的咱们可以用Beta散布。若是咱们認為大要率 p_i 都應當是0.5，即對半開，而不太可能呈現一些很极真個环境，咱们便可以選擇Beta(1,1)散布作為咱们的先验散布。然後在咱们真正摇了山君機以後，按照响應的反馈，咱们便可以调解 p_i 们响應的後验散布（posterior distribution）。好比若是某台呆板摇了四五次一向吐不出錢，咱们就應當将這台呆板的吐錢几率的散布往左推，由于它的 p_i 大要率應當是小于0.5的。那末，你的使命即是要在有限的時候內找出 p_i 後验散布比力靠右的那些呆板（由于他们更易吐錢），而且尽量多的去摇這些比力赚錢的呆板。
而若是你是频率學家，就没甚麼先验或後验散布了，你假如你一起頭對這些呆板的吐錢几率全無所聞。你認為每一個呆板的 p_i 是個肯定的值止咳貼,。那末，你的使命就是要在有限的時候內找到那些高 p_i 的呆板，并尽量多的去摇它们，以得到更多的回報。那末這里咱们注重到這種問题的一大特色，即咱们只有 T 次摇呆板的機遇，若何去均衡這 T 次中exploration（摸索）和exploitation（發掘）的次数。摸索象征着广度，好比若是你是频率學家，你一起頭甚麼都不晓得，你最少每一個呆板都必要略微摇几回（假如 T>K ，否则問题就没法搞定了）才能對每一個呆板吐錢几率有個大要感受。然後，你可能會缩小你的搜刮范畴，再几台呆板里重點實行，最後可能就專門摇一台你感觉最轻易吐錢的呆板了。固然，咱们以後會看到這類法子也未必是最佳的。不外這個答复里咱们不谈详细的算法，是以這個問题先抛给大師思虑了。
本節最後，咱们指出這個MAB問题可能的一些（更繁杂的）變種。首當其冲的在于，咱们前面的會商默许了情况是不會變革的。而一些MAB問题，這個假如可能不可立，這就好好比果一名玩家發明某個呆板的 p_i 很高，一向摇以後赌场可强人為低落這台呆板吐錢的几率。在這類环境下，MAB問题的情况就是跟着時候/玩家的举动會產生變革。這種問题，在公道的假如下，也是有很多钻研和响應的算法的。今朝做的至多的假如，也就是所谓的adversarial bandit（就不是stochastic bandit了），就是說這些 p_i 會被一個“敌手”（也能够當作天主）設定好。若是這是事前設定好，而且在玩家起頭有动作以後也没法更改，咱们叫做oblivious adversary setting; 若是這個敌手在玩家有动作以後還能随時更改本身的設定，那就叫做adaptive adversary setting, 一般要做成zero-sum game了。别的，近来也有止咳化痰小零食,一些随機但nonstationary的假如下的事情。
此外MAB有一類很首要的變種，叫做contextual MAB(cMAB)。几近台北外送茶,所有在線告白推送（dynamic ad display）均可以當作是cMAB問题。在這種問题中，每一個arm的回報會和當前時段呈現的主顾的特性（也就是這里說的context）有關。一样，今天咱们不開展讲cMAB，這會在以後花文章專門會商。
此外，若是每台山君機天天摇的次数有上限，那咱们就获得了一個Bandit with Knapsack問题，這種問题以傳统组合優化里的背包問题定名，它的钻研也和近来很多钻研在線背包問题的文章有關，以後咱们也會專門會商。另有不少變種，如Lipshitz bandit, 咱们再也不有有限台呆板，而有無穷台（它们的reward function知足利普西茨持续性）等等。。题主既然要最普通的版本，以是這里就不赘述了，有樂趣深刻领會的同窗们可以斟酌存眷我的專栏系列文章，主如果讓大師有更好的筹备去读一些專門的册本文献~
關于這個問题，咱们想采纳微软亚洲钻研院資深钻研員陈卫在中國理论计较機年會上的陈述“在線组合進修”举行答复，解读多臂山君機和组合在線進修之間的瓜葛。
————這里是正式答复的朋分線————
赌场的山君機有一個外号叫单臂匪贼（single-armed bandit），由于它即便只有一只胳膊，也會把你的錢拿走。而多臂山君機（或多臂匪贼）就從這個外号引伸而来。假如你進入一個赌场，面临一排山君機（以是有多個臂），因為分歧山君機的指望收益和指望丧失分歧，你采纳甚麼山君機選擇计谋来包管你的总收益最高呢？這就是經典的多臂山君機問题。
這個經典問题集中表現了在線進修及更宽泛的强化進修中一個焦點的掂量問题：咱们是應當摸索（exploration）去测验考试新的可能性，仍是應當守成（exploitation），對峙今朝已知的最佳選擇?在多臂山君機問题中，摸索象征着去玩還没玩過的山君機，但這有可能使你花太多時候和款項在收益欠好的呆板上；而守成象征着只玩今朝為止给你收益最佳的呆板，但這又可能使你落空找到更好呆板的機遇。而雷同决议在平常糊口中到處可见：去一個餐厅，你是否是也纠结因而點認識的菜品，仍是點個新菜？去一個處所，是走熟知的老路仍是選一條新路？而摸索和守成的掂量就是在線進修的焦點。
多臂山君機的提出和钻研最先可以追述到上世纪三十年月，其钻研模子和法子已有不少。此中一類首要的模子是随機多臂山君機，即情况赐與的反馈顺從某種随機但未知的散布，在線進修的進程就是要學出這個未知散布中的某些参数，并且要包管全部進修進程的总體收益尽可能高。這此中最着名的一個法子是UCB（Upper Confidence Bound）法子，可以或许經由過程严酷的理论论证阐明UCB可到达靠近理论最優的总體收益。
先容了多臂山君機問题，那组合在線進修和它之間有何联系關系呢？咱们继续来看一下组合多臂山君機（CMAB）問题。在组合多臂山君機問题中，你一次拉动的不是一個臂，而是多個臂构成的调集，咱们称之為超臂（super arm），本来的每一個臂咱们称之為基准臂（base arm），以示區分。拉完這個超臂後，超臂所包括的每一個基准臂會给你一個反馈，而這個超臂总體也给你带来某種复合的收益。
那末若何解决组合多臂山君機的問题呢？你可能起首想到的就是把每個超臂當作是經典多臂山君機問题中的一個臂。可是超臂是多個基准臂的组合，而如许组合的数量會大大跨越問题自己的范围——组合問题中經典的组合爆炸征象，是以傳统的法子其實不合用。以是在線進修不克不及在超臂這個條理举行，而必要在基准臂條理长進行，并必要與離線组合優化奇妙地連系。咱们在ICML2013的论文中给出了组合多臂山君機的一般框架和基于UCB法子的CUCB算法。CUCB算法将组合優化和在線進修無缝對接實現了前面圖示中的反馈回路。较以前的触及组合多臂山君機的钻研，咱们的模子合用范畴更广，特别是咱们經由過程给出收益函数的两個一般前提，可以或许涵盖非線性的收益函数，這是第一個能解决非線性多臂山君機問题的方案。咱们的事情，包含以後咱们和别人的後续事情，都夸大對在線進修部門和離線優化部門的模块化處置和無缝對接。也即咱们将離線優化部門作為一個黑盒子神谕（oracle），這部門可以由具备相干范畴常識的專家来完成。而一旦離線優化問题可以切确解决或類似解决，咱们便可以把這個離線算法看成黑盒子拿過来和咱们在線進修法子相連系，到达有严酷理论包管的组合在線進修结果。這使得咱们的法子可以合用于一多量已有離線優化算法的组合在線進修問题，好比最短路径、最小天生树、最大匹配、最大笼盖等問题的在線進修版本，而不必要對每一個問题零丁再設計在線進修算法。
在论文“Combinatorial Multi-Armed Bandit: GeneralFramework, Results and Applications”中,咱们進一步将组合多臂山君機模子扩大為容许有随機被触發臂的模子。這一模子可以被用于在線序列举薦、社交收集病毒式營销等场景中，由于在這些场景中前面动作的反馈可能會触發更多的反馈。但是在其理论成果中，咱们包括了一個和触發几率有關的項，而這個項在序列举薦和病毒營销场景中城市過大，造成在線進修淡斑藥膏，结果欠好。在本年刚被登科的NIPS论文“ Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications”中，咱们完全解决了這個問题：一方面咱们论证了序列举薦和病毒營销等知足某種特定前提的問题都不會有這個欠好的項，另外一方面咱们指出在更一般的组合多臂山君機中這個項又是不成防止的。這是今朝钻研可触發臂的组合多臂山君機中最佳的一般成果。
除此以外，咱们還在與组合多臂山君機相干的方面做了若干事情，好比如安在反馈受限环境下到达好的進修结果；若何解决先摸索再找到最好方案的组合摸索問题；當離線優化基于贪默算法時，若是更好地将離線贪默算法和在線進修相連系；如安在有上下文的场景中解决组合序列举薦問题；和當超臂的指望收益取决于每一個基准臂的随機散布而不但是每一個基准臂的散布均值時，若何一样有用地举行组合在線進修。
————這里是答复竣事的朋分線————
以上答复摘選自微软钻研院AI頭條，组合在線進修：及時反馈玩转组合優化。
感激大師的浏览。
本账号為微软亚洲钻研院的官方知乎账号。本账号安身于计较機范畴，出格是人工智能相干的前沿钻研，旨在為人工智能的相干钻研供给典范，從專業的角度促成公家對人工智能的理解，并為钻研职員供给會商和介入的開放平台，從而共建计较機范畴的将来。
微软亚洲钻研院的每位專家都是咱们的军師团，你在這個账号可以浏览到来自计较機科學范畴各個分歧標的目的的專家们的看法。请大師不要怜惜手里的“约抽水肥,请”，讓咱们在分享中配合前進。
也接待大師存眷咱们的微博和微信 (ID:MSRAsia) 账号，领會更多咱们的钻研。
頁:
[1]