Iteração de Políticas

A iteração de política é um método clássico de controle por programação dinâmica (dynamic programming, DP) para resolver um Processo de Decisão de Markov (MDP) conhecido. Ela encontra uma política ótima alternando repetidamente entre:

1. Avaliação de política: calcular a função de valor (V^\pi) para a política atual (\pi)
2. Melhoria de política: atualizar a política para ser gananciosa (greedy) em relação a essa função de valor

No cenário tabular (estados/ações finitos, expectativas exatas a partir de um modelo conhecido), a iteração de política tem fortes garantias de convergência e é uma pedra angular para entender algoritmos modernos de aprendizado por reforço, incluindo a ideia mais ampla de iteração de política generalizada (generalized policy iteration, GPI).

Contexto: MDPs, políticas e funções de valor

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

• (\mathcal{S}): conjunto finito de estados
• (\mathcal{A}): conjunto finito de ações
• (P(s' \mid s, a)): probabilidade de transição para o próximo estado (s')
• (R(s,a)) (ou (R(s,a,s'))): recompensa imediata esperada
• (\gamma \in [0,1)): fator de desconto (para tarefas contínuas; tarefas episódicas podem ser tratadas de forma semelhante sob suposições padrão)

Uma política (estacionária) (\pi(a \mid s)) mapeia estados para uma distribuição sobre ações.

A função de valor de estado da política (\pi) é:

[ V^\pi(s) = \mathbb{E}\pi\left[\sum{t=0}^\infty \gamma^t r_{t} ,\middle|, s_0=s\right] ]

A função de valor de ação é:

[ Q^\pi(s,a) = \mathbb{E}\pi\left[\sum{t=0}^\infty \gamma^t r_{t} ,\middle|, s_0=s, a_0=a\right] ]

O objetivo do controle é encontrar uma política ótima (\pi^*) que satisfaça (V^{\pi^*}(s) = V^*(s)) para todos os estados.

A ideia da iteração de política

A iteração de política operacionaliza um loop simples:

• Se você sabe o quão boa é sua política atual (avaliação),
• você pode melhorá-la localmente agindo de forma gananciosa em relação ao seu valor (melhoria),
• e repetir isso deve eventualmente chegar a uma política ótima.

Isso está intimamente ligado a dois operadores de Bellman:

• Operador de expectativa de Bellman (Bellman expectation operator) para uma política fixa (\pi): avalia (V^\pi)
• Operador de otimalidade de Bellman (Bellman optimality operator): define a otimalidade e fundamenta a Iteração de Valor

A iteração de política usa o operador de expectativa para avaliação e, em seguida, usa um passo ganancioso que se move em direção ao operador de otimalidade.

Passo 1: Avaliação de política (calcular \(V^\pi\))

Equação de expectativa de Bellman

Para uma política fixa (\pi), (V^\pi) é a solução única de:

[ 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] ]

Há duas formas tabulares comuns de calculá-la.

(A) Avaliação exata de política (resolver um sistema linear)

Em forma matricial:

[ V^\pi = R^\pi + \gamma P^\pi V^\pi \quad \Rightarrow \quad (I - \gamma P^\pi)V^\pi = R^\pi ]

Então:

[ V^\pi = (I - \gamma P^\pi)^{-1} R^\pi ]

Isso é “exato”, mas pode ser caro para (|\mathcal{S}|) grande (inversão de matriz é aproximadamente (O(|\mathcal{S}|^3)) de forma ingênua).

(B) Avaliação iterativa de política (backups repetidos de Bellman)

Inicialize (V_0(s)) arbitrariamente (frequentemente com zeros), então itere:

[ V_{k+1}(s) \leftarrow \sum_a \pi(a\mid s)\sum_{s'} P(s'\mid s,a)\left[R(s,a,s') + \gamma V_k(s')\right] ]

Pare quando a mudança máxima for pequena:

[ \max_s |V_{k+1}(s) - V_k(s)| < \theta ]

Como o operador de expectativa de Bellman é uma contração (contraction) quando (\gamma<1), essa iteração converge para (V^\pi).

Na prática, a avaliação iterativa costuma ser preferida porque evita resolver grandes sistemas lineares e pode ser feita com varreduras parciais, atualizações assíncronas, etc.

Passo 2: Melhoria de política (tornar \(\pi\) gananciosa em relação a \(V^\pi\))

Depois de obter (V^\pi), defina uma nova política (\pi') que escolhe ações que maximizam a projeção de um passo à frente (one-step lookahead) usando (V^\pi):

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

A quantidade que está sendo maximizada é exatamente (Q^\pi(s,a)) calculado via projeção de um passo à frente:

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

Assim, a melhoria pode ser declarada de forma simples:

• Calcular (Q^\pi(s,a)) a partir de (V^\pi)
• Atualizar a política para escolher (\arg\max_a Q^\pi(s,a))

Teorema de Melhoria de Política (intuição)

Um resultado teórico fundamental é:

Se (\pi') é gananciosa em relação a (V^\pi), então (V^{\pi'}(s) \ge V^\pi(s)) para todo (s).
Se a política muda em pelo menos um estado e empates são tratados adequadamente, a melhoria é estrita em pelo menos um estado.

Intuitivamente, (V^\pi) informa o valor de longo prazo dos estados assumindo que você seguirá (\pi) a partir dali. O passo de melhoria gananciosa escolhe, em cada estado, a ação que leva à melhor recompensa imediata mais o valor descontado do próximo estado (medido por (V^\pi)). Isso não pode piorar a situação, porque a própria (\pi) era uma das opções que você poderia continuar escolhendo.

Algoritmo completo de iteração de política (tabular)

Pseudocódigo

Initialize policy π0 (e.g., random)
Repeat for k = 0,1,2,...

  1) Policy Evaluation:
     Compute Vk = V^{πk}
     (exact via linear solve, or iterative until convergence threshold θ)

  2) Policy Improvement:
     For each state s:
        π_{k+1}(s) ← argmax_a Σ_{s'} P(s'|s,a)[ R(s,a,s') + γ Vk(s') ]

Until π_{k+1} = π_k (policy stable)

Return π_k

Critérios práticos de parada

Escolhas comuns incluem:

• Estabilidade da política: parar quando a política não muda mais
• Avaliação aproximada: parar a avaliação quando (|V_{k+1}-V_k|_\infty < \theta)
• Máximo de iterações: limitar o número de varreduras de avaliação por passo de melhoria (isso se torna iteração de política modificada (modified policy iteration), discutida abaixo)

Garantias de convergência e intuição (cenário tabular)

A iteração de política é especialmente bem-comportada no caso tabular com modelo conhecido.

Por que ela converge

1. A avaliação é bem definida: Para uma (\pi) fixa, o operador de expectativa de Bellman tem um ponto fixo único (V^\pi) (sob condições padrão, como (\gamma<1) para tarefas contínuas).
2. A melhoria é monotônica: A melhoria gananciosa de política produz uma política (\pi') tal que (V^{\pi'} \ge V^\pi) (Teorema de Melhoria de Política).
3. Número finito de políticas: Com (|\mathcal{S}|) e (|\mathcal{A}|) finitos, há apenas um número finito de políticas determinísticas. Se cada iteração melhora estritamente (a menos que já seja ótima), o processo deve terminar em um número finito de passos.

