【优化】在線學習(MAB)與强化學習(RL)入门系列

admin

编者案：這會是一個關于在線進修和强化進修的入门向系列，專门给對這两個方面（实在也能够当作是一個方面）感樂趣的同窗们做個科普，和小我向的解读。固然若是你已是在做這些方面钻研了，這個系列可能帮不到你甚么。後续的內容會公布在本人知乎小我專栏和運筹OR帷幄的知乎專栏，而不必定會继续在公家号上更新。這個系列的內容也可能會成为運筹OR帷幄优化理论電子科普丛书的一部门。

這個系列预期最少會有個5~10篇文章（MAB和RL大要各占一半），重要仅仅触及理论系统，而根基不會触及現实算法若何去实現。這邊先说一下我重要會用（举薦）的一些参考文献。

MAB：

重要就是微软钻研院（Microsoft Research）的Aleksandrs Slivkins的這本關于MAB的draft book Introduction to Multi-Armed Bandits （還未正式出书，他近来還一向在完美）： 這是我小我認为今朝市道市情上最合适入门的MAB教科书。整本书的逻辑都很清楚，且数學derivation也尽量都是從first principles動身，對很多成果的proof都是我見過的写的最简便的，Slivkins本人對這個范畴進献也很是大，他對不少细節都有很深刻的思虑，以是才能写出這么neat的讲授向內容吧。小我很是举薦，并将重要在MAB的內容先容他的思绪。

Slivkins以前，另外一位MAB范畴的大神Sebastien Bubeck（也在MSR...）的课本Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems多是市道市情上独一找的到的體系性论述各方面MAB理论的课本。 Bubeck天然也是MAB范畴一名极具缔造力和洞察力的大牛，不外小我認为他的這本课本并無Slivkins的书合适入门，由于Bubeck的课本气概一如他写博客的气概，不少處所很是handwavy，即不给证实细節而跟你“简略聊聊”這些個成果和暗地里的intuition。。。以是建议有必定根本的同窗再去读他的內容，如许可能反而收成會更大一些。

RL:

零根本的环境下，天然Richard Sutton和Andrew Barto的Reinforcement learning: An introduction是不克不及错過的。這两位也是上世纪90年月最先引入RL這個名称的人。這本书的益處是触及的內容很广，近来也正好重版。总之是RL進修者必定不克不及错過的，不外由于內容太多实在我也一向没读完。。

Dimitri Bertsekas近来的新书Reinforcement Learning and Optimal Control。值得注重的是，這本书今朝也仍是在底稿（draft）状况，估计會在来岁正式搞定。Bertsekas老爷子是新晋的2018年冯诺依曼奖得到者，是動态计劃（dynamic progra妹妹ing,DP）范畴的奠定人之一，此中之一的缘由即是他和他的學生/互助者 John Tsitsiklis曾钻研并撰著的范畴Neuro-dynamic Progra妹妹ing(NDP)，這实在就是如今火热的深度强化進修(deep reinforcement learning)的理论前身。John是以本年和Dimitri一块儿获奖（他们一块儿获奖的另外一缘由是他们同時也是并行和散布式计较理论的前驱，這里就不细谈了）。咱们晓得，RL和DP，特别是類似動态计劃（approximate dynamic progra妹妹ing, ADP）实在并無甚么很本色的區分（RL對付很多做節制、优化的人来讲就是DP）。老爷子的新书即是從DP的角度来说RL內里的各類建模和算法，也有很多颇有意思的概念。

前两個质料可能仍是有點經典。是以，我将偏重谈一些比力新的內容。這一方面，好比Benjamin Van Roy, Daniel Russo, Ian Osband都是近来几年對(deep) RL很是有建树的年青學者。特别是這個Ian Osband（如今是Google Deepmind的钻研員，對，Deepmind就是阿谁搞出了AlphaGo的處所）的很多文章很是值得初學者去研读。好比他的PhD thesis，另有這篇（也是他thesis的焦點），颁發在JMLR上的长文Deep Exploration via Randomized Value Functions，在贝叶斯的框架下，不但谈了理论和实行成果，最首要的是大量谈“咱们應当若何做好RL？”。我感觉在钻研任何问题的時辰，在咱们在详细上手以前弄清晰咱们到底要做甚么，要怎样做真的是很首要的。

