Comencemos revisando un concepto familiar: la función de valor de estado, denotada como $v_\pi(s)$. Se puede definir como

El objetivo en este capítulo es estimar esta función a partir de datos, asumiendo que se nos da una política fija $\pi$ pero no tenemos acceso al modelo del entorno.

Estimación Monte Carlo

Los métodos Monte Carlo abordan esta tarea de estimación mediante el muestreo de episodios de experiencia bajo la política $\pi$, utilizando luego estas muestras para formar estimaciones empíricas de $v_\pi(s)$.

En general, el proceso puede dividirse en los siguientes pasos:

1. Generar un episodio usando la política $\pi$;
2. Guardar el valor de retorno obtenido para cada estado que aparece en el episodio;
3. Repetir los pasos 1-2 durante un tiempo;
4. Calcular los nuevos valores promediando los retornos para cada estado.

Recopilación de los Retornos

La estimación Monte Carlo de la función de valor requiere recopilar los retornos de los episodios generados. Para calcular estos retornos, se pueden utilizar dos enfoques principales:

• Primera-visita: para cada estado $s$ encontrado en un episodio, solo se considera el retorno posterior a su primera aparición. Las ocurrencias posteriores del mismo estado dentro del mismo episodio se ignoran para fines de estimación;
• Cada-visita: se utiliza cada aparición de un estado $s$ dentro de un episodio. Es decir, el retorno posterior a cada visita al estado se incluye en la estimación, incluso si el estado aparece varias veces en el mismo episodio.

Exploración de Inicios

Imagina un mundo simple unidimensional representado por una línea que se extiende desde -10 hasta +10. El agente comienza en la posición 0, y su política actual dicta que siempre se mueve hacia la derecha en cada paso de tiempo.

Si intentamos generar episodios bajo esta política, ¿qué sucede? El agente se moverá continuamente hacia el extremo positivo de la línea — visitando estados como 1, 2, 3, y así sucesivamente — pero nunca visitará ningún estado negativo. Como resultado, no podemos estimar las funciones de valor para los estados a la izquierda del origen, simplemente porque el agente nunca los experimenta.

Así que el problema principal es: si ciertas partes del espacio de estados nunca se exploran, sus estimaciones de valor permanecerán inexactas o indefinidas. Una solución común a este problema es el uso de inicios exploratorios.

Con los inicios exploratorios, cada episodio comienza no en un estado inicial fijo como el 0, sino en un estado seleccionado aleatoriamente. Una vez que el episodio comienza, el agente sigue su política actual como de costumbre. Con el tiempo, al comenzar desde muchos puntos diferentes a lo largo del espacio de estados, el agente puede visitar todos los estados — no solo aquellos a los que su política lo llevaría de forma natural. Esto permite que el método de Monte Carlo produzca estimaciones de valor más precisas y completas para todo el espacio de estados.

Pseudocódigo

Este pseudocódigo utiliza el enfoque de todas las visitas junto con inicios exploratorios.