Iteração Generalizada de Políticas

Visão geral

Iteração Generalizada de Políticas (Generalized Policy Iteration, GPI) é uma forma unificadora de entender a maioria dos algoritmos de controle em aprendizado por reforço (reinforcement learning, RL). Ela descreve aprendizado e planejamento como a interação contínua entre dois processos acoplados:

Avaliação de política (policy evaluation): estimar quão boa é a política (policy) atual (via uma função de valor (value function)).
Melhoria de política (policy improvement): mudar a política para que ela seja melhor de acordo com as estimativas de valor atuais.

Algoritmos clássicos de programação dinâmica (dynamic programming, DP) (como Iteração de Políticas e Iteração de Valor) alternam esses passos de maneira limpa, em “lotes” (batch). A GPI generaliza esse quadro: avaliação e melhoria podem ser intercaladas, aproximadas e assíncronas — e, ainda assim, tendem a conduzir o comportamento rumo à optimalidade em muitos cenários.

Essa perspectiva explica por que métodos que parecem muito diferentes na superfície — como Aprendizado por Diferença Temporal (Temporal-Difference, TD), Aprendizado Q (Q-learning) e Métodos Ator–Crítico (Actor-Critic Methods) — podem todos ser vistos como instâncias do mesmo ciclo subjacente.

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

Assumimos um Processo de Decisão de Markov (Markov Decision Process, MDP) com:

