Aprendizado por Reforço #1— Introdução
Bem-vindos a mais uma edição do Turing Talks! Nessa semana daremos início a nossa série de aprendizado por reforço, uma técnica de Machine Learning um tanto quanto diferente das abordadas nos posts anteriores. Nesta publicação trataremos de conceitos básicos e daremos uma visão geral sobre o tópico. Então, caso você já tenha alguma familiaridade com o assunto, recomendamos que acompanhe os próximos posts.
Introdução
A ideia básica é que um agente (explicaremos melhor este conceito a seguir) procura cumprir uma determinada tarefa, inicialmente com um abordagem de tentativa e erro. Posteriormente, os resultados de cada tentativa, independente de seu sucesso, são utilizados para treinar o agente por meio de um sistema de recompensa/punição e determinar se as ações tomadas são válidas ou não. Daí a ideia de aprendizado por reforço. O agente aprende tanto com os erros quanto com os acertos, e no final é esperado que ele execute a tarefa com maestria.
Suponha agora que você nunca tenha jogado Pong, o famoso jogo de Atari. Você irá jogá-lo pela primeira vez, mas ninguém te passou as regras e as únicas informações sabidas sobre o funcionamento do jogo é que é possível mover a barra direita para cima ou para baixo e que a tela “Game Over” é o pior resultado possível. O jogo se inicia e, reparando na bola vindo em sua direção, você decide tomar a seguinte abordagem: desviar toda vez que a bola chegar perto de você. O jogo segue, até que o placar atinge 11:0 e a tela “Game Over” é exibida. Para próxima partida, com base em sua experiência anterior, você resolve mover a barra na direção da bola toda vez que ela se aproxima. Com essa nova estratégia você conseguiu vencer o jogo e evitar a tela de “Game Over”.
Esse exemplo, apesar de um pouco absurdo na perspectiva de um modelo de Reinforcement Learning, pois a evolução do agente geralmente requer muito mais do que apenas um episódio (nesse caso, partida jogada) para aprender a tarefa desejada, ilustra como funciona a lógica do aprendizado por reforço.
Qual a diferença em relação a outros métodos de Machine Learning?
- Aprendizado supervisionado: É necessário um dataset de treino, no qual é sabido os valores corretos de saída para as entradas correspondentes. A partir dele, é treinado o algoritmo que aprende a predizer resultados, com certo grau de acurácia, previamente desconhecidos.
- Aprendizado não supervisionado: o algoritmo procura separar os dados em grupos com características similares. Não há dataset para treino, ou seja, não há informação prévia sobre em qual grupo pertence uma determinada entrada.
Comparando com os anteriores, Reinforcement Learning se assemelha com o primeiro no sentido de aprender com as experiências anteriores e com o segundo no sentido de aprender de uma forma não supervisionada, porém essas experiências geralmente são simuladas, como veremos a seguir, e o aprendizado se dá tanto com os acertos quanto com os erros.
Conceitos importantes
Antes de nos aprofundarmos no assunto é importante entender alguns conceitos-chave:
- Agente: Entidade, podendo ser tanto um software quanto a sua combinação com hardware, que tomará decisões no ambiente, interagindo com ele tomando determinadas ações e recebendo as recompensas correspondentes. Essa é a entidade que aprende no Reinforcement Learning.
- Ambiente: É a materialização (ou simulação) do problema a ser resolvido. Podendo ser real ou virtual, este será o espaço no qual o agente realizará suas ações.
- Estado (s): É como o sistema, agente e ambiente, se encontra em um determinado instante. Sempre que o agente realiza uma ação, o ambiente fornece um novo estado e uma recompensa correspondente.
- Política (π): Estratégia aplicada pelo agente para decidir a próxima ação com base no estado atual. A política é sempre atualizada para se atingir um comportamento ideal.
- Recompensa (r): Norteia as ações do agente, sendo a política ideal determinada a partir dela. Se a ação tomada pelo agente em um determinado estado for desejada, a recompensa é positiva, caso contrário, ela é negativa ou nula.
Markov Decision Process (MDP)
A lógica do aprendizado por reforço é fácil de entender e visualizar pois se assemelha bastante com a forma como nós aprendemos. O desafio, então, é traduzir essa lógica para uma forma que a máquina possa executá-la. Para isso, é utilizado um modelo matemático conhecido como Markov Decision Process.
O processo se dá da seguinte maneira: no instante inicial (t), o agente seleciona uma ação, muda para um novo estado, recebe uma recompensa e então o ciclo é reiniciado para o próximo instante (t+1).
Probabilidade de transição
Para entender esse comportamento de forma probabilística, iremos trabalhar com a probabilidade de uma transição de estado. Essa probabilidade será função do estado e ação imediatamente anteriores, não importando todo o resto.
Imagine um indivíduo hipotético que só pense em três coisas: dormir, correr ou tomar sorvete. Caso ele esteja correndo, há 60% de chance dele continuar, 30% de chance dele ir tomar sorvete ou 10% de chance dele ir dormir. Para cada um dos estados que esse indivíduo consegue almejar e atingir, existem as chances correspondentes de migração para outro pertencente a esse grupo. Essa é uma ilustração das probabilidades de transição.
Formalmente, definimos a probabilidade de transição para o estado s’, com recompensa r por tomar a ação a, como:
Retorno (G)
O retorno é um conceito importante pois ele representa o sucesso do agente. Ele é definido como a soma das recompensas futuras (repare que o que acompanha o primeiro termo é t+1 e não t), sendo o objetivo do agente maximizá-lo. É equacionado como segue:
Mas e no caso de uma tarefa que não possui um final bem definido? Por exemplo, o jogo Flappy Bird, caso o jogador jogue de maneira perfeita (situação esperada de um agente bem treinado), o jogo segue indefinidamente. Nesse caso, o valor do retorno tenderá para o infinito, o que não é muito conveniente pois precisamos que ele convirja para um valor fixo.
Para contornar esse fato utilizamos o retorno com desconto (discounted return). É definido um fator de desconto γ, entre 0 e 1, que vai determinar a importância dada as recompensas mais futuras. Matematicamente, escrevemos:
Quanto menor o γ, mais relevante são as recompensas mais imediatas.
Política (π)
A política é a função que mapeia um dado estado em probabilidades de se selecionar cada ação possível nele. A política é atualizada até atingir uma configuração ótima (quando o agente executa sua função corretamente).
Então, se um agente segue uma política π em um determinado momento t, então π(a|s) é a probabilidade da ação a ser executada caso o estado correspondente seja s.
Função state-value
Definida em função do estado, determina quão bom ele é caso o agente siga uma política π pelo resto do processo. O resultado dessa função é o retorno médio seguindo essas condições. É equacionado como segue:
Função state-action
Definida em função do estado e da ação, determina quão bom é para o agente tomar esta ação específica, nesse estado, caso ele siga a política π pelo resto do processo. O resultado dessa função é o retorno médio seguindo essas condições. Equacionando:
Repare que para as duas funções acima, como as ações tomadas pelo agente são influenciadas pela política, elas também são definidas em relação a essa política.
Política ótima
Quando o agente executa sua função da forma esperada é dito que a política ótima foi atingida. Isso ocorre quando para todo estado possível a função state-value atinge seu valor máximo. Em outras palavras:
Atrelado a política ótima há também a Q-function ótima, que é quando a função state-action atinge seu valor máximo para todo estado e ação possíveis. Expressando formalmente:
Equação de Bellman
Esse tópico é um tanto quanto complexo e será melhor elucidado em um Turing Talks futuro totalmente dedicado a ele. Por hora, iremos aceitar o seguinte fato: uma propriedade fundamental da Q-function ótima é que ela deve satisfazer a seguinte equação:
conhecida como equação de Bellman, onde s’ e a’ representam o estado e a ação no instante t+1, respectivamente. Ela é útil pois, uma vez determinada a Q-function ótima, podemos determinar a política ótima porque, com q∗, para qualquer estado s, o algoritmo de reinforcement learning consegue encontrar a ação a que maximiza q∗(s, a).
Q-learning
E como a gente aplica tudo isso pra poder chegar no nosso modelo esperado? Há vários algoritmos para fazer isso(SARSA, Deep Q-network, Deep Deterministic Policy Gradient etc), mas vamos nos ater a explicar como funciona o Q-learning.
O objetivo do Q-learning é gerar a política que maximize o total de recompensa recebida depois de todos os estados sucessivos. O algoritmo atualizará iterativamente os valores de q para cada par estado/ação (s, a) usando a equação de Bellman até que o valor da função convirja para q∗. Para entender melhor, vejamos no exemplo.
Exemplo prático: novo Jogo da Cobrinha
Suponha o seguinte jogo: há 9 posições possíveis, sendo que em cada uma pode haver maçãs ou armadilhas. O jogador é a cobrinha que pode se mover para cima, para baixo, direita ou esquerda. O objetivo é coletar o maior número de maçãs com no máximo 5 movimentos. Caso a cobrinha passe por uma armadilha, o jogador é derrotado.
A cobrinha será nosso agente e o tabuleiro será o ambiente. Vamos então montar nossa estrutura de recompensas para treinar o agente:
- 5 maçãs recompensam 10 pontos
- 3 maçãs recompensam 6 pontos
- 2 maçãs recompensam 4 pontos
- Armadilha recompensa -10 pontos e recebe derrota
- Casa vazia recompensa -1 ponto
De início, o agente sabe apenas para quais direções pode se mover, porém, não tem noção alguma de como esse sistema de pontuação funciona e todo o tabuleiro é uma grande incógnita.
Para saber mais sobre o jogo, a cobrinha deve explorar o tabuleiro. Sendo assim, o valor de q para cada par (s, a) é inicializado com 0 e após cada partida esses valores são atualizados.
Podemos montar uma tabela com todas as ações possíveis(movimento da cobrinha) em cada estado(casas do tabuleiro) para armazenar os valores de q.
Após cada partida, os valores de q na tabela se aproximam cada vez mais do valor ideal, possibilitando que o agente os use de referência para tomar as decisões adequadas e vencer o jogo.
Exploração x Aplicação
Se a política determina que o agente deve tomar as ações que maximizem o retorno, como a cobrinha irá tomar uma decisão na primeira partida se o valor inicial da função state-action é o mesmo para todo par (s, a)?
Inicialmente o agente deve tomar ações aleatórias, sem buscar aumentar o retorno, para melhor entender o ambiente e ajustar os valores de q. Esse processo é conhecido como exploração (exploration).
Com base nos conhecimentos adquiridos, a cobrinha passa a tomar decisões mais lógicas para cumprir seu objetivo (vencer o jogo). Essa abordagem fica conhecida como aplicação (note que aqui fizemos uma tradução livre do conceito que é visto nas literaturas em inglês, exploitation, para ficar de mais fácil entendimento para o leitor).
De início, o comportamento predominante é o de exploração e posteriormente, passa a ser o de aplicação. Essa mudança gradual é importante pois se o agente apenas explorar, ele continuará a agir de maneira desmotivada, no sentido de nunca tentar cumprir a tarefa proposta. Se ele apenas aplicar, antes de ter explorado por completo o ambiente, ele poderá cair numa política pseudo-ótima.
Imagine a seguinte situação: Antes de explorar todo tabuleiro a cobrinha encontra primeiro o par de maçãs. Para encontrá-las foram necessários 2 movimentos. Os outros 3 movimentos restantes não são suficientes para atingir outras maçãs e claramente esta não é a situação que a cobrinha mais comeu. Porém, como o tabuleiro não foi totalmente explorado, o agente acredita estar seguindo um política ótima, quando na verdade não está. Daí a importância tanto da exploração quanto da aplicação.
Estratégia Epsilon greedy
Para conseguir esses pesos diferenciados para exploração/aplicação utilizamos um fator de exploração ϵ iniciado em 1. Esse fator representa a probabilidade de o agente tomar uma ação que fuja da política, ou seja, uma exploração. Com o passar do episódios, o fator decai e o agente toma uma abordagem mais “gananciosa” (greedy), buscando aplicar cada vez mais o que foi aprendido anteriormente.
Tá bom, mas isso daí só serve pra joguinho?
No decorrer do post nos restringimos em demonstrar o funcionamento do Reinforcement Learning apenas com sua utilidade em treinar agentes para jogos. Mas não se deixe enganar em achar que essa é a sua única aplicação (ufa!). Ela foi exaustivamente usada pois é a mais tangível para a maioria dos leitores. Vamos ver a seguir algumas outras.
Robótica
Robôs que aprendem sozinhos a realizarem tarefas complexas já fazem parte de algumas fábricas pelo mundo, como a Fanuc, fabricante japonesa de robôs.
Preços dinâmicos
Ajustes de preços de acordo com a oferta e demanda podem fazer uso de técnicas como Q-learning, sendo utilizada durante as interações com os clientes.
Tratamento de cânceres
O tratamento de regime dinâmico (DTR) é tópico de várias pesquisas médicas da atualidade. Algoritmos de RL ajudam a processar dados clínicos para se chegar em um estratégia de tratamento, usando-se indicadores recolhidos de pacientes.
Mercado financeiro
A Pit.ai é pioneira em utilizar as técnicas de reinforcement learning para avaliar estratégias de investimentos, e tem se mostrado uma ferramenta bastante robusta.
Personalização de sugestões no e-Commerce
Reconhecer o perfil de cada cliente e sugerir preços e ofertas que terão mais chances de gerarem uma venda bem-sucedida.
Conclusão
É importante que tenha ficado claro o seguinte: a partir do mapeamento de cada estado do ambiente, por meio do que é aprendido com as experiências anteriores, tanto favoráveis quanto desfavoráveis, é possível atingir uma política ótima que permitirá que o agente execute a tarefa proposta. Os episódios iniciais são majoritariamente para exploração enquanto os finais são focados em aplicação.
Construímos aqui a fundação para que você possa acompanhar sem grandes dificuldades as próximas publicações dessa série. Caso não tenha entendido as minúcias da matemática, não se preocupe, o mais importante é entender a ideia geral do que cada função representa.
