Ao substituir a etapa de avaliação de política no algoritmo padrão de iteração de política pelas técnicas de estimação de Monte Carlo descritas no capítulo anterior, já podemos derivar uma nova variação da iteração de política—uma que depende de experiências amostradas em vez de programação dinâmica.

No entanto, existe uma limitação crítica. Na iteração de política tradicional, a etapa de melhoria de política depende do acesso a um modelo completo do ambiente. Especificamente, para atualizar a política, utilizamos a seguinte expressão:

Esta equação assume que conhecemos as probabilidades de transição $p(s', r | s, a)$. Mas este é exatamente o problema: os métodos de Monte Carlo são projetados para cenários sem modelo, onde a dinâmica de transição do ambiente é desconhecida. Se um modelo completo estiver disponível, então seria mais eficiente e preciso utilizar programação dinâmica em todo o processo, inclusive para avaliação de política.

Portanto, embora substituir métodos de Monte Carlo para estimação de valor seja um passo em direção ao aprendizado por reforço sem modelo, também é necessário encontrar uma forma de realizar a melhoria de política sem depender do conhecimento do modelo. Isso exige a transição da função de valor de estado para a função de valor de ação.

Por que valores de ação?

Ao utilizar valores de ação, é possível realizar a melhoria de política sem a necessidade de um modelo do ambiente. Em vez de depender das probabilidades de transição para calcular os retornos esperados, é possível selecionar diretamente as ações que aparentam fornecer o maior valor. A etapa de melhoria de política torna-se então:

E não é difícil provar que a nova política não é pior do que a anterior, pois o teorema de melhoria de política ainda pode ser aplicado:

E, assim como na programação dinâmica, este teorema garante que $\pi_{k+1}$ é melhor que $\pi_k$, ou que ambas são iguais e ótimas.

Estimativa da Função de Valor de Ação

O processo de estimativa é quase idêntico ao da função de valor de estado. Todas as ideias utilizadas para estimar valores de estado podem ser aplicadas para estimar valores de ação.

Pseudocódigo

Dessa forma, com iterações suficientes, os valores de ação estimados devem se aproximar dos valores de ação reais.

Com isso, já é possível construir um método semelhante à iteração de política que não depende de um modelo. Para isso, basta substituir as etapas de avaliação de política e melhoria de política pelos processos descritos acima.

Otimização

Embora a etapa de avaliação possa ser realizada utilizando a estimação de Monte Carlo conforme descrito, ela tende a ser computacionalmente ineficiente. Como já observado, métodos de Monte Carlo normalmente exigem um grande número de amostras para produzir estimativas razoavelmente precisas. Se seguirmos uma estrutura semelhante à iteração de política, essa ineficiência é ampliada: após cada melhoria de política, é necessário executar novamente a estimação de Monte Carlo para reavaliar a nova política — resultando em sobrecarga substancial e aprendizado lento.

Uma alternativa mais natural é atualizar a política imediatamente após o processamento de cada episódio. Em vez de aguardar a conclusão de toda a avaliação da política, permite-se que o agente refine seu comportamento episódio por episódio, utilizando as estimativas de valor de ação mais recentes.

Isso resulta em um método que se assemelha mais à iteração de valor: combinando aspectos de avaliação e melhoria em uma única etapa. Isso aumenta a eficiência amostral, acelerando o processamento computacional.

Pseudocódigo

Este algoritmo segue o framework GPI, pois possui etapas de avaliação de política e melhoria de política, sendo chamado de controle Monte Carlo. A principal desvantagem desta implementação específica é a suposição de inícios exploratórios. Nos próximos capítulos, será explicado por que isso é um problema e como pode ser solucionado.