estados (s \in \mathcal{S})
ações (a \in \mathcal{A})
dinâmica de transição (p(s' \mid s,a))
recompensa (r(s,a)) (ou (r(s,a,s')))
fator de desconto (\gamma \in [0,1))

Uma política (policy) (\pi(a \mid s)) define o comportamento. Duas funções de valor principais:

Valor de estado (state-value):
[ v_\pi(s) = \mathbb{E}\pi\left[\sum{t=0}^\infty \gamma^t R_{t+1} \mid S_0=s\right] ]
Valor de ação (action-value):
[ q_\pi(s,a) = \mathbb{E}\pi\left[\sum{t=0}^\infty \gamma^t R_{t+1} \mid S_0=s, A_0=a\right] ]

O controle busca uma política ótima (optimal policy) (\pi^) que atinja (v^(s) = \max_\pi v_\pi(s)) (e, de forma análoga, (q^*)).

Os dois operadores: avaliação e melhoria

A GPI é mais fácil de expressar usando operadores de Bellman (Bellman operators).

Avaliação de política (atualização por expectativa de Bellman) (Bellman expectation backup)

Para uma (\pi) fixa, a equação de expectativa de Bellman (Bellman expectation equation) é:

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

Defina o operador de expectativa de Bellman (Bellman expectation operator) (T^\pi):

[ (T^\pi v)(s) = \sum_a \pi(a\mid s)\sum_{s'} p(s'\mid s,a)\left[r + \gamma v(s')\right] ]

Então (v_\pi) é o único ponto fixo: (v_\pi = T^\pi v_\pi). Em MDPs finitos tabulares (tabular) com (\gamma<1), (T^\pi) é um mapeamento de contração (contraction mapping), o que fornece fortes garantias de convergência.

Melhoria de política (gulosificação) (greedification)

Dada uma estimativa de valor, podemos melhorar a política sendo guloso (greedy) em relação a ela. Se tivermos (q_\pi), um passo típico de melhoria é:

[ \pi'(s) \in \arg\max_a q_\pi(s,a) ]

Ou, se tivermos apenas (v_\pi), calculamos uma antecipação de um passo:

[ q_\pi(s,a) = \sum_{s'} p(s'\mid s,a)\left[r + \gamma v_\pi(s')\right] ]

Um teorema central (teorema de melhoria de política) diz: se (\pi') é gulosa em relação a (q_\pi), então (v_{\pi'}(s) \ge v_\pi(s)) para todo (s).

Algoritmos clássicos como casos especiais

Iteração de Políticas (PI): alternar até convergir

Iteração de Políticas repete:

Avaliar (\pi_k) até que (v_{\pi_k}) seja (essencialmente) exato.
Melhorar: (\pi_{k+1} \leftarrow \text{Greedy}(v_{\pi_k}))

Isso é “limpo”, mas caro: a avaliação exata pode exigir resolver sistemas lineares ou muitas varreduras.

Iteração de Valor (VI): avaliação mínima por melhoria

Iteração de Valor pode ser vista como executar uma atualização de avaliação antes de melhorar novamente:

[ v_{k+1}(s) \leftarrow \max_a \sum_{s'} p(s'\mid s,a)\left[r + \gamma v_k(s')\right] ]

Isso usa o operador de otimalidade de Bellman (Bellman optimality operator) (T^*), que também é uma contração no caso tabular com desconto. A iteração de valor intercala avaliação e melhoria de forma estreita: cada atualização tanto avalia quanto melhora.

O que a torna “generalizada”?

A GPI relaxa suposições feitas pela iteração de políticas e pela iteração de valor:

Avaliação aproximada (approximate evaluation): as estimativas de valor podem ser ruidosas, enviesadas ou atualizadas apenas parcialmente.
Atualizações assíncronas (asynchronous updates): nem todos os estados são atualizados a cada varredura; atualizações podem acontecer onde a experiência ocorre.
Intercalação (interleaving): a melhoria pode acontecer antes que a avaliação tenha convergido.
Atualizações baseadas em amostras (sample-based backups): em vez de expectativas completas (programação dinâmica), usar amostras (aprendizado por reforço sem modelo (model-free RL)).

Em outras palavras, a GPI descreve a realidade de aprender a partir de dados, em que você atualiza o que consegue, quando consegue, e ainda assim avança em direção a um comportamento melhor.

Um esboço genérico:

Initialize policy π and value estimates (v or q)
Loop:
    (Policy evaluation)   Update value estimates toward values under π
                          (possibly with sampling, bootstrapping, partial/asynchronous updates)
    (Policy improvement)  Adjust π to be (more) greedy w.r.t. current value estimates
                          (possibly softly, e.g., ε-greedy or policy-gradient step)

O ponto crucial: avaliação e melhoria formam um ciclo de realimentação (feedback loop). Políticas melhores mudam a distribuição dos dados; estimativas de valor melhores permitem melhorias melhores.

Um exemplo concreto: mundo em grade com atualizações incrementais

Imagine uma tarefa de navegação em um mundo em grade (gridworld). Com a iteração de políticas clássica, você poderia:

computar (v_\pi) para todos os estados (muitas varreduras),
então atualizar a política em toda parte.

Em um cenário online (online RL setting), você normalmente vivencia apenas um pequeno subconjunto de estados por episódio (episode). Uma abordagem no estilo GPI faria:

atualizar estimativas de valor apenas para estados visitados (assíncrono),
ocasionalmente (ou continuamente) atualizar a política para ser mais gulosa em relação às estimativas atuais.

Por exemplo, com uma política (\varepsilon)-gulosa ((\varepsilon)-greedy) sobre um (Q(s,a)) aprendido:

a avaliação é feita por atualizações de TD (TD updates) em (Q),
a melhoria é “implícita” porque o comportamento se torna mais guloso conforme (Q) muda (ou conforme (\varepsilon) decai).

Isto é a GPI em ação: você nunca “termina” totalmente a avaliação antes de melhorar.

Como a GPI fundamenta o controle por TD

SARSA: GPI on-policy

O SARSA aprende (q_{\pi}) para a política de comportamento atual (\pi), e então melhora (\pi) (muitas vezes de forma gradual via (\varepsilon)-gulosa).

Atualização de TD:

[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)\right] ]

Avaliação: o erro TD (TD error) empurra (Q) em direção a (q_\pi).
Melhoria: escolher ações usando uma política melhorada como (\varepsilon)-gulosa em relação ao (Q) atual.

Mesmo que (Q) seja imperfeito e esteja mudando, a intercalação ainda tende a melhorar o desempenho em cenários tabulares sob condições padrão.

Aprendizado Q: GPI off-policy com “alvo guloso”

Aprendizado Q usa um alvo de avaliação diferente:

[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a') - Q(S_t,A_t)\right] ]

Isso se parece com iteração de valor usando amostras: o alvo usa (\max_{a'} Q), isto é, ele avalia como se a próxima ação fosse gulosa.

Pela lente da GPI:

Avaliação: as atualizações empurram (Q) em direção a (q^*) (a função ótima de valor de ação).
Melhoria: o comportamento frequentemente é (\varepsilon)-guloso em relação a (Q), tornando-se gradualmente mais guloso.

Assim, o aprendizado Q pode ser interpretado como iteração de valor aproximada e assíncrona, que por si só é um caso especial de GPI.

Ator–crítico como GPI explícita

Métodos Ator–Crítico tornam os dois componentes explícitos:

Crítico (critic): estima (v_\pi) ou (q_\pi) (avaliação de política).
Ator (actor): atualiza os parâmetros da política para melhorar o desempenho (melhoria de política).

Uma estrutura típica (simplificada):

Erro TD do crítico: [ \delta_t = R_{t+1} + \gamma V_\phi(S_{t+1}) - V_\phi(S_t) ]
Atualização do ator no estilo de gradiente de política (policy gradient): [ \theta \leftarrow \theta + \beta , \delta_t , \nabla_\theta \log \pi_\theta(A_t\mid S_t) ]

Aqui, avaliação e melhoria são intercaladas a cada passo:

O crítico está sempre um pouco errado (avaliação aproximada).
O ator muda a política antes que o crítico converja (melhoria aproximada).

Essa é precisamente a filosofia da GPI, e ela permanece a espinha dorsal de sistemas modernos de aprendizado por reforço profundo, como métodos no estilo PPO (ver Otimização de Política Proximal (Proximal Policy Optimization, PPO)) e outras variantes ator–crítico.

Aproximação e melhoria “suave”

Na prática, a melhoria em aprendizado por reforço muitas vezes não é um passo guloso rígido. Mecanismos comuns de melhoria suavizada incluem:

(\varepsilon)-gulosa: majoritariamente gulosa, mas explora aleatoriamente com probabilidade (\varepsilon).
Políticas softmax / Boltzmann (softmax / Boltzmann policies): preferem ações de maior valor de forma suave.
Regularização por entropia (entropy regularization) (comum em ator–crítico profundo): desencoraja determinismo prematuro.
Pequenas atualizações de política (trust region / clipping) (região de confiança / recorte, como no PPO): evita saltos destrutivos.

Tudo isso ainda é GPI: você está melhorando a política em relação às estimativas atuais, só que sem dar o salto guloso completo.

Atualizações assíncronas e parciais: por que a GPI se encaixa no aprendizado real

A programação dinâmica clássica assume que você consegue varrer todos os estados e computar atualizações por expectativa. Agentes reais:

veem um fluxo de experiência,
atualizam apenas estados visitados,
podem revisitar alguns estados muito mais frequentemente do que outros,
podem atualizar a partir de buffers de replay (replay buffers) ou rollouts simulados (simulated rollouts).

A GPI abrange confortavelmente tudo isso. De fato, muitos algoritmos podem ser descritos como escolhendo:

o que avaliar (V ou Q, quais estados),
como avaliar (Monte Carlo, TD(0), TD((\lambda)), n-step),
como melhorar (gulosa, suave, passo de gradiente),
quando fazer cada uma (a cada passo, a cada episódio, periodicamente).

Essa flexibilidade é uma razão pela qual a GPI é considerada um “princípio organizador” fundamental em aprendizado por reforço.

Intuição básica de convergência em cenários tabulares

A história de convergência da GPI no caso tabular, finito, com desconto, é construída a partir de alguns fatos que interagem entre si.

1) Avaliação de política é estável (uma contração)

Para (\pi) fixa, aplicar repetidamente (T^\pi) converge para (v_\pi). Com atualizações assíncronas (atualizando um estado por vez), a convergência ainda vale se todo estado for atualizado infinitas vezes e se os tamanhos de passo se comportarem bem (em cenários estocásticos).

É por isso que o aprendizado por TD pode funcionar: cada atualização empurra as estimativas em direção ao ponto fixo de (T^\pi), mesmo que esses empurrões sejam ruidosos.

2) Melhoria de política gulosa é monotônica (no caso exato)

Se você avalia totalmente (\pi) e então gulosifica, obtém uma política (\pi') que é pelo menos tão boa em toda parte: [ v_{\pi'} \ge v_\pi ]

Assim, na iteração de políticas exata, os valores melhoram de modo monotônico e o processo termina em um número finito de iterações (MDP finito, desempate determinístico).

3) A intercalação funciona porque a avaliação “acompanha” o alvo móvel

Na GPI, a política-alvo muda enquanto a avaliação está em andamento. Intuitivamente:

as atualizações de avaliação tentam alcançar a função de valor da política atual,
a melhoria usa as estimativas de valor atuais para propor um comportamento melhor.

Se a avaliação for “boa o suficiente” com frequência suficiente — e a melhoria não oscilar violentamente — o ciclo tende a subir em direção à optimalidade.

4) Exemplos de convergência de controle tabular

O aprendizado Q converge para (q^*) sob condições padrão: exploração suficiente (todos os pares estado–ação visitados infinitas vezes) e taxas de aprendizado satisfazendo as condições de Robbins–Monro (Robbins–Monro conditions) (aproximadamente: tamanhos de passo decrescentes com soma total infinita, mas soma dos quadrados finita). Este é um exemplo clássico de GPI convergindo apesar de atualizações assíncronas e baseadas em amostras.
O SARSA converge para a política ótima (\varepsilon)-gulosa no limite se (\varepsilon \to 0) lentamente o suficiente (GLIE: “guloso no limite com exploração infinita (greedy in the limit with infinite exploration, GLIE)”) e se os tamanhos de passo forem bem comportados.

O tema central: desde que o processo de aprendizado continue explorando e as atualizações permaneçam estáveis, avaliação aproximada + melhoria aproximada ainda podem convergir em cenários tabulares.

Implicações práticas: como “fazer GPI bem”

A GPI é uma estrutura conceitual, não um algoritmo. Mas ela sugere escolhas práticas de projeto.

Escolha um método de avaliação apropriado ao seu cenário

Baseado em modelo / estilo DP: atualizações de Bellman completas se você tiver um modelo.
Sem modelo: aprendizado por TD (bootstrap) se você tiver apenas amostras.
Multietapas: retornos em n passos (n-step returns) ou TD((\lambda)) para balancear viés e variância.

Veja Aprendizado por Diferença Temporal (TD) para o lado da avaliação.

Escolha um método de melhoria que combine com sua representação

Se você representa (Q(s,a)) explicitamente (tabular), gulosa/(\varepsilon)-gulosa é natural.
Se você tem uma política parametrizada diferenciável (comum em aprendizado por reforço profundo), use gradientes de política e atualizações ator–crítico (veja Gradientes de Política e Métodos Ator–Crítico).

Estabilize o ciclo de realimentação (especialmente com aproximação de função)

Com grandes aproximadores de função (function approximation) (redes neurais (neural networks)), a história limpa de convergência tabular pode falhar. Um alerta famoso é a “tríade mortal (deadly triad)”: aproximação de função + bootstrap + aprendizado off-policy pode causar divergência.

O aprendizado por reforço profundo moderno frequentemente usa estabilizadores que podem ser interpretados como “tornar a GPI mais suave”:

redes-alvo (target networks) (alvo de avaliação que muda lentamente)
replay de experiência (experience replay) (reduz correlação, melhora eficiência de dados)
região de confiança / recorte (trust region / clipping) (restringe o tamanho do passo de melhoria; ex.: PPO)
regularização (regularization) (bônus de entropia, decaimento de peso)

Para um contexto mais amplo, veja Aprendizado Profundo por Reforço (Deep Reinforcement Learning).

Resumo de relações: PI, VI, controle por TD e ator–crítico

Iteração de Políticas: GPI com avaliação exata e melhoria gulosa, alternadas em grandes blocos.
Iteração de Valor: GPI com avaliação mínima por melhoria (uma atualização de otimalidade), tipicamente síncrona em livros-texto, mas que também pode ser assíncrona.
Controle por TD (SARSA, aprendizado Q): GPI em que a avaliação é feita por atualizações de TD baseadas em amostras, e a melhoria é implícita via seleção de ação gulosa/(\varepsilon)-gulosa.
Ator–crítico: GPI explicitada com dois aprendizes executando simultaneamente: crítico (avaliação) e ator (melhoria).

Equívocos comuns

“GPI é um algoritmo.”
É melhor entendida como um princípio ou modelo que descreve como a maioria dos métodos de controle em aprendizado por reforço opera.
“Você precisa avaliar completamente antes de melhorar.”
Isso é iteração de políticas, não GPI. Em muitos problemas práticos, a avaliação completa é cara demais ou impossível.
“Avaliação aproximada estraga tudo.”
Não necessariamente — controle por TD tabular pode convergir, e muitos métodos aproximados funcionam bem na prática. Mas a aproximação introduz novos modos de falha, especialmente com aprendizado off-policy e aproximação de função.

Principal conclusão

A Iteração Generalizada de Políticas é o ciclo central por trás do controle em aprendizado por reforço: avaliar continuamente (e muitas vezes de forma aproximada) a política atual e melhorá-la com base nas estimativas de valor correntes. Ela explica as conexões entre métodos de programação dinâmica como iteração de políticas e iteração de valor, e métodos baseados em aprendizado como controle por TD e ator–crítico. Em MDPs tabulares com desconto, as propriedades de contração dos operadores de Bellman e a intuição de melhoria monotônica fornecem uma base para entender por que essa intercalação converge — enquanto, em cenários de grande escala, estabilizadores práticos muitas vezes são necessários para manter o ciclo de realimentação da GPI bem comportado.