Explorando o k-armed Bandit Problem verificamos que podemos tomar diferentes estratégias para encontrar a melhor ação – aquela que tem a maior probabilidade de sucesso – buscando o máximo de performance no menor tempo possível.
Uma estratégia interessante para atingir esse objetivo será utilizar Exploration e Exploitation.
O que é Exploitation?
O Exploitation é uma técnica que estará sempre procurando repetir a ação que já apresentou o melhor resultado – aquela que apresentou a maior recompensa – lembrando que não sabemos qual é a ação que dá a maior recompensa média dentre todas as possíveis.
Conhecemos apenas os dados que já usamos, e estamos ignorando que possa existir outra ação ainda melhor, que levará a uma recompensa média maior.
Continuaremos escolhendo essa ação até que sua recompensa média seja superada por a de outra ação, momento em que migraremos para a outra.
O Exploitation sempre vai tentar escolher, em cada momento, a ação que está apresentando a melhor performance e, claro, não é preciso refletir muito para se chegar na conclusão de que facilmente estacionaremos em uma ação que, possivelmente, não será a melhor.
O que é Exploration?
O Exploration, por outro lado, faz a exploração. Assim, ele dará chances iguais de escolha para todas as ações, não importando sua recompensa média.
Mesmo as ações com as recompensas médias mais baixas poderão ser escolhidas. O Exploration seria a ideia de sentar e observar todo o cenário se desenrolando diante dos nossos olhos, onde todas as combinações possíveis seriam testadas, e encontraríamos a ação com melhor recompensa média em cada situação.
Esse seria o cenário ideal, se pudéssemos esperar todo o tempo necessário.
Exploration ou Exploitation?
A estratégia, então, será utilizar uma mescla, atribuindo um percentual para Exploitation e outro para Exploration.
Por exemplo, se quisermos utilizar metade de cada, isso significa que, antes de tomar uma ação, iremos escolher aleatoriamente entre Exploitation ou Exploration. Poderíamos jogar uma moeda para cima – cara ou coroa – e se sair “cara” fazemos Exploitation, se sair “coroa”, Exploration.
Se jogamos a moeda e saiu “cara”, iremos buscar a ação que apresentou o melhor resultado até o momento, e repetiremos essa ação.
Se, por acaso, a moeda der “coroa”, vamos fazer Exploration, sorteando a ação que tomaremos considerando, inclusive, aquelas que apresentam o pior desempenho.
Antes de tomar cada decisão, o agente sempre realizará um sorteio entre Exploration e Exploitation a partir de uma probabilidade definida por nós.
Lembrando que, não importa o que ele faça – se está fazendo Exploration ou Exploitation – a recompensa obtida será sempre registrada, compondo assim a recompensa média da ação. Dessa forma, estamos registrando a recompensa média de todas as ações que estamos realizando.
Obviamente, nesse cenário em que estamos fazendo 50% de cada, como metade das vezes estamos fazendo Exploitation, a distribuição não ficará uniforme: algumas ações serão mais testadas que outras. Mas, naturalmente, talvez, acabemos testando mais ações que tenham maior chance de funcionar, e é exatamente isso que queremos.
Queremos testar mais ações com maiores probabilidades de sucesso e, entre elas, definir aquela que converge mais.
Mas quanto de Exploitation e quanto de Exploration?
Aqui utilizamos o exemplo de 50%, mas um valor comum de se usar em muitos cenários para este tipo de K-armed Bandit Problem, é um Epsilon (que é o valor de Exploration), geralmente definido como a quantidade de Exploration que teremos.
Então, o Epsilon pode ser, por exemplo 0.1; ou menor ou maior, dependendo do problema. Mas, se começarmos com o Epsilon de 0.1, ou seja, 10%, isso quer dizer que faremos 10% de Exploration e 90% de Exploitation.
Portanto, antes de tomar cada ação, sorteamos a probabilidade (sempre teremos 10% de chance de fazer uma escolha randômica, mas 90% de chance de escolher a ação que está com a maior recompensa média).
Com isso, na maior parte das vezes estaremos perseguindo as ações com maiores recompensas, mas, de tempos em tempos, vamos acabar fazendo um pouco de Exploration, possibilitando então que, eventualmente, uma ação que estava sendo descartada por conta de sua baixa recompensa média, que perdemos de vista devido ao nosso foco nas melhores, possa ser testada novamente.
Assim, permitindo que outras ações também sejam testadas, repetindo esse evento muitas vezes, algumas dessas ações podem acabar se mostrando melhores. Ou seja, a partir do momento em que determinada ação está se mostrando melhor; então, começamos a migrar o nosso Exploitation para lá.
Ao utilizar Exploration estamos diminuindo a probabilidade de estagnar em uma única ação que não é efetivamente a melhor.
Como utilizar exploration e exploitation na prática?
Agora que já entendemos melhor essa questão, podemos começar a falar de simulações e utilizar alguns casos de problemas mais específicos, mostrando um acúmulo de probabilidades e ver como diferentes valores de Epsilon nos ajudam a convergir mais rápido, ou mais lentamente, para um ponto ótimo ou nos impedem de chegar no ponto ótimo.
Em nosso Curso Aprendizado por Reforço, Algoritmos Genéticos, NLP e GANs realizamos essas aplicações práticas, além de todo embasamento teórico necessário, com muito cuidado em cada explicação. Não deixe de conferir!
Confira também: