Münzwurf, Entscheidungsprozesse und Informationswert

14

Stellen Sie sich folgendes Setup vor: Sie haben 2 Münzen, Münze A, die garantiert fair ist, und Münze B, die fair sein kann oder nicht. Sie werden aufgefordert, 100 Münzen zu werfen, und Ihr Ziel ist es, die Anzahl der Köpfe zu maximieren .

Ihre vorherige Information über Münze B ist, dass sie dreimal geworfen wurde und 1 Kopf ergab. Wenn Ihre Entscheidungsregel lediglich auf dem Vergleich der erwarteten Wahrscheinlichkeit der Köpfe der 2 Münzen basiert, würden Sie die Münze A 100-mal werfen und damit fertig sein. Dies gilt auch dann, wenn vernünftige Bayes'sche Schätzungen (hintere Mittelwerte) der Wahrscheinlichkeiten verwendet werden, da Sie keinen Grund zu der Annahme haben, dass Münze B mehr Köpfe ergibt.

Was ist jedoch, wenn die Münze B tatsächlich zugunsten der Köpfe voreingenommen ist? Sicherlich sind die "potentiellen Köpfe", die Sie aufgeben, wenn Sie die Münze B ein paarmal umwerfen (und damit Informationen über ihre statistischen Eigenschaften erhalten), in gewisser Weise wertvoll und fließen daher in Ihre Entscheidung ein. Wie kann dieser "Informationswert" mathematisch beschrieben werden?

Frage: Wie konstruieren Sie in diesem Szenario mathematisch eine optimale Entscheidungsregel?

M. Cypher
quelle
Ich lösche meine Antwort. Zu viele Leute beschweren sich, dass ich ausdrücklich einen Prior verwendet habe (was in der Literatur Standard ist). Genießen Sie die falsche Antwort von Cam Davidson Pilon, bei der er ebenfalls eine frühere (aber keine Einwände erregende) Methode voraussetzt und eine Methode als optimal bezeichnet, die 1,035 unter der optimalen liegt.
Douglas Zare
whoah, wann ist das alles passiert? Übrigens, ich stimme Douglas zu, dass es in Ordnung ist, einen Prior zu verwenden. Ich widerrufe auch meine Optimalitätsbehauptung.
Cam.Davidson.Pilon
Ich akzeptiere die Lösung von Cam, weil sie mir sehr geholfen hat. Ich bin damit einverstanden, dass es nicht optimal ist, aber es ist die beste Wahl , wenn nicht jemand eine allgemein optimale Lösung aufzeigt, die einfach berechnet werden kann.
M. Cypher
Warum war es so schlimm, dass ich mit einem Prior (den ich eindeutig angegeben habe) eine Frage mit dem Tag "Bayesian" beantwortete?
Douglas Zare
1
Ich habe die Verwendung eines Prior nicht kritisiert. Ich erwähnte als Randbemerkung, dass es möglicherweise angemessenere Prioritäten als die Uniform geben könnte (z. B. Jeffreys), aber dies ist für die Frage nur am Rande relevant. Ihre Lösung war vollkommen in Ordnung und für mich nicht so nützlich, da sie sich nicht leicht verallgemeinern lässt.
M. Cypher

Antworten:

7

Mehrarmiger Bandit

Dies ist ein besonderer Fall eines mehrarmigen Banditenproblems . Ich sage einen bestimmten Fall, weil wir im Allgemeinen keine der Wahrscheinlichkeiten von Köpfen kennen (in diesem Fall wissen wir, dass eine der Münzen eine Wahrscheinlichkeit von 0,5 hat).

Das Problem, das Sie ansprechen, wird als Exploration-vs.-Exploitation- Dilemma bezeichnet: Untersuchen Sie die anderen Optionen oder bleiben Sie bei dem, was Sie für das Beste halten. Es gibt eine sofortige optimale Lösung, wenn Sie alle Wahrscheinlichkeiten kennen : Wählen Sie einfach die Münze mit der höchsten Gewinnwahrscheinlichkeit. Wie Sie angedeutet haben, besteht das Problem darin, dass wir uns nicht sicher sind, wie hoch die tatsächlichen Wahrscheinlichkeiten sind.

Es gibt viel Literatur zu diesem Thema und es gibt viele deterministische Algorithmen, aber da Sie diesen Bayesian markiert haben, möchte ich Ihnen von meiner persönlichen Lieblingslösung erzählen: dem Bayesianischen Banditen !

Die baysische Banditenlösung

Die bayesianische Herangehensweise an dieses Problem ist sehr natürlich. Wir sind interessiert an der Antwort "Wie groß ist die Wahrscheinlichkeit, dass die Münze X die bessere von beiden ist?".

