Sua Primeira IA: o Problema dos k-Armed Bandits
Um exemplo simples de Aprendizado por Reforço
Para o texto de hoje você não vai precisar de conhecimento prévio na área de Aprendizado por Reforço, só de uma familiaridade com Python.
Olá entusiastas de Inteligência Artificial! Sejam bem-vindos a mais um Turing Talks! Há algum tempo aqui no Medium fizemos uma série de posts introduzindo o conceito de Aprendizado por Reforço e inclusive já fizemos um te mostrando como usar essa incrível técnica para ensinar uma IA a jogar Super Mario Bros! Mas hoje decidimos voltar um pouco atrás, falaremos sobre O Problema do k-Armed Bandits (em português, o Problema das Roletas de K Alavancas), um problema que pode — de maneira intuitiva — esclarecer alguns conceitos básicos de Aprendizado Por Reforço e que você poderá implementar!
Resumo do Problema
Imagine que um robô vá a um cassino, e nele se depare com uma roleta com 10 alavancas. Cada alavanca tem uma certa chance de devolver uma certa quantidade de dinheiro, na média algumas alavancas devolvem mais dinheiro do que outras. O objetivo desse robô é aprender, a partir de conceitos chave do Aprendizado por Reforço, a puxar a alavanca que mais lhe devolve dinheiro.
Generalizando o Problema
Podemos generalizar esse problema para qualquer situação em que um agente é apresentado com um número k de escolhas, e após cada escolha ele recebe uma recompensa dentro de uma distribuição probabilística estacionária.
O que significa isso? Basicamente, dizemos que uma distribuição probabilística é como as probabilidades estão distribuídas ao longo de algum valor aleatório. Por exemplo, em uma escola de ensino médio, encontraremos majoritariamente alunos distribuídos entre os 15 até 18 anos, com muito menos alunos distribuídos nas outras idades. Como exemplificado neste gráfico fictício:
Assim, dizemos que a probabilidade de escolhermos um aluno dentro desse intervalo (15–18) é maior. E que se escolhermos um aluno aleatoriamente, é esperado que o aluno tenha por volta dessa idade.
E estacionária basicamente significa que durante toda a simulação do episódio, essa distribuição probabilística não muda.
Agora que você sabe o que este termo significa, imagine que cada alavanca possui uma dessas distribuições para suas recompensas, a imagem a seguir ilustra as distribuições para um problema com 10 alavancas:
No nosso problema de k-Armed Bandits dizemos que para cada k ações há uma recompensa média esperada; esse valor esperado geralmente é chamado de valor da ação. Ou seja, definimos o valor de uma ação arbitrária a, denotado de q*(a), como uma recompensa em um tempo t (Rt) dado que a ação em t (At) foi a como:
(Esse 𝔼 significa o valor esperado, é como se fosse a “recompensa média” — a recompensa com maior probabilidade de acontecer dado a.)
Se nosso agente soubesse todos os valores esperados, o problema seria facilmente resolvido: ele simplesmente escolheria a ação com o maior valor. O problema é justamente que ele não sabe esses valores. E para descobri-los ele necessitará realizar o que chamamos de exploração e explotação.
Na exploração ele tentará conhecer melhor os valores de cada ação, para que na explotação ele já conheça uma variedade de valores diferentes e assim poderá escolher os melhores. Uma analogia com o mundo real seria o menu de um restaurante: imagine que você pediu um prato lá e acabou gostando deste prato, você poderia sempre pedi-lo quando fosse nesse restaurante e acabaria feliz, porém, se não se arriscar a pedir nenhum outro prato nunca saberá se pode haver um prato do qual você acabe gostando mais!
Estimando o Valor Q
Normalmente em Aprendizado por Reforço nós usamos letras maiúsculas para representar algo aleatório ou um valor estimado, por isso agora estamos utilizando Q maiúsculo, pois ele é uma estimativa.
Como nosso agente não conhece os Valores q reais cabe a ele tentar estima-los de alguma maneira. Como estamos buscando um valor esperado — ou seja, a recompensa média — basta calcularmos a média das recompensas recebidas por nosso agente naquela ação:
Porém, como na computação seria custoso executar uma somatória toda vez que gostaríamos de atualizar Q podemos fazer algumas manipulações algébricas e cair na seguinte equação:
Que é a equação que utilizaremos em nosso algoritmos para estimar Q! Lembre-se que n, nesse caso, vai ser o número de vezes que aquela ação ocorreu. Então teremos um n e um Q para cada ação.
Como vamos aplicar a exploração e explotação?
Para a explotação vamos utilizar uma função bastante comum em Aprendizado por Reforço, a função argmax.
O que ela faz? Ela irá receber a lista de valores Q de cada ação e devolverá o índice do maior valor, dessa maneira escolhendo a ação de maior valor estimado. Se houverem empates, por definição, ela escolhe um dos valores empatados aleatoriamente.
Ué, mas se ela devolve a ação de maior valor, não era melhor só usar ela? O problema de só utilizar a função argmax é o de que se o agente não conhece os valores, ele poderá facilmente “viciar” em uma ação que na verdade não é a melhor ação, caindo assim em uma solução subótima.
Para evitar esse problema vamos utilizar um método de exploração também bem comum no Aprendizado por Reforço, um algoritmo epsilon-greedy. (em português epsilon-guloso)
O que ele faz? Dado um número epsilon menor que 1 e geralmente pequeno, o algoritmo escolherá um número real entre 0 e 1 aleatoriamente. Se esse número for menor que esse epsilon pequeno, o agente realizará uma ação aleatória. Caso contrário o agente escolherá uma ação baseada na função argmax. Em outras palavras, o algoritmo tem uma chance epsilon pequena de fazer uma ação aleatória. Assim, incentivando o agente a testar ações novas aleatoriamente, mas ainda explotando a ação que estimou ser melhor na maior parte do tempo.
Implementando um Algoritmo que resolve o problema!
Ok, teoria é legal e tudo mais, mas agora vamos por a mão na massa!
No código a baixo utilizaremos alguns conceitos de orientação à objetos, mas se você não está familiarizado com este conceito, não se preocupe! Ele não é muito relevante para o resultado, só facilita a leitura do código.
Importando o numpy e criando os k-Armed Bandits:
Esse
__init__, é uma função que é chamada junta com o objeto quando ele é criado, ela serve para passar os primeiros atributos dele. Nesse caso são as k -distribuições de probabilidade das recompensas dos Bandits.
Aqui definimos o que é geralmente chamado em Aprendizado por Reforço de Enviroment (o Ambiente em português), ele é o “local” onde o agente interage com e toma suas ações.
Definindo a função Argmax:
Definindo o Agente:
Para nosso agente utilizaremos os seguintes atributos :
- epsilon: a chance epsilon pequena do agente escolher uma ação aleatória
- k_arms: o número k de braços que o agente possuí
- n_arms: lista de tamanho k que guarda o número n de vezes que um braço foi ativado
- Q_values: lista de tamanho k que guarda o valor estimado Q da recompensa de cada braço
- last_action: última ação (braço escolhido) feita pelo agente
Os parâmetros epsilon e k_arms serão definidos pelo usuário, enquanto n_arms e Q_values são inicializados como listas de zeros. last_action é inicializado com um ação aleatória.
Treinando o agente e plotando a curva de aprendizado:
Agora chegamos na parte mais interessante e divertida do Aprendizado por Reforço: treinar nosso agente!
Aqui inicializaremos um roleta e um agente de 10 alavancas e 10 braços, com um epsilon de 0.1. Faremos 200 simulações com 1000 steps cada. Depois disso faremos um gráfico com as recompensas médias que demonstrará o quão bem o agente aprendeu a escolher a melhor alavanca.
A curva de aprendizado será algo parecido com:
Como podemos ver nosso agente consegue aprender razoavelmente bem qual ação lhe da uma recompensa maior! Agora, você pode experimentar outros parâmetros e ver como eles afetam o aprendizado do agente. Que tal escolher um epsilon maior, e ver se o agente aprende mais rápido? Ou escolher um epsilon menor e aumentar o número de steps em cada simulação, será que o agente consegue um resultado melhor? Deixamos esses experimentos como um exercício para você se familiarizar com o problema e o agente :D.
É legal notar também que esse não é o único tipo de algoritmo que resolve esse problema, também existem algumas variações dele como o algoritmo de Limite de Confiança Superior e o algoritmo de Softmax, ambas implementações estão em nosso repositório de Aprendizado por Reforço no Github!
Obrigado por ter lido até aqui! Esperamos que tenha gostado e contamos com sua presença no próximo Turing Talks!
Lembre-se de nos acompanhar em nossas redes sociais! No Facebook, no Linkedin, Instagram, nossas postagens anteriores no Medium e agora nosso novo servidor no Discord!
Agradecimentos especiais à Camilla Fonseca e ao Bernado Coutinho
