k-armed Bandit Problem

Após o entendimento inicial de como estados, ações e recompensas funcionam no Aprendizado por Reforço, o primeiro tipo de problema que podemos explorar é o k-armed Bandit Problem.

Essa categoria de problema consiste no seguinte: temos uma quantidade “K” de ações possíveis a serem tomadas em cada situação e precisamos escolher uma delas; sendo que a cada ação que tomamos, recebemos uma recompensa, lembrando que a recompensa não é fixa, ela pode variar a cada nova execução de uma mesma ação.

Escolhendo uma porta entre muitas - tomando decisão de ação

Como as pessoas aprendem o que fazer?

Para deixar mais claro, vamos trabalhar com um exemplo bem simples, um bebê chorando. Nosso objetivo é fazer com que ele pare de chorar. A recompensa será igual a 1 se o bebê parar de chorar e 0 se o bebê continuar chorando, após cada ação executada. É claro que poderíamos estabelecer outros tipos de recompensa, como 0.6 se o bebê está chorando menos do que estava chorando antes, mas para simplificar e facilitar, vamos imaginar esse cenário mais objetivo.

Podemos realizar várias ações distintas na tentativa de atingir o objetivo, que serão as “K” ações possíveis. Por exemplo, podemos: pegar no colo numa determinada posição, ou colocar o bebê de cabeça para baixo, ou, ainda, cantar uma música para ele, ou dar de mamá.

Enfim, teremos várias ações possíveis e teremos que escolher algumas delas e começar a entender se aquilo faz o bebê parar de chorar ou não. Quem tem um filho vai saber que, na realidade, não existe uma única ação que, sozinha, sempre resolverá o problema.

O que acontece é que cada vez que tomamos uma ação teremos um feedback positivo ou negativo. Então, como nós, seres humanos, aprendemos o que fazer?

Bebê sendo acalmado - conceito de tentativa e erro no aprendizado

Naturalmente, nós seguimos um modelo de aprendizado por reforço, que muitas vezes não é uma técnica rigorosa e, por isso, tomamos decisões equivocadas; acabamos fazendo uma busca gulosa e não seguimos uma diretriz muito bem estabelecida.

Mas, a partir do momento que vamos compreendendo e aprendendo por reforço, isso até pode ajudar a tomarmos decisões mais sábias ao longo da vida.

Recompensa média

Então, nesse caso prático, o que aconteceria se um pai visse o seu bebê chorando e tivesse que tomar uma dessas muitas decisões? Vamos imaginar que o bebê estava chorando e o pai decidiu pegá-lo no colo numa determinada posição, e o bebê parou de chorar. Então ele recebeu recompensa de 1.

Só que, depois, num outro momento, o bebê chorou e ele pensou: “Da última vez eu peguei no colo dessa forma ele parou de chorar, então vou tentar de novo, já que eu tive sucesso!”. Ele vai e o pega no colo da mesma forma, mas, dessa vez, o bebê continua chorando. A recompensa, nesse caso, foi 0.

Podemos imaginar, agora, que essa ação específica de pegar o bebê no colo está com uma recompensa média de 0.5, porque de duas ações, uma recebeu a recompensa 1 e a outra 0. Então, na média, a recompensa tomada para cada ação foi de 0.5.

Essa será a lógica: tomando as ações e, depois, fazendo uma média para ver quantas vezes se teve sucesso e quantas se teve fracasso. E se testássemos todas as ações – uma quantidade suficientemente grande de amostras – saberíamos exatamente qual a nossa probabilidade de sucesso para cada uma das ações.

Basta que tenhamos uma amostragem relevante de todas as ações e saberemos qual a ação que, por exemplo, nos daria 80% de chance de sucesso, ou 70%, ou 40%. Então, optamos por aquelas ações que tenham maior probabilidade de sucesso.

Buscando a melhor ação

Qual é o problema? O problema é que não dispomos de todo o tempo do mundo para ficar testando infinitas amostras de cada uma das ações. Na realidade, temos um problema que queremos resolver agora: o bebê está chorando e queremos maximizar nossa tentativa de recompensa!

