Rzut monetą, procesy decyzyjne i wartość informacji

Wyobraź sobie następującą konfigurację: masz 2 monety, monetę A, która jest gwarantowana , oraz monetę B, która może, ale nie musi być uczciwa. Zostaniesz poproszony o wykonanie 100 rzutów monetą, a Twoim celem jest maksymalizacja liczby głów .

Wcześniejsze informacje na temat monety B były takie, że została ona odwrócona 3 razy i przyniosła 1 głowę. Jeśli twoja reguła decyzyjna polegała po prostu na porównaniu oczekiwanego prawdopodobieństwa głów 2 monet, rzuciłbyś monetę A 100 razy i skończyłbyś z nią. Jest to prawdą nawet przy zastosowaniu rozsądnych szacunków bayesowskich (średnich tylnych) prawdopodobieństw, ponieważ nie ma powodu, by sądzić, że moneta B daje więcej głów.

Co jednak, jeśli moneta B jest rzeczywiście stronnicza na korzyść głów? Z pewnością „potencjalne głowy”, które porzucisz kilkakrotnie przerzucając monetę B (a zatem uzyskując informacje o jej właściwościach statystycznych), byłyby w pewnym sensie cenne i dlatego wpłynęłyby na twoją decyzję. Jak matematycznie opisać tę „wartość informacji”?

Pytanie: Jak skonstruować matematycznie optymalną regułę decyzyjną w tym scenariuszu?

bayesian decision-theory M. Cypher
źródło

Usuwam moją odpowiedź. Zbyt wiele osób narzeka, że wyraźnie użyłem przeora (co jest standardem w literaturze). Ciesz się niepoprawną odpowiedzią Cam Davidson Pilon, w której również zakłada on przeora (ale nikt się nie sprzeciwia) i twierdzi, że jest optymalną metodą, która jest 1,035 poniżej optymalnej.

Douglas Zare

Whoah, kiedy to wszystko się stało? BTW, zgodziłbym się z Douglasem, że używanie przeora jest w porządku. Cofam również moje twierdzenie o optymalności.

Cam.Davidson.Pilon

Akceptuję rozwiązanie Cam, ponieważ bardzo mi pomogło. Zgadzam się, że nie jest to optymalne, ale chyba że ktoś wskaże ogólne optymalne rozwiązanie, które można łatwo obliczyć, jest to najlepszy zakład.

M. Cypher

Dlaczego było tak źle, że użyłem przeora (co wyraźnie stwierdziłem), aby odpowiedzieć na pytanie oznaczone jako „bayesian?”

Douglas Zare

Nie krytykowałem użycia przeora. Jako sidenotkę wspomniałem, że mogą być bardziej odpowiednie priorytety niż mundurowe (np. Jeffreya), ale ma to tylko nieznaczne znaczenie dla pytania. Twoje rozwiązanie było całkowicie w porządku, ale nie było dla mnie tak przydatne, ponieważ nie jest łatwe do uogólnienia.

M. Cypher,

Odpowiedzi:

Wieloręki bandyta

Jest to szczególny przypadek problemu wielorękiego bandyty . Mówię o konkretnym przypadku, ponieważ generalnie nie znamy żadnego prawdopodobieństwa głów (w tym przypadku wiemy, że jedna z monet ma prawdopodobieństwo 0,5).

Podnoszony przez ciebie problem jest znany jako dylemat eksploracji kontra eksploatacji : czy badasz inne opcje, czy trzymasz się tego, co uważasz za najlepsze. Istnieje natychmiastowe optymalne rozwiązanie, zakładając, że znasz wszystkie prawdopodobieństwa : po prostu wybierz monetę o najwyższym prawdopodobieństwie wygranej. Problem, jak wspomniałeś, polega na tym, że nie jesteśmy pewni, jakie są prawdziwe prawdopodobieństwa .

Istnieje wiele literatury na ten temat i istnieje wiele deterministycznych algorytmów, ale skoro oznaczyłeś ten Bayesian, chciałbym opowiedzieć o moim osobistym ulubionym rozwiązaniu: Bayesian Bandit !

Rozwiązanie Baysian Bandit

Bayesowskie podejście do tego problemu jest bardzo naturalne. Interesuje nas odpowiedź „Jakie jest prawdopodobieństwo, że moneta X jest lepsza z tych dwóch?”.

A priori , zakładając, że nie zaobserwowaliśmy jeszcze żadnych rzutów monetą, nie mamy pojęcia, jakie może być prawdopodobieństwo głów monet B, oznaczenie tego nieznanego . Powinniśmy więc przypisać wcześniejszy rozkład równomierny temu nieznanemu prawdopodobieństwu. Alternatywnie, nasz poprzedni (i późniejszy) moneta A jest trywialnie skoncentrowany całkowicie na 1/2. $p_B$

