Phase 09: Reinforcement Learning

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

Type: Build

Languages: Python

Prerequisites: Phase 9 · 01 (MDPs)

Time: ~75 minutes

O problema

Você tem um MDP com um modelo conhecido: você pode consultar P(s' | s, a)E ...R(s, a, s')Um gerente de estoque conhece a distribuição da demanda. um jogo de tabuleiro tem transições deterministas. um mundo de grade é quatro linhas de Python. você tem um modelo.

O RL livre de modelos (Q-learning, PPO, REINFORCE) foi inventado para o caso em que você não tem um modelo você só pode sampler do ambiente. Mas quando você tem um, há métodos mais rápidos e melhores: programação dinâmica. Bellman os projetou em 1957. Eles ainda definem a corretão: quando as pessoas dizem "política ideal para este MDP", eles querem dizer que a política DP retornaria.

Os dados são necessários para 2026 por três razões: primeiro, cada ambiente tabular na pesquisa RL (GridWorld, FrozenLake, CliffWalking) é resolvido com DP para produzir a política padrão de ouro.V*(s_0)Terceiro, os modernos métodos de RL offline e planejamento (MCTS, pesquisa do AlphaZero, RL baseado em modelo na Fase 9 · 10) todos iteram um backup Bellman sobre um modelo aprendido ou dado.

O conceito

!Policy iteration and value iteration, side by side

Two algorithms, both fixed-point iteration on Bellman.

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

1. Evaluation: dada política π, computação V^πatravés da aplicação repetida V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')]Até que converja.
2. Melhoria: dada V^π, fazerπganancioso W.R.T.V^π- Não .π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]- Não .

A convergência é garantida porque (a) cada etapa de melhoria mantém πAumento do número de pessoas em situação de riscoV^πPara alguns estados, (b) o espaço das políticas deterministas é finito. geralmente converge em ~ 520 iterações externas mesmo para grandes espaços de estado.

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

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

Repita até max_s |V_{new}(s) - V(s)| < ε. Extrair a política no final tomando a ação gananciosa. Estritamente mais rápido por iteração nenhum loop de avaliação interna mas normalmente precisa de mais iterações para convergir.

Generalized policy iteration (GPI).A estrutura unificadora. Função de valor e política estão bloqueadas em um loop de melhoria bidirecional; qualquer método que conduza ambos para a consistência mútua (iteração de valor assíncrona, iteração de política modificada, Q-learning, ator-crítica, PPO) é uma instância de GPI.

Why γ < 1 matters.O operador Bellman é umγ- contracção na norma-sup: ||T V - T V'||_∞ ≤ γ ||V - V'||_∞A contração implica um ponto fixo único e uma convergência geométrica.γ < 1E se perder a garantia, precisa de um horizonte finito ou um estado terminal de absorção.

Construí-lo

Passo 1: construir o modelo GridWorld MDP

Usar o mesmo 4x4 GridWorld da lição 01. Adicionamos uma variante estocástica: com probabilidade 0.1O agente desliza numa direcção perpendicular aleatória.

pythonCopySLIP = 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 uma lista de (s', r, p)Este é o modelo inteiro.

Passo 2: Avaliação das políticas

Dado uma política π(s) = {action: prob}, iterar a equação de Bellman até VParou de se mover:

pythonCopydef 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 das políticas

SubstituiπCom a política gananciosa W.R.T.VSe ...πNão mudou, retorno estamos no óptimo.

pythonCopydef 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: Conectar-os

pythonCopydef 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 em 4×4: 46 iterações externas.V*(0,0) ≈ -6E uma política que reduz rigorosamente a contagem de passos.

Passo 5: Iteração de valor (versão de um ciclo)

pythonCopydef 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

O mesmo ponto fixo, menos linhas de código.

Encurralagens

• Forgetting to handle terminals.Se aplicarmos o Bellman a um estado de absorção, ele ainda capta uma "melhor ação" que não muda nada.if s == terminal: V[s] = 0- Não .
• Sup-norm vs L2 convergence.Utilizaçãomax |V_new - V|A garantia teórica está na sup-norma.
• In-place vs synchronous updates.AtualizaçãoV[s]O sistema de concentração de gases em local (Gauss-Seidel) converge mais rapidamente do que um sistema de concentração separado.V_newO código de produção usa o local.
• Policy ties.Se duas ações tiverem o mesmo valor Q,argmaxA primeira ação em ordem fixa é a de uma relação de separação estável.
• State-space explosion.DP éO(|S| · |A|)Para a análise, a função é estimada em cerca de 107.

Usá-lo

Em 2026, o DP é a linha de base de correcção e o ciclo interno dos planejadores:

Sempre que alguém diz "a função de valor ideal", eles querem dizer "o ponto fixo DP".Vou Qnum jornal, imaginem este ciclo.

Envia-o

Salva comooutputs/skill-dp-solver.md- Não .

markdownCopy---
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. Easy.Execute iteração de valor no 4×4 GridWorld com γ ∈ {0.9, 0.99}Quantos baralhos atémax |ΔV| < 1e-6ImpressãoV*como uma grade 4x4.
2. Medium.Compare iteração de política vs iteração de valor no GridWorld stochastic (probabilidade de deslize 0.1Contar: varreduras, tempo de relógio de parede, final V*(0,0)O que converge mais rápido em iterações?
3. Hard.Construir iteração de política modificada: na fase de avaliação, executar apenas k- Esvaziam em vez de convergirem.V*(0,0)erro vs kParak ∈ {1, 2, 5, 10, 50}O que diz a curva sobre a compensação entre avaliação e melhoria?

Termos-chave

Mais leitura

• Sutton & Barto (2018). Ch. 4 — Dynamic Programming a apresentação canónica da iteração de políticas e da iteração de valores.
• Bertsekas (2019). Reinforcement Learning and Optimal Control tratamento rigoroso dos argumentos de mapeamento de contracção.
• Puterman (2005). Markov Decision Processes a iteração da política modificada e a sua análise de convergência.
• Howard (1960). Dynamic Programming and Markov Processes o documento original de iteração da política.
• Bertsekas & Tsitsiklis (1996). Neuro-Dynamic Programming a ponte de DP a aproximadamente-DP / profunda RL utilizada em cada aula subsequente.

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.