Quando ela para, e por que o resultado é ótimo?

A iteração de política para quando a política é estável: o passo de melhoria não faz alterações. Nesse caso, a política atual (\pi) é gananciosa em relação à sua própria função de valor (V^\pi). Isso implica que ela satisfaz as condições de otimalidade de Bellman e, portanto, (\pi) é ótima.

A avaliação aproximada ainda funciona (com ressalvas)

Na prática, frequentemente fazemos avaliação inexata (paramos cedo). Isso gera uma família de algoritmos entre iteração de política e iteração de valor. No cenário tabular de DP, usando avaliação suficientemente precisa e melhoria padrão, ainda se converge para a otimalidade, embora a afirmação mais “limpa” de “término finito” seja para avaliação exata.

Exemplo: iteração de política em um pequeno Gridworld

Considere um Gridworld com:

• estados = células da grade
• ações = {cima, baixo, esquerda, direita}
• recompensa = (-1) por passo, (0) em um objetivo terminal
• transições majoritariamente determinísticas (ou “escorregão” estocástico)

Uma execução típica de iteração de política se parece com:

1. Começar com uma política aleatória (por exemplo, uniforme sobre ações).
2. A avaliação de política propaga custos de longo prazo: estados longe do objetivo ficam com valores mais negativos porque são necessários mais passos para terminar.
3. A melhoria de política atualiza cada célula para escolher a ação que reduz o número esperado de passos até o objetivo (isto é, move “ladeira abaixo” no relevo da função de valor).
4. Após algumas iterações, a política se torna a política de caminho mais curto (ou próxima disso se as transições forem estocásticas).

