Чеканка монет, процессы принятия решений и ценность информации

14

Представьте себе следующую схему: у вас есть 2 монеты, монета A, которая гарантированно будет честной, и монета B, которая может быть или не быть честной. Вас просят сделать 100 монетных бросков, и ваша цель - максимизировать количество голов .

Ваша предварительная информация о монете B состоит в том, что она была подброшена 3 раза и принесла 1 голову. Если ваше правило принятия решения основывалось на сравнении ожидаемой вероятности выпадения двух монет, вы бы подбросили монету А 100 раз и с этим покончено. Это верно даже при использовании разумных байесовских оценок (апостериорных средних) вероятностей, поскольку у вас нет оснований полагать, что монета B дает больше голов.

Однако что, если монета B на самом деле смещена в пользу головы? Конечно, «потенциальные головы», которые вы бросаете, бросая монету B пару раз (и, следовательно, получая информацию о ее статистических свойствах), будут в некотором смысле полезны и, следовательно, будут влиять на ваше решение. Как эту «ценность информации» можно описать математически?

Вопрос: Как построить математическое правило оптимального решения в этом сценарии?

М. Сайфер
источник
Я удаляю свой ответ. Слишком много людей жалуются, что я явно использовал априор (что является стандартным в литературе). Наслаждайтесь неправильным ответом Кэма Дэвидсона Пилона, где он также принимает априор (но никто не возражает) и утверждает, что оптимальным является метод, который на 1,035 ниже оптимального.
Дуглас Заре
Ого, когда это все произошло? Кстати, я бы согласился с Дугласом, что использование априора в порядке. Я также отказываюсь от своего утверждения об оптимальности.
Cam.Davidson.Pilon
Я принимаю решение Кэма, потому что оно мне очень помогло. Я согласен, что это не оптимально, но если кто-то не может указать общее оптимальное решение, которое можно легко вычислить, это лучшая ставка.
М. Сайфер
Почему это было так плохо, что я использовал априор (который я четко указал), чтобы ответить на вопрос с меткой «байесовский»?
Дуглас Заре
1
Я не критиковал использование априора. Как упоминание я упомянул, что может быть более подходящих приоров, чем у единого (например, у Джеффри), но это лишь незначительно относится к вопросу. Ваше решение было прекрасно, но оно не так полезно для меня, так как оно не легко обобщается.
М. Сайфер

Ответы:

7

Многорукий бандит

Это частный случай проблемы многорукого бандита . Я говорю о конкретном случае, потому что, как правило, мы не знаем ни одной из вероятностей головок (в этом случае мы знаем, что одна из монет имеет вероятность 0,5).

Проблема, которую вы поднимаете, известна как дилемма исследование - эксплуатация : исследуете ли вы другие варианты или придерживаетесь того, что считаете лучшим. Существует немедленное оптимальное решение, предполагающее, что вы знали все вероятности : просто выберите монету с наибольшей вероятностью выигрыша. Проблема, на которую вы ссылались, заключается в том, что мы не уверены в том, каковы истинные вероятности .

Существует много литературы по этому вопросу, и есть много детерминированных алгоритмов, но так как вы пометили этот байесовский, я хотел бы рассказать вам о моем личном любимом решении: байесовский бандит !

Baysian Bandit Solution

Байесовский подход к этой проблеме очень естественен. Мы заинтересованы в ответе «Какова вероятность того, что монета Х является лучшей из двух?».

Априори , предполагая , что мы наблюдали не монета не переворачивает все же, мы не имеем ни малейшего представления о том , что вероятность глав нумизмата Б может быть, обозначу этот неизвестный . Таким образом, мы должны назначить предварительное равномерное распределение этой неизвестной вероятности. В качестве альтернативы, наша предшествующая (и задняя) монета А тривиально полностью сконцентрирована на 1/2.pB

Как вы сказали, мы наблюдаем 2 хвоста и 1 голову из монеты B, нам нужно обновить наше апостериорное распределение. Предполагая одинаковый априор, а броски - это броски Бернулли, наш апостериор - это . Сравнивая апостериорные распределения или А и Б сейчас:Beta(1+1,1+2)

введите описание изображения здесь

Нахождение примерно оптимальной стратегии

Теперь, когда у нас есть постеры, что делать? Мы заинтересованы в ответе «Какова вероятность, что монета B является лучшей из двух» (помните, с нашей байесовской точки зрения, хотя есть определенный ответ, какой из них лучше, мы можем говорить только с вероятностью):

wB=P(pb>0.5)

wB1wBwB

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

Эта схема также самообновляется. Когда мы наблюдаем результат выбора монеты B, мы обновляем нашу апостериор этой новой информацией и выбираем снова. Таким образом, если монета B действительно плохая, мы выберем ее меньше, а монета B на самом деле очень хорошая, мы выберем ее чаще. Конечно, мы байесовцы, поэтому мы никогда не можем быть абсолютно уверены, что монета B лучше. Подобный вероятностный выбор является наиболее естественным решением дилеммы разведки и эксплуатации.

Это частный пример отбора проб Томпсона . Дополнительную информацию и полезные приложения для онлайн-рекламы можно найти в исследовательской статье Google и Yahoo . Я люблю это!

Cam.Davidson.Pilon
источник
2
Я не думаю, что стратегия верна. Я не думаю, что вы должны выбирать, выбирать ли A или B вероятностно.
Дуглас Заре
2
Я не думаю, что бумага говорит, что вы думаете, что она делает. Если вы не согласны, пожалуйста, подсчитайте ожидаемое количество голов, которые вы получите по этой стратегии.
Дуглас Заре
5
Я не думаю, что это близко к оптимальному. Это говорит о том, что при первом броске вы выбрали B с вероятностью 1/2. Должно быть ясно, что вы не получите никакой информации, если выберете A, поэтому вы должны выбирать B все время. Сумма, которую вы теряете из-за этой ошибки, составляет около 0,12, когда вы ее совершаете, поэтому на первом этапе она стоит около 0,06. Вы теряете аналогичную сумму, когда грубо подбрасываете монету, чтобы решить, собирать ли какую-либо информацию на следующих нескольких шагах. Переворот означает, что у вас меньше времени, чтобы использовать преимущество, которое вы можете найти.
Дуглас Заре
3
0,5
1
@DouglasZare Если ваша единственная мера - это ожидаемое количество голов, учитывая, что мы подбрасываем монеты, тогда лучшая стратегия - всегда подбирать монету А. Но это неполно, так как в ней слишком много внимания уделяется объяснению , а недостаточно - потенциальному росту разведка . Логическое завершение вашего предложения состоит в том, чтобы, если мы возобновим эксперимент, подбросить монету B один раз: если это Хвосты, всегда выбирайте A; еще переверните его еще раз, если это Heads всегда выбирайте B.
Cam.Davidson.Pilon
9

Это простой случай проблемы многорукого бандита . Как вы заметили, вы хотите сбалансировать собираемую информацию, пытаясь найти неизвестную монету, если считаете, что в краткосрочной перспективе она неоптимальна и не использует ваши знания.

1/2

В общем, я думаю, что вы не можете избежать проблемы динамического программирования, хотя могут быть особые случаи, когда оптимальная стратегия может быть найдена и проверена более просто.

С единообразным предварительным, вот где вы должны остановиться:

(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

Я использовал следующий код Mathematica для вычисления акций:

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

Для сравнения, эвристика выборки Томпсона (которую, по утверждению Кэма Дэвидсона Пилона, является оптимальной) дает в среднем 60,2907 голов, что ниже на 1,03915. Проблема с выборкой Томпсона заключается в том, что она иногда производит выборку B, когда у вас достаточно информации, чтобы знать, что это не очень хорошая ставка, и она часто теряет шансы на выборку B на ранней стадии, когда информация стоит больше всего. В этом типе проблемы вы почти никогда не оставляете равнодушными ваши варианты, и существует чистая оптимальная стратегия.

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])]]
Дуглас Заре
источник
Я согласен, что оптимальное решение будет лучше, чем приблизительное. Интересно, существует ли оптимальное общее решение, которое можно эффективно применять в течение миллисекунд в динамической среде с несколькими сотнями «монет». Если нет, то я думаю, что выборка Томпсона является лучшим вариантом.
М. Сайфер
Выборка Томпсона - плохое приближение. Есть лучшие приближения, которые вы можете использовать, если вы не хотите проходить через проблему (в худшем случае квадратичного) точного вычисления, но все же хотите избежать больших ошибок. На самом деле, точный расчет может быть ближе к линейному.
Дуглас Заре
PrB(heads)(0,1)1/250
Я не знаю Mathematica, поэтому не могу понять, как вы рассчитали ожидаемое количество голов. Хотите объяснить эту часть? Если мы предположим, что уклон монеты B взят из равномерного распределения на [0,1], то я не понимаю, как вы можете ожидать, что вы победите 50/50.
Джерад
1
Дуглас: Потому что я уделил больше внимания вашему ответу :-). Пожалуйста, не поймите меня неправильно - мне это нравится, и мне нравится эта тема. Я подумал, что важно указать, что вам нужно добавить предположение, чтобы получить ответ, вот и все. На практике во многих ситуациях, в том числе и в этой , нет предшествующего . (Я уверен, что не хотел бы придумывать личное заранее, а затем ставить на него большие деньги!) Но, конечно, есть оптимальный вариант, если вы укажете функцию проигрыша. («Максимизация» ожидания не является функцией полной потери.)
whuber