Métodos de Monte Carlo

Los métodos de Monte Carlo requieren solo experiencia: secuencias de muestra de estados, acciones y recompensas de la interacción real o simulada con un entorno.

$\circ$ El aprendizaje a partir de la experiencia real es sorprendente porque no requiere un conocimiento previo de la dinámica del entorno, pero aún así puede lograr un comportamiento óptimo.

$\circ$ El aprendizaje a partir de la experiencia simulada también es poderoso. Aunque se requiere un modelo, el modelo solo necesita generar transiciones de muestra, no las distribuciones de probabilidad completas de todas las transiciones posibles que se requieren para la programación dinámica (PD).

En un número sorprendente de casos, es fácil generar experiencia muestreada de acuerdo con las distribuciones de probabilidad deseadas, pero no es factible obtener las distribuciones en forma explícita.

Los métodos de Monte Carlo son formas de resolver el problema del aprendizaje de refuerzo basándose en el promedio de los retornos de la muestra. Para garantizar que se disponga de retornos bien definidos, aquí definimos los métodos de Monte Carlo solo para tareas episódicas.

El término Monte Carlo suele utilizarse de forma más amplia para cualquier método de estimación cuyo funcionamiento implica un componente aleatorio significativo. Es una manera de transformar un problema determinista a uno estocástico.

Predicción de Montecarlo

Comenzamos considerando los métodos de Monte Carlo para aprender la función de valor del estado para una política dada. Recordemos que el valor de un estado es el retorno esperado (la recompensa futura acumulada esperada descontada) a partir de ese estado.

Una manera obvia de estimarlo a partir de la experiencia, entonces, es simplemente promediar los retornos observados después de las visitas a ese estado. A medida que se observan más retornos, el promedio debería converger al valor esperado .

En particular, supongamos que deseamos estimar $v_{π} (s)$ , el valor de un estado $s$ bajo la política $π$ , dado un conjunto de episodios obtenidos siguiendo $π$ y pasando por $s$ . Cada ocurrencia del estado $s$ en un episodio se llama visita a $s$ .

Por supuesto, $s$ puede ser visitado varias veces en el mismo episodio; llamemos a la primera vez que se visita en un episodio la primera visita a $s$ . El método MC de la primera visita estima $v_{π} (s)$ como el promedio de los retornos posteriores a las primeras visitas a $s$ , mientras que el método MC de cada visita promedia los retornos posteriores a todas las visitas a $s$ . Estos dos métodos de Monte Carlo (MC) son muy similares pero tienen propiedades teóricas ligeramente diferentes.

La primera visita de MC se muestra en forma de procedimiento en el recuadro.

Predicción con la primera visita MC, para estimar

Entrada: una política $π$ a ser evaluada.

Inicializar:

$V (s) \in R$ arbitrariamente para todo $s \in S$

$D e v o l u c i o n (s) \leftarrow$ una lista vacía para todo $s \in S$

Bucle para siempre (para cada episodio):

Generar un episodio siguiendo $π$ :

$S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \dots, S_{T - 1}, A_{T - 1}, R_{T}$

$G \leftarrow 0$

Bucle para cada paso del episodio, $t = T - 1, T - 2, \dots, 0$ :

$G \leftarrow γ G + R_{t + 1}$

Hasta que $S_{t}$ esté en $S_{0}, S_{1}, \dots, S_{t + 1}$ :

Añadir $G$ a $D e v o l u c i o n (S_{t})$

$V (S_{t}) \leftarrow p r o m e d i o (D e v o l u c i o n (S_{t}))$

Estimación de valores de acción mediante Monte Carlo

Si no hay un modelo disponible, resulta especialmente útil estimar valores de acción (los valores de los pares estado-acción) en lugar de valores de estado.

El problema de evaluación de políticas para valores de acción es estimar $q_{π} (s, a)$ , el retorno esperado al comenzar en el estado $s$ , tomar la acción $a$ y luego seguir la política $π$ . Los métodos de Monte Carlo para esto son esencialmente los mismos que los que se acaban de presentar para los valores de estado, excepto que ahora hablamos de visitas a un par estado-acción en lugar de a un estado. Se dice que un par estado-acción $s, a$ es visitado en un episodio si alguna vez se visita el estado $s$ y se toma la acción $a$ en él.

