Multi-Armed Bandits: Como fazer boas escolhas
Uma introdução ao problema dos bandidos com várias armas
Introdução
Considere o seguinte problema de aprendizagem:
Você se depara repetidamente com uma escolha entre k diferentes opções ou ações que devem ser tomadas. Após cada escolha, você recebe uma recompensa numérica que está ligada a sua escolha e que pode influenciar suas escolhas futuras. Seu objetivo é maximizar a recompensa total esperada ao longo do tempo fazendo as escolhas certas.
Esse é o problema que o Multi-armed Bandits (MaB) tenta resolver e que pode ser utilizando em diferentes aplicações. Por exemplo:
- Em sua modelagem mais exemplificada, podemos pensar em um cassino com diferentes máquinas (opções), cada máquina tem uma distribuição de probabilidade específica para dar a premiação (recompensa). O nosso objetivo é sair do cassino com a maior quantidade de dinheiro possível no final da noite (maximizar a recompensa).
- Essa mesma ideia pode ser utilizada em um Sistema de Recomendação, onde, repetidamente teremos que escolher o conteúdo que será apresentado para o usuário (ações), cada conteúdo tem uma distribuição de probabilidade de ser clicado (recompensa) e o objetivo do RecSys é maximizar a taxa de cliques no final do dia (maximizar a recompensa). Exemplo.
- Outro exemplo é a substituição de um teste A/B clássico. Você precisa escolher entre duas opções de telas a serem exibidas ao usuário, cada opção tem uma taxa de conversão diferente, essa é a recompensa, ao final de um ciclo espera-se escolher a opção que mais obteve conversão do usuário (maximizar a recompensa). Exemplo.
Existem várias aplicações para MaB, todas com a mesma ideia de maximizar uma recompensa ao longo do tempo, o que varia são as definições do que são os “braços ou arms”, que são as opções a serem escolhidas, e a modelagem da recompensa que queremos maximizar.
O grande problema a ser resolvido é que a priori não conhecemos a distribuição de probabilidade da recompensa de cada arm, caso contrário escolheríamos sempre o que tem a probabilidade maior de retornar a recompensa. Por isso a necessidade de explorar as opções e exploitar as melhores que encontrarmos.
Outro ponto é que a distribuição de probabilidade da recompensa pode mudar ao longo do tempo e por definição cada arm tem sua distribuição específica. Por esse motivo o algoritmo de Multi-armed bandits deve se adaptar e levar em consideração a exploração e a exploitação na escolha dos braços, o trade-off entre essas duas fases é a que trará a melhor recompensa média.
Multi-armed Badits
O MaB é definido como um problema de Reinforcement Learning (embora não na definição completa de RL por alguns pontos…) por ter essa modelagem de ambiente, agente e recompensa. O agente explora as opções e faz a escolha da ação com base em uma política, essa escolha é levada para o ambiente que retorna uma recompensa sobre essa ação. A recompensa pode ser usada para mudar as escolhas futuras do agente.
A escolha de uma política de exploração e exploitação dos braços é o que faz do MaB um algoritmo muito adaptável e que funciona bem em diferentes cenários. O algoritmo base de um MaB é muito simples, dado que temos k-braços, que são as possíveis escolhas, e que, queremos executar o algoritmo um total de T vezes, que é o tempo, o algoritmo base do MaB é:
1. Obtem uma estimativa inicial de recompensa de cada k-arm
2. Para cada episódio t até T:
3. Seleciona um arm de acordo com uma política
4. Obtem a recompensa desse arm
5. Atualizar a recompensa média O pseudo-algoritmo do MaB é simples, espera-se que a política de escolha do arm possa explorar o bastante para que o algoritmo tenha a confiança de fazer as escolhas certas, levando a maximização da recompensa a longo prazo com a exploitação da melhor opção.
Cenário
Vamos propor um cenário fictício para testar algumas ideias de MaB.
Somos uma empresa de venda de anúncios digitais e nosso principal objetivo é obter lucro com a venda dos anúncios. Devemos escolher o melhor anúncio dentre vários na nossa base para ser exibido a cada iteração. Cada clique garante o valor de R$ 1,00 e cada exibição gastamos um total de R$ 0,20.
Dessa forma, devemos criar um algoritmo que maximize o retorno financeiro da empresa com a exibição dos anúncios.
Utilizando o cenário proposto, podemos definir alguns pontos do nosso ambiente simulado:
- Nossos braços são os anúncios a serem exibidos, que aqui definiremos que são 50 anúncios diferentes. Cada anúncio tem uma probabilidade de ser clicado, esse valor é o ground-truth, o valor real que aconteceria em produção….. a priore esse valor é totalmente desconhecido pelos agentes por motivos óbvios.
Como estamos em um cenário fictício, iremos definir uma probabilidade de clique para cada anúncio seguindo uma Distribuição Beta com alpha=1.4 e beta=5.4 (algo como a imagem ao lado). Dessa forma, poucos anúncios terão uma probabilidade alta de serem clicados e a maioria uma probabilidade baixa.
Se visualizarmos a recompensa média acumulada de cada arm ao longo de 2000 iterações teríamos algo como a imagem ao lado. Seguindo a distribuição beta temos que alguns braços tem probabilidade alta de clique enquanto a maioria tem baixa probabilidade. Agora resta saber como escolheríamos os melhores anúncios em um ambiente dinâmico.
- A recompensa é o valor resultante da ação, que no nosso caso se o anúncio for clicado será de R$ 0,80 e se não for gastamos R$ 0,20 a toa. No momento podemos definir uma função de Reward Binária para simplificar e posteriormente transformaremos em custo.
- Iremos usar diferentes algoritmos de exploração usados no MaB para identificar qual consegue obter a maior recompensa média, ou seja, o que na média consegue obter mais cliques sem conhecer a distribuição de probabilidade real dos dados, o ground-truth.
Para isso nosso ambiente de simulação será algo como a função abaixo, que simula os passos que comentamos anteriormente do MaB:
Iremos simular 2000 iterações, ou steps, cada step é como se fosse uma interação do usuário com o site de notícias, em cada iteração a política vigente irá selecionar um anúncio (arm) dentre todos os disponíveis e apresentar ao usuário, dependendo da distribuição de probabilidade do anúncio ele será clicado ou não, retornando assim a recompensa dessa interação.
Random
Vamos partir de uma política burra para entender o básico do nosso ambiente simulado. Nessa política escolhemos aleatoriamente um anúncio dentre os 50 disponíveis para exibir. Como existem mais anúncios com probabilidade baixa de serem clicados é de se esperar que a Recompensa Média Acumulada seja baixa no final.
Exemplo de execução para apenas 10 steps. Em cada step é escolhido um arm pela política e coletado sua recompensa com base na distribuição de probabilidade de clique desse arm.
_, random_rewards = run(steps = 10,
arms= arms,
func_reward = reward,
policy = RandomPolicy(total_arms),
verbose=True)0: arm 38 with reward 0
1: arm 28 with reward 0
2: arm 14 with reward 0
3: arm 42 with reward 0
4: arm 07 with reward 1
5: arm 20 with reward 0
6: arm 38 with reward 0
7: arm 18 with reward 1
8: arm 22 with reward 0
9: arm 10 with reward 1
Reward Cum: 3
Se executarmos para 2000 iterações utilizando a política randômica de seleção, a probabilidade média de recompensa converge para 20% (que é a média da distribuição que nós utilizamos no ground-truth). Isso quer dizer que poderíamos estimar um ganho de R$ 0,00 (20%*R$ 1,00 - R$ 0,20) a cada step no final do experimento, um total de zero rendimentos ao final das 2000 iterações….. pelo menos não ficamos no prejuízo.
Ao utilizar uma política randômica não estamos considerando a qualidade do arm, então todos os braços são recomendados na mesma proporção. É possível observar que não existe diferença na quantidade de vezes que cada arm é recomendado ao visualizar a exploração do RandomPolicy
Epsilon-Greedy
O e-greedy é uma das políticas de exploração mais simples de implementar e entender. Basicamente é definido um valor de epsilon qualquer que será a probabilidade de exploração aleatória dos anúncios, algo como:
Dessa forma, a política define que a cada iteração existe uma probabilidade epsilon de se escolher um arm aleatório, e uma probabilidade 1-epsilon de se escolher o arm que tenha a recompensa média histórica maior, que no caso seria a melhor escolha. Isso garante que os braços serão todos testados com uma certa frequência, e, caso a distribuição de recompensa mude ao longo do tempo o algoritmo vai se adaptando devido à exploração constante.
O valor ideal do epsilon depende de cada caso, mas é fácil perceber que se epsilon=1 teremos apenas escolhas aleatórias igual o RandomPolicy, o que não faz muito sentido se queremos buscar o melhor resultado. Por outro lado, se epsilon=0 o algoritmo não explora nunca e sempre vai escolher o mesmo arm que foi melhor inicialmente, o que não garante que seja a melhor escolha a longo prazo e provavelmente seria uma solução sub-ótima e sem adaptação.
Ao executar o experimento para diferentes parâmetros de epsilon é interessante observar que o resultado pode variar bastante a depender do nível de exploração. No caso de epsilon=0, nesse exemplo ficou abaixo da política randômica, provavelmente por ter escolhido um arm inicial que parecia bom mas não era o melhor.
O espaço de recomendação do e-greedy é bem diferente do randômico, embora sempre teremos uma taxa fixa de exploração randômico, o algoritmo exploita a melhor opção até encontrar outra melhor opção. É possível observar que na iteração ~500 o algoritmo muda o comportamento e intensifica a recomendação de um anúncio diferente.
Essa mudança de comportamento é essencial para garantir que o algoritmo se adapte a mudança de cenário sempre que encontrar um arm melhor. Mas explorar de forma constante pode ser um problema em outros aspectos.
UCB — Upper Confidence Bound
UCB é um dos métodos mais amplamente usado para problemas de bandits. Esse algoritmo é 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.
A função que rege a escolha do arm é dada pela equação abaixo, onde, Q(a) é a recompensa média dada pelo arm ao longo do tempo (ou uma estimativa dela), c é um parâmetro de exploração, quanto maior menos confiança terá na estimativa, e sqrt(lnt/n(a)) é o que modela a incerteza como um limiar superior, quanto mais escolhas forem feitas usando o arm menor esse limiar.
O único detalhe da classe do UCB é que ele armazena a quantidade de escolhas de cada arm para usar na função de confiança.
Dependendo da parametrização o algoritmo pode ter um comportamento diferente, com mais ou menos exploração dos braços a cada escolha. Para o nosso exemplo o valor de c=0.5 foi o ideal e obteve um valor médio maior de recompensa.
É interessante notar a diferença do comportamento das escolhas em comparação com e-greedy. Aqui, acontece muito mais exploração no início e com pouca exploitação em um único arm. A exploração vai reduzindo a medida que a incerteza dos resultados vão diminuindo. Embora o crescimento seja mais lento, provavelmente a longo prazo o UCB encontre melhores resultados que o e-greedy.
UCB na prática é uma família de algoritmos e existem divérsas versões que modelam a confiança. https://www.youtube.com/watch?v=RPbtzWgzD9M
Thompson Sampling
O Thompson Sampling (TS) parte de uma ideia interessante. Se estamos querendo descobrir a distribuição de probabilidade real, por que não modelar uma distribuição de probabilidade a partir das recompensas e usar esse modelo para escolher o arm com a maior esperança de recompensa?
Uma distribuição de probabilidade bem conhecida e bem versátil é a Distribuição Beta, que a depender dos parâmetros de alpha e beta assume um comportamento totalmente diferente.
Essa versatilidade em mudar de forma faz do TS um método muito adaptável. Pois, se ajustarmos os valores de alpha e beta de cada arm teremos uma distribuição de probabilidade diferente para cada arm e possivelmente próxima da real.
Dessa forma, podemos seguir os seguintes passos:
- Inicializar o alpha e beta igual a um, o que inicia uma distribuição com probabilidade de recompensa de 50%.
- A cada step, amostramos uma recompensa através da distribuição que estamos criando de cada arm e selecionamos a que tem a maior recompensa esperada.
- Após receber a verdadeira recompensa atualizamos os valores de alpha e beta para que a próxima estimativa esteja mais correta.
Como todas as distribuições começam iguais o algoritmo consegue explorar bastante no começo e vai ajustando as estimativas de recompensa de cada arm
Quanto mais as distribuições são ajustadas mais assertivas são as escolhas de qual o arm tem a maior probabilidade de recompensa.
O efeito da exploração é semelhante ao do UCB, embora mais suave e assertivo. Dá para fazer um paralelo entre a confiança do UCB com o ajuste da distribuição beta, pois os dois melhoram a cada interação do arm.
Resultados
Utilizando a melhor parametrização encontrada de cada método podemos comparar as curvas de recompensa média. Embora o e-greedy tenha um crescimento rápido no começo, o que indica que provavelmente encontrou o melhor arm e começou a exploitar, seu crescimento é limitado pela taxa fixa de exploração. Por outro lado, o UCB e TS continuam sempre em crescimento, pois, a cada step a confiança e a distribuição beta estão mais ajustadas, garantindo assim um resultado melhor a longo prazo.
Ao final das 2000 iterações teríamos uma renda média por clique de aproximadamente R$ 0,38 centavos para o UCB e zerada para o Random. Claro que esses valores dependem de quantas iterações estamos usando, a curto prazo o e-greedy teria um retorno financeiro melhor do que o UCB ou TS.
A parametrização e o algoritmo ideal dependem do tipo de problema e contexto onde será utilizado. Existem diversos métodos de exploração que não foram utilizados aqui, para mais detalhes indico o artigo https://arxiv.org/abs/1904.07272
Todos os códigos utilizandos no artigo podem ser vistos aqui.