Não queremos testar ações que já sabemos que não funcionam. Não estamos preocupados com o bem da estatística, de maneira que possamos realizar inúmeros testes até nos certificarmos que, de fato, num intervalo de confiança razoável, isso realmente não funcionou.

Não temos todo o tempo do mundo; o bebê vai crescer e não nos adianta ficar testando coisas que não vão levar a lugar nenhum. Então, queremos tomar as ações que nos levarão para o resultado correto o mais rápido possível.

Tempo é importante

É isso que motiva as técnicas de aprendizado por reforço: não temos um tempo infinito para testar tudo o que gostaríamos, nem recursos infinitos para testarmos tudo isso. Porque, se tivéssemos, não precisaríamos falar de aprendizado por reforço; bastaria testar tudo por força bruta e estaria resolvido.

Como poderíamos, então, usar alguma técnica de aprendizado por reforço para resolver, agora, esse problema do bebê? Uma técnica poderia ser a seguinte: iniciamos testando todas as ações duas vezes em cada; depois, vemos aquelas metades das ações que mais tiveram resultado positivo e damos mais uma rodada de duas vezes em cada.

Assim, vamos restringindo cada vez mais nossas ações daquelas que mais estão tendo um feedback positivo e terminamos naquela que teve a média mais alta. Essa é uma hipótese.

Boa sorte com os dados

Problema: tudo é uma questão probabilística. Então, uma ação que tem 80% de chance de ter sucesso e outra, 70%, não é com duas amostras que descobriremos que uma tem 80% e outra 70%.

Talvez, dê o azar que aquela que tinha 80%, saiu uma vez não e outra sim (uma amostra com sucesso e a outra fracasso) e a outra que tinha 70 ou 60%, saiu as duas vezes sucesso. Poderíamos nos iludir e achar que aquela é melhor.

Então, obviamente, se estamos trabalhando com poucas amostras, facilmente podemos acabar nos iludindo e indo para um lugar equivocado. Logo, essa pode não ser a melhor solução.

Outras opções de estratégias

Podemos estabelecer outros tipos de estratégias, executando, por exemplo, algo como: “Vamos tomar uma ação e, enquanto, a recompensa for superior a 0.7, vamos continuar com ela.

Se, por acaso, a recompensa média cair para menos de 0.7 migramos para outra ação. E assim vamos avançando.” Por exemplo, pegamos o bebê e, com uma ação específica, tivemos recompensa de 1; aí vamos e tomamos aquela ação específica novamente, mas agora com recompensa de 0. A nossa média passou a ser 0.5. Como está inferior a 0.7 vamos para a próxima ação e, assim, vamos avançando.

Na sequência, podemos encontrar uma ação com média de 0.75, que, devido ao acaso, na primeira ação teve recompensa de 1, depois 1 novamente e, aí, na terceira ação, tivemos a recompensa de 0, levando a média para 0.66, sendo assim rejeitada. Mas, se na terceira hipótese a recompensa recebida fosse 1 e, só no quarto evento 0, a média ficaria em 0.75 e continuaríamos com ela.

Porém, dessa forma, podemos estacionar nessa ação para sempre caso sua probabilidade real seja 0.75, que está acima dos 0.7 que definimos. Isso pode acontecer.

Podemos convergir para essa ação logo no começo, ganhando muito tempo. Ótimo! Mas, e se outra ação for melhor? Pode existir uma ação com probabilidade de 90%, e estaríamos presos na ação com probabilidade de 75%.

Assim, fica evidente que a solução apresentada pode encontrar uma boa ação de maneira rápida, porém com grande probabilidade de não estar entre as melhores ações. Uma alternativa para este problema é utilizar Exploration e Exploitation em conjunto, conforme abordamos neste artigo.

Continue aprendendo

Este e muitos outros assuntos estão disponíveis em nosso curso Aprendizado por Reforço, Algoritmos Genéticos, NLP e GANs, um curso totalmente focado no aprendizado do aluno, com aulas teóricas e práticas, sempre priorizando a didática, mesmo nos assuntos mais complexos.

Confira também:

cursos