2016 年 5 月

第 31 卷,第 5 期

本文章是由機器翻譯。

測試回合 - 多臂吃角子老虎問題

James McCaffrey

James McCaffrey想像您是在美國拉斯維加斯舉辦站前面三個位置的機器。您必須使用其中放入任何三個機器的語彙基元、 提取的控制代碼和付費的隨機數量的 20 語彙基元。機器支付不同,但您一開始都不知道何種支付排程機器遵循。您可以使用何種策略來最大化您的增益?

這是所謂的多武裝的強盜問題,因此如此命名因為角子老虎非正式地稱為 one-armed bandit 的範例。這個問題不是因為第一次看起來的古怪。有許多重要現實生活的問題,例如藥物臨床試驗,老虎範例類似。

也不太可能,您將需要多重武裝的強盜問題,在大部分的企業開發案例的實作程式碼。但是,您可以閱讀這篇文章的三個原因。首先,本文中使用的程式設計技術的數個可用在其他更常見的程式設計案例中。第二,多重武裝的強盜問題的具體的程式碼實作可以做為高經濟效益和機器學習研究的簡介使用中的區域。和第三,您會發現主題有趣本身很。

看一下示範程式中顯示為初步的這篇文章向其中的最佳方式 [圖 1。有許多不同的演算法可用於多武裝的強盜問題。例如,完全隨機的方式就是只需要選取每個提取,隨機的機器,然後希望為了獲得最佳的。此處所提供的範例將使用稱為瀏覽入侵演算法的基本技術。

使用瀏覽利用多武裝的強盜問題
[圖 1 多武裝的強盜問題上使用瀏覽攻擊

示範開始先建立三部機器。每一部機器支付隨機的數量,在每一個提取中,其中支付額遵循高斯 (鐘型) 散發,以指定的平均數和標準差。第三部電腦是最適合的某一個角度來說,因為它每次提取 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。

有數個不同的度量資訊可以用來評估多武裝的強盜演算法的效率。一個常見的量值稱為生命。生命是理論基準總支付額和實際的總支付額演算法之間的差異。基準理論支付額是預期支付額,如果所有配置的會使用最佳的電腦上。如果是在示範三個的機器,最佳的機器具有 0.10 單位,平均支付額預期支付額,如果在該電腦上所使用的所有 20 提取是 20 * 0.10 = 2.00 單位。因為瀏覽入侵演算法產生只 1.30 單位生命公制為總支付 2.00 1.30 版 = 0.70 的單位。具有較低的生命值的演算法是比具有較高的生命值。

本文假設您有至少中繼程式設計技巧,但不會假設您了解多武裝的強盜問題。完整的範例程式,以幾個次要的編輯,以節省空間,以顯示 [圖 2, ,同時它也是相關聯的程式碼下載中取得。使用 C# 程式碼示範,但您不應該有重構到另一種語言,例如 Python 或 Java 示範沒什麼問題。所有一般錯誤檢查已從示範移除以保持盡可能清楚多武裝的強盜問題的主要概念。

[圖 2 完成多武裝的強盜示範程式碼

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 陳述式,留下只是最上層系統命名空間的一個參考。

所有的控制邏輯會在 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 單位和-0.5 + 2.0 = 1.5 單位。請注意,不同於實際位置機器,付出零或正值的數量,示範機器可以支付負的數量。

三部機器執行瀏覽入侵演算法的陳述式如下 ︰

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 單位的標準差平均支付。使用高斯值會產生此示範的程式碼,撰寫了一個簡短的程式,以產生 100 隨機支出,從 [0] 的電腦。結果會顯示在圖形中 [圖 3

100 個隨機高斯值
[圖 3 100 隨機高斯值

請注意,產生的值大部分接近平均值。產生的值的變化會受到標準差的值。較大的標準差會產生較大的值散佈。在多重武裝的強盜問題中,其中最重要的因素,適用於所有的演算法是機器支出的變化。如果電腦上有很大的不同支出,變得很難評估的機器,則為 true 的平均支付額。

有數種演算法可以用來產生高斯分佈的隨機值與指定之平均值和標準差。我的慣用的方法被呼叫方塊 Muller 演算法。方塊 Muller 演算法首先會產生統一分佈的值 (.NET Math.Random 類別所產生的類型),然後使用統一的值轉換成一個高斯一些非常聰明數學計算散發。有好幾種方塊 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 用來隨機選取的電腦,瀏覽階段。名為 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
}

BestIdx 的程式定義的 helper 方法會傳回其保留的最大值的陣列引數的儲存格的索引。有多種變化的多重武裝的強盜問題。例如,一些變化定義不同的方式瀏覽階段期間找到的最佳機器。在我 cranky 看來,這些差異大多只搜尋研究問題的解決方案。

方法 ExploreExploit 完成計算,並傳回每個提取平均支付額透過所有 nPulls 播放 ︰

. . .
  return totPay / nPulls;
}

替代的設計是為了傳回總支付額,而不是平均支付額,或傳回總生命的值,或兩個資料格陣列中或做為兩個 out 參數傳回總支付額和平均支付額值。

其他演算法

研究建議最適合所有類型的多重武裝的強盜問題沒有單一演算法。不同的演算法有不同的優點和缺點,多半視問題、 可用的提取數目和變化性的支付額發佈函式中的機器數目。


Dr。James McCaffreyRedmond,華盛頓中的 Microsoft Research 的運作方式他曾在包括 Internet Explorer 和 Bing 的數個 Microsoft 產品。Dr.McCaffrey 可以到達jammc@microsoft.com

感謝下列 Microsoft 技術專家檢閱這份文件 ︰ Miro Dudik 和 Kirk Olynyk