Mesmo sem calcular caminhos mais curtos explicitamente, a iteração de política os recupera porque as equações de Bellman codificam a mesma estrutura: “tome a ação que leva ao melhor valor do próximo estado”.

Esboço mínimo de implementação tabular (baseado em modelo)

Abaixo está um esboço compacto em estilo Python assumindo que você já tem o modelo (P(s'|s,a)) e a recompensa esperada (R(s,a,s')) disponíveis (para MDPs pequenos, isso frequentemente é armazenado como arrays).

import numpy as np

def policy_iteration(P, R, gamma=0.99, theta=1e-8):
    """
    P: shape [S, A, S] transition probabilities
    R: shape [S, A, S] rewards
    """
    S, A, _ = P.shape
    pi = np.random.randint(A, size=S)      # deterministic policy
    V = np.zeros(S)

    while True:
        # Policy evaluation (iterative)
        while True:
            delta = 0.0
            for s in range(S):
                a = pi[s]
                v_new = np.sum(P[s, a, :] * (R[s, a, :] + gamma * V))
                delta = max(delta, abs(v_new - V[s]))
                V[s] = v_new
            if delta < theta:
                break

        # Policy improvement
        policy_stable = True
        for s in range(S):
            old_a = pi[s]
            q = np.zeros(A)
            for a in range(A):
                q[a] = np.sum(P[s, a, :] * (R[s, a, :] + gamma * V))
            pi[s] = np.argmax(q)
            if pi[s] != old_a:
                policy_stable = False

        if policy_stable:
            return pi, V

Isso captura a mecânica central usada em muitos exemplos de DP em livros-texto.

Relação com iteração de valor e iteração de política generalizada

Iteração de política vs. iteração de valor

A Iteração de Valor aplica diretamente o backup de otimalidade de Bellman:

