August 2019
Band 34, Nummer 8
[Test Run]
Der UCB1-Algorithmus für Probleme mit mehrarmigen Banditen
Von James McCaffrey
.jpg "James McCaffrey")
Angenommen, Sie sind in einem Kasino und stehen vor drei Spielautomaten. Sie haben 30 Spielmarken. Jeder Automat gewinnt nach einer anderen Wahrscheinlichkeitsverteilung, und diese Verteilungen sind Ihnen unbekannt. Ihr Ziel ist es, schnell den besten Automaten zu finden, damit Sie den Geldbetrag, den Sie gewinnen, maximieren können. Dies ist ein Beispiel für ein mehrarmiges Banditenproblem, das als solches bezeichnet wird, weil Spielautomaten informell „einarmige Banditen“ genannt werden.
In Ihrer täglichen Arbeitsumgebung ist es unwahrscheinlich, dass Sie sich mit Spielautomaten in Kasinos beschäftigen müssen. Aber das mehrarmige Banditenszenario entspricht vielen praxisnahen Problemen. So muss beispielsweise ein Pharmaunternehmen, das drei neue Medikamente für eine Erkrankung entwickelt hat, mit einer Mindestanzahl von klinischen Studien am Menschen herausfinden, welches Medikament das wirksamste ist. Und eine Onlinewerbekampagne mit mehreren neuen Ansätzen muss herausfinden, welcher Ansatz den Umsatz so schnell wie möglich maximiert.
Es gibt viele verschiedene Algorithmen, die für ein mehrarmiges Banditenproblem verwendet werden können. Der UCB1-Algorithmus (Upper Confidence Bound, Version 1) ist einer der mathematisch anspruchsvollsten Algorithmen, aber überraschenderweise einer der am einfachsten zu implementierenden. Sehen Sie sich die Demoausführung in Abbildung 1 an, um ein Gefühl dafür zu bekommen, was der UCB1-Algorithmus ist und worauf ich in diesem Artikel hinaus will.
.png "Demoausführung des UCB1-Algorithmus")
Abbildung 1: Demoausführung des UCB1-Algorithmus
Die Demo richtet drei Automaten mit einem auf 0 basierenden Index ein, die jeweils eine unterschiedliche Gewinnwahrscheinlichkeit aufweisen. Die drei Wahrscheinlichkeiten sind (0,3, 0,7, 0,5), sodass Automat [1] der beste Automat ist. Bei jeder Betätigung zahlt ein Automat bei einem Gewinn 1 USD aus und 0 USD, wenn der Spieler verliert. Der UBC1-Algorithmus beginnt damit, jeden Automaten ein Mal zu spielen. In der Demo haben die Automaten [0] und [1] gewonnen, aber Automat [2] hat verloren.
Der UCB1-Algorithmus ist iterativ. Die Demo gibt sechs Versuche nach den anfänglichen Spielen an. Im ersten Versuch berechnet der Algorithmus den durchschnittlichen Gewinn für jeden Automaten. Da die Automaten [0] und[1] in der Initialisierungsphase gewonnen haben, ist ihr aktueller durchschnittlicher Gewinn = 1,00 USD/1 Spiel = 1,00 USD. Da der Automat [2] verloren hat, ist sein aktueller durchschnittlicher Gewinn = 0,00 USD/1 Spiel = 0,00 USD.
Die aktuellen durchschnittlichen Gewinne und die aktuelle Versuchsnummer werden auf raffinierte Weise verwendet, um einen Entscheidungswert für jeden Automaten zu berechnen. Für Versuch Nr. 1 sind die Entscheidungswerte die gleichen wie die durchschnittlichen Gewinne. Der zu spielende Arm/Automat ist derjenige mit dem größten Entscheidungswert. An dieser Stelle sind die Automaten [0] und[1] mit dem größten Entscheidungswert gleichwertig. Der Automat [0] wird willkürlich ausgewählt (und nicht Automat [1]). Automat [0] wird dann gespielt, verliert aber.
In Versuch Nr. 2 beträgt der aktualisierte durchschnittliche Gewinn für den Automaten [0] 1,00 USD/2 Spiele = 0,50 USD. Die durchschnittlichen Gewinne für die Automaten [1] und [2] sind noch immer 1,00 USD bzw. 0,00 USD, weil keiner der Automaten gespielt wurde. Die Entscheidungswerte werden als (1,33, 2,18, 1,18) berechnet, sodass Automat [1] ausgewählt wird und gewinnt.
Dieser Vorgang wird bis zu Test Nr. 6 fortgesetzt. Zu diesem Zeitpunkt scheint der UCB1-Algorithmus erfolgreich zu sein, da der Automat [1] (der beste Automat) am häufigsten gespielt wurde (4) und den höchsten durchschnittlichen Gewinn (0,75 USD) erbringt.
Der UCB1-Algorithmus ist recht intelligent. Sehen Sie sich den Versuch Nr. 5 in Abbildung 1 an. Die kumulativen Gewinne sind (1,00 USD, 3,00 USD, 0,00 USD), und die Anzahl der gespielten Automaten ist (2, 4, 1). Daher wurde der Automat [2] seit seinem anfänglichen Verlust in der Initialisierungsphase nicht mehr verwendet. Ein nicht ausgefeilter Algorithmus würde durch die Auswahl von Automat [0] oder[1] fortfahren, aber UCB1 gleicht die Untersuchung der Automateneigenschaften mit der Verwendung des besten gefundenen Automaten aus und entscheidet sich für Automat [2].
Der UCB1-Algorithmus wurde speziell für Banditenprobleme entwickelt, bei denen die Auszahlungswerte 0 oder 1 sind. Dies wird als Bernoulli-Prozess bezeichnet. UCB1 kann auf andere Arten von Problemen angewendet werden, z.B. wenn die Auszahlung einer Gaußschen Verteilung folgt. Aber je unterschiedlicher eine Auszahlungsverteilung von Bernoulli ist, desto schlechter wird der UCB1-Algorithmus funktionieren. Ich empfehle UCB1 nicht für Nicht-Bernoulli-Probleme, aber einige meiner Kollegen glauben, dass UCB1 erfolgreich verwendet werden kann, wenn er konservativ eingesetzt wird.
Die Informationen in diesem Artikel basieren auf der Forschungsarbeit von 2002 mit dem Titel „Finite-Time Analysis of the Multiarmed Bandit Problem“ von P. Auer, N. Cesa-Bianchi und P. Fischer. Zusätzlich zu UCB1 stellt die Studie einen Algorithmus namens UCB-Normal vor, der für die Verwendung bei mehrarmigen Banditenproblemen mit Gaußscher Verteilung vorgesehen ist.
Dieser Artikel geht davon aus, dass Sie über mittlere oder bessere Programmierkenntnisse in C# oder einer Sprache der C-Familie wie Python oder Java verfügen, setzt aber nicht davon aus, dass Sie etwas über den UCB1-Algorithmus wissen. Die Demo ist zwar in C# erstellt, aber der Code sollte sich ohne Schwierigkeiten in eine andere von Ihnen bevorzugte Sprache umgestalten lassen. Der gesamte Democode wird in diesem Artikel vorgestellt. Der Quellcode ist auch im begleitenden Download verfügbar.
Grundlegendes zum UCB1-Algorithmus
Der Schlüssel zum UCB1-Algorithmus ist eine Funktion, die eine Reihe von durchschnittlichen Gewinnen beim Versuch t in eine Reihe von Entscheidungswerten konvertiert, die dann verwendet werden, um festzustellen, mit welchem Automaten gespielt werden soll. Diese Gleichung ist in Abbildung 2 dargestellt. Mit anderen Worten: Wählen Sie beim Versuch t aus allen Armen Arm a aus, der den größten durchschnittlichen Gewinn (r-hut) plus die obere Konfidenzgrenze (der Quadratwurzelausdruck) aufweist. Hier ist n(a) die Anzahl der Betätigungen von Arm a.
.png "Die Schlüsselgleichung für UCB1")
Abbildung 2: Die Schlüsselgleichung für UCB1
Die Gleichung ist einfacher als es scheint und lässt sich am besten an einem Beispiel erklären. Angenommen, der Algorithmus ist wie in der Demo bei Versuch t = 5, und die kumulativen Gewinne sind (1,00, 3,00, 0,00) und die Anzahl der Arme (2, 4, 1). Der erste Schritt besteht darin, den durchschnittlichen Gewinn für jeden Arm zu berechnen: (1,00/2, 3,00/4, 0,00/1) = (0,50, 0,75, 0,00). Dann wird der Entscheidungswert für Arm [0] wie folgt berechnet:
decision[0] = 0.50 + sqrt( 2 * ln(5) / 2 )
= 0.50 + sqrt(1.61)
= 0.50 + 1.27
= 1.77
Ähnlich sind die Entscheidungswerte für die Arme [1] und[2]:
decision[1] = 0.75 + sqrt( 2 * ln(5) / 4 )
= 0.75 + sqrt(0.80)
= 0.75 + 0.90
= 1.65
decision[2] = 0.00 + sqrt( 2 * ln(5) / 1 )
= 0.00 + sqrt(3.22)
= 0.00 + 1.79
= 1.79
Da die Anzahl der gespielten Arme im Nenner des Bruchteils der oberen Konfidenzgrenze liegt, erhöhen kleine Werte den Entscheidungswert. Dies ermöglicht es selten verwendeten Armen, schließlich eine Chance gegen Arme mit einem hohen durchschnittlichen Gewinn zu erhalten. Klasse.
Das Demoprogramm
Das vollständige Demoprogramm (mit einigen kleinen Bearbeitungen, um Platz zu sparen) wird in Abbildung 3 gezeigt. Um das Programm zu erstellen, habe ich Visual Studio gestartet und eine neue Konsolenanwendung mit dem Namen „BanditUCB“ erstellt. Ich habe Visual Studio 2017 verwendet, aber das Demoprogramm weist keine nennenswerten .NET Framework-Abhängigkeiten auf.
Abbildung 3: Das Demoprogramm für den UCB1-Algorithmus
using System;
namespace BanditUCB
{
class BanditProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin UCB1 bandit demo \n");
Console.WriteLine("Three arms with true means u1 = " +
"0.3, u2 = 0.7, u3 = 0.5");
Random rnd = new Random(20);
int N = 3;
int trials = 6;
double p = 0.0;
double[] means = new double[] { 0.3, 0.7, 0.5 };
double[] cumReward = new double[N];
int[] armCounts = new int[N];
double[] avgReward = new double[N];
double[] decValues = new double[N];
// Play each arm once to get started
Console.WriteLine("Playing each arm once: ");
for (int i = 0; i < N; ++i) {
Console.Write("[" + i + "]: ");
p = rnd.NextDouble();
if (p < means[i]) {
Console.WriteLine("win");
cumReward[i] += 1.0;
}
else {
Console.WriteLine("lose");
cumReward[i] += 0.0;
}
++armCounts[i];
}
Console.WriteLine("-------------");
for (int t = 1; t <= trials; ++t) {
Console.WriteLine("trial #" + t);
Console.Write("curr cum reward: ");
for (int i = 0; i < N; ++i)
Console.Write(cumReward[i].ToString("F2") + " ");
Console.Write("\ncurr arm counts: ");
for (int i = 0; i < N; ++i)
Console.Write(armCounts[i] + " ");
Console.Write("\ncurr avg reward: ");
for (int i = 0; i < N; ++i) {
avgReward[i] = (cumReward[i] * 1.0) / armCounts[i];
Console.Write(avgReward[i].ToString("F2") + " ");
}
Console.Write("\ndecision values: ");
for (int i = 0; i < N; ++i) {
decValues[i] = avgReward[i] +
Math.Sqrt( (2.0 * Math.Log(t) / armCounts[i]) );
Console.Write(decValues[i].ToString("F2") + " ");
}
int selected = ArgMax(decValues);
Console.WriteLine("\nSelected machine = [" +
selected + "]");
p = rnd.NextDouble();
if (p < means[selected]) {
cumReward[selected] += 1.0;
Console.WriteLine("result: a WIN");
}
else {
cumReward[selected] += 0.0;
Console.WriteLine("result: a LOSS");
}
++armCounts[selected];
Console.WriteLine("-------------");
} // t
Console.WriteLine("End bandit UCB1 demo ");
Console.ReadLine();
} // Main
static int ArgMax(double[] vector)
{
double maxVal = vector[0];
int result = 0;
for (int i = 0; i < vector.Length; ++i) {
if (vector[i] > maxVal) {
maxVal = vector[i];
result = i;
}
}
return result;
}
} // Program
} // ns
Nach dem Laden des Vorlagencodes habe ich oben im Editor-Fenster alle nicht benötigten Namespaceverweise entfernt und nur noch den Verweis auf den Systemnamespace der obersten Ebene beibehalten. Ich habe im Fenster des Projektmappen-Explorers mit der rechten Maustaste auf die Datei „Program.cs“ geklickt, die Datei in den beschreibenden Namen „BanditProgram.cs“ umbenannt und Visual Studio die automatische Umbenennung der Klasse „Program“ gestattet.
Die gesamte normale Fehlerprüfung wurde ausgelassen, um die Hauptideen so klar wie möglich darzustellen. Die gesamte Steuerungslogik ist in der Main-Methode enthalten. Es gibt eine einzelne Hilfsfunktion namens ArgMax, die den Index des größten Werts in einem numerischen Array zurückgibt. Wenn beispielsweise ein Array die Werte (5,0, 7,0, 2,0, 9,0) enthält, gibt ArgMax 3 zurück.
Einrichten von UCB1
Das Demoprogramm beginnt mit diesen Anweisungen:
Random rnd = new Random(20);
int N = 3;
int trials = 6;
double p = 0.0;
double[] means = new double[] { 0.3, 0.7, 0.5 };
Das Random-Objekt wird verwendet, um festzustellen, ob ein ausgewählter Automat gewinnt oder verliert. Der Seedwert (20) wird nur verwendet, weil er eine repräsentative Demo liefert. Das Array mit dem Namen „means“ hätte stattdessen auch beispielsweise „probsWin“ heißen können. Da jeder Automat jedoch entweder 1 USD oder 0 USD auszahlt, ist der durchschnittliche (mittlere) Wert für jeden Automat gleich der Gewinnwahrscheinlichkeit. Wenn zum Beispiel die Gewinnwahrscheinlichkeit für einen Automaten 0,6 beträgt und Sie den Automaten 1.000 Mal spielen, würden Sie erwarten, etwa 600 Mal 1 USD zu gewinnen. Der Mittelwert pro Spiel ist 600 USD/1.000 = 0,60.
Berechnen der Entscheidungswerte
Das Demoprogramm berechnet Entscheidungswerte unter Verwendung einer direkten Zuordnung zur UCB1-Gleichung in Abbildung 2:
for (int i = 0; i < N; ++i) {
decValues[i] = avgReward[i] +
Math.Sqrt( (2.0 * Math.Log(t) / armCounts[i]) );
Console.Write(decValues[i] + " ");
}
Die Berechnung löst eine Ausnahme aus, wenn t = 0 (der Logarithmus von 0 ist negativ unendlich) ist oder eine Armzahl von 0 (Division durch 0) vorliegt. Die UCB1-Initialisierungsphase, in der jeder Automat ein Mal ausprobiert wird, verhindert jedoch das Auftreten von Ausnahmebedingungen.
Nach der Berechnung der Entscheidungswerte wird durch diese Anweisung der zu spielende Automat bestimmt:
int selected = ArgMax(decValues);
Console.WriteLine("Selected machine = [" + selected + "]");
Die ArgMax-Funktion gibt den Index des größten Entscheidungswerts zurück. Wenn mindestens zwei Entscheidungswerte als größte Werte gleichwertig sind, gibt ArgMax den ersten gefundenen Index zurück. Dies führt zu einer leichten Verzerrung in Richtung kleinerer indizierter Automaten. Ein Ansatz, um diese Verzerrung zu beseitigen, wäre ein Refactoring von ArgMax, sodass bei einem Gleichstand einer der gleichwertigen Indizes zufällig ausgewählt wird.
Der Epsilon-Greedy-Algorithmus
Der UCB1-Algorithmus ist eng mit einem anderen mehrarmigen Banditenalgorithmus namens Epsilon-Greedy verwandt. Der Epsilon-Greedy-Algorithmus beginnt mit der Angabe eines kleinen Werts für Epsilon. Dann wird bei jedem Versuch ein zufälliger Wahrscheinlichkeitswert zwischen 0,0 und 1,0 generiert. Wenn die generierte Wahrscheinlichkeit kleiner als (1 - Epsilon) ist, wird der Arm mit dem aktuell größten durchschnittlichen Gewinn ausgewählt. Andernfalls wird ein Arm nach dem Zufallsprinzip ausgewählt. Eine Epsilon-Greedy-Implementierung auf Basis der Struktur des Demoprogramms könnte folgendermaßen aussehen:
//int selected = ArgMax(decValues); // UCB1
double epsilon = 0.05; // Epsilon-greedy
int selected;
double pr = rnd.NextDouble(); // [0.0, 1.0)
if (pr < (1 - epsilon))
selected = ArgMax(avgReward); // Usually
else
selected = rnd.Next(0, N); // 5% of the time
Eine von mehreren Variationen des grundlegenden Epsilon-Greedy-Algorithmus besteht darin, den Wert von Epsilon im Lauf der Zeit langsam zu verringern. Dies hat den Effekt, dass der Schwerpunkt auf der Exploration zu Beginn der Ausführung liegt und die Exploration des besten gefundenen Arms später während der Ausführung im Vordergrund steht. Das größte Problem mit Epsilon-Greedy ist, dass es keine einfache Möglichkeit gibt, einen guten Wert für Epsilon zu ermitteln.
Meiner Meinung nach sind die Forschungsergebnisse, die UCB1 und Epsilon-Greedy und viele andere mehrarmige Banditenalgorithmen vergleichen, nicht eindeutig. Basierend auf meiner Erfahrung gibt es keinen einzigen, durchgängig besten Algorithmus. Wenn möglich, ist es eine bewährte Vorgehensweise, einige Experimente mit verschiedenen Algorithmen unter Verwendung einer Simulation Ihres realen Problems durchzuführen.
Die Standardmethode zum Vergleichen verschiedener Algorithmen für mehrarmige Banditen besteht darin, eine Regret-Metrik zu berechnen. Der Regret-Wert ist die Differenz zwischen dem erwarteten Wert des Systems (vorausgesetzt, Sie kennen den besten Arm) und dem tatsächlichen Wert des Systems in Experimenten. Angenommen, Sie haben die drei Automaten des Demosystems 10 Mal gespielt und dabei sechs Mal gewonnen und vier Mal verloren. Der Gesamtgewinn beträgt 6,00 USD. Aber wenn Sie hypothetisch alle 10 Mal den besten Arm verwendet haben (mit einer Gewinnwahrscheinlichkeit von 0,7), würde der durchschnittliche Gesamtgewinn 7,00 USD betragen. Daher berechnet sich der Regret-Wert als 7,00 USD - 6,00 USD = 1,00 USD.
Zusammenfassung
Ich teile Machine Learning mental in drei Kategorien ein: überwachtes Lernen, bei dem Sie Trainingsdaten mit bekannten, richtigen Antworten verwenden, unbeaufsichtigtes Lernen, bei dem Sie Daten ohne richtige Antworten verwenden, und Verstärkungslernen (Reinforcement Learning, RL), bei dem ein richtiges oder falsches Ergebnis als Gewinn (der negativ sein könnte) bezeichnet wird und aus einer Funktion anstelle von Daten stammt. Mehrarmige Banditenprobleme werden normalerweise als Teil von Verstärkungslernen betrachtet, aber einige meiner Forschungskollegen sehen den mehrarmigen Banditen als eine besondere Art von Problem an.
Es gibt Dutzende von Algorithmen für mehrarmige Banditenszenarien. Basierend auf meiner Erfahrung ist zusätzlich zu den in diesem Artikel beschriebenen UCB1- und Epsilon-Greedy-Algorithmen der in der Praxis am häufigsten verwendete Algorithmus der als „Thompson Sampling“ bezeichnete Algorithmus. Sie können in der Februar 2018-Ausgabe von MSDN Magazine unter msdn.com/magazine/mt829274 mehr über diesen Algorithmus erfahren.
Dr. James McCaffreyist in Redmond (Washington, USA) für Microsoft Research tätig. Er hat an verschiedenen wichtigen Microsoft-Produkten mitgearbeitet, unter anderem an Azure und Bing. Dr. McCaffrey erreichen Sie unter jamccaff@microsoft.com.
Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee, Ricky Loynd