Multi-armed Bandits: uma alternativa para testes A/B
Como acelerar os resultados de um teste A/B e evitar custos desnecessários?
A versão em inglês deste artigo está disponível em Multi-armed Bandits: an alternative to A/B testing
O teste A/B é uma prática muito utilizada em diversas empresas para comparar duas ou mais estratégias e/ou versões de um produto (anúncio, design, página de destino, etc.) e obter aquele que tem um melhor desempenho, ou seja, que tem uma taxa de conversão superior às outras. Por exemplo, considere um aplicativo de uma empresa, um possível teste é considerar se a cor de um botão deve ser azul ou laranja. Com o teste A/B dividimos o público na qual uma parte recebe a versão com o botão azul e outra parte com o botão laranja, e analisa-se qual das versões obteve uma taxa de cliques maior.
A figura acima ilustra o funcionamento do teste A/B: as diferentes variantes do produto são divididas aleatoriamente para os usuários com uma distribuição fixa. Assim, uma parte do público recebe apenas a versão A do produto enquanto a outra parte apenas a versão B por um certo período de tempo. Ao fim desse período, testes estatísticos são aplicados com o intuito de observar qual das diferentes versões tem um resultado melhor.
Entretanto há alguns problemas com o teste A/B:
- há um alto custo com as versões “ruins” do produto, pois elas continuarão sendo oferecidas ao usuário até o fim do teste sendo que o retorno delas não são boas;
- existe também o risco de perder usuários, pois aqueles que durante todo o período de teste que receberam a versão “ruim” do produto podem ficar insatisfeitos.
Existe alguma alternativa ao teste A/B para evitar esses problemas? Ou seja, que podemos reduzir esses custos associados às versões inferiores do produto?
Multi-armed Bandits
O Aprendizado por Reforço é uma técnica de aprendizado de máquina na qual o agente aprende interagindo com o ambiente. Primeiramente o agente observa o estado do ambiente e executa uma ação baseada na sua observação. Essa ação irá modificar o ambiente que transiciona para um novo estado e retorna uma recompensa para o agente dependendo se a ação foi boa ou não. O objetivo do agente é aprender uma política, ou seja, como escolher as ações de modo a receber o máximo de recompensa possível a longo prazo. Imagine por exemplo um jogo de xadrez: o ambiente é o tabuleiro em si e o seu estado corresponde ao posicionamento das peças em determinada fase do jogo. As ações do agente são todos os movimentos que ele pode fazer e a recompensa é de acordo com o resultado final do jogo (vitória, derrota ou empate).
O Multi-armed Bandits (MaB) [1] é um caso específico e mais simples do problema de aprendizado por reforço na qual você tem k diferentes opções (ou ações) A₁, A₂, …, Aₖ, cada uma associada a uma distribuição real R= {R₁, R₂, …, Rₖ} correspondente às recompensas, onde μ₁, μ₂,…, μₖ são as médias dessas distribuições, respectivamente. Assim o agente executa iterativamente uma ação Aₜ de acordo com a sua política e recebe uma recompensa numérica rₜ (que é amostrada a partir da distribuição Rₜ) associada à essa ação. O objetivo é maximizar as recompensas recebidas durante as interações, ou seja, encontrar a ação que possui a maior recompensa esperada. Em outras palavras, o agente precisa descobrir as distribuições de recompensa associadas a cada ação para obter aquela que possui o maior retorno esperado. Uma possível métrica para avaliar o aprendizado do agente em T interações é o arrependimento ρ, dada pela diferença esperada entre a soma da recompensa associada à ação ótima com a soma das recompensas coletadas:
Onde μ* é a média da distribuição de recompensa associada à ação ótima e rₜ é a recompensa recebida no instante t.
O algoritmo base para o MaB é bem simples:
1. Obtém uma estimativa inicial de recompensa de cada uma das k ações
2. Para cada episódio t até T:
3. Seleciona uma ação de acordo com uma política
4. Obtém a recompensa dessa ação
5. Atualiza a estimativa da recompensa da ação escolhidaA política é o ponto principal de um algoritmo MaB, a qual está relacionada em como o agente irá escolher a ação de acordo com as estimativas de recompensa que ele possui. Essa escolha da ação depende da estratégia de exploration e exploitation de cada política.
Exploration vs Exploitation
Imagine que você está em uma cidade nova e não conhece nenhum restaurante da cidade. Na primeira vez, você vai em um restaurante A e gosta bastante dele, ou seja, ele tem uma boa recompensa. Na próxima vez fica o dilema: você deve ir no mesmo restaurante (exploitation), visto que você já sabe que ele é bom, ou você deve visitar um novo restaurante (exploration), para tentar descobrir algum outro que possivelmente seja melhor?
O ideal é que no começo seja feito mais exploration para que o agente consiga conhecer um pouco melhor o ambiente com a qual ele está interagindo, e no final, mais exploitation para usufruir da melhor ação considerando que o agente já conseguiu conhecer bem o ambiente, isto é, ter uma boa estimativa das recompensas de cada ação.
É justamente neste balanceamento entre o exploration e o exploitation que os diferentes algoritmos de MaB trabalham. Veremos em um artigo posterior alguns algoritmos de MaB detalhando cada uma delas. Agora, vamos ver como podemos aplicar o MaB em testes A/B e quais as suas vantagens :).
MaB e Teste A/B
Uma aplicação do MaB é justamente em testes A/B, na qual as diferentes versões do produto são mapeadas para as ações, e as taxas de conversão de cada produto para as recompensas. E como não se sabe a priori a verdadeira taxa de conversão de cada produto, o MaB se encaixa bem no problema para encontrar a versão ótima, i.e., que trás a maior recompensa.
Devido à natureza do MaB ser um método iterativo, a sua principal vantagem é que ele consegue dinamicamente mudar a distribuição de usuários que serão impactados com cada versão de produto, priorizando aqueles que obtiveram melhores recompensas, ou seja, atribuindo um volume maior de usuários para aquela versão. Em outras palavras, o método permite que você aprenda durante o teste, e não apenas no fim dele. Com isso é possível reduzir os custos associados às versões “ruins” visto que eles serão despriorizados durante o processo.
Além disso, conseguimos obter o resultado mais rápido do que no teste A/B, visto que a distribuição vai progressivamente favorecendo a variante com maior conversão.
Dito isso, o foco do MaB é maximizar os ganhos durante todo o período do teste, modificando, dinamicamente, as distribuições de cada variante do produto. Com isso temos as vantagens já citadas: diminuição no custo e obtenção do melhor grupo mais rápido. O trade-off que temos com relação ao teste A/B é que não é possível realizar testes estatísticos para demonstrar que duas versões são estatisticamente distintas ou não.
Conclusão
Neste artigo vimos o que são os testes A/B e alguns dos seus principais problemas e introduzimos o MaB e como eles são aplicados como uma alternativa para os testes A/B.
Em um artigo posterior apresentaremos os principais algoritmos do MaB, analisando a estratégia de cada uma para fazer o balanceamento entre o exploration e exploitation.
Referências
1. Slivkins, Aleksandrs. Introduction to Multi-Armed Bandits — https://arxiv.org/pdf/1904.07272.pdf
2. Gupta, Shubhankar. Multi-Armed Bandit (MAB) — A/B Testing Sans Regret — https://vwo.com/blog/multi-armed-bandit-algorithm/
3. Veleaev, Denis. How to generate a lot more leads and reduce costs? A/B Testing vs Reinforcement Learning. — https://towardsdatascience.com/reinforcement-learning-64730aaa46c9
4. Rafferty, Greg. A/B testing — Is there a better way? An exploration of multi-armed bandits — https://towardsdatascience.com/a-b-testing-is-there-a-better-way-an-exploration-of-multi-armed-bandits-98ca927b357d
