16 KiB

Raw Permalink Blame History

Introdução ao Aprendizado por Reforço e Q-Learning

Sketchnote por Tomomi Imura

O aprendizado por reforço envolve três conceitos importantes: o agente, alguns estados e um conjunto de ações por estado. Ao executar uma ação em um estado específico, o agente recebe uma recompensa. Imagine novamente o jogo de computador Super Mario. Você é o Mario, está em um nível do jogo, ao lado de um precipício. Acima de você há uma moeda. Você, sendo o Mario, em um nível do jogo, em uma posição específica... esse é o seu estado. Mover um passo para a direita (uma ação) fará com que você caia no precipício, o que lhe dará uma pontuação numérica baixa. No entanto, pressionar o botão de salto permitirá que você marque um ponto e continue vivo. Esse é um resultado positivo e deve lhe conceder uma pontuação numérica positiva.

Usando aprendizado por reforço e um simulador (o jogo), você pode aprender a jogar para maximizar a recompensa, que é permanecer vivo e marcar o máximo de pontos possível.

🎥 Clique na imagem acima para ouvir Dmitry falar sobre Aprendizado por Reforço

Quiz pré-aula

Pré-requisitos e Configuração

Nesta lição, vamos experimentar algum código em Python. Você deve ser capaz de executar o código do Jupyter Notebook desta lição, seja no seu computador ou em algum lugar na nuvem.

Você pode abrir o notebook da lição e seguir esta lição para construir.

Nota: Se você estiver abrindo este código na nuvem, também precisará buscar o arquivo rlboard.py, que é usado no código do notebook. Adicione-o ao mesmo diretório que o notebook.

Introdução

Nesta lição, vamos explorar o mundo de Pedro e o Lobo, inspirado por um conto musical de fadas de um compositor russo, Sergei Prokofiev. Usaremos Aprendizado por Reforço para permitir que Pedro explore seu ambiente, recolha maçãs saborosas e evite encontrar o lobo.

Aprendizado por Reforço (RL) é uma técnica de aprendizado que nos permite aprender um comportamento ideal de um agente em algum ambiente ao realizar muitos experimentos. Um agente nesse ambiente deve ter algum objetivo, definido por uma função de recompensa.

O ambiente

Para simplificar, vamos considerar o mundo de Pedro como um tabuleiro quadrado de tamanho largura x altura, como este:

Cada célula neste tabuleiro pode ser:

chão, onde Pedro e outras criaturas podem caminhar.
água, onde obviamente não se pode caminhar.
uma árvore ou grama, um lugar onde se pode descansar.
uma maçã, que representa algo que Pedro ficaria feliz em encontrar para se alimentar.
um lobo, que é perigoso e deve ser evitado.

Há um módulo Python separado, rlboard.py, que contém o código para trabalhar com este ambiente. Como este código não é importante para entender nossos conceitos, vamos importar o módulo e usá-lo para criar o tabuleiro de exemplo (bloco de código 1):

from rlboard import *

width, height = 8,8
m = Board(width,height)
m.randomize(seed=13)
m.plot()

Este código deve imprimir uma imagem do ambiente semelhante à acima.

Ações e política

No nosso exemplo, o objetivo de Pedro seria encontrar uma maçã, enquanto evita o lobo e outros obstáculos. Para isso, ele pode essencialmente andar por aí até encontrar uma maçã.

Portanto, em qualquer posição, ele pode escolher entre uma das seguintes ações: cima, baixo, esquerda e direita.

Definiremos essas ações como um dicionário e as mapearemos para pares de mudanças de coordenadas correspondentes. Por exemplo, mover para a direita (R) corresponderia ao par (1,0). (bloco de código 2):

actions = { "U" : (0,-1), "D" : (0,1), "L" : (-1,0), "R" : (1,0) }
action_idx = { a : i for i,a in enumerate(actions.keys()) }

Resumindo, a estratégia e o objetivo deste cenário são os seguintes:

A estratégia, do nosso agente (Pedro) é definida por uma chamada política. Uma política é uma função que retorna a ação em qualquer estado dado. No nosso caso, o estado do problema é representado pelo tabuleiro, incluindo a posição atual do jogador.
O objetivo, do aprendizado por reforço é eventualmente aprender uma boa política que nos permita resolver o problema de forma eficiente. No entanto, como base, vamos considerar a política mais simples chamada caminhada aleatória.

Caminhada aleatória

Vamos primeiro resolver nosso problema implementando uma estratégia de caminhada aleatória. Com a caminhada aleatória, escolheremos aleatoriamente a próxima ação entre as ações permitidas, até chegarmos à maçã (bloco de código 3).

Implemente a caminhada aleatória com o código abaixo:

def random_policy(m):
    return random.choice(list(actions))

