Vamos começar revisitando um conceito familiar: a função de valor de estado, denotada como $v_\pi(s)$. Ela pode ser definida como

O objetivo neste capítulo é estimar essa função a partir de dados, assumindo que temos uma política fixa $\pi$, mas sem acesso ao modelo do ambiente.

Estimativa de Monte Carlo

Os métodos de Monte Carlo abordam essa tarefa de estimativa por meio da amostragem de episódios de experiência sob a política $\pi$, utilizando essas amostras para formar estimativas empíricas de $v_\pi(s)$.

De modo geral, o processo pode ser dividido nos seguintes passos:

1. Gerar um episódio utilizando a política $\pi$;
2. Salvar o valor de retorno obtido para cada estado que aparece no episódio;
3. Repetir os passos 1-2 por algum tempo;
4. Calcular os novos valores pela média dos retornos para cada estado.

Coleta dos Retornos

A estimação de função de valor por Monte Carlo requer a coleta dos retornos a partir dos episódios gerados. Para calcular esses retornos, dois métodos principais podem ser utilizados:

• Primeira-visita: para cada estado $s$ encontrado em um episódio, apenas o retorno após sua primeira ocorrência é considerado. Ocorrências subsequentes do mesmo estado dentro do mesmo episódio são ignoradas para fins de estimação;
• Toda-visita: toda ocorrência de um estado $s$ dentro de um episódio é utilizada. Ou seja, o retorno após cada visita ao estado é incluído na estimativa, mesmo que o estado apareça várias vezes no mesmo episódio.

Exploração de Inícios

Imagine um mundo unidimensional simples representado por uma linha que se estende de -10 a +10. O agente começa na posição 0, e sua política atual determina que ele sempre se move para a direita a cada passo de tempo.

Se tentarmos gerar episódios sob essa política, o que acontece? O agente continuará se movendo em direção à extremidade positiva da linha — visitando estados como 1, 2, 3 e assim por diante — mas nunca visitará estados negativos. Como resultado, não podemos estimar funções de valor para os estados à esquerda da origem, simplesmente porque o agente nunca os experimenta.

Portanto, o principal problema é: se certas partes do espaço de estados nunca são exploradas, suas estimativas de valor permanecerão imprecisas ou indefinidas. Uma solução comum para esse problema é o uso de inícios exploratórios.

Com inícios exploratórios, cada episódio começa não em um estado inicial fixo como 0, mas em um estado selecionado aleatoriamente. Uma vez iniciado o episódio, o agente segue sua política atual normalmente. Com o tempo, ao começar de vários pontos diferentes do espaço de estados, o agente consegue visitar todos os estados — não apenas aqueles para os quais sua política naturalmente o levaria. Isso permite que o método de Monte Carlo produza estimativas de valor mais precisas e completas para todo o espaço de estados.

Pseudocódigo

Este pseudocódigo utiliza a abordagem every-visit juntamente com exploring starts.