Reinforcement learning: primeiros passos
Quando falamos de aprendizado de máquina, comumente nos referimos aos aprendizados supervisionado e não supervisionado. Será que existe outro paradigma? A resposta é sim!
O aprendizado por reforço começou há décadas como duas vertentes independentes: problema do controle ótimo e psicologia de aprendizado animal. No final da década de 1980, as duas vertentes foram relacionadas com base no conceito de métodos de diferença temporal, o que deu origem ao reinforcement learning (RL) moderno (Sutton, R.S. & Barto, A.G. Reinforcement Learning: An Introduction. 2.ed. Cambridge, MA: MIT Press, 2018).
Neste artigo, teremos uma intuição inicial sobre como o aprendizado por reforço difere das outras abordagens e mergulharemos direto em exemplos práticos utilizando Python para entender conceitos essenciais sobre esse paradigma.
Mas qual é a diferença entre aprendizado supervisionado, não supervisionado e por reforço?
Vamos começar considerando o aprendizado supervisionado: um dos problemas mais exemplificados é a detecção de imagens. Para criar um sistema capaz de classificar imagens de gatos ou cachorros, precisamos de:
- exemplos, nesse caso imagens contendo gatos e cachorros (abaixo);
- saber qual é a resposta correta (ground truth ou label);
- features, que podem ser aprendidas automaticamente, a depender do modelo (exemplo: redes neurais convolucionais);
- função de perda;
- algoritmo de aprendizado.
Se considerarmos uma rede neural CNN para a tarefa, em essência, o aprendizado consistirá em ajustar os parâmetros da rede para que as predições se aproximem do label real, minimizando assim a função de perda.
No caso do aprendizado não supervisionado, temos elementos similares, exceto pela necessidade de ter um label ou valor contendo a resposta correta. Por exemplo, na figura abaixo um algoritmo de aprendizado pode consistir em otimizar alguma métrica de distância entre as observações, agrupando os elementos por similaridade, ou em criar clusters que ajudem a entender padrões não explícitos nessas observações.
Já pensou em como um bebê aprende a falar, ou como aprende que o fogo queima? Será que ele recebe uma base de dados de seus pais contendo vários exemplos? Em diversas atividades, humanos e animais aprendem simplesmente com base na interação e na exploração do mundo, de forma incremental. Como essa forma de aprendizado pode ser traduzida numa abordagem computacional?
Podemos pensar numa abstração em que há duas partes: um agente e um ambiente. O agente não possui, a priori, todas as informações do ambiente, mas interage com ele e é capaz de refinar suas ações com base nas informações recebidas pelo ambiente de forma incremental:
Nesse contexto, o que a máquina aprende afinal de contas? Quais ações o AGENTE deve realizar em cada situação para que possa maximizar a recompensa recebida do AMBIENTE ao longo do tempo?
Vamos entender na prática como funciona?
O problema clássico: k-armed bandits
Esse é o problema mais básico quando se fala de aprendizado por reforço. Com ele, adotamos uma série de simplificações, mas já é possível identificar conceitos-chave nesse tipo de aplicação:
- imagine que temos uma espécie de jackpot, em que o agente pode escolher entre k alavancas para puxar. Cada alavanca irá fornecer uma recompensa em dinheiro;
- cada alavanca tem uma recompensa média predefinida; no entanto, cada vez que o agente aciona uma delas, um fator aleatório é somado ou subtraído da recompensa original. Esse fator segue uma distribuição normal com média zero e desvio-padrão predefinido;
- o agente tem n “fichas” para acionar as alavancas. O objetivo é ganhar a maior recompensa possível utilizando essas fichas;
- o agente não conhece nenhuma informação do sistema (ambiente) a priori. Se conhecesse o valor das alavancas, a ação a ser realizada seria trivial.
Um exemplo da distribuição de recompensas para cada alavanca pode ser ilustrado por este gráfico, em que a parte mais larga de cada violino representa o valor aproximado de sua mediana:
import numpy as np
import pandas as pd
import gym
import plotly.express as px
from tqdm import tqdm
import matplotlib.pyplot as plt
from IPython.display import display, Image%matplotlib inlinemeans = np.random.randint(0,10, 10)samples = {}
for v in range(len(means)):
samples[v] = means[v] + np.random.randn(1000)
df = pd.DataFrame(samples)print(means)
fig = px.violin(data_frame =df)
fig.update_layout({
'title': 'Distribuição recompensas',
'yaxis_title': 'Retorno $',
'xaxis_title': 'Alavanca'
})
Vamos definir um ambiente que simule o processo descrito acima. Na comunidade de pesquisa do reinforcement learning, é comum utilizar ambientes padronizados para que se possa fazer comparações entre diferentes algoritmos. Uma biblioteca que fornece vários ambientes é o OpenAI Gym. Nesse caso, para entender melhor como funciona, vamos utilizar um ambiente personalizado construído com base nessa biblioteca:
class MultiarmedBanditsEnv(gym.Env):
"""
Environment for multiarmed bandits
Fonte: https://github.com/magni84/gym_bandits/blob/master/gym_bandits/envs/bandits_env.py
"""
metadata = {'render.modes': ['human']}def __init__(self, nr_arms=10):
self.action_space = gym.spaces.Discrete(nr_arms)
self.observation_space = gym.spaces.Discrete(1)
self.state = 0
self.reset()def step(self, action):
assert self.action_space.contains(action)
random_factor = np.random.normal(scale=1)
reward = self.values[action] + random_factorreturn self.state, reward, False, {self.optimal}def reset(self):
self.values = np.random.randint(0,10,self.action_space.n)
self.optimal = np.argmax(self.values)
return self.statedef render(self, mode='human', close=False):
print("You are playing a %d-armed bandit" % self.action_space.n)
Aqui, o mais importante é entender a função step, que simula “uma puxada de alavanca”. Ela irá retornar a média predefinida pela alavanca, adicionada ou subtraída de um valor amostrado por uma distribuição normal com média zero e desvio-padrão 1. Vamos simular o acionamento da alavanca 0:
env = MultiarmedBanditsEnv(nr_arms=n_alavancas)
env.step(0)(0, 1.1651351085025232, False, {7})
A resposta do ambiente é uma tupla contendo o estado do ambiente (não aplicável aqui; mais tarde falaremos sobre), a recompensa obtida, se o estado é terminal e um dicionário com informações opcionais. Esse problema é considerado contínuo; portanto, nunca há um estado terminal. Um exemplo não contínuo, ou episódico, seria uma partida de xadrez, que pode ser quebrada naturalmente em sequências finitas, visto que ao fim do jogo as peças retornam ao seu estado inicial.
Agora que temos nosso ambiente, vamos fazer um experimento. Suponha que tenhamos 1.000 fichas para acionar qualquer alavanca de forma aleatória. Qual seria o desempenho do agente?
n_steps = 1000
n_alavancas = 10res = [] #holder para historizar resultadosprint(f"Jogando com {n_steps} fichas")for n in range(n_steps):
action = np.random.randint(n_alavancas)
state, reward, terminal, info = env.step(action)
resultado = {
'ficha': n,
'action': action,
'recompensa': reward,
'melhor_acao': env.optimal,
'recompensa_maxima': np.max(env.values)
}
res.append(resultado)
res = pd.DataFrame(res).set_index('ficha')
aproveitamento = np.round(100*res['recompensa'].sum()/res['recompensa_maxima'].sum(),1)
print(f'Feito! Aproveitamento: {aproveitamento}%')Jogando com 1000 fichas
Feito! Aproveitamento: 62.6%fig = px.line(res[['recompensa', 'recompensa_maxima']])
fig.update_layout({
'title': 'Recompensa x Passo',
'yaxis_title': 'Recompensa [$]',
'xaxis_title': 'Ficha jogada',
})
Como esperado, um agente que aciona alavancas de forma aleatória irá, eventualmente, acionar a alavanca de maior recompensa (obs.: aqui estamos considerando a recompensa máxima sem o fator aleatório; por isso, em alguns casos, a recompensa obtida [azul] é maior que a máxima).
No entanto, a aleatoriedade do sistema traz uma resposta muito variável. Poderíamos repetir esse mesmo experimento várias vezes para obter melhores estimativas:
n_runs = 200 #quantidade de vezes a repetir o experimento
n_steps = 1000
n_alavancas = 10print(f"Jogando {n_runs} vezes com {n_steps} fichas:")all_rewards = []
all_max_reward = []for run in tqdm(range(n_runs)):
run_reward = []
run_best_reward = []
for n in range(n_steps):action = np.random.randint(n_alavancas)
state, reward, terminal, info = env.step(action)run_reward.append(reward)
run_best_reward.append(np.max(env.values))
all_rewards.append(run_reward)
all_max_reward.append(run_best_reward)
avg_reward = np.mean(all_rewards, axis=0)
avg_best_reward = np.mean(all_max_reward,axis=0)res = pd.DataFrame(zip(avg_reward, avg_best_reward), columns=['recompensa_media', 'recompensa_maxima'])
aproveitamento = np.round(100*res['recompensa_media'].sum()/res['recompensa_maxima'].sum(),1)
print(f'Feito! Aproveitamento: {aproveitamento}%')Feito! Aproveitamento: 61.1%fig = px.line(res[['recompensa_media', 'recompensa_maxima']])
fig.update_layout({
'title': 'Recompensa x Passo',
'yaxis_title': 'Recompensa [$]',
'xaxis_title': 'Ficha jogada',
})
Repetindo o mesmo experimento várias vezes, a variância no resultado cai, e a recompensa tende a se aproximar da média dos retornos (nesse caso, 5.5). Nessa baseline, tivemos um aproveitamento de cerca de 61.1% (soma da recompensa obtida dividida pela máxima possível). Será que podemos fazer melhor?
Observando o gráfico acima, fica claro que o agente que definimos não está melhorando nem aprendendo ao longo do tempo. Ele não aproveita a informação recebida do ambiente a cada interação para que suas ações sejam melhores. Ainda assim, já é possível identificar alguns componentes essenciais do aprendizado por reforço:
- Ambiente: entidade que provê uma recompensa, tem um conjunto de ações e estados.
- Recompensa: sinal escalar que indica a qualidade da ação. Deve ser definida de acordo com o objetivo do problema.
- Agente: entidade que interage com o ambiente com base em uma política definida.
- Política: função que mapeia estados em ações, ou Pi(s) = P(a|s).
Esse contexto é mais simplificado, e ainda não estamos falando de diferentes estados. Mas como podemos pensar numa política melhor que a aleatória?
Uma alternativa seria aproveitar a informação de recompensa recebida a cada interação para estimar qual seria a média da recompensa de cada alavanca. Para isso, poderíamos inicializar nosso agente com um vetor contendo as estimativas de recompensa esperada para cada alavanca e refiná-las a cada interação. Para não dependermos de armazenar todas as recompensas obtidas ao longo das interações, podemos utilizar a seguinte regra de atualização de média:
Dessa forma, para cada alavanca armazenamos somente as médias conhecidas até o passo k-1 e atualizamos essa média todas as vezes que há um novo acionamento da mesma alavanca.
Vamos construir um agente que leve em conta essa atualização de média, e sua política será acionar sempre a alavanca que tiver a maior estimativa de retorno.
def argmax(q_values):
"""
Função auxiliar: recebe uma lista de valores e retorna o índice do maior deles. Se houver empate, decide de forma aleatória entre os índices de maior valor.
""" top_value = float("-inf")
ties = []
for i in range(len(q_values)):
# if a value in q_values is greater than the highest value update top and reset ties to zero
# if a value is equal to top value add the index to ties
# return a random selection from ties.
# YOUR CODE HERE
if q_values[i] > top_value:
top_value = q_values[i]
ties = [i]
elif q_values[i] == top_value:
ties.append(i)
return np.random.choice(ties)
Na implementação do agente, agora utilizaremos um padrão comum que, assim como o ambiente, também terá a função step, responsável por receber a resposta do ambiente e realizar a próxima ação:
class GreedyAgent():
def __init__(self, n_actions, **kwargs):
self.action_space = n_actions
self.q_values = np.zeros(self.action_space) #armazena a recompensa media
self.arm_count = np.zeros(self.action_space) #armazena a contagem de vezes que cada alavanca foi acionada
self.last_action=None
def update_q_values(self, reward):
if not self.last_action:
return
qn = self.q_values[self.last_action]
n = self.arm_count[self.last_action]
alpha = 1/n
self.q_values[self.last_action] = qn + alpha*(reward - qn)
def step(self, reward):
#atualizar a estimativa das recompensas com base na ultima ação
self.update_q_values(reward)
self.current_action = argmax(self.q_values)
self.arm_count[self.current_action]+=1
self.last_action = self.current_action
return self.current_action
def reset(self):
self.q_values = np.zeros(self.action_space)
self.arm_count = np.zeros(self.action_space)
self.last_action=NoneE agora, com nosso greedy agent, vamos repetir o último experimento. Repare que, no bloco abaixo, a única diferença é a linha em que se define uma ação, que não é mais aleatória:
n_runs = 200
n_steps = 1000
n_alavancas = 10print(f"Jogando {n_runs} vezes com {n_steps} fichas:")all_rewards = []
all_max_reward = []for run in tqdm(range(n_runs)):
agent = GreedyAgent(n_actions=n_alavancas)
run_reward = []
run_best_reward = []
reward = 0
for n in range(n_steps):
#aqui entra nosso agente
action = agent.step(reward)
state, reward, terminal, info = env.step(action)run_reward.append(reward)
run_best_reward.append(np.max(env.values))
all_rewards.append(run_reward)
all_max_reward.append(run_best_reward)
avg_reward = np.mean(all_rewards, axis=0)
avg_best_reward = np.mean(all_max_reward,axis=0)res = pd.DataFrame(zip(avg_reward, avg_best_reward), columns=['recompensa_media', 'recompensa_maxima'])
aproveitamento = np.round(100*res['recompensa_media'].sum()/res['recompensa_maxima'].sum(),1)
print(f'Feito! Aproveitamento: {aproveitamento}%')
Feito! Aproveitamento: 64.7%
Observando o aproveitamento (64.4%), temos uma pequena melhora em relação ao agente aleatório (61.1%). Perceba o início do gráfico acima: a recompensa média começou com um valor ligeiramente mais baixo, que logo subiu e se manteve estável pelo resto das interações entre o agente e o ambiente; ou seja, ele só aprendeu um pouco no começo. Mas o que aconteceu?
Se verificarmos na definição da classe greedy agent, o vetor de estimativas das médias foi inicializado com todos os valores iguais a zero; a primeira ação escolhida pelo agente se sobressaiu em relação às outras; e, pela sua política, o agente escolheu sempre a ação com maior estimativa de recompensa. Dessa forma, a partir desse ponto, ele sempre escolherá a primeira ação realizada.
Veja como exemplo o que aconteceu no último dos 200 experimentos:
Aqui, o agente escolheu primeiramente a alavanca 5, que trazia recompensa média de 7. A partir da primeira ação, ele não testou mais nenhuma alavanca, porque essa era a que ele estimava ter a maior recompensa, mesmo que houvesse a alavanca 7 trazendo uma recompensa de 9.
Como resolver isso?
O método de atualização de média trouxe uma boa estimativa para a ação escolhida. Uma forma de aproveitá-lo para estimar corretamente as outras ações é adotar um comportamento exploratório na política do agente. Dessa forma, o agente até então greedy (ganancioso em relação à recompensa) agora será transformado num agente epsilon-greedy (ε-greedy), cuja política é:
- realizar a ação com maior estimativa de recompensa com (1-ε) de probabilidade;
- realizar uma ação exploratória com probabilidade ε.
Em sua implementação, a única diferença está na função step, em que é definida a ação. Assim, se ε for maior que zero, garantimos que o agente eventualmente irá explorar outras ações que possam trazer maior ou menor recompensa que a atualmente preferida por ele.
class EpsilonGreedyAgent():
def __init__(self, n_actions, epsilon=0.05):
self.action_space = n_actions
self.q_values = np.zeros(self.action_space) #armazena a recompensa media
self.arm_count = np.zeros(self.action_space) #armazena a contagem de vezes que cada alavanca foi acionada
self.epsilon = epsilon
self.last_action = None
def update_q_values(self, reward):
qn = self.q_values[self.last_action]
n = self.arm_count[self.last_action]
alpha = 1/n
self.q_values[self.last_action] = qn + alpha*(reward - qn)
def step(self, reward):
#atualizar a estimativa das recompensas com base na ultima ação
if self.last_action:
self.update_q_values(reward)
if np.random.random() < self.epsilon:
self.current_action = np.random.randint(self.action_space)
else:
self.current_action = argmax(self.q_values)
self.arm_count[self.current_action]+=1
self.last_action = self.current_action
return self.current_action
def reset(self):
self.q_values = np.zeros(self.action_space)
self.arm_count = np.zeros(self.action_space)
self.last_action=NoneVamos rodar o mesmo experimento com nosso novo agente. Por padrão, ele está configurado para explorar com probabilidade de 5%:
n_runs = 200
n_steps = 1000
n_alavancas = 10print(f"Jogando {n_runs} vezes com {n_steps} fichas:")all_rewards = []
all_max_reward = []for run in tqdm(range(n_runs)):
agent = EpsilonGreedyAgent(n_actions=n_alavancas)
run_reward = []
run_best_reward = []
reward = 0
for n in range(n_steps):
#aqui entra nosso agente
action = agent.step(reward)
state, reward, terminal, info = env.step(action)run_reward.append(reward)
run_best_reward.append(np.max(env.values))
all_rewards.append(run_reward)
all_max_reward.append(run_best_reward)
avg_reward = np.mean(all_rewards, axis=0)
avg_best_reward = np.mean(all_max_reward,axis=0)res = pd.DataFrame(zip(avg_reward, avg_best_reward), columns=['recompensa_media', 'recompensa_maxima'])
aproveitamento = np.round(100*res['recompensa_media'].sum()/res['recompensa_maxima'].sum(),1)
print(f'Feito! Aproveitamento: {aproveitamento}%')
Feito! Aproveitamento: 93.6%
Esse agente foi capaz de aproveitar muito mais o conhecimento adquirido do ambiente, com aproveitamento de 93.6% da recompensa. Perceba também que há um aumento incremental conforme o agente interage.
Amostrando do último dos 200 experimentos, percebemos que o comportamento exploratório do agente ajudou a mapear de forma muito mais eficiente as recompensas:
No entanto, por que escolhemos um agente com ε=5%? Não poderia ser maior ou menor? De forma semelhante ao que acontece nos aprendizados supervisionado e não supervisionado, essa variável pode ser entendida como um hiperparâmetro. Diferentes ambientes demandarão diferentes níveis de exploração.
Para entender o que acontece em nosso exemplo, vamos novamente fazer um experimento com vários agentes:
#vamos iniciar implantando um agente aleatório no mesmo padrão dos demais
class RandomAgent():
def __init__(self, n_actions, **kwargs):
self.action_space = n_actions
def step(self, reward):
action = np.random.randint(self.action_space)
return action
def reset(self):
passRepetindo nosso experimento-padrão, considerando agora vários níveis de exploração nos agentes ε-greedy:
n_runs = 200
n_steps = 1000
n_alavancas = 10agentes = {
'Aleatorio': RandomAgent(n_actions = n_alavancas),
'Greedy': GreedyAgent(n_actions = n_alavancas),
'Epsilon_0.01': EpsilonGreedyAgent(n_actions = n_alavancas, epsilon=0.01),
'Epsilon_0.05': EpsilonGreedyAgent(n_actions = n_alavancas, epsilon=0.1),
'Epsilon_0.1': EpsilonGreedyAgent(n_actions = n_alavancas, epsilon=0.1),
'Epsilon_0.3': EpsilonGreedyAgent(n_actions = n_alavancas, epsilon=0.3),
'Epsilon_0.5': EpsilonGreedyAgent(n_actions = n_alavancas, epsilon=0.5),
}all_agents_res = []for name, agent in agentes.items():
print(f"Agente: {name} Jogando {n_runs} vezes com {n_steps} fichas:")all_rewards = []
all_max_reward = []for run in tqdm(range(n_runs)):
run_reward = []
run_best_reward = []
reward = 0
for n in range(n_steps):#aqui entra nosso agente
action = agent.step(reward)
state, reward, terminal, info = env.step(action)run_reward.append(reward)
run_best_reward.append(np.max(env.values))all_rewards.append(run_reward)
all_max_reward.append(run_best_reward)
agent.reset()avg_reward = np.mean(all_rewards, axis=0)
avg_best_reward = np.mean(all_max_reward,axis=0)res = pd.DataFrame(zip(avg_reward, avg_best_reward), columns=['recompensa_media', 'recompensa_maxima'])
aproveitamento = np.round(100*res['recompensa_media'].sum()/res['recompensa_maxima'].sum(),1)
print(f'Feito! Aproveitamento agente {name}: {aproveitamento}%')
res['agente'] = name
all_agents_res.append(res)
all_res = pd.concat(all_agents_res)
O aproveitamento obtido por cada agente foi:
- aleatório: 61.1%;
- greedy: 66.1%;
- ε-greedy 1%: 84.3%;
- ε-greedy 5%: 94.1%;
- ε-greedy 10%: 94%;
- ε-greedy 30%: 87,7%;
- ε-greedy 50%: 80.3%.
Pelo gráfico acima, percebemos que, a partir de determinado ponto, o comportamento exploratório não contribui para o desempenho do agente (nesse caso ε>10%). Isso acontece porque o agente já tem uma estimativa robusta sobre a recompensa esperada de cada alavanca, e mesmo assim continua explorando, perdendo a oportunidade de aproveitar esse conhecimento.
Essa comparação nos dá a intuição de um conceito essencial em RL: exploration vs exploitation:
- se o agente focar somente a recompensa imediata (exploitation, utilizando o conhecimento que ele tem até então), ele não descobrirá melhores ações porque no instante atual elas parecem ser piores do que a ação que ele já conhece;
- se o agente explorar novas ações (exploration), estará sacrificando obter uma recompensa imediata conhecida em função de uma melhor recompensa futura.
Nesse problema clássico chamado k-armed bandits, percebe-se que as ações realizadas não alteram o ambiente ou a distribuição de recompensas obtidas. Será que isso é o que acontece na maior parte dos problemas práticos? Como seria se houvesse alteração?
A base da abordagem para tomadas de decisão de forma sequencial é o conceito de Markov decision processes (MDP). Esse será o assunto da continuação desta publicação. ;)
O exemplo de k-armed bandits utilizado aqui está disponível em meu Github.
