Phase 09 - Lesson 02

Programação Dinâmica — Iteração de Política & Iteração de Valor

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

Programação dinâmica é aprendizado por reforço com trapaça. Você já conhece as funções de transição e recompensa; você apenas itera a equação de Bellman até que V ou π parem de mudar. É a referência que todo método baseado em amostragem tenta alcançar.

Type: Build Languages: Python Prerequisites: Phase 9 · 01 (MDPs) Time: ~75 minutos

O Problema

Você tem um MDP com um modelo conhecido: você pode consultar P(s' | s, a) e R(s, a, s') para qualquer par estado-ação. Um gerente de estoque conhece a distribuição da demanda. Um jogo de tabuleiro possui transições determinísticas. Um gridworld são quatro linhas de Python. Você tem um modelo.

O RL livre de modelo (Q-learning, PPO, REINFORCE) foi inventado para o caso em que você não tem um modelo — você só pode obter amostras do ambiente. Mas quando você tem um, existem métodos melhores e mais rápidos: programação dinâmica. Bellman os projetou em 1957. Eles ainda definem o que é correto: quando as pessoas dizem "política ótima para este MDP", elas se referem à política que a programação dinâmica retornaria.

Você precisa deles em 2026 por três motivos. Primeiro, todo ambiente tabular na pesquisa de RL (GridWorld, FrozenLake, CliffWalking) é resolvido com programação dinâmica para produzir a política padrão-ouro. Segundo, valores exatos permitem que você faça o depuração de métodos de amostragem: se a estimativa do Q-learning para V*(s_0) diferir da resposta da programação dinâmica em 30%, seu Q-learning tem um bug. Terceiro, o RL offline moderno e os métodos de planejamento (MCTS, busca do AlphaZero, RL baseado em modelo na Fase 9 · 10) todos iteram uma atualização de Bellman sobre um modelo aprendido ou fornecido.

O Conceito

Dois algoritmos, ambos iterações de ponto fixo em Bellman.

Policy iteration. Alterna duas etapas até que a política pare de mudar.

1. Avaliação: dada a política π, calcule V^π aplicando repetidamente V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')] até convergir.
2. Melhoria: dada V^π, torne π gulosa em relação a V^π: π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')].

A convergência é garantida porque (a) cada etapa de melhoria mantém π igual ou aumenta estritamente V^π para algum estado, (b) o espaço de políticas determinísticas é finito. Geralmente converge em ~5–20 iterações externas, mesmo para grandes espaços de estados.

Value iteration. Colapsa a avaliação e a melhoria em uma única varredura. Aplique a equação de otimalidade de Bellman:

V(s) ← max_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]

Repita até que max_s |V_{new}(s) - V(s)| < ε. Extraia a política ao final tomando a ação gulosa. Estritamente mais rápido por iteração — sem laço interno de avaliação — mas tipicamente precisa de mais iterações para convergir.

Generalized policy iteration (GPI). O enquadramento unificador. A função de valor e a política estão travadas em um laço de melhoria mútua; qualquer método que direcione ambos para a consistência mútua (iteração de valor assíncrona, iteração de política modificada, Q-learning, actor-critic, PPO) é uma instância de GPI.

Por que γ < 1 é importante. O operador de Bellman é uma γ-contração na norma do supremo: ||T V - T V'||_∞ ≤ γ ||V - V'||_∞. A contração implica ponto fixo único e convergência geométrica. Remova γ < 1 e você perderá a garantia — você precisará de um horizonte finito ou de um estado terminal absorvente.

Construa

Passo 1: construir o modelo MDP GridWorld

Use o mesmo GridWorld 4×4 da Lição 01. Adicionamos uma variante estocástica: com probabilidade 0.1, o agente escorrega para uma direção perpendicular aleatória.

SLIP = 0.1

def transitions(state, action):
    if state == TERMINAL:
        return [(state, 0.0, 1.0)]
    outcomes = []
    for direction, prob in action_probs(action):
        outcomes.append((apply_move(state, direction), -1.0, prob))
    return outcomes

transitions(s, a) retorna a lista de (s', r, p). Este é o modelo completo.

Passo 2: avaliação de política

Dada uma política π(s) = {action: prob}, itere a equação de Bellman até que V pare de mudar:

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = sum(pi_a * sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a))
                   for a, pi_a in policy(s).items())
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

Passo 3: melhoria de política

Substitua π pela política gulosa em relação a V. Se π não mudou, retorne — estamos no ótimo.

def policy_improvement(V, gamma=0.99):
    new_policy = {}
    for s in states():
        best_a = max(
            ACTIONS,
            key=lambda a: sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a)),
        )
        new_policy[s] = best_a
    return new_policy

