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

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

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

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

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

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

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

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

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

Baysian Bandit Solution

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

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

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

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

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

$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.

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

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

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

$1/2$

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

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

$(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)$

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