A priori , vorausgesetzt , wir beobachtet haben , nicht die Wahrscheinlichkeit der Münze B Heads , auch sein mag, bezeichnen diese unbekannte Münze noch Flips, wir , was keine Ahnung haben , . Daher sollten wir dieser unbekannten Wahrscheinlichkeit eine vorherige Gleichverteilung zuweisen. Alternativ ist unsere vorherige (und hintere) für Münze A ganz auf 1/2 konzentriert.pB

Wie Sie angegeben haben, beobachten wir 2 Schwänze und 1 Köpfe von Münze B. Wir müssen unsere hintere Verteilung aktualisieren. Unter der Annahme, dass ein einheitlicher Prior und Flips Bernoulli-Coin-Flips sind, ist unser Posterior ein . Vergleich der posterioren Verteilungen von A und B:Betein(1+1,1+2)

Bildbeschreibung hier eingeben

Eine annähernd optimale Strategie finden

Was ist nun zu tun, da wir die Nachhut haben? Wir sind daran interessiert zu antworten: "Was ist die Wahrscheinlichkeit, dass Münze B die bessere der beiden ist?"

wB=P(pb>0,5)

Die annähernd optimale Lösung besteht darin, B mit der Wahrscheinlichkeit und A mit der Wahrscheinlichkeit 1 - w B zu wählen . Dieses Schema maximiert die erwarteten Gewinne. w B kann numerisch berechnet werden, da wir die hintere Verteilung kennen, aber ein interessanter Weg ist der folgende:wB1-wBwB

1. Sample P_B from the posterior of coin B
2. If P_B > 0.5, choose coin B, else choose coin A.

Dieses Schema aktualisiert sich ebenfalls von selbst. Wenn wir das Ergebnis der Auswahl von Münze B beobachten, aktualisieren wir unseren hinteren Teil mit diesen neuen Informationen und wählen erneut aus. Auf diese Weise wählen wir die Münze B, wenn sie wirklich schlecht ist, seltener aus, und die Münze B ist in der Tat wirklich gut. Natürlich sind wir Bayesianer, daher können wir niemals absolut sicher sein, dass Münze B besser ist. Eine solche probabilistische Wahl ist die natürlichste Lösung für das Explorations-Exploitations-Dilemma.

Dies ist ein besonderes Beispiel für Thompson Sampling . Weitere Informationen und coole Anwendungen für Online-Werbung finden Sie in den Forschungsberichten von Google und Yahoo . Ich liebe dieses Zeug!

Cam.Davidson.Pilon
quelle
2
Ich denke nicht, dass diese Strategie richtig ist. Ich denke nicht, dass Sie sich entscheiden sollten, ob Sie A oder B probabilistisch auswählen.
Douglas Zare
2
Ich glaube nicht, dass das Papier sagt, was Sie denken, dass es tut. Wenn Sie nicht einverstanden sind, berechnen Sie bitte die erwartete Anzahl der Köpfe, die Sie im Rahmen dieser Strategie erhalten.
Douglas Zare
5
Ich denke nicht, dass dies nahezu optimal ist. Es deutet darauf hin, dass Sie beim ersten Flip B mit der Wahrscheinlichkeit 1/2 gewählt haben. Es sollte klar sein, dass Sie keine Informationen erhalten, wenn Sie A wählen, daher sollten Sie die ganze Zeit B wählen. Die Menge, die Sie durch diesen Fehler verlieren, ist ungefähr 0,12, wenn Sie es machen, so kostet es Sie ungefähr 0,06 im ersten Schritt. Sie verlieren einen ähnlichen Betrag, wenn Sie ungefähr eine Münze werfen, um zu entscheiden, ob Sie Informationen zu den nächsten Schritten sammeln möchten. Ein früher Schlag bedeutet, dass Sie weniger Zeit haben, um einen Vorteil zu nutzen, den Sie vielleicht finden.
Douglas Zare
3
Ein anderer Weg, um zu sehen, dass diese probabilistische Methode nicht optimal ist, besteht darin, den letzten Flip zu berücksichtigen. Sie sollten keine Stichprobe aus der Verteilung für B ziehen, um zu entscheiden, ob B beim letzten Wurf gewürfelt wird. Sie sollten den Mittelwert mit . 0,5
Douglas Zare
1
@DouglasZare Wenn Ihre einzige Messgröße die erwartete Anzahl der Köpfe ist, ist es angesichts unserer Münzwürfe die beste Strategie, immer Münze A zu wählen. Dies ist jedoch unvollständig, da zu viel auf die Explioitation und nicht genug auf die potenzielle Oberseite von geachtet wird Erforschung . Die logische Konsequenz Ihres Vorschlags ist, wenn wir das Experiment neu starten, Münze B einmal umzuwerfen: Wenn es sich um Tails handelt, wählen Sie immer A; andernfalls drehe es noch einmal um, wenn es Heads ist, wähle immer B.
Cam.Davidson.Pilon
9

