Pesquisa
Limpar pesquisa
Fechar pesquisa
Google Apps
Menu principal
true

Visão geral

Apêndice (experimento tipo multi-armed bandit)

Detalhes teóricos e de cálculo

Primeiro, lembre-se de que o nome "experimento tipo multi-armed bandit" descreve um problema para o qual várias "soluções" foram propostas. Se você pegar um livro sobre "Reforço de aprendizagem" encontrará diversas abordagens listadas no capítulo introdutório sobre experimentos tipo multi-armed bandits. Isso é porque a matemática por trás do problema de experimentos tipo multi-armed bandit é tão difícil que, na prática, são usadas soluções heurísticas aproximadas. As dificuldades matemáticas estão bem resumida em uma frase famosa de Peter Whittle (Whittle, 1979):

[O problema do experimento] foi formulado durante a [segunda] guerra mundial e os esforços para resolvê-lo exauriram tanto as energias e a mente dos analistas aliados que sugeriu-se que o problema fosse jogado para a Alemanha, como o instrumento final de sabotagem intelectual.

Usamos uma heurística conhecida como amostragem de Thompson, ou correspondência de probabilidades aleatórias, porque combina muitos dos melhores recursos dessas heurísticas. Você pode saber mais sobre essa técnica em [5] e consultar mais detalhes sobre suas propriedades matemáticas em [2] , [3] e [4].

Probabilidades do cenário ideal

A amostragem de Thompson atribui sessões aos cenários proporcionalmente à probabilidade de cada cenário ser o ideal. Isso é um cálculo bayesiano. θ = (θ1, θ2,..., θk) denotará o vetor das taxas de conversão para os cenários 1, …, k. E y denotará os dados observados até agora no experimento. Modelamos "y" como um vetor de resultados binomiais independentes e admitimos antecedentes uniformes independentes em θ. Ia(θ) denotará o indicador do evento que o cenário a é ideal. Então, podemos escrever:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

Essa integral pode ser resolvida de forma fechada (embora a solução de forma fechada envolva funções especiais complicadas, como a função beta incompleta) ou por integração numérica. Nos dois casos, o cálculo rapidamente se torna instável para valores relativamente pequenos de y. No entanto, as probabilidades do cenário ideal podem ser calculadas de forma estável pela simulação. Cada elemento θ é uma variável independente aleatória da distribuição beta. Simule uma matriz grande que contém resultados θ de distribuições beta relevantes, onde as linhas da matriz representam os resultados aleatórios e as colunas representam os cenários k do experimento. Uma estimativa de Monte Carlo da probabilidade do cenário ser o ideal é a fração empírica das linhas para as quais o cenário a teve o maior valor simulado. A probabilidade de que cada cenário supere o original pode ser calculada de forma semelhante.

Valor restante

A simulação que produz as probabilidades do cenário ideal também pode produzir a distribuição do valor restante no experimento. O valor restante é a distribuição superior de (θmax-θ*)/θ*, onde θmax é o maior valor de θ e θ* é o valor de θ para o cenário com maior probabilidade de ser o ideal. Para ilustrar o cálculo, suponha que existam três cenários com 20, 30 e 40 sessões, que geraram 12, 20 e 30 conversões. As probabilidades do cenário ideal são aproximadamente 0,09, 0,20 e 0,71. Os seis primeiros resultados da simulação de Monte Carlo de θ podem ser:

  [,1] [,2] [,3]
[1,] 0,54 0,73 0,74
[2,] 0,55 0,66 0,73
[3,] 0,53 0,81 0,80
[4,] 0,57 0,50 0,65
[5,] 0,52 0,67 0,83
[6,] 0,65 0,84 0,63

Calculamos o valor linha por linha, subtraindo o maior elemento da linha do elemento na coluna 3 (porque o cenário 3 tem maior probabilidade de ser o cenário ideal). Nas primeiras duas linhas o valor é zero porque o maior resultado aparece na coluna 3. Na terceira linha o valor é 0,01/0,80 porque a coluna 2 é 0,01 maior do que a coluna 3. Se continuarmos em cada linha, teremos uma distribuição de valores que poderíamos traçar em um histograma como o painel à esquerda da Figura A1. O cenário 3 tem uma probabilidade de 71% de ser o melhor. Portanto, o valor para alterar do cenário 3 é zero em 71% dos casos. O percentil 95 da distribuição de valor é o "valor potencial restante" do experimento, que nesse caso é cerca de 0,16. Você interpreta este número como "Ainda não temos certeza da CVR para o cenário 3, mas independente disso existe a probabilidade de 16% de outro cenário superá-lo".

O painel à direita na Figura A1 mostra o que acontece com a distribuição do valor restante no decorrer do experimento. Suponha que cada braço tinha cinco vezes o tamanho da amostra (assim, 100, 150, e 200 sessões) com cinco vezes o número de conversões (60, 100, 150). Com tamanhos maiores de amostra, teremos muito mais certeza sobre as taxas de conversão dos cenários. O cenário 3 tem agora cerca de 95% de chance de ser o cenário ideal. Sendo assim, o percentil 95 da distribuição de valor restante é zero.

Figura A1. A distribuição do valor restante em um experimento. A linha vertical em cada caso é o percentil 95 ou o valor potencial restante.
Este artigo foi útil para você?
Como podemos melhorá-lo?