Mai 2016
Band 31, Nummer 5
Dieser Artikel wurde maschinell übersetzt.
Testlauf – Das Problem des mehrarmigen Banditen
Durch James McCaffrey
.jpg "James McCaffrey")
Angenommen Sie, Sie möchten in Las Vegas, vor drei Spielautomaten ständigen. Sie haben 20 Token verwenden, in dem ein Token in einem der drei Computer löschen, der Hebel und eine zufällige Menge bezahlt werden. Die Computer unterschiedlich Auszahlung, aber Sie anfänglich haben keine Kenntnis plant, welche Art von Auszahlung der Computer gehen Sie folgendermaßen vor. Welche Strategien können Sie versuchen, und der Gewinn maximieren?
Dies ist ein Beispiel für die genannten Problems mit mehreren bewaffneten Bandit so genannt, da die Slot Computer ein One-armed Bandit informell bezeichnet wird. Das Problem ist nicht als erregenden, wie es zunächst scheint. Es gibt viele realen Probleme, z. B. Medikament klinische, die ähnlich wie im Beispiel Slot Computer sind.
Es ist unwahrscheinlich, dass Sie jemals eine Implementierung des Problems mit mehreren bewaffneten Bandit in den meisten Unternehmen Entwicklungsszenarien code. Aber möglicherweise möchten aus drei Gründen für diesen Artikel lesen. Erstens können einige der in diesem Artikel verwendeten Programmiertechniken in anderen, häufiger Programmierszenarios verwendet werden. Zweitens kann eine Implementierung konkrete Code das Problem mit mehreren bewaffneten Bandit als eine gute Einführung in einem aktiven Bereich der Wirtschaftlichkeit und Forschung Computer dienen. Und drittens nur unter Umständen das Thema interessante erkenntnisreich.
Die beste Möglichkeit, ein Gefühl für, in diesem Artikel geht ist auf einen Blick auf das Demoprogramm Abbildung 1. Es gibt viele verschiedene Algorithmen, die auf Probleme mit mehreren bewaffneten Bandit verwendet werden können. Z. B. wäre ein vollkommen zufälliger Ansatz nur ein Computer nach dem Zufallsprinzip für jede Pull aus, anschließend hoffen optimal. Die hier vorgestellte Demo wird eine grundlegende Technik den Durchsuchen-Exploit-Algorithmus verwendet.
.png "Untersuchen Angriff auf ein Problem mit mehreren bewaffneten Bandit Verwendung")
Abbildung 1: Untersuchen Angriff auf ein Problem mit mehreren bewaffneten Bandit Verwendung
Das Demoprogramm drei Computer erstellen. Jeder Computer zahlt es sich um eine zufällige Menge auf jedes Pull, folgt der Auszahlung eine Gauß (glockenförmigen) Verteilung mit einem angegebenen Mittelwert (Durchschnitt) und die Standardabweichung. Der dritte Computer ist das beste in gewisser Hinsicht, weil der höchsten durchschnittlichen Auszahlung pro Abruf von 0,1 beliebige Einheiten verwendet. In einer nicht-Demoszenario würde nicht kennen Sie die Merkmale der Computer.
Die Gesamtzahl der verfügbaren zieht ist auf 20 festgelegt. Im Durchsuchen-Exploit reservieren Sie einen bestimmten Anteil des Ihr zugewiesenen zieht und verwenden, versuchen Sie es, und suchen den besten Computer zu. Verwenden Sie die verbleibenden zieht nur auf dem besten Computer während der Phase der vorläufigen durchsuchen gefunden. Die wichtigste Variable für den Explorer-Exploit-Algorithmus ist der Prozentsatz der zieht, die Sie für die Durchsuchen-Phase festlegen. Die Demo legt den Durchsuchen-Prozentsatz auf 0,40, daher sind 20 * 0,40 = 8 untersuchen zieht, gefolgt von 20-8 = 12 Exploit zieht. Erhöhen dem Prozentsatz der Explorer zieht erhöht die Wahrscheinlichkeit der Suche nach dem besten Computer zu Lasten mit weniger zieht Links zu den besten Computer in der Exploit-Phase nutzen.
Während der Phase acht Pull-Explorer zeigt die Demo die Computer nach dem Zufallsprinzip ausgewählt wurde und der zugehörigen Auszahlung. Hinter den Kulissen speichert die Demo die kumulierte Auszahlungen jedes Computers. Computer 0 wurde drei Mal ausgewählt und bezahlt-0.09 + 0,12 + 0,29 = +0.32 Einheiten. Computer 1 zweimal ausgewählt und bezahlt-0.46 +-1.91 =-2.37 Einheiten. Computer 2 drei Mal ausgewählt und bezahlt 0,19 + 0,14 + 0,70 = +1.03 Einheiten. Im Fall der Demo identifiziert der Algorithmus durchsuchen-Exploit ordnungsgemäß Computer 2 als die beste Computer da sie die größte insgesamt Auszahlung verfügt. An diesem Punkt hat der Algorithmus ein Nettogewinn (Verlust) 0,32 +-2.37 + 1.03 =-1.02 Einheiten.
Während der Phase 12 Pull-Exploit spielt die Demo wiederholt nur Computer 2. Der Exploit-Phase Auszahlungen sind 0,03 + 0,33 +. . + 0.45 = +2.32 Einheiten. Daher ist der gesamte Auszahlung über alle 20 zieht-1.02 + 2.32 = +1.30 Einheiten und die durchschnittliche Auszahlung pro Pull ist 1.30 / 20 = 0,065.
Es gibt mehrere verschiedene Metriken, die verwendet werden können, um die Wirksamkeit eines Algorithmus mit mehreren bewaffneten Bandit bewerten. Eine gemeinsame Maßnahme wird bedauern aufgerufen. Bedauern ist der Unterschied zwischen einer theoretischen Baseline insgesamt Auszahlung und der tatsächlichen insgesamt Auszahlung für einen Algorithmus. Der Baseline theoretischen Auszahlung ist der erwartete Auszahlung, wenn alle zugewiesenen zieht auf dem besten Computer verwendet wurden. Im Fall der drei Computer in der Demo der besten Computer hat eine durchschnittliche Auszahlung 0,10 Einheiten ist also der erwarteten Auszahlung, wenn alle 20 zieht auf diesem Computer verwendeten 20 * 0,10 = 2.00 Einheiten. Da die Durchsuchen-Exploit-Algorithmus ergab einen gesamten Auszahlung von nur 1.30 Einheiten, um die Metrik bedauern 2.00 1.30 = 0,70 Einheiten. Algorithmen mit niedrigeren bedauern Werte sind besser als mit höheren bedauern-Werten.
Dieser Artikel setzt Sie zumindest fortgeschrittene Programmierkenntnisse verfügen, jedoch nicht vorausgesetzt, dass Sie sich das Problem mit mehreren bewaffneten Bandit auskennen. Das vollständige Demoprogramm mit ein paar kleinen Änderungen, um Platz zu sparen werden im Abbildung 2, und es ist auch im zugehörigen Codedownload verfügbar. Die Demo mit c# codiert ist, aber Sie sollten keine Umgestalten der Demo in eine andere Sprache, z. B. Python oder Java. Alle normale fehlerprüfung wurde aus der Demo entfernt, um die wichtigsten Konzepte des Problems mit mehreren bewaffneten Bandit so deutlich wie möglich zu halten.
Abbildung 2 abgeschlossen mit mehreren bewaffneten Bandit Demo-Code
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
Das Demoprogramm
Um das Demoprogramm zu erstellen, wenn ich Visual Studio gestartet und die C#-Console Application-Vorlage ausgewählt. Kann ich mit dem Namen des Projekts MultiBandit. Ich verwendete Visual Studio 2015, aber die Demo hat keine nennenswerten .NET versionsabhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte.
Nachdem der Vorlagencode geladen, im Projektmappen-Explorer-Fenster kann ich mit der rechten Maustaste auf die Datei Program.cs den aussagekräftigeren MultiBanditProgram.cs umbenannt, und Visual Studio die Klasse MultiBandit automatisch umbenannt. Am Anfang der Code im Editor-Fenster gelöscht ich unnötige "using"-Anweisungen einfach die einen Verweis auf den Namespace der obersten Ebene System verlassen.
Die Steuerelementlogik wird in der Main-Methode die Methode ExploreExploit aufruft. Die Demo hat eine Programm definierten Computer Klasse, die wiederum eine programmdefinierte verschachtelte Klasse namens Gauß verfügt.
Nachdem einige einführenden WriteLine-Anweisungen erstellt die Demo drei Computer:
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);
Der Computer-Klassenkonstruktor akzeptiert drei Argumente: den Mittelwert Auszahlung, die Standardabweichung der Auszahlungen und ein Ausgangswert für die Erzeugung von Zufallszahlen. Daher Computer [1] wird Auszahlung -0,5 Einheiten pro pull im Durchschnitt, werden die meisten der Auszahlungen (ca. 68 Prozent) zwischen -0,5 - 2.0 =-1.5 Einheiten und -0,5 + 2.0 = + 1,5 Einheiten. Beachten Sie, dass im Gegensatz zu echten Slot-Computer, die auf 0 (null) oder einen positiven Betrag zu bezahlen, die Demo-Computer einen negativen Betrag auszahlen können.
Die Anweisungen, die von den Durchsuchen-Exploit-Algorithmus auf drei Computern ausgeführt werden:
int nPulls = 20;
double pctExplore = 0.40;
double avgPay = ExploreExploit(machines, pctExplore, nPulls);
double totPay = avgPay * nPulls;
ExploreExploit-Methode gibt die durchschnittliche Gewinn (oder verloren gehen, wenn negativ) pro Pull nach nPulls zufällig Ereignisse. Daher ist die Bezahlung gesamte aus der Sitzung die Anzahl der zieht, multipliziert mit der durchschnittlichen Nutzungsabhängige Pull. Ein alternativer Entwurf ist für ExploreExploit die Bezahlung gesamte anstelle der durchschnittlichen Lohn zurückgegeben.
Die bedauern wird berechnet wie folgt:
double avgBase = machines[2].mean;
double totBase = avgBase * nPulls;
double regret = totBase - totPay;
Variable AvgBase ist der durchschnittliche Auszahlung pro Abruf von den besten Computer, [2] = 0,1 Einheiten. Daher wird der gesamte Durchschnitt erwartet Auszahlung über zwei zieht ist 20 * 0,10 = 2.0 Einheiten.
Gauß Zufallswerte generieren
Wie bereits erwähnt, zahlt sich jeder Computer im Demoprogramm, ein Wert, der einen Gauß (auch als normale oder glockenförmigen) Verteilung. Computer [0] hat z. B. einen Mittelwert Auszahlung von 0.0 mit einer Standardabweichung von 1,0 Einheiten. Verwenden den Code aus der Demo, die Gauß-Werte generiert, habe ich ein kurzes Programm zu 100 zufällige Auszahlungen vom Computer [0]. Die Ergebnisse werden angezeigt, im Diagramm in Abbildung 3.
.png "100 zufällige Gauß-Werte")
Abbildung 3 100 zufällige Gauß-Werte
Beachten Sie, dass die Mehrheit der generierten Werte nah am Mittelwert liegen. Die Variabilität der generierten Werte wird durch den Wert der Standardabweichung gesteuert. Eine größere Standardabweichung erzeugt eine größere Verbreitung von Werten. Bei einem Problem mit mehreren bewaffneten Bandit ist einer der wichtigsten Faktoren für alle Algorithmen die Variabilität des Computers Auszahlungen. Wenn ein Computer sehr variabel Auszahlungen verfügt, wird es sehr schwierig, auszuwertende true durchschnittliche Auszahlung des Computers.
Es gibt verschiedene Algorithmen, die zum Generieren von Gauß verteilte Zufallswerte mit einem angegebenen Mittelwert und Standardabweichung verwendet werden können. Meine bevorzugte Methode heißt den Box-Muller-Algorithmus. Der Box-Muller-Algorithmus generiert zuerst einen gleichmäßig verteilten Wert (die Art von der .NET Math.Random-Klasse erzeugt), und anschließend verwendet einige sehr raffinierte Mathematik einheitlichen Wert in eine umwandeln, der Gaussian wird verteilt. Es gibt mehrere Varianten der Box-Muller. Das Demoprogramm verwendet eine Abweichung, die etwas ineffizient ist im Vergleich zu anderen Variationen, aber sehr einfach.
Im Demoprogramm wird die Klasse Gauß innerhalb der Klasse Computer definiert. In Microsoft .NET Framework sind die Definitionen der geschachtelten Klasse hauptsächlich zur Vereinfachung für Situationen, in denen die geschachtelte Klasse eine Hilfsklasse, die von der äußeren enthaltenden Klasse verwendet. Wenn Sie mit dieser Democode in einer Sprache von .NET portieren, empfiehlt sich die Umgestaltung Klasse Gauß zu einer eigenständigen Klasse. Die Gauß-Klasse verfügt über einen einzelnen Konstruktor, der einen Mittelwert Auszahlung, eine Standardabweichung für die Auszahlung und ein Ausgangswert für den zugrunde liegenden uniform Zufallszahlengenerator akzeptiert.
Die Computer-Klasse
Das Demoprogramm definiert die Klasse Computer sehr einfach. Es gibt drei Felder der Klasse:
public class Machine
{
public double mean; // Avg payout per pull
public double sd; // Variability about the mean
private Gaussian g; // Payout generator
...
Die Computer-Klasse ist in erster Linie einen Wrapper für einen Gauß-Zufallszahlen-Generator. Es gibt viele mögliche Entwürfe im Allgemeinen ich meine Klassendefinitionen so einfach wie möglich halten möchten. Anstelle der Standardabweichung, wie hier schon verwenden einige Artikel Research die mathematische Varianz. Standardabweichung und Varianz sind gleichwertig, da die Varianz nur die quadrierte Standardabweichung ist.
Der Computer-Klasse verfügt über einen einzelnen Konstruktor, der die Gauß-Generator eingerichtet:
public Machine(double mean, double sd, int seed)
{
this.mean = mean;
this.sd = sd;
this.g = new Gaussian(mean, sd, seed);
}
Der Computer-Klasse verfügt über eine einzelne öffentliche Methode, die einen Gauß verteilten zufälligen Auszahlung zurückgibt:
public double Pay()
{
return this.g.Next();
}
Eine Alternative zum Zurückgeben einer Gauß verteilte Auszahlung ist einen gleichmäßig verteilten Wert zwischen angegebenen Endpunkte zurückgegeben. Z. B. ein Computer konnte einen zufälligen Wert zwischen-2.0 zurückgeben und + 3.0, der durchschnittliche Auszahlung wäre (-2 + 3) / 2 = +0.5 Einheiten.
Die Durchsuchen-Exploit-Implementierung
Die Definition der ExploreExploit-Methode beginnt mit:
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;
...
Das Random-Objekt R wird verwendet, ein Computer während der Phase durchsuchen nach dem Zufallsprinzip aus. Das Array namens ExplorePays enthält die kumulativen Auszahlungen für jeden Computer während der Phase durchsuchen. Es gibt nur müssen für eine einzelne Variable, TotPay, der kumulativen Auszahlung der Exploit-Phase zu halten, da nur ein einzelner Computer verwendet wird.
Als Nächstes wird die Anzahl der für die Phasen durchsuchen und Ausnutzung zieht berechnet:
int nExplore = (int)(nPulls * pctExplore);
int nExploit = nPulls - nExplore;
Es wäre, einen Fehler zu berechnen, dass die Anzahl der Exploit zieht den Begriff (1.0 - PctExplore) aufgrund der möglichen Round aus in die Berechnung verwenden.
Die Phase durchsuchen, ohne WriteLine-Anweisungen ist:
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;
}
Der Random.Next (MinVal Int, Int MaxVal) gibt eine ganze Zahl Wert zwischen (einschließlich) MinVal und MaxVal (ausschließlich), sodass Wenn nMachines = 3, r.Next (0, nMachines) gibt eine zufällige ganze Zahl von 0, 1 oder 2 zurück.
Der beste Computer finden Sie in der Explorer-Phase wird als Nächstes ermittelt und in der Exploit-Phase verwendet:
int bestMach = BestIdx(explorePays);
for (int pull = 0; pull < nExploit; ++pull)
{
double pay = machines[bestMach].Pay();
totPay += pay; // Accumulate
}
Programm definierten Hilfsmethode BestIdx gibt den Index einer Zelle und die Arrayargument, das den größten Wert enthält. Es gibt Dutzende von Variationen des Problems mit mehreren bewaffneten Bandit. Einige Varianten definieren z. B. den besten Computer während der Phase Durchsuchen auf andere Weise gefunden. Launisches meiner Meinung nach sind viele Variationen nichts anderes als Lösungen auf der Suche nach einem Problem, das auf.
ExploreExploit-Methode wird durch berechnen und Zurückgeben von der durchschnittlichen Auszahlung pro Pull über alle nPulls spielt beendet:
. . .
return totPay / nPulls;
}
Alternative Entwürfe möglicherweise der total Auszahlung anstelle der durchschnittliche Auszahlung oder den gesamten bedauern-Wert zurückgeben, oder Zurückgeben der insgesamt Auszahlung und die durchschnittliche Auszahlung Werte in einem Array zwei Zellen oder als zwei Parameter.
Andere Algorithmen
Research schlägt vor, dass keiner der Algorithmen, die am besten für alle Arten von Problemen mit mehreren bewaffneten Bandit vorhanden ist. Verschiedene Algorithmen haben unterschiedliche Stärken und Schwächen, vor allem auf die Anzahl der Computer in das Problem, die Anzahl der verfügbaren zieht und die Variabilität der Auszahlung Verteilungsfunktionen abhängig.
Dr. James McCaffrey ist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.
Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Miro Dudik und Kirk Olynyk