Phase 09 - Lesson 01

MDPs, Estados, Ações & Recompensas

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Um Processo de Decisão de Markov é constituído por cinco elementos: estados, ações, transições, recompensas e um fator de desconto. Tudo em RL — Q-learning, PPO, DPO, GRPO — é otimizado com base nessa estrutura. Aprenda isso uma vez e compreenda o restante do aprendizado por reforço facilmente.

Tipo: Aprender Linguagens: Python Pré-requisitos: Fase 1 · 06 (Probabilidade & Distribuições), Fase 2 · 01 (Taxonomia de ML) Tempo: ~45 minutos

O Problema

Você está escrevendo um bot de xadrez. Ou um planejador de inventário. Ou um agente de trading. Ou o loop PPO que treina um modelo de raciocínio. Quatro domínios diferentes, um fato surpreendente: todos os quatro se reduzem ao mesmo objeto matemático.

O aprendizado supervisionado fornece pares (x, y) e pede para você ajustar uma função. O aprendizado por reforço não fornece rótulos — apenas um fluxo de estados, as ações que você tomou e uma recompensa escalar. O movimento venceu o jogo? A decisão de reabastecimento economizou dinheiro? A negociação gerou lucro? O token que o LLM acabou de produzir levou a uma recompensa maior do avaliador?

Você não pode aprender com esse fluxo até formalizá-lo. "O que eu vi", "o que eu fiz", "o que aconteceu em seguida", "o quão bom isso foi" — cada um deve se tornar um objeto sobre o qual você possa raciocinar. Essa formalização é um Processo de Decisão de Markov (MDP). Cada algoritmo de RL nesta fase, incluindo os loops de RLHF e GRPO ao final, otimiza com base nessa estrutura.

O Conceito

Os cinco objetos.

• Estados S. Tudo o que o agente precisa para decidir. No GridWorld, a célula. No xadrez, o tabuleiro. Em um LLM, a janela de contexto mais qualquer memória.
• Ações A. As escolhas. Mover para cima/baixo/esquerda/direita. Fazer uma jogada. Emitir um token.
• Transições P(s' | s, a). Dado um estado s e uma ação a, a distribuição sobre o próximo estado. Determinístico no xadrez, estocástico no inventário, quase determinístico na decodificação de LLM.
• Recompensas R(s, a, s'). O sinal escalar. Vitória = +1, derrota = -1. Receita menos custo. O termo da razão de log-verossimilhança no GRPO.
• Desconto γ ∈ [0, 1). O quanto a recompensa futura conta em relação à presente. γ = 0.99 define um horizonte de ~100 passos; γ = 0.9 define ~10 passos.

A propriedade de Markov P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_0, a_0, …, s_t, a_t). O futuro depende apenas do estado presente. Se não depender, a representação do estado está incompleta — não se trata de uma falha do método, mas de uma falha do estado.

Políticas e retornos. Uma política π(a | s) mapeia estados para distribuições de ações. O retorno G_t = r_t + γ r_{t+1} + γ² r_{t+2} + … é a soma descontada das recompensas futuras. O valor V^π(s) = E[G_t | s_t = s] é o retorno esperado começando a partir de s sob a política π. O valor Q Q^π(s, a) = E[G_t | s_t = s, a_t = a] é o retorno esperado começando com uma ação específica. Todo algoritmo de RL estima um desses dois valores e, em seguida, melhora π de acordo.

As equações de Bellman. As equações de ponto fixo que tudo nesta fase utiliza:

V^π(s) = Σ_a π(a|s) Σ_{s', r} P(s', r | s, a) [r + γ V^π(s')] Q^π(s, a) = Σ_{s', r} P(s', r | s, a) [r + γ Σ_{a'} π(a'|s') Q^π(s', a')]

Elas dividem o retorno esperado em "recompensa deste passo" mais o "valor descontado de onde você pousa." Recursivo. Todo algoritmo na Fase 9 itera essa equação até a convergência (programação dinâmica), realiza amostragens a partir dela (Monte Carlo) ou faz o bootstrap de um passo (diferença temporal).

Construa

Passo 1: um pequeno MDP determinístico

Um GridWorld 4×4. O agente começa no canto superior esquerdo, o estado terminal fica no canto inferior direito, a recompensa é de -1 por passo e as ações são {up, down, left, right}. Veja code/main.py.

GRID = 4
TERMINAL = (3, 3)
ACTIONS = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}

def step(state, action):
    if state == TERMINAL:
        return state, 0.0, True
    dr, dc = ACTIONS[action]
    r, c = state
    nr = min(max(r + dr, 0), GRID - 1)
    nc = min(max(c + dc, 0), GRID - 1)
    return (nr, nc), -1.0, (nr, nc) == TERMINAL

Cinco linhas. Esse é o ambiente inteiro. Transições determinísticas, penalidade constante por passo, estado terminal absorvente.

Passo 2: executar (rollout) uma política

Uma política é uma função que mapeia um estado para uma distribuição de ações. A mais simples: aleatória uniforme.

def uniform_policy(state):
    return {a: 0.25 for a in ACTIONS}

def rollout(policy, max_steps=200):
    s, total, steps = (0, 0), 0.0, 0
    for _ in range(max_steps):
        a = sample(policy(s))
        s, r, done = step(s, a)
        total += r
        steps += 1
        if done:
            break
    return total, steps

Execute a política aleatória 1000 vezes. O retorno médio fica em torno de -60 a -80 para este tabuleiro 4×4. O retorno ideal é -6 (caminho em linha reta para baixo e para a direita). Fechar essa lacuna é o objetivo principal da Fase 9.

