Como você já sabe, a função de valor de estado de uma política pode ser determinada resolvendo uma equação de Bellman:

Se você possui um modelo completo do ambiente (ou seja, probabilidades de transição conhecidas e recompensas esperadas para todos os pares de estado-ação), as únicas variáveis desconhecidas restantes na equação são os valores dos estados. Portanto, a equação acima pode ser reformulada como um sistema de $|S|$ equações lineares com $|S|$ incógnitas.

Por exemplo, se um MDP possui 2 estados ($s_1$, $s_2$) e 2 ações (mover para $s_1$, mover para $s_2$), a função de valor de estado pode ser definida assim:

Isso pode ser resolvido utilizando técnicas padrão de álgebra linear.

Uma solução única para tal sistema linear é garantida se pelo menos uma das seguintes condições for satisfeita:

• O fator de desconto satisfaz $γ < 1$;
• A política $\pi$, quando seguida a partir de qualquer estado $s$, garante que o episódio eventualmente termina.

Avaliação Iterativa de Política

A solução pode ser computada diretamente, mas uma abordagem iterativa é mais comumente utilizada devido à sua facilidade de implementação. Este método começa atribuindo valores arbitrários iniciais para todos os estados, exceto para os estados terminais, que são definidos como 0. Os valores são então atualizados iterativamente utilizando a equação de Bellman como regra de atualização:

A função de valor de estado estimada $v_k$ eventualmente converge para a verdadeira função de valor de estado $v_\pi$ à medida que $k \to \infty$, se $v_\pi$ existir.

Estratégias de Backup de Valor

Ao atualizar as estimativas de valor, novas estimativas são calculadas com base nos valores anteriores. O processo de preservar estimativas anteriores é conhecido como backup. Existem duas estratégias comuns para realizar backups:

• Backup completo: este método envolve armazenar as novas estimativas em um array separado, distinto daquele que contém os valores anteriores (armazenados em backup). Consequentemente, são necessários dois arrays — um para manter as estimativas anteriores e outro para armazenar os novos valores calculados;
• Backup in-place: esta abordagem mantém todos os valores em um único array. Cada nova estimativa substitui imediatamente o valor anterior. Este método reduz o uso de memória, pois apenas um array é necessário.

Normalmente, o método de backup in-place é preferido porque requer menos memória e converge mais rapidamente, devido ao uso imediato das estimativas mais recentes.

Quando parar de atualizar?

Na avaliação iterativa de política, não existe um ponto exato em que o algoritmo deve ser interrompido. Embora a convergência seja garantida no limite, continuar os cálculos além de certo ponto é desnecessário na prática. Um critério de parada simples e eficaz é acompanhar a diferença absoluta entre as estimativas de valor consecutivas, $|v_{k+1}(s) - v_k(s)|$, e compará-la a um pequeno limiar $\theta$. Se, após um ciclo completo de atualização (em que os valores de todos os estados são atualizados), nenhuma alteração exceder $\theta$, o processo pode ser encerrado com segurança.

Pseudocódigo