Multi-Armed土匪和勘探与开发平衡问题

赌场老虎机有好玩的外号——“角子老虎机”——因为我们的单杆和亏钱当我们玩他们的倾向。他们也激发创造力的研究。今天的嘉宾博客古原竹内将介绍一个有趣的思想实验称为multi-armed强盗。

图片来源

普通的老虎机只有一个杠杆。如果您有多个选择,每个都有不同的支付。这是一个multi-armed强盗。你不知道杠杆支付最高——你只需要尝试不同的杠杆,看看哪个效果最好,但多长时间?如果你继续支付低杆,你放弃更多的回报,但你不会知道哪个杠杆是好的,直到你试着足够的次数。

这个有趣的思维实验,最初在第二次世界大战期间,开发非常棘手,盟军科学家想把这个问题在德国,德国科学家也会浪费他们的时间。从那时起,许多策略也已经被开发出来,以解决这个问题,但显然许多人仍在工作考虑到关于这个主题的论文数量在2015年捏。

这是因为强盗算法相关的领域机器学习被称为强化学习。而不是学习从显式的训练数据,或在静态数据中发现模式,强化学习发现最好的选择与生活尝试和错误的例子。multi-armed土匪尤其是重点勘探与开发权衡的问题——多少资源应该在尝试和错误与效益最大化。

内容

例子——选择最优颜色现在购买按钮

让我们来看看几个基本的受欢迎的策略使用一个例子从一个博客20行代码,每次打A / B测试。它谈论如何使用强盗算法代替普通A / B测试网站优化和提供了一个简洁的伪代码。

我们将使用一个示例中使用的类似博客:“现在购买”按钮应该是蓝色,橙色或黄色,点击最大化?你可以看到这个问题的现场演示由MATLAB生产服务器在AWS上运行。

Epsilon-Greedy策略

这个策略允许您选择一个随机的手臂有统一的概率\ε的美元一小部分试验(勘探),选择最好的臂(1 - \ε)美元的试验(剥削)。这是实现eGreedy类的选择方法。通常的价值\ε是0.1美元或10%的试验。

“最好”的部门是什么?在每个试验中,我们选择手臂拉可能会或可能不会给一个奖励。最好的手臂期望最高奖励根据接收到的奖励了这一点。我们跟踪预期为各自的武器奖励分数。

dbtype“eGreedy.m”31:38

31日函数选择=选择(自我)%选择一只手臂32如果兰德< =自我。ε%(ε)33次选择=兰迪(self.n_arms);%探索所有其他武器34 %(1 -ε)乘以35[~,选择]=…%利用最好的手臂36 max (self.scores(最终,:));37结束38结束

测试按钮颜色的护身强盗

在我们的示例中,我们可以把这些按钮作为杠杆的选择,我们可以拉,我们得到一个奖励的点击或没有点击未知概率与每个颜色。这就是所谓的二进制奖励。的强盗类创建一个对象有三个武器与未知的概率,在这种情况下代表各自的“现在购买”按钮。我们称之为对象按钮。对象提供了测试方法返回一个奖励1或0的选择按钮我们展示,代表一次点击(1)或没有点击(0)。

我们将评估这些按钮的点击未知概率通过我们的试验使用eGreedy类,我们将初始化的myGreedy对象\ε默认设置为0.1美元。最初的预期回报所有武器也将统一设置为1,这意味着我们期望按钮点击时间的100%。

关口= {“蓝”,“橙”,“黄色”};%按钮颜色作为武器按钮=土匪();%初始化强盗与3武器myGreedy = eGreedy (buttons.N);% epsilon-greedyε= 0.1s = array2table (myGreedy.scores);%最初期望的奖励s.Properties。VariableNames =关口%的名字列的颜色

s = __交蓝橙黄1 1 1

第一次审判

在试验中,我们将选择基于epsilon-greedy策略使用一个按钮选择方法myGreedy对象。因为最初的预期回报是统一设置为1时,三种颜色将随机选择web访问者在一个页面。

rng (1);%的再现性颜色= myGreedy.choose ()%选择按钮的颜色

颜色= 1

我们将显示访客在页面上的蓝色按钮,这是使用的实现测试方法,相当于把杆老虎机。奖励(点击)给出的隐藏的概率选择按钮。

单击= buttons.test(颜色)%显示按钮

单击=逻辑0

根据实际结果,我们将更新我们的期望的奖励选择按钮。因为我们没有得到奖励的蓝色按钮,该按钮的期望的奖励现在减少:蓝色= 1/2 = 0.5美元

myGreedy。(颜色,点击更新);%更新期望的奖励s = array2table (myGreedy.scores);%的新期望的奖励s.Properties。VariableNames =关口;%的名字列s.Properties.RowNames = {“初始”,“Trial_1”}%的名字行

s = __出生最初的蓝色橙色黄色1 1 1 Trial_1 0.5 1 1

重复试验

让我们继续为更多的考验和情节的变化预期回报。最初的值波动很大,但最终他们适应特定的范围。它看起来像橙色预期最高奖励和蓝色有略低。

n_trials = 500;%的试验为i = 1: n_trials - 1%减去完成试验颜色= myGreedy.choose ();%选择一个颜色单击= buttons.test(颜色);%测试按钮myGreedy。(颜色,点击更新);%更新期望的奖励结束name =“Epsilon-Greedy策略”;%的标题myGreedy。情节(名称、峡路)%情节预期回报

估计与实际预期的回报

我们永远不会知道实际的概率在现实世界的情况下,但这只是一个模拟,所以我们知道我们用于生成随机奖励的实际参数。让我们看看,怎么来评估他们使用epsilon-greedy策略。估计,但它仍能准确地识别最好的按钮。

array2table ([myGreedy.scores (,);buttons.probs),…“VariableNames”关口,…“RowNames”,{“估计”,“实际”})

ans =蓝色橙色黄色累积_________估计实际0.32353 0.32667 0.21053 0.28 0.32 0.26

后悔

让我们考虑替代方案。如果我们做这个测试标准的a / B测试协议下,我们就会显示三个按钮以同样的比例首先追求纯勘探,然后切换到纯开发最好通过只显示按钮。这也被称为epsilon-first策略。假设我们的A / B测试第一个300次试验,只有显示橙色按钮之后。

如果我们知道最好的按钮使用提前,我们会显示所有的橙色按钮时的最优策略。

策略= {“Epsilon-First”,“Epsilon-Greedy”,“最优”};试验= array2table ((100 300 100;…%的试验myGreedy.trials;[0 n_trials 0]]);trials.Properties。VariableNames =关口;%的名字关口trials.Properties。RowNames =策略%的名字行

试验= __交Epsilon-First蓝橙黄100 300 100 Epsilon-Greedy 33 449 18最佳0 500 0

我们可以计算预期的点击每个策略(奖励),看看我们有多少点击少使用epsilon-greedy与epsilon-first (A / B测试)。这些差异被称为“遗憾”。您可以看到epsilon-greedy非常接近最优。

点击=总和(bsxfun (@times…%得到预期的数量table2array(试验),buttons.probs), 2);%的点击后悔=点击-点击(结束);%减去最佳点击后悔=表(遗憾,“RowNames”、策略)

后悔后悔= ______ Epsilon-First -10 Epsilon-Greedy -2.4最佳0

建立现场演示

我的同事Arvind Hosagrahara咨询服务帮我创建一个现场演示链接。请阅读Arvind优秀的博客构建一个产品,构建一个服务更多细节关于如何用MATLAB创建一个web应用程序。这是快速的总结我所做的。

不要担心如果你不理解JavaScript。在真实的项目中,您将使用一个web开发人员和IT人员团队,他们会照顾的web前端和后端,你可以专注于你的MATLAB代码。这种方法的优点是,您可以直接使用MATLAB代码本身,而不是踏踏实实在C / c++中,. net或Java。

Epsilon-Decreasing策略

现在回到了算法。epsilon-greedy策略的一个问题是如何设置\ε美元的价值,以及我们如何继续探索理想武器速度,即使在算法确定最优的选择。而不是使用\ε美元的固定值,我们可以从一个高价值的减少。通过这种方式,我们可以支持探索最初,然后忙剥削。我们可以很容易地创建一个新类eDcrease从eGreedy来完成。

棘手的部分是我们应该如何定义函数,降低了\ε美元价值。这是一种方法。它始于纯勘探但我们分配更多的试验开发随着实验的进行,逐渐减少年代\ε美元。我尝试了不同的递减函数,但减少的速度似乎不应该过早地得到最好的结果。

f = @ (x) 1。/ (x ^ 5);%递减函数x = 1: n_trials;%的试验图%的新人物情节(x, f (x))%的阴谋ε值包含(“试验”)%轴标签ylabel (‘ε’)%轴标签标题(“ε递减函数”)%的标题

测试新策略

现在让我们运行这个相同数量的试验。看起来它也认为橙色按钮是最好的选择,但它花费更多的时间在最初探索。

rng (1);%的再现性myDec = eDecrease(按钮。N、f);%初始化对象为我= 1:n_trials%重复试验颜色= myDec.choose ();%选择一个颜色单击= buttons.test(颜色);%测试按钮myDec。(颜色,点击更新);%更新期望的奖励结束name =“Epsilon-Decreasing策略”;%的标题myDec。情节(名称、峡路)%情节预期回报

估计预期回报也更接近实际值。

array2table ([myDec.scores(最终:);buttons.probs),…“VariableNames”关口,…“RowNames”,{“估计”,“实际”})

ans =蓝色橙色黄色累积_________估计实际0.27586 0.33148 0.25217 0.28 0.32 0.26

不幸的是,结果表明,这种策略不做以及epsilon-greedy。

策略= {“Epsilon-First”,“Epsilon-Greedy”,“Epsilon-Decreasing”,“最优”};试验= array2table ([[100 300 100];…%的试验myGreedy.trials;myDec.trials;[0 n_trials 0]]);点击=总和(bsxfun (@times…%得到预期的数量table2array(试验),buttons.probs), 2);%的点击后悔=点击-点击(结束);%减去最佳点击后悔=表(遗憾,“RowNames”、策略)

后悔=后悔……Epsilon-First -10 Epsilon-Greedy -2.4 Epsilon-Decreasing -7.96最佳0

更新现场演示

如果epsilon-decreasing策略工作,我可能会想更新我的现场演示。如果我实现epsilon-greedy算法在其他语言中,我将不得不再次重新编码。幸运的是,我用我原来的MATLAB代码,这就是我想做的事:

如果你工作在一个团队中,这意味着你可以自由更新你的代码没有问你的前端或后端人帮助你。甜蜜的!这是一个强大的工作流优势获得使用MATLAB生产服务器。

现实世界中使用

在这里使用的例子,我们考虑的情况下选择最好的“现在购买”按钮的颜色一个web页面但是你可以看到这是有用的,例如,选择广告新闻聚合网站搜索页面上应该显示-《华盛顿邮报》显然使用一个强盗算法。

推荐系统通常面临着冷启动问题——例如,网飞公司没有数据,人们如何将新发布的电影。它仍然可以推荐这样的电影通过反复试验的过程。

我们还讨论了利用MATLAB的生产服务器在您的工作流。痛点Netflix经验之一是双重的问题——你原型实现算法在MATLAB等一种语言,你将其部署到生产系统在另一个,如C / c++、。net或Java。这意味着你必须重新每次你改变你的算法。你可以原型算法在MATLAB,代码可以部署到生产系统很容易与MATLAB生产服务器。

总结——生命是一个土匪的问题?

MATLAB社区博客主机内德看到了这篇文章的初稿,发给我这个视频使用算法使生活决定何时停止寻找一个理想的公寓或配偶。这是一个不同类型的算法最优停止视频,但建议你可以把它应用在生活中。也许你也可以找到一种方法来土匪算法应用于生活。让我们知道如何使用这个算法在这里!

得到了MATLAB代码

发表与MATLAB®R2016b