O algoritmo de aprendizado por reforço Multi-Armed Bandit (MaB) é uma técnica de aprendizado de máquina que busca encontrar a melhor opção entre várias alternativas, levando em conta a recompensa e o custo de cada uma. O nome vem de uma analogia com um cenário em que um apostador ao lidar com várias máquinas caça-níqueis em um cassino, cada uma com uma probabilidade desconhecida de dar um prêmio e onde ele tem que escolher de forma inteligente e múltipla qual será a escolhida (por isso o polvo). O desafio é balancear a exploração das máquinas para aprender sobre elas e a explotação (escolha) da máquina que parece ser a mais lucrativa.
Existem diferentes estratégias para implementar o algoritmo MaB, como epsilon-greedy, upper confidence bound (UCB) ou Thompson sampling. Cada uma delas tem vantagens e desvantagens em termos de complexidade, convergência e eficiência. A seguir, explicaremos mais sobre a estratégia UCB.
Lembrando que vou deixar todos os códigos do post nas referências
...
Para fins didáticos eu tenho os seguintes dados que representam a quantidade de cliques de post por hora em um período de 31 dias. Os posts 3 é o melhor, seguido do post 1, mas é importante ter consciência que no momento que o algoritmo processa isso ela não tem noção do cenário geral de qual vai ser o melhor post (que fica evidente para gente), mas com o decorrer do tempo ele tende a convergir para o melhor.
The Upper Confidence Bound (UCB)
A estratégia UCB se baseia na ideia de que cada opção de ação tem um intervalo de confiança associado à sua estimativa de recompensa, uma boa representação disso são os box-plot que vimos agora pouco, porém essas distribuições não são conhecidas de início e depende do número de vezes que cada opção foi escolhida ao longo do tempo entendermos suas reais distribuições. Quanto mais vezes uma opção é escolhida, menor é o intervalo de confiança e mais precisa é a estimativa e evita que façamos uma escolha baseada em uma quantidade pequena de observações. A estratégia UCB consiste em escolher sempre a opção que tem o maior limite superior do intervalo de confiança, ou seja, a opção que tem o maior potencial de recompensa, e ele também pondera explorar um pouco opções que foram pouco escolhidas, dando uma segunda chance para que elas se provem. Isso garante que as opções com estimativas incertas sejam exploradas e as opções com estimativas promissoras sejam explotadas.
A vantagem da estratégia UCB é que ela é simples, eficiente e teoricamente ótimo, ou seja, ela minimiza o arrependimento esperado do agente (o algoritmo). O arrependimento é a diferença entre a recompensa ótima (a escolha sempre da melhor opção) e a recompensa obtida pelo agente. A desvantagem da estratégia UCB é que ela requer conhecer o número total de iterações do algoritmo e assumir que as recompensas seguem distribuições estacionárias e limitadas. Vou deixar aqui dois links que ajudam bem a compreender Multi-Armed Bandit e o UCB.
Abaixo temos a fórmula do Multi-Armed Bandit UCB;
t = o tempo (ou rodada) em que estamos atualmente
a = ação selecionada (no nosso caso o post escolhido)
Nt(a) = número de vezes que a ação a foi selecionada antes do tempo t
Qt(a) = recompensa média da ação a antes do tempo t
c = um número maior que 0 que controla o grau de exploração
Testando o desempenho
Para entender melhor essa exploração e explotação, eu processei duas vezes o algoritmo, a primeira com pouca exploração (c = 50) e a seguinte com muita exploração (c = 500). Repare que no primeiro caso ele identifica logo que os posts 3 e 1 são os melhores e tende a recomendar eles, para o segundo caso ele tenta mais verificar as outras opções já que a métrica de exploração foi alta , porém penaliza a recompensa final total.
Ficou evidente que calibrar bem a métrica de exploração vai definir a qualidade do resultado, como no nosso caso a distância geral dos posts 1 e 3 em relação aos outros é bem grande logo o modelo entende que eles são melhores escolhas. Abaixo você consegue ver o decaimento da recompensa total com o aumento do grau de exploração.
No nosso caso encontramos c=2 como grau de exploração que gera a maior recompensa que é apenas 1% menor que a melhor escolha contra 18% da escolha aleatória. Observe também que um grau de exploração alto demais se aproxima de uma escolha aleatória, o que é ruim.
Em resumo
O algoritmo de Multi-Armed Bandit UCB é um algoritmo de aprendizado por reforço que visa maximizar a recompensa ao longo do tempo. Para aplicar o algoritmo UCB, você deve levar em consideração as seguintes premissas:
Exploração vs. explotação: O algoritmo UCB tenta encontrar um equilíbrio entre explorar novas opções e explorar opções que já foram bem-sucedidas no passado. Isso é importante porque, se você explorar apenas novas opções, poderá perder oportunidades valiosas de recompensa. Por outro lado, se você explorar apenas opções que já foram bem-sucedidas no passado, poderá ficar preso em uma solução sub-ótima.
Recompensas estocásticas: O algoritmo UCB assume que as recompensas são estocásticas, o que significa que embora siga algum padrão, não tem um resultado previsível devido à influência de elementos aleatórios. Isso é importante porque, se as recompensas fossem determinísticas, seria fácil encontrar a melhor opção simplesmente escolhendo a opção com a maior recompensa.
Conhecimento prévio limitado: O algoritmo UCB assume que você tem conhecimento prévio limitado sobre as recompensas associadas a cada opção. Isso é importante porque, se você tivesse conhecimento completo sobre as recompensas associadas a cada opção, seria fácil encontrar a melhor opção simplesmente escolhendo a opção com a maior recompensa.
Bonûs
Como citado anteriormente o UCB assume que temos distribuições estacionárias e limitadas e por isso o conjunto de dados anterior era estacionário. Contudo a quantidade de cliques de post por hora em uma cenário real iria variar com o decorrer do tempo, subindo em um momento, decaindo em outro e outro post tomaria o seu lugar em destaque. Por curiosidade testei como ele desempenharia nesse cenário mais semelhante ao real. De inicio as nossas distribuições seriam algo mais parecido com o que temos abaixo. Observe que os posts 2 e 4 são os que tomam picos de acesso e nesses momentos seriam as melhores recomendações.
Agora veja como por conta da natureza mais complexa dado o ato de explorar é benéfico para o ganho das recompensas, chegando em um nível de estabilidade em que nesse caso foi otimizado para c=44.
Observe que o post 4 se destaca logo como recomendação, mas no momento que o post 2 começa a gerar recompensas boas ele passa a ser recomendo.
Para esse caso o UCB otimizado chega ser 15% inferior a melhor escolha contra 59% da escolha aleatória.
