Pesquisa
Limpar pesquisa
Fechar pesquisa
Google Apps
Menu principal

Visão geral

Experimentos tipo multi-armed bandit

Por Steven L. Scott, PhD, analista econômico sênior

Este artigo descreve o mecanismo estatístico por trás dos Experimentos de conteúdo do Analytics. O Analytics usa uma abordagem de experimentos tipo multi-armed bandit para gerenciar os experimentos on-line. Um experimento tipo multi-armed bandit tem as seguintes características:

  • A meta é encontrar a melhor ação ou a mais lucrativa
  • Pode ser feito upload da distribuição aleatória durante o progresso do experimento

O nome "experimento tipo multi-armed bandit" descreve um experimento hipotético na qual você enfrenta diversas máquinas caça-níqueis (chamada de "one-armed bandits", em inglês) com resultados esperados potencialmente diferentes. Você quer encontrar a máquina com a melhor taxa de resultado, mas também que maximizar seus ganhos. A tensão fundamental é entre "explorar" os cenários com bom desempenho no passado e "estudar" cenários novos ou aparentemente inferiores caso eles possam ter um desempenho ainda melhor. Existem modelos matemáticos altamente desenvolvidos para gerenciar esse problema que podemos usar nos Experimentos de conteúdo do Analytics.

Este documento começa com um histórico geral sobre o uso de experimentos tipo multi-armed bandit no Analytics. Depois ele apresenta dois exemplos de experimentos simulados realizados usando nosso algoritmo multi-armed bandit. Em seguida, aborda algumas perguntas frequentes e conclui com um apêndice que descreve os detalhes teóricos e técnicos dos cálculos.

Histórico

Como os experimentos funcionam

Duas vezes por dia, examinamos seu experimento para ver o desempenho de cada uma das variações e ajustamos a fração do tráfego que cada variação receberá desse momento em diante. Uma variação que aparentemente tem se saído bem obtém mais tráfego, e uma variação com um desempenho claramente insatisfatório obtém menos. Os ajuste realizados têm como base uma fórmula estatística (consulte o apêndice para mais detalhes) que considera o tamanho da amostra e as métricas de desempenho juntas para que tenhamos certeza de que as diferenças de desempenho são reais, não apenas coincidência. À medida que o experimento avança, sabemos cada vez mais sobre os retornos relativos e, assim, fazemos um trabalho melhor escolhendo boas variações.

Vantagens

Os experimentos do tipo multi-armed bandit são geralmente mais eficientes do que experimentos "clássicos" A-B com base em testes de hipóteses estatísticas. Eles são estatisticamente tão válidos quanto e, em algumas circunstâncias, podem produzir respostas mais rapidamente. Elas são mais eficientes porque migram o tráfego para variações vencedoras gradualmente, em vez forçar você a aguardar uma "resposta final" ao término de um experimento. Elas podem ser mais rápidas porque as amostras que obviamente iriam para variações inferiores podem ser atribuídas a ganhadores em potencial. Os dados extra coletados nas variações com alto desempenho podem ajudar a separar os cenários "bons" dos "melhores" mais rapidamente.

Basicamente, eles tornam os experimentos mais eficientes. Portanto, use-os mais. Você também pode alocar uma fração maior de seu tráfego para seus experimentos, porque o tráfego será direcionado automaticamente para páginas com melhor desempenho.

Exemplos

Um teste simples A/B

Suponha que a taxa de conversão de seu site seja de 4%. Você faz experimentos com uma nova versão do site que, na verdade, gera conversões 5% do tempo. Você não conhece as taxas de conversão verdadeiras, é claro, por isso que está realizando o experimento. Suponhamos que você gostaria que o experimento detectasse uma taxa de conversão de 5% como estatisticamente significativa com probabilidade de 95%. Um cálculo de potência1 padrão diz que você precisaria de 22.330 observações (11.165 em cada cenário) para ter 95% de chance de detectar uma alteração de 0,04 a 0,05 nas taxas de conversão. Suponhamos que você receba cem sessões por dia para o experimento. Assim, ele levaria 223 dias para ser concluído. Em um experimento padrão, você espera 223 dias, realiza o teste de hipóteses e recebe sua resposta.

Agora vamos gerenciar as cem sessões diárias com o experimento tipo multi-armed bandit. No primeiro dia, cerca de 50 sessões são atribuídas a cada braço, e observamos resultados. Usamos o teorema de Bayes para calcular a probabilidade da variação ser melhor do que o original2. A probabilidade do original ser melhor é um menos esse número. Suponhamos que o original teve sorte no primeiro dia e parece ter 70% de chance de ser superior. Então, atribuímos a ele 70% do tráfego no segundo dia e 30% para a variação. No final do segundo dia, acumulamos todo o tráfego até o momento (dos dois dias) e recalculamos a probabilidade de cada cenário ser melhor. Isso nos dá a ponderação para o terceiro dia. Repetimos o processo até que um conjunto de regras de interrupção seja satisfeito (falaremos mais sobre as regras de interrupção abaixo).

