Aprendizaje por refuerzo

Para simplificar, supongamos por un momento que el problema estudiado es episódico, un episodio que termina cuando se alcanza un estado terminal. Supongamos, además, que no importa el curso de las acciones que toma el agente, la terminación es inevitable. Bajo ciertas condiciones de regularidad adicional está entonces bien definida la expectativa de la recompensa total para cualquier política y cualquier distribución inicial sobre los estados. En este sentido, una política se refiere a una asignación de cierta distribución de probabilidad sobre las acciones a todas las historias posibles. Dada una distribución inicial fija ${\displaystyle \mu }$, Que por lo tanto podemos asignar el retorno esperado ${\displaystyle \rho ^{\pi }}$ a la política ${\displaystyle \pi }$:${\displaystyle \rho ^{\pi }=E[R|\pi ],}$ donde la variable aleatoria ${\displaystyle R}$ denota el retorno y se define por:${\displaystyle R=\sum _{t=0}^{N-1}r_{t+1},}$ donde ${\displaystyle r_{t+1}}$ es la recompensa recibida después de la ${\displaystyle t}$-ésima transición, el estado inicial se realiza un muestreo al azar de ${\displaystyle \mu }$ y las acciones son seleccionados por la política ${\displaystyle \pi }$. Aquí, ${\displaystyle N}$ denota el tiempo aleatorio cuando se alcanza un estado terminal, es decir, el momento en que el episodio termina. En el caso de problemas no episódicos el retorno a menudo se descuenta,:${\displaystyle R=\sum _{t=0}^{\infty }\gamma ^{t}r_{t+1},}$ dando lugar a la esperado criterio de recompensa para un descuento total. ${\displaystyle 0\leq \gamma \leq 1}$ es el llamado factor de descuento. Desde el retorno sin descontar es un caso especial de la devolución de descuento, a partir de ahora asumiremos el descuento. Aunque esto parece bastante inocente, el descuento es de hecho un problema si uno se preocupa por el rendimiento en línea. Esto se debe a que el descuento hace que el tiempo inicial de los pasos más importantes. Puesto que un agente de aprendizaje es probable que cometa errores durante los primeros pasos después de sus inicios "vida", ningún algoritmo de aprendizaje desinformado puede lograr un rendimiento casi óptimo en el descuento, incluso si la clase de entornos está restringida a la de PDM finitos. (Esto no significa sin embargo que, dado el tiempo suficiente, un agente de aprendizaje no puede entender cómo actuar casi de forma óptima, si el tiempo se ha reiniciado.) El problema entonces es especificar un algoritmo que puede ser usado para encontrar una póliza con el máximo rendimiento esperado. De la teoría de la PDM se sabe que, sin pérdida de generalidad, la búsqueda puede ser restringida al conjunto de las llamadas políticas estacionarias. Una política se llama estacionaria si la acción de distribución que devuelve solo depende del último estado visitado (que es parte de la historia de la observación del agente, por nuestro supuesto simplificador). De hecho, la búsqueda se puede restringir aún más a las políticas estacionarias deterministas. Una política estacionaria determinista es aquella que selecciona de manera determinista acciones basadas en el estado actual. Desde cualquiera de estas políticas puede ser identificadas con una correspondencia entre el conjunto de estados en el conjunto de acciones, estas políticas se pueden identificar con este tipo de asignaciones, sin pérdida de generalidad.

El enfoque por fuerza bruta implica las dos etapas siguientes:

1. Para cada política posible, muestrear resultados.
2. Elija la política con el mayor retorno esperado.

Un problema con esto es que el número de políticas puede ser extremadamente grande, o incluso infinito. Otra es que la varianza de los rendimientos podría ser grande, en cuyo caso se requiere un gran número de muestras para estimar con precisión el retorno de cada política. Estos problemas se pueden aliviar utilizamos alguna estructura y permitir que las muestras sean generadas a partir de una política para influir en las estimaciones realizadas por otro. Los dos enfoques principales para conseguirlo son función de la estimación del valor y la búsqueda de políticas directas.