La única complicación es que muchos pares de acciones y estados pueden no ser visitados nunca. Si $π$ es una política determinista, entonces al seguir $π$ se observarán retornos solo para una de las acciones de cada estado. Sin retornos al promedio, las estimaciones de Monte Carlo de las otras acciones no mejorarán con la experiencia. Este es un problema serio porque el propósito de aprender los valores de las acciones es ayudar a elegir entre las acciones disponibles en cada estado. Para comparar alternativas necesitamos estimar el valor de todas las acciones de cada estado, no solo de la que actualmente favorecemos.

Éste es el problema general de mantener la exploración. Para que la evaluación de políticas funcione en el caso de los valores de acción, debemos asegurar una exploración continua. Una forma de hacerlo es especificando que los episodios comienzan en un par estado-acción, y que cada par tiene una probabilidad distinta de cero de ser seleccionado como inicio. Esto garantiza que todos los pares estado-acción serán visitados una cantidad infinita de veces en el límite de una cantidad infinita de episodios. A esto lo llamamos el supuesto de inicios de exploración.

En particular, cuando se aprende directamente de la interacción real con un entorno. El enfoque alternativo más común para garantizar que se encuentren todos los pares de estado-acción es considerar solo políticas que sean estocásticas con una probabilidad distinta de cero de seleccionar todas las acciones en cada estado.

Control Monte Carlo

Ahora estamos listos para considerar cómo se puede utilizar la estimación de Monte Carlo en el control, es decir, para aproximar políticas óptimas. La idea general es proceder de acuerdo con la idea de iteración generalizada de políticas (GPI).

Realizamos pasos completos alternos de evaluación de políticas y mejora de políticas, comenzando con una política arbitraria $π_{0}$ y terminando con la política óptima y la función de valor de acción óptima: $π_{0} \overset{E}{⟶} q_{π_{0}} \overset{I}{⟶} π_{1} \overset{E}{⟶} q_{π_{1}} \overset{I}{⟶} π_{2} \overset{E}{⟶} \dots \overset{I}{⟶} π_{*} \overset{E}{⟶} q_{*},$ donde $\overset{E}{⟶}$ denota la evaluación de la política y $\overset{I}{⟶}$ denota la mejora de política.

La mejora de la política se realiza haciendo que la política sea codiciosa con respecto a la función de valor actual. En este caso, tenemos una función de valor de acción y, por lo tanto, no se necesita ningún modelo para construir la política codiciosa. Para cualquier función de valor de acción $q$ , la política codiciosa correspondiente es la que, para cada $s \in S$ , elige de manera determinista una acción con el valor de acción máximo: $π (s) = \underset{a}{a r g m a x} q (s, a) .$

La mejora de la política puede entonces realizarse construyendo cada $π_{k + 1}$ como la política codiciosa con respecto a $q_{k}$ . El teorema de mejora de política aplicado a $π_{k}$ y $π_{k + 1}$ porque, para todo $s \in S$ , $\begin{array}{rcl} q_{π_{k}} (s, π_{k + 1} (s)) & = & q_{π_{k}} (s, \underset{a}{a r g m a x} q_{π_{k}} (s, a)) \\ = & \underset{a}{m a x} q_{π_{k}} (s, a) \\ \geq & q_{π_{k}} (s, π_{k} (s)) \\ \geq & v_{π_{k}} (s) . \end{array}$

Esto, a su vez, nos asegura que el proceso general converge hacia la política óptima y la función de valor óptima. De esta manera, los métodos de Monte Carlo pueden utilizarse para encontrar políticas óptimas dados solo episodios de muestra y ningún otro conocimiento de la dinámica del entorno.

Para obtener fácilmente esta garantía de convergencia para el método de Monte Carlo, hemos hecho dos suposiciones poco probables:

$\circ$ Una era que los episodios tienen inicios exploratorios.

$\circ$ Y la otra era que la evaluación de políticas se podía hacer con un número infinito de episodios.

Para obtener un algoritmo práctico tendremos que eliminar ambas suposiciones.