[ V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s'\mid s,a)\left[R(s,a,s') + \gamma V_k(s')\right] ]

Você pode ver a iteração de valor como uma forma de iteração de política com avaliação truncada:

• Iteração de política: avaliar a política atual “até o fim” (ou quase), e então melhorar
• Iteração de valor: fazer um (ou um pequeno número de) backups de otimalidade a cada iteração, movendo-se implicitamente em direção a uma política gananciosa

Trade-off:

• Iteração de política: menos iterações externas, mas cada iteração pode ser cara (avaliação)
• Iteração de valor: iterações mais baratas, mas pode exigir muitas mais iterações para convergir

Iteração de política modificada (ponte entre as duas)

Um meio-termo muito comum é a iteração de política modificada (modified policy iteration):

• fazer um número limitado de varreduras de avaliação (por exemplo, 1–10) em vez de convergir completamente
• depois fazer melhoria de política

Isso frequentemente funciona bem na prática e torna explícita a conexão entre PI e VI.

Iteração de Política Generalizada (GPI)

A iteração de política generalizada (generalized policy iteration, GPI) é uma estrutura conceitual: manter alguma aproximação de uma política e de uma função de valor, e permitir que processos do tipo avaliação e do tipo melhoria interajam — possivelmente simultaneamente, não em fases estritamente alternadas.

• A iteração de política é a instância “limpa” de DP da GPI (avaliação exata, melhoria gananciosa).
• Muitos métodos de RL são instâncias aproximadas de GPI:
  • Q-learning: a melhoria é guiada por uma estimativa em evolução dos valores de ação (off-policy)
  • Métodos Ator-Crítico: um crítico estima valores enquanto um ator melhora a política
  • Gradientes de Política: a “melhoria” é feita por ascensão de gradiente em vez de (\arg\max) ganancioso
  • Aprendizado por Reforço Profundo: usa aproximação de função em vez de tabelas

Pensar em termos de GPI ajuda a unificar planejamento (DP) e aprendizado (RL sem modelo): ambos tentam acoplar estimação de valor com melhoria de política.

Aplicações práticas e quando a iteração de política é usada

A iteração de política é mais diretamente aplicável quando você tem um modelo conhecido e tratável:

• Pesquisa operacional / planejamento: controle de estoque, escalonamento, modelos de filas
• Robótica (pequenas abstrações discretas): planejamento sobre espaços de estados discretizados
• IA para jogos (MDPs pequenos): computação de políticas para ambientes simplificados
• Educação e depuração: como um algoritmo “padrão-ouro” em domínios pequenos

Em problemas de grande escala, a PI tabular exata frequentemente é inviável porque:

• (|\mathcal{S}|) é enorme ou contínuo
• o modelo de transição (P) é desconhecido
• armazenar e atualizar (V) para todos os estados é caro demais

No entanto, a estrutura da iteração de política ainda importa: muitos algoritmos escaláveis são melhor compreendidos como iteração de política aproximada (approximate policy iteration, API), em que avaliação e melhoria são feitas de forma aproximada usando amostragem e aproximação de função.

Considerações de implementação e armadilhas comuns

Requisito de modelo (planejamento vs aprendizado)

A iteração de política clássica é um algoritmo de planejamento: ela assume que você consegue calcular expectativas sob (P(s'|s,a)). Se você só tem experiência amostrada, normalmente você migra para métodos TD (por exemplo, Q-learning) ou para avaliação aproximada via rollouts.

Desempate e políticas estocásticas

Se múltiplas ações maximizam o critério ganancioso, você pode:

• escolher uma regra determinística de desempate (comum)
• ou definir uma política gananciosa estocástica que divide probabilidade entre os maximizadores

O desempate afeta qual política ótima você obtém (pode haver várias), mas não a otimalidade.

Custo da avaliação

• Avaliação exata: cara, porém precisa.
• Avaliação iterativa: flexível; pode parar cedo.
• Avaliação assíncrona: atualizar estados in-place ou em ordens priorizadas para acelerar a convergência.

Riscos com aproximação de função

Com aproximadores de função não lineares (por exemplo, redes neurais), “avaliação de política + melhoria gananciosa” não é garantidamente estável. A iteração de política aproximada pode oscilar ou divergir sem estrutura adicional (regularização, regiões de confiança, atualizações conservadoras de política, etc.). Muitos métodos de RL profundo podem ser vistos como adicionando tais estabilizadores.

Resumo

A iteração de política é um algoritmo fundamental de controle por DP para resolver MDPs tabulares alternando entre:

• Avaliação de política para calcular (V^\pi)
• Melhoria de política para tornar (\pi) gananciosa em relação à função de valor avaliada

No cenário tabular com modelo conhecido, ela fornece melhoria monotônica e converge para uma política ótima (frequentemente em um número finito de melhorias). Conceitualmente, ela está ao lado da Iteração de Valor e é um exemplo canônico de Iteração de Política Generalizada, que também fundamenta muitos algoritmos modernos de aprendizado por reforço.