Processos de Decisão de Markov (Markov Decision Processes, MDPs)

Processos de Decisão de Markov (MDPs) são a estrutura matemática padrão para modelar tomada de decisão sequencial sob incerteza, e estão no núcleo do Aprendizado por Reforço moderno. Um MDP formaliza o ciclo de interação entre um agente (tomador de decisão) e um ambiente (mundo): o agente observa um estado, toma uma ação, o ambiente transita para um novo estado, e o agente recebe uma recompensa. Aprender (ou planejar) consiste em escolher ações ao longo do tempo para maximizar a recompensa de longo prazo.

O que é um MDP (definição formal)

Um MDP é tipicamente definido como uma 5-tupla:

[ \mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \gamma) ]

Onde:

• (\mathcal{S}) (estados): O conjunto de estados do ambiente.
• (\mathcal{A}) (ações): O conjunto de ações disponíveis para o agente.
• (P) (dinâmica de transição): Um modelo estocástico de como o ambiente evolui: [ P(s' \mid s, a) = \Pr(S_{t+1}=s' \mid S_t=s, A_t=a) ]
• (R) (função de recompensa): Um modelo de feedback imediato. Formas comuns:
  • Recompensa esperada: [ R(s,a) = \mathbb{E}[R_{t+1} \mid S_t=s, A_t=a] ]
  • Ou recompensa dependente da transição: [ R(s,a,s') ]
• (\gamma) (fator de desconto): (\gamma \in [0,1)) (às vezes (\gamma = 1) para tarefas episódicas de horizonte finito). Ele reduz o peso de recompensas no futuro distante.

Em muitos textos você também verá uma distribuição de estado inicial explícita (\rho_0(s)) e estados terminais para problemas episódicos; eles são úteis, mas nem sempre são incluídos na definição mínima.

O ciclo de interação

No tempo (t):

1. O ambiente está no estado (S_t).
2. O agente escolhe uma ação (A_t).
3. O ambiente transita para (S_{t+1}\sim P(\cdot\mid S_t,A_t)).
4. O agente recebe uma recompensa (R_{t+1}).

O objetivo do agente é maximizar o retorno esperado, geralmente a soma descontada de recompensas futuras:

[ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} ]

Para tarefas episódicas com tempo terminal (T), a soma vai até (T-1).

A propriedade de Markov (por que “Markov” importa)

Um MDP assume a propriedade de Markov:

O futuro é condicionalmente independente do passado dado o estado presente.

Formalmente:

[ \Pr(S_{t+1}=s', R_{t+1}=r \mid S_t=s, A_t=a, \text{history}) = \Pr(S_{t+1}=s', R_{t+1}=r \mid S_t=s, A_t=a) ]

Intuição: o estado (S_t) deve conter toda a informação do histórico que é relevante para prever o que acontece a seguir.

Implicações práticas

• Se o seu “estado” estiver faltando informações-chave, o problema pode não ser Markoviano, e algoritmos que assumem um MDP podem se comportar mal.
• Muitas vezes é possível tornar um processo Markoviano expandindo a representação de estado:
  • Incluir velocidade além da posição (controle clássico).
  • Incluir as últimas observações (quadros empilhados em Atari).
  • Usar um modelo de memória aprendido (por exemplo, redes recorrentes), o que aproxima você da visão de POMDP (Processo de Decisão de Markov Parcialmente Observável).

Exemplo: termostato (estado Markoviano vs não Markoviano)

• Estado não Markoviano: apenas a temperatura atual pode não prever a temperatura de amanhã se o aquecimento depender de uma janela estar aberta.
• Estado Markoviano: temperatura + estado da janela + temperatura externa (ou variáveis suficientes para prever a dinâmica).

Políticas: como um agente se comporta

Uma política (\pi) especifica como o agente escolhe ações.

• Política estocástica: [ \pi(a\mid s) = \Pr(A_t=a \mid S_t=s) ]
• Política determinística: [ a = \pi(s) ]

Uma restrição comum são políticas estacionárias (invariantes no tempo), em que o mapeamento de estado para ação não depende explicitamente do tempo (t). Para muitos MDPs descontados de horizonte infinito, existem políticas ótimas na classe estacionária.

Desconto e por que \(\gamma\) existe

O fator de desconto (\gamma) cumpre múltiplos papéis:

• Preferência por recompensas mais cedo: útil quando “agora” é mais valioso do que “depois”.
• Conveniência matemática: garante que retornos sejam finitos em tarefas contínuas.
• Modelagem de incerteza: às vezes interpretado como a probabilidade de o episódio continuar.

A escolha de (\gamma) depende da tarefa:

• Perto de 0: comportamento míope (otimiza recompensa imediata).
• Perto de 1: planejamento de longo prazo (mas pode aumentar a variância e a dificuldade de aprendizado).

Funções de valor: prevendo recompensa de longo prazo

Dada uma política (\pi), definimos:

Função valor-estado \(V^\pi(s)\)

Retorno esperado a partir do estado (s), seguindo (\pi):

[ V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t=s] ]