def walk(m,policy,start_position=None):
    n = 0 # number of steps
    # set initial position
    if start_position:
        m.human = start_position 
    else:
        m.random_start()
    while True:
        if m.at() == Board.Cell.apple:
            return n # success!
        if m.at() in [Board.Cell.wolf, Board.Cell.water]:
            return -1 # eaten by wolf or drowned
        while True:
            a = actions[policy(m)]
            new_pos = m.move_pos(m.human,a)
            if m.is_valid(new_pos) and m.at(new_pos)!=Board.Cell.water:
                m.move(a) # do the actual move
                break
        n+=1

walk(m,random_policy)

A chamada para walk deve retornar o comprimento do caminho correspondente, que pode variar de uma execução para outra.

Execute o experimento de caminhada várias vezes (digamos, 100) e imprima as estatísticas resultantes (bloco de código 4):

def print_statistics(policy):
    s,w,n = 0,0,0
    for _ in range(100):
        z = walk(m,policy)
        if z<0:
            w+=1
        else:
            s += z
            n += 1
    print(f"Average path length = {s/n}, eaten by wolf: {w} times")

print_statistics(random_policy)

Note que o comprimento médio de um caminho é em torno de 30-40 passos, o que é bastante, dado que a distância média até a maçã mais próxima é em torno de 5-6 passos.

Você também pode ver como é o movimento de Pedro durante a caminhada aleatória:

Função de recompensa

Para tornar nossa política mais inteligente, precisamos entender quais movimentos são "melhores" que outros. Para isso, precisamos definir nosso objetivo.

O objetivo pode ser definido em termos de uma função de recompensa, que retornará algum valor de pontuação para cada estado. Quanto maior o número, melhor a função de recompensa. (bloco de código 5)

move_reward = -0.1
goal_reward = 10
end_reward = -10

def reward(m,pos=None):
    pos = pos or m.human
    if not m.is_valid(pos):
        return end_reward
    x = m.at(pos)
    if x==Board.Cell.water or x == Board.Cell.wolf:
        return end_reward
    if x==Board.Cell.apple:
        return goal_reward
    return move_reward

Uma coisa interessante sobre funções de recompensa é que, na maioria dos casos, só recebemos uma recompensa substancial no final do jogo. Isso significa que nosso algoritmo deve, de alguma forma, lembrar os "bons" passos que levam a uma recompensa positiva no final e aumentar sua importância. Da mesma forma, todos os movimentos que levam a resultados ruins devem ser desencorajados.

Q-Learning

O algoritmo que discutiremos aqui é chamado Q-Learning. Neste algoritmo, a política é definida por uma função (ou uma estrutura de dados) chamada Q-Table. Ela registra a "qualidade" de cada uma das ações em um estado dado.

É chamada de Q-Table porque muitas vezes é conveniente representá-la como uma tabela ou matriz multidimensional. Como nosso tabuleiro tem dimensões largura x altura, podemos representar a Q-Table usando um array numpy com formato largura x altura x len(actions): (bloco de código 6)

Q = np.ones((width,height,len(actions)),dtype=np.float)*1.0/len(actions)

Observe que inicializamos todos os valores da Q-Table com um valor igual, no nosso caso - 0.25. Isso corresponde à política de "caminhada aleatória", porque todos os movimentos em cada estado são igualmente bons. Podemos passar a Q-Table para a função plot para visualizar a tabela no tabuleiro: m.plot(Q).

No centro de cada célula há uma "seta" que indica a direção preferida de movimento. Como todas as direções são iguais, um ponto é exibido.

Agora precisamos executar a simulação, explorar nosso ambiente e aprender uma melhor distribuição de valores da Q-Table, o que nos permitirá encontrar o caminho para a maçã muito mais rapidamente.

Essência do Q-Learning: Equação de Bellman

Uma vez que começamos a nos mover, cada ação terá uma recompensa correspondente, ou seja, teoricamente podemos selecionar a próxima ação com base na maior recompensa imediata. No entanto, na maioria dos estados, o movimento não alcançará nosso objetivo de chegar à maçã, e assim não podemos decidir imediatamente qual direção é melhor.

Lembre-se de que não é o resultado imediato que importa, mas sim o resultado final, que obteremos no final da simulação.

Para levar em conta essa recompensa atrasada, precisamos usar os princípios de programação dinâmica, que nos permitem pensar sobre nosso problema de forma recursiva.

Suponha que estamos agora no estado s, e queremos nos mover para o próximo estado s'. Ao fazer isso, receberemos a recompensa imediata r(s,a), definida pela função de recompensa, mais alguma recompensa futura. Se supusermos que nossa Q-Table reflete corretamente a "atratividade" de cada ação, então no estado s' escolheremos uma ação a que corresponda ao valor máximo de Q(s',a'). Assim, a melhor recompensa futura possível que poderíamos obter no estado s será definida como max

Verificar a política

Como a Q-Table lista a "atratividade" de cada ação em cada estado, é bastante fácil utilizá-la para definir a navegação eficiente no nosso mundo. No caso mais simples, podemos selecionar a ação correspondente ao valor mais alto da Q-Table: (bloco de código 9)

def qpolicy_strict(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = list(actions)[np.argmax(v)]
        return a

walk(m,qpolicy_strict)

Se experimentares o código acima várias vezes, podes notar que, por vezes, ele "fica preso", e precisas de pressionar o botão STOP no notebook para o interromper. Isto acontece porque podem existir situações em que dois estados "apontam" um para o outro em termos de valor ótimo de Q-Value, caso em que o agente acaba por se mover entre esses estados indefinidamente.

🚀Desafio

Tarefa 1: Modifica a função walk para limitar o comprimento máximo do caminho a um certo número de passos (por exemplo, 100), e observa o código acima retornar este valor ocasionalmente.

Tarefa 2: Modifica a função walk para que não volte aos locais onde já esteve anteriormente. Isto evitará que o walk entre em loop, no entanto, o agente ainda pode acabar "preso" num local do qual não consegue escapar.

Navegação

Uma política de navegação melhor seria aquela que utilizámos durante o treino, que combina exploração e aproveitamento. Nesta política, selecionamos cada ação com uma certa probabilidade, proporcional aos valores na Q-Table. Esta estratégia pode ainda resultar no agente voltar a uma posição que já explorou, mas, como podes ver no código abaixo, resulta num caminho médio muito curto até ao local desejado (lembra-te que print_statistics executa a simulação 100 vezes): (bloco de código 10)

def qpolicy(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = random.choices(list(actions),weights=v)[0]
        return a

print_statistics(qpolicy)

Depois de executar este código, deverás obter um comprimento médio de caminho muito menor do que antes, na faixa de 3-6.

Investigar o processo de aprendizagem

Como mencionámos, o processo de aprendizagem é um equilíbrio entre exploração e aproveitamento do conhecimento adquirido sobre a estrutura do espaço do problema. Vimos que os resultados da aprendizagem (a capacidade de ajudar um agente a encontrar um caminho curto até ao objetivo) melhoraram, mas também é interessante observar como o comprimento médio do caminho se comporta durante o processo de aprendizagem:

Resumo das aprendizagens:

O comprimento médio do caminho aumenta. O que vemos aqui é que, inicialmente, o comprimento médio do caminho aumenta. Isto provavelmente deve-se ao facto de que, quando não sabemos nada sobre o ambiente, é mais provável ficarmos presos em estados desfavoráveis, como água ou lobos. À medida que aprendemos mais e começamos a usar esse conhecimento, conseguimos explorar o ambiente por mais tempo, mas ainda não sabemos muito bem onde estão as maçãs.
O comprimento do caminho diminui, à medida que aprendemos mais. Quando aprendemos o suficiente, torna-se mais fácil para o agente alcançar o objetivo, e o comprimento do caminho começa a diminuir. No entanto, ainda estamos abertos à exploração, por isso frequentemente desviamos do melhor caminho e exploramos novas opções, tornando o caminho mais longo do que o ideal.
O comprimento aumenta abruptamente. O que também observamos neste gráfico é que, em determinado momento, o comprimento aumentou abruptamente. Isto indica a natureza estocástica do processo, e que podemos, em algum momento, "estragar" os coeficientes da Q-Table ao sobrescrevê-los com novos valores. Isto idealmente deve ser minimizado ao diminuir a taxa de aprendizagem (por exemplo, no final do treino, ajustamos os valores da Q-Table apenas por um valor pequeno).

No geral, é importante lembrar que o sucesso e a qualidade do processo de aprendizagem dependem significativamente de parâmetros, como a taxa de aprendizagem, a diminuição da taxa de aprendizagem e o fator de desconto. Estes são frequentemente chamados de hiperparâmetros, para distingui-los dos parâmetros, que otimizamos durante o treino (por exemplo, os coeficientes da Q-Table). O processo de encontrar os melhores valores de hiperparâmetros é chamado de otimização de hiperparâmetros, e merece um tópico à parte.

Questionário pós-aula

Trabalho

Um Mundo Mais Realista

Aviso Legal:
Este documento foi traduzido utilizando o serviço de tradução automática Co-op Translator. Embora nos esforcemos para garantir a precisão, esteja ciente de que traduções automáticas podem conter erros ou imprecisões. O documento original no seu idioma nativo deve ser considerado a fonte oficial. Para informações críticas, recomenda-se uma tradução profissional realizada por humanos. Não nos responsabilizamos por quaisquer mal-entendidos ou interpretações incorretas resultantes do uso desta tradução.

16 KiB Raw Permalink Blame History