Ao substituir a etapa de avaliação de política no algoritmo padrão de iteração de política pelas técnicas de estimativa 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:

Essa equação pressupõe que conhecemos as probabilidades de transição $p(s', r | s, a)$. Mas esse é justamente 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 é preferível utilizar programação dinâmica em todo o processo, inclusive para avaliação de política, pois seria mais eficiente e preciso.

Portanto, embora substituir métodos de Monte Carlo para estimativa 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, podemos selecionar diretamente as ações que aparentam fornecer o maior valor. A etapa de melhoria de política então se torna:

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

E, assim como na programação dinâmica, esse 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 na estimativa de 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 usando a estimação de Monte Carlo conforme descrito, ela tende a ser computacionalmente ineficiente. Como já foi 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 esperar pela conclusão de toda uma varredura de avaliação de 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 um único passo. Isso aumenta a eficiência amostral, acelerando a computação.

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 exploring starts. Nos próximos capítulos, você verá por que isso é um problema e como pode ser resolvido.