Função valor-ação \(Q^\pi(s,a)\)

Retorno esperado a partir de ((s,a)), e então seguindo (\pi):

[ Q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s, A_t=a] ]

Essas funções comprimem “o futuro” em um único número e são a base da maioria dos métodos de planejamento e aprendizado.

Equações de Bellman: a recursão central

A propriedade de Markov implica que funções de valor satisfazem equações de Bellman, que expressam “valor = recompensa imediata + valor descontado do estado sucessor”.

Equação de expectativa de Bellman (para \(V^\pi\))

[ V^\pi(s) = \sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\left(R(s,a,s') + \gamma V^\pi(s')\right) ]

Equação de expectativa de Bellman (para \(Q^\pi\))

[ Q^\pi(s,a) = \sum_{s'}P(s'\mid s,a)\left(R(s,a,s') + \gamma \sum_{a'}\pi(a'\mid s')Q^\pi(s',a')\right) ]

Elas não são apenas definições — são restrições de autoconsistência. Muitos algoritmos de aprendizado por reforço podem ser vistos como tentativas de impô-las a partir de dados.

Otimalidade: encontrando a melhor política

Defina as funções de valor ótimas:

[ V^(s) = \max_\pi V^\pi(s), \quad Q^(s,a) = \max_\pi Q^\pi(s,a) ]

Equação de otimalidade de Bellman (para \(V^*\))

[ V^(s) = \max_{a}\sum_{s'}P(s'\mid s,a)\left(R(s,a,s') + \gamma V^(s')\right) ]

Equação de otimalidade de Bellman (para \(Q^*\))

[ Q^(s,a) = \sum_{s'}P(s'\mid s,a)\left(R(s,a,s') + \gamma \max_{a'}Q^(s',a')\right) ]

Uma política ótima pode ser extraída de (Q^*) agindo de forma gananciosa:

[ \pi^(s) \in \arg\max_a Q^(s,a) ]

Planejamento vs aprendizado: visões baseadas em modelo e sem modelo

MDPs separam de forma clara dois cenários de problema:

Planejamento (modelo conhecido)

Se (P) e (R) são conhecidos (ou podem ser consultados), você pode computar comportamento ótimo via programação dinâmica (dynamic programming):

• Avaliação de política: computar (V^\pi) para uma (\pi) fixa
• Melhoria de política: tornar (\pi) mais gananciosa em relação aos seus valores
• Iteração de política: alternar avaliação e melhoria
• Iteração de valor: aplicar diretamente o backup de otimalidade de Bellman até convergir

Aprendizado (modelo desconhecido)