Jak już zauważyłeś, obserwujemy 2 ogony i 1 główkę z monety B, musimy zaktualizować nasz rozkład boczny. Zakładając jednolity przeor, a klapki są monetami Bernoulliego, naszym późniejszym jest . Porównując teraz rozkłady tylne lub A i B: $Beta( 1 + 1, 1 + 2)$

wprowadź opis zdjęcia tutaj

Znalezienie w przybliżeniu optymalnej strategii

Teraz, gdy mamy już tylnych, co robić? Interesuje nas odpowiedź „Jaka jest moneta prawdopodobieństwa B jest lepsza z dwóch” (Pamiętaj z naszej perspektywy bayesowskiej, chociaż istnieje wyraźna odpowiedź na to, która z nich jest lepsza, możemy mówić tylko z prawdopodobieństwem):

w_{B} = P (p_{b} > 0.5)

$w_B = P( p_b > 0.5 )$

W przybliżeniu optymalnym rozwiązaniem jest wybór B z prawdopodobieństwem i A z prawdopodobieństwem . Ten schemat maksymalizuje oczekiwane zyski. można obliczyć numerycznie, ponieważ znamy rozkład tylny, ale interesujący sposób jest następujący: $w_B$ $1 - w_B$ $w_B$

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

Ten schemat sam się aktualizuje. Kiedy obserwujemy wynik wybrania monety B, aktualizujemy nasz późniejszy o te nowe informacje i wybieramy ponownie. W ten sposób, jeśli moneta B jest naprawdę zła, wybieramy ją mniej, a moneta B jest naprawdę dobra, wybieramy ją częściej. Oczywiście jesteśmy Bayesianami, dlatego nigdy nie możemy być absolutnie pewni, że moneta B jest lepsza. Wybór probabilistycznie tego typu jest najbardziej naturalnym rozwiązaniem dylematu poszukiwawczo-wydobywczego.

Jest to szczególny przykład próbkowania Thompsona . Więcej informacji i fajne aplikacje do reklamy online, można znaleźć w pracy badawczej Google i pracy badawczej Yahoo . Uwielbiam te rzeczy!

Cam.Davidson.Pilon
źródło

Nie sądzę, żeby ta strategia była poprawna. Nie sądzę, że powinieneś decydować, czy wybrać probabilistycznie A czy B.

Douglas Zare

Nie sądzę, że ten papier mówi, co myślisz. Jeśli się nie zgadzasz, proszę obliczyć oczekiwaną liczbę zdobytych głów w ramach tej strategii.

Douglas Zare

Nie sądzę, żeby było to bliskie optymalności. Sugeruje to, że przy pierwszym rzucie wybrałeś B z prawdopodobieństwem 1/2. Powinno być jasne, że nie otrzymujesz żadnych informacji, jeśli wybierzesz A, więc powinieneś wybierać B przez cały czas. Kwota, którą stracisz przez ten błąd, wynosi około 0,12, gdy go popełnisz, więc kosztuje on około 0,06 na pierwszym kroku. Podobną kwotę tracisz, gdy z grubsza rzucasz monetą, aby zdecydować, czy chcesz zebrać jakieś informacje na następnych kilku krokach. Przerzucanie Wczesne oznacza, że masz mniej czasu na wykorzystanie przewagi, którą możesz znaleźć.

Douglas Zare

Innym sposobem, aby przekonać się, że ta metoda probabilistyczna nie jest optymalna, jest rozważenie ostatniego odwrócenia. Nie powinieneś próbować z rozkładu dla B, aby zdecydować, czy przerzucić B na ostatnim rzucie, powinieneś porównać średnią wartość z .

0.5

$0.5$

Douglas Zare

@DouglasZare Jeśli jedyną miarą jest spodziewana liczba głów, biorąc pod uwagę nasze rzuty monetami, najlepszą strategią jest zawsze wybieranie monety A. Ale jest to niekompletne, ponieważ zbyt mocno koncentruje się na eksplozji , a niewystarczająco na potencjalnym plusie eksploracja . Logicznym wnioskiem z Twojej sugestii jest to, że jeśli ponownie rozpoczniemy eksperyment, rzucisz monetą B jeden raz: jeśli jest to Ogon, zawsze wybierz A; inaczej odwróć to jeszcze raz, jeśli to jest Heads, zawsze wybieraj B.

Cam.Davidson.Pilon

Jest to prosty przypadek problemu wielorękiego bandyty . Jak zauważyłeś, chcesz zrównoważyć informacje, które gromadzisz, próbując nieznanej monety, gdy uważasz, że w krótkim okresie jest ona nieoptymalna, z wykorzystaniem posiadanej wiedzy.

W klasycznym problemie wielorękiego bandyty nie ma pewności co do prawdopodobieństwa dla obu monet. Jednak tutaj otrzymujesz informację, że znasz wartość monety A, więc po odwróceniu A nie otrzymasz żadnych informacji. W rzeczywistości równie dobrze możesz zignorować stochastyczną naturę A i założyć, że dostajesz płaską za wybór A. Oznacza to, że jeśli kiedykolwiek jest słuszne rzucić monetą A, to powinieneś ciągle przewracać A. po prostu chcę znaleźć optymalną regułę zatrzymania, kiedy należy zrezygnować z B. To zależy od wcześniejszego rozkładu parametru dla B i liczby prób. Przy większej liczbie prób odkrywanie ma większą wartość, więc testowałbyś B więcej. $1/2$

Ogólnie rzecz biorąc, myślę, że nie można uciec od problemu z dynamicznym programowaniem, chociaż mogą istnieć specjalne przypadki, w których można znaleźć i sprawdzić optymalną strategię w prostszy sposób.

Z mundurem przełożonym, tutaj powinieneś przestać:

$(0 ~ \text{heads}, 3 ~\text{tails}), (1 ~\text{head}, 5 ~\text{tails}), (2 ~\text{heads}, 6 ~\text{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)$ .

W ramach tej strategii spodziewasz się zebrać głów. $61.3299$

Użyłem następującego kodu Mathematica do obliczenia akcji:

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]
           ]
      ]

Dla porównania, heurystyka próbkowania Thompsona (którą Cam Davidson Pilon uznał za optymalną) daje średnio 60,2907 głów, niższą o 1,03915. Problem z próbkowaniem Thompsona polega na tym, że czasami pobiera próbki B, gdy masz wystarczającą ilość informacji, aby wiedzieć, że nie jest to dobry zakład, i często marnuje szanse na wcześniejsze pobranie próbki B, gdy informacja jest najbardziej warta. W tego rodzaju problemach prawie nigdy nie jesteś obojętny między opcjami i istnieje czysta optymalna strategia.

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
źródło

Zgadzam się, że optymalne rozwiązanie byłoby lepsze niż przybliżone. Zastanawiam się, czy istnieje optymalne ogólne rozwiązanie, które można skutecznie zastosować w ciągu milisekund w dynamicznym środowisku z kilkoma setkami „monet”. Jeśli nie, to próbowanie Thompsona jest najlepszą opcją.

M. Cypher,

Próbkowanie Thompsona jest słabym przybliżeniem. Są lepsze aproksymacje, których możesz użyć, jeśli nie chcesz przejść przez kłopot (najgorszego kwadratu) dokładnego obliczenia, ale nadal chcesz uniknąć dużych błędów. W rzeczywistości dokładne obliczenia mogą być bliższe liniowym.

Douglas Zare

Co pozwala nam założyć, że wcześniejsza dystrybucja na B? Przyznaję, że takie założenie sprawia, że problem jest łatwiejszy do rozwiązania, ale istnienie obiektywnie uzasadnionej oceny uczciwości B jest dla mnie wątpliwe. Tak, mamy wyniki niektórych poprzednich rzutów, ale są one nadal zgodne z dowolną wartością dla w . Jeśli w tym, że prawdopodobieństwo jest mniejsze niż , a ja nie dbam o to , co przed ty zdecydujesz się przyjąć: to będzie obiektywny fakt, że przewidywana liczba głowic z podejściem jest mniejsza niż .

\underset{B}{Pr} (heads)

$\Pr_B(\text{heads})$

(0, 1)

$(0,1)$

1 / 2

$1/2$

50

$50$

Whuber

Nie znam Mathematiki, więc nie mogę śledzić, jak obliczyłeś oczekiwaną liczbę głów. Chcesz wyjaśnić tę część? Jeśli założymy, że stronniczość monety B jest pobierana z równomiernego rozkładu na [0,1], to nie widzę, jak można oczekiwać pokonania 50/50.

jerad

Douglas: Ponieważ zwracałem większą uwagę na twoją odpowiedź :-). Nie zrozumcie mnie źle - podoba mi się ten wątek. Pomyślałem, że ważne jest, aby zaznaczyć, że trzeba było założyć założenie, aby uzyskać odpowiedź, to wszystko. W praktyce w wielu sytuacjach - w tym w tej - nie ma wcześniejszego . (Na pewno nie chciałbym nadrobić osobistego przeora, a potem musiałbym postawić na to duże pieniądze!) Ale oczywiście jest jeszcze optymalny, pod warunkiem, że określisz funkcję straty. („Maksymalizacja” oczekiwania nie jest funkcją pełnej straty.)

whuber