Aprendizado por Reforço #3 — Processo de Decisão de Markov (Parte 2)
Decisões de Markov e as equações de Bellman
Escrito por Gustavo Corrêa, William Fukushima e Fernando Matsumoto
Bem vindos a mais uma edição dos Turing Talks! Hoje damos continuidade aos posts relacionados a Reinforcement Learning.
Veremos agora como encontrar o comportamento do agente que faz ele ser melhor recompensado no ambiente em que ele foi colocado, ou seja, melhor resolve o processo de decisão de Markov.
Vale muito a pena dar uma olhada no Turing Talks próprio de decisão de Markov, apesar de não ser totalmente necessário uma vez que alguns conceitos importantes serão revisados no início do texto.
Atenção! O texto de hoje se assemelha em muito a uma aula, porém não há necessidade de se desesperar de antemão, nada aqui será demasiadamente complicado a ponto do leitor ter que fazer uma lista de exercícios. Apesar disso, talvez seja necessário ler mais de uma vez um conceito ou parar para analisar uma equação, mesmo assim vos digo que não se desesperem, é normal ao lidar com esse assunto ter que fazer uma segunda análise.
1 - INTRODUÇÃO E OBJETIVOS
Chegamos oficialmente à parte mais matemática e cheia de variáveis parecidas entre si de RL, as Equações de Bellman, nomeadas em homenagem a Richard E. Bellman, um matemático americano que introduziu o conceito de programação dinâmica, a base de aprendizado por reforço.
Programação dinâmica é uma técnica de resolução de problemas complexos, na qual dividimos o problema em simples subproblemas e para cada um deles nós computamos e guardamos o resultado, caso o mesmo subproblema apareça novamente, nós não iremos refazê-lo, mas sim usa a solução já encontrada. A solução desses subproblemas no nosso caso são as tais equações.
O objetivo de RL é a determinar a melhor política a ser adotada, isto é, a que maximize o retorno, aqui significando o total e não aquele que vocês verão como o recebido por uma única ação.
Para resolver esse problema, introduzido em programação dinâmica por Bellman ele desenvolveu as chamadas Equações de Bellman, que vocês verão em detalhes durante esse post mas são, basicamente, modos de dizer o valor dos estados e ações do agente, afim de poder comparar qual caminho seria melhor que outro.
2 - NOTAÇÕES E CONCEITOS IMPORTANTES PARA O ENTENDIMENTO
Antes de entrarmos nos pormenores das equações devemos explicar seus componentes para evitar a confusão inicial de quem não tem muito contato com as notações matemáticas envolvidas. Para mais informações e um post sensacional acesse o Turing Talks de Probabilidade para Machine learning : Fundamentos de Probabilidade para Machine Learning
2.1 Processo de decisão de Markov
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 as ações possíveis em todos os estados existentes.
Considerando que o intuito do Processo de Recompensa de Markov é o cálculo das função de valor em todos os estados, podemos analogamente dizer que o Processo de Decisão de Markov serve para encontrarmos a Função de Política ótima. Tal política é estacionária, ou seja, não muda com o tempo. Mas pode ser tanto estocástica (que segue uma distribuição probabilística específica) quanto determinística (o comportamento ótimo ser bem definido). É preferível que se mantenha um comportamento estocástico para que o algoritmo possa explorar mais e mais o ambiente em vez de se fixar a uma única estratégia.
Para encontrar a política ótima a ser seguida resolvendo o Processo de Decisão de Markov, utilizaremos as equações de Bellman.
Relacionadas ao processo de decisão de Markov há ainda as equações que determinam as funções valor melhores descritas nos tópicos abaixo.
2.2 Variáveis Aleatórias
Um valor quantitativo cujo valor depende de resultados aleatórios/desconhecidos. Como por exemplo um lançamento de dados.
O resultado de um lançamento de dados pode dar um número inteiro de 1 a 6, porém os fatores que determinam o valor dessa variável no fim são aleatórios. São esse tipo de variável as da esperança.
2.3 Esperança ou Expectativa
Esperança dentro desse contexto significa o valor esperado a ser recebido, os valores que serão obtidos estarão no entorno desse valor. Por exemplo, se jogarmos uma moeda comum duas vezes existirão 3 possibilidades, obter nenhuma cara, 1 cara ou 2 caras. Então qual seria o resultado esperado ao jogar? Bem, caso decidíssemos repetir esse experimento muitas vezes a média dos valores tenderá para 1, indicando que a esperança, o valor esperado, corresponde a 1. Não acredita em mim? Sem problemas, temos uma demonstração mais bonita mais a baixo.
Agora, a definição matemática de esperança é a soma dos produtos dos valores possíveis pela probabilidade deles serem obtidos. Isso parece bem complicado mas quando vocês pararem para pensar um pouco sobre essa definição verão que ela é simplesmente uma média.
Depois dessa definição, um exemplo simples serve muito bem para esclarecer tudo. Consideremos o mesmo lançamento de uma moeda duas vezes, esquecendo o argumento dos vários lançamentos. Qual o valor médio que deveríamos obter ? Para tal, vamos ver as probabilidades de cada caso, ter 1 cara, 2 ou nenhuma.
Por tanto, o valor esperado de caras ao se jogar uma moeda duas vezes é 1, sua esperança é 1.
Sempre que aparecer a notação ‘E’ indicando esperança pode-se ler ‘valor esperado para tal variável’, essa interpretação facilita em muito o entendimento das equações.
2.4 Políticas
Políticas são padrões de ação tomados pelo agente. Em outros termos, são funções que, quando providas do estado atual e uma ação escolhida, retornam a probabilidade de se tomar aquela ação.
Podem ser definidas matematicamente como uma distribuição de probabilidades das ações a serem tomadas para todos os estados, e é definida por:
Lê-se “probabilidade de se tomar a ação ‘a’ estando em um estado ‘S’”.
2.5 Funções Valor
Funções Valor descrevem o valor de um estado ou ação dentro de uma política específica e servem para determinar se essa política é a melhor a ser escolhida. São utilizadas pelas próprias políticas para determinar a próxima ação, tendo seus valores atualizados a cada recompensa retornada. Por exemplo, se a sua política sempre escolhe ir pro estado de maior valor ou tomar a ação de maior valor ela é chamada de política gananciosa ou ‘greedy’ e caso a escolha dessa política resulte numa recompensa negativa o valor do estado ou ação utilizado é atualizado com sua diminuição.
Elas podem ser divididas em dois tipos, funções valor de estado e de ação. O primeiro retorna o valor do estado recebendo em qual estado está e o segundo recebendo o estado e a ação.
A função de estado-valor ótima (V*) é a maior função estado-valor que se pode obter em um estado considerando todas as políticas. Define a recompensa máxima que se pode extrair do sistema a partir do estado ‘s’.
A função de ação-valor ótima (Q*) é a maior função ação-valor que se pode obter em um estado considerando todas as políticas. Define a recompensa máxima que se pode obter a partir de um estado ‘s’ tomando uma ação ‘a’.
3 - DEDUÇÃO (Equações de Esperança de Bellman)
Podemos deduzir as Equações de Esperança de Bellman a partir das de valor e esperança já apresentadas previamente. Modificando levemente as funções valor:
Nessa nova forma a função de estado utiliza o conceito de esperança como somatório como apresentado na explicação de esperança. Já a função de ação muda de forma que exige uma breve explicação sobre seu significado.
Como ressaltado na imagem o ‘R’ representa a recompensa fornecida por aquela ação e o somatório é a esperança dos estados possíveis, o valor esperado do próximo estado.
Multiplicando a esperança do próximo estado há o fator de desconto representado pela letra grega gama (γ), ele serve, em simples termos, para determinar o quanto valorizamos os resultados futuros, seu valor pode variar entre 0 e 1. Se o agente usa gama igual a 0 é por que só valoriza as recompensas imediatas sem considerar as direções futuras e se usar 1 é por que dá total valor ao estado futuro.
Agora, finalmente, juntando essas duas equações obtemos as Equações de Esperança de Bellman:
Sem pressa nesse momento, pode pegar uns segundos para substituir uma equação na outra e chegar nas equações.
4 - OPTIMALIDADE
4.1 Condições Ótimas
Lembrando que o objetivo de RL é achar a política ótima (representada pelo símbolo “*”), o comportamento do agente no qual ele maximiza seus ganhos, podemos reescrever as funções valor nessas condições como:
4.2 Equações de Optimalidade de Bellman
A política que sempre toma a melhor ação possível é em simples termos um agente que conhece as melhores decisões a se tomar e só toma elas, dispensando as outras um vez que já sabe que seu resultado não é tão satisfatório. Isso se traduz nas equações como a probabilidade de tomar a decisão ótima sendo igual a 1 e a probabilidade de tomar qualquer outra é 0. Considerando isso as equações se reduzem a:
5 - DIAGRAMAS DE BACKUP
Não bastando as prévias deduções veremos também como percorrer esse caminho de uma forma mais visual, tanto para os leitores que tem mais facilidade quando há visualização quanto para quem já conhece o assunto ter uma abordagem diferente da usual. Faremos isso por meio de diagramas de backup.
Diagramas de backup são representação gráficas de algoritmos com estados, transições, recompensas etc. Eles servem inclusive para representar Processos de Decisão de Markov (MDP) e facilitar seu entendimento e dedução das Equações de Bellman.
Como pode ver pelo diagrama as vezes uma ação pode levar a diversos estados dependendo da probabilidade desses.
EXEMPLO
Consideremos o caso de um robô que coleta lixo que possui 2 estados:
- Bateria Alta
- Bateria Baixa
E 3 ações:
- Coletar Lixo
- Recarregar
- Não Fazer Nada
A consequência de não fazer nada é ter -1 de recompensa, ao coletar lixo sua recompensa é maior, porém gasta bateria. Caso sua bateria já esteja baixa existe a possibilidade dele ficar sem bateria, o que levaria a uma recompensa de -3 e ser recarregado manualmente.
Isso pode ser modelado num diagrama de backup da seguinte forma:
Se a política do robô for π(s,a) então a probabilidade de chegar no nó A é P(A) mostrado abaixo e analogamente P(B) e P(C) são:
A recompensa da ação procurar é +3, dessa forma as trajetórias (sequências de ações e estados que passam por A) tem valor V(A) da figura abaixo e analogamente V(B) e V(C) são:
E a partir dessas equações é possível escrever o V(W), o valor de W. Portanto, dado um estado inicial W é possível calcular as trajetórias possíveis a partir desse. O valor de W é então a média ponderada dos valores calculados com os pesos sendo as probabilidades das trajetórias.
5.1 Interpretação da Equação de Esperança
A ideia aqui contemplada é que as Equações de Bellman relacionam o valor de um estado com o valor de estados adjacentes. Analisemos o diagrama abaixo.
Para calcular o valor de s devemos passar por todas as trajetórias a partir de s. Para isso, devemos passar por todos os valores de a e s’ possíveis. O valor de uma dessas trajetórias é r + γV(s’) e a sua probabilidade é π(a|s)P(a,ss’). Portanto,
Considerando que:
E substituindo na equação anterior a ela obtemos a Equação de Bellman de Esperança para V(s):
Similarmente, para Q(s,a), temos o seguinte diagrama
Observe que todas as trajetórias têm inicialmente uma recompensa média dada por R abaixo. Logo, a equação obtida passando por todas as trajetórias (todas as combinações de s’ e a’) é:
E rearranjando os termos obtemos a equação abaixo dela, a Equação de Bellman de Esperança para Q(s,a).
5.2 Equações de Optimalidade
Até agora, vimos equações que lidam com o valor de uma política arbitrária π. No entanto, em geral, estamos interessados em uma política particular, a política ótima, essa que toma sempre as melhores ações, ou seja, as ações que maximizam Q(s,a). Associados a essa política, temos as funções de valor ótimas:
Podemos obter as equações de Bellman para V ótimo e Q ótimo por meio de uma pequena modificação nos diagramas utilizamos acima. Para V ótimo, temos:
Os arcos indicam que estamos tomando a melhor ação, ou seja, que a política é ótima. Assim sendo, a equação resultante é quase a mesma que a de V(s), mas tomamos a melhor ação ao invés de tomar a média sobre todas as ações:
Para Q(s,a) ótimo, o diagrama fica:
A recompensa obtida inicialmente (com média R abaixo) continua igual. No entanto, a partir dos estados s’, precisamos escolher a melhor ação a’ ao invés de tomar a média sobre a’ pertencente a A. Logo:
Essa é a Equação de Optimalidade de Bellman.
6 - Conclusão e o que esperar do futuro
Chegamos ao fim de mais um Turing Talks. Parabéns por chegar até aqui! Nós sabemos que esse conteúdo é bem denso, principalmente para quem está no seu terceiro post de RL, não tenha vergonha de voltar aqui as vezes para dar uma revisada.
Para resolução de problemas aqui vistos em escala maior vocês verão conteúdos como value iteration, policy iteration e Q-learning, tudo isso sem suar uma vez que vocês já passaram pela pior parte que é entender todo esse matematiquês.
