Markov Decision Process (MDP)

Também chamado: MDP
Categoria: Learning & autonomy › RL & simulation
Tags: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

O modelo matemático padrão da tomada de decisão sequencial: estados, ações, probabilidades de transição, recompensas e um fator de desconto, com o próximo estado dependendo apenas do estado e da ação atuais.

Definição

Um processo de decisão de Markov (Markov decision process, MDP) descreve um agente que repetidamente observa um estado, escolhe uma ação, recebe uma recompensa e passa para um novo estado. Ele costuma ser escrito como uma tupla (S, A, P, R, γ), muitas vezes com uma distribuição de estado inicial ρ₀: o espaço de estados, o espaço de ações, as probabilidades de transição P(s′ | s, a), a função de recompensa R(s, a) e um fator de desconto γ entre 0 e 1 que pondera as recompensas futuras em relação às imediatas. A suposição que o define é a propriedade de Markov: a distribuição do próximo estado depende apenas do estado e da ação atuais, não do histórico que levou até ali. O trabalho de Richard Bellman sobre programação dinâmica na década de 1950 estabeleceu o arcabouço.

O objetivo em um MDP é uma política, um mapeamento de estados para ações (ou para distribuições sobre ações), que maximize a soma descontada esperada das recompensas. A função de valor V(s) e a função de valor de ação Q(s, a) dão esse retorno esperado a partir de um estado, ou de um estado e uma ação, sob uma política. Elas satisfazem as equações de Bellman, que expressam o valor de um estado como a recompensa imediata mais o valor descontado dos estados seguintes. Quando P e R são conhecidas e o espaço de estados é pequeno, a iteração de valor e a iteração de política resolvem o MDP de forma exata. Quando são desconhecidas, ou os espaços são grandes e contínuos, o aprendizado por reforço estima valores e políticas a partir de experiência amostrada.

Os MDPs são a base formal de quase todo o aprendizado por reforço e de grande parte do planejamento sob incerteza. Muitas variantes relaxam uma das suposições: um MDP parcialmente observável (POMDP) abandona a suposição de que o agente vê o estado verdadeiro; os MDPs com restrições acrescentam limites de custo; os semi-MDPs permitem ações de duração variável; e extensões multiagente, como os jogos de Markov, modelam vários tomadores de decisão. Escolher o que entra no estado é uma decisão de engenharia: se informações importantes, como velocidades, o estado de contato ou a intenção de outros agentes, ficarem de fora, o processo deixa de ser markoviano do ponto de vista do agente.

Por que importa

Todo artigo de aprendizado por reforço e a maioria dos métodos de tomada de decisão em robótica formulam seu problema como um MDP ou uma variante dele. Conhecer as partes da tupla, e em qual suposição cada método se apoia, torna possível ler esses artigos, projetar estados e recompensas para um robô real e reconhecer quando um problema é, na verdade, parcialmente observável.

Principais aplicações

Formulação de problemas de aprendizado por reforço para manipulação e locomoção
Planejamento sob incerteza com iteração de valor e iteração de política
Projeto de recompensas e aprendizado por reforço inverso, que inferem ou moldam R
Aprendizado por reforço baseado em modelo, que aprende a função de transição P
Modelagem da interação com outros agentes por meio de jogos de Markov e variáveis latentes de intenção

Na prática

Uma equipe que treina um braço robótico para empurrar um bloco até um alvo formula a tarefa como um MDP. O estado contém os ângulos e as velocidades das juntas, a pose do bloco e a posição do alvo; a ação é uma mudança na posição do efetuador final a cada passo de controle; a recompensa é a distância negativa do bloco ao alvo, com um bônus em caso de sucesso; e γ é definido perto de 1 porque a tarefa se estende por muitos passos. Nos primeiros testes, a política se comporta de forma errática quando o bloco está em movimento, porque o estado inclui a pose do bloco, mas não sua velocidade. Acrescentar a velocidade do bloco, ou empilhar as últimas observações, restaura a propriedade de Markov de forma suficientemente próxima para que um algoritmo padrão como SAC ou PPO aprenda de forma confiável.

Equívocos comuns

Um MDP exige estados e ações discretos — espaços de estados e de ações contínuos são comuns em robótica, com somas substituídas por integrais e métodos tabulares substituídos por aproximação de funções
A propriedade de Markov é um fato sobre o mundo — ela é uma propriedade do estado escolhido; deixar de fora velocidades ou variáveis ocultas pode tornar um sistema físico não markoviano do ponto de vista do agente
O fator de desconto reflete apenas impaciência — ele também limita o retorno em problemas de horizonte infinito e afeta a variância e a estabilidade do aprendizado, por isso costuma ser ajustado como um hiperparâmetro
Resolver um MDP exige um modelo de P — os métodos de aprendizado por reforço encontram boas políticas a partir de transições amostradas sem nunca escrever P

Quem deve saber

Profissionais e pesquisadores de aprendizado por reforço
Engenheiros de aprendizado robótico que projetam estados, ações e recompensas
Pesquisadores de planejamento e tomada de decisão
Estudantes de robótica que estão começando no aprendizado robótico

Tecnologias relacionadas

Equação de Bellman (Bellman Equation)
Iteração de valor (Value Iteration)
Iteração de política (Policy Iteration)
Q-Learning
Gymnasium
Programação dinâmica (Dynamic Programming)

Termos relacionados

Projetos relacionados

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
MuJoCo: DeepMind physics engine for robotics and ML research
PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
OpenPI: Physical Intelligence VLA foundation models for general robot control
Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

Vídeos

Markov Decision Processes - Computerphile: Computerphile