propagando valores para trás

Iteração de valor é um algoritmo de programação dinâmica que converge para a função valor ótima. Ele usa a equação de Bellman para atualizar V(s) repetidamente. Primeiramente, calcula Q(s,a) para cada ação usando modelo do ambiente. Além disso, atualiza V(s) como o máximo sobre Q(s,a). Por exemplo, em um labirinto, valores propagam da saída para entrada. O processo repete até convergência.

algoritmo passo a passo

O algoritmo começa com V(s) arbitrário para todos os estados. Primeiramente, para cada estado, calcula Q(s,a) = R(s,a) + γ Σ P(s’|s,a) V(s’). Além disso, atualiza V(s) = max_a Q(s,a). Repete até mudanças muito pequenas nos valores. Por exemplo, cada iteração melhora aproximação da função valor ótima. Convergência garantida para problemas com fator de desconto γ < 1.

vantagens e aplicações

Iteração de valor é simples e converge para política ótima sem iterações de política. Primeiramente, combina avaliação e melhoria da política em um único passo. Além disso, funciona bem para problemas com espaço de estados moderado. Por exemplo, resolver labirintos, jogos simples e planejamento discreto. É a base teórica para algoritmos mais avançados. Para iniciantes, mostra como valores se propagam pelo espaço de estados. Demonstra o poder da programação dinâmica em aprendizado por reforço.

Problemas baseados em valor e programação dinâmica

A programação dinâmica resolve problemas de decisão sequencial. Ela é usada quando o modelo do ambiente é conhecido. Primeiramente, ela calcula funções valor de forma iterativa. Em segundo lugar, ela extrai políticas ótimas dessas funções. Por conseguinte, é uma ferramenta poderosa para planejamento. Este método é considerado a base teórica do aprendizado por reforço moderno.

Iteração de valor e iteração de política

A iteração de valor atualiza todos os estados simultaneamente. A fórmula é \( V_{k+1}(s) = \max_a \sum_{s’,r} p(s’,r|s,a) [r + \gamma V_k(s’)] \). Esse processo converge para V* após várias iterações. A iteração de política, por outro lado, alterna entre avaliação e melhoria. Primeiro, avaliamos a política atual. Depois, melhoramos ela guloso. Ambos os métodos são garantidos de convergir.

A avaliação de política é feita resolvendo \( V^\pi(s) = \sum_a \pi(a|s) \sum_{s’,r} p(s’,r|s,a) [r + \gamma V^\pi(s’)] \). Isso é um sistema de equações lineares. Na prática, usamos iteração para resolvê-lo. A melhoria de política atualiza com \( \pi'(s) = \arg\max_a \sum_{s’,r} p(s’,r|s,a) [r + \gamma V^\pi(s’)] \). O processo repete até que a política não mude mais.

Hiperparâmetros e arquitetura

O fator de desconto γ é o hiperparâmetro mais importante. Valores típicos são 0.9, 0.95 ou 0.99. O critério de convergência θ (theta) controla a precisão. Valores menores como 1e-6 dão resultados mais exatos. O número máximo de iterações evita loops infinitos. A arquitetura armazena valores em uma tabela (espaço discreto). Para espaços contínuos, usamos aproximadores como redes neurais. Contudo, programação dinâmica clássica assume tabela finita.

A complexidade computacional é O(|S|² × |A|). Isso pode ser pesado para muitos estados. Por isso, usamos técnicas de varredura assíncrona. A programação dinâmica é um método de planejamento. Ela não aprende por interação, mas sim por cálculo direto. Portanto, é diferente do Q-learning que é livre de modelo.

Exemplo clássico: grade com recompensas

Imagine uma grade 4×4 onde cada célula é um estado. O agente começa no canto superior esquerdo. O objetivo está no canto inferior direito. Recompensas: -0.1 por passo, +10 no objetivo. Paredes bloqueiam certas células. O ambiente é determinístico e conhecido. O objetivo é encontrar a política ótima. O código abaixo resolve com iteração de valor.