A Figura 1 mostra uma simulação do que pode ocorrer com essa configuração. Nela você pode ver as ponderações de apresentação do original (a linha preta) e da variação (a linha pontilhada vermelha), essencialmente se alternando até que a variação finalmente cruze a linha de confiança de 95%. As duas percentagens devem totalizar 100%. Sendo assim, quando uma sobe, a outra desce. O experimento foi concluído em 66 dias, o que reduziu o teste em 157 dias.

Figure 1. Uma simulação das probabilidades ideais de cada cenário para um experimento simples com dois cenários. Essas ponderações fornecem a fração do tráfego alocada em cada cenário em cada dia.

É claro que esse é apenas um exemplo. Nós refizemos a simulação 500 vezes para ver o desempenho em amostragens repetidas. A distribuição dos resultados é mostrada na Figura 2. Na média, o teste terminou 175 dias antes do que o teste clássico com base no cálculo de potência. A economia média foi de 97,5 conversões.

Figura 2. As distribuições do tempo e do número de conversões economizados em comparação com um experimento clássico planejado pelo cálculo de potência. Leva em consideração um original com 4% de CvR (taxa de conversão) e uma variação com 5% de CvR.

E sobre a validade estatística? Usando menos dados, não estamos aumentando a taxa de erros? Na verdade não. Dos 500 experimentos mostrados acima, em 482 o cenário correto foi encontrado. Isso significa 96,4%, que é aproximadamente a mesma taxa de erro do teste clássico. Houve alguns experimentos em que o tipo multi-armed bandit levou mais tempo do que a análise de potência sugeriu. No entanto. isso ocorreu em cerca de 1% dos casos (5 em 500).

Nós também realizamos o experimento inverso, em que o original tinha uma taxa de sucesso de 5% e a variação tinha 4%. Os resultados foram essencialmente simétricos. Novamente, o experimento tipo multi-armed bandit encontrou o cenário correto 482 vezes de 500. O tempo médio economizado em relação ao experimento clássico foi de 171,8 dias, e o número médio de conversões economizadas foi de 98,7.

Interrupção do experimento

Por padrão, forçamos a execução do experimento tipo multi-armed bandit por pelo menos duas semanas. Depois disso, acompanhamos duas métricas.

A primeira é a probabilidade de cada variação superar o original. Se tivermos 95% de certeza de que a variação supera o original, o Analytics declara que um vencedor foi encontrado. Tanto a duração mínima de duas semanas quanto o nível de confiança de 95% podem ser ajustados pelo usuário.

A segunda métrica que monitoramos é o "valor potencial restante no experimento", que é particularmente útil quando há vários cenários. Em qualquer momento do experimento há um cenário "campeão" que se acredita ser o melhor. Se o experimento fosse encerrado "agora", o campeão seria o cenário escolhido por você. O valor restante em um experimento é a quantidade da taxa de conversão aumentada que você poderia conseguir ao alternar o campeão. O motivo do experimento é a procura desse valor. Se você tem 100% de certeza de que o campeão é o melhor cenário, não há valor restante no experimento e nem motivo para fazer o experimento. Mas, se você tiver apenas 70% de certeza que um cenário é o ideal, poderemos usar a regra de Bayes para trabalhar melhor a distribuição. Consulte o apêndice para mais detalhes sobre os cálculos.

O Analytics encerra o experimento quando existe uma probabilidade de pelo menos 95% de que o valor restante no experimento seja menor do que 1% da taxa de conversão do campeão. Isso é uma melhoria de 1%, não um ponto percentual de melhoria. Se o melhor cenário tiver uma melhor taxa de conversão de 4%, encerraremos o experimento se o valor restante no experimento for menor do que 0,04 pontos percentuais da CvR.

Encerrar um experimento com base no valor potencial restante é bom porque não deixa dúvidas. Em um experimento com vários cenários, por exemplo, é possível que dois ou mais cenários tenham desempenho semelhante. Sendo assim, não importa qual for escolhido. Você não gostaria de realizar o experimento até encontrar o melhor cenário, já que existem dois cenários ideais. Você quer realizar o experimento apenas até ter certeza de que alterar os cenários não ajudará muito.

Experimentos mais complexos

