Benutzer:Leonry/Mehrarmiger Bandit

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Leonry auf.

Der mehrarmige Bandit, auch ${\displaystyle k}$-armiger Bandit oder stochastischer Bandit genannt, ist Forschungsgegenstand der Spieltheorie und Stochastik. Erkenntnisse in Bezug auf den mehrarmigen Banditen finden Anwendung in der Finanzmathematik oder dem maschinellen Lernen.^[1]

Das Problem des mehrarmigen Banditen lässt sich informell wiefolgt beschreiben. Ein Spieler hat die Möglichkeit an ${\displaystyle k}$ einarmigen Banditen sein Glück zu versuchen. Jeder Spielautomat wirft dabei mit verschiedener Wahrscheinlichkeit einen verschiedentlichen Ertrag aus. Die Wahrscheinlichkeitsverteilungen der Gewinnausschüttungen der einzelnen Spielautomaten ist zu Beginn unbekannt. Wie muss der Spieler sein Geld einsetzen, um den höchstmöglichen Betrag zu gewinnen?

Anders formuliert lässt sich das Problem auch im Rahmen des Arbeitsalltages darstellen. Ein Mitarbeiter ist in verschiedenen Projekten im Unternehmen beteiligt. Dabei sind mit jedem Projekt eine verschiedene, zu Beginn unbekannte Erfolgswahrscheinlichkeit und eine verschiedene Belohnung (zum Beispiel Bonuszahlung) verbunden. Wie sollte der Mitarbeiter seine Zeit je Projekt einteilen, um die höchstmögliche Belohnung zu erhalten?

Sei ${\displaystyle \mathbb {T} }$ entweder die natürlichen Zahlen ${\displaystyle \mathbb {N} }$ (unbeschränkte Laufzeit) oder die aufsteigende Zahlenfolge ${\displaystyle 0,\ldots ,T}$ für ein ${\displaystyle T\in \mathbb {N} }$ (beschränkte Laufzeit). Zu jedem Zeitpunkt ${\displaystyle t\in \mathbb {T} }$ wählt der Spieler eine Handlungstaktik ${\displaystyle a_{t}\in {\mathcal {A}}}$ aus allen möglichen Handlungstaktiken aus. Er beobachtet einen Belohnungsprozess ${\displaystyle X_{t}}$ verteilt nach ${\displaystyle \nu _{a_{t}}}$, wobei ${\displaystyle \nu _{a_{t}}\in \lbrace \nu _{a}|a\in {\mathcal {A}}\rbrace }$. Das Ziel des Spielers ist die Summe der Belohnungen ${\displaystyle \sum _{t\in \mathbb {T} }X_{t}}$ zu maximieren.

Im Jarh 1979 bewies Gittins, dass sich das Problem des mehrarmigen Banditen auf eine Menge einfacherer Probleme reduzieren lässt. Dabei wird die Leistung des dynamischen Lösungsansatzes durch den sogenannten Gittins-Index geprüft.^[2]

Verschiedene sogenannte Bandit-Algorithmen wurden entwickelt, u.a. Epsilon Greedy, Oberes Konfidenzniveau und Thompson-Probe.^[3][4]

Das Problem lässt in seiner Allgemeinheit als dynamisches Zuteilproblem sehen. Dadurch lässt es sich in ein Darstellungsproblem für einen stochastischen Prozess durch das laufende Supremum eines weiteren stochastischen Prozesses umformulieren.^[1]

• J. C. Gittins: Bandit Processes and Dynamic Allocation Indices. In: Journal of the Royal Statistical Society Series B: Statistical Methodology. Band 41, Nr. 2, 1. Januar 1979, ISSN 1369-7412, S. 148–164, doi:10.1111/j.2517-6161.1979.tb01068.x (Publizierter Artikel oder [1] [abgerufen am 22. Juni 2024]). 

• Dipl.-Phys. Matthias Rakowski, Dr. Walter Fußeder: Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation. JBerries, 11. März 2020, abgerufen am 22. Juni 2024. 
• Online-Präferenzlernen mit Bandit-Algorithmen. In: GEPRIS. Deutsche Forschungsgemeinschaft, abgerufen am 22. Juni 2024. 

1. ↑ ^{a b} Peter Bank, Hans Föllmer: American Options, Multi–armed Bandits, and Optimal Consumption Plans: A Unifying View. In: Paris-Princeton Lectures on Mathematical Finance 2002. Band 1814. Springer Berlin Heidelberg, Berlin, Heidelberg 2003, ISBN 978-3-540-40193-3, S. 1–42, doi:10.1007/978-3-540-44859-4_1 (Publizierter Artikel und Artikelentwurf auf der Website des Erstautors [abgerufen am 22. Juni 2024]). 
2. ↑ Esther Frostig, Gideon Weiss: Four proofs of Gittins’ multiarmed bandit theorem. In: Annals of Operations Research. Band 241, Nr. 1-2, Juni 2016, ISSN 0254-5330, S. 127–165, doi:10.1007/s10479-013-1523-0 (springer.com [abgerufen am 22. Juni 2024]). 
3. ↑ Marina Wyss: Multi-Armed Bandits als Alternative zum A/B-Test. INWT Statistics GmbH, abgerufen am 22. Juni 2024. 
4. ↑ Mehrarmiger Bandit. In: Optimierungsglossar. Optimizely, 7. Juli 2021, abgerufen am 22. Juni 2024. 

[[Kategorie:Stochastik]]

[[Kategorie:Spieltheorie]]