La evaluación de políticas suele asumirse sobre episodios infinitos, pero este supuesto puede eliminarse. Tanto en Programación Dinámica (DP) como en Monte Carlo, la convergencia es asintótica. Para abordar esto, se puede aproximar $q_{π_{k}}$ en cada evaluación, estableciendo límites de error y asegurando que sean pequeños. Aunque este método garantiza una buena convergencia teórica, puede requerir demasiados episodios, volviéndolo poco práctico para problemas grandes.

Otro enfoque para evitar episodios infinitos es no completar la evaluación antes de mejorar la política. En cada paso, la función de valor se mueve hacia $q_{π_{k}}$ , pero sin esperar una aproximación completa. Un caso extremo es la iteración de valor, donde solo se realiza una evaluación antes de mejorar la política. Aún más extremo es hacerlo por estado, alternando mejora y evaluación continuamente.

Para la iteración de políticas de Monte Carlo es natural alternar entre evaluación y mejora episodio por episodio. Después de cada episodio, los retornos observados se utilizan para la evaluación de políticas y luego la política se mejora en todos los estados visitados en el episodio. Un algoritmo simple completo en esta línea, que llamamos Monte Carlo ES, para Monte Carlo con inicios exploratorios, se presenta en pseudocódigo en el recuadro de la página siguiente.

Monte Carlo ES, para estimar $π \approx π_{*}$

Inicializar:

$π (s) \in A (s)$ arbitrariamente, para todo $s \in S$

$Q (s, a) \in R$ aribitrariamente, para todo $s \in S, a \in A (s)$

$D e v o l u c i o n (s, a) \leftarrow e m p t y$ , para todo $s \in S, a \in A (s)$

Bucle para siempre (para cada episodio):

Escoge $S_{0} \in S, A_{0} \in A (S_{0})$ aleatoriamente tales que todos los pares tienen probabilidad $> 0$

Genera un episodio desde $S_{0}, A_{0}$ , siguiendo $π$ : $S_{0}, A_{0}, R_{1}, \dots, S_{T - 1}, A_{T - 1}, R_{T}$

$G \leftarrow 0$

Bucle para cada episodio, $t = T - 1, T - 2, \dots, 0$ :

$G \leftarrow γ G + R_{t + 1}$

Hasta que el par $S_{t}, A_{t}$ aparezca en $S_{0}, A_{0}, S_{1}, A_{1}, \dots, S_{t - 1}, A_{t - 1}$ :

Añadir $G$ a $D e v o l u c i o n (S_{t}, A_{t})$

$Q (S_{t}, A_{t}) \leftarrow p r o m e d i o (D e v o l u c i o n (S_{t}, A_{t}))$

$π (S_{t}) \leftarrow a r g m a x_{a} Q (S_{t}, a)$

Control de Montecarlo sin inicios exploratorios

¿Cómo podemos evitar la improbable suposición de que inicios exploratorios? La única forma general de garantizar que todas las acciones se seleccionen con una frecuencia infinita es que el agente continúe seleccionándolas. Existen dos enfoques para garantizar esto, que dan como resultado lo que llamamos métodos on-policy y métodos off-policy.

Los métodos on-policy intentan evaluar o mejorar la política que se utiliza para tomar decisiones.

Los métodos off-policy evalúan o mejoran una política diferente de la utilizada para generar los datos.

En los métodos de control basados on-policy, la política es generalmente blanda (soft), lo que significa que $π (a | s) > 0$ para todos los $s \in S$ y todos los $a \in A (s)$ , pero gradualmente se va acercando cada vez más a una política óptima determinista.

El método de política que presentamos en esta sección utiliza políticas $ε$ -codiciosas, lo que significa que la mayoría de las veces eligen una acción que tiene un valor de acción estimado máximo, pero con probabilidad $ε$ seleccionan una acción al azar. (con $ε \in (0, 1)$ )

Todas las acciones no codiciosas se les da la probabilidad miníma de ser seleccioandas $ε / | A (s) |$ y a la acción con mayor valor $1 - ε + ε / | A (s) |$ .

La idea general del control de Monte Carlo en función de la política sigue siendo la del GPI. Al igual que en el método Monte Carlo ES, utilizamos métodos de control de Monte Carlo de primera visita para estimar la función de valor de la acción para la política actual.