A vantagem do experimento tipo multi-armed bandit em relação a experimentos clássicos aumenta conforme os experimentos ficam mais complexos. Você provavelmente tem mais do que uma ideia de como melhorar sua página na Web e, portanto, mais de uma variação que gostaria de testar. Suponhamos que você tenha cinco variações, além do original. Você fará um cálculo comparando o original à maior variação. Sendo assim, faremos alguns ajustes na conta para várias comparações. A correção de Bonferroni é um ajuste fácil (e conservador) que pode ser implementado dividindo o nível de significância do teste de hipóteses pelo número de cenários. Assim, fazemos o cálculo de potência padrão com um nível de significância de 0,05 / (6-1) e descobrimos que precisamos de 15.307 observações em cada cenário do experimento. Com seis cenários, temos um total de 91.842 observações. Com cem sessões diárias, o experimento teria que ser realizado por 919 dias (mais de dois anos e meio). Na vida real, não faz sentido executar um experimento por tanto tempo, mas ainda podemos pensar no experimento como uma simulação.

Agora vamos realizar o experimento com seis cenários por meio do simulador de experimentos do tipo multi-armed bandit. Novamente, assumiremos um cenário original com taxa de conversão de 4% e um cenário ideal com uma taxa de conversão de 5%. Os outros quatro cenários incluem um quase ideal que supera o original com uma taxa de conversão de 4,5% e três cenários inferiores, com taxas de 3%, 2% e 3,5%. A Figura 3 mostra a distribuição dos resultados. A duração média do experimento é de 88 dias (comparado com 919 dias para o experimento clássico) e o número médio de conversões economizadas é de 1.173. Nem sempre os experimentos de distribuição terminam rápido, mas mesmo nos piores casos, executar o experimento do tipo multi-armed bandit economiza mais de 800 conversões em comparação com o experimento clássico.

Figura 3. Economias em um experimento com seis cenários e comparação com um cálculo de potência ajustado de Bonferroni para um experimento clássico. O painel à esquerda mostra o número de dias necessários para encerrar o experimento, e a linha vertical mostra o tempo necessário para o cálculo de potência clássico. O painel à direita mostra o número de conversões que foram economizadas pelo experimento tipo multi-armed bandit.

As economias de custo são atribuídas parcialmente ao encerramento mais rápido do experimento e parcialmente aos fato de que o experimento gasta menos quando está em execução. A Figura 4 mostra o histórico das ponderações de apresentação para todos os cenários nas primeiras 500 simulações realizadas. Há uma certa confusão no início, enquanto define-se quais cenários têm um bom desempenho e quais não têm. No entanto, os cenários com desempenho ruim têm sua ponderação diminuída rapidamente. Neste caso, o cenário original tem sorte no início do experimento e sobrevive mais tempo do que outros cenários concorrentes. Mas depois de cerca de 50 dias, as coisas se estabeleceram em uma corrida entre o cenário original e o vencedor final. Depois que os outros cenários foram eliminados, o original e o vencedor final dividiram as cem observações diárias entre eles. Veja como as observações estão sendo alocadas de forma eficiente do ponto de vista econômico (estão sendo direcionadas para os cenários com maior probabilidade de dar um bom retorno), bem como do ponto de vista estatístico (estão sendo direcionadas para os cenários que queremos conhecer melhor).

Figura 4. Histórico das ponderações de apresentação em um dos seis cenários do experimento.

A Figura 5 mostra o custo diário de execução do experimento tipo multi-armed bandit em relação a uma estratégia "oracle" de sempre usar o cenário 2, o cenário ideal. Isso é injusto porque na vida real não sabemos qual é o cenário ideal, mas é um ponto de partida útil. Em média, cada observação atribuída aos original custa 0,01 de uma conversão, porque a taxa de conversão do original é 0,01 menor do que a do cenário 2. Da mesma forma, cada observação alocada ao cenário 5, por exemplo, custa 0,03 conversões, porque sua taxa de conversão é 0,03 menor do que a do cenário 2. Se multiplicarmos o número de observações atribuídas a cada cenário pelo custo dele e somarmos todos os cenários, teremos os custo de execução do experimento para o dia. No experimento clássico, são alocadas 100 / 6 sessões por dia para cada cenário (em média, dependendo de como as observações parciais são alocadas). Assim, o experimento clássico custa 1,333 conversões a cada dia de execução. A linha vermelha na Figura 5 mostra o custo de execução diário do experimento tipo multi-armed bandit. Com o passar do tempo, o experimento começa a gastar cada vez menos, conforme os cenários inferiores vão recebendo menor peso.

Figura 5. Custo por dia de execução do experimento tipo multi-armed bandit. O custo diário constante da execução do experimento clássico é mostrado pela linha horizontal tracejada.

1O power.prop.test da função R realizou todos os testes de potência neste artigo.

2Consulte o apêndice para ver os detalhes do cálculo. Se quiser, pode ignorá-los.

Este artigo foi útil para você?
Como podemos melhorá-lo?