Em aprendizado por reforço, o agente frequentemente não conhece (P) e (R) e deve aprender a partir de transições amostradas ((s,a,r,s')). Famílias populares incluem:

• Métodos de diferença temporal (temporal-difference) (alvos de Bellman via bootstrap)
  • Q-learning (off-policy)
  • SARSA (on-policy)
• Métodos de gradiente de política (policy-gradient) / ator-crítico (actor-critic) (otimizam políticas parametrizadas diretamente)
• Aprendizado por reforço baseado em modelo (model-based RL) (aprende uma aproximação de (P) e (R), e então planeja)

Mesmo quando o ambiente não é um MDP perfeito, a abstração de MDP frequentemente permanece como ponto de partida.

Exemplo prático 1: navegação em Gridworld

Considere um robô em uma grade 2D:

• Estados (\mathcal{S}): células da grade (por exemplo, ((x,y)))
• Ações (\mathcal{A}): {cima, baixo, esquerda, direita}
• Transições (P):
  • Determinísticas: mover na direção pretendida a menos que esteja bloqueado
  • Ou estocásticas: 80% pretendida, 10% escorrega à esquerda, 10% escorrega à direita
• Recompensas (R):
  • -1 por passo (incentiva caminhos mais curtos)
  • +10 ao alcançar o objetivo
  • Estado terminal no objetivo
• Desconto (\gamma): 0.99 (prefere levemente caminhos mais curtos)

Este é um MDP clássico em que backups de Bellman correspondem diretamente a “qual é a melhor forma de chegar ao objetivo levando em conta o escorregão?”

Iteração de valor mínima (Python ilustrativo)

import numpy as np

def value_iteration(states, actions, P, R, gamma=0.99, tol=1e-6):
    # V[s] stores value; assume states are indexed 0..n-1
    n = len(states)
    V = np.zeros(n)

    while True:
        delta = 0.0
        for s in range(n):
            v_old = V[s]
            q_values = []
            for a in actions:
                # P[s][a] is list of (prob, s_next)
                q = 0.0
                for prob, s_next in P[s][a]:
                    q += prob * (R[s][a][s_next] + gamma * V[s_next])
                q_values.append(q)
            V[s] = max(q_values)
            delta = max(delta, abs(v_old - V[s]))
        if delta < tol:
            break

    # derive greedy policy
    pi = np.zeros(n, dtype=int)
    for s in range(n):
        q_values = []
        for a in actions:
            q = sum(prob * (R[s][a][s_next] + gamma * V[s_next])
                    for prob, s_next in P[s][a])
            q_values.append(q)
        pi[s] = int(np.argmax(q_values))
    return V, pi

Este trecho mostra o uso mecânico da atualização de otimalidade de Bellman. Em espaços de estados grandes, você raramente enumera estados dessa forma; em vez disso, você aproxima funções de valor com aproximadores de função (frequentemente redes neurais profundas).

Exemplo prático 2: controle de estoque (um MDP real de operações)

Um problema semanal simplificado de estoque:

• Estado (s): nível atual de estoque (por exemplo, 0…100 unidades)
• Ação (a): quantidade a pedir (0…50 unidades)
• Transição: o próximo estoque depende da demanda estocástica (D): [ s' = \max(0, s + a - D) ]
• Recompensa: lucro menos custos:
  • receita de vendas (limitada pelo estoque)
  • custo de armazenagem para estoque remanescente
  • penalidade por ruptura de estoque para demanda não atendida
• Desconto: próximo de 1 para negócios contínuos

Isso é naturalmente modelado como um MDP e resolvido com programação dinâmica (se estado/ação forem pequenos) ou aprendizado por reforço (se a dinâmica de demanda for complexa/desconhecida). O estado “Markoviano” pode precisar incluir sazonalidade ou regimes latentes de demanda, o que leva diretamente a preocupações de observabilidade parcial.

Tarefas episódicas vs contínuas, horizontes e término

MDPs podem representar:

• Tarefas episódicas: têm estados terminais (jogos, navegação até um objetivo, robótica de pegar-e-colocar). Os retornos são finitos devido ao término.
• Tarefas contínuas: sem estado terminal (balanceamento de carga de servidores, trading). Desconto ((\gamma < 1)) ou formulações de recompensa média são comuns.

Em MDPs episódicos, é comum adicionar um estado terminal absorvente em que as transições permanecem no terminal com recompensa zero, tornando a matemática uniforme.

O que MDPs assumem — e o que não assumem

MDPs são poderosos, mas codificam suposições:

• Observabilidade completa: o agente “vê” o verdadeiro estado (S_t)
• Dinâmica Markoviana: o estado é suficiente para prever resultados no próximo passo
• Estacionariedade: (P) e (R) não mudam ao longo do tempo (a menos que o tempo seja incluído no estado)

Sistemas do mundo real frequentemente violam isso (variáveis ocultas, dinâmica com deriva, usuários não estacionários). Quando isso acontece, você:

• enriquece a representação de estado (engenharia de atributos ou aprendizado de representações), ou
• migra para a formalização de observabilidade parcial.

Relação com POMDPs (observabilidade parcial)

Um Processo de Decisão de Markov Parcialmente Observável (Partially Observable Markov Decision Process) (veja POMDP (Processo de Decisão de Markov Parcialmente Observável)) generaliza um MDP ao assumir que o agente não consegue observar diretamente o verdadeiro estado (S_t). Em vez disso, ele recebe uma observação (O_t) gerada a partir de um modelo de observação:

[ O_t \sim \Omega(\cdot \mid S_t) ]

Um POMDP é frequentemente escrito como:

[ (\mathcal{S}, \mathcal{A}, P, R, \Omega, \mathcal{O}, \gamma) ]

Ideia-chave: em um POMDP, a decisão ótima geralmente depende do histórico de observações e ações, e não apenas da observação mais recente. Uma forma padrão de recuperar uma estrutura tipo MDP é manter um estado de crença (belief state):

[ b_t(s) = \Pr(S_t=s \mid \text{history}) ]

Estados de crença evoluem de modo Markoviano (dada a ação e a nova observação), então um POMDP pode ser convertido em um MDP (tipicamente contínuo) sobre crenças. Na prática, muitos sistemas de aprendizado por reforço profundo aproximam isso com recorrência (RNNs) ou estimadores de estado.

Por que MDPs continuam sendo a “formalização padrão” em aprendizado por reforço

Mesmo quando ambientes são complexos, MDPs fornecem:

• Uma linguagem limpa para especificar problemas (estados/ações/recompensas/dinâmica)
• Uma base para funções de valor e equações de Bellman
• Um referencial para desenho de algoritmos (programação dinâmica, aprendizado por diferença temporal, otimização de políticas)
• Uma ponte para cenários mais realistas (POMDPs, extensões multiagente, MDPs com restrições)

A maior parte do trabalho em aprendizado por reforço pode ser vista como respondendo a alguma variante de:

• Dado um MDP, como computamos ou aprendemos (\pi^*) de forma eficiente?
• Se o mundo não é exatamente um MDP, como o aproximamos bem o suficiente para agir?

Aplicações comuns da modelagem com MDPs

MDPs (e variantes próximas) aparecem em muitos cenários aplicados:

• Robótica: locomoção, manipulação, navegação (frequentemente aproximadas como MDPs; às vezes melhor como POMDPs devido a ruído de sensores)
• Recomendação e ranqueamento: interação sequencial com o usuário, engajamento de longo prazo (não estacionariedade é um grande desafio)
• Pesquisa operacional: estoque, escalonamento, filas, precificação
• Saúde: planejamento de tratamento como decisões sequenciais (requer cuidado com observabilidade parcial e confundimento)
• Jogos e simuladores: jogos de informação perfeita frequentemente se ajustam a MDPs; informação imperfeita se alinha a POMDPs

Resumo

Um MDP modela tomada de decisão sequencial com:

• Estados (\mathcal{S}), ações (\mathcal{A})
• Dinâmica de transição (P(s'\mid s,a))
• Recompensas (R)
• Desconto (\gamma)
• Políticas (\pi(a\mid s))

A propriedade de Markov faz com que o futuro dependa do estado presente (e da ação), em vez de todo o passado, viabilizando funções de valor (V^\pi, Q^\pi) e suas equações de Bellman recursivas. Resolver um MDP (por planejamento ou aprendizado) é central em aprendizado por reforço; quando a observabilidade completa falha, a extensão natural é o POMDP (Processo de Decisão de Markov Parcialmente Observável), em que o agente raciocina sobre estado oculto via observações ou estados de crença.

---