Las funciones de valor intentan encontrar una política que maximice el retorno al mantener un conjunto de estimaciones de los rendimientos esperados por alguna política (por lo general, ya sea la "corriente" o la óptima). Estos métodos se basan en la teoría de los PDM, donde optimalidad se define en un sentido que es más fuerte que los anteriores: Una política se llama óptima si se logra un mejor rendimiento esperado en cualquier estado inicial (es decir, las distribuciones iniciales no juegan ningún papel en esta definición). Una vez más, siempre se puede encontrar una política óptima entre las políticas estacionarias. Para definir la optimalidad de una manera formal, definir el valor de una política ${\displaystyle \pi }$ por: ${\displaystyle V^{\pi }(s)=E[R|s,\pi ],}$ donde ${\displaystyle R}$ significa el regreso al azar asociado con las siguientes ${\displaystyle \pi }$ desde el estado inicial ${\displaystyle s}$. Se define ${\displaystyle V^{*}(s)}$ como el valor máximo posible de ${\displaystyle V^{\pi }(s)}$, en donde ${\displaystyle \pi }$ se le permite cambiar: ${\displaystyle V^{*}(s)=\sup \limits _{\pi }V^{\pi }(s).}$ Una política que alcanza estos valores óptimos en cada estado se llama óptima. Es evidente que una política óptima en este sentido fuerte también es óptima en el sentido de que maximiza el rendimiento esperado ${\displaystyle \rho ^{\pi }}$, desde ${\displaystyle \rho ^{\pi }=E[V^{\pi }(S)]}$, en donde ${\displaystyle S}$ es un estado de la muestra al azar de la distribución ${\displaystyle \mu }$. Aunque los valores de estado son suficientes para definir el óptimo, que demostrará ser útil para definir la acción-valores. Dado un estado ${\displaystyle s}$, Una acción ${\displaystyle a}$ y una política de ${\displaystyle \pi }$, La acción-valor del par ${\displaystyle (s,a)}$ bajo ${\displaystyle \pi }$ se define por:${\displaystyle Q^{\pi }(s,a)=E[R|s,a,\pi ],\,}$ donde, ahora, ${\displaystyle R}$ significa el retorno aleatorio asociado con la primera toma de acción ${\displaystyle a}$ en el estado de ${\displaystyle s}$ y siguiendo ${\displaystyle \pi }$,, a partir de entonces. Es bien conocido a partir de la teoría de los PDM que si alguien nos da ${\displaystyle Q}$ para una política óptima, siempre podemos optar por acciones óptimas simplemente eligiendo la acción con el valor más alto en cada estado. La función de acción-valor de una política óptima se llama la función óptima acción-valor y se representa por ${\displaystyle Q^{*}}$. Suponiendo pleno conocimiento de la MDP, hay dos enfoques básicos para calcular la función óptima acción del valor, valor de iteración y la política de repetición. Ambos algoritmos calcular una secuencia de funciones ${\displaystyle Q_{k}}$ (${\displaystyle k=0,1,2,\ldots ,}$) Que convergen a ${\displaystyle Q^{*}}$.

Los Método de Montecarlo más simples se pueden usar en un algoritmo que imita políticas de iteración. La política de iteración consta de dos etapas: la evaluación y mejora. Los Método de Montecarlo se utilizan en la etapa de evaluación. En este paso, dado, la política determinista estacionaria ${\displaystyle \pi }$, el objetivo es calcular los valores de la función ${\displaystyle Q^{\pi }(s,a)}$ (O una buena aproximación a ellas) para todos los pares estado-acción ${\displaystyle (s,a)}$. Supongamos (por simplicidad) que el MDP es finito y que hay una tabla de acciones por estados en la memoria. Además, se supone que el problema es episódico y después de cada episodio uno nuevo comienza a partir de un estado inicial aleatorio. Entonces, la estimación del valor de un par estado-acción determinada ${\displaystyle (s,a)}$se puede calcular simplemente el promedio de los rendimientos de la muestra que se originaron a partir de ${\displaystyle (s,a)}$Dado el tiempo suficiente, este procedimiento puede así construir una estimación precisa ${\displaystyle Q}$ de la función de la acción-valor ${\displaystyle Q^{\pi }}$. Aquí termina la descripción de la etapa de evaluación de políticas. En la etapa de mejora de las políticas, como se hace en el algoritmo de iteración, la siguiente política se obtiene mediante el cálculo de una política greedy con respecto a ${\displaystyle Q}$: Dado un estado ${\displaystyle s}$, la nueva política devuelve una acción que maximiza ${\displaystyle Q(s,\cdot )}$. En la práctica a menudo se evita el cómputo y el almacenamiento de la nueva política, pero utiliza la evaluación perezosa para aplazar el cómputo de las acciones que maximizan cuando realmente sea necesario. Este procedimiento puede acarrear algunos problemas como los siguientes:

• Se puede perder mucho tiempo en la evaluación de una política subóptima;
• Utilizar muestras de manera ineficiente
• Cuando las trayectorias tienen una alta varianza, la convergencia será lenta;
• Funciona solo en los problemas episódicos;
• Actúa en solo MDPs pequeños y finitos.

