Como já visto, a função de valor de estado de uma política pode ser determinada resolvendo a 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 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 termine.

Avaliação Iterativa de Política

A solução pode ser calculada diretamente, mas uma abordagem iterativa é mais comumente utilizada devido à sua facilidade de implementação. Este método começa atribuindo valores arbitrários a 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 as estimativas anteriores é denominado 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 valores recém-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