Algoritmos para el control de aprendizaje
Contenido
Aunque el tema de la exploración se tiene en cuenta, e incluso si el estado era observable (que asumimos a partir de ahora), el problema sigue siendo saber qué acciones son buenas basadas en la experiencia pasada.
Criterio de optimalidad
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 , Que por lo tanto podemos asignar el retorno esperado a la política : donde la variable aleatoria denota el retorno y se define por: donde es la recompensa recibida después de la -ésima transición, el estado inicial se realiza un muestreo al azar de y las acciones son seleccionados por la política . Aquí, 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,: dando lugar a la esperado criterio de recompensa para un descuento total. 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.
Fuerza bruta
El enfoque por fuerza bruta implica las dos etapas siguientes:.
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.
Acercamiento al valor de la función
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 por: donde significa el regreso al azar asociado con las siguientes desde el estado inicial . Se define como el valor máximo posible de , en donde se le permite cambiar: 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 , desde , en donde es un estado de la muestra al azar de la distribución . Aunque los valores de estado son suficientes para definir el óptimo, que demostrará ser útil para definir la acción-valores. Dado un estado , Una acción y una política de , La acción-valor del par bajo se define por: donde, ahora, significa el retorno aleatorio asociado con la primera toma de acción en el estado de y siguiendo ,, a partir de entonces. Es bien conocido a partir de la teoría de los PDM que si alguien nos da 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 . 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 () Que convergen a .
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 , el objetivo es calcular los valores de la función (O una buena aproximación a ellas) para todos los pares estado-acción . 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 se puede calcular simplemente el promedio de los rendimientos de la muestra que se originaron a partir de Dado el tiempo suficiente, este procedimiento puede así construir una estimación precisa de la función de la acción-valor . 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 : Dado un estado , la nueva política devuelve una acción que maximiza . 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:.
Búsqueda política directa
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 , dado denotar la política asociada a . Definir la función de rendimiento por: Bajo condiciones suaves esta función será diferenciable como una función del vector de parámetros . Si el gradiente de 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.