Markov Decision Process (MDP)

Um processo de decisão de Markov (MDP) é o modelo matemático de um problema de decisão sequencial: um agente observa um estado, escolhe uma ação, recebe uma recompensa e chega a um estado seguinte que depende em parte de sua escolha e em parte do acaso. Formalmente, um MDP consiste num conjunto de estados, um conjunto de ações, probabilidades de transição P(s′ | s, a), uma função de recompensa R(s, a) e, geralmente, um fator de desconto γ entre 0 e 1. Resolvê-lo significa encontrar uma política — uma regra que escolhe uma ação em cada estado — que maximize a soma esperada e descontada das recompensas futuras. Os MDPs surgiram na pesquisa operacional na década de 1950, quando a programação dinâmica de Richard Bellman forneceu métodos para resolvê-los, e constituem a formulação padrão de problemas de aprendizado por reforço (RL).

A propriedade de Markov#

A suposição fundamental é a propriedade de Markov: o próximo estado e a recompensa dependem apenas do estado e da ação atuais, não do caminho que levou até eles. Assim, o estado é o resumo completo de tudo que é relevante para o agente. Um único quadro da câmera viola essa suposição para um objeto em movimento, pois mostra a posição, mas não a velocidade; por isso, a DQN da DeepMind que jogava Atari recebia os últimos quatro quadros empilhados para poder perceber o movimento.

Quando o agente não consegue observar o estado completo, como no caso de um robô com sensores ruidosos ou obstruídos, o problema é um MDP parcialmente observável (POMDP). Nesse caso, o agente age com base numa crença sobre o estado, mantida por um filtro ou uma rede recorrente, em vez de agir com base no próprio estado.

Componentes de um MDP#

• Estados: as situações em que o agente pode estar, como os ângulos das juntas de um robô e a posição do objeto que ele tenta alcançar.
• Ações: as opções disponíveis em cada estado. O espaço de ações pode ser discreto (virar à esquerda, virar à direita) ou contínuo (um ângulo de direção em graus).
• Probabilidades de transição: a probabilidade de cada estado seguinte após uma ação, que representa o deslizamento das rodas, outros motoristas e todas as demais fontes de aleatoriedade.
• Recompensas: o retorno numérico imediato de uma transição. A escolha das recompensas pelo projetista define a tarefa, e uma escolha descuidada pode incentivar a manipulação de recompensas.
• Fator de desconto: quanto as recompensas futuras contam em relação às imediatas. Com γ = 0.9, uma recompensa daqui a dez passos vale 0.9¹⁰ ≈ 0.35 da mesma recompensa recebida agora.

A cada passo de tempo, a mesma interação se repete até o fim do episódio:

Resolução de um MDP#

O valor de um estado é o retorno esperado a partir dele segundo uma política, e os valores ótimos satisfazem a equação de Bellman: o valor de cada estado equivale à recompensa imediata da melhor ação somada ao valor descontado e ponderado pelas probabilidades dos estados aos quais ela leva. Quando as probabilidades de transição e as recompensas são conhecidas, a programação dinâmica resolve essa equação diretamente. A iteração de valores (Bellman, 1957) aplica a equação repetidamente até que os valores parem de mudar, e a iteração de políticas (Howard, 1960) alterna entre avaliar uma política e aprimorá-la.

Este exemplo com NumPy executa a iteração de valores no robô de reciclagem do livro Reinforcement Learning: An Introduction, de Sutton e Barto. O robô precisa escolher entre procurar latas, esperar e recarregar a bateria, que pode estar alta ou baixa:

import numpy as np

# MDP do robô de reciclagem: estados 0 = bateria alta, 1 = bateria baixa; ações 0 = procurar, 1 = esperar, 2 = recarregar
gamma = 0.9  # fator de desconto
P = np.zeros((2, 3, 2))  # P[s, a, s'] = probabilidade de chegar a s' após executar a em s
P[0, 0] = [0.7, 0.3]  # procurar com a bateria alta pode deixá-la baixa
P[1, 0] = [0.4, 0.6]  # procurar com a bateria baixa pode esgotá-la (o robô é resgatado e recarregado)
P[:, 1] = np.eye(2)  # esperar mantém o nível da bateria inalterado
P[:, 2] = [1.0, 0.0]  # recarregar sempre restaura a bateria ao nível alto
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # R[s, a] esperado; procurar com bateria baixa: 0.6 * 2 + 0.4 * -3 = 0

# Iteração de valores: aplica a atualização de otimalidade de Bellman até que os valores parem de mudar
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # valor de cada ação em cada estado
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

O código imprime valores de 15.75 para a bateria alta e 14.17 para a baixa, além de uma política que procura com a bateria alta e recarrega com a baixa: o risco de 40% de uma penalidade de resgate de −3 faz com que procurar com a bateria baixa valha menos do que recarregar.

Quando as probabilidades de transição são desconhecidas, o aprendizado por reforço estima os mesmos valores com base na experiência. O Q-learning atualiza os valores das ações a partir de transições amostradas, os métodos de gradiente de política ajustam diretamente uma política e o aprendizado profundo por reforço usa redes neurais quando o espaço de estados é grande demais para ser enumerado. Algoritmos de planejamento, como a busca em árvore de Monte Carlo, resolvem MDPs enormes on-line simulando apenas os futuros alcançáveis a partir do estado atual.

MDPs e modelos relacionados#

• Cadeia de Markov: sequência de estados aleatórios sem ações nem recompensas. Um MDP acrescenta as escolhas e o objetivo.
• Modelo oculto de Markov (HMM): cadeia de Markov cujos estados são observados apenas por meio de sinais ruidosos. Um POMDP tem a mesma relação com um MDP.
• Bandido multibraço: MDP com um único estado, em que cada ação gera um retorno independente do passado.
• Aprendizado por reforço: conjunto de métodos que aprendem a agir bem num MDP por meio da interação, sem receber as probabilidades de transição.

Aplicações#

• Robótica e controle: tarefas de agarrar, caminhar e navegar são formuladas como MDPs, e suas políticas costumam ser treinadas em simulação. No controle baseado em câmera, um detector como o Ultralytics YOLO26 pode fornecer o estado, transformando cada quadro numa lista curta de classes de objetos e coordenadas de caixas, uma entrada muito menor para a política do que os pixels brutos.
• Treinamento de modelos de linguagem: RLHF e RLVR tratam a geração de texto como um MDP cujo estado é o prompt mais os tokens gerados até então, cuja ação é o próximo token e cuja recompensa chega quando a resposta está completa.
• Pesquisa operacional: reabastecimento de estoque, manutenção de equipamentos e precificação dinâmica são problemas clássicos de MDP, e Ronald Howard desenvolveu a iteração de políticas enquanto otimizava o envio de catálogos da Sears.