Reinforcement learning: Markov decision processes
Na primeira parte desta publicação, estudamos o problema mais básico do aprendizado por reforço: k-armed bandits. Nele, tínhamos k alavancas, e cada uma, quando acionada, tinha uma distribuição de recompensa com uma média predeterminada, porém essa recompensa era adicionada ou subtraída de um valor amostrado de uma distribuição normal com média zero e desvio-padrão um.
Nesse tipo de sistema, as ações do agente não tinham impacto no ambiente, isto é, não o levavam a outro estado e não alteravam sua distribuição de recompensas. Na maior parte das aplicações práticas ocorre o oposto: as ações realizadas pelo agente afetam as recompensas e os estados futuros. Hoje vamos entender como abstrair essas interações em um framework chamado Markov decision processes (MDPs). Além disso, vamos entender como resolver problemas caracterizados por MDPs finitos e encontrar uma política ótima para o agente (e entender o que isso significa).
Conteúdo:
- Definição de Markov decision processes e um exemplo prático.
- Formalização do objetivo de um agente RL e equações de Bellman.
- Encontrando a política ótima para o dado exemplo com programação dinâmica.
- Resolvendo o mesmo exemplo usando Q-learning.
Markov decision processes
Markov decision processes, ou MDPs, abstraem o conceito de interação sequencial entre um agente e o ambiente. Diferentemente do k-armed bandits, aqui, a cada vez que o agente realiza uma ação, o ambiente pode transacionar para um novo estado com determinada probabilidade, e sua distribuição de recompensa para a dada ação pode mudar. O agente, por sua vez, pode utilizar as informações de estado (que pode ser representado por um vetor e informações) e recompensa (sempre escalar) para refinar sua política.
A interação pode ser representada por uma sequência:
S0, A0, R1, S1, A1, R2, A2, S2, R3...E a dinâmica de transição é dada pela equação abaixo:
Perceba que a relação dada acima condiciona a probabilidade de o sistema mudar para o estado s’ e prover uma recompensa r, dado um estado s, e que foi realizada uma ação a na etapa anterior de interação. Um MDP deve respeitar a seguinte condição:
Propriedade Markov: o estado atual deve incluir todas as informações das interações passadas entre agente e ambiente que possam fazer alguma diferença no futuro. Ou seja, a dinâmica de transição e recompensa deve depender somente do estado/das ações atuais.
Também podemos separar os MDPs em duas categorias:
- Episódicos: o sistema pode ser dividido em sequências naturais, em que, ao final delas, o seu estado retorna ao inicial. Exemplo: na partida de xadrez há um estado final definido, após o qual o jogo pode ser reiniciado.
- Contínuos: não há uma definição de estado terminal, em que, ao atingi-lo, o sistema retorna ao estado inicial. Exemplo: um agente controlando um processo industrial contínuo.
Vamos entender melhor com um exemplo prático: imagine um jogo chamado Gridworld, em que o agente (seta vermelha) precisa encontrar o caminho mais curto até a bandeira.
A definição de um MDP precisa contemplar:
- Conjunto de estados: cada quadrado do grid é um estado. Pode ser nomeado de acordo com suas coordenadas xy. Exemplo: 11, 21, 32. Nessa lógica, o estado inicial é o 54, e o objetivo é o estado 12.
- Conjunto de ações: o agente pode se movimentar para as quatro direções, e cada ação é representada por um número inteiro: {0->esquerda,
1->cima, 2->direita, 3->baixo). - Recompensa: lembre-se de que a recompensa sempre é um sinal escalar retornado pelo ambiente e deve ser cuidadosamente pensada para que possibilite que o agente atinja seu objetivo.
Aqui, se quiséssemos encontrar o caminho mais curto, como poderíamos determinar a recompensa? Vamos entender primeiramente como expressar o objetivo do agente.
Objetivo do agente e equações de Bellman:
No exemplo do Gridworld, queremos que o agente encontre o caminho mais curto até o estado final. Esse objetivo pode ser definido matematicamente como a soma das recompensas futuras até o final do episódio:
Se estivermos falando de um MDP contínuo, será necessário adicionar um fator de desconto (gamma) para que essa soma seja convergente:
Quanto menor for o fator de desconto, maior será o peso das ações mais próximas, ou seja, o agente priorizará mais o curto prazo.
Reward hypothesis: o que se espera de objetivo de um agente deve ser parametrizado de modo a maximizar um valor esperado da soma acumulada de um sinal escalar recebido do ambiente (chamado recompensa). O agente sempre aprende a maximizar sua recompensa. Dessa forma, devemos parametrizar a recompensa de forma que ele, ao maximizá-la, também resolva o objetivo proposto de sua tarefa (Sutton, R.S. & Barto, A.G. Reinforcement Learning: An Introduction. 2.ed. Cambridge, MA: MIT Press, 2018).
Trazendo esse conceito para nosso exemplo do Gridworld, podemos pensar numa forma de definir a recompensa do MDP: se o objetivo é que ele encontre o caminho mais rápido até o estado final, a recompensa do Gridworld pode ser definida como:
- -1 para qualquer transição que não seja o estado final. Se o agente estiver numa borda e tentar se mover para fora dela, ele ficará no mesmo estado e também ganhará -1 de recompensa;
- 10 quando o agente encontra o estado final e o episódio é reiniciado.
Dessa forma, qualquer algoritmo utilizado, ao buscar maximizar o objetivo (função Gt), consequentemente precisará encontrar o caminho mais curto, ou seja, que gere menos transições com recompensa -1.
Equações de Bellman: value functions e action-value functions
Considere novamente o nosso exemplo do Gridworld, agora com foco no estado inicial (54). Faz sentido pensar que se mover para a esquerda (53) ou para cima (44) tem um valor maior que se mover para baixo ou para a direita?
Essa noção de valor de um estado ou de um par estado-ação pode ser formulada matematicamente pelas equações de Bellman. Aqui vamos vê-las de forma básica e, principalmente, entender como utilizá-las na prática. Se você deseja se aprofundar mais, indico o livro de Sutton & Barto, já referenciado nas imagens até aqui e descrito no final deste artigo.
- Value function: dado um estado s, qual é o valor esperado do objetivo do agente, ou seja, qual é a esperança da soma de suas recompensas partindo desse estado quando o agente segue uma política π?
- Action-value function: qual é a soma de recompensas esperada, dado que o agente segue uma política π e parte de um estado s no qual foi realizada a ação a?
Parece complicado? Vamos calcular vπ(s) para o estado inicial de nosso MDP. Antes disso, porém, vamos definir a política do agente. Lembre-se de que a política nada mais é do que uma função que mapeia estados em ações:
Inicialmente, vamos considerar que nossa política é uniforme aleatória. Ou seja, em qualquer estado do Gridworld, o agente tem 25% de probabilidade de se mover para cada um dos quatro lados possíveis.
De volta para o cálculo, aqui podemos simplificar a equação da dinâmica do ambiente, visto que as transições são determinísticas. Exemplo: se a ação foi mover para a esquerda, sabemos com 100% de certeza o próximo estado. Assim, eliminamos o somatório interior e precisamos abrir somente o somatório exterior (sobre as ações):
vπ(s=54) =
ação mover para a esquerda: 0.25*1*(-1 + v_pi(s=53)) +
ação mover para a direita: 0.25*1*(-1 + v_pi(s=55)) +
ação mover para cima: 0.25*1*(-1 + v_pi(s=44)) +
ação mover para baixo: 0.25*1*(-1 + v_pi(s=54))
Se aplicarmos a mesma equação para todos os estados, teremos um sistema de equações, e os valores encontrados serão uma forma de avaliar quão boa é a política π. Esses valores podem ser facilmente utilizados para calcular qπ(s,a), que por sua vez pode ser utilizado para encontrar a política ótima do agente, ou seja, aquela que irá maximizar o objetivo.
No entanto, na maior parte das vezes não é possível resolver as equações de Bellman dessa forma, uma vez que a complexidade cresce conforme aumentam os estados e as ações. Os principais algoritmos de reinforcement learning foram desenvolvidos para resolver as equações de Bellman em MDPs de diferentes complexidades. Algumas alternativas para o caso tabular são:
- Programação dinâmica.
- Monte Carlo.
- Temporal difference (TD).
Encontrando uma política ótima com programação dinâmica
Como discutido, resolver as equações de Bellman em um MDP permite avaliar quão boa é a política utilizada e, a partir dessa avaliação, melhorar sua política. Vamos resolver o Gridworld utilizando um método de programação dinâmica chamado value iteration.
Primeiramente, vamos definir algumas funções para o ambiente:
#definir MDPxr = np.arange(1,6,1)
yr = np.arange(1,6,1)states = [x*10 + y for x in xr for y in yr]
actions = [0, 1, 2, 3]
rewards = {s: -1 if s != 12 else 10 for s in states}lower_edge = [50 + y for y in yr]
upper_edge = [10 + y for y in yr]
left_edge = [10*x + 1 for x in xr]
right_edge = [10*x + 5 for x in xr]def move_left(s):
return s-1 if not s in left_edge else sdef move_right(s):
return s+1 if not s in right_edge else sdef move_up(s):
return s-10 if not s in upper_edge else sdef move_down(s):
return s+10 if not s in lower_edge else s
Utilizando value iteration, em vez de resolver o sistema de equações para todos os estados, vamos transformar a equação de Bellman em uma regra de atualização e computá-la iterativamente:
V = {s: 0 for s in states}thr = 1e-20
err = 10
k = 1while err > thr:
delta = 0
err = []
for s in states:
v_old = V[s]
v_actions = [
0.25*1*(rewards[move_left(s)] + 1*V[move_left(s)]),
0.25*1*(rewards[move_right(s)] + 1*V[move_right(s)]),
0.25*1*(rewards[move_up(s)] + 1*V[move_up(s)]),
0.25*1*(rewards[move_down(s)] + 1*V[move_down(s)])
]
V[s] = max(v_actions)
V[12] = 0 #estado terminal sempre tem value function = 0
err.append(abs(v_old-V[s]))
err = max(err)
k+=1
print(f"iteração: {k}, erro: {err}")
O método utilizado combina algumas etapas e costuma convergir mais rápido do que o iterative policy evaluation. Aqui não trataremos dele, mas você pode encontrar a comparação entre os dois métodos no notebook indicado no final desta publicação.
Para entender melhor o resultado, vamos plotar V(s) no grid. Na figura abaixo, podemos ver que, nos estados vizinhos ao estado terminal, a value-function atinge valor maior (amarelo na escala) e, conforme se afasta do objetivo, tem valores mais negativos. Isso está coerente com o objetivo do MDP, visto que, nos estados mais distantes, serão necessários mais passos para chegar ao objetivo.
Com os valores de vπ(s), é fácil determinar a política ótima:
actions_mapping ={
0: move_left,
1: move_up,
2: move_right,
3: move_down
}pi = {}for s in states:
vals = []
for a in [0,1,2,3]:
movement = actions_mapping[a]
q = rewards[movement(s)] + 1*V[movement(s)]
vals.append(q)
pi[s] = argmax(vals)m = np.array([x for x in pi.values()]).reshape(5,-1)
A resposta é um mapeamento de cada estado do Gridworld e de qual ação resultará no maior qπ(s). Exemplo: no estado inicial (54), a indicação é mover para a esquerda (na verdade poderia ser para cima também, já que a função argmax aplicada acima realizou o desempate entre as duas de forma aleatória).
Vamos melhorar essa visualização:
def plot_arrows(m: np.ndarray):
"""
recebe uma matriz contendo as decisões do Gridworld e retorna um gráfico com setas indicando o caminho
tomado pela política vigente
"""
arr = np.flip(m, axis=0).flatten()
width = m.shape[0]
height = m.shape[1]
x_pos = [x for x in np.arange(0.5,width,1)]*height
y_pos = np.concatenate([np.repeat(x,width) for x in np.arange(0.5,height, 1)])
#mapeia ações em incrementos para as setas
xdir_map = {0: -1, 1:0, 2: 1, 3: 0}
ydir_map = {0:0, 1:1, 2:0, 3:-1}
x_direct = [xdir_map[x] for x in arr]
y_direct = [ydir_map[x] for x in arr]
ig, ax = plt.subplots()
ax.quiver(x_pos, y_pos,x_direct,y_direct,scale=10)ax.axis([0, width, 0, height])
return plt
plot_arrows(m)
Assim, para cada estado, encontramos o caminho mais curto para o objetivo. As equações de Bellman permitem esse resultado porque estamos sempre relacionando o valor do estado atual com seu estado seguinte. Como todos estão encadeados, resolver cada estado implica levar em conta todo o desdobramento das transições a partir dele.
Resolvendo o mesmo exemplo usando Q-learning
Ao utilizar programação dinâmica, você deve ter percebido que há uma varredura nos estados e ações (lembre-se das somatórias). Em MDPs com maior número de estados e ações, isso pode ser computacionalmente pesado, a ponto de ser impraticável utilizar esses métodos para resolver as equações de Bellman.
Adicionalmente, no Gridworld a equação dinâmica do ambiente é trivial, ou seja, sabemos de forma determinística qual será a transição de estado causada por cada ação e, por consequência, sabemos a função P(s’,r|s,a). Em vários sistemas não temos acesso a essa função de dinâmica. Para esses casos, podemos resolver as equações de Bellman utilizando métodos de diferença temporal (TD).
Agora vamos resolver o mesmo exemplo utilizando Q-learning, um dos métodos mais importantes para o reinforcement learning, que é baseado no conceito de diferença temporal (uma junção entre programação dinâmica e Monte Carlo).
Em métodos de TD, utilizamos um processo chamado bootstrapping, que consiste em atualizar estimativas a partir de outras estimativas (nesse caso, dos estados subsequentes).
Vamos começar definindo um ambiente Gridworld de forma mais padronizada:
class Gridworld():
"""
- estado: é um número de dois dígitos em que o primeiro é a posição vertical; e o segundo, a horizontal
ex. 25: segunda linha (de cima para baixo), quinta coluna (da esquerda para a direita)
- inicia em pos_start. Todas as transições valem -1, exceto a transição para pos_end, que vale 10
- ao chegar a pos_end, o ambiente é resetado e retorna a pos_start
- é possível tomar 4 ações em cada estado:
0: esquerda,
1: cima,
2: direita,
3: baixo
- nos estados da borda, as transições retornam o mesmo estado, mas continuam gerando recompensa -1
"""
def __init__(self, hsize, vsize, pos_start, pos_target):
self.hsize = hsize
self.vsize = vsize
self.lower_edge = [(self.hsize)*10 + v for v in np.arange(1,self.vsize+1,1)]
self.upper_edge = [1*10+v for v in np.arange(1,self.vsize+1,1)]
self.left_edge = [h*10+1 for h in np.arange(1,self.hsize+1,1)]
self.right_edge = [h*10+self.vsize for h in np.arange(1,self.hsize+1,1)]self.initial_state = pos_start
self.state = self.initial_state
self.pos_target = pos_target
def __repr__(self):
return f"Grid de {self.hsize}x{self.vsize} iniciando em {self.initial_state} com objetivo {self.pos_target}"
def __str__(self):
return f"Grid de {self.hsize}x{self.vsize} iniciando em {self.initial_state} com objetivo {self.pos_target}"
def step(self,action):
if action == 0: #esquerda
self.state = self.state-1 if not self.state in self.left_edge else self.state
if action == 2: #direita
self.state = self.state+1 if not self.state in self.right_edge else self.state
if action == 1: #cima
self.state = self.state-10 if not self.state in self.upper_edge else self.state
if action == 3: #baixo
self.state = self.state+10 if not self.state in self.lower_edge else self.state
if self.state == self.pos_target:
self.reward = 10
self.terminal = True
self.state = self.initial_state
else:
self.reward = -1
self.terminal = False
return self.state, self.reward, self.terminal, {}
Inicialmente, vamos testar um agente com política uniforme e aleatória:
n_runs=200
cumulative_reward = []
for run in tqdm(range(n_runs)):
terminal = False
k=0
r = 0
while not terminal:
k+=1
action = np.random.choice([0,1,2,3])
out = env.step(action)
r+=out[1]
terminal = out[2]
cumulative_reward.append(r)
print(f"run {run} levou {k} passos")fig = px.line(cumulative_reward)
fig.update_layout({
'title': 'Recompensa acumulada por episódio',
'xaxis_title': 'Episódio',
'yaxis_title': 'Recompensa'
})
Perceba que, de forma similar ao k-armed bandits com agente aleatório, não há uma melhoria ao longo das interações. Aqui, a máxima recompensa possível é de 5 (veja no grid que, no mínimo, o agente precisa dar cinco passos para chegar ao final, recebendo -5 de recompensa + 10 do estado final).
Agora vamos construir um agente que atualiza sua política a partir do Q-learning:
class QLearningAgent():
def __init__(self, alpha=0.1, gamma=1, epsilon=0.05):
self.alpha = alpha #step size
self.gamma = gamma #discount
self.epsilon = epsilon #exploration rate for E-greedy policty
assert self.gamma >0 and self.gamma <=1, "Discount factor must be between (0,1])"
xr = np.arange(1,6,1)
yr = np.arange(1,6,1)
self.states = [x*10 + y for x in xr for y in yr]self.smap = dict(enumerate(states))
self.smap = {v:k for k,v in self.smap.items()} #mapeia os estados recebidos nas linhas da matriz q
self.actions = [0, 1, 2, 3]
self.q_values = np.zeros((len(self.states), len(self.actions)))
def policy(self):
if np.random.random() < self.epsilon:
action = np.random.choice(self.actions)
else:
state_idx = self.smap[self.state]
action = argmax(self.q_values[state_idx,:])
return action
def start(self,response):
"""
called after env starts
"""
self.state = response[0]
action = self.policy()
self.prev_state = self.state
self.prev_action = action
return action
def step(self, response):
"""
agent dealing with env response and taking another action
"""
self.state = response[0]
reward = response[1]
terminal = response[2]
env_info = response[3]
action = self.policy()
# Perform an update
state_idx = self.smap[self.state]
prev_state_idx = self.smap[self.prev_state]
current_q = self.q_values[state_idx, :]
greedy_action = argmax(current_q)
self.q_values[prev_state_idx, self.prev_action] += self.alpha*(
reward +
self.gamma*self.q_values[state_idx,greedy_action] -
self.q_values[prev_state_idx, self.prev_action]
)
self.prev_state = self.state
self.prev_action = action
return actiondef end(self, reward):
"""
agent dealing with episode termination
"""
state_idx = self.smap[self.state]
prev_state_idx = self.smap[self.prev_state]
self.q_values[prev_state_idx, self.prev_action] += self.alpha*(
reward - self.q_values[prev_state_idx, self.prev_action]
)
Realizando o experimento com o agente Q-learning:
n_runs=1500
cumulative_reward = []agent = QLearningAgent(epsilon=0.1)for run in tqdm(range(n_runs)):
terminal = False
k=0
r = 0
while not terminal:
if k==0:
response = (env.initial_state, 0, terminal, {})
action = agent.start(response)
else:
action = agent.step(out)
out = env.step(action)
r+=out[1]
terminal = out[2]
k+=1
agent.end(out[1])
cumulative_reward.append(r)
print(f"run {run} levou {k} passos")
Sem termos uma dinâmica explícita do ambiente, foi possível aprender a política ótima em cerca de 20 episódios. As eventuais quedas na recompensa acumulada são provenientes do comportamento exploratório do agente (com 10% de probabilidade de realizar ações exploratórias nesse caso).
Uma característica importante do Q-learning é que ele é um método off-policy, ou seja, ele pode aprender uma política ótima mesmo que o agente esteja seguindo outra política mais exploratória ou operacional (desde que os estados sejam suficientemente explorados). Essa é uma implicação prática importante, dado que em diversos ambientes não é possível seguir uma política enquanto ela está sendo aprendida, pois isso geraria perdas ou riscos significativos (por exemplo, no caso de um controle de processo industrial com alto risco de segurança).
Para testar esse comportamento, simplesmente mude o parâmetro epsilon para 1 (agente 100% exploratório) e verifique a política aprendida.
Para o agente com epsilon=10%, a política ótima aprendida difere um pouco do resultado encontrado via programação dinâmica: perceba que alguns estados mais distantes do início ou do final tiveram uma estimativa de ação ótima incorreta. Possivelmente com mais episódios ou maior exploração, o Q-learning teria encontrado os resultados corretos, mas essa é uma implicação que pode acontecer em estados pouco explorados.
Conclusão
Wow, cobrimos bastante conteúdo até aqui! Na parte 1 começamos a falando sobre como o aprendizado por reforço difere dos aprendizados supervisionado e não supervisionado e realizamos um experimento com k-armed bandits.
Aqui, exploramos o framework de Markov decision processes para entender a interação sequencial entre um agente e o ambiente, expandindo o conceito para mudanças de estado e recompensa a cada interação.
Vimos que resolver um problema de RL é, na prática, encontrar a política ótima do agente para um dado objetivo, e que esse objetivo deve ser coerente com a definição de recompensa do ambiente. Resolvemos um exemplo de Gridworld para encontrar o caminho mais curto até o estado final utilizando métodos que fundamentam todos os algoritmos de reinforcement learning: programação dinâmica, Monte Carlo e diferença temporal, tudo isso para um caso tabular em que temos um número finito de estados e ações.
Ainda há muito a ser explorado, mas espero que essas duas seções tenham ajudado você a desenvolver uma intuição básica sobre o que é RL e como aplicar algoritmos para o aprendizado de políticas ótimas em um contexto de tomada de decisão sequencial.
Se você deseja se aprofundar no assunto, recomendo explorar os notebooks contendo esses experimentos, que deixei preparados em meu Github, e entender melhor como funciona a teoria a partir do livro de Sutton & Barto, Reinforcement Learning: An Introduction (2.ed. Cambridge, MA: MIT Press, 2018).
