Iteração de Valor

Visão geral

iteração de valores (value iteration) é um algoritmo clássico de programação dinâmica (dynamic programming) para resolver Processos de Decisão de Markov (Markov Decision Processes) conhecidos (Processos de Decisão de Markov) (MDPs). Dado o modelo de transição (P(s' \mid s,a)) e o modelo de recompensa (R(s,a,s')), a iteração de valores calcula:

• a função de valor de estado ótima (optimal state-value function) (V^*) (retorno esperado a partir de cada estado sob o melhor comportamento possível), e
• uma política ótima (optimal policy) (\pi^*) (um mapeamento de estados para ações ótimas)

aplicando repetidamente backups de otimalidade de Bellman (Bellman optimality backups) até que os valores convirjam.

A iteração de valores é um algoritmo de planejamento (planning algorithm) baseado em modelo (model-based): ela não aprende com a experiência como o aprendizado Q (Q-learning); em vez disso, assume que o MDP é conhecido e realiza backups repetidos para calcular a solução ótima.

Pré-requisitos: MDPs, valores e otimalidade

Um MDP é tipicamente definido por ((\mathcal{S}, \mathcal{A}, P, R, \gamma)), onde:

• (\mathcal{S}): conjunto de estados
• (\mathcal{A}): conjunto de ações (frequentemente (\mathcal{A}(s)) por estado)
• (P(s' \mid s,a)): probabilidades de transição
• (R(s,a,s')): recompensa imediata esperada (às vezes escrita (R(s,a)))
• (\gamma \in [0,1)): fator de desconto (discount factor) (para problemas descontados de horizonte infinito)

A função de valor de estado (state-value function) para uma política (\pi) é: [ V^\pi(s) = \mathbb{E}\pi\left[\sum{t=0}^{\infty} \gamma^t r_{t} \mid s_0=s\right]. ]

A função de valor ótima (optimal value function) é: [ V^*(s) = \max_{\pi} V^\pi(s). ]

A iteração de valores mira (V^*) diretamente, usando a equação de otimalidade de Bellman (Bellman optimality equation).

Backup de otimalidade de Bellman (ideia central)

A equação de otimalidade de Bellman para valores de estado é: [ V^*(s) = \max_{a \in \mathcal{A}(s)} \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V^*(s')\right]. ]

Defina o operador de otimalidade de Bellman (Bellman optimality operator) (T) atuando sobre uma função de valor (V): [ (TV)(s) = \max_{a} \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V(s')\right]. ]

Uma única aplicação (V \leftarrow TV) é chamada de backup de otimalidade de Bellman. A iteração de valores aplica repetidamente esse operador até a convergência.

Regra de atualização da iteração de valores

Iteração de valores síncrona (padrão)

Comece com uma inicialização arbitrária (V_0) (frequentemente tudo zero), depois itere: [ V_{k+1}(s) \leftarrow \max_{a} \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V_k(s')\right] \quad \forall s. ]

Após iterações suficientes, (V_k \to V^*). Uma política ótima pode então ser extraída de forma gulosa: [ \pi^*(s) \in \arg\max_{a} \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V^*(s')\right]. ]

Intuição

• A soma interna calcula o retorno de um passo (one-step return) (recompensa imediata mais o valor descontado do próximo estado).
• O (\max) escolhe a melhor ação assumindo que nos comportaremos de forma ótima a partir daí.
• Repetir isso propaga consequências de longo prazo “para trás” através do espaço de estados.

Algoritmo (pseudocódigo)

Input: states S, actions A, transition P, reward R, discount γ
Initialize V(s) arbitrarily (e.g., 0 for all s)

repeat:
    Δ = 0
    for each state s in S:
        v_old = V(s)
        V(s) = max_a Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ V(s') ]
        Δ = max(Δ, |v_old - V(s)|)
until Δ < θ

Output: V and greedy policy π(s) = argmax_a Σ_{s'} P(s'|s,a) [ R + γ V(s') ]

Aqui, (\theta) é uma pequena tolerância que controla quando parar.

Convergência: quando e por que funciona

Caso descontado de horizonte infinito (\(\gamma < 1\))

No cenário padrão com (|\mathcal{S}|) finito e (\gamma < 1):

• O operador de otimalidade de Bellman (T) é uma (\gamma)-contração ((\gamma)-contraction) na norma do máximo (max norm): [ |TV - TW|\infty \le \gamma |V - W|\infty. ]
• Pelo teorema do ponto fixo de Banach (Banach fixed-point theorem), aplicações repetidas convergem para um ponto fixo único (unique fixed point), que é (V^*): [ V_k \to V^* \text{ as } k \to \infty. ]

Este é um dos principais motivos teóricos pelos quais a iteração de valores é tão confiável em problemas descontados.

Considerações para casos episódicos / caminho estocástico mais curto (\(\gamma = 1\))

Quando (\gamma = 1), a contração não é mais garantida. A iteração de valores ainda pode convergir sob condições adicionais, por exemplo:

• tarefas episódicas (episodic tasks) com estados terminais (terminal states) e políticas que atingem estados terminais com probabilidade 1 (“políticas próprias (proper policies)”), ou
• estrutura de caminho estocástico mais curto (stochastic shortest path) com suposições adequadas (custos, terminação, ausência de ciclos negativos).

Na prática, muitos planejadores mantêm (\gamma < 1) mesmo para problemas episódicos porque isso simplifica a teoria e pode melhorar a estabilidade numérica.

Critérios de parada e garantias de acurácia

Em implementações reais, paramos quando os valores estão “próximos o suficiente” em vez de esperar pela convergência exata.

Critério prático comum (resíduo de Bellman)

Uma regra de parada padrão usa a maior mudança em qualquer estado durante uma iteração: [ \Delta_k = \max_s |V_{k+1}(s) - V_k(s)|. ] Pare quando (\Delta_k < \theta), para uma tolerância escolhida (\theta) (por exemplo, (10^{-6}) a (10^{-3}), dependendo da escala).

Isso é fácil de computar e se correlaciona bem com a convergência.

Relacionando o resíduo à qualidade da política (caso descontado)

Se você parar quando (|V - TV|\infty \le \varepsilon) (isto é, resíduo de Bellman (Bellman residual) pequeno), então (V) está próximo de (V^*). Um limite comumente usado (para (\gamma < 1)) é: [ |V - V^*|\infty \le \frac{\varepsilon}{1-\gamma}. ]

Uma visão mais centrada em política: se você extrair uma política gulosa (greedy policy) (\pi) a partir de uma função de valor aproximada (\hat V), então, sob condições típicas, a política resultante é quase ótima, com subotimalidade escalando como (\frac{\text{erro}}{1-\gamma}). Na prática, quando (\gamma) está próximo de 1, você normalmente precisa de uma tolerância mais estrita porque os erros são amplificados por (\frac{1}{1-\gamma}).

Exemplo resolvido (MDP pequeno)

Considere um MDP minúsculo com dois estados não terminais (A, B) e desconto (\gamma = 0.9).

• De (A):
  • ação (a_1): vai para (B) com recompensa (+5)
  • ação (a_2): permanece em (A) com recompensa (+1)
• De (B):
  • ação (b_1): vai para terminal com recompensa (+2)
  • ação (b_2): vai para (A) com recompensa (0)

Inicialize (V_0(A)=V_0(B)=0).

Iteração 1:

• (V_1(A)=\max{5 + 0.9 V_0(B),; 1 + 0.9 V_0(A)}=\max{5,1}=5)
• (V_1(B)=\max{2 + 0.9\cdot 0,; 0 + 0.9 V_0(A)}=\max{2,0}=2)

Iteração 2:

• (V_2(A)=\max{5 + 0.9\cdot V_1(B),; 1 + 0.9\cdot V_1(A)}) (=\max{5+1.8,; 1+4.5}=\max{6.8,5.5}=6.8)
• (V_2(B)=\max{2,; 0 + 0.9\cdot V_1(A)}=\max{2,4.5}=4.5)

Podemos ver que os valores se propagam rapidamente: (B) se torna valioso porque pode retornar a (A), que por sua vez pode obter (+5) indo para (B).

Após a convergência, uma política gulosa escolherá:

• em (A): ação (a_1) (ir para (B))
• em (B): ação (b_2) (ir para (A)) a menos que a ação terminal se torne melhor dependendo dos valores finais no ponto fixo.

Este exemplo ilustra que a iteração de valores lida naturalmente com loops e consequências de longo prazo via backups repetidos.

Implementação prática (estilo Python)

Abaixo está uma implementação síncrona direta para MDPs finitos com um modelo de transição esparso.

import math

def value_iteration(states, actions, P, R, gamma=0.99, theta=1e-6):
    """
    states: iterable of states
    actions(s): function returning iterable of actions available in state s
    P[s][a]: list of (s_next, prob)
    R[s][a][s_next]: reward for transition s --a--> s_next (or use a function)
    """
    V = {s: 0.0 for s in states}

    while True:
        delta = 0.0
        for s in states:
            v_old = V[s]
            best = -math.inf
            for a in actions(s):
                q = 0.0
                for s_next, p in P[s][a]:
                    q += p * (R[s][a][s_next] + gamma * V[s_next])
                best = max(best, q)
            V[s] = best
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            break

    # greedy policy extraction
    policy = {}
    for s in states:
        best_a, best = None, -math.inf
        for a in actions(s):
            q = 0.0
            for s_next, p in P[s][a]:
                q += p * (R[s][a][s_next] + gamma * V[s_next])
            if q > best:
                best = q
                best_a = a
        policy[s] = best_a

    return V, policy

Detalhes comuns de implementação

• Estados terminais: Tipicamente, define-se (V(\text{terminal}) = 0) e ou se pula a atualização para estados terminais ou se dá a eles apenas uma ação nula.
• Transições esparsas: Armazene apenas transições com probabilidade não nula; a complexidade escala com o número de arestas em vez de (|S|^2).
• Escalonamento numérico: Magnitudes de recompensa afetam fortemente quão estrito seu (\theta) deve ser.

Variantes e melhorias de engenharia

Iteração de valores assíncrona (no lugar)

Em vez de calcular (V_{k+1}) a partir de uma cópia congelada (V_k), você pode atualizar valores no lugar (in-place) conforme percorre os estados. Isso pode convergir mais rápido na prática e usa menos memória. A convergência ainda vale sob suposições padrão se todo estado for atualizado infinitas vezes.

Varredura priorizada (ideia)

Em MDPs grandes e esparsos, nem todos os estados mudam igualmente. A varredura priorizada (prioritized sweeping) mantém uma fila de prioridade de estados cujo erro de Bellman é grande e os atualiza primeiro, muitas vezes reduzindo bastante o número de backups necessários.

Programação dinâmica em tempo real (RTDP)

A programação dinâmica em tempo real (Real-time dynamic programming), ou RTDP, foca o cálculo em estados alcançáveis a partir de uma distribuição inicial, em vez de varrer todos os estados. Isso é útil quando (|S|) é enorme, mas apenas um subconjunto importa para uma tarefa específica.

Relação com iteração de políticas

A Iteração de Políticas (Policy Iteration) é outro método de controle por programação dinâmica. Ela alterna:

1. Avaliação de política (policy evaluation): computar (V^\pi) para a política atual (\pi)
2. Melhoria de política (policy improvement): definir (\pi \leftarrow \text{gulosa}(V^\pi))

A iteração de valores pode ser vista como uma forma de iteração generalizada de políticas (generalized policy iteration) em que:

• você não avalia completamente uma política até a convergência
• em vez disso, você aplica backups de otimalidade diretamente, efetivamente mesclando avaliação e melhoria

Uma comparação útil:

• Iteração de políticas: menos passos de melhoria, mas cada passo pode exigir muitas iterações de avaliação (ou resolver equações lineares).
• Iteração de valores: muitas iterações baratas, cada uma um simples backup de otimalidade de Bellman.

Na prática:

• A iteração de políticas pode convergir em menos iterações externas, especialmente em problemas pequenos.
• A iteração de valores costuma ser mais simples e pode ser mais amigável em memória e implementação.

Relação com iteração de valores de Q (e aprendizado Q)

Iteração de valores de Q (programação dinâmica em \(Q\))

Em vez de manter (V(s)), você pode manter valores de ação (action-values) (Q(s,a)) e aplicar o backup de otimalidade de Bellman: [ Q_{k+1}(s,a) \leftarrow \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma \max_{a'} Q_k(s',a')\right]. ]

Então: [ V(s) = \max_a Q(s,a), \quad \pi(s) \in \arg\max_a Q(s,a). ]

Isso às vezes é chamado de iteração de Q (Q-iteration) ou iteração de valores de Q e é o análogo, em programação dinâmica baseada em modelo, de métodos sem modelo.

Contraste com aprendizado Q (sem modelo)

O aprendizado Q usa transições amostradas (sampled transitions) ((s,a,r,s')) para atualizar: [ Q(s,a) \leftarrow Q(s,a) + \alpha \left(r + \gamma \max_{a'}Q(s',a') - Q(s,a)\right), ] sem precisar de (P) ou (R). A iteração de valores, por outro lado, assume que você conhece toda a dinâmica e calcula backups esperados somando sobre (s').

Complexidade e quando a iteração de valores é apropriada

Custo computacional

Para iteração de valores síncrona, cada varredura (sweep) custa aproximadamente:

• (O\left(\sum_{s} \sum_{a} \text{nnz}(P(\cdot\mid s,a))\right))

Em MDPs tabulares densos, isso frequentemente é simplificado para:

• (O(|S|^2|A|)) por iteração

O número de iterações depende de (\gamma) e da acurácia desejada; à medida que (\gamma \to 1), a convergência desacelera porque o fator de contração enfraquece.

Quando ela se destaca

A iteração de valores é uma escolha forte quando:

• O MDP é conhecido (você tem um simulador/modelo que pode consultar de forma exaustiva, ou uma tabela de transição explícita).
• O espaço de estados é pequeno o suficiente para representar (V(s)) (configuração tabular (tabular setting)).
• Você precisa de um planejador (planner) de base confiável, por exemplo, para:
  • navegação em gridworld e planejamento de caminho mais curto
  • problemas de decisão no estilo de pesquisa operacional
  • computar comportamento ótimo em jogos pequenos ou ambientes simplificados
  • fornecer alvos ou benchmarks para métodos de Aprendizado Profundo por Reforço (Deep Reinforcement Learning)

Quando ela tem dificuldades

• Espaços de estados muito grandes ou contínuos ( (V) tabular inviável)
• Dinâmicas desconhecidas (prefira métodos sem modelo (model-free), ou aprenda um modelo)
• (\gamma) extremamente próximo de 1 e necessidade de otimalidade muito estrita (convergência lenta)

Em cenários de grande escala, a iteração de valores frequentemente é combinada com aproximação de funções (function approximation) (programação dinâmica aproximada (approximate dynamic programming)), embora garantias clássicas de convergência geralmente deixem de valer sem restrições adicionais.

Armadilhas comuns

• Tratamento incorreto de estados terminais: Se os valores terminais não forem fixos (frequentemente 0) ou as transições não forem definidas com cuidado, backups podem produzir valores errados.
• Parar cedo demais quando (\gamma) é alto: Com (\gamma=0.99), resíduos pequenos importam mais porque (\frac{1}{1-\gamma}=100).
• Escalonamento de recompensas: Recompensas grandes podem tornar os valores grandes; escolha (\theta) relativo à magnitude das recompensas.
• Empates de ação: Múltiplas ações ótimas podem existir; use um critério de desempate estável se reprodutibilidade for importante.

Resumo

A iteração de valores é um algoritmo fundamental de programação dinâmica para resolver MDPs conhecidos aplicando repetidamente backups de otimalidade de Bellman:

• Regra de atualização: [ V_{k+1}(s) = \max_{a} \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V_k(s')\right] ]
• Convergência: Garantida para MDPs finitos com (\gamma<1) porque o operador de otimalidade de Bellman é uma contração.
• Parada: Use a maior mudança por varredura ou o resíduo de Bellman; tolerâncias mais estritas são necessárias à medida que (\gamma \to 1).
• Extração de política: Tome a ação gulosa em relação ao (V) convergido.
• Relações:
  • Em comparação com a Iteração de Políticas, a iteração de valores intercala avaliação e melhoria via backups de otimalidade.
  • A iteração de valores de Q aplica backups análogos a (Q(s,a)); o aprendizado Q é seu contraparte sem modelo e baseado em amostras.

Como resultado, a iteração de valores permanece um método de referência central no aprendizado por reforço (reinforcement learning) — tanto como um planejador prático para pequenos problemas conhecidos quanto como uma ponte conceitual para métodos aproximados e sem modelo mais avançados.

---