Mehrarmige Banditen: Die beste Lernlösung zur Verstärkung für Ihre Aufgabe

Multi-Armed Bandits (MABs) bilden einen Eckpfeiler in der Welt des Reinforcement Learning und bieten einen leistungsstarken Mechanismus zur Aushandlung von Szenarien, die ein optimales Gleichgewicht zwischen Erkundung und Ausbeutung erfordern. Unter Exploration versteht man das Ausprobieren neuer Optionen, während Exploitation das Festhalten an der aktuell besten Option bedeutet. Unter solchen Umständen erweisen sich MABs aufgrund ihrer intelligenten Lernmechanismen oft als hervorragende Wahl.

Lassen Sie uns zunächst das Konzept hinter MABs entschlüsseln. Stellen Sie sich einen Spieler vor, der von einer Reihe von Spielautomaten umgeben ist, von denen jeder als „einarmiger Bandit“ bekannt ist. Zu den entscheidenden Entscheidungen, die hier getroffen werden müssen, gehört die Festlegung der zu spielenden Maschinen, der Spielreihenfolge und der Spielhäufigkeit. Der Haken daran ist, dass jede Maschine eine andere, ungewisse Belohnung bietet. Das ultimative Ziel besteht darin, die höchste kumulative Belohnung über eine Reihe von Spielen hinweg zu erzielen.

Was ist ein mehrarmiger Bandit?

Der Name „mehrarmiger Bandit“ stammt von einem Gedankenexperiment mit einem Spieler an einer Reihe von Spielautomaten (oft als „einarmiger Bandit“ bekannt). Der Spieler muss entscheiden, welche Maschinen er spielen möchte, wie oft er jede Maschine spielen möchte und in welcher Reihenfolge, mit dem Ziel, seinen Gesamtgewinn zu maximieren.

In einer formelleren Definition ist ein MAB-Problem ein Tupel (A, R)

Das Ziel des MAB-Problems besteht darin, eine Richtlinie π (eine Zuordnung von historischen Daten zu Aktionen) zu finden, die die erwartete Gesamtbelohnung Q über eine bestimmte Anzahl von Runden maximiert.

Das Hauptdilemma bei MAB ist der Kompromiss zwischen „Exploration“ und „Ausbeutung“:

1. Bei der Erkundung geht es darum, verschiedene Waffen auszuprobieren, um mehr über die mögliche Belohnung zu erfahren. Dies erfordert möglicherweise das Ziehen suboptimaler Arme, hilft aber dabei, Informationen über das System zu sammeln.
2. Bei der Ausbeutung geht es darum, den Arm zu ziehen, von dem der Agent aufgrund der bisher gesammelten Informationen derzeit glaubt, dass er die höchste erwartete Belohnung bringt.

Das Ausbalancieren von Exploration und Exploitation ist eine zentrale Herausforderung bei Reinforcement Learning und MAB-Problemen.

Um dieses Problem anzugehen, wurde eine Vielzahl von Algorithmen entwickelt, darunter die Epsilon-Greedy-, die Upper Confidence Bound (UCB)- und die Thompson Sampling-Strategie.

Die detaillierte Überprüfung von Contextual Bandits als Erweiterung von MAB wird in den nächsten Artikeln behandelt.

Der Epsilon(ε)-Gierige

Die Epsilon(ε)-Greedy-Strategie folgt einem einfachen Prinzip. Meistens, quantifiziert als (1 – ε), entscheidet es sich für die Aktion, die die höchste geschätzte Belohnung bringt, und nutzt damit die bekannteste Option aus. In der restlichen Zeit, quantifiziert als ε, wählt es jedoch eine zufällige Aktion und erkundet so neue Möglichkeiten. Der Einfallsreichtum dieser Strategie liegt in ihrer Einfachheit und Effektivität, trotz der Einschränkung, dass sie während ihrer Erkundungsphase möglicherweise weniger lohnende Aktionen mit der gleichen Wahrscheinlichkeit wie die lohnendsten auswählt und der Wert von ε das Gleichgewicht zwischen Erkundung und Ausbeutung bestimmt.

Mathematisch kann es wie folgt definiert werden:

Dies kann durch den folgenden Pseudocode definiert werden:

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Die Pythonic-Implementierung der Epsilon-Greedy-Strategie ist ziemlich einfach:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

Der ε-Greedy-Algorithmus hat den Vorteil der Einfachheit und der Garantie, dass er auch nach vielen Schritten noch (ein wenig) weiter forscht. Im Gegensatz zu UCB oder Thompson Sampling wird bei der Untersuchung jedoch nicht berücksichtigt, wie viel über jede Aktion bekannt ist.

UCB

Umgekehrt berücksichtigt die UCB-Strategie sowohl die geschätzte Belohnung als auch die damit verbundene Unsicherheit oder Varianz bei der Entscheidung für eine Aktion. Es zeigt eine Präferenz für Maßnahmen mit hoher Unsicherheit, um diese zu verringern und eine produktivere Erkundungsphase sicherzustellen. Die UCB-Strategie ist mathematisch wie folgt definiert:

Die Python-Implementierung lautet wie folgt:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

Das Gleichgewicht zwischen Exploration und Ausbeutung in UCB ergibt sich aus seiner Formel: dem geschätzten Wert einer Aktion plus einem Begriff, der mit der Zeit abnimmt (je mehr über die Aktion gelernt wird), aber mit der Unsicherheit über diese Aktion zunimmt. Daher tendiert der Algorithmus dazu, Waffen mit hoher Unsicherheit und hohem Belohnungspotenzial zu erkunden.

Thompson-Probenahme

Thompson Sampling ist ein von Bayesian inspirierter Algorithmus für das Problem der mehrarmigen Banditen. Es weist den Belohnungswahrscheinlichkeiten jedes Banditen (oder jeder Aktion) eine Prior-Verteilung zu und aktualisiert diese Priors dann, wenn Belohnungen beobachtet werden. Die Aktionsauswahl erfolgt probabilistisch, entsprechend der Posteriorverteilung über die beste Aktion.

In einem Beta-Bernoulli-Framework betrachten wir die Belohnungsverteilung jedes Banditen als Bernoulli-Verteilung (dh binäre Belohnungen 0 oder 1). Wir weisen dann eine Beta zu, bevor die Wahrscheinlichkeit für den Erhalt einer Belohnung ermittelt wird. Die Beta-Verteilung ist die konjugierte Prior-Verteilung der Bernoulli-Verteilung, was eine einfache posteriore Aktualisierung ermöglicht.

Logik:

1. Weisen Sie jedem Banditen eine Beta-Verteilung mit den Parametern α=1, β=1 (einheitlicher Prior) zu.

2. Für jede Runde:

   1. Probieren Sie eine Zufallszahl aus der aktuellen Beta-Verteilung jedes Banditen aus.
   2. Wählen Sie den Banditen mit der höchsten Stichprobenzahl aus und ziehen Sie diesen Banditen.
   3. Beobachten Sie die Belohnung des gezogenen Banditen. Wenn es ein Erfolg ist (1), erhöhen Sie den α des Banditen um eins; Wenn es ein Fehlschlag ist (0), erhöhen Sie das β des Banditen um eins.
   4. Wiederholen Sie die Schritte 2 und 3.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Thompson Sampling „erforscht“ daher Aktionen, über die es unsicher ist (solche, bei denen die Verteilung der Werte gestreut ist) und „nutzt“ Aktionen aus, von denen es annimmt, dass sie einen hohen Wert haben könnten (solche, bei denen die Verteilung zu hohen Werten tendiert).

Je mehr man mit der Zeit über jede Aktion lernt, desto spitzer werden die Verteilungen und die vom Algorithmus ausgewählten Aktionen tendieren dazu, sich der Aktion mit dem höchsten erwarteten Wert anzunähern.

Das Explorations-/Ausbeutungsgleichgewicht bei Thompson Sampling ergibt sich auf natürliche Weise aus der Form der Verteilungen. Diese Methode ist recht effektiv, kann jedoch komplexer zu implementieren sein als UCB oder ε-Greedy, insbesondere bei Problemen mit großen oder kontinuierlichen Aktionsräumen oder komplexen Belohnungsstrukturen.

Warum sind Multi-Armed Bandits das beste RL für Ihre Aufgabe?

1. Einfachheit : MAB-Algorithmen sind einfacher und recheneffizienter als vollwertige RL-Algorithmen, die die Pflege und Aktualisierung einer potenziell großen Zustandsaktionswerttabelle oder eines Approximators erfordern.
2. Gleichgewicht zwischen Erkundung und Nutzung : MAB-Algorithmen bieten robuste Methoden zur Bewältigung des Kompromisses zwischen dem Ausprobieren neuer Aktionen und dem Festhalten an bekanntermaßen guten Aktionen.
3. Anpassungsfähigkeit in Echtzeit : MAB-Algorithmen können sich in Echtzeit an Änderungen in der Belohnungsverteilung der Aktionen anpassen.
4. Einfache Integration : Die Einfachheit und Effizienz von MABs ermöglichen eine einfache Integration in bestehende Systeme und bieten sofortige Vorteile bei minimaler Unterbrechung.
5. Breite Anwendbarkeit : MABs wurden erfolgreich in verschiedenen Bereichen eingesetzt, darunter in der Werbung (Auswahl der angezeigten Anzeige zur Maximierung der Klickrate), im Gesundheitswesen (Personalisierung von Behandlungsstrategien) und bei der Webseitenoptimierung (A/B-Tests).

Anwendungen von MABs

Mehrarmige Banditen (Multi-Armed Bandits, MABs) haben ein breites Anwendungsspektrum in verschiedenen Branchen und Bereichen. Hier sind einige Beispiele, wie sie verwendet werden können:

1. Online-Werbung : MABs können verwendet werden, um die Auswahl der Werbung, die den Benutzern angezeigt wird, basierend auf ihren Interaktionen dynamisch anzupassen. Dies trägt dazu bei, die Klickraten oder Conversions im Laufe der Zeit zu maximieren.
2. Klinische Studien : In der medizinischen Forschung können MAB-Algorithmen verwendet werden, um Patienten dynamisch verschiedenen Behandlungen zuzuordnen. Dadurch wird sichergestellt, dass mehr Patienten die effektivsten Behandlungen erhalten, wodurch das Bedauern, also der Verlust, der dadurch entsteht, dass man sich nicht immer für die beste Behandlung entschieden hat, verringert wird.
3. Empfehlung für Nachrichtenartikel : Nachrichtenwebsites können MABs verwenden, um die jedem Benutzer angezeigten Artikel zu personalisieren. Der MAB-Algorithmus kann im Laufe der Zeit lernen, für welche Art von Artikeln sich jeder Benutzer interessiert, und die Empfehlungen entsprechend anpassen.
4. Dynamische Preisgestaltung : E-Commerce-Plattformen oder Fluggesellschaften können MAB-Algorithmen verwenden, um ihre Preisstrategien in Echtzeit zu optimieren und so den Umsatz basierend auf Kundenverhalten und Marktdynamik zu maximieren.
5. Netzwerk-Routing : In Computernetzwerken können MAB-Algorithmen verwendet werden, um Überlastungen zu bewältigen und die Weiterleitung von Paketen zu optimieren. Jede Route kann als Arm behandelt werden und der Algorithmus kann Routen dynamisch auswählen, um Paketverluste oder Latenzzeiten zu minimieren.
6. Hyperparameter-Tuning für maschinelles Lernen : MABs können auch verwendet werden, um die Auswahl von Hyperparametern in Modellen für maschinelles Lernen zu optimieren. Jeder Satz von Hyperparametern kann als Arm behandelt werden, und der Algorithmus kann die Auswahl iterativ verfeinern, um die optimale Modellkonfiguration zu finden.

Im Wesentlichen geht der Nutzen von MABs weit über herkömmliche Verstärkungslernaufgaben hinaus. Sie symbolisieren einen wirksamen Rahmen zur Verbesserung von Entscheidungsprozessen in unsicheren Umgebungen und bieten praktische Lösungen für reale Probleme in verschiedenen Bereichen. Wenn es bei der anstehenden Aufgabe darum geht, Exploration und Ausbeutung in Einklang zu bringen, erweisen sich MABs daher oft als die erste Wahl und bieten eine vielseitige, robuste und anpassungsfähige Lösung für Entscheidungsprobleme.

Abschluss

Mehrarmige Banditen bieten mit ihrer Fähigkeit, Erkundung und Ausbeutung effektiv in Einklang zu bringen, eine robuste Lösung für viele reale Entscheidungsprobleme. Ihre inhärente Anpassungsfähigkeit und Vielseitigkeit machen sie zu einem wertvollen Werkzeug, nicht nur im Bereich des verstärkenden Lernens, sondern auch in einem breiten Anwendungsspektrum, vom Gesundheitswesen bis zur Online-Werbung. Egal, ob Sie ein Datenwissenschaftler, ein Enthusiast des maschinellen Lernens oder ein Fachmann sind, der seine Entscheidungsprozesse verbessern möchte, das Verstehen und Implementieren von MAB-Strategien kann eine bereichernde und lohnende Erfahrung sein.