Die meisten Online Marketer kennen A/B Tests. Aber was sind Multi Armed Bandits? In diesem Artikel stelle ich den grundlegenden Ansatz des sogenannten Reinforcement Learnings, eine spezielle Art des Machine Learnings, anhand von Multi Armed Bandits vor und eine Umsetzung mittels der Programmiersprache Python. Das Ziel ist es dabei, die Klickanzahl eines durch Budget limitierten Google Ads Accounts mittels Budgereallokation mit Hilfe des Epsilon Greedy Algorithmus zu erhöhen.

Nehmen wir ein herkömmliches Google Ads Konto als Grundlagenscenario und unterstellen wir eine einfache Kontostruktur von 4 Suchkampagnen K1, K2, K3 und K4 mit einem Gesamtbudget von G=100 Euro pro Tag. Nehmen wir des Weiteren an, für die Optimierung wurde eine Google Ads Agentur oder ein Freiberufler beauftragt. Aufgrund des zur Verfügung stehenden, bezahlten workloads können 2 Stunden pro Woche mit der Optimierung des Accounts verbracht werden. Als eine der grundlegenden Optimierungsarbeiten sei darüber hinaus die Optimierung der Verteilung des Budgets unter den 4 Kampagnen vom Klienten so vorgeben, dass die Höchstzahl an Klicks erzielt wird. Da die Arbeitszeit, die zur Verfügung steht, begrenzt ist, ist natürlich auch die Zeit, die für die Budgetoptimierung zur Verfügung steht, begrenzt. Ein realistisches Szenario wäre in unserem Beispiel eine Überprüfung der Budgetallokation von 1-2 Mal die Woche mit einer gegebenenfalls sich anschließenden Änderung der Verteilung, so dass der gesamte workload der Budgetoptimierung nur einige Minuten pro Woche in Anspruch nimmt. Und hier kommt Epsilon-Greedy, bzw. die Multi Armed Bandits Methode „ins Spiel“.

Multi Armed Bandits

Der Begriff des Bandits entstammt dem Glücksspiel und bezeichnet die Slot Maschinen, die mit einem seitlich angebrachten Hebel (Arm) ausgestattet sind, welcher die Mechanik der Automaten in Gang setzt. Bei dem Spiel geht es darum, eine möglichst gewinnbringende Kombination von angezeigten Symbolen zu erhalten.

Multi-armed-bandits
Abbildung: Bandit, Quelle: Pixabay, NikeChillemi, Free for commercial use

Das Zustandekommen einer der möglichen Kombinationen unterliegt dem Zufall und der eigentliche Gewinn (die Belohnung des Spiels) wird durch zahlreiche einzelne Faktoren bestimmt (Stand der Kombination beim Zeitpunkt t-1, die Geldmenge, die sich beim Zeitpunkt t im Automaten befindet usw.). Prinzipiell können wir also einen dieser Automaten mit einer unserer 4 Suchkampagnen vergleichen, bei der ein Klick ebenfalls durch den Zufall bestimmt wird und vom Zeitpunkt der Impressionen der Anzeigen, der Gemütsverfassung des Users, der die Anzeige sieht, die Zahl der mitbietenden, konkurrierenden Werbetreibenden usw. abhängt. Die Analogie des Multi Armed Bandit Szenarios steht dann also für eine Sammlung von mehreren dieser Banditen, bzw. Google Ads Kampagnen.

Im Bemühen, den größten Nutzen aus dem Spiel mit den Automaten zu ziehen, steht der Spieler vor der Entscheidung, in welchen der Automaten er sein Geld investieren soll. Für unsere 4 Suchkampagnen stellt sich analog dazu die Frage, wieviel in die einzelnen Kampagnen vom Gesamtbudget verteilt werden soll. Allgemein wird ein solches Problem als 4-armed bandit problem bezeichnet (dementsprechend für k Automaten dann als „k-armed bandit problem, wobei k eine beliebige, natürliche Zahl ist). Das Spielen eines der Banditen wird in der Sprache des Machine Learnings als action bezeichnet. Durch wiederholte Wahl einer action (welche Maschine wähle ich als nächstes?) ist das Langzeitziel dann, die Gewinne zu maximieren (die Anzahl der Jackpots). Dies wird dadurch erreicht, dass sich schlussendlich auf den Automaten konzentriert wird, bei dem diese Anzahl am höchsten ist.

Die mathematische Formulierung

Wir widmen uns nun der eigentlichen Modellierung des Problems. Als Ausgangslage wird angenommen, dass alle 4 Kampagnen durch Ihr Budget aktuell limitiert sind (also komplett von unserem Freelancer durchoptimiert wurden) und das eine Anhebung des Gesamtbudgets nicht möglich ist, da der Klient keine weitere Anhebung des Gesamtbudgets freigibt*. Wir stehen demnach vor einer gewöhnlichen Situation, die jeder Google Ads Marketer bereits erlebt haben sollte. Zur Wiederholung: Das Ziel ist es nun mit einer entsprechenden, regelmäßigen Reallokation des Gesamtbudgets die höchstmögliche Anzahl an Klicks zu erhalten.

*wenn das Gesamtbudget weiter anhebbar wäre, würde die Budgetallokationsoptimierung ohnehin keinen Sinn machen.

Jede der Kampagnen K1, K2, K3 und K4 weist eine wöchentliche Durchschnittsanzahl von Klicks auf (= Erwartungswert, = Wert der action), wenn von dem Gesamtbudget G ein Anteil x, welcher sich durch Abzug des Einzelbudgets der anderen Kampagnen ergibt reallokalisiert wird. Wir nennen diese Veränderung der Anzahl an Klicks (ob positiv oder negativ) den Wert der action a, q(a) und bezeichnen die action, die wir zum Zeitpunkt t wählen als At. Die mit der Budgetverschiebung verbundene Belohnung nennen wir Rt. Die Größen unserer Modellierung sind also zusammengefasst wie folgt:

a1, a2, a3 und a4: Unsere 4 Suchkampagnen

q(a): Wert der action = Erwartungswert (Durchschnittswert) der Klicks für die jeweilige Verschiebung, wenn Budget von anderen Kampagnen zur jeweiligen Kampagne verschoben wird (sprich: Verlust der Klicks durch Minimierung des Budgets bei Kampagne Ki plus Gewinn der Klicks durch Erhöhung des Budgets bei Kampagne Kj).

x: Budgetanteil der Reallokation (der Einfachheit halber sei dieser eine fixe Summe, z.B. 15 Euro)

At: action, die wir zum Zeitpunkt t wählen (= aktuell gewählte Kampagne, welche das reallokalisierte Budget bekommt)

Rt: Belohnung = Anzahl der erhaltenen aktuellen Klicks durch action Ai.
Der Erwartungswert einer beliebigen action q(a) kann als q(a) = E[Rt|At = a] geschrieben werden und q(a) können wir dann wie folgt lesen: „Erwartungswert, der erhaltenden Klicks R zum Zeitpunkt t, wenn action A das „Auswählen der Kampagne a als Empfänger der Budgetreallokation zum Zeitpunkt t“ ist.

Da der Erwartungswert allerdings nicht bekannt ist (wäre dies der Fall, könnten wir einfach immer diejenige Budgetverschiebung mit dem größten Erwartungswert vornehmen), muss er nun geschätzt werden. Diesen geschätzten Wert der action a zum Zeitpunkt t wollen wir mit Qt(a) bezeichnen und unser Ziel ist es, dass die Schätzung von Qt(a) möglichst dicht an q(a) herankommt. Die Schätzung einer Zufallsgröße lässt sich einfachsten Fall durch Ihren Mittelwert darstellen. In unserem Beispiel lässt sich der Mittelwert folgendermaßen darstellen:
Qn = R1+R2+…+Rn / n. Dabei steht das n für die n’te Wahl einer action. Wurde beispielsweise bereits einmal eine action gewählt, so n=1. Durch geschicktes Umformulieren lässt sich obige Formel für die Wahl der nächsten action Wahl (also Wahl n+1) umschreiben zu Qn+1 = Qn + 1/n*(Rn – Qn) (Sutton, R. S. & Barto A. G. (2018). Reinforcement Learning. Westchester Publishing Services, US). In dieser Darstellung lässt sich der neue Wert (also der Wert nach der n+1 ten action) inkremental darstellen und damit besser mittels eines Algorithmus berechnen und speichern.

Exploring versus Exploiting (Entdecken versus Ausnutzen)

Doch nach welchem Prinzip wird nun a, also die beste action zum Zeitpunkt t ausgesucht und wie können wir unsere Klicks, sprich Belohnungen maximieren? Zur Beantwortung dieser beiden Fragen betrachten wir nun den Begriff „Epsilon“, sowie den Begriff „Greedy“. Nehmen wir dafür an, wir hätten uns bereits mehrmals für die eine oder andere Kampagne als Ziel unserer Budget Reallokation entschieden. Dabei haben wir jeweils 5 Euro der Einzelbudgets von 3 Kampagnen zu der jeweils vierten Kampagne verschoben. Dann können wir zu jedem Zeitpunkt t mindestens eine Verschiebung bestimmen, für die q(a) am größten ausfällt. Diese Verschiebung wird die greedy action genannt (greedy = gierig) und der Vorgang der „gierigen“ Verschiebung bezeichnet man als Exploitation (= Ausnutzen). Eine Exploitation verschafft uns zwar kurzfristig (sprich zum Zeitpunkt t) den größten Erwartungswert der Belohnung, da wir das aktuelle Wissen über Wert der „ausgenutzten“ action nutzen, langfristig gesehen könnte jedoch das „Testen“ oder „Erforschen“ (= Exploration) von anderen actions als der greedy action eine höhere Belohnung einbringen, da wir im Falle des Aufspürens von größeren Belohnungen langfristig diese dann wiederum ausnutzen können. Hier kommt nun das „Epsilon“ ins Spiel.
Der Trick beim Ganzen Epsilon greedy Ansatz ist es, hauptsächlich greedy zu sein, mit einer geringen, aber wiederkehrenden Häufigkeit (Epsilon) aber auch zu überprüfen, ob es actions mit einer höheren Belohnung gibt.
Wir wollen diese Methode nun modellieren. Die greedy action schreiben wir wie folgt auf: At = arg max Qt(a). Dabei bezeichnet arg max die action a, welche in Qt(a) eingesetzt die maximale Schätzung des Erwartungswert zum Zeitpunkt t ergibt. Die Häufigkeit, mit der wir bessere Alternativen testen, modellieren wir als Wahrscheinlichkeit und bezeichnen diese mit ε (dem griechischen Buchstaben Epsilon). Mit dieser kleinen Wahrscheinlichkeit ε (deren Wert wir selbstverständlich selbst vorgeben können) wählen wir von allen 4 Kampagnen mit jeweils gleicher Wahrscheinlichkeit (bei unseren 4 Kampagnen also 0.25 für jede Kampagne) irgendeine beliebige action, unabhängig von deren Erwartungswert. Wenn nun die Anzahl der gewählten actions beliebig groß wird, weil wir ja beliebig große Umschichtungen vornehmen können, werden alle beteiligten actions beliebig oft ausgewählt und alle Qt(a) konvergieren gegen q(a), so dass bei entsprechenden langen Testräumen die action mit dem größten Erwartungswert bestimmt werden kann.
Versuchen wir das Ganze nun einmal mittels Python zu formulieren. Um einen ungeübten Leser (hallo Papa 🙂 ) den Einstieg zu vereinfachen, fange ich mit einem einfachen „Gerüst“ an, dass dann Schritt für Schritt konkretisiert wird.

Es liegt auf der Hand, dass als erstes eine Möglichkeit der Generierung von Zufallszahlen benötigt wird. Python macht es uns hier mit der Numpy Bibliothek einfach. Indem wir Numpy importieren (also den Zugriff innerhalb des von uns zu schreibenden Programms ermöglichen) können wir mit dem Befehl np.random.randint(a,b) eine ganzzahlige Zufallszahl zwischen a und b generieren. Hier ist ein schneller Screenshot einer solchen Generierung, bei der eine Zufallszahl zwischen 1 und 10 generiert wird. Es wird die Zahl 2 generiert:

google-das-machine-learning-1

Versuchen wir nun eine Wenn-Dann Situation zu modellieren, so, dass mit einer Wahrscheinlichkeit von 0.1 (unser Epsilon) in allen Fällen „Epsilon choice“ geschrieben wird und mit einer Wahrscheinlichkeit von 0.9 „Greedy choice“.

google-das-machine-learning-2

Als Nächstes fülle ich dieses Gerüst nun mit dem finalen Code auf. Für die Erläuterung der Funktionsanteile sind Kommentare im Code verteilt (welche man durch das Hash-Zeichen am Anfang erkennt):

campaign_counters=np.array([1,1,1,1])
# Initialisierung von 4 counter Variablen in Form eines Arrays

campaign_exp=np.array([0,0,0,0])
# Initialisierung von 4 Erwartungswert Variablen in Form eines Arrays

def exp_reward(a,b):
# berechnet den Erwartungswert, erhöht den Zähler (n)
# und gibt den Erwartungswert aus

    cexp=campaign_exp[a]
    campaign_exp[a]=cexp+((1/campaign_counters[a])*(b-cexp))
    campaign_counters[a]=campaign_counters[a] +1
    print(campaign_exp[a])
    return campaign_exp[a]

choice=np.random.randint(1,10)

if choice==1:
# Der Zufallszähler wählt eine von 10 Zahlen (von den Zahlen 1 bis 10). Ist die Zahl 1 (epsilon ist also 1/10), dann wird
# der Block bis zu else: ausgeführt, sprich eine der 4 Kampagnen wird mit gleicher Wahrscheinlichkeit ausgewählt,
# der Online Marketer gibt den reward ein (Klickanzahl nach Budgetverschiebung) und der Erwartungswert der zufällig
# ausgewählten Kampagne wird mit der Funktion exp_reward (siehe oben) errechnet.

# Wähle eine der 4 Kampagnen mit einer Wahrschenilichkeit von 1/4:

    epsilon_choice=np.random.randint(1,5)
    print(“epsilon choice = campaign “,epsilon_choice)

    # Übermittlung des rewards zum Zeitpunkt t:
    reward=input(“Bitte gib den aktuellen reward ein: “)
    reward=float(reward)

    # Funktion exp_reward wird aufgerufen:
    epsilon_choice=epsilon_choice-1
    print(reward,epsilon_choice)
    exp_reward(epsilon_choice,reward)

else:
    print(“greedy choice = campaign “, np.argmax(campaign_exp)+1)
    # Mit einer Wahrscheinlichkeit von 1 – 1/10 = 9/10 wird die Kampagne mit     dem zum Zeitpunkt t höchsten Erwartungswert
   # ausgewählt, deren reward wird durch den Online Marketer eingegeben     und der neue Erwartungswert wird durch Aufruf der
   # Funktion exp_reward berechnet

    reward=input(“Bitte gib den aktuellen reward ein: “)
    reward=float(reward)
    exp_reward(np.argmax(campaign_exp),reward)

Hier kommt ein screenshot der Ausgabe des campaign_exp Arrays, dem Array der Erwartungswerte eines hypothetischen Durchlaufs nach 28 Durchgängen (1 Durchgang = 1 Tag). Der Befehl np.amax(campagn_exp) ermittelt At = arg max Qt(a) und der Befehl np.argmax(campaign_exp) +1 gibt die zugrundeliegende Kampagnennummer wieder:

google-ads-maschine-learning-screenshot

Ein nächster Schritt in der Modellierung wäre die Anbindung an die Google Ads API. Da dies jedoch nicht dem weiteren Verständnis des Konzeptes dient, ist dieser Schritt nicht Teil dieses Artikels. Auch wenn reward Eingabe und die Ausgabe der Erwartungswerte in unserer Beispielmodellierung mittels Python manuell erfolgen, ist die Funktionalität gegeben und kann bei entsprechender, einfacher Erweiterung auf beliebig viele Kampagnen ausgedehnt werden. Ein vorgebildete Leser wird sich allerdings eventuell die Frage gestellt haben, inwieweit beim Epsilon Greedy Algorithmus dem Umstand Rechnung getragen wird, dass die Wahrscheinlichkeitsverteilung der Klickraten nicht konstant ist, sprich sich durch zahlreiche Faktoren prinzipiell ständig ändert, also nicht stationär ist. Für diesen Leser sei der zweite Teil meiner Artikelreihe zum Thema Goole Ads Optimierung budgetlimitierter Kampagnen mit Multi Armed Bandits in Aussicht gestellt, welcher sich genau diesem Umstand widmet. Also: stay tuned – to be continued…

Der Artikel hat gefallen? Dann freue ich mich auf ein Feedback.
Bis dahin viel Spaß beim Modellieren
Jan

Wer schreibt hier? Mein Name ist Jan Tappé. Als selbstständiger Online Marketing Consultant berate ich Firmen aus der ganzen Welt zum Thema Online Marketing seit 2010. Ich bin überzeugt davon, dass die Zukunft des Online Marketings maßgeblich durch Machine Learning bestimmt wird. Um hierbei einen Beitrag zu leisten, promoviere ich berufsbegleitend zu einem Schnittstellenthema von angewandter Mathematik, Machine Learning und Online Marketing.