El primer problema se puede corregir fácilmente, permitiendo que el procedimiento pueda cambiar la política (en todos, o en algunos estados) antes de que los valores se establezcan. Por muy bueno que parezca, esto puede ser peligroso, ya que esto podría impedir la convergencia. Sin embargo, la mayoría de los algoritmos actuales implementan esta idea, dando lugar a la clase de algoritmo de iteración política generalizada. Observamos de pasada que el actor crítico métodos pertenecen a esta categoría. El segundo problema se puede corregir en el algoritmo, permitiendo trayectorias para contribuir a cualquier par estado-acción en ellos. Esto también puede ayudar, hasta cierto punto con el tercer problema, aunque una solución mejor cuando los rendimientos tienen alta varianza es utilizar diferencia temporal de Sutton (TD) métodos que se basan en la recursiva ecuación de Bellman. Tenga en cuenta que el cálculo en métodos TD puede ser incrementales (cuando después de cada transición de la memoria se cambia y la transición se desecha), o por lotes (cuando se recogen las transiciones y luego las estimaciones se calculan una vez sobre la base de un gran número de transiciones). El métodos por lotes, un excelente ejemplo de lo que es el método de mínimos cuadrados diferencia temporal debido al Bradtke and Barto(1996), puede utilizar la información de las muestras mejor, mientras que los métodos incrementales son la única opción cuando los métodos de proceso por lotes se convierten en inviable debido a su alta computacional o la complejidad de la memoria. Además, existen métodos que tratan de unificar las ventajas de los dos enfoques. Con el fin de abordar la última cuestión mencionada en el apartado anterior, se utilizan métodos de aproximación de funciones. En la aproximación función lineal se parte de una asignación ${\displaystyle \phi }$ que asigna un vector de dimensión finita a cada par estado-acción. Entonces, los valores de acción de un par estado-acción ${\displaystyle (s,a)}$ se obtienen mediante la combinación lineal de los componentes ${\displaystyle \phi (s,a)}$ con algunos pesos ${\displaystyle \theta }$::${\displaystyle Q(s,a)=\sum \limits _{i=1}^{d}\theta _{i}\phi _{i}(s,a)}$. La aproximación lineal de la función no es la única opción. Más recientemente, los métodos basados en las ideas de estadística no paramétrica se han explorado (que se pueden ver para construir sus propias características). Hasta ahora, la discusión se limita a la forma de iteración política se puede utilizar como base de los algoritmos de aprendizaje de refuerzo diseño. Igualmente importante, el valor de iteración también se puede utilizar como punto de partida, dando lugar al algoritmo Q-aprendizaje (Watkins 1989) y sus muchas variantes. El problema con los métodos que utilizan los valores de acción es que es posible que necesiten estimaciones muy precisas de los valores de acción de la competencia, que pueden ser difíciles de obtener cuando los rendimientos son ruidosos. Aunque este problema se mitiga en cierta medida por métodos de diferencias temporales y si se utiliza el llamado método de aproximación de funciones compatibles, queda mucho trabajo por hacer para aumentar la generalidad y la eficiencia. Otro problema específico de los métodos de diferencia temporal viene de su dependencia de la ecuación de Bellman recursiva. La mayoría de los métodos de diferencias temporales han llamado así a ${\displaystyle \lambda }$ parámetro ${\displaystyle (0\leq \lambda \leq 1)}$ que permite a interpolar de forma continua entre los métodos de Monte-Carlo (que no se basan en las ecuaciones de Bellman) y los métodos de diferencias temporales básicas (que se basan exclusivamente en las ecuaciones de Bellman), que pueden por lo tanto ser eficaz para paliar este problema.

Un método alternativo para encontrar una buena política es buscar directamente en (algún subconjunto) del espacio de la política, en cuyo caso el problema se convierte en una instancia de optimización estocástica. Los dos enfoques disponibles se basan en el gradiente y métodos de gradiente libre. Métodos basados en gradiente (que dan lugar a los denominados métodos de política gradiente) comienzan con una asignación de un (parámetro) espacio de dimensión finita al espacio de políticas: dado el vector de parámetros ${\displaystyle \theta }$, dado ${\displaystyle \pi _{\theta }}$ denotar la política asociada a ${\displaystyle \theta }$. Definir la función de rendimiento por: ${\displaystyle \rho (\theta )=\rho ^{\pi _{\theta }}.}$ Bajo condiciones suaves esta función será diferenciable como una función del vector de parámetros ${\displaystyle \theta }$. Si el gradiente de ${\displaystyle \rho }$ era conocido, se podría utilizar gradiente de ascenso. Desde una expresión analítica para el gradiente no está disponible, uno debe confiar en una estimación ruidosa. Tal estimación puede construirse de muchas maneras, dando lugar a algoritmos como el método Williams' Reinforce. Una gran clase de métodos evita confiar en la información de gradiente. Estos incluyen el recocido simulado, búsqueda de entropía cruzada o métodos de computación evolutiva. Muchos métodos de gradiente libre pueden alcanzar (en la teoría y en el límite) de un óptimo global. En un número de casos que de hecho han demostrado un rendimiento notable. El problema con los métodos de búsqueda es que pueden converger lentamente si la información basada en el que actúan es ruidosa. Por ejemplo, esto sucede cuando está en problemas episódicos las trayectorias son largas y la varianza de los retornos es grande. Como se ha argumentado antes, los métodos basados en el valor de funciones que se basan en diferencias temporales podrían ayudar en este caso. En los últimos años se han propuesto varios algoritmos actor y crítico siguiendo esta idea y han demostrado un buen desempeño en diversos problemas.