Aprendizado por Reforço #5 — Programação Dinâmica
Crie um agente que aprende sozinho a navegar um ambiente.
Escrito por: Stephanie Urashima e Bernardo Coutinho.
Na edição dessa semana do Turing Talks, vamos dar continuidade à nossa série de Aprendizado por Reforço! Se você ainda não leu os textos anteriores dessa série, deixamos aqui o link para caso você tenha interesse. Caso contrário, vamos direto ao assunto!
Nessa publicação, abordaremos o conceito de Programação Dinâmica, trataremos de suas aplicações no Aprendizado por Reforço e, por fim, apresentaremos como criar seu próprio agente que aprenda sozinho a navegar um ambiente.
O que é Programação Dinâmica?
A Programação Dinâmica é um método muito útil de se resolver problemas de computação, que consiste em pegar um problema complexo cuja solução é difícil de ser calculada diretamente, e dividir sua resolução em diversos subp’roblemas mais fáceis de serem resolvidos. Seu uso objetiva diminuir o custo computacional do programa, bem como simplificá-lo.
Contudo, esse método só pode ser aplicado quando nosso problema atende a dois requisitos:
- Subestrutura Ótima — Um problema atende a esse requisito quando sua solução ideal depende das soluções ideias de subproblemas mais simples.
- Superposição de Subproblemas — Um problema segue essa propriedade se sua resolução requer a re-examinação dos mesmos subproblemas diversas vezes. A solução desses subproblemas podem (e devem) ser guardadas para uso futuro.
Esse método é chamado dinâmico pois esses requisitos pressupõem que o problema possui um aspecto sequencial/temporal, já que a solução de cada subproblema depende de um outro anterior.
Mas como aplicamos a Programação Dinâmica em um problema?
Exemplo de Programação Dinâmica
Vamos supor que nosso problema é calcular o n-ésimo número da Sequência de Fibonacci. Essa sequência é caracterizada da seguinte forma: seus dois primeiros valores são iguais a 1, e cada número seguinte é obtido calculando a soma dos dois anteriores. Logo, o início da sequência seria o seguinte:
1 1 2 3 5 8 13 21
Uma maneira bem simples de resolver esse problema é utilizando uma abordagem recursiva: cada vez que quisermos encontrar o n-ésimo termo da sequência, nós chamamos a mesma função para descobrir os dois anteriores para depois somá-los, da seguinte forma:
Entretanto, essa é uma abordagem pouco eficaz, já que você está chamando a função várias vezes para um mesmo número da sequência. Por exemplo, quando calculamos o Fibonacci(5), nós chamamos as funções Fibonacci(4) e Fibonacci(3). Mas dentro do Fibonacci(4), estamos novamente chamando o Fibonacci(3), mesmo já tendo calculado ele.
Dessa forma, o que podemos fazer é aplicar a Programação Dinâmica na Sequência de Fibonacci, já que é um problema que atende à Subestrutura Ótima, um termo depende de outros termos menores, e atende à Superposição de Problemas, um termo é usado diversas vezes para calcular os termos seguintes.
Assim, podemos guardar os termos da sequência em um vetor f, sem precisar calculá-los várias vezes, como no código a seguir:
Programação Dinâmica em Aprendizado por Reforço
Quando buscamos resolver um problema de Aprendizado por Reforço, nós estamos tentando calcular a Função Valor e a Política ótimas para o nosso ambiente. E, como vimos no último post, calcular a Função Valor envolve resolver a Equação de Esperança de Bellman:
Só que as Equações de Bellman atendem os requisitos da programação dinâmica, uma vez que o valor ótimo V(s) de um estado supõe que o valor dos estados seguintes V(s’) seja ótimo (Subestrutura Ótima), e cada vez que calculamos um V(s), nós precisamos calcular os valores de todos os estados seguintes (Superposição de Subproblemas).
Dessa forma, nós aplicamos Programação Dinâmica nas Equações de Bellman e guardamos todos os valores em uma tabela V[s], que atualizaremos ao longo do tempo até descobrir o valor ótimo de cada estado!
Policy Evaluation e Policy Improvement
A partir de Bellman derivam-se as seguintes formulas de atualização da função valor a partir de uma politica:
E com isso definimos 2 ações possíveis:
- Iterative Policy Evaluation: O ato de encontrar a Função Valor (V) de uma política já existente. Uma forma de encontrá-la é aplicar a equação de Bellman.
- Policy Improvement: É o processo de criação de uma nova política que procura com base na função valor de uma política passada maximizar os ganhos imediatos, ou seja, a nova política é uma política greedy em relação a antiga política, garantindo assim que a política nova sempre será melhor ou igual a antiga.
Atenção: Só é possível garantir a existência e a unicidade da função valor caso o processo tenha um fim (seja episódico) ou o gamma seja menor que 1 (constante que define a importância das recompensas do futuro, ou seja, mesmo que o processo seja infinito o conjunto de ações futuras relevantes são finitas).
Com essas duas ações é possível encontrar a politica ótima no processo chamado de Generalized Policy Iteration.
Generalized Policy Iteration
Generalized Policy Iteration (GPI) é o termo dado à ideia geral de intercalar processos de Policy Evaluation com processos de Policy Improvement (a ordem e a quantidade de cada um pode variar).
Uma parte dos métodos de Aprendizado por Reforço podem ser classificados como GPIs, isto é, têm politicas e funções de valor identificáveis, com uma politica sempre sendo atualizada de acordo com a função valor enquanto esta é atualizada para uma nova politica. Um esquema simples seria o seguinte:
A seguir, vamos explicar alguns exemplos específicos de GPI: Policy Iteration e Value Iteration. Para deixar as aplicações mais ilustrativas iremos fazer elas para resolver o ambiente Frozen Lake, do Gym:
Nesse ambiente, o nosso agente deve percorrer um lago congelado com vários buracos até chegar em um objetivo. Se ele chegar no espaço final, ele recebe uma recompensa de +1, mas se ele cair em um buraco, ele perde aquela rodada.
- Policy Iteration
É a forma mais simples de se aplicar os dois processos discutidos previamente, a ideia é intercalar as duas ações até a política se estabilizar. Abaixo há o código sobre o passo a passo desta técnica para o Frozen Lake:
Obs: Essa técnica sempre funcionará em um MDP finito, uma vez que como o próprio nome diz o processo tem ações finitas e estados finitos e portanto há um numero finito de políticas, possibilitando assim encontrar a política ótima em um numero finito de iterações.
- Value Iteration
Ao ler o código acima provavelmente deve ter notado que Policy Evaluation é um processo que pode, dependendo das circunstâncias, exigir muito poder computacional se feita iterativamente, uma vez que só é possível garantir a convergência da função valor no infinito.
Portanto, em Value Iteration, em vez de fazer Policy Evaluation até que a função valor estabilize, atualiza-se somente uma vez a função valor com o valor da ação de maior retorno.
Para implementar isso foi utilizado a variável valor_ação que guarda os valores de cada ação possível. E no fim a função_valor só recebe o maior valor guardado em valor_ação.
Depois de rodar o Value Iteration, nós obtemos a função de valor V para cada estado do Frozen Lake!
Obs: A função valor é zero para o estado final, pois o ambiente do Gym dá a recompensa na transição entre os estados, por isso que somente o estado anterior a chegar no objetivo tem valor 1.
Agora que obtivemos a Função Valor ótima, nosso agente conseguirá agir de forma a sempre chegar no objetivo, conforme o gif abaixo!
Todo o código que utilizamos nesse post pode ser encontrado aqui!
Conclusão
A Programação Dinâmica é uma ferramenta essencial para resolver diversos problemas computacionais, e agora você entende como esse conceito se relaciona com a área de Aprendizado por Reforço.
Talvez você tenha percebido que para utilizar essa abordagem em problemas de RL é necessário conhecer todas informações sobre o ambiente, as quais nem sempre estarão disponíveis em outras situações, são elas: dinâmica de transição entre os estados, recompensas e/ou ações. O que deixa a aplicação desse conceito limitado a pouquíssimos problemas.
Felizmente, existem alternativas aos problemas de falta de informações, as quais serão abordadas em futuros posts aqui no Turing Talks =).
