Aprendizado por Reforço #2 | Processo de Decisão de Markov — Parte 1
Processos e recompensas de Markov
Escrito por William Fukushima e Lucas Oliveira Reis
Olá seres humanos (ou o que quer que sejam). Bem vindos a mais um Turing Talks!
Neste capítulo, iniciaremos o tópico de Processo de Decisão de Markov, uma maneira simples de descrever problemas de Aprendizado por Reforço que requerem tomadas de ações com incertezas, como diagnósticos médicos, tratamentos de enfermidades, controle da movimentação de um robô, e muito mais.
Nossa jornada será realizada por meio de dois textos, nos quais iremos destrinchar o máximo possível de cada conceito, então não se preocupe porque qualquer base de probabilidade será explicada sucintamente.
Mas caso esteja bastante confuso e precise de uma base mais forte, confira nossa edição do Turing Talks em que ensinamos probabilidade para machine learning:
Para explicar o Processo de Decisão de Markov, primeiramente precisamos compreender:
- Propriedade de Markov;
- Função de transição;
- Processo de Markov;
- Ambientes Parcialmente e Completamente Observáveis;
- Tarefas Episódicas e Contínuas;
- Recompensa e Retorno;
- Função de Valor;
- Processo de Recompensa de Markov;
- Função de Política.
Após tudo isso, poderemos entender:
- O que é um Processo de Decisão de Markov (parte 1);
- Funções de Estado-Valor (parte 2);
- Funções de Valor Ótimas (parte 2);
- Equações de Bellman (parte 2).
Então mãos à obra! Tome o tempo necessário para ter uma visão clara de cada um dos conceitos pois eles dependem uns dos outros.
Antes de começar, devemos revisar os seguintes tópicos abordados em nosso post anterior:
Agente: Entidade que tomará decisões no ambiente, interagindo com ele tomando determinadas ações e recebendo as recompensas correspondentes.
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.
Propriedade de Markov
A Propriedade de Markov enuncia o seguinte:
“Dado o presente, o futuro independe do passado.”
Bem filosófico não é mesmo?
Vamos meditar um pouco sobre isso. Basicamente, um estado seguirá essa propriedade caso todos os estados anteriores a ele não influenciarem na decisão do próximo estado, apenas o estado atual. Não são todos os estados que obedecem a Propriedade de Markov, mas caso obedeçam, o problema torna-se mais fácil.
Passando essa relação ao matematiquês obtemos a seguinte expressão:
Esse bando de letras significa algo muito simples, mas primeiro precisamos explicar o que esses símbolos significam. P(A | B, C) significa “probabilidade de A ocorrer dado que B e C ocorreram”. A probabilidade de eu passar para o estado St+1 dado que eu estou no estado St (parte esquerda da equação) é igual a probabilidade de eu passar para o estado St+1 dado todos estados em que estive em meu histórico. Significando que todos os estados antes do atual não são importantes para a passagem de um estado novo.
Ainda tá difícil de entender? Segue o exemplo usado no post anterior para ver se clarifica o significado.
Se o meu estado atual é correr, não importa quantas vezes eu já dormi ou se antes eu estava tomando sorvete, a probabilidade de eu ir tomar sorvete ainda é 0.3, a de dormir é 0.1 e a de continuar correndo é de 0.6 .
Função de Transição (Matriz de Probabilidade de Transição de Estados)
Todas essas probabilidades de mudança de estado podem ser colocadas em uma matriz chamada de Matriz de Probabilidade de Transição, com seu modelo geral dado abaixo. As linhas da matriz representam o estado atual, com os seus elementos sendo as probabilidades de mudar para os respectivos estados, tendo eles que somar 1. Vale notar que estas mudanças de estado registradas pela matriz acontecem naturalmente e não são decisões do agente sendo dessa forma também parte do ambiente.
A matriz criada para o exemplo anterior, com os estados Dormir, Sorvete e Correr sendo os estados 1, 2 e 3, respectivamente, seria a seguinte:
Processo de Markov
Consiste em um espaço de estados S associado a uma função de transição P onde todos os estados seguem a propriedade de Markov. No exemplo anterior, S seriam os três estados possíveis e P a sua matriz de probabilidade de transição.
Com processos de Markov (e as variações que veremos abaixo) podemos simular nosso ambiente em um problema de aprendizado por reforço.
Ambientes Completamente e Parcialmente Observáveis
Ambientes Completamente Observáveis: são ambientes em que todas as informações estão disponíveis para o agente. Ex: jogos de informação perfeita como Xadrez ou Go.
Ambientes Parcialmente Observáveis: nem todas as informações sobre o ambiente estarão disponíveis para o agente. Exemplo: jogos de informação imperfeita como jogos de cartas.
Tarefas Episódicas e Contínuas
Tarefas episódicas: São aqueles que chegam ao fim alcançando um estado terminal. Podemos dizer que eles tem estados finitos. Exemplo: Uma partida de Go.
Tarefas contínuas: São tarefas infinitas, sem um estado terminal. Exemplo: simular o comportamento Humano…
Recompensa e Retorno
Para se definir Retorno deve-se primeiro definir Recompensa (R), um certo valor que é dado para cada estado para indicar se ele é desejável ou não, como por exemplo, correr pode ter uma recompensa positiva e tomar sorvete pode ter uma recompensa negativa.
No Aprendizado por Reforço, a métrica que devemos maximizar trata-se da soma cumulativa de todas as recompensas que o agente recebe e não apenas a recompensa imediata do estado atual. A essa soma, damos o nome de Retorno (Gt).
Podemos comparar a relação de recompensa e retorno com pontos em videogames. Dessa forma, toda vez que recebemos pontos é como se estivéssemos recebendo recompensas e nossa pontuação final seria nosso retorno.
Exemplo: Considere o seguinte Processo de Recompensa de Markov (que explicaremos do que se trata mais a frente):
Se percorrermos os estados da seguinte forma partindo de “Class 2” : “Class 2” -> ”Class 3” -> “Pass” -> “Sleep”. Teremos acumulado as recompensas gerando o seguinte retorno: Gt = -2 + -2 + 10 + 0 = 6.
Para tarefas episódicas, o retorno é fácil de ser calculado, pois será a soma de todas as recompensas obtidas pelo agente. Mas para tarefas contínuas, como a atividade não tem fim e não podemos somar até o infinito, há a necessidade da inserção de um fator de desconto (γ).
O fator de desconto é um hiperparâmetro (definido pelo programador) e consiste em um número entre 0 e 1 que define a importância das recompensas futuras em relação à atual.
Valores mais próximos ao 0 dão mais importância a recompensas imediatas enquanto os mais próximos de 1 tentarão manter a importância de recompensas futuras.
Na prática, um algoritmo com fator de desconto 0 nunca aprenderá uma vez que irá considerar apenas as recompensas imediatas e com 1 continuará somando recompensas futuras até o infinito. Portanto, um valor ótimo de um fator de desconto está entre 0.2 e 0.8.
Utilizando o fator de desconto, podemos escrever o retorno da seguinte forma:
Exemplo: Utilizando a mesma sequência do exemplo anterior com um fator de desconto de 0.5, temos: Gt = -2 + 0.5*-2 + 0.25*10 + 0.125*0 = -0.5.
Função de Valor
A função de valor basicamente determina o quão bom é estar em um estado específico, para o agente.
A função de valor V(s) é o retorno esperado iniciando no estado s e seguindo a política pelos próximos estados até encontrar um estado terminal (e o valor da recompensa deste será 0). A função (também chamada de função de estado-valor) é definida por:
(este E em probabilidade simboliza esperança)
Relembrando…
Esperança : É a média ponderada de um resultado utilizando a probabilidade de ocorrência como peso. Ex: Em uma partida de rpg, ao atacar um goblin, executamos uma rolagem de dados onde há 10% de chance de se causar 10 pontos de dano, 70% de chance de causar 5 pontos e 20% de chance de errarmos o ataque. Dessa forma, a esperança é de 0,1*10 + 0,7*5 + 0,2*0 = 4,5 de dano.
Portanto, para calcular a função valor para um estado (s), devemos calcular a média ponderada pelas probabilidades das funções de retorno partindo de s até o estado terminal onde a recompensa terá o valor de 0.
Bootstrapping (acelerando com um ponto de partida)
Como calcular a média de todos os retornos é inviável para atualizar a função de valor, podemos acelerar a programação linear (BLP), utilizamos o valor do próximo estado para estimar o valor do estado atual.
Programação linear: Em matemática, problemas de Programação Linear são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.
Será visto mais a frente, que esta estimativa é possível e converge pois conforme progredimos na Iteração de Valor, a magnitude do erro de Bellman (a diferença máxima entre dois Valores de dois estados consecutivos) diminui. Mas não é necessário se preocupar com isso por enquanto…
Processo de Recompensa de Markov (MRP)
Juntando todos os conceitos abordados até aqui, podemos definir o Processo de Recompensa de Markov, que é basicamente um Processo de Markov onde adicionamos também a função de recompensa que nos dá a próxima recompensa esperada para cada estado e o fator de desconto (S, P, R, γ).
Exemplo:
Com todas as informações armazenadas por um MRP, é possível calcular a função de valor para cada estado.
Se utilizarmos operações com matrizes para o cálculo, obtemos:
Dessa forma, podemos programar essas operações e acelerá-las utilizando bibliotecas como o numpy. Não abordaremos operações matriciais, mas é fortemente recomendado o estudo.
Certo, então sabemos como calcular o valor de todos os estados e temos todos os dados modelados, mas ainda não sabemos quais são as decisões corretas a serem tomadas e como treinamos nosso algoritmo.
Processo de Decisão de Markov
Finalmente, o Processo de Decisão de Markov trata-se de um Processo de Recompensa de Markov com as ações que podem ser tomadas (S, A, P, R, γ), onde A é o espaço de todas ações possíveis em todos os estados existentes.
Para um Processo de Decisão de Markov, além da função de valor V(s), há também o retorno esperado da tomada de uma ação, chamado de Q valor ou função de valor da ação.
Basicamente é uma função de valor, mas para uma ação. Ela determina a esperança da recompensa que uma ação tomada pode devolver. Lê-se “Retorno esperado (ou simplesmente valor) da ação ‘a’ no estado ‘s’ é igual à recompensa da ação ‘a’ no estado ‘s’ mais o valor descontado do estado seguinte”
Muito obrigado por acompanharem até aqui! A área de Aprendizado por Reforço não é tão simples de se entender, demanda a compreensão da modelagem utilizando probabilidade, algo não muito intuitivo para alguns, mas espero que tenham gostado.
Em nosso próximo texto da série Aprendizado por reforço abordaremos em mais detalhes o Processo de Decisão de Markov.
E como sempre, para ficar por dentro de Inteligência Artificial basta seguir o Grupo Turing nas redes: Medium, Facebook, Instagram e LinkedIn.
Força! E até a próxima!!
