Jack, o pirata apostador (ou O que é Reinforcement Learning? O que é o Algoritmo Multi Armed Bandit? O que é ε-Greedy?)
Aqui, com esta simples história de piratas, pretendo compartilhar um pouco sobre Inteligência Artificial. Qual é a idéia do Reinforcement Learning, como ele resolve o problema clássico Multi Armed Bandit, e o que é o ε-Greedy. Aqui daremos uma pincelada nesses conceitos, uma amostra do que essa ferramenta pode fazer, e um pouco de como usá-la. Não falaremos da matemática complexa por trás do problema, que é o que faz a mágica acontecer.
Jack é um pirata.
Oh, sim, ele é um pirata.
E como um bom pirata ele ama navegar por mares desconhecidos, beber muito rum e apostar.
Sim, Jack é um pirata apostador.
Mas Jack não é um pirata comum.
Ele vem do pacífico, viveu no vale do silício. E ele tem um papagaio robô chamado AI.
Jack é um pirata esperto. Enquanto ele bebe, o papagaio joga. E AI sempre vence!!!
Bebendo com outros piratas, Jack descobriu que o cassino tem um problema. Os caça níqueis (ou One Armed Bandits) são muito velhos. E por causa disso, estão desbalanceados. Alguns favorecem o cassino, mas outros favorecem o apostador!
Jack já estava bêbado e visualizava/sonhava com os caça-níqueis…
Sonhou com os 3 caça-níqueis…
Se ele ganhar, os caça-níqueis devolvem em dobro as moedas apostadas. Haviam 3 caça níqueis, representados por 3 cores:
Verde — Nesse ele tinha 70% de chance de ganhar.
Amarelo — Nesse ele tinha 50% de chance de ganhar.
Vermelho — Nesse ele tinha 10% de chance de ganhar.
Mas qual seria qual? Qual é o verde, qual o amarelo e qual o vermelho?
Jack teve um sonho agressivo: Colocar todo o dinheiro no mesmo caça-níqueis. Isso mesmo, como um verdadeiro pirata, apostando tudo! Tudo ou Nada!
Vamos lembrar aqui um pouco de matemática…
Jack quer colocar $1000 em um dos caça-níqueis.
Se ele escolher o vermelho, aposta $1000 e ganha $1000 * 10% * 2=$200
Se escolher o amarelo, aposta $1000 e ganha $1000 * 50% *2 = $1000
Se escolher o verde, aposta $1000 e ganha $1000 * 70% * 2 = $1400
Jack não sabe nada sobre os caça-níqueis. Ele vai simplesmente rodar a garrafa, e pra onde apontar ele vai apostar. Lembrando um pouquinho de probabilidade, como são 3 caça-níqueis ele tem 1/3 de chance de cair em cada um.
Agora eu vou citar um conceito de aposta (vai, economia) e vou deixar um link abaixo pra quem quiser se aprofundar. Existe um conceito chamado retorno ajustado ao risco. No caso da aposta aí, Jack, o risco para cada uma das opções é 1/3. Então pra saber quando de retorno é esperado, ponderando esse retorno pelo risco, é só multiplicar resultado esperado pelo risco.
Assim, como mostra a figura abaixo, o retorno esperado ponderando pelo risco nesse “chute” do Jack é $866,67. E esse monte de contas deixou o Jack com uma baita dor de cabeça.
(Para mais informações sobre Expected Return on Risk: https://www.investopedia.com/terms/e/expectedreturn.asp)
E com essa dor de cabeça, ele teve um outro sonho:
Nesse ele se livrou de toda a matemática e resolveu distribuir o dinheiro entre as 3 máquinas, 1/3 pra cada uma.
Outro pesadelo, menos dor de cabeça mas… continua sendo um pesadelo. Nesse Jack ganha quase a mesma coisa do anterior, $866 (matematicamente era pra ser o mesmo valor, só dá diferente pq considerei aqui arredondamentos). E como $866 é menor que $1000, Jack perde de novo.
E eis que Jack acorda e grita:
PAPAGAIO AI! PEGUE MEU DINHEIRO E VENÇA!!!
E o papagaio diz:
Reinforment Learning, Reinforment Learning!
Jack diz: Reinforcement o que? Papagaio doido, você tá falando do que? Condicionamento? Psicologia? Skinner? Mas que m. o Skinner tem a ver com apostas?
Nesse momento os olhos do pirata Jack marearam, e ele, com muita dor, lembrou de sua infância, do treino do pequeno Jack para se tornar um pirata…
…Aprendendo como lutar com uma espada…
…O objetivo era fazer um movimento perfeito e acertar a cabeça do adversário…
…Quando dava certo, ele recebia uma recompensa (chocolate com rum)…
… Quando dava errado, ele recebia uma punição (10 flexões)… … E ele lembrou que seu mestre falava algo sobre uma teoria psicológica de aprendizado e recompensa, de um tal de Skinner que testou isso com uns ratinhos… e agora o ratinho era ele.
(Para mais informações sobre o experimento de Skinner: https://en.wikipedia.org/wiki/Operant_conditioning_chamber)
Mas quando Jack estava a ponto de cair no choro com essa lembrança, o Papagaio AI gritou:
REINFORCEMENT LEARNING! AI! MACHINE LEARNING!
O papagaio explicou que a ideia é parecida com o pesadelo, porém diferente.
Você tem um objetivo, como aprender a lutar ou aprender qual é o caça-níqueis que te trás mais lucro e apostar nele.
Vamos pensar no caça-níqueis.
Eu, apostando o seu dinheiro, sou o que chamam em Reinforcement Learning de agente (Agent). Vou tomar uma ação (Action), que é colocar seu dinheiro em alguma máquina caça-níqueis. Vou começar escolhendo aleatoriamente.
O ambiente (enviroment) é o conjunto de caça-níqueis, e o resultado da minha aposta (action) vai ser interpretado, e de acordo com ele, vou receber uma recompensa (reward). No caso do exemplo, recebo se ganhar. Se acontecer isso, o sistema reforçou em mim o aprendizado, me disse que o que estou fazendo está certo e devo continuar assim.Nesse caso, vamos utilizar uma técnica chamada Multi Armed Bandit, que foi inspirada em problemas semelhantes a estes, com caça-níqueis (One Armed Bandits).
Assim, o Papagaio gritou:
REINFORCEMENT LEARNING! MULTI ARMED BANDIT!
LEARN TO WIN (Aprenda para ganhar)! EXPLORE (explore) THAN EXPLOIT (replique, reproduza) !
Jack não entendeu muito bem, mas disse:
Vá lá e faça sua mágica, Papagaio AI. Eu vou aprender vendo você jogar.
(For more info about Multi Armed Bandit: https://en.wikipedia.org/wiki/Multi-armed_bandit)
E o Papagaio AI fez isso!
Na primeira “sessão”, ele apostou $60, distribuindo o dinheiro de maneira aleatória, $20 em cada máquina. E ganhou $52.
Essa aposta aleatória de maneira a descobrir qual máquina é a melhor é chamada Exploration, então na sessão 1 ele colocou todas as suas fichas em Exploration.
Agora, com os resultados da primeira sessão, o papagaio já tem uma ideia de qual máquina deu mais dinheiro, qual deve ser a verde. Assim, ele vai adotar outra estratégia. Vai continuar com parte do dinheiro em Exploration (apostando aleatoriamente) mas vai colocar parte do dinheiro na que ele acha que é a melhor, na que foi indicada como a melhor a partir dos resultados que ele tem até agora (e isso é chamado de Exploitation). Assim, ele vai apostar $300, sendo 50% em Exploration e 50% em Exploitation.
Nesse cenário, ele apostou $300 e ganhou $270. Com esses resultados, ele confirmou que a que ele achou que era a verde, a última de baixo, realmente era e deu os melhores resultados. Então para a próxima sessão, a última, ele vai apostar todo o dinheiro que sobrou, e colocar 85% dele em Exploitation, e só 15% em Exploration.
(Essa estratégia de trocar os percentuais de Exploitation E Exploration, de acordo com os resultados, é chamada E-Greedy. Mais informações podem ser obtidas nesse tutorial:https://www.youtube.com/watch?v=uAB9WOQCSxw)
Nessa última tentativa, o Papagaio AI apostou $640 e ganhou $806.
Pegando o total das 3 sessões, o Papagaio AI apostou $1000 e ganhou $1166.
Assim, o que aprendemos dessa história de piratas amiguinhos?
1 — Não aposte enquanto você está bêbado! Melhor deixar um papagaio fazer isso por você!
2 — Se seu Papagaio usar Inteligência Artificial, melhor ainda!
3 — Reinforcement Learning funciona! Esse problema clássico, Multi Armed Bandit, pode ser resolvido com a técnica descrita acima e utilizando a estratégia ε-Greedy. Assim como outros algoritmos de inteligência artificial, ele foi inspirado na forma como humanos trabalham e aprendem, especialmente em cenários de incerteza, como aquele onde, a princípio, não se sabia qual era a máquina caça-níqueis certa.
Assim, se você tem problemas onde não se sabe a resposta a princípio, como o dos caça-níqueis, deixe o algoritmo resolver pra você!
Muito obrigado pela leitura!
Abaixo um link para outro exemplo fantástico de MAB, sobre como o Netflix utiliza essa técnica para recomendação:
Contextual Multi Armed Bandit Application on Recomendation by Netflix:
https://pt.slideshare.net/JayaKawale/a-multiarmed-bandit-framework-for-recommendations-at-netflix