Passo 4: juntando as partes

def policy_iteration(gamma=0.99):
    policy = {s: "up" for s in states()}   # arbitrary start
    for _ in range(100):
        V = policy_evaluation(lambda s: {policy[s]: 1.0}, gamma)
        new_policy = policy_improvement(V, gamma)
        if new_policy == policy:
            return V, policy
        policy = new_policy

Convergência típica no 4×4: 4–6 iterações externas. Retorna V*(0,0) ≈ -6 e uma política que reduz estritamente a contagem de passos.

Passo 5: iteração de valor (a versão de um único laço)

def value_iteration(gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = max(sum(p * (r + gamma * V[s_prime])
                       for s_prime, r, p in transitions(s, a))
                   for a in ACTIONS)
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            break
    policy = policy_improvement(V, gamma)
    return V, policy

Mesmo ponto fixo, menos linhas de código.

Armadilhas

• Esquecer de tratar os estados terminais. Se você aplicar Bellman a um estado absorvente, ele ainda escolherá uma "melhor ação" que não altera nada. Proteja com if s == terminal: V[s] = 0.
• Convergência de norma do supremo vs L2. Use max |V_new - V|, não a média. A garantia teórica é na norma do supremo.
• Atualizações in-place vs síncronas. Atualizar V[s] in-place (Gauss-Seidel) converge mais rápido do que um dicionário V_new separado (Jacobi). Códigos de produção usam in-place.
• Empates de política. Se duas ações tiverem valores Q iguais, o argmax pode desempatar de forma diferente a cada iteração, fazendo com que a verificação de "política estável" oscile. Use um desempate estável (primeira ação em uma ordem fixa).
• Explosão do espaço de estados. A programação dinâmica é O(|S| · |A|) por varredura. Funciona para até ~10⁷ estados. Além disso, você precisa de aproximação de funções (Fase 9 · 05 em diante).

Use-o

Em 2026, a programação dinâmica é a linha de base de corretude e o laço interno de planejadores:

Toda vez que alguém diz "a função de valor ótima", refere-se ao "ponto fixo da programação dinâmica". Quando vir V* ou Q* em um artigo, imagine este laço.

Envie

Salve como outputs/skill-dp-solver.md:

---
name: dp-solver
description: Solve a small tabular MDP exactly via policy iteration or value iteration. Report convergence behavior.
version: 1.0.0
phase: 9
lesson: 2
tags: [rl, dynamic-programming, bellman]
---

Given an MDP with a known model, output:

1. Choice. Policy iteration vs value iteration. Reason tied to |S|, |A|, γ.
2. Initialization. V_0, starting policy. Convergence sensitivity.
3. Stopping. Sup-norm tolerance ε. Expected number of sweeps.
4. Verification. V*(s_0) computed exactly. Greedy policy extracted.
5. Use. How this baseline will be used to debug/evaluate sampling-based methods.

Refuse to run DP on state spaces > 10⁷. Refuse to claim convergence without a sup-norm check. Flag any γ ≥ 1 on an infinite-horizon task as a guarantee violation.

Exercícios

1. Fácil. Execute a iteração de valor no GridWorld 4×4 com γ ∈ {0.9, 0.99}. Quantas varreduras até que max |ΔV| < 1e-6? Imprima V* como uma grade 4×4.
2. Médio. Compare a iteração de política versus a iteração de valor no GridWorld estocástico (probabilidade de escorregamento de 0.1). Conte: varreduras, tempo de execução real (wall-clock), V*(0,0) final. Qual converge mais rápido em número de iterações? E em tempo de execução real?
3. Difícil. Implemente a iteração de política modificada: na etapa de avaliação, execute apenas k varreduras em vez de ir até a convergência. Plote o erro de V*(0,0) versus k para k ∈ {1, 2, 5, 10, 50}. O que a curva diz a você sobre a relação de compromisso (tradeoff) entre avaliação/melhoria?

Termos-Chave

Leitura Adicional

• Sutton & Barto (2018). Ch. 4 — Dynamic Programming — a apresentação canônica de iteração de política e iteração de valor.
• Bertsekas (2019). Reinforcement Learning and Optimal Control — tratamento rigoroso de argumentos de mapeamento de contração.
• Puterman (2005). Markov Decision Processes — iteração de política modificada e sua análise de convergência.
• Howard (1960). Dynamic Programming and Markov Processes — o artigo original sobre iteração de política.
• Bertsekas & Tsitsiklis (1996). Neuro-Dynamic Programming — a ponte de DP para DP aproximada / RL profundo usada por todas as lições subsequentes.