Dies ist ein einfacher Fall eines mehrarmigen Banditenproblems . Wie Sie bemerken, möchten Sie die gesammelten Informationen ausgleichen, indem Sie die unbekannte Münze ausprobieren, wenn Sie der Meinung sind, dass sie auf kurze Sicht nicht optimal ist, und nicht, wenn Sie das vorhandene Wissen ausnutzen.

1/2

Im Allgemeinen glaube ich, dass Sie nicht von einem dynamischen Programmierproblem loskommen können, obwohl es Sonderfälle geben kann, in denen die optimale Strategie einfacher gefunden und überprüft werden kann.

Mit einem Uniformprior sollten Sie hier aufhören:

(0 heads,3 tails),(1 head,5 tails),(2 heads,6 tails),(3,7),(4,8),...(31,35),(32,35),(33,36),(34,37),...(41,44),(42,44),...(46,48),(47,48),(48,49),(49,50)

61.3299

Ich habe den folgenden Mathematica-Code verwendet, um die Aktien zu berechnen:

Clear[Equity];
Equity[n_, heads_, tails_] := Equity[n, heads, tails] = 
    If[n == 0, heads, 
       Max[1/2 + Equity[n - 1, heads, tails], 
           (heads + 1)/(heads + tails + 2) Equity[n - 1, heads + 1, tails] + 
           (tails + 1)/(heads + tails + 2) Equity[n - 1, heads, tails + 1]
           ]
      ]

Zum Vergleich ergibt die von Cam Davidson Pilon als optimal bezeichnete Thompson-Stichprobenheuristik einen um 1.03915 niedrigeren Durchschnitt von 60.2907 Köpfen. Thompson Sampling hat das Problem, dass es manchmal B abtastet, wenn Sie genug Informationen haben, um zu wissen, dass es keine gute Wette ist, und es verschwendet oft die Chance, B früh abzutasten, wenn die Informationen die meisten wert sind. Bei dieser Art von Problem ist es Ihnen fast nie gleichgültig, welche Optionen Sie haben, und es gibt eine rein optimale Strategie.

tp[heads_, tails_] := tp[heads, tails] = 
    Integrate[x^heads (1 - x)^tails / Beta[heads + 1, tails + 1], {x, 0, 1/2}]


Clear[Thompson];
Thompson[flipsLeft_, heads_, tails_] := Thompson[flipsLeft, heads, tails] = 
    If[flipsLeft == 0, heads, 
       Module[{p = tp[heads, tails]}, 
           p (1/2 + Thompson[flipsLeft-1,heads,tails]) + 
           (1-p)((heads+1)/(heads+tails+2)Thompson[flipsLeft-1,heads+1,tails] + 
           ((tails+1)/(heads+tails+2)) Thompson[flipsLeft-1,heads,tails+1])]]
Douglas Zare
quelle
Ich stimme zu, dass eine optimale Lösung besser wäre als eine ungefähre. Ich frage mich, ob es eine optimale allgemeine Lösung gibt, die in einer dynamischen Umgebung mit mehreren hundert "Münzen" innerhalb von Millisekunden effizient angewendet werden kann. Wenn nicht, ist Thompson-Sampling die beste Option.
M. Cypher
Die Thompson-Abtastung ist eine schlechte Näherung. Es gibt bessere Näherungen, die Sie verwenden können, wenn Sie nicht die Mühe der (im schlimmsten Fall quadratischen) exakten Berechnung auf sich ziehen, aber dennoch große Fehler vermeiden möchten. Tatsächlich könnte die genaue Berechnung eher linear sein.
Douglas Zare
PrB(heads)(0,1)1/250
Ich kenne Mathematica nicht und kann daher nicht nachvollziehen, wie Sie Ihre erwartete Anzahl von Köpfen berechnet haben. Möchtest du diesen Teil erklären? Wenn wir davon ausgehen, dass die Verzerrung von Münze B von einer gleichmäßigen Verteilung auf [0,1] herrührt, sehe ich nicht, wie Sie mit einem Sieg von 50/50 rechnen können.
Jerad
1
Douglas: Weil ich mehr auf deine Antwort geachtet habe :-). Bitte versteh mich nicht falsch - ich mag es und ich mag diesen Thread. Ich fand es wichtig, darauf hinzuweisen, dass Sie eine Annahme hinzufügen müssen, um Ihre Antwort zu erhalten, das ist alles. In der Praxis gibt es in vielen Situationen - einschließlich dieser - keine Vorbedingung . (Ich würde mir sicher keinen persönlichen Prior ausdenken und dann viel Geld darauf setzen müssen!) Aber natürlich gibt es immer noch ein Optimum, vorausgesetzt, Sie geben eine Verlustfunktion an. ("Maximieren" einer Erwartung ist keine vollständige Verlustfunktion.)
whuber