Quando o Teste A/B não é o suficiente: melhorando suas escolhas com Multi-Armed Bandit
Imagine a seguinte situação: um produto novo da sua empresa foi criado e ele será anunciado em uma nova página. Três opções de página foram criadas e você precisa decidir qual delas vai para o ar.
Talvez você tenha pensado em fazer um Teste A/B(/C) para descobrir qual das 3 páginas possui o melhor desempenho. Vamos ver o que aconteceria nesta situação supondo que este teste vá durar 4 semanas:
Após 4 longas semanas nós descobrimos que a Página A possui a melhor taxa de conversão. A partir da semana 5 temos que 100% do nosso tráfego passará apenas pela melhor página, colocando um fim ao nosso dilema.
Até então tudo lindo, problema resolvido e todas as pessoas felizes, não? Bem, pode ser que exista um problema com a metodologia acima. Olhe novamente para a imagem acima mas prestando atenção nas Páginas B e C. Você vê algum problema aí?
Vamos supor que nossa vencedora Página A teve uma taxa de conversão “apenas” 1 p.p. melhor que as demais. Considerando que o tráfego em cada página testada foi de aproximadamente 1 milhão de pessoas semanalmente, significa que esta página gera cerca de 10 mil negócios a mais por semana em comparação às outras variantes.
Levando em conta que foram 4 semanas de teste e que outras 2 milhões de pessoas não passaram inicialmente pela nossa melhor opção, tivemos 80 mil negócios não fechados durante o período de teste.
E se o cenário tivesse sido o seguinte:
Neste caso em que as escolhas são dinâmicas, de modo que se aumenta gradualmente o percentual de clientes que visualizam a Página A, o número de pessoas impactadas por uma solução sub-ótima seria bem menor, gerando 50 mil negócios a mais que o Teste A/B convencional.
Mas como fazer esta escolha mais inteligente e dinâmica ? É aí que entra em cena o conceito do Multi-Armed Bandit (MAB).
O framework de Multi-Armed Bandit
Em poucas palavras, o MAB consiste em deixar um agente descobrir qual é a melhor variante de um experimento seguindo um política de aprendizado contínuo por tentativa e erro.
Assim como nós, este agente não sabe inicialmente qual das páginas do nosso exemplo é a melhor. Ele então começa uma série de interações com o ambiente, escolhendo diferentes ações (no caso cada ação é uma página diferente) e observando qual a recompensa que o ambiente retorna com base nessas escolhas. Esta recompensa pode ser tanto binária (1 no caso de sucesso e 0 no caso de fracasso) quanto numérica (o valor obtido pela venda de uma determinada variante ou o quanto de receita um determinado banner gerou, por exemplo).
A figura abaixo resume este processo:
Se você já estudou algo relacionado a Reinforcement Learning (ou Aprendizado por Reforço) provavelmente já viu alguma figura similar a essa. Acontece que o MAB é um problema de reforço simplificado onde o agente não sabe nada sobre o estado (ou o contexto).
Voltando ao nosso exemplo das páginas do novo produto, cada ação possível que o nosso agente pode executar é uma das 3 páginas (A, B ou C) e a recompensa no caso é representada por ou 0 (pessoa que viu a página escolhida não converteu) ou 1 (pessoa viu a página e converteu).
A medida que o agente interage mais com o ambiente, mais informações ele vai ter das possíveis ações com base nas recompensas obtidas e mais precisas serão suas escolhas futuras, aumentando a frequência da escolha das melhores ações com o tempo.
Como o agente faz as escolhas
Considere um cenário em que você quer jantar fora e tem duas opções: ir no lugar onde sabe que a comida é boa e você tem uma boa segurança de que vai sair de lá relativamente feliz ou arriscar um novo estabelecimento para ver como se sai, afinal ele poderia se tornar seu próximo lugar preferido a partir daquele momento.
Perceba que existe um certo dilema nessa escolha: aproveitar a opção confortável que sabe que vai trazer resultados ou explorar novas opções que podem lhe render frutos melhores que ainda são desconhecidos. Este conceito também existe em machine learning e é conhecido como Exploration vs Exploitation Dilemma.
Assim como na sua decisão sobre o jantar, o nosso agente também enfrenta esse problema ao ter que escolher entre escolher exibir a página que trouxe melhores resultados até então ou de explorar as outras para ganhar mais conhecimento sobre elas.
Para resolver este dilema o agente usa de algumas políticas de escolhas de forma a equilibrar a exploração e o aproveito. Vamos falar das 3 principais políticas utilizadas em Multi-Armed Bandit:
1) Ɛ-Greedy (ou Ɛ-Guloso)
Esta política é uma evolução da escolha aleatória com chances iguais. Aqui o agente possui uma pequena probabilidade Ɛ (geralmente entre 0.10 e 0.30) de realizar uma escolha aleatória e uma grande probabilidade 1-Ɛ de escolher o experimento com a melhor média de recompensas até então.
Desta forma nós garantimos que o agente aproveite desde cedo as melhores escolhas sem deixar de explorar os outros experimentos para adquirir conhecimento.
Como o MAB funciona com aprendizado contínuo é importante frisar que um experimento performando bem no começo não é garantia de que sempre vai ser o melhor. É perfeitamente possível que haja alguma mudança no ambiente em que uma outra variante passe a ser a melhor com o tempo.
2) UCB — Upper Confidence Bound
Uma das melhores definições que já li sobre UCB foi esta feita pelo Marlesson Santana:
O UCB é baseado no princípio do otimismo diante da incerteza, ou seja, braços que foram pouco explorados são escolhidos com maior frequência para que as incertezas com relação as suas recompensas sejam reduzidas.
Vamos olhar um pouco mais matematicamente para entender melhor:
A ação escolhida pela política UCB não depende apenas de possuir uma Recompensa Média mais alta que as demais, mas também de um alto valor para este segundo termo da equação c * Intervalo Superior. Este intervalo depende do número de vezes em que uma dada ação foi escolhida: quanto mais vezes ela foi escolhida, menor será este valor. Por fim o parâmetro de calibragem c é uma constante que representa o peso que daremos para este intervalo (geralmente é um número entre 1.0e 3.0). Quanto maior este valor, mais queremos que o agente explore em vez de aproveitar.
Explicando agora de uma maneira mais gráfica:
Num primeiro momento, numa das nossas páginas possui informação e nunca foram escolhidas, portanto tanto nossa recompensa média quanto nosso valor do intervalo superior serão os mesmos para todas as páginas. Podemos desempatar tanto escolhendo aleatoriamente ou ao escolher a primeira das opções.
Supondo que nossa escolha foi a Página A, o próximo momento será o seguinte:
Perceba que apesar da Página A ter se saído bem na sua primeira interação e sua recompensa média (linha preta) ter aumentado, as outras duas páginas possuem um maior valor devido ao peso do Intervalo Superior já que elas não foram escolhidas. O mesmo processo então se repete e a próxima página com a melhor possibilidade de recompensa é escolhida:
Como depois de mais duas interações todas as páginas foram escolhidas e as páginas B e C obtiveram fracassos (recompensa zero) o valor da recompensa média delas será inferior ao da Página A escolhida inicialmente. Como o termo de Aproveito c * Intervalo Superior de todas possui o mesmo valor (todas foram escolhidas apenas uma vez) então a Página A que agora possui a maior recompensa média é a página escolhida.
3) Thompson Sampling
A política de Thompson Sampling tem o objetivo de descobrir qual a distribuição das recompensas de cada variante. Para isso ela usa um tipo de distribuição bem adaptável da estatística conhecida como Distribuição Beta:
Esse tipo de distribuição é controlada por dois parâmetros, α (alfa) e β(beta). Pela imagem acima podemos notar três principais comportamentos:
- Maior alfa e Menor beta -> Maiores probabilidades
- Menor alfa e Maior beta -> Menores probabilidades
- Alfa e Beta com valores similares -> Probabilidades mais centradas ao redor de 0.50
Para cada sucesso obtido por uma escolha o parâmetro alfa aumenta em 1 e para cada fracasso o parâmetro beta aumenta em 1. A política Thompson Sampling é a única que vimos até agora que só aceita recompensas binárias.
Como cada variante do experimento terá sua própria distribuição de probabilidades beta, a escolha das ações da política Thompson Sampling é também probabilística, onde o experimento com maior probabilidade será escolhido mais frequentemente.
A grande vantagem dessa política em relação às Ɛ-Greedy e UCB é que os dois únicos parâmetros necessários, alfa e beta, não dependem do nosso controle, diferente dos parâmetros Ɛ e c.
Vamos ao exemplo prático:
No primeiro momento nenhuma página possui informação, portanto todas as distribuições são iguais e cada uma tem a mesma chance de ser escolhida. Neste caso hipotético a página A foi a escolhida.
Mais uma vez a Página A teve um sucesso no nosso exemplo, fazendo com que seu parâmetro alfa aumente, deslocando a distribuição de probabilidade desta variante para a direita e, com isso, aumentando sua chance de ser novamente escolhida.
Da imagem vemos que, mesmo a Página A possuindo essa maior chance, isso não garante que ela será escolhida, lembrando sempre que se trata de um fator probabilístico, o que garante que o fator exploração ainda estará será presente nas escolhas.
Nesse caso, a Página C é a próxima a ser exibida e seus parâmetros alfa e beta são atualizados conforme a recompensa obtida por ela.
Passadas algumas iterações, as distribuições beta de cada variante é atualizada para um valor mais próximo da realidade. No exemplo acima vemos que a Página A possui a distribuição mais à direita, com mais chance de ser escolhida, enquanto opostamente a Página C obteve piores desempenhos ao longo de suas interações e tem menor probabilidade de ser escolhida.
Um exemplo da vida real
Em vez de falarmos de páginas, vamos mudar um pouco o nosso problema. A bola da vez será testar diferentes mensagens de modo a descobrir qual delas possui uma melhor taxa de solução de problemas.
Vamos considerar neste exemplo a última política que vimos, Thompson Sampling, porque não queremos pré-estabelecer nenhum tipo de parâmetro para influenciar nas suas descobertas e também queremos saber a distribuição de probabilidades de sucesso de cada mensagem.
Considere também que a atualização das distribuições é feita diariamente, e não em tempo real, já que não saberemos a recompensa de uma determinada escolha antes de precisar escolher qual a próxima mensagem a ser enviada.
A figura abaixo mostra tanto qual foi a distribuição de probabilidades das mensagens do primeiro dia quanto os resultados obtidos:
Novamente vemos que no primeiro dia como não temos nenhuma informação sobre as mensagens todas têm a mesma probabilidade de serem escolhidas. Vendo os resultados obtidos por cada uma percebemos que existem casos em que não sabemos ainda se o problema foi ou não resolvido, portanto a recompensa ainda não foi contabilizada naquele momento, sendo necessário atualizá-las no dia seguinte.
Atualizadas as distribuições de probabilidade das três mensagens após o primeiro dia, vamos para o dia 2:
No segundo dia já vemos uma diferenciação entre as escolhas das mensagens, sendo a Mensagem C a mais escolhida (e portanto com o maior número de recompensas) e a Mensagem B a menos. Percebam que as recompensas que não obtivemos ao final do primeiro dia agora estão contabilizadas ao final do segundo. Após o final de mais um dia de experimentos os parâmetros alfa e beta de todas as distribuições são atualizados:
Passaram-se alguns dias dos nossos testes e descobrimos que a Mensagem B, antes a pior, mostrou-se a que mais possui uma taxa de solução para o nosso problema. O exemplo reforça a importância de que o teste deve seguir continuamente dado que nossa melhor variante a médio/longo prazo pode não ser a melhor a curto prazo, simplesmente pode ter sido obra do acaso de que no primeiro dia ela não teve um bom desempenho.
Vamos ver o que acontece no dia seguinte em que temos uma nova Mensagem D proposta pelo time de comunicação:
A nova mensagem começa sua jornada de exploração exatamente no mesmo pontos que as demais no primeiro dia, com parâmetros alfa e beta iguais a 1. Desta forma ela será mais escolhida que a pior e menos escolhida que a melhor, garantindo ainda assim que ela seja explorada.
Por fim, vamos imaginar que o nosso problema mudou e queremos agora maximizar a taxa de abertura das mensagens. Como o problema mudou a recompensa também muda já que não necessariamente um problema não resolvido significa também que a mensagem não foi aberta.
Como o nosso problema mudou, nós devemos resetar o experimento, ou seja, todas as distribuições voltam para o estado de desconhecimento com os parâmetros alfa e beta iguais a 1:
Então agora é um adeus ao Teste A/B?
Apesar de ter várias vantagens em relação ao Teste A/B, o Multi-Armed Bandit também apresenta algumas desvantagens:
- Como algumas variantes não terão o mesmo volume de dados, leva-se mais tempo para atingir a significância estatística. Além disso, perde-se um pouco da capacidade de aprendizado considerando outras variáveis já que o foco do MAB é apenas otimização.
- A otimização é feita usando apenas uma métrica, fazendo com que seja necessário recomeçar o teste caso haja alguma mudança de estratégia
Onde posso usar o Multi-Armed Bandit?
Existem algumas situações onde o framework de MAB seria mais indicado que o tradicional Teste A/B:
1. Onde o custo de oportunidade é bem alto
Como vimos no início do artigo, quando o teste envolve uma venda de imóveis, por exemplo, cada oportunidade perdida representa um grande impacto para o negócio.
2. Onde você quer focar em otimização contínua de apenas uma métrica bem estabelecida
Caso o problema de negócio a ser resolvido seja bem definido e a métrica de sucesso seja imutável, a otimização contínua do MAB é uma boa solução.
3. Otimização de fluxos com baixo tráfego
Com um baixo tráfego o volume de dados já é reduzido, então mesmo um Teste A/B convencional demoraria muito a atingir a significância estatística antes de uma otimização ser aplicada. Como essa é uma grande vantagem do Teste A/B que seria perdida, então o MAB poderia ser utilizado.
4. Otimização de métricas sensíveis com o tempo
Uma variante bem sucedida durante a Black Friday pode não ser a melhor em época de Natal. Como o MAB trabalha com otimização contínua ele pode lidar melhor com essa mudança de contexto temporal em comparação ao Teste A/B. Ainda sobre este ponto é recomendado a atenção das pessoas especialistas para que possa existir um hard reset das variantes caso haja alguma mudança muito drástica de domínio, como foi o caso da Covid-19 em março deste ano.
Conclusão
O Multi-Armed Bandit é um framework simples mas muito poderoso de testes contínuos que se bem utilizado pode entregar ótimos resultados ao negócio. Diversas grandes empresas como Facebook, Google, Amazon e Magazine Luiza usam este e outros algoritmos baseados neste mesmo princípio no seu dia a dia.
Caso você perceba que está investindo mais tempo analisando resultados de Teste A/B contínuos do que pensando nos experimentos em si que de fato entregam valor, pode ser o caso de dar uma chance a esta técnica.
Referências
Caso queira conhecer mais o MAB sob o ponto de vista técnico, inclusive com códigos em Python, recomendo o excelente artigo do Marlesson Santana:
Deixo também outros ótimos artigos como referência sobre o assunto:
Tem interesse em trabalhar conosco? Nós estamos sempre procurando por pessoas apaixonadas por tecnologia para fazer parte da nossa Tripulação! Você pode conferir nossas vagas aqui.