好了，系列第一篇文章，我相沿Sutton和Barto的书，也從MAB起頭讲起。現实上，MAB问题可以当作RL的一類特例问题，我也将在系列前几篇文章偏重谈谈MAB這個特例，然後再带大師過渡到解决一般Markov Decision Process（MDP）的RL算法。

咱们晓得，如今市道市情上各類“進修”處處都是。好比如今大師都出格認識呆板進修（machine learning）,或很多年之前实在统计進修（statistical learning）多是更易听到的一個词。那末强化進修的“進修”跟其它這些“進修”有甚么區分呢？這里天然没有甚么尺度谜底，我给如许一個诠释（也可見Sutton & Barto第二章弁言）：在傳统的呆板進修中，主流的進修法子都是消除外痔肉球，所谓的“有监視進修”（supervised learning），不论是模式辨認，神經收集练習等等，你的分類器其实不會去自動评價（evaluate）你經由過程得到的每一個样本（sample）所举行的练習成果（反馈），也不存在自動選擇動作（action）的選項（好比，可以選擇在收集了一些样本以後去收集哪些特定的样本）。意思就是，在這些傳统的呆板進修法子中（現实上也包含其它無监視進修或半监視進修的不少法子），你其实不會動态的去按照采集到的已有的样本去调解你的练習模子，你的练習模子只是纯真被動地得到样本并被教诲(instruct，作为比拟，active learning重要就是来解决這一问题的）。

而强化進修重要针對的是在一個可能不竭演變的情况中，练習一個能自動選擇本身的動作，并按照動作所返回的分歧類型的反馈（feedback），動态调解本身接下来的動作，以到达在一個比力持久的時候段內均匀得到的反馈质量。是以，在這個问题中，若何evaluate每次得到的反馈，并举行调解，就是RL的焦點问题。

這么讲可能還比力抽象，但若大師認識下围棋的AlphaGo，它的练習進程即是如斯。咱们認为每局棋是一個episode。全部的练習周期就是不少不少個epsiode。那末每一個episode又由不少步（ste早洩藥,p）组成。

動作——指的就是阿法狗每步下棋的位置（按照敌手的落子而定）

反馈——每次epsiode竣事，输赢子的数量。

明显，咱们但愿能找到一個RL算法，使得咱们的阿法狗可以或许在比力短的epsisode数量中經由過程调解落子的计谋，就到达一個均匀比力好的反馈。固然，對這個问题来讲，咱们的動作空间（action space，便可以選擇的動作）和状况空间（state space，即棋盘的落子状况）的可能性都是极为大的。是以，AlphaGo的RL算法也是很是繁杂的。我今天在系列首篇就不具體會商AlphaGo算法（放到今後，先容更一般的MDP和RL算法以後），而是先先容给大師MAB的问题框架，從這個比拟围棋简略的多的问题中（一類特别的MDP）但愿先给大師一些更直觀的熟悉。

作为引子，咱们斟酌最根基的MAB问题（MAB问题如今也有各類變種，有些已很是繁杂了......）。如上圖所示，你進了一家赌场，假如眼前有K台山君機（arms）。咱们晓得，山君機本色上就是個命運遊戲，咱们假如每台山君機 i都有必定几率 Pi吐出一块钱，或不吐钱（ 几率1-Pi ）。假如你手上只有T枚代币（tokens），而每摇一次山君機都必要耗费一枚代币，也就是说你一共只能摇T次，那末若何做才能使得指望回报（expected reward）最大呢？

這就是最經典的MAB场景。那末问题的焦點是甚么呢？天然，咱们應当要假如Pi们是不太同样的（否则怎样摇都同样了），即有一些山君機比力“好”（更易吐钱），有一些则比力“差”（不太轻易吐钱）。回到RL的框架，咱们的動作是甚么？即每次摇哪台山君新豐馬桶不通,機。咱们的反馈呢？即咱们摇了某台特定的山君機当回合可以察看它吐了钱没有。

這里固然另有個首要的统计學/哲學问题：即咱们是贝叶斯人（Bayesian）仍是频率學家（frequentist）。對贝叶斯人来讲，咱们在一進入赌场就對每台山君機扔钱的几率Pi就有一個先驗散布（prior distribution）的假如了，好比一個很常見的咱们可以用Beta散布。若是咱们認为大要率都應当是0.5，即對半開，而不太可能呈現一些很极真個环境，咱们便可以選擇Beta(2,2)散布作为咱们的先驗散布。然後在咱们真正摇了山君機以後，按照响應的反馈，咱们便可以调解Pi们响應的後驗散布（posterior distribution）。好比若是某台呆板摇了四五次一向吐不出钱，咱们就應当将這台呆板的吐钱几率的散布往左推，由于它的Pi大要率應当是小于0.5的。那末，你的使命即是要在有限的時候內找出Pi後驗散布比力靠右的那些呆板（由于他们更易吐钱），而且尽量多的去摇這些比力赚钱的呆板。

而若是你是频率學家，就没甚么先驗或後驗散布了，你假如你一起頭對這些呆板的吐钱几率全無所闻。你認为每一個呆板的Pi是個肯定的值。那末，你的使命就是要在有限的時候內找到那些高Pi的呆板，并尽量多的去摇它们，以得到更多的回报。那末這里咱们注重到這種问题的一大特色，即咱们只有T次摇呆板的機遇，若何去均衡這T次中exploration（摸索）和exploitation（發掘）的次数。摸索象征着广度，好比若是你是频率學家，你一起頭甚么都不晓得，你最少每一個呆板都必要略微摇几回（假如T>K，否则问题就没法搞定了）才能對每一個呆板吐钱几率有個大要感受。然後，你可能會缩小你的搜刮范畴，再几台呆板里重點实行，最後可能就專门摇一台你感觉最轻易吐钱的呆板了。固然，咱们以後會看到這類法子也未必是最佳的。不外今天的文章里咱们不谈详细的算法，是以這個问题先抛给大師思虑了。

本節最後，咱们指出這個MAB问题可能的一些（更繁杂的）變種。首当其冲的在于，咱们前面的會商默许了情况是不會變革的。而一些MAB问题，這個假如可能不可立，這就好好比果一名玩家發明某個呆板Pi的很高，一向摇以後赌场可强人为低落這台呆板吐钱的几率。在這類环境下，MAB问题的情况就是跟着時候/玩家的举動會產生變革。這種问题，在公道的假如下，也是有很多钻研和响應的算法的。今朝做的至多的假如，也就是所谓的adversarial bandit（就不是stochastic bandit了），就是说這些Pi會被一個“敌手”（也能够当作天主）設定好。若是這是事前設定好，而且在玩家起頭有動作以後也没法更改，咱们叫做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知足利普西茨持续性）等等。。

今天咱们固然不聊算法，可是sample complexity实在也是個颇有意思的话题。同時，也能够帮忙眼睛保健茶飲, 初學者先把握regret（真心想晓得中文這個词是若何翻译的）的觀點。咱们這里仅谈MAB问题的sample complexity, 那末大師也應当會晓得這是和RL问题的sample complexity也是紧密亲密相干的。Sample complexity, 简略来讲，是钻研有哪些事變任何bandit算法都是不克不及做到的。

简略起見，咱们只斟酌最简略的情景，即咱们是频率學家，且情况是stationary的K-arm bandit，也就是说每一個arm的reward散布是IID（自力同散布）的，不會跟着時候和玩家的举動變革。然後，我的文章其实不會會商详细证实這些成果的技能和步调（详细可見Slivkins书的第二章，是今朝能找到的對這種bound最简便的证实），而旨在给出一些更high-level的看法。

凡事都要從最简略起頭。咱们先令K=2，即只有两個arms。MAB的样本繁杂度，現实上可以当作是如许一個信息论/统计學问题：即，咱们有两個Bernouli散布Ber(p1),Ber(p2)（注重咱们假如p1≠p2 ），那末咱们最少必要别離從這两個散布中得到几多样本（samples），咱们才能以较大要率将這两個散布區分隔来？

由于現实上只有两個arm，和MAB问题的特征，現实上，咱们只必要可以或许以较高几率果断出p1和p2哪一個更大就好了。由于一旦咱们能果断出哪一個arm的吐钱几率更大，咱们天然也就晓得了哪一個arm更好，咱们便主動得到了最优算法（一向摇這個更好的arm就好了）。

而這個问题，不就是说，最少要有几多样本，咱们才能高置信度地做如下的假如查驗？

固然到這里尚未竣事，有個小技能即是必要randomization，或说是计较繁杂度理论里最根基的probabilistic method。這個缘由也很直觀，若是咱们機關的例子是肯定性的（deterministic），那末必定要末p1>p2或相反，那末天然在這两種环境下（别離）有两個极为愚笨的算法都不必要任何样本就可以直接“蒙”對，好比前者就是直接猜p1更大的算法，後者就是直接猜p2更大的算法。是以，這里的小技能（trick）就是说咱们機關一個随機化（randomized）的例子，好比说在這個例子里0.5的几率p1>p2 ，而0.5的几率p1<p2 （你可以想象成我用了两套對arm举行index的法子，如许本来的arm 1就@酿%P5妹妹e%成@了arm 2，本来的arm 2@酿%P5妹妹e%成@了arm 1）。如许的话以前那些愚笨的算法就最少會有0.5的几率猜错了。而咱们的方针就是只要证实任何算法都有必定的几率在這個问题上出错就ok了！

想大白了以上几點，加之一些KL divergence（最根基的信息论）常識，包含一些甚么Pinsker不等式，你便可以证实本節的重要內容了。哦，再讓我来先容下regret的觀點。一般来讲，咱们設計较法的方针就是讓指望的regret（一般钻研的是regret的upper bound）比力小。那末sample complexity，说的则是相反的一件事變，即不管甚么算法，對MAB问题，你指望的regret都最少應当有多大（给的是lower bound）。详细来讲，在咱们的K-arm例子中，記最大的 Pi 为P* ，咱们的算法在時刻t選擇的呆板是i(t) ，那末咱们的算法所酿成的regret即是：

即，和某個先知比拟（一起頭就晓得P*），咱们所得到的回报和他得到的回报在T時候段內的差距。

好了，咱们终究可以给出經典的两類lower bound。一類是 T½ 的，一類是logT   。你可能要说了， logT的不是從阶上比T½更低嘛，那岂不是更紧？而現实上，這两類bound实在可以当作一類，由于與问题相干的系数無關，尔後者有關（咱们很快會看到系数详细是甚么）。详细为甚么這两類bound实在可以当作一類，我在後面先容UCB算法的時辰會再说，感受在何處會更易说一些。

注灰指甲修復液,重，這两類lower bound都是成心义的。由于若是你胡乱蒙的话，你的regret最少會跟着時候線性增加（即阶为~T）。是以，這两類也叫做次線性（sublinear）的regret。

定理1. 對這種MAB问题，存在某一個例子，使得任何的算法都知足

定理2. 對這種MAB问题，存在某一個例子，使得任何的算法都知足

這里△(a)的界说是△(a):=P*-Pa ，即這個arma和最佳的arm在指望reward上的差距。這個系数也是我所谓的這種bound現实上內里有跟问题相干的系数。直觀理解，固然 T的阶比前一類bound要紧了，可是這里乘的系数却更大了。

最後，咱们不加阐明的點出，贝叶斯版本的K-arm MAB也有不异阶的這两類lower bound。和，咱们确切有算法，可以到达這两類regret，即它们在理论意义上是最优的（今後的內容！）。

【优化】版块今朝招募副主编，请求：

1. 國表里運筹學、优化理论等相干專業博士在读或以上

2. 有時候有热忱有能力去分享本身的設法，做一些運筹學或人工智能的科普事情

3. 對优化理论此中任何一個范畴比力認識便可

4. 有事情热忱，每周能有時候支出

5. 具备缔造力，可以或许有自力創作專题系列文章的能力

可以在 本公家号後台 复兴關頭词：“MABRL”得到本文参考文献的pdf版本，若是感觉有效， 请勿鄙吝你的留言和赞哦！~

扫二维码存眷『運筹OR帷幄』公家号：

點击檢察『運筹OR帷幄』自愿者招募先容及参加方法：