Passo 3: calcular V^π exatamente por meio da equação de Bellman

Para MDPs pequenos, a equação de Bellman é um sistema linear. Enumere os estados, aplique a expectativa (valor esperado), e itere até que os valores parem de mudar.

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in all_states()}
    while True:
        delta = 0.0
        for s in all_states():
            if s == TERMINAL:
                continue
            v = 0.0
            for a, pi_a in policy(s).items():
                s_next, r, _ = step(s, a)
                v += pi_a * (r + gamma * V[s_next])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

Isso é a avaliação de política iterativa. É o primeiro algoritmo em Sutton & Barto e a base teórica de todos os métodos de RL que o sucedem.

Passo 4: γ é um hiperparametro com significado físico

O horizonte efetivo é de aproximadamente 1 / (1 - γ). γ = 0.9 → 10 passos. γ = 0.99 → 100 passos. γ = 0.999 → 1000 passos.

Um valor muito baixo faz o agente agir de forma míope. Um valor muito alto torna a atribuição de crédito ruidosa, pois muitos passos iniciais compartilham a responsabilidade por recompensas no futuro distante. O RLHF para LLMs normalmente usa γ = 1 porque os episódios são curtos e delimitados. Tarefas de controle usam 0.95–0.99. Jogos de estratégia com horizonte longo usam 0.999.

Armadilhas

• Estado Não Markoviano. Se você precisa das três últimas observações para decidir, o "estado" não é apenas a observação atual. Solução: empilhar quadros (o DQN no Atari empilha 4) ou usar um estado recorrente (LSTM/GRU sobre as observações).
• Recompensas esparsas. Recompensas baseadas apenas em vitória/derrota tornam o aprendizado quase impossível em espaços de estados grandes. Modele as recompensas (sinal intermediário) ou inicialize com imitação (Fase 9 · 09).
• Exploração de recompensa (Reward hacking). Otimizar uma recompensa proxy frequentemente produz comportamentos patológicos. O agente de corrida de barcos da OpenAI girava em círculos coletando power-ups indefinidamente em vez de terminar a corrida. Sempre defina a recompensa a partir do resultado final desejado, não de uma proxy.
• Especificação incorreta do desconto. γ = 1 em uma tarefa de horizonte infinito torna todos os valores infinitos. Sempre defina um limite usando um horizonte finito ou γ < 1.
• Escala de recompensa. Recompensas de {+100, -100} versus {+1, -1} geram políticas ideais idênticas, mas magnitudes de gradiente muito diferentes. Normalize para algo próximo a [-1, 1] antes de usar em PPO/DQN.

Use

O stack de 2026 reduz cada pipeline de RL a um MDP antes de tocar no código:

Escreva as cinco tuplas antes de programar qualquer loop de treinamento. A maioria dos relatórios de bug do tipo "RL não funciona" se resume a uma formulação de MDP que já estava incorreta no papel.

Entregar

Salve como outputs/skill-mdp-modeler.md:

---
name: mdp-modeler
description: Given a task description, produce a Markov Decision Process spec and flag formulation risks before training.
version: 1.0.0
phase: 9
lesson: 1
tags: [rl, mdp, modeling]
---

Given a task (control / game / recommendation / LLM fine-tuning), output:

1. State. Exact feature vector or tensor spec. Justify Markov property.
2. Action. Discrete set or continuous range. Dimensionality.
3. Transition. Deterministic, stochastic-with-known-model, or sample-only.
4. Reward. Function and source. Sparse vs shaped. Terminal vs per-step.
5. Discount. Value and horizon justification.

Refuse to ship any MDP where the state is non-Markovian without explicit mention of frame-stacking or recurrent state. Refuse any reward that was not defined in terms of the target outcome. Flag any `γ ≥ 1.0` on an infinite-horizon task. Flag any reward range >100x the typical step reward as a likely gradient-explosion source.

Exercícios

1. Fácil. Implemente o GridWorld 4×4 e o rollout de política aleatória em code/main.py. Execute 10.000 episódios. Relate a média e o desvio padrão do retorno. Compare com o retorno ideal (-6).
2. Médio. Execute policy_evaluation com γ ∈ {0.5, 0.9, 0.99} para a política aleatória uniforme. Imprima V como uma grade 4×4 para cada caso. Explique por que os valores de estado próximos ao terminal crescem mais rapidamente com um γ maior.
3. Difícil. Torne o GridWorld estocástico: cada ação desliza para uma direção adjacente com probabilidade p = 0.1. Reavalie a política uniforme. V[start] melhora ou piora? Por quê?

Termos-Chave

Leituras Adicionais

• Sutton & Barto (2018). Reinforcement Learning: An Introduction, 2nd ed. — o livro-texto. O Capítulo 3 cobre MDPs e equações de Bellman; o Capítulo 1 fundamenta a hipótese de recompensa que serve de base para todas as lições subsequentes.
• Bellman (1957). Dynamic Programming — a origem da equação de Bellman.
• OpenAI Spinning Up — Part 1: Key Concepts — introdução concisa sobre MDP sob a perspectiva de deep-RL.
• Puterman (2005). Markov Decision Processes — a referência de pesquisa operacional sobre MDPs e métodos de solução exatos.
• Littman (1996). Algorithms for Sequential Decision Making (PhD thesis) — a derivação mais clara de MDPs como uma especialização de programação dinâmica.