2016 年 5 月
第 31 卷，第 5 期
此文章由机器翻译。
测试运行 - 多臂赌博机问题
.jpg "James 麦卡弗里")
假设您是在拉斯维加斯举行，读取前三个老虎机。您有 20 令牌来使用，其中一个标记放入的任何三个计算机、 拉出该句柄和他们拿了报酬随机的一段。机支付方式不同，但最初在哪种支出计划机按照不知道。您可以使用哪些策略尝试并最大化效果？
这是一种称为多武装的 bandit 问题，这样命名是因为槽机非正式地称为 one-armed bandit。问题不是因为第一次，这可能看起来一样古怪。有许多重要的现实生活中问题，如药品临床试验，类似于槽机示例。
不太可能您将需要编写的大多数企业开发方案中的多武装的 bandit 问题实现的代码。但您可能想要阅读本文以下三个原因。首先，在这篇文章中使用的编程技术的几个可以在其他，更常见的编程方案中使用。其次，多武装的 bandit 问题的具体代码实现可充当详细介绍了活动区域的经济性和机器学习研究。和第三，您可能觉得主题感兴趣本身。
了解现况，本文所述观点的最佳方法是看一看中所示的演示程序 图 1。有许多不同的算法可用于多武装的 bandit 问题。例如，一种完全随机的方法应是只需选择随机用于每个请求的计算机，然后祈求得到最佳。此处介绍该演示使用称为资源管理器-漏洞算法的基本技术。
.png "在多武装的 Bandit 问题上使用探索攻击")
图 1 在多武装的 Bandit 问题上使用探索攻击
该演示首先创建三个计算机。每台计算机支付其中支出紧跟指定的平均值、 标准偏差 （钟形） 高斯分布在每个请求上随机的一段。第三台计算机是从某种意义上的最佳，因为它具有每个请求 0.1 任意单位的最高的平均付出比率。在非演示方案中，您不知道的计算机的特征。
拉出可用的总次数设置为 20。在探索攻击可以留出了某些大部分的分配拉和使用它们来尝试并找到最佳的计算机。然后，您只能在最佳的初步了解阶段找到的计算机上使用剩余取出。资源管理器-漏洞算法的密钥变量是拉出为探索阶段指定的百分比。该演示将资源管理器百分比设置为 0.40，因此，有 20 * 0.40 = 8 浏览拉出跟 20-8 = 12 攻击拉出。查找最佳的机器，代价是必须较少拉出左利用最佳机攻击阶段中的概率提高浏览拉出增加的百分比。
在八个请求资源管理器阶段中，该演示显示随机选择哪台计算机和相关联的支出。在后台，该演示将保存每台计算机的累计的付款。机 0 被选定三次并支付-0.09 + 0.12 + 0.29 = +0.32 单位。计算机 1 被选定两次并支付-0.46 +-1.91 =-2.37 单位。计算机 2 被选定三次并支付 0.19 + 0.14 + 0.70 = +1.03 单位。如果使用演示用，资源管理器-漏洞算法正确标识计算机 2 作为最佳机因为它有最大总支出。此时，该算法包含 0.32 +-2.37 + 1.03 =-1.02 的净增加 （损失） 单元。
在 12 请求攻击阶段中，演示重复播放仅计算机 2。利用漏洞阶段付款是 0.03 + 0.33 +。.+ 0.45 = +2.32 单位。因此，通过所有 20 拉出的总付出比率是-1.02 + 2.32 = +1.30 单位，每个请求的平均付出比率是 1.30 / 20 = 0.065。
有几个不同的度量值可以用于评估的多武装的 bandit 算法的效果。一个常见的度量值称为遗憾。遗憾是理论基线总支出和一种算法的实际总付出比率之间的差异。基线理论支出是预期的支出，如果所有分配拉出最佳的计算机上使用了。对于三个计算机上在演示中，最佳的机器有 0.10 单位平均支出，因此如果在该计算机上使用了所有 20 拉出预期的付出比率为 20 * 0.10 = 2.00 单位。因为资源管理器-漏洞算法生成的仅 1.30 单位的遗憾跃点数是总支出 2.00 1.30 = 0.70 单位。值较低的遗憾算法都有较大的遗憾值比更好。
本文假定您至少具有中级编程技能，但并不假定您知道多武装的 bandit 问题有关的任何信息。中提供完整的演示程序，少量小幅改动，以节省空间，与 图 2, ，它也有关联的代码下载中。演示使用 C# 中，进行编码，但您应能够该演示程序重构为其他语言，如 Python 或 Java 太多问题。所有常规错误检查已从删除演示为了让主要思想尽可能清晰多武装的 bandit 问题。
图 2 完成多武装的 Bandit 演示代码
using System;
namespace MultiBandit
{
class MultiBanditProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin multi-armed bandit demo \n");
Console.WriteLine("Creating 3 Gaussian machines");
Console.WriteLine("Machine 0 mean = 0.0, sd = 1.0");
Console.WriteLine("Machine 1 mean = -0.5, sd = 2.0");
Console.WriteLine("Machine 2 mean = 0.1, sd = 0.5");
Console.WriteLine("Best machine is [2] mean pay = 0.1");
int nMachines = 3;
Machine[] machines = new Machine[nMachines];
machines[0] = new Machine(0.0, 1.0, 0);
machines[1] = new Machine(-0.5, 2.0, 1);
machines[2] = new Machine(0.1, 0.5, 2);
int nPulls = 20;
double pctExplore = 0.40;
Console.WriteLine("Setting nPulls = " + nPulls);
Console.WriteLine("\nUsing pctExplore = " +
pctExplore.ToString("F2"));
double avgPay = ExploreExploit(machines, pctExplore,
nPulls);
double totPay = avgPay * nPulls;
Console.WriteLine("\nAverage pay per pull = " +
avgPay.ToString("F2"));
Console.WriteLine("Total payout = " +
totPay.ToString("F2"));
double avgBase = machines[2].mean;
double totBase = avgBase * nPulls;
Console.WriteLine("\nBaseline average pay = " +
avgBase.ToString("F2"));
Console.WriteLine("Total baseline pay = " +
totBase.ToString("F2"));
double regret = totBase - totPay;
Console.WriteLine("\nTotal regret = " +
regret.ToString("F2"));
Console.WriteLine("\nEnd bandit demo \n");
Console.ReadLine();
} // Main
static double ExploreExploit(Machine[] machines,
double pctExplore, int nPulls)
{
// Use basic explore-exploit algorithm
// Return the average pay per pull
int nMachines = machines.Length;
Random r = new Random(2); // which machine
double[] explorePays = new double[nMachines];
double totPay = 0.0;
int nExplore = (int)(nPulls * pctExplore);
int nExploit = nPulls - nExplore;
Console.WriteLine("\nStart explore phase");
for (int pull = 0; pull < nExplore; ++pull)
{
int m = r.Next(0, nMachines); // pick a machine
double pay = machines[m].Pay(); // play
Console.Write("[" + pull.ToString().PadLeft(3) + "] ");
Console.WriteLine("selected machine " + m + ". pay = " +
pay.ToString("F2").PadLeft(6));
explorePays[m] += pay; // update
totPay += pay;
} // Explore
int bestMach = BestIdx(explorePays);
Console.WriteLine("\nBest machine found = " + bestMach);
Console.WriteLine("\nStart exploit phase");
for (int pull = 0; pull < nExploit; ++pull)
{
double pay = machines[bestMach].Pay();
Console.Write("[" + pull.ToString().PadLeft(3) + "] ");
Console.WriteLine("pay = " +
pay.ToString("F2").PadLeft(6));
totPay += pay; // accumulate
} // Exploit
return totPay / nPulls; // avg payout per pull
} // ExploreExploit
static int BestIdx(double[] pays)
{
// Index of array with largest value
int result = 0;
double maxVal = pays[0];
for (int i = 0; i < pays.Length; ++i)
{
if (pays[i] > maxVal)
{
result = i;
maxVal = pays[i];
}
}
return result;
}
} // Program class
public class Machine
{
public double mean; // Avg payout per pull
public double sd; // Variability about the mean
private Gaussian g; // Payout generator
public Machine(double mean, double sd, int seed)
{
this.mean = mean;
this.sd = sd;
this.g = new Gaussian(mean, sd, seed);
}
public double Pay()
{
return this.g.Next();
}
// -----
private class Gaussian
{
private Random r;
private double mean;
private double sd;
public Gaussian(double mean, double sd, int seed)
{
this.r = new Random(seed);
this.mean = mean;
this.sd = sd;
}
public double Next()
{
double u1 = r.NextDouble();
double u2 = r.NextDouble();
double left = Math.Cos(2.0 * Math.PI * u1);
double right = Math.Sqrt(-2.0 * Math.Log(u2));
double z = left * right;
return this.mean + (z * this.sd);
}
}
// -----
} // Machine
} // ns
演示程序
若要创建演示程序，我启动了 Visual Studio，并选择了 C# 控制台应用程序模板。我将命名为项目 MultiBandit。我使用 Visual Studio 2015，但演示对并没有明显的.NET 版本依赖性，因此任何版本的 Visual Studio 将正常运行。
加载模板代码后，在解决方案资源管理器窗口中我右键单击文件 Program.cs 并将其更名为更具描述性的 MultiBanditProgram.cs，然后允许 Visual Studio 会自动重命名类 MultiBandit。在编辑器窗口中的代码的顶部，我删除了所有不必要的 using 语句，将只对顶级 System 命名空间的一个引用。
在 Main 方法中，调用方法 ExploreExploit 是所有控制逻辑。该演示具有一个程序定义机类，该类又具有名为高斯的程序定义的嵌套的类。
在一些介绍性 WriteLine 语句之后演示将创建三个计算机 ︰
int nMachines = 3;
Machine[] machines = new Machine[nMachines];
machines[0] = new Machine(0.0, 1.0, 0);
machines[1] = new Machine(-0.5, 2.0, 1);
machines[2] = new Machine(0.1, 0.5, 2);
机类构造函数接受三个参数 ︰ 平均支出、 付款和随机数字生成的种子的标准偏差。因此，计算机 [1] 将支付-0.5 单位 / 拉动的平均值中，将在其中放置大部分支出 （大约 68%) 之间-0.5-2.0 =-1.5 单位和 + 1.5-0.5 + 2.0 = 单位。请注意，与不同的是真实的老虎机，支付零个或正金额，演示机可以进行相应支付出负量。
这些语句在三台计算机上执行资源管理器-漏洞算法包括 ︰
int nPulls = 20;
double pctExplore = 0.40;
double avgPay = ExploreExploit(machines, pctExplore, nPulls);
double totPay = avgPay * nPulls;
方法 ExploreExploit 返回平均增益 （或丢失，如果为负数） 每 nPulls 随机事件发生后的请求。因此，在会话中的总工资是每个请求的平均工资乘以拉出数。另一种设计是 ExploreExploit 返回而不是平均支付工资总额。
计算的遗憾如下所示 ︰
double avgBase = machines[2].mean;
double totBase = avgBase * nPulls;
double regret = totBase - totPay;
变量 avgBase 是每个最佳的计算机，计算机 [2] 的请求的平均付出比率 = 0.1 单位。这样就通过两个拉出付出比率为 20 * 0.10 = 2.0 不产生的总平均单位。
生成高斯随机值
正如我提到，演示程序中的每台计算机不错的回报一个值，遵循 （也称为普通或钟形） 高斯分布。例如，计算机 [0] 具有 0.0，1.0 单位的标准偏差平均支出。使用生成高斯值的演示中的代码，编写了一个小程序，以生成从计算机 [0] 100 随机付款。结果显示中的图形 图 3。
.png "100 个随机高斯值")
图 3 100 随机高斯值
请注意，生成的值大部分接近平均值。生成的值的可变性受控制的标准偏差值。更大的标准偏差将产生更大的值分布。在多武装的 bandit 问题中，所有算法的最重要因素之一是机器支出的变化。如果一台计算机有很大的变化付款，就很难评估的计算机，则返回 true 平均支出。
有几种可用来生成高斯分布式的随机值与指定的平均值和标准偏差的算法。我首选的方法称为 Box-muller 算法。Box-muller 算法首先生成一个均匀分布的值 （由.NET Math.Random 类类型），然后使用一些非常巧妙数学统一的值转换为一个高斯分布。有多种变体 Box-muller。该演示程序使用相比其他变体，但非常简单，进行某种程度上效率低下的变体。
演示程序中，在类机器的内部定义了类高斯。在 Microsoft.NET Framework 中，嵌套的类定义是一些主要的情况下该嵌套的类外部包含类所使用的实用工具类很方便。如果您要迁移此演示代码与非.NET 语言，我建议重构到独立类高斯类。高斯类具有一个接受平均支出、 支出标准偏差的基础统一的随机数字生成器的种子值的单个构造函数。
机类
该演示程序定义类机器中非常简单的方法。有三个类字段 ︰
public class Machine
{
public double mean; // Avg payout per pull
public double sd; // Variability about the mean
private Gaussian g; // Payout generator
...
机类是主要的包装高斯随机数生成器。有许多可能的设计可选项，但我更喜欢在一般情况下使我的类定义尽可能简单。而不是使用标准偏差，像我在这里，有些研究文章使用数学的方差。标准偏差和方差是等效的差异在于，只是标准偏差的平方。
机类具有单独的构造函数将设置为高斯生成器 ︰
public Machine(double mean, double sd, int seed)
{
this.mean = mean;
this.sd = sd;
this.g = new Gaussian(mean, sd, seed);
}
机类具有一个返回高斯分布式随机付出比率的单个公共方法 ︰
public double Pay()
{
return this.g.Next();
}
返回高斯分布式的支出的一种替代方法是返回指定的终结点之间均匀分布的值。例如，一台计算机可能会返回一个随机值之间-2.0 和 + 3.0，平均支出将 (-2 + 3) / 2 = +0.5 单位。
探索攻击实现
ExploreExploit 方法的定义开头 ︰
static double ExploreExploit(Machine[] machines, double pctExplore,
int nPulls)
{
int nMachines = machines.Length;
Random r = new Random(2); // Which machine
double[] explorePays = new double[nMachines];
double totPay = 0.0;
...
R 的 Random 对象用于在资源管理器阶段随机选择一台计算机。名为 explorePays 列阵储存在资源管理器阶段的每台计算机累积付款。就只需一个变量、 totPay，以容纳攻击阶段的累积付出比率，因为只有一台计算机使用。
接下来，计算资源管理器并利用阶段的拉出的数量 ︰
int nExplore = (int)(nPulls * pctExplore);
int nExploit = nPulls - nExplore;
它会计算利用漏洞数目中提取由于可能往返关闭在计算中使用的术语 (1.0-pctExplore) 一个错误。
资源管理器阶段，而无需 WriteLine 语句是 ︰
for (int pull = 0; pull < nExplore; ++pull)
{
int m = r.Next(0, nMachines); // Pick a machine
double pay = machines[m].Pay(); // Play
explorePays[m] += pay; // Update
totPay += pay;
}
Random.Next （int minVal，int maxVal） 返回一个整数值之间 （含） minVal 和 maxVal （排他），因此如果 nMachines = 3，r.Next (0，nMachines) 返回 0、 1 或 2 的随机整数值。
接下来，在资源管理器阶段过程中发现的最佳机确定，并在攻击阶段中使用 ︰
int bestMach = BestIdx(explorePays);
for (int pull = 0; pull < nExploit; ++pull)
{
double pay = machines[bestMach].Pay();
totPay += pay; // Accumulate
}
程序定义的 helper 方法 BestIdx 返回其包含的最大值的数组参数的单元格的索引。目前有多种变体多武装的 bandit 问题。例如，一些变体定义不同的方式在资源管理器阶段找到的最佳机。我不稳定的看来，在很多这些变体都没有什么比搜索研究问题的解决方案。
通过计算并返回每个请求的平均付出比率通过所有 nPulls 播放方法 ExploreExploit 完成 ︰
. . .
return totPay / nPulls;
}
备选设计可能返回的总付出比率而不是平均支出，或返回总遗憾值，或在两个单元格构成的数组，或作为两个输出参数返回总支出和平均支出值。
其他算法
研究表明没有单个算法最适用于所有类型的多武装的 bandit 问题。不同的算法具有不同的优势和劣势，主要取决于问题、 拉出可用，数以及支出分发功能的变化中的计算机数量。
Dr.James McCaffrey供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。
衷心感谢以下 Microsoft 技术专家对本文的审阅： Miro Dudik 和 Kirk Olynyk