Inversão de moeda, processos de decisão e valor da informação

Imagine a seguinte configuração: Você tem 2 moedas, a moeda A que é garantida como justa e a moeda B que pode ou não ser justa. Você é solicitado a fazer 100 lançamentos de moedas, e seu objetivo é maximizar o número de caras .

Sua informação prévia sobre a moeda B é que ela foi lançada 3 vezes e rendeu 1 cabeça. Se a sua regra de decisão baseasse simplesmente na comparação da probabilidade esperada de cara das 2 moedas, você jogaria a moeda A 100 vezes e terminaria com ela. Isso é verdade mesmo ao usar estimativas Bayesianas razoáveis ​​(médias posteriores) das probabilidades, pois você não tem motivos para acreditar que a moeda B produz mais cabeças.

No entanto, e se a moeda B for realmente tendenciosa em favor das cabeças? Certamente as "cabeças em potencial" que você desiste lançando a moeda B algumas vezes (e, portanto, obtendo informações sobre suas propriedades estatísticas) seriam valiosas em algum sentido e, portanto, levariam em consideração sua decisão. Como esse "valor da informação" pode ser descrito matematicamente?

Pergunta: Como você constrói uma regra de decisão ideal matematicamente neste cenário?

Bandido Multi-armado

Este é um caso particular de um problema de bandido multarmado . Eu digo um caso particular porque geralmente não sabemos qualquer das probabilidades de cara (neste caso, sabemos que uma das moedas tem probabilidade 0,5).

A questão que você levanta é conhecida como dilema de exploração versus exploração : você explora as outras opções ou se mantém com o que considera melhor. Existe uma solução ótima imediata, assumindo que você conhecia todas as probabilidades : basta escolher a moeda com a maior probabilidade de ganhar. O problema, como você aludiu, é que não temos certeza sobre quais são as verdadeiras probabilidades .

Há muita literatura sobre o assunto e existem muitos algoritmos determinísticos, mas desde que você marcou esse bayesiano, gostaria de falar sobre minha solução favorita: o bandido bayesiano !

A solução Baysian Bandit

A abordagem bayesiana para esse problema é muito natural. Estamos interessados ​​em responder "Qual é a probabilidade de a moeda X ser a melhor das duas?".

A priori , supondo que não tenhamos observado nenhum lançamento de moeda ainda, não temos idéia de qual seja a probabilidade das cabeças da moeda B, denotam esse desconhecido $p_B$ . Portanto, devemos atribuir uma distribuição uniforme anterior a essa probabilidade desconhecida. Alternativamente, nosso anterior (e posterior) para a moeda A é trivialmente concentrado inteiramente em 1/2.

Como você afirmou, observamos 2 caudas e 1 cara da moeda B, precisamos atualizar nossa distribuição posterior. Supondo que um uniforme anterior e flips sejam moedas de Bernoulli, nosso posterior é um . Comparando as distribuições posteriores ou A e B agora:$Beta( 1 + 1, 1 + 2)$

Encontrando uma estratégia aproximadamente ideal

Agora que temos os posteriores, o que fazer? Estamos interessados ​​em responder "Qual é a probabilidade da moeda B ser a melhor das duas" (lembre-se de nossa perspectiva bayesiana, embora exista uma resposta definitiva para qual a melhor, só podemos falar em probabilidades):

A solução aproximadamente óptima é escolher B com probabilidade e A com probabilidade 1 - w B . Esse esquema maximiza os ganhos esperados. w B pode ser calculado calculado numericamente, como sabemos a distribuição posterior, mas uma maneira interessante é a seguinte:$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.

Esse esquema também é auto-atualizável. Quando observamos o resultado da escolha da moeda B, atualizamos nosso posterior com essas novas informações e selecionamos novamente. Dessa forma, se a moeda B for muito ruim, escolheremos menos e, na verdade, a moeda B será muito boa, vamos escolher com mais frequência. É claro que somos bayesianos, portanto nunca podemos ter certeza absoluta de que a moeda B é melhor. Escolher probabilisticamente assim é a solução mais natural para o dilema exploração-exploração.

Este é um exemplo particular de Thompson Sampling . Mais informações e aplicativos interessantes para publicidade on-line podem ser encontrados no artigo de pesquisa do Google e no artigo de pesquisa do Yahoo . Eu amo essas coisas!

Este é um caso simples de um problema de bandidos com várias armas . Como você observa, você deseja equilibrar as informações coletadas experimentando a moeda desconhecida quando você pensa que é subótimo a curto prazo contra a exploração do conhecimento que possui.

$1/2$por escolha de A. Isso significa que, se é certo jogar a moeda A, então você deve continuar jogando A. Então, você só quer encontrar a regra de parada ideal para quando você deve desistir de B. Isso depende da distribuição anterior para o parâmetro para B e o número de tentativas. Com um número maior de tentativas, explorar tem mais valor, então você deve testar B mais.

Em geral, acho que você não consegue se livrar de um problema de programação dinâmica, embora possa haver casos especiais em que a estratégia ideal pode ser encontrada e verificada de maneira mais simples.

Com um uniforme anterior, aqui é onde você deve parar:

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

Sob essa estratégia, você espera coletar $61.3299$ cabeças.

Usei o seguinte código do Mathematica para calcular as ações:

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

Para comparação, a heurística de amostragem Thompson (que Cam Davidson Pilon afirmou ser ideal) fornece uma média de 60.2907 cabeças, menor em 1,03915. A amostragem Thompson tem o problema de, às vezes, amostrar B quando você tem informações suficientes para saber que não é uma boa aposta, e muitas vezes perde chances de amostrar B mais cedo, quando as informações valem mais. Nesse tipo de problema, você quase nunca fica indiferente entre suas opções, e existe uma estratégia ideal pura.

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