Das Warren Buffett Problem

Hier ist eine Abstraktion eines Online-Lern- / Banditenproblems, an dem ich im Sommer gearbeitet habe. Ich habe so ein Problem noch nie gesehen und es sieht ziemlich interessant aus. Wenn Sie verwandte Arbeiten kennen, würde ich mich über Referenzen freuen.

Das Problem Die Einstellung ist die von mehrarmigen Banditen. Du hast N Arme. Jeder Arm hat eine unbekannte, aber feste Wahrscheinlichkeitsverteilung über Belohnungen, die durch das Spielen verdient werden können. Nehmen wir der Vollständigkeit halber an, dass jeder Arm, den ich bezahle, $ 10 mit der Wahrscheinlichkeit p [i] und $ 0 mit prob belohnt. 1-p [i] .

In jeder Runde t wählst du einen Satz S [t] von Armen zum Spielen aus. Für jeden Arm, den Sie auswählen, zahlen Sie im Voraus eine Gebühr von 1 USD . Für jeden ausgewählten Arm sammeln Sie eine Belohnung, die aus der (unbekannten) Wahrscheinlichkeitsverteilung für die Belohnung dieses Arms gezogen wird. Alle Belohnungen werden Ihrem Bankkonto gutgeschrieben und alle Gebühren werden von diesem Konto abgezogen. Zusätzlich erhalten Sie zu Beginn jeder Iteration ein Guthaben von 1 US-Dollar .

Das Problem besteht darin, eine Strategie zur Auswahl einer Teilmenge von Waffen zu entwickeln, die in jeder Iteration gespielt werden soll, um den Gewinn (dh die Belohnungen abzüglich der Spielgebühren) über einen ausreichend langen Zeitraum zu maximieren, vorbehaltlich der Einschränkung, dass ein nicht negativer Kontostand aufrechterhalten werden muss jederzeit.

Ich habe nicht angegeben, ob die Pro-Arm-Belohnungsverteilungen aus einer vorherigen Verteilung oder von einem Gegner ausgewählt wurden. Beide Entscheidungen sind sinnvoll. Die Formulierung des Gegners ist für mich ansprechender, aber wahrscheinlich schwieriger, Fortschritte zu erzielen. Hier wählt der Gegner einen Verteilungsvektor (D1, D2, .., DN). In Anbetracht der Verteilungen besteht die optimale Strategie für einen ausgeglichenen Haushalt darin, alle Waffen zu spielen, deren erwartete Belohnung über 1 USD liegt. Sei P der schrittweise Gewinn dieser optimalen allwissenden Politik. Ich möchte, dass meine Online-Richtlinie das Bedauern (dh den Gewinnverlust über ein Zeitfenster hinweg) dieser allwissenden Richtlinie minimiert.

Ich stelle mir vor, dass es viele mögliche Ansätze für dieses Problem gibt (von denen ich sicher bin, dass Sie darüber nachgedacht haben) - hier sind einige Ideen / Referenzen.

• $N$
• $O(2^{N/2} T^{1/2})$
• Saten Kale, Rob Schapire und ich betrachten in einem anstehenden NIPS 2010-Artikel den Fall, in dem man auf einmal mit dem Arm spielt. In unserer Arbeit ist jedoch die Größe des Schiefers festgelegt. Dieses Papier betrachtet auch ein ähnliches Problem. Eine andere ähnliche Arbeit erschien in ALT 2010. Vielleicht übertragen sich einige der Ideen.
• $2^N$$O(N\sqrt{T})$$O(2^N T)$

BEARBEITEN Sie unten:

$0$$1$$(n-1)/n$$T$$T$$(n-1)T/n$

$B